hanoiSort.h
Go to the documentation of this file.
//
// Copyright (C) 2014 Greg Landrum
// Adapted from pseudo-code from Roger Sayle
//
// @@ All Rights Reserved @@
// This file is part of the RDKit.
// The contents are covered by the terms of the BSD license
// which is included in the file license.txt, found at the root
// of the RDKit source tree.
//
#ifndef HANOISORT_H_
#define HANOISORT_H_
#include <cstring>
#include <iostream>
#include <cassert>
#include <cstdlib>
namespace RDKit {
template <typename CompareFunc>
bool hanoi( int* base, int nel, int *temp, int *count, int *changed, CompareFunc compar ) {
//std::cerr<<" hanoi: "<<nel<< " start " << (*base)+1 << std::endl;
register int *b1,*b2;
register int *t1,*t2;
register int *s1,*s2;
register int n1,n2;
register int result;
register int *ptr;
if( nel == 1 ) {
count[base[0]] = 1;
return false;
} else if( nel == 2 ) {
n1 = base[0];
n2 = base[1];
int stat = (/*!changed || */changed[n1]||changed[n2]) ? compar(n1,n2) : 0;
if( stat == 0 ) {
count[n1] = 2;
count[n2] = 0;
return false;
} else if( stat < 0 ) {
count[n1] = 1;
count[n2] = 1;
return false;
} else /* stat > 0 */ {
count[n1] = 1;
count[n2] = 1;
base[0] = n2; /* temp[0] = n2; */
base[1] = n1; /* temp[1] = n1; */
return false; /* return True; */
}
}
n1 = nel/2; n2 = nel-n1;
b1 = base; t1 = temp;
b2 = base+n1; t2 = temp+n1;
if( hanoi(b1,n1,t1,count,changed,compar) ) {
if( hanoi(b2,n2,t2,count,changed,compar) ) {
s2 = t2;
} else s2 = b2;
result = false;
ptr = base;
s1 = t1;
} else {
if( hanoi(b2,n2,t2,count,changed,compar) ) {
s2 = t2;
} else s2 = b2;
result = true;
ptr = temp;
s1 = b1;
}
while( true ) {
assert(*s1!=*s2);
int stat = (/*!changed || */changed[*s1]||changed[*s2]) ? compar(*s1,*s2) : 0;
int len1 = count[*s1];
int len2 = count[*s2];
assert(len1>0);
assert(len2>0);
if( stat == 0 ) {
count[*s1] = len1+len2;
count[*s2] = 0;
memmove(ptr,s1,len1*sizeof(int));
ptr += len1; n1 -= len1;
if( n1 == 0 ) {
if( ptr != s2 )
memmove(ptr,s2,n2*sizeof(int));
return result;
}
s1 += len1;
//std::cerr<<" cpy: "<<*s1<<" "<<*s2<<" "<<len2<<std::endl;
memmove(ptr,s2,len2*sizeof(int));
ptr += len2; n2 -= len2;
if( n2 == 0 ) {
memmove(ptr,s1,n1*sizeof(int));
return result;
}
s2 += len2;
} else if( stat < 0 && len1>0 ) {
memmove(ptr,s1,len1*sizeof(int));
ptr += len1; n1 -= len1;
if( n1 == 0 ) {
if( ptr != s2 )
memmove(ptr,s2,n2*sizeof(int));
return result;
}
s1 += len1;
} else if (stat > 0 && len2>0) /* stat > 0 */ {
memmove(ptr,s2,len2*sizeof(int));
ptr += len2; n2 -= len2;
if( n2 == 0 ) {
memmove(ptr,s1,n1*sizeof(int));
return result;
}
s2 += len2;
} else {
assert(0);
}
}
}
template <typename CompareFunc>
void hanoisort( int* base, int nel, int *count, int *changed, CompareFunc compar )
{
register int *temp;
temp = (int*)malloc(nel*sizeof(int));
if( hanoi(base,nel,temp,count,changed,compar) )
memmove(base,temp,nel*sizeof(int));
free(temp);
}
}
#endif /* HANOISORT_H_ */
RDKit::hanoisort
void hanoisort(int *base, int nel, int *count, int *changed, CompareFunc compar)
Definition: hanoiSort.h:126
RDKit
Includes a bunch of functionality for handling Atom and Bond queries.
Definition: Atom.h:28
RDKit::hanoi
bool hanoi(int *base, int nel, int *temp, int *count, int *changed, CompareFunc compar)
Definition: hanoiSort.h:22