Permalink
Switch branches/tags
Nothing to show
Commits on Mar 28, 2012
  1. Update benchmark script

    nahi committed Mar 28, 2012
  2. Adopt Left leaning RBTree

    nahi committed Mar 28, 2012
    I was unaware that LL RBTree is faster in addition to it's simpler.  See
    more detail at http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
    Trees are rebalanced in 'left leaning' manner after insert so you don't
    see '-' as results of dump_sexp (See updated test expectations.)
    
    Thanks Gaku Nakamura-san for letting me know this by implementing Scala
    version of RBTreeMap!
Commits on Mar 27, 2012
  1. Update benchmark script

    nahi committed Mar 27, 2012
    Show elapsed time of the last execution.
  2. Make :color=, :right= and :left= be public

    nahi committed Mar 27, 2012
    Who can understand 'protected methods' of Ruby in 5 minutes? :)
  3. Make EmptyTree as a subclass of RBTree

    nahi committed Mar 27, 2012
    Reduce method definition duplication.  It improves the performance in
    addition to simplify the code for explanation.
  4. Do loop for retrieval

    nahi committed Mar 27, 2012
    No need to do recursive call.  Perf becomes slightly better.
  5. Make rebalance code simpler

    nahi committed Mar 27, 2012
    For perf and readability.  Introduced RBTree#need_rebalance? and removed
    unnecesarry conditions to be checked for rebalance after insert.
Commits on Mar 26, 2012
  1. Add benchmark script

    nahi committed Mar 26, 2012
Commits on Mar 25, 2012
Commits on Mar 23, 2012
  1. Test update for taking coverage

    nahi committed Mar 23, 2012
  2. Remove unused methods (delete, etc.)

    nahi committed Mar 23, 2012
    Not needed for this benchmark.  Use avl_tree instead for actual
    Red-black tree implementation.
  3. Revert the change to height definition

    nahi committed Mar 23, 2012
    Also, remove height() health check from regulation.
Commits on Mar 19, 2012
  1. Merge RBTreeHash into RBTreeMap

    nahi committed Mar 19, 2012
    extract required impl only
  2. Make put()'s return value undefined

    nahi committed Mar 19, 2012
    As the result of discussion in ML.  No need to care for benchmarking.
    Also fixed the bug in height definition.  Height of empty list is 1, not
    0.
Commits on Mar 16, 2012
  1. Initial version RBTreeHash in avl_tree gem

    nahi committed Mar 16, 2012
    TODO
     - optimize
     - make more easier to read
  2. Add regulation document

    nahi committed Mar 16, 2012