www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Re: [GSoC] Container proposals by Ishan and Christian


 Do you really find it appropriate to throw an avalanche of new data structure 
 over Ishan when he just said he has "never heard about" "Skip list, Binary 
 decision tree, Trie, rope"?

If you are going to design collections for Phobos, you want to know a long list of the ones that are interesting, to choose from. ----------------------- KennyTM~:
 Union-Find - Maybe useful, but when did you need a union-find structure
 outside of Kruskal's algorithm?

Union-Find is easy to implement and it's useful in lot of situations. One example: http://www.vdrobot.com/UnionFind/UnionFind.html
 Bloom filter - I've never hit a case where a hash set is too big and a
 bloom filter is enough.

I have used Bloom Filters twice so far, in filtering strings and genomic processing/search. I agree it's not so widely useful, but it is not hard to implement for a student in the summer. Dawg, BK-tree, finger tree - What are these? Why are they useful for Phobos? Dawgs and BK-trees are useful if you search strings, etc. I have not used a finger tree yet, it's probably not immediate to implement, but it's a building block of several purely function data structures, so it's a good starting point for functional (immutable) data structures in D2/Phobos.
 Graph - Yes it is useful, but there are too many operations associated
 with it, which should better live as its own module (std.container.graph?).

You design the core and its interface, then the graph functions are often free function external to the core data structure.
 P.P.S. if you don't mind I'd like to add 'interval set' to the list. See

Good idea. Bye, bearophile
Apr 05 2011