On Wed, 23 Dec 2009, Stéphane Ducasse wrote:
On Dec 23, 2009, at 6:09 PM, Levente Uzonyi wrote:
On Wed, 23 Dec 2009, Adrian Kuhn wrote:
Stéphane Ducasse <stephane.ducasse@...> writes:
I started to implement OrderedSet (OrderedCollection no duplicate) >> but I think that I want probably UniqueOrdered. >> I will publish what I have done and ask for feedback and that other can improve. I like the idea of using the TraitsTest to have coherent sets of behavior. > > Oh yeah, TreeSet ftw, missed that already sometime! what is TreeSet?
The common data structure to implement ordered sets. Which one do you use?
IMO ordered sets (where ordering means the same as in OrderedCollection) should be implemented with a hashtable of linked elements.
Why not an OrderedCollection?
That's doable, but removal cost would be O(n) instead of O(1), though removal from sets/dictionaries is rare in smalltalk. Of course this means that the cost of accessing an element by index is O(n) instead of O(1), but I wouldn't expect a set to be indexable even if it's "ordered". Levente
if we mean UniqueOrderedCollection For an OrderedSet I imagine that this is because you want a constant access to elements (which happend to be ordered)? Stef _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project