On Wed, 23 Dec 2009, Adrian Kuhn wrote:
Stéphane Ducasse <stephane.ducasse@...> writes:
what is TreeSet?
The common data structure to implement ordered sets. Which one do you use?
OrderedCollection as in VW the order is based on addition order.
I think that what I'm implemented is more UniqueOrderedCollection than OrderedSet
Okay, so all basic operations are O(n) and elements are not ordered by their natural order. Sounds kinda like a push-only stack with unique elements and "global" remove. Mebbe `UniqueStack` is a good name? Would be nice to get a tree set also then. In a tree set all basic operations (add, remove, includes) are O(log n) and elements are ordered by their natural order. This could be called `SortedSet` even. No tree set implementation in Smalltalk out there? There's BTree on squeaksource, I have LLRBTree (left-leaning red-black tree) but that needs some polishing. Probably there are other implementations too. (I think there's an AVL-tree implementation somewhere, but i'm unsure.) Trees are rarely useful anyway. Levente --AA -- 4th Workshop on Dynamic Languages and Applications Submit papers by March 31, 2010. http://bit.ly/dyla2010 _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project