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