Re: Advanced data structures in Glib ?

[Sander Vesik <Sander Vesik Sun COM>]

On Tue, 12 Mar 2002, William Lee Irwin III wrote:

> 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...
> 

Make the structure happen in a generic, well-planned and implemented way
in a separate library and then start lobbying to get the pieces moved
upstream into glib? And the lobbying part is probably easier if you show
how these fit in with existing structures (and so on).

> 
> Cheers,
> Bill
> 

	Sander

	I see a dark sail on the horizon
	Set under a dark cloud that hides the sun
	Bring me my Broadsword and clear understanding