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 #include <RDGeneral/export.h>
13 #ifndef HANOISORT_H_
14 #define HANOISORT_H_
15 
16 #include <cstring>
17 #include <iostream>
18 #include <cassert>
19 #include <cstdlib>
20 
21 #if defined(_MSC_VER)
22 #pragma warning(push, 1)
23 #pragma warning(disable : 4800)
24 #endif
25 namespace RDKit {
26 template <typename CompareFunc>
27 bool hanoi(int *base, int nel, int *temp, int *count, int *changed,
28  CompareFunc compar) {
29  assert(base);
30  assert(temp);
31  assert(count);
32  assert(changed);
33  // std::cerr<<" hanoi: "<<nel<< " start " << (*base)+1 << std::endl;
34  int *b1, *b2;
35  int *t1, *t2;
36  int *s1, *s2;
37  int n1, n2;
38  int result;
39  int *ptr;
40 
41  if (nel == 1) {
42  count[base[0]] = 1;
43  return false;
44  } else if (nel == 2) {
45  n1 = base[0];
46  n2 = base[1];
47  int stat =
48  (/*!changed || */ changed[n1] || changed[n2]) ? compar(n1, n2) : 0;
49  if (stat == 0) {
50  count[n1] = 2;
51  count[n2] = 0;
52  return false;
53  } else if (stat < 0) {
54  count[n1] = 1;
55  count[n2] = 1;
56  return false;
57  } else /* stat > 0 */ {
58  count[n1] = 1;
59  count[n2] = 1;
60  base[0] = n2; /* temp[0] = n2; */
61  base[1] = n1; /* temp[1] = n1; */
62  return false; /* return True; */
63  }
64  }
65 
66  n1 = nel / 2;
67  n2 = nel - n1;
68  b1 = base;
69  t1 = temp;
70  b2 = base + n1;
71  t2 = temp + n1;
72 
73  if (hanoi(b1, n1, t1, count, changed, compar)) {
74  if (hanoi(b2, n2, t2, count, changed, compar)) {
75  s2 = t2;
76  } else {
77  s2 = b2;
78  }
79  result = false;
80  ptr = base;
81  s1 = t1;
82  } else {
83  if (hanoi(b2, n2, t2, count, changed, compar)) {
84  s2 = t2;
85  } else {
86  s2 = b2;
87  }
88  result = true;
89  ptr = temp;
90  s1 = b1;
91  }
92 
93  while (true) {
94  assert(*s1 != *s2);
95  int stat =
96  (/*!changed || */ changed[*s1] || changed[*s2]) ? compar(*s1, *s2) : 0;
97  int len1 = count[*s1];
98  int len2 = count[*s2];
99  assert(len1 > 0);
100  assert(len2 > 0);
101  if (stat == 0) {
102  count[*s1] = len1 + len2;
103  count[*s2] = 0;
104  memmove(ptr, s1, len1 * sizeof(int));
105  ptr += len1;
106  n1 -= len1;
107  if (n1 == 0) {
108  if (ptr != s2) {
109  memmove(ptr, s2, n2 * sizeof(int));
110  }
111  return result;
112  }
113  s1 += len1;
114 
115  // std::cerr<<" cpy: "<<*s1<<" "<<*s2<<" "<<len2<<std::endl;
116  memmove(ptr, s2, len2 * sizeof(int));
117  ptr += len2;
118  n2 -= len2;
119  if (n2 == 0) {
120  memmove(ptr, s1, n1 * sizeof(int));
121  return result;
122  }
123  s2 += len2;
124  } else if (stat < 0 && len1 > 0) {
125  memmove(ptr, s1, len1 * sizeof(int));
126  ptr += len1;
127  n1 -= len1;
128  if (n1 == 0) {
129  if (ptr != s2) {
130  memmove(ptr, s2, n2 * sizeof(int));
131  }
132  return result;
133  }
134  s1 += len1;
135  } else if (stat > 0 && len2 > 0) /* stat > 0 */ {
136  memmove(ptr, s2, len2 * sizeof(int));
137  ptr += len2;
138  n2 -= len2;
139  if (n2 == 0) {
140  memmove(ptr, s1, n1 * sizeof(int));
141  return result;
142  }
143  s2 += len2;
144  } else {
145  assert(0);
146  }
147  }
148 }
149 
150 template <typename CompareFunc>
151 void hanoisort(int *base, int nel, int *count, int *changed,
152  CompareFunc compar) {
153  assert(base);
154  int *temp = (int *)malloc(nel * sizeof(int));
155  assert(temp);
156  if (hanoi(base, nel, temp, count, changed, compar)) {
157  memmove(base, temp, nel * sizeof(int));
158  }
159  free(temp);
160 }
161 } // namespace RDKit
162 
163 #if defined(_MSC_VER)
164 #pragma warning(pop)
165 #endif
166 
167 #endif /* HANOISORT_H_ */
Std stuff.
Definition: Abbreviations.h:19
bool hanoi(int *base, int nel, int *temp, int *count, int *changed, CompareFunc compar)
Definition: hanoiSort.h:27
void hanoisort(int *base, int nel, int *count, int *changed, CompareFunc compar)
Definition: hanoiSort.h:151