RDKit
Open-source cheminformatics and machine learning.
Loading...
Searching...
No Matches
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
25namespace RDKit {
26template <typename CompareFunc>
27bool hanoi(int *base, int nel, int *temp, int *count, int *changed,
29 assert(base);
30 assert(temp);
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
150template <typename CompareFunc>
151void hanoisort(int *base, int nel, int *count, int *changed,
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.
bool rdvalue_is(const RDValue_cast_t)
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