Re: Advanced data structures in Glib ?

[William Lee Irwin III <wli holomorphy com>]

On Tue, Mar 12, 2002 at 03:25:55PM -0500, Zack Rusin wrote:
> I was wondering if there's a chance of seeing a little more advanced data 
> structures in the next release of Glib. To be more specific, I think it 
> would be really beneficial to see:
> - Red Black tree moved from GTK+ to Glib,
> - Hash table with collision resolution (linked list preferably),
> - B-Tree (come on you know you want it :) ),
> - Splay tree, 
> - priority queue, 
> added to Glib. What do you guys think?

Perhaps also:
(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)
...

Hmm, there's a lot of these things. =) They're great to have, but maybe
waiting until someone needs them might be better. OTOH it would be
nice to have them at hand...


Cheers,
Bill