egra: agg will respect clip rect now
[iv.d.git] / aatree.d
blob4c38c8db6c8dd1e64f894d32eb7e32fc81e338cf
1 /*
2 * Invisible Vector Library
3 * Andersson tree library
5 * based on the code from Julienne Walker
6 * further coded by Ketmar // Invisible Vector <ketmar@ketmar.no-ip.org>
7 * Understanding is not required. Only obedience.
9 * This program is free software: you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation, version 3 of the License ONLY.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program. If not, see <http://www.gnu.org/licenses/>.
21 module iv.aatree /*is aliced*/;
23 import iv.alice;
26 // ////////////////////////////////////////////////////////////////////////// //
27 final class AATree(TKey, TValue, bool stableIter=true) if (is(typeof((TKey a, TKey b) => a < b || a > b))) {
28 public:
29 enum HEIGHT_LIMIT = 64; // tallest allowable tree
31 private:
32 enum Left = 0;
33 enum Right = 1;
34 static if (stableIter) enum HasNodeList = true; else enum HasNodeList = false;
36 static if (is(TKey == string)) enum KeyIsString = true; else enum KeyIsString = false;
37 static if (is(TValue == string)) enum ValueIsString = true; else enum ValueIsString = false;
39 static if (is(TKey == struct)) enum KeyIsStruct = true; else enum KeyIsStruct = false;
40 static if (is(TValue == struct)) enum ValueIsStruct = true; else enum ValueIsStruct = false;
42 private static template ArgPfx(bool isStruct) {
43 static if (isStruct) enum ArgPfx = "auto ref"; else enum ArgPfx = "";
46 static final class Node {
47 private:
48 static if (is(typeof((TKey n) => n.clone()))) enum HasKeyClone = true; else enum HasKeyClone = false;
49 static if (is(typeof((TValue n) => n.clone()))) enum HasValueClone = true; else enum HasValueClone = false;
51 static if (is(typeof((TKey n) { n.release(); }))) enum HasKeyRelease = true; else enum HasKeyRelease = false;
52 static if (is(typeof((TValue n) { n.release(); }))) enum HasValueRelease = true; else enum HasValueRelease = false;
54 int level; // horizontal level for balance
55 public TKey key;
56 public TValue value;
57 Node[2] link; // left (0) and right (1) links
58 static if (stableIter) { public Node prev, next; }
60 // create sentinel node
61 this (AATree tree) {
62 //value = null; // simplifies some ops
63 level = 0;
64 link.ptr[Left] = link.ptr[Right] = this;
67 private enum ThisBodyMixin = q{
68 level = 1;
69 link.ptr[Left] = link.ptr[Right] = tree.nil;
70 static if (HasKeyClone) {
71 static if (is(typeof(akey is null))) {
72 if (akey !is null) key = akey.clone();
73 } else {
74 key = akey.clone();
76 } else {
77 key = akey;
79 static if (HasValueClone) {
80 static if (is(typeof(avalue is null))) {
81 if (avalue !is null) value = avalue.clone();
82 } else {
83 value = avalue.clone();
85 } else {
86 value = avalue;
90 // create normal node
91 mixin("this() (AATree tree, "~ArgPfx!KeyIsStruct~" TKey akey, "~ArgPfx!ValueIsStruct~" TValue avalue) {"~ThisBodyMixin~"}");
93 void release () {
94 //pragma(inline, true);
95 static if (HasKeyRelease) {
96 static if (is(typeof(key is null))) {
97 if (key !is null) key.release();
98 } else {
99 key.release();
102 static if (HasValueRelease) {
103 static if (is(typeof(value is null))) {
104 if (value !is null) value.release();
105 } else {
106 value.release();
112 private:
113 Node root; // top of the tree
114 Node nil; // end of tree sentinel
115 usize treeSize; // number of items (user-defined)
116 ulong modFrame; // to invalidate walkers
118 static if (stableIter) {
119 Node head, tail;
121 void addNodeToList (Node n) {
122 pragma(inline, true);
123 n.prev = tail;
124 if (tail !is null) tail.next = n;
125 tail = n;
126 if (head is null) head = n;
129 void removeNodeFromList (Node n) {
130 pragma(inline, true);
131 if (n.prev !is null) n.prev.next = n.next; else head = n.next;
132 if (n.next !is null) n.next.prev = n.prev; else tail = n.prev;
133 assert(head is null || head.prev is null);
134 assert(tail is null || tail.next is null);
137 Node firstNode () { pragma(inline, true); return head; }
138 Node lastNode () { pragma(inline, true); return tail; }
140 auto byNodes(bool fromHead=true) () {
141 //alias TreeType = typeof(this);
142 static struct Iterator(bool fromHead) {
143 nothrow @safe @nogc:
144 AATree tree;
145 Node it; // current node
146 ulong modFrame; // to sync with owner tree
148 this (AATree atree) {
149 tree = atree;
150 modFrame = atree.modFrame;
151 static if (fromHead) it = tree.firstNode; else it = tree.lastNode;
154 @property bool empty () const pure { pragma(inline, true); return (it is null || it is tree.nil || modFrame != tree.modFrame); }
155 @property Node front () pure { pragma(inline, true); return it; }
156 @property auto save () @trusted {
157 pragma(inline, true);
158 typeof(this) res = void;
159 res.tree = tree;
160 res.it = it;
161 res.modFrame = modFrame;
162 return res;
164 void popFront () {
165 if (empty) { it = null; tree = null; return; }
166 static if (fromHead) it = it.next; else it = it.prev;
167 if (empty) { it = null; tree = null; return; }
170 return Iterator!fromHead(this);
173 alias fromFirstNode = byNodes!true;
174 alias fromLastNode = byNodes!false;
177 debug usize maxTreeDepth () {
178 usize maxdepth = 0;
179 void descend (Node n, usize depth) {
180 if (n is null || n is nil) {
181 if (depth-1 > maxdepth) maxdepth = depth-1;
182 return;
184 descend(n.link[0], depth+1);
185 descend(n.link[1], depth+1);
187 descend(root, 0);
188 return maxdepth;
191 public:
192 this () {
193 // initialize sentinel
194 nil = new Node(this);
195 // initialize tree
196 root = nil;
197 treeSize = 0;
200 ~this () { clear(); }
202 void clear () {
203 auto it = root;
204 Node save;
205 // destruction by rotation
206 while (it !is nil) {
207 if (it.link.ptr[Left] is nil) {
208 // remove node
209 save = it.link.ptr[Right];
210 it.release();
211 static if (stableIter) removeNodeFromList(it);
212 //free(it);
213 } else {
214 // rotate right
215 save = it.link.ptr[Left];
216 it.link.ptr[Left] = save.link.ptr[Right];
217 save.link.ptr[Right] = it;
219 it = save;
221 ++modFrame;
222 // finalize destruction
223 //free(this.nil);
224 //free(this);
228 private enum FindBodyMixin = q{
229 auto it = root;
230 while (it !is nil) {
231 int cmp = (it.key < key ? -1 : it.key > key ? 1 : 0);
232 if (cmp == 0) break;
233 it = it.link.ptr[(cmp < 0 ? Right : Left)];
235 // nil.value == null
236 return (it !is nil ? it : null);
239 static if (KeyIsString) {
240 Node find() (const(char)[] key) { mixin(FindBodyMixin); }
241 Node opBinaryRight(string op : "in") (const(char)[] key) { pragma(inline, true); return find(key); }
242 } else {
243 mixin("Node find() ("~ArgPfx!KeyIsStruct~" TKey key) { "~FindBodyMixin~" }");
244 mixin("Node opBinaryRight(string op : `in`) ("~ArgPfx!KeyIsStruct~" TKey key) { pragma(inline, true); return find(key); }");
248 private enum InsertBodyMixin = q{
249 if (root is nil) {
250 // empty this case
251 static if (KeyIsString) { static if (!is(TK == string)) { auto dkey = key.idup; } else { alias dkey = key; } } else { alias dkey = key; }
252 static if (ValueIsString) { static if (!is(TV == string)) { auto dvalue = value.idup; } else { alias dvalue = value; } } else { alias dvalue = value; }
253 root = new Node(this, dkey, dvalue);
254 static if (stableIter) addNodeToList(root);
255 //if (root is nil) return false;
256 } else {
257 auto it = root;
258 Node[HEIGHT_LIMIT] path;
259 int top = 0, dir;
260 // find a spot and save the path
261 for (;;) {
262 path[top++] = it;
263 dir = (it.key < key ? Right : Left);
264 if (it.link.ptr[dir] is nil) break;
265 it = it.link.ptr[dir];
267 // create a new item
268 static if (KeyIsString) { static if (!is(TK == string)) { auto dkey = key.idup; } else { alias dkey = key; } } else { alias dkey = key; }
269 static if (ValueIsString) { static if (!is(TV == string)) { auto dvalue = value.idup; } else { alias dvalue = value; } } else { alias dvalue = value; }
270 it.link.ptr[dir] = new Node(this, dkey, dvalue);
271 static if (stableIter) addNodeToList(it.link.ptr[dir]);
272 //if (it.link.ptr[dir] is nil) return false;
273 // walk back and rebalance
274 while (--top >= 0) {
275 // which child?
276 if (top != 0) dir = (path[top-1].link.ptr[Right] is path[top] ? Right : Left);
277 mixin(skew!"path[top]");
278 mixin(split!"path[top]");
279 // fix the parent
280 if (top != 0) {
281 path[top-1].link.ptr[dir] = path[top];
282 } else {
283 root = path[top];
287 ++treeSize;
288 ++modFrame;
289 return true;
292 static if (KeyIsString && ValueIsString) {
293 bool insert(TK, TV) (TK key, TV value) if (is(TK : const(char)[]) && is(TV : const(char)[])) { mixin(InsertBodyMixin); }
294 } else static if (KeyIsString) {
295 mixin("bool insert(TK) (TK key, "~ArgPfx!ValueIsStruct~" TValue value) if (is(TK : const(char)[])) { "~InsertBodyMixin~" }");
296 } else static if (ValueIsString) {
297 mixin("bool insert(TV) ("~ArgPfx!KeyIsStruct~" TKey key, TV value) if (is(TV : const(char)[])) { "~InsertBodyMixin~" }");
298 } else {
299 mixin("bool insert() ("~ArgPfx!KeyIsStruct~" TKey key, "~ArgPfx!ValueIsStruct~" TValue value) { "~InsertBodyMixin~" }");
303 private enum RemoveBodyMixin = q{
304 if (root is nil) return false;
305 auto it = root;
306 Node[HEIGHT_LIMIT] path;
307 int top = 0, dir, cmp;
308 // find node to remove and save path
309 for (;;) {
310 path[top++] = it;
311 if (it is nil) return false;
312 cmp = (it.key < key ? -1 : it.key > key ? 1 : 0);
313 if (cmp == 0) break;
314 dir = (cmp < 0 ? Right : Left);
315 it = it.link.ptr[dir];
317 // remove the found node
318 if (it.link.ptr[Left] is nil || it.link.ptr[Right] is nil) {
319 // single child case
320 int dir2 = (it.link.ptr[Left] is nil ? Right : Left);
321 // unlink the item
322 if (--top != 0) {
323 path[top-1].link.ptr[dir] = it.link.ptr[dir2];
324 } else {
325 root = it.link.ptr[Right];
327 it.release();
328 static if (stableIter) removeNodeFromList(it);
329 //free(it);
330 } else {
331 // two child case
332 auto heir = it.link.ptr[Right];
333 auto prev = it;
334 while (heir.link.ptr[Left] !is nil) {
335 path[top++] = prev = heir;
336 heir = heir.link.ptr[Left];
338 // order is important!
339 // (free item, replace item, free heir)
340 it.release();
341 it.key = heir.key;
342 it.value = heir.value;
343 prev.link.ptr[(prev is it ? Right : Left)] = heir.link.ptr[Right];
344 static if (stableIter) {
345 // replace `heir` with `it` in node list
346 removeNodeFromList(it);
347 it.prev = heir.prev;
348 it.next = heir.next;
349 // patch nodes
350 if (it.prev !is null) it.prev.next = it; else head = it;
351 if (it.next !is null) it.next.prev = it; else tail = it;
353 //free(heir);
355 // walk back up and rebalance
356 while (--top >= 0) {
357 auto up = path[top];
358 if (top != 0) dir = (path[top-1].link.ptr[Right] is up ? Right : Left);
359 // rebalance (aka. black magic)
360 if (up.link.ptr[Left].level < up.level-1 || up.link.ptr[Right].level < up.level-1) {
361 if (up.link.ptr[Right].level > --up.level) up.link.ptr[Right].level = up.level;
362 // order is important!
363 mixin(skew!"up");
364 mixin(skew!"up.link.ptr[Right]");
365 mixin(skew!"up.link.ptr[Right].link.ptr[Right]");
366 mixin(split!"up");
367 mixin(split!"up.link.ptr[Right]");
369 // fix the parent
370 if (top != 0) {
371 path[top-1].link.ptr[dir] = up;
372 } else {
373 root = up;
376 --treeSize;
377 ++modFrame;
378 return true;
381 static if (KeyIsString) {
382 bool remove() (const(char)[] key) { mixin(RemoveBodyMixin); }
383 } else {
384 mixin("bool remove() ("~ArgPfx!KeyIsStruct~" TKey key) { "~RemoveBodyMixin~" }");
387 usize size () const pure nothrow @safe @nogc { pragma(inline, true); return treeSize; }
389 auto fromMin () { pragma(inline, true); return Walker(this, Left); }
390 auto fromMax () { pragma(inline, true); return Walker(this, Right); }
392 static private:
393 // remove left horizontal links
394 enum skew(string t) = "{\n"~
395 " if ("~t~".link.ptr[Left].level == "~t~".level && "~t~".level != 0) {\n"~
396 " auto save = "~t~".link.ptr[Left];\n"~
397 " "~t~".link.ptr[Left] = save.link.ptr[Right];\n"~
398 " save.link.ptr[Right] = "~t~";\n"~
399 " "~t~" = save;\n"~
400 " }\n"~
401 "}";
403 // remove consecutive horizontal links
404 enum split(string t) = "{\n"~
405 " if ("~t~".link.ptr[Right].link.ptr[Right].level == "~t~".level && "~t~".level != 0) {\n"~
406 " auto save = "~t~".link.ptr[Right];\n"~
407 " "~t~".link.ptr[Right] = save.link.ptr[Left];\n"~
408 " save.link.ptr[Left] = "~t~";\n"~
409 " "~t~" = save;\n"~
410 " ++"~t~".level;\n"~
411 " }\n"~
412 "}";
414 static struct Walker {
415 nothrow @trusted @nogc:
416 private:
417 AATree tree; // paired tree
418 Node it; // current node
419 Node[HEIGHT_LIMIT] path; // traversal path (actually, pointer to Node)
420 usize top; // top of stack
421 int curdir; // direction
422 ulong modFrame; // to sync with owner tree
424 public:
425 // 0: min; 1: max
426 this (AATree atree, int dir) {
427 tree = atree;
428 curdir = !!dir;
429 modFrame = tree.modFrame;
430 top = 0;
431 auto nil = tree.nil;
432 it = tree.root;
433 while (it !is nil) {
434 path[top++] = it;
435 it = it.link.ptr[curdir];
437 if (top) it = path[top-1];
440 @property bool empty () const pure { pragma(inline, true); return (tree is null || it is tree.nil || modFrame != tree.modFrame); }
441 Node front () pure { pragma(inline, true); return it; }
443 @property auto save () {
444 Walker res = void;
445 res.tree = tree;
446 res.it = it;
447 res.path[] = path[];
448 res.top = top;
449 res.curdir = curdir;
450 res.modFrame = modFrame;
451 return res;
454 // if TOS is it: now we should go opposite dir
455 // go opposite dir: pop TOS (we shouldn't return there)
456 void popFront () {
457 if (tree is null || modFrame != tree.modFrame || it is tree.nil || top == 0) { top = 0; it = tree.nil; tree = null; return; }
458 auto nil = tree.nil;
459 if (it is path[top-1]) {
460 // we should go right, and pop this branch
461 --top;
462 it = it.link.ptr[curdir^1];
463 while (it !is nil) {
464 path[top++] = it;
465 // stepped right branch, now go left again
466 it = it.link.ptr[curdir];
469 // use stack top
470 if (top) it = path[top-1];
471 if (it is tree.nil) { tree = null; }
474 @property bool toMin () const pure { pragma(inline, true); return (curdir != Left); }
475 @property bool toMax () const pure { pragma(inline, true); return (curdir == Left); }
480 version(aat_test) {
481 // ////////////////////////////////////////////////////////////////////////// //
482 void test00 () {
483 import std.stdio : writeln;
486 void checkIterators(AATree) (AATree tree, int[] values) {
487 import std.conv : to;
488 int curK = 0;
489 { import std.stdio; writeln("*** size=", tree.size); }
490 foreach (/+auto+/ n; tree.fromMin) {
491 { import std.stdio; writeln(" curK=", curK, "; values[", curK, "]=", values[curK]); }
492 if (n.key != values[curK]) assert(0, "(0)Invalid key for key "~to!string(curK)~" ("~to!string(n.key)~","~to!string(n.value)~" : "~to!string(values[curK])~")");
493 if (n.value != curK+1) assert(0, "(0)Invalid value for key "~to!string(curK)~" ("~to!string(n.key)~","~to!string(n.value)~" : "~to!string(values[curK])~")");
494 ++curK;
496 curK = cast(int)tree.size;
497 { import std.stdio; writeln(" curK=", curK, "; size=", tree.size); }
498 foreach (/+auto+/ n; tree.fromMax) {
499 --curK;
500 { import std.stdio; writeln(" curK=", curK, "; values[", curK, "]=", values[curK]); }
501 if (n.key != values[curK]) assert(0, "(1)Invalid key for key "~to!string(curK)~" ("~to!string(n.key)~","~to!string(n.value)~" : "~to!string(values[curK])~")");
502 if (n.value != curK+1) assert(0, "(1)Invalid value for key "~to!string(curK)~" ("~to!string(n.key)~","~to!string(n.value)~" : "~to!string(values[curK])~")");
507 void checkIterators(AATree) (AATree tree) {
508 import std.conv : to;
509 //int curK = int.min, curV = int.min;
512 auto it = tree.fromMin();
513 while (!it.empty) {
514 import std.stdio;
515 writeln(" k=", it.front.key, "; v=", it.front.value);
516 it.popFront();
519 { import std.stdio; writeln("---"); }
520 { auto it = tree.fromMax(); while (!it.empty) { import std.stdio; writeln(" k=", it.front.key, "; v=", it.front.value); it.popFront(); } }
522 int count = 0, ln = int.min;
523 { auto it = tree.fromMin(); while (!it.empty) { assert(it.front.key > ln); ln = it.front.key; ++count; it.popFront(); } }
524 assert(count == tree.size);
525 count = 0;
526 ln = int.max;
527 { auto it = tree.fromMax(); while (!it.empty) { assert(it.front.key < ln); ln = it.front.key; ++count; it.popFront(); } }
528 assert(count == tree.size);
529 int[] keys, values;
530 //{ import std.stdio; writeln(" ** size=", tree.size); }
531 foreach (/*auto*/ n; tree.fromMin) {
532 //if (n.key <= curK) assert(0, "(0)Invalid key for key "~to!string(curK)~" ("~to!string(n.key)~","~to!string(n.value)~")");
533 //if (n.value <= curV) assert(0, "(0)Invalid value for key "~to!string(curK)~" ("~to!string(n.key)~","~to!string(n.value)~")");
534 keys ~= n.key;
535 values ~= n.value;
536 //curK = n.key;
537 //curV = n.value;
539 //{ import std.stdio; writeln(" keys=", keys); writeln(" values=", values); }
540 foreach (/*auto*/ n; tree.fromMax) {
541 if (n.key != keys[$-1]) assert(0, "(1)Invalid key for key "~to!string(keys.length-1)~" ("~to!string(n.key)~","~to!string(n.value)~")");
542 if (n.value != values[$-1]) assert(0, "(1)Invalid value for key "~to!string(keys.length-1)~" ("~to!string(n.key)~","~to!string(n.value)~")");
543 keys = keys[0..$-1];
544 values = values[0..$-1];
548 void test (int[] values) {
549 import std.conv : to;
550 //{ import std.stdio; writeln("*** len=", values.length); }
551 auto tree = new AATree!(int, int, true)();
553 static if (tree.HasNodeList) {
554 void checkNodeList () {
555 auto n = tree.firstNode;
556 int count = 0;
557 //auto ln = int.min;
558 while (n !is null) {
559 //if (n.key <= ln) { import std.stdio; writeln("ln=", ln, "; key=", n.key); }
560 //assert(n.key > ln);
561 //ln = n.key;
562 n = n.next;
563 ++count;
565 ///*if (count != tree.size)*/ { import std.stdio; writeln("count=", count, "; size=", tree.size); }
566 assert(count == tree.size);
567 n = tree.lastNode;
568 count = 0;
569 //ln = int.max;
570 while (n !is null) {
571 //assert(n.key < ln);
572 //ln = n.key;
573 n = n.prev;
574 ++count;
576 import std.range : enumerate;
577 assert(count == tree.size);
578 count = 0;
579 foreach (/*auto*/ idx, /*auto*/ nn; tree.fromFirstNode.enumerate) { assert(count == idx); ++count; }
580 assert(count == tree.size);
581 count = 0;
582 foreach (/*auto*/ idx, /*auto*/ nn; tree.fromLastNode.enumerate) { assert(count == idx); ++count; }
583 assert(count == tree.size);
584 if (count != tree.size) { import std.stdio; writeln("count=", count, "; size=", tree.size); }
586 } else {
587 void checkNodeList () {}
590 for (int i = 0; i < values.length; ++i) {
591 if (!tree.insert(values[i], i+1)) assert(0, "Failed to insert {0}"~to!string(values[i]));
592 if (auto n = tree.find(values[i])) {
593 if (n.value != i+1) assert(0, "Invalid value for key "~to!string(values[i]));
594 } else {
595 assert(0, "Could not find key "~to!string(values[i]));
597 checkIterators(tree);
598 checkNodeList();
600 checkIterators(tree);
601 checkNodeList();
602 for (int i = 0; i < values.length; ++i) {
603 for (int j = 0; j < i; j++) {
604 if (tree.find(values[j])) assert(0, "Found deleted key {0}"~to!string(values[j]));
606 for (int j = i; j < values.length; j++) {
607 if (auto n = tree.find(values[j])) {
608 if (n.value != j+1) assert(0, "Invalid value for key {0}"~to!string(values[j]));
609 } else {
610 assert(0, "Could not find key {0}"~to!string(values[j]));
613 if (!tree.remove(values[i])) assert(0, "Failed to delete {0}"~to!string(values[i]));
614 checkIterators(tree);
615 checkNodeList();
619 writeln("test00 (0)");
620 test([1, 2, 3, 4]);
622 test([1]);
624 test([1, 2]);
625 test([2, 1]);
627 test([1, 2, 3]);
628 test([2, 1, 3]);
629 test([1, 3, 2]);
630 test([2, 3, 1]);
631 test([3, 1, 2]);
632 test([3, 2, 1]);
634 test([1, 2, 3, 4]);
635 test([2, 1, 3, 4]);
636 test([1, 3, 2, 4]);
637 test([2, 3, 1, 4]);
638 test([3, 1, 2, 4]);
639 test([3, 2, 1, 4]);
640 test([1, 2, 4, 3]);
641 test([2, 1, 4, 3]);
642 test([1, 3, 4, 2]);
643 test([2, 3, 4, 1]);
644 test([3, 1, 4, 2]);
645 test([3, 2, 4, 1]);
646 test([1, 4, 2, 3]);
647 test([2, 4, 1, 3]);
648 test([1, 4, 3, 2]);
649 test([2, 4, 3, 1]);
650 test([3, 4, 1, 2]);
651 test([3, 4, 2, 1]);
652 test([4, 1, 2, 3]);
653 test([4, 2, 1, 3]);
654 test([4, 1, 3, 2]);
655 test([4, 2, 3, 1]);
656 test([4, 3, 1, 2]);
657 test([4, 3, 2, 1]);
659 writeln("test00 (1)");
660 foreach (int count; 0..1000) {
661 auto a = new int[](100);
662 for (int i = 0; i < a.length; ++i) {
663 int r;
664 bool dup;
665 do {
666 import std.random : uniform;
667 dup = false;
668 r = uniform!"[]"(r.min, r.max);
669 for (int j = 0; j < i; ++j) {
670 if (a[j] == r) { dup = true; break; }
672 } while (dup);
673 a[i] = r;
675 test(a);
680 // ////////////////////////////////////////////////////////////////////////// //
681 void test01 () {
682 import std.stdio;
684 static final class Data {
685 usize idx;
686 string word;
687 uint cloneCount;
689 this (usize aidx, string aword) { idx = aidx; word = aword; }
691 Data clone () {
692 //writeln("cloning #", idx, "[", word, "](", cloneCount, "+1)");
693 auto res = new Data(idx, word);
694 res.cloneCount = cloneCount+1;
695 return res;
698 void release () {
699 //writeln("releasing #", idx, "[", word, "](", cloneCount, ")");
703 writeln("test01");
705 auto tree = new AATree!(string, Data, true);
707 writeln("creating tree...");
708 string[] words;
709 foreach (string line; File("/usr/share/dict/words").byLineCopy) {
710 assert(line.length);
711 words ~= line;
714 import std.random : randomShuffle, uniform;
715 words.randomShuffle;
717 foreach (immutable idx, string w; words) tree.insert(w, new Data(idx, w));
719 debug { writeln("tree items: ", tree.size, "; max tree depth: ", tree.maxTreeDepth); }
721 char[] key = "supernatural".dup;
722 assert(key in tree);
724 key = "motherfucker".dup;
725 assert(key !in tree);
726 tree.insert(key, new Data(words.length, key.idup));
727 words ~= key.idup;
729 void checkTree () {
730 string ww;
732 foreach (/*auto*/ node; tree.fromMin) {
733 assert(ww.length == 0 || ww < node.key);
734 ww = node.key;
737 ww = null;
738 foreach (/*auto*/ node; tree.fromMax) {
739 assert(ww.length == 0 || ww > node.key);
740 ww = node.key;
743 import std.range : enumerate;
745 foreach (immutable idx, /*auto*/ node; tree.fromFirstNode.enumerate) assert(node.key == words[idx]);
746 foreach (immutable idx, /*auto*/ node; tree.fromLastNode.enumerate) assert(node.key == words[words.length-idx-1]);
749 checkTree();
751 writeln("removing elements from tree...");
753 usize count = 0;
754 while (words.length != 0) {
755 if (count++%128 == 0) {
756 stdout.write("\r", words.length, " items left\x1b[K");
757 stdout.flush();
759 import std.algorithm.mutation : remove;
760 auto idx = uniform!"[)"(0, words.length);
761 auto w = words[idx];
762 words = words.remove(idx);
763 if (!tree.remove(cast(const(char)[])w)) assert(0, "boo!");
764 checkTree();
766 stdout.writeln("\r0 items left\x1b[K");
768 writeln("clearing tree...");
769 tree.clear;
773 // ////////////////////////////////////////////////////////////////////////// //
774 void main () {
775 test00();
776 test01();
779 } // version