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, either version 3 of the License, or
  12  * (at your option) any later version.
  13  *
  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.
  18  *
  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/>.
  21  */
  22 module iv.aatree /*is aliced*/;
  23
  24 import iv.alice;
  25
  26
  27 // ////////////////////////////////////////////////////////////////////////// //
  28 final class AATree(TKey, TValue, bool stableIter=true) if (is(typeof((TKey a, TKey b) => a < b || a > b))) {
  29 public:
  30   enum HEIGHT_LIMIT = 64; // tallest allowable tree
  31
  32 private:
  33   enum Left = 0;
  34   enum Right = 1;
  35   static if (stableIter) enum HasNodeList = true; else enum HasNodeList = false;
  36
  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;
  39
  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;
  42
  43   private static template ArgPfx(bool isStruct) {
  44     static if (isStruct) enum ArgPfx = "auto ref"; else enum ArgPfx = "";
  45   }
  46
  47   static final class Node {
  48   private:
  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;
  51
  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;
  54
  55     int level; // horizontal level for balance
  56     public TKey key;
  57     public TValue value;
  58     Node[2] link; // left (0) and right (1) links
  59     static if (stableIter) { public Node prev, next; }
  60
  61     // create sentinel node
  62     this (AATree tree) {
  63       //value = null; // simplifies some ops
  64       level = 0;
  65       link.ptr[Left] = link.ptr[Right] = this;
  66     }
  67
  68     private enum ThisBodyMixin = q{
  69       level = 1;
  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();
  74         } else {
  75           key = akey.clone();
  76         }
  77       } else {
  78         key = akey;
  79       }
  80       static if (HasValueClone) {
  81         static if (is(typeof(avalue is null))) {
  82           if (avalue !is null) value = avalue.clone();
  83         } else {
  84           value = avalue.clone();
  85         }
  86       } else {
  87         value = avalue;
  88       }
  89     };
  90
  91     // create normal node
  92     mixin("this() (AATree tree, "~ArgPfx!KeyIsStruct~" TKey akey, "~ArgPfx!ValueIsStruct~" TValue avalue) {"~ThisBodyMixin~"}");
  93
  94     void release () {
  95       //pragma(inline, true);
  96       static if (HasKeyRelease) {
  97         static if (is(typeof(key is null))) {
  98           if (key !is null) key.release();
  99         } else {
 100           key.release();
 101         }
 102       }
 103       static if (HasValueRelease) {
 104         static if (is(typeof(value is null))) {
 105           if (value !is null) value.release();
 106         } else {
 107           value.release();
 108         }
 109       }
 110     }
 111   }
 112
 113 private:
 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
 118
 119   static if (stableIter) {
 120     Node head, tail;
 121
 122     void addNodeToList (Node n) {
 123       pragma(inline, true);
 124       n.prev = tail;
 125       if (tail !is null) tail.next = n;
 126       tail = n;
 127       if (head is null) head = n;
 128     }
 129
 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);
 136     }
 137
 138     Node firstNode () { pragma(inline, true); return head; }
 139     Node lastNode () { pragma(inline, true); return tail; }
 140
 141     auto byNodes(bool fromHead=true) () {
 142       //alias TreeType = typeof(this);
 143       static struct Iterator(bool fromHead) {
 144       nothrow @safe @nogc:
 145         AATree tree;
 146         Node it; // current node
 147         ulong modFrame; // to sync with owner tree
 148
 149         this (AATree atree) {
 150           tree = atree;
 151           modFrame = atree.modFrame;
 152           static if (fromHead) it = tree.firstNode; else it = tree.lastNode;
 153         }
 154
 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;
 160           res.tree = tree;
 161           res.it = it;
 162           res.modFrame = modFrame;
 163           return res;
 164         }
 165         void popFront () {
 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; }
 169         }
 170       }
 171       return Iterator!fromHead(this);
 172     }
 173
 174     alias fromFirstNode = byNodes!true;
 175     alias fromLastNode = byNodes!false;
 176   }
 177
 178   debug usize maxTreeDepth () {
 179     usize maxdepth = 0;
 180     void descend (Node n, usize depth) {
 181       if (n is null || n is nil) {
 182         if (depth-1 > maxdepth) maxdepth = depth-1;
 183         return;
 184       }
 185       descend(n.link[0], depth+1);
 186       descend(n.link[1], depth+1);
 187     }
 188     descend(root, 0);
 189     return maxdepth;
 190   }
 191
 192 public:
 193   this () {
 194     // initialize sentinel
 195     nil = new Node(this);
 196     // initialize tree
 197     root = nil;
 198     treeSize = 0;
 199   }
 200
 201   ~this () { clear(); }
 202
 203   void clear () {
 204     auto it = root;
 205     Node save;
 206     // destruction by rotation
 207     while (it !is nil) {
 208       if (it.link.ptr[Left] is nil) {
 209         // remove node
 210         save = it.link.ptr[Right];
 211         it.release();
 212         static if (stableIter) removeNodeFromList(it);
 213         //free(it);
 214       } else {
 215         // rotate right
 216         save = it.link.ptr[Left];
 217         it.link.ptr[Left] = save.link.ptr[Right];
 218         save.link.ptr[Right] = it;
 219       }
 220       it = save;
 221     }
 222     ++modFrame;
 223     // finalize destruction
 224     //free(this.nil);
 225     //free(this);
 226   }
 227
 228
 229   private enum FindBodyMixin = q{
 230     auto it = root;
 231     while (it !is nil) {
 232       int cmp = (it.key < key ? -1 : it.key > key ? 1 : 0);
 233       if (cmp == 0) break;
 234       it = it.link.ptr[(cmp < 0 ? Right : Left)];
 235     }
 236     // nil.value == null
 237     return (it !is nil ? it : null);
 238   };
 239
 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); }
 243   } else {
 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); }");
 246   }
 247
 248
 249   private enum InsertBodyMixin = q{
 250     if (root is nil) {
 251       // empty this case
 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;
 257     } else {
 258       auto it = root;
 259       Node[HEIGHT_LIMIT] path;
 260       int top = 0, dir;
 261       // find a spot and save the path
 262       for (;;) {
 263         path[top++] = it;
 264         dir = (it.key < key ? Right : Left);
 265         if (it.link.ptr[dir] is nil) break;
 266         it = it.link.ptr[dir];
 267       }
 268       // create a new item
 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
 275       while (--top >= 0) {
 276         // which child?
 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]");
 280         // fix the parent
 281         if (top != 0) {
 282           path[top-1].link.ptr[dir] = path[top];
 283         } else {
 284           root = path[top];
 285         }
 286       }
 287     }
 288     ++treeSize;
 289     ++modFrame;
 290     return true;
 291   };
 292
 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~" }");
 299   } else {
 300     mixin("bool insert() ("~ArgPfx!KeyIsStruct~" TKey key, "~ArgPfx!ValueIsStruct~" TValue value) { "~InsertBodyMixin~" }");
 301   }
 302
 303
 304   private enum RemoveBodyMixin = q{
 305     if (root is nil) return false;
 306     auto it = root;
 307     Node[HEIGHT_LIMIT] path;
 308     int top = 0, dir, cmp;
 309     // find node to remove and save path
 310     for (;;) {
 311       path[top++] = it;
 312       if (it is nil) return false;
 313       cmp = (it.key < key ? -1 : it.key > key ? 1 : 0);
 314       if (cmp == 0) break;
 315       dir = (cmp < 0 ? Right : Left);
 316       it = it.link.ptr[dir];
 317     }
 318     // remove the found node
 319     if (it.link.ptr[Left] is nil || it.link.ptr[Right] is nil) {
 320       // single child case
 321       int dir2 = (it.link.ptr[Left] is nil ? Right : Left);
 322       // unlink the item
 323       if (--top != 0) {
 324         path[top-1].link.ptr[dir] = it.link.ptr[dir2];
 325       } else {
 326         root = it.link.ptr[Right];
 327       }
 328       it.release();
 329       static if (stableIter) removeNodeFromList(it);
 330       //free(it);
 331     } else {
 332       // two child case
 333       auto heir = it.link.ptr[Right];
 334       auto prev = it;
 335       while (heir.link.ptr[Left] !is nil) {
 336         path[top++] = prev = heir;
 337         heir = heir.link.ptr[Left];
 338       }
 339       // order is important!
 340       // (free item, replace item, free heir)
 341       it.release();
 342       it.key = heir.key;
 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);
 348         it.prev = heir.prev;
 349         it.next = heir.next;
 350         // patch nodes
 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;
 353       }
 354       //free(heir);
 355     }
 356     // walk back up and rebalance
 357     while (--top >= 0) {
 358       auto up = path[top];
 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!
 364         mixin(skew!"up");
 365         mixin(skew!"up.link.ptr[Right]");
 366         mixin(skew!"up.link.ptr[Right].link.ptr[Right]");
 367         mixin(split!"up");
 368         mixin(split!"up.link.ptr[Right]");
 369       }
 370       // fix the parent
 371       if (top != 0) {
 372         path[top-1].link.ptr[dir] = up;
 373       } else {
 374         root = up;
 375       }
 376     }
 377     --treeSize;
 378     ++modFrame;
 379     return true;
 380   };
 381
 382   static if (KeyIsString) {
 383     bool remove() (const(char)[] key) { mixin(RemoveBodyMixin); }
 384   } else {
 385     mixin("bool remove() ("~ArgPfx!KeyIsStruct~" TKey key) { "~RemoveBodyMixin~" }");
 386   }
 387
 388   usize size () const pure nothrow @safe @nogc { pragma(inline, true); return treeSize; }
 389
 390   auto fromMin () { pragma(inline, true); return Walker(this, Left); }
 391   auto fromMax () { pragma(inline, true); return Walker(this, Right); }
 392
 393 static private:
 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"~
 400     "    "~t~" = save;\n"~
 401     "  }\n"~
 402     "}";
 403
 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"~
 410     "    "~t~" = save;\n"~
 411     "    ++"~t~".level;\n"~
 412     "  }\n"~
 413     "}";
 414
 415   static struct Walker {
 416   nothrow @trusted @nogc:
 417   private:
 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
 424
 425   public:
 426     // 0: min; 1: max
 427     this (AATree atree, int dir) {
 428       tree = atree;
 429       curdir = !!dir;
 430       modFrame = tree.modFrame;
 431       top = 0;
 432       auto nil = tree.nil;
 433       it = tree.root;
 434       while (it !is nil) {
 435         path[top++] = it;
 436         it = it.link.ptr[curdir];
 437       }
 438       if (top) it = path[top-1];
 439     }
 440
 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; }
 443
 444     @property auto save () {
 445       Walker res = void;
 446       res.tree = tree;
 447       res.it = it;
 448       res.path[] = path[];
 449       res.top = top;
 450       res.curdir = curdir;
 451       res.modFrame = modFrame;
 452       return res;
 453     }
 454
 455     // if TOS is it: now we should go opposite dir
 456     // go opposite dir: pop TOS (we shouldn't return there)
 457     void popFront () {
 458       if (tree is null || modFrame != tree.modFrame || it is tree.nil || top == 0) { top = 0; it = tree.nil; tree = null; return; }
 459       auto nil = tree.nil;
 460       if (it is path[top-1]) {
 461         // we should go right, and pop this branch
 462         --top;
 463         it = it.link.ptr[curdir^1];
 464         while (it !is nil) {
 465           path[top++] = it;
 466           // stepped right branch, now go left again
 467           it = it.link.ptr[curdir];
 468         }
 469       }
 470       // use stack top
 471       if (top) it = path[top-1];
 472       if (it is tree.nil) { tree = null; }
 473     }
 474
 475     @property bool toMin () const pure { pragma(inline, true); return (curdir != Left); }
 476     @property bool toMax () const pure { pragma(inline, true); return (curdir == Left); }
 477   }
 478 }
 479
 480
 481 version(aat_test) {
 482 // ////////////////////////////////////////////////////////////////////////// //
 483 void test00 () {
 484   import std.stdio : writeln;
 485
 486   /*
 487   void checkIterators(AATree) (AATree tree, int[] values) {
 488     import std.conv : to;
 489     int curK = 0;
 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])~")");
 495       ++curK;
 496     }
 497     curK = cast(int)tree.size;
 498     { import std.stdio; writeln(" curK=", curK, "; size=", tree.size); }
 499     foreach (/+auto+/ n; tree.fromMax) {
 500       --curK;
 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])~")");
 504     }
 505   }
 506   */
 507
 508   void checkIterators(AATree) (AATree tree) {
 509     import std.conv : to;
 510     //int curK = int.min, curV = int.min;
 511     /*
 512     {
 513       auto it = tree.fromMin();
 514       while (!it.empty) {
 515         import std.stdio;
 516         writeln(" k=", it.front.key, "; v=", it.front.value);
 517         it.popFront();
 518       }
 519     }
 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(); } }
 522     */
 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);
 526     count = 0;
 527     ln = int.max;
 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);
 530     int[] keys, values;
 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)~")");
 535       keys ~= n.key;
 536       values ~= n.value;
 537       //curK = n.key;
 538       //curV = n.value;
 539     }
 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)~")");
 544       keys = keys[0..$-1];
 545       values = values[0..$-1];
 546     }
 547   }
 548
 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)();
 553
 554     static if (tree.HasNodeList) {
 555       void checkNodeList () {
 556         auto n = tree.firstNode;
 557         int count = 0;
 558         //auto ln = int.min;
 559         while (n !is null) {
 560           //if (n.key <= ln) { import std.stdio; writeln("ln=", ln, "; key=", n.key); }
 561           //assert(n.key > ln);
 562           //ln = n.key;
 563           n = n.next;
 564           ++count;
 565         }
 566         ///*if (count != tree.size)*/ { import std.stdio; writeln("count=", count, "; size=", tree.size); }
 567         assert(count == tree.size);
 568         n = tree.lastNode;
 569         count = 0;
 570         //ln = int.max;
 571         while (n !is null) {
 572           //assert(n.key < ln);
 573           //ln = n.key;
 574           n = n.prev;
 575           ++count;
 576         }
 577         import std.range : enumerate;
 578         assert(count == tree.size);
 579         count = 0;
 580         foreach (/*auto*/ idx, /*auto*/ nn; tree.fromFirstNode.enumerate) { assert(count == idx); ++count; }
 581         assert(count == tree.size);
 582         count = 0;
 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); }
 586       }
 587     } else {
 588       void checkNodeList () {}
 589     }
 590
 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]));
 595       } else {
 596         assert(0, "Could not find key "~to!string(values[i]));
 597       }
 598       checkIterators(tree);
 599       checkNodeList();
 600     }
 601     checkIterators(tree);
 602     checkNodeList();
 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]));
 606       }
 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]));
 610         } else {
 611           assert(0, "Could not find key {0}"~to!string(values[j]));
 612         }
 613       }
 614       if (!tree.remove(values[i])) assert(0, "Failed to delete {0}"~to!string(values[i]));
 615       checkIterators(tree);
 616       checkNodeList();
 617     }
 618   }
 619
 620   writeln("test00 (0)");
 621   test([1, 2, 3, 4]);
 622
 623   test([1]);
 624
 625   test([1, 2]);
 626   test([2, 1]);
 627
 628   test([1, 2, 3]);
 629   test([2, 1, 3]);
 630   test([1, 3, 2]);
 631   test([2, 3, 1]);
 632   test([3, 1, 2]);
 633   test([3, 2, 1]);
 634
 635   test([1, 2, 3, 4]);
 636   test([2, 1, 3, 4]);
 637   test([1, 3, 2, 4]);
 638   test([2, 3, 1, 4]);
 639   test([3, 1, 2, 4]);
 640   test([3, 2, 1, 4]);
 641   test([1, 2, 4, 3]);
 642   test([2, 1, 4, 3]);
 643   test([1, 3, 4, 2]);
 644   test([2, 3, 4, 1]);
 645   test([3, 1, 4, 2]);
 646   test([3, 2, 4, 1]);
 647   test([1, 4, 2, 3]);
 648   test([2, 4, 1, 3]);
 649   test([1, 4, 3, 2]);
 650   test([2, 4, 3, 1]);
 651   test([3, 4, 1, 2]);
 652   test([3, 4, 2, 1]);
 653   test([4, 1, 2, 3]);
 654   test([4, 2, 1, 3]);
 655   test([4, 1, 3, 2]);
 656   test([4, 2, 3, 1]);
 657   test([4, 3, 1, 2]);
 658   test([4, 3, 2, 1]);
 659
 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) {
 664       int r;
 665       bool dup;
 666       do {
 667         import std.random : uniform;
 668         dup = false;
 669         r = uniform!"[]"(r.min, r.max);
 670         for (int j = 0; j < i; ++j) {
 671           if (a[j] == r) { dup = true; break; }
 672         }
 673       } while (dup);
 674       a[i] = r;
 675     }
 676     test(a);
 677   }
 678 }
 679
 680
 681 // ////////////////////////////////////////////////////////////////////////// //
 682 void test01 () {
 683   import std.stdio;
 684
 685   static final class Data {
 686     usize idx;
 687     string word;
 688     uint cloneCount;
 689
 690     this (usize aidx, string aword) { idx = aidx; word = aword; }
 691
 692     Data clone () {
 693       //writeln("cloning #", idx, "[", word, "](", cloneCount, "+1)");
 694       auto res = new Data(idx, word);
 695       res.cloneCount = cloneCount+1;
 696       return res;
 697     }
 698
 699     void release () {
 700       //writeln("releasing #", idx, "[", word, "](", cloneCount, ")");
 701     }
 702   }
 703
 704   writeln("test01");
 705
 706   auto tree = new AATree!(string, Data, true);
 707
 708   writeln("creating tree...");
 709   string[] words;
 710   foreach (string line; File("/usr/share/dict/words").byLineCopy) {
 711     assert(line.length);
 712     words ~= line;
 713   }
 714
 715   import std.random : randomShuffle, uniform;
 716   words.randomShuffle;
 717
 718   foreach (immutable idx, string w; words) tree.insert(w, new Data(idx, w));
 719
 720   debug { writeln("tree items: ", tree.size, "; max tree depth: ", tree.maxTreeDepth); }
 721
 722   char[] key = "supernatural".dup;
 723   assert(key in tree);
 724
 725   key = "motherfucker".dup;
 726   assert(key !in tree);
 727   tree.insert(key, new Data(words.length, key.idup));
 728   words ~= key.idup;
 729
 730   void checkTree () {
 731     string ww;
 732
 733     foreach (/*auto*/ node; tree.fromMin) {
 734       assert(ww.length == 0 || ww < node.key);
 735       ww = node.key;
 736     }
 737
 738     ww = null;
 739     foreach (/*auto*/ node; tree.fromMax) {
 740       assert(ww.length == 0 || ww > node.key);
 741       ww = node.key;
 742     }
 743
 744     import std.range : enumerate;
 745
 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]);
 748   }
 749
 750   checkTree();
 751
 752   writeln("removing elements from tree...");
 753
 754   usize count = 0;
 755   while (words.length != 0) {
 756     if (count++%128 == 0) {
 757       stdout.write("\r", words.length, " items left\x1b[K");
 758       stdout.flush();
 759     }
 760     import std.algorithm.mutation : remove;
 761     auto idx = uniform!"[)"(0, words.length);
 762     auto w = words[idx];
 763     words = words.remove(idx);
 764     if (!tree.remove(cast(const(char)[])w)) assert(0, "boo!");
 765     checkTree();
 766   }
 767   stdout.writeln("\r0 items left\x1b[K");
 768
 769   writeln("clearing tree...");
 770   tree.clear;
 771 }
 772
 773
 774 // ////////////////////////////////////////////////////////////////////////// //
 775 void main () {
 776   test00();
 777   test01();
 778 }
 779
 780 } // version