• bearophile <bearophileHUGS lycos.com> Apr 05 2011

bearophile <bearophileHUGS lycos.com> writes:

spir:

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


Good idea.

Bye,
bearophile