TODO

   1                                                         -*- mode: org -*-
   2
   3 * other variations on balanced trees?
   4 left-leaning red-black trees come to mind
   5 * add necessary type declarations to get good performance out of structures
   6 * eliminate SYMBOL-MACROLET from red-black deletion routines
   7 * add documentation of some sort
   8 * make sure the asdf system looks sane
   9 * parse out declarations from DOTREE's &BODY?
  10 * fix DO-TREE-RANGE
  11 * fix WITH-TREE-ITERATOR
  12 * write tests for DO-TREE-RANGE
  13 ** make sure to include tests where
  14 - :lower is out-of-range for the tree, both :KEY and :INDEX
  15 - :upper is out-of-range for the tree, both :KEY and :INDEX
  16 - :upper is < :lower (<= is probably ok, I think)
  17 * try to make DO-TREE-RANGE support :FROM-END?
  18 * write tests for WITH-TREE-ITERATOR
  19 * add :START and :END arguments for REDUCE?
  20
  21 * DONE convert trees to structures?
  22 * DONE use symbol names for the testcases
  23 * DONE make separate paths for FUNCTION objects for KEY/PRED/TEST and everything else
  24 or add COERCEs in MAKE-BINARY-TREE
  25 * DONE add better test suite
  26 * DONE change iterators to return the node rather than the datum
  27 * DONE update utility bits to match
  28 * DONE make the iterators check the modcount before incrementing
  29 * DONE iterators feel ugly, try redoing them
  30 * DONE convert test suite to use RT
  31 * DONE make DOTREE generate a TAGBODY so that GO works as expected
  32 * DONE write tests for REDUCE :FROM_END T
  33 * DONE change method combination in test suite to be non-SBCL specific
  34 * DONE get ranks working correctly
  35 * DONE add validation checks for ranks to tests
  36 * DONE delete old TREES building code from tree-test.lisp
  37 * DONE switch red-black trees over to using ROTATE-{LEFT,RIGHT}
  38 * DONE add generation count to accomodate limited forms of mutation during iteration
  39 * DONE rearrange DELETE and INSERT to have congruent arglists
  40 * DONE rearrange DELETE and INSERT to have congruent return values
  41 * DONE write wrapping generic function for MAKE-TREE
  42 * DONE add validation routines for the various tree kinds
  43 ** DONE red-black black-height invariant
  44 ** DONE red-black child constraint
  45 these are really slow, though; see if they can be made faster
  46 ** DONE avl height constraint
  47 ** DONE aa level constraint
  48 need to figure out how this last one works (wikipedia knows all)
  49 * DONE rewrite testsuite to work on execution traces
  50 ** DONE generate execution traces from testing routines
  51 ** DONE interface to redo execution traces
  52 what would I use this for, though?
  53 * DONE redo deletion routines for red-black trees
  54 * DONE redo deletion routines for AVL trees
  55 try to factor as much common code from basic and AA
  56 * DONE fix WITH-TREE-ITERATOR to honor FROM-END
  57 again, WITH-TREE-ITERATOR needs to be modified to take advantage
  58 * DONE fix WITH-TREE-ITERATOR to not crash when there's nothing left to move to
  59 * DONE fix order of return values for WITH-TREE-ITERATOR
  60 this is basically done with new iterators, but WITH-TREE-ITERATOR needs to use them
  61 * DONE change DELETE to return the item so deleted
  62 * DONE rewrite iterators to handle non-parented trees
  63 some sort of parent/no-parent iterators with generic functions
  64 * DONE convert nodes to structures
  65 * DONE profile after doing the structure conversion to find more hotspots
  66 assuming that the conversion improves performance the estimated 30-50%
  67 * DONE switch AA trees over to using ROTATE-{LEFT,RIGHT}
  68 * DONE switch avl insertion routines over to using ROTATE-{LEFT,RIGHT}