Re: Possible Glib BTree substitute

[Derek Simkowiak <dereks kd-dev com>]

	See comments below...

> In my opinion, there should be only one O(log n) searching data
> structure in GLib. These are some of the possibilities:
> 
>  - Skip lists:
> 
>       advantages: 
>           A simple and, on the average/in the expected sense, very
>           fast data structure.

	Also, we now have a mostly-complete implementation.  

	Another advantage to skip lists is that the 'balancing' is
randomized, so there is no particular type, series, or ordering of data
that will produce a slower search time than another.

	Finally, as an application developer I find it very convenient to
have all of my data elements wind up in a simple linked list.  I find it
easier to visualize the data and what to do with it.  But that's just
me...

>       disadvantages: 
>           It is randomized, which means that it's worst case
>           behavoiour is O(n).

	"To search a list containing 1000 items, the probability that
search time will be 5 times the average is about 1 in
1,000,000,000,000,000,000."
 (http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/niemann/s_skl.htm)

>  - Balanced binary search trees (AVL, red/black, ...)
> 
>       advantages: 
>           Guaranteed O(log n) worst case behaviour. There is already a
>           working and bug-free implementation. 

	Your first comment that there should be only one O(log n)
structure, combined with the fact that the GTree already exists, implies
that you object to considering a skip list (or other tree implementation)
for addition into Glib.

	First, I'd like to say that a two child-node based structure is
not always appropriate.  It is not as flexible as, say, a BTree that would
let the programmer set the MIN/MAX (where MAX=2*MIN) number of nodes.  At
the same time, I would be strongly opposed to *removing* the GTree in
favor of a more flexible structure.

	Also, it is likely that the new Gtk+ text widget (probably Havoc's
TkText port) will have some kind of Glib-style Node-based structure on the
backend.  If that is going to be shipped with Gtk+, it would make sense to
have that structure made available to other programmers through Glib.

	Therefor, I think we should be open to the idea of adding a second
O(log n) search structure.

>       disadvantages: 
>           The constant hidden in O(log n), while small, is larger than
>           that for skip lists (I am not certain as I have not seen
>           your skip list implementation).

	I would sincerely appreciate it if you could take the time to look
at the code and offer some criticism.  I'm not in an environment where I
have local peers to effectively review the code.


Thank You,
Derek Simkowiak
dereks@kd-dev.com