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  result = false;
79  ptr = base;
80  s1 = t1;
81  } else {
82  if (hanoi(b2, n2, t2, count, changed, compar)) {
83  s2 = t2;
84  } else
85  s2 = b2;
86  result = true;
87  ptr = temp;
88  s1 = b1;
89  }
90 
91  while (true) {
92  assert(*s1 != *s2);
93  int stat =
94  (/*!changed || */ changed[*s1] || changed[*s2]) ? compar(*s1, *s2) : 0;
95  int len1 = count[*s1];
96  int len2 = count[*s2];
97  assert(len1 > 0);
98  assert(len2 > 0);
99  if (stat == 0) {
100  count[*s1] = len1 + len2;
101  count[*s2] = 0;
102  memmove(ptr, s1, len1 * sizeof(int));
103  ptr += len1;
104  n1 -= len1;
105  if (n1 == 0) {
106  if (ptr != s2) memmove(ptr, s2, n2 * sizeof(int));
107  return result;
108  }
109  s1 += len1;
110 
111  // std::cerr<<" cpy: "<<*s1<<" "<<*s2<<" "<<len2<<std::endl;
112  memmove(ptr, s2, len2 * sizeof(int));
113  ptr += len2;
114  n2 -= len2;
115  if (n2 == 0) {
116  memmove(ptr, s1, n1 * sizeof(int));
117  return result;
118  }
119  s2 += len2;
120  } else if (stat < 0 && len1 > 0) {
121  memmove(ptr, s1, len1 * sizeof(int));
122  ptr += len1;
123  n1 -= len1;
124  if (n1 == 0) {
125  if (ptr != s2) memmove(ptr, s2, n2 * sizeof(int));
126  return result;
127  }
128  s1 += len1;
129  } else if (stat > 0 && len2 > 0) /* stat > 0 */ {
130  memmove(ptr, s2, len2 * sizeof(int));
131  ptr += len2;
132  n2 -= len2;
133  if (n2 == 0) {
134  memmove(ptr, s1, n1 * sizeof(int));
135  return result;
136  }
137  s2 += len2;
138  } else {
139  assert(0);
140  }
141  }
142 }
143 
144 template <typename CompareFunc>
145 void hanoisort(int *base, int nel, int *count, int *changed,
146  CompareFunc compar) {
147  assert(base);
148  int *temp = (int *)malloc(nel * sizeof(int));
149  assert(temp);
150  if (hanoi(base, nel, temp, count, changed, compar))
151  memmove(base, temp, nel * sizeof(int));
152  free(temp);
153 }
154 } // namespace RDKit
155 
156 #if defined(_MSC_VER)
157 #pragma warning(pop)
158 #endif
159 
160 #endif /* HANOISORT_H_ */
RDKit
Std stuff.
Definition: Atom.h:30
RDKit::hanoi
bool hanoi(int *base, int nel, int *temp, int *count, int *changed, CompareFunc compar)
Definition: hanoiSort.h:27
RDKit::hanoisort
void hanoisort(int *base, int nel, int *count, int *changed, CompareFunc compar)
Definition: hanoiSort.h:145
export.h