RDKit
Open-source cheminformatics and machine learning.
hanoiSort.h
Go to the documentation of this file.
1 //
2 // Copyright (C) 2014 Greg Landrum
3 // Adapted from pseudo-code from Roger Sayle
4 //
5 // @@ All Rights Reserved @@
6 // This file is part of the RDKit.
7 // The contents are covered by the terms of the BSD license
8 // which is included in the file license.txt, found at the root
9 // of the RDKit source tree.
10 //
11 
12 #ifndef HANOISORT_H_
13 #define HANOISORT_H_
14 
15 #include <cstring>
16 #include <iostream>
17 #include <cassert>
18 #include <cstdlib>
19 
20 namespace RDKit {
21  template <typename CompareFunc>
22  bool hanoi( int* base, int nel, int *temp, int *count, int *changed, CompareFunc compar ) {
23  //std::cerr<<" hanoi: "<<nel<< " start " << (*base)+1 << std::endl;
24  register int *b1,*b2;
25  register int *t1,*t2;
26  register int *s1,*s2;
27  register int n1,n2;
28  register int result;
29  register int *ptr;
30 
31  if( nel == 1 ) {
32  count[base[0]] = 1;
33  return false;
34  } else if( nel == 2 ) {
35  n1 = base[0];
36  n2 = base[1];
37  int stat = (/*!changed || */changed[n1]||changed[n2]) ? compar(n1,n2) : 0;
38  if( stat == 0 ) {
39  count[n1] = 2;
40  count[n2] = 0;
41  return false;
42  } else if( stat < 0 ) {
43  count[n1] = 1;
44  count[n2] = 1;
45  return false;
46  } else /* stat > 0 */ {
47  count[n1] = 1;
48  count[n2] = 1;
49  base[0] = n2; /* temp[0] = n2; */
50  base[1] = n1; /* temp[1] = n1; */
51  return false; /* return True; */
52  }
53  }
54 
55  n1 = nel/2; n2 = nel-n1;
56  b1 = base; t1 = temp;
57  b2 = base+n1; t2 = temp+n1;
58 
59  if( hanoi(b1,n1,t1,count,changed,compar) ) {
60  if( hanoi(b2,n2,t2,count,changed,compar) ) {
61  s2 = t2;
62  } else s2 = b2;
63  result = false;
64  ptr = base;
65  s1 = t1;
66  } else {
67  if( hanoi(b2,n2,t2,count,changed,compar) ) {
68  s2 = t2;
69  } else s2 = b2;
70  result = true;
71  ptr = temp;
72  s1 = b1;
73  }
74 
75  while( true ) {
76  assert(*s1!=*s2);
77  int stat = (/*!changed || */changed[*s1]||changed[*s2]) ? compar(*s1,*s2) : 0;
78  int len1 = count[*s1];
79  int len2 = count[*s2];
80  assert(len1>0);
81  assert(len2>0);
82  if( stat == 0 ) {
83  count[*s1] = len1+len2;
84  count[*s2] = 0;
85  memmove(ptr,s1,len1*sizeof(int));
86  ptr += len1; n1 -= len1;
87  if( n1 == 0 ) {
88  if( ptr != s2 )
89  memmove(ptr,s2,n2*sizeof(int));
90  return result;
91  }
92  s1 += len1;
93 
94  //std::cerr<<" cpy: "<<*s1<<" "<<*s2<<" "<<len2<<std::endl;
95  memmove(ptr,s2,len2*sizeof(int));
96  ptr += len2; n2 -= len2;
97  if( n2 == 0 ) {
98  memmove(ptr,s1,n1*sizeof(int));
99  return result;
100  }
101  s2 += len2;
102  } else if( stat < 0 && len1>0 ) {
103  memmove(ptr,s1,len1*sizeof(int));
104  ptr += len1; n1 -= len1;
105  if( n1 == 0 ) {
106  if( ptr != s2 )
107  memmove(ptr,s2,n2*sizeof(int));
108  return result;
109  }
110  s1 += len1;
111  } else if (stat > 0 && len2>0) /* stat > 0 */ {
112  memmove(ptr,s2,len2*sizeof(int));
113  ptr += len2; n2 -= len2;
114  if( n2 == 0 ) {
115  memmove(ptr,s1,n1*sizeof(int));
116  return result;
117  }
118  s2 += len2;
119  } else {
120  assert(0);
121  }
122  }
123  }
124 
125  template <typename CompareFunc>
126  void hanoisort( int* base, int nel, int *count, int *changed, CompareFunc compar )
127  {
128  register int *temp;
129 
130  temp = (int*)malloc(nel*sizeof(int));
131  if( hanoi(base,nel,temp,count,changed,compar) )
132  memmove(base,temp,nel*sizeof(int));
133  free(temp);
134  }
135 }
136 
137 #endif /* HANOISORT_H_ */
void hanoisort(int *base, int nel, int *count, int *changed, CompareFunc compar)
Definition: hanoiSort.h:126
Includes a bunch of functionality for handling Atom and Bond queries.
Definition: Atom.h:28
bool hanoi(int *base, int nel, int *temp, int *count, int *changed, CompareFunc compar)
Definition: hanoiSort.h:22