begin

Gemification

To simplify my usage of this nice package, and managing my patches to it, I have added it to this repository and added a Rakefile to create a gem for it. Install it like any gem, basically.

//Martin Kihlgren <martin at troja dot ath dot cx>

Ruby/RBTree

RBTree is a sorted associative collection using Red-Black Tree as the internal data structure. The elements of RBTree are ordered and the interface is the almost same as Hash, so simply you can consider RBTree sorted Hash.

Red-Black Tree is a kind of binary tree that automatically balances by itself when a node is inserted or deleted. Thus the complexity for insert, search and delete is O(log N) in expected and worst case. On the other hand the complexity of Hash is O(1). Because Hash is unordered the data structure is more effective than Red-Black Tree as an associative collection.

The interface of RBTree is the almost same as Hash although there are some limitations.

* While iterating (e.g. in RBTree#each block), RBTree is
  unmodifiable.

* Comparison is done using <=> method of key objects. So all types
  of keys in RBTree should be comparable each other or an arbitrary
  Proc might be set by RBTree#readjust.

RBTree has a few searching methods that Hash doesn’t have. They are RBTree#lower_bound, RBTree#upper_bound and RBTree#bound. See document of each method for details.

Pretty printing is available for RBTree by using pp.rb. The output of pp is easier than p to read. Just call Kernel#pp for the object.

MultiRBTree that allows duplicates of keys is also available.

Download

* ((<"Ruby/RBTree 0.2.0"|URL:rbtree-0.2.0.tar.gz>))

Requirement

* Ruby 1.6.7 or higher

Install

$ tar xzf rbtree-x.x.x.tar.gz
$ cd rbtree-x.x.x.tar.gz
$ ruby extconf.rb
$ make
$ make site-install

Test

$ ruby test.rb

Incomplete Document

$ rdoc rbtree.c

License

dict.c and dict.h are modified copies that are originally in Kazlib written by Kaz Kylheku. Copyright is held by Kaz Kylheku, see dict.c and dict.h for the license. The web page of Kazlib is at ((<URL:users.footprints.net/~kaz/kazlib.html>)).

Support

Bug fixes, suggestions and other feedbacks are welcomed. Please mail me at ((<[email protected]|URL:[email protected]>)).