Re: Advanced data structures in Glib ?

[Paolo Molaro <lupus ximian com>]

On 03/12/02 William Lee Irwin III wrote:
> (1) treaps		(simple tree with O(1) expected rotations on ins/del)
> (2) open-addressed hash tables
> (3) tree hashing	(hash table buckets using binary search trees)
> (4) lazy queue		(priority queue #1, list-based)
> (5) calendar queue	(priority queue #2, array-based)
> (6) timer queue		(priority queue #3, array-based)
> (7) binomial heap	(priority queue #4, tree-based)
> (8) Fibonacci heap	(priority queue #5, tree-based)
> (9) complete bin. tree	(priority queue #6, array- or tree- based)
> (10) tries / radix trees
> (11) hash trie		(trie with child links in open-addressed hash tables)
> (12) Patricia tries	(trie with path compression)
> (13) union/find trees
> (14) stratified trees	(priority queue #7, a.k.a. van Emde Boas queues)
> ...

I don't think we want all that in glib, if someone wants a very
specialized data structure he can code his own (or we could have a
repository of glib-style data structures he can copy in it's own
source, or we can put it in a different library).
What I miss in GLib is any (but only _one_:-) priority queue and trie 
with path compression. 
I think a bitset could be of general enough use, too (but I already
wrote my own for mono, so I'm not going to push hard this one:-).

lupus

-- 
-----------------------------------------------------------------
lupus debian org                                     debian/rules
lupus ximian com                             Monkeys do it better