aatree.d

   1 /*
   2  * Invisible Vector Library
   3  * Andersson tree library
   4  *
   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.
   8  *
   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.
  12  *
  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.
  17  *
  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/>.
  20  */
  21 module iv.aatree /*is aliced*/;
  22
  23 import iv.alice;
  24
  25
  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
  30
  31 private:
  32   enum Left = 0;
  33   enum Right = 1;
  34   static if (stableIter) enum HasNodeList = true; else enum HasNodeList = false;
  35
  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;
  38
  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;
  41
  42   private static template ArgPfx(bool isStruct) {
  43     static if (isStruct) enum ArgPfx = "auto ref"; else enum ArgPfx = "";
  44   }
  45
  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;
  50
  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;
  53
  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; }
  59
  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;
  65     }
  66
  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();
  75         }
  76       } else {
  77         key = akey;
  78       }
  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();
  84         }
  85       } else {
  86         value = avalue;
  87       }
  88     };
  89
  90     // create normal node
  91     mixin("this() (AATree tree, "~ArgPfx!KeyIsStruct~" TKey akey, "~ArgPfx!ValueIsStruct~" TValue avalue) {"~ThisBodyMixin~"}");
  92
  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();
 100         }
 101       }
 102       static if (HasValueRelease) {
 103         static if (is(typeof(value is null))) {
 104           if (value !is null) value.release();
 105         } else {
 106           value.release();
 107         }
 108       }
 109     }
 110   }
 111
 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
 117
 118   static if (stableIter) {
 119     Node head, tail;
 120
 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;
 127     }
 128
 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);
 135     }
 136
 137     Node firstNode () { pragma(inline, true); return head; }
 138     Node lastNode () { pragma(inline, true); return tail; }
 139
 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
 147
 148         this (AATree atree) {
 149           tree = atree;
 150           modFrame = atree.modFrame;
 151           static if (fromHead) it = tree.firstNode; else it = tree.lastNode;
 152         }
 153
 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;
 163         }
 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; }
 168         }
 169       }
 170       return Iterator!fromHead(this);
 171     }
 172
 173     alias fromFirstNode = byNodes!true;
 174     alias fromLastNode = byNodes!false;
 175   }
 176
 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;
 183       }
 184       descend(n.link[0], depth+1);
 185       descend(n.link[1], depth+1);
 186     }
 187     descend(root, 0);
 188     return maxdepth;
 189   }
 190
 191 public:
 192   this () {
 193     // initialize sentinel
 194     nil = new Node(this);
 195     // initialize tree
 196     root = nil;
 197     treeSize = 0;
 198   }
 199
 200   ~this () { clear(); }
 201
 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;
 218       }
 219       it = save;
 220     }
 221     ++modFrame;
 222     // finalize destruction
 223     //free(this.nil);
 224     //free(this);
 225   }
 226
 227
 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)];
 234     }
 235     // nil.value == null
 236     return (it !is nil ? it : null);
 237   };
 238
 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); }");
 245   }
 246
 247
 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];
 266       }
 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];
 284         }
 285       }
 286     }
 287     ++treeSize;
 288     ++modFrame;
 289     return true;
 290   };
 291
 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~" }");
 300   }
 301
 302
 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];
 316     }
 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];
 326       }
 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];
 337       }
 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;
 352       }
 353       //free(heir);
 354     }
 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]");
 368       }
 369       // fix the parent
 370       if (top != 0) {
 371         path[top-1].link.ptr[dir] = up;
 372       } else {
 373         root = up;
 374       }
 375     }
 376     --treeSize;
 377     ++modFrame;
 378     return true;
 379   };
 380
 381   static if (KeyIsString) {
 382     bool remove() (const(char)[] key) { mixin(RemoveBodyMixin); }
 383   } else {
 384     mixin("bool remove() ("~ArgPfx!KeyIsStruct~" TKey key) { "~RemoveBodyMixin~" }");
 385   }
 386
 387   usize size () const pure nothrow @safe @nogc { pragma(inline, true); return treeSize; }
 388
 389   auto fromMin () { pragma(inline, true); return Walker(this, Left); }
 390   auto fromMax () { pragma(inline, true); return Walker(this, Right); }
 391
 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     "}";
 402
 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     "}";
 413
 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
 423
 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];
 436       }
 437       if (top) it = path[top-1];
 438     }
 439
 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; }
 442
 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;
 452     }
 453
 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];
 467         }
 468       }
 469       // use stack top
 470       if (top) it = path[top-1];
 471       if (it is tree.nil) { tree = null; }
 472     }
 473
 474     @property bool toMin () const pure { pragma(inline, true); return (curdir != Left); }
 475     @property bool toMax () const pure { pragma(inline, true); return (curdir == Left); }
 476   }
 477 }
 478
 479
 480 version(aat_test) {
 481 // ////////////////////////////////////////////////////////////////////////// //
 482 void test00 () {
 483   import std.stdio : writeln;
 484
 485   /*
 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;
 495     }
 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])~")");
 503     }
 504   }
 505   */
 506
 507   void checkIterators(AATree) (AATree tree) {
 508     import std.conv : to;
 509     //int curK = int.min, curV = int.min;
 510     /*
 511     {
 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();
 517       }
 518     }
 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(); } }
 521     */
 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;
 538     }
 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];
 545     }
 546   }
 547
 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)();
 552
 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;
 564         }
 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;
 575         }
 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); }
 585       }
 586     } else {
 587       void checkNodeList () {}
 588     }
 589
 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]));
 596       }
 597       checkIterators(tree);
 598       checkNodeList();
 599     }
 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]));
 605       }
 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]));
 611         }
 612       }
 613       if (!tree.remove(values[i])) assert(0, "Failed to delete {0}"~to!string(values[i]));
 614       checkIterators(tree);
 615       checkNodeList();
 616     }
 617   }
 618
 619   writeln("test00 (0)");
 620   test([1, 2, 3, 4]);
 621
 622   test([1]);
 623
 624   test([1, 2]);
 625   test([2, 1]);
 626
 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]);
 633
 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]);
 658
 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; }
 671         }
 672       } while (dup);
 673       a[i] = r;
 674     }
 675     test(a);
 676   }
 677 }
 678
 679
 680 // ////////////////////////////////////////////////////////////////////////// //
 681 void test01 () {
 682   import std.stdio;
 683
 684   static final class Data {
 685     usize idx;
 686     string word;
 687     uint cloneCount;
 688
 689     this (usize aidx, string aword) { idx = aidx; word = aword; }
 690
 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;
 696     }
 697
 698     void release () {
 699       //writeln("releasing #", idx, "[", word, "](", cloneCount, ")");
 700     }
 701   }
 702
 703   writeln("test01");
 704
 705   auto tree = new AATree!(string, Data, true);
 706
 707   writeln("creating tree...");
 708   string[] words;
 709   foreach (string line; File("/usr/share/dict/words").byLineCopy) {
 710     assert(line.length);
 711     words ~= line;
 712   }
 713
 714   import std.random : randomShuffle, uniform;
 715   words.randomShuffle;
 716
 717   foreach (immutable idx, string w; words) tree.insert(w, new Data(idx, w));
 718
 719   debug { writeln("tree items: ", tree.size, "; max tree depth: ", tree.maxTreeDepth); }
 720
 721   char[] key = "supernatural".dup;
 722   assert(key in tree);
 723
 724   key = "motherfucker".dup;
 725   assert(key !in tree);
 726   tree.insert(key, new Data(words.length, key.idup));
 727   words ~= key.idup;
 728
 729   void checkTree () {
 730     string ww;
 731
 732     foreach (/*auto*/ node; tree.fromMin) {
 733       assert(ww.length == 0 || ww < node.key);
 734       ww = node.key;
 735     }
 736
 737     ww = null;
 738     foreach (/*auto*/ node; tree.fromMax) {
 739       assert(ww.length == 0 || ww > node.key);
 740       ww = node.key;
 741     }
 742
 743     import std.range : enumerate;
 744
 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]);
 747   }
 748
 749   checkTree();
 750
 751   writeln("removing elements from tree...");
 752
 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();
 758     }
 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();
 765   }
 766   stdout.writeln("\r0 items left\x1b[K");
 767
 768   writeln("clearing tree...");
 769   tree.clear;
 770 }
 771
 772
 773 // ////////////////////////////////////////////////////////////////////////// //
 774 void main () {
 775   test00();
 776   test01();
 777 }
 778
 779 } // version