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