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, either version 3 of the License, or
12 * (at your option) any later version.
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
19 * You should have received a copy of the GNU General Public License
20 * along with this program. If not, see <http://www.gnu.org/licenses/>.
22 module iv
.aatree
/*is aliced*/;
27 // ////////////////////////////////////////////////////////////////////////// //
28 final class AATree(TKey
, TValue
, bool stableIter
=true) if (is(typeof((TKey a
, TKey b
) => a
< b || a
> b
))) {
30 enum HEIGHT_LIMIT
= 64; // tallest allowable tree
35 static if (stableIter
) enum HasNodeList
= true; else enum HasNodeList
= false;
37 static if (is(TKey
== string
)) enum KeyIsString
= true; else enum KeyIsString
= false;
38 static if (is(TValue
== string
)) enum ValueIsString
= true; else enum ValueIsString
= false;
40 static if (is(TKey
== struct)) enum KeyIsStruct
= true; else enum KeyIsStruct
= false;
41 static if (is(TValue
== struct)) enum ValueIsStruct
= true; else enum ValueIsStruct
= false;
43 private static template ArgPfx(bool isStruct
) {
44 static if (isStruct
) enum ArgPfx
= "auto ref"; else enum ArgPfx
= "";
47 static final class Node
{
49 static if (is(typeof((TKey n
) => n
.clone()))) enum HasKeyClone
= true; else enum HasKeyClone
= false;
50 static if (is(typeof((TValue n
) => n
.clone()))) enum HasValueClone
= true; else enum HasValueClone
= false;
52 static if (is(typeof((TKey n
) { n
.release(); }))) enum HasKeyRelease
= true; else enum HasKeyRelease
= false;
53 static if (is(typeof((TValue n
) { n
.release(); }))) enum HasValueRelease
= true; else enum HasValueRelease
= false;
55 int level
; // horizontal level for balance
58 Node
[2] link
; // left (0) and right (1) links
59 static if (stableIter
) { public Node prev
, next
; }
61 // create sentinel node
63 //value = null; // simplifies some ops
65 link
.ptr
[Left
] = link
.ptr
[Right
] = this;
68 private enum ThisBodyMixin
= q
{
70 link
.ptr
[Left
] = link
.ptr
[Right
] = tree
.nil
;
71 static if (HasKeyClone
) {
72 static if (is(typeof(akey
is null))) {
73 if (akey
!is null) key
= akey
.clone();
80 static if (HasValueClone
) {
81 static if (is(typeof(avalue
is null))) {
82 if (avalue
!is null) value
= avalue
.clone();
84 value
= avalue
.clone();
92 mixin("this() (AATree tree, "~ArgPfx
!KeyIsStruct
~" TKey akey, "~ArgPfx
!ValueIsStruct
~" TValue avalue) {"~ThisBodyMixin
~"}");
95 //pragma(inline, true);
96 static if (HasKeyRelease
) {
97 static if (is(typeof(key
is null))) {
98 if (key
!is null) key
.release();
103 static if (HasValueRelease
) {
104 static if (is(typeof(value
is null))) {
105 if (value
!is null) value
.release();
114 Node root
; // top of the tree
115 Node nil
; // end of tree sentinel
116 usize treeSize
; // number of items (user-defined)
117 ulong modFrame
; // to invalidate walkers
119 static if (stableIter
) {
122 void addNodeToList (Node n
) {
123 pragma(inline
, true);
125 if (tail
!is null) tail
.next
= n
;
127 if (head
is null) head
= n
;
130 void removeNodeFromList (Node n
) {
131 pragma(inline
, true);
132 if (n
.prev
!is null) n
.prev
.next
= n
.next
; else head
= n
.next
;
133 if (n
.next
!is null) n
.next
.prev
= n
.prev
; else tail
= n
.prev
;
134 assert(head
is null || head
.prev
is null);
135 assert(tail
is null || tail
.next
is null);
138 Node
firstNode () { pragma(inline
, true); return head
; }
139 Node
lastNode () { pragma(inline
, true); return tail
; }
141 auto byNodes(bool fromHead
=true) () {
142 //alias TreeType = typeof(this);
143 static struct Iterator(bool fromHead
) {
146 Node it
; // current node
147 ulong modFrame
; // to sync with owner tree
149 this (AATree atree
) {
151 modFrame
= atree
.modFrame
;
152 static if (fromHead
) it
= tree
.firstNode
; else it
= tree
.lastNode
;
155 @property bool empty () const pure { pragma(inline
, true); return (it
is null || it
is tree
.nil || modFrame
!= tree
.modFrame
); }
156 @property Node
front () pure { pragma(inline
, true); return it
; }
157 @property auto save () @trusted {
158 pragma(inline
, true);
159 typeof(this) res
= void;
162 res
.modFrame
= modFrame
;
166 if (empty
) { it
= null; tree
= null; return; }
167 static if (fromHead
) it
= it
.next
; else it
= it
.prev
;
168 if (empty
) { it
= null; tree
= null; return; }
171 return Iterator
!fromHead(this);
174 alias fromFirstNode
= byNodes
!true;
175 alias fromLastNode
= byNodes
!false;
178 debug usize
maxTreeDepth () {
180 void descend (Node n
, usize depth
) {
181 if (n
is null || n
is nil
) {
182 if (depth
-1 > maxdepth
) maxdepth
= depth
-1;
185 descend(n
.link
[0], depth
+1);
186 descend(n
.link
[1], depth
+1);
194 // initialize sentinel
195 nil
= new Node(this);
201 ~this () { clear(); }
206 // destruction by rotation
208 if (it
.link
.ptr
[Left
] is nil
) {
210 save
= it
.link
.ptr
[Right
];
212 static if (stableIter
) removeNodeFromList(it
);
216 save
= it
.link
.ptr
[Left
];
217 it
.link
.ptr
[Left
] = save
.link
.ptr
[Right
];
218 save
.link
.ptr
[Right
] = it
;
223 // finalize destruction
229 private enum FindBodyMixin
= q
{
232 int cmp = (it
.key
< key ?
-1 : it
.key
> key ?
1 : 0);
234 it
= it
.link
.ptr
[(cmp < 0 ? Right
: Left
)];
237 return (it
!is nil ? it
: null);
240 static if (KeyIsString
) {
241 Node
find() (const(char)[] key
) { mixin(FindBodyMixin
); }
242 Node
opBinaryRight(string op
: "in") (const(char)[] key
) { pragma(inline
, true); return find(key
); }
244 mixin("Node find() ("~ArgPfx
!KeyIsStruct
~" TKey key) { "~FindBodyMixin
~" }");
245 mixin("Node opBinaryRight(string op : `in`) ("~ArgPfx
!KeyIsStruct
~" TKey key) { pragma(inline, true); return find(key); }");
249 private enum InsertBodyMixin
= q
{
252 static if (KeyIsString
) { static if (!is(TK
== string
)) { auto dkey
= key
.idup
; } else { alias dkey
= key
; } } else { alias dkey
= key
; }
253 static if (ValueIsString
) { static if (!is(TV
== string
)) { auto dvalue
= value
.idup
; } else { alias dvalue
= value
; } } else { alias dvalue
= value
; }
254 root
= new Node(this, dkey
, dvalue
);
255 static if (stableIter
) addNodeToList(root
);
256 //if (root is nil) return false;
259 Node
[HEIGHT_LIMIT
] path
;
261 // find a spot and save the path
264 dir
= (it
.key
< key ? Right
: Left
);
265 if (it
.link
.ptr
[dir
] is nil
) break;
266 it
= it
.link
.ptr
[dir
];
269 static if (KeyIsString
) { static if (!is(TK
== string
)) { auto dkey
= key
.idup
; } else { alias dkey
= key
; } } else { alias dkey
= key
; }
270 static if (ValueIsString
) { static if (!is(TV
== string
)) { auto dvalue
= value
.idup
; } else { alias dvalue
= value
; } } else { alias dvalue
= value
; }
271 it
.link
.ptr
[dir
] = new Node(this, dkey
, dvalue
);
272 static if (stableIter
) addNodeToList(it
.link
.ptr
[dir
]);
273 //if (it.link.ptr[dir] is nil) return false;
274 // walk back and rebalance
277 if (top
!= 0) dir
= (path
[top
-1].link
.ptr
[Right
] is path
[top
] ? Right
: Left
);
278 mixin(skew
!"path[top]");
279 mixin(split
!"path[top]");
282 path
[top
-1].link
.ptr
[dir
] = path
[top
];
293 static if (KeyIsString
&& ValueIsString
) {
294 bool insert(TK
, TV
) (TK key
, TV value
) if (is(TK
: const(char)[]) && is(TV
: const(char)[])) { mixin(InsertBodyMixin
); }
295 } else static if (KeyIsString
) {
296 mixin("bool insert(TK) (TK key, "~ArgPfx
!ValueIsStruct
~" TValue value) if (is(TK : const(char)[])) { "~InsertBodyMixin
~" }");
297 } else static if (ValueIsString
) {
298 mixin("bool insert(TV) ("~ArgPfx
!KeyIsStruct
~" TKey key, TV value) if (is(TV : const(char)[])) { "~InsertBodyMixin
~" }");
300 mixin("bool insert() ("~ArgPfx
!KeyIsStruct
~" TKey key, "~ArgPfx
!ValueIsStruct
~" TValue value) { "~InsertBodyMixin
~" }");
304 private enum RemoveBodyMixin
= q
{
305 if (root
is nil
) return false;
307 Node
[HEIGHT_LIMIT
] path
;
308 int top
= 0, dir
, cmp;
309 // find node to remove and save path
312 if (it
is nil
) return false;
313 cmp = (it
.key
< key ?
-1 : it
.key
> key ?
1 : 0);
315 dir
= (cmp < 0 ? Right
: Left
);
316 it
= it
.link
.ptr
[dir
];
318 // remove the found node
319 if (it
.link
.ptr
[Left
] is nil || it
.link
.ptr
[Right
] is nil
) {
321 int dir2
= (it
.link
.ptr
[Left
] is nil ? Right
: Left
);
324 path
[top
-1].link
.ptr
[dir
] = it
.link
.ptr
[dir2
];
326 root
= it
.link
.ptr
[Right
];
329 static if (stableIter
) removeNodeFromList(it
);
333 auto heir
= it
.link
.ptr
[Right
];
335 while (heir
.link
.ptr
[Left
] !is nil
) {
336 path
[top
++] = prev
= heir
;
337 heir
= heir
.link
.ptr
[Left
];
339 // order is important!
340 // (free item, replace item, free heir)
343 it
.value
= heir
.value
;
344 prev
.link
.ptr
[(prev
is it ? Right
: Left
)] = heir
.link
.ptr
[Right
];
345 static if (stableIter
) {
346 // replace `heir` with `it` in node list
347 removeNodeFromList(it
);
351 if (it
.prev
!is null) it
.prev
.next
= it
; else head
= it
;
352 if (it
.next
!is null) it
.next
.prev
= it
; else tail
= it
;
356 // walk back up and rebalance
359 if (top
!= 0) dir
= (path
[top
-1].link
.ptr
[Right
] is up ? Right
: Left
);
360 // rebalance (aka. black magic)
361 if (up
.link
.ptr
[Left
].level
< up
.level
-1 || up
.link
.ptr
[Right
].level
< up
.level
-1) {
362 if (up
.link
.ptr
[Right
].level
> --up
.level
) up
.link
.ptr
[Right
].level
= up
.level
;
363 // order is important!
365 mixin(skew
!"up.link.ptr[Right]");
366 mixin(skew
!"up.link.ptr[Right].link.ptr[Right]");
368 mixin(split
!"up.link.ptr[Right]");
372 path
[top
-1].link
.ptr
[dir
] = up
;
382 static if (KeyIsString
) {
383 bool remove() (const(char)[] key
) { mixin(RemoveBodyMixin
); }
385 mixin("bool remove() ("~ArgPfx
!KeyIsStruct
~" TKey key) { "~RemoveBodyMixin
~" }");
388 usize
size () const pure nothrow @safe @nogc { pragma(inline
, true); return treeSize
; }
390 auto fromMin () { pragma(inline
, true); return Walker(this, Left
); }
391 auto fromMax () { pragma(inline
, true); return Walker(this, Right
); }
394 // remove left horizontal links
395 enum skew(string t
) = "{\n"~
396 " if ("~t
~".link.ptr[Left].level == "~t
~".level && "~t
~".level != 0) {\n"~
397 " auto save = "~t
~".link.ptr[Left];\n"~
398 " "~t
~".link.ptr[Left] = save.link.ptr[Right];\n"~
399 " save.link.ptr[Right] = "~t
~";\n"~
404 // remove consecutive horizontal links
405 enum split(string t
) = "{\n"~
406 " if ("~t
~".link.ptr[Right].link.ptr[Right].level == "~t
~".level && "~t
~".level != 0) {\n"~
407 " auto save = "~t
~".link.ptr[Right];\n"~
408 " "~t
~".link.ptr[Right] = save.link.ptr[Left];\n"~
409 " save.link.ptr[Left] = "~t
~";\n"~
415 static struct Walker
{
416 nothrow @trusted @nogc:
418 AATree tree
; // paired tree
419 Node it
; // current node
420 Node
[HEIGHT_LIMIT
] path
; // traversal path (actually, pointer to Node)
421 usize top
; // top of stack
422 int curdir
; // direction
423 ulong modFrame
; // to sync with owner tree
427 this (AATree atree
, int dir
) {
430 modFrame
= tree
.modFrame
;
436 it
= it
.link
.ptr
[curdir
];
438 if (top
) it
= path
[top
-1];
441 @property bool empty () const pure { pragma(inline
, true); return (tree
is null || it
is tree
.nil || modFrame
!= tree
.modFrame
); }
442 Node
front () pure { pragma(inline
, true); return it
; }
444 @property auto save () {
451 res
.modFrame
= modFrame
;
455 // if TOS is it: now we should go opposite dir
456 // go opposite dir: pop TOS (we shouldn't return there)
458 if (tree
is null || modFrame
!= tree
.modFrame || it
is tree
.nil || top
== 0) { top
= 0; it
= tree
.nil
; tree
= null; return; }
460 if (it
is path
[top
-1]) {
461 // we should go right, and pop this branch
463 it
= it
.link
.ptr
[curdir^
1];
466 // stepped right branch, now go left again
467 it
= it
.link
.ptr
[curdir
];
471 if (top
) it
= path
[top
-1];
472 if (it
is tree
.nil
) { tree
= null; }
475 @property bool toMin () const pure { pragma(inline
, true); return (curdir
!= Left
); }
476 @property bool toMax () const pure { pragma(inline
, true); return (curdir
== Left
); }
482 // ////////////////////////////////////////////////////////////////////////// //
484 import std
.stdio
: writeln
;
487 void checkIterators(AATree) (AATree tree, int[] values) {
488 import std.conv : to;
490 { import std.stdio; writeln("*** size=", tree.size); }
491 foreach (/+auto+/ n; tree.fromMin) {
492 { import std.stdio; writeln(" curK=", curK, "; values[", curK, "]=", values[curK]); }
493 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])~")");
494 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])~")");
497 curK = cast(int)tree.size;
498 { import std.stdio; writeln(" curK=", curK, "; size=", tree.size); }
499 foreach (/+auto+/ n; tree.fromMax) {
501 { import std.stdio; writeln(" curK=", curK, "; values[", curK, "]=", values[curK]); }
502 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])~")");
503 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])~")");
508 void checkIterators(AATree
) (AATree tree
) {
509 import std
.conv
: to
;
510 //int curK = int.min, curV = int.min;
513 auto it = tree.fromMin();
516 writeln(" k=", it.front.key, "; v=", it.front.value);
520 { import std.stdio; writeln("---"); }
521 { auto it = tree.fromMax(); while (!it.empty) { import std.stdio; writeln(" k=", it.front.key, "; v=", it.front.value); it.popFront(); } }
523 int count
= 0, ln
= int.min
;
524 { auto it
= tree
.fromMin(); while (!it
.empty
) { assert(it
.front
.key
> ln
); ln
= it
.front
.key
; ++count
; it
.popFront(); } }
525 assert(count
== tree
.size
);
528 { auto it
= tree
.fromMax(); while (!it
.empty
) { assert(it
.front
.key
< ln
); ln
= it
.front
.key
; ++count
; it
.popFront(); } }
529 assert(count
== tree
.size
);
531 //{ import std.stdio; writeln(" ** size=", tree.size); }
532 foreach (/*auto*/ n
; tree
.fromMin
) {
533 //if (n.key <= curK) assert(0, "(0)Invalid key for key "~to!string(curK)~" ("~to!string(n.key)~","~to!string(n.value)~")");
534 //if (n.value <= curV) assert(0, "(0)Invalid value for key "~to!string(curK)~" ("~to!string(n.key)~","~to!string(n.value)~")");
540 //{ import std.stdio; writeln(" keys=", keys); writeln(" values=", values); }
541 foreach (/*auto*/ n
; tree
.fromMax
) {
542 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
)~")");
543 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
)~")");
545 values
= values
[0..$-1];
549 void test (int[] values
) {
550 import std
.conv
: to
;
551 //{ import std.stdio; writeln("*** len=", values.length); }
552 auto tree
= new AATree
!(int, int, true)();
554 static if (tree
.HasNodeList
) {
555 void checkNodeList () {
556 auto n
= tree
.firstNode
;
560 //if (n.key <= ln) { import std.stdio; writeln("ln=", ln, "; key=", n.key); }
561 //assert(n.key > ln);
566 ///*if (count != tree.size)*/ { import std.stdio; writeln("count=", count, "; size=", tree.size); }
567 assert(count
== tree
.size
);
572 //assert(n.key < ln);
577 import std
.range
: enumerate
;
578 assert(count
== tree
.size
);
580 foreach (/*auto*/ idx
, /*auto*/ nn
; tree
.fromFirstNode
.enumerate
) { assert(count
== idx
); ++count
; }
581 assert(count
== tree
.size
);
583 foreach (/*auto*/ idx
, /*auto*/ nn
; tree
.fromLastNode
.enumerate
) { assert(count
== idx
); ++count
; }
584 assert(count
== tree
.size
);
585 if (count
!= tree
.size
) { import std
.stdio
; writeln("count=", count
, "; size=", tree
.size
); }
588 void checkNodeList () {}
591 for (int i
= 0; i
< values
.length
; ++i
) {
592 if (!tree
.insert(values
[i
], i
+1)) assert(0, "Failed to insert {0}"~to
!string(values
[i
]));
593 if (auto n
= tree
.find(values
[i
])) {
594 if (n
.value
!= i
+1) assert(0, "Invalid value for key "~to
!string(values
[i
]));
596 assert(0, "Could not find key "~to
!string(values
[i
]));
598 checkIterators(tree
);
601 checkIterators(tree
);
603 for (int i
= 0; i
< values
.length
; ++i
) {
604 for (int j
= 0; j
< i
; j
++) {
605 if (tree
.find(values
[j
])) assert(0, "Found deleted key {0}"~to
!string(values
[j
]));
607 for (int j
= i
; j
< values
.length
; j
++) {
608 if (auto n
= tree
.find(values
[j
])) {
609 if (n
.value
!= j
+1) assert(0, "Invalid value for key {0}"~to
!string(values
[j
]));
611 assert(0, "Could not find key {0}"~to
!string(values
[j
]));
614 if (!tree
.remove(values
[i
])) assert(0, "Failed to delete {0}"~to
!string(values
[i
]));
615 checkIterators(tree
);
620 writeln("test00 (0)");
660 writeln("test00 (1)");
661 foreach (int count
; 0..1000) {
662 auto a
= new int[](100);
663 for (int i
= 0; i
< a
.length
; ++i
) {
667 import std
.random
: uniform
;
669 r
= uniform
!"[]"(r
.min
, r
.max
);
670 for (int j
= 0; j
< i
; ++j
) {
671 if (a
[j
] == r
) { dup
= true; break; }
681 // ////////////////////////////////////////////////////////////////////////// //
685 static final class Data
{
690 this (usize aidx
, string aword
) { idx
= aidx
; word
= aword
; }
693 //writeln("cloning #", idx, "[", word, "](", cloneCount, "+1)");
694 auto res
= new Data(idx
, word
);
695 res
.cloneCount
= cloneCount
+1;
700 //writeln("releasing #", idx, "[", word, "](", cloneCount, ")");
706 auto tree
= new AATree
!(string
, Data
, true);
708 writeln("creating tree...");
710 foreach (string line
; File("/usr/share/dict/words").byLineCopy
) {
715 import std
.random
: randomShuffle
, uniform
;
718 foreach (immutable idx
, string w
; words
) tree
.insert(w
, new Data(idx
, w
));
720 debug { writeln("tree items: ", tree
.size
, "; max tree depth: ", tree
.maxTreeDepth
); }
722 char[] key
= "supernatural".dup
;
725 key
= "motherfucker".dup
;
726 assert(key
!in tree
);
727 tree
.insert(key
, new Data(words
.length
, key
.idup
));
733 foreach (/*auto*/ node
; tree
.fromMin
) {
734 assert(ww
.length
== 0 || ww
< node
.key
);
739 foreach (/*auto*/ node
; tree
.fromMax
) {
740 assert(ww
.length
== 0 || ww
> node
.key
);
744 import std
.range
: enumerate
;
746 foreach (immutable idx
, /*auto*/ node
; tree
.fromFirstNode
.enumerate
) assert(node
.key
== words
[idx
]);
747 foreach (immutable idx
, /*auto*/ node
; tree
.fromLastNode
.enumerate
) assert(node
.key
== words
[words
.length
-idx
-1]);
752 writeln("removing elements from tree...");
755 while (words
.length
!= 0) {
756 if (count
++%128 == 0) {
757 stdout
.write("\r", words
.length
, " items left\x1b[K");
760 import std
.algorithm
.mutation
: remove
;
761 auto idx
= uniform
!"[)"(0, words
.length
);
763 words
= words
.remove(idx
);
764 if (!tree
.remove(cast(const(char)[])w
)) assert(0, "boo!");
767 stdout
.writeln("\r0 items left\x1b[K");
769 writeln("clearing tree...");
774 // ////////////////////////////////////////////////////////////////////////// //