[Goodie] OrderedSet and OrderedDictionary

Brian T Rice water at tunes.org
Thu Jun 12 21:23:47 UTC 2003


On Thu, 12 Jun 2003, Derek Brans wrote:

> > Why not just inherit from OrderedCollection and override the basic add-
> > methods (and at:put: and such) to test for the element's presence?
> >
> > Otherwise there's not much point in making it ordered.
>
> I've done it both ways now (subclassing OrderedCollection and subclassing
> Set).  One of the powerful things that Set provides is a fast lookup of an
> object using hashing.  This is useful for dictionaries.

I see. So the point is to quickly find objects in a sequence. I suppose I
can't argue much with that.

> What is the best way to combine "order" with "quick lookup" in a single
> Collection without keeping essentially two pointers to each element?

When I see this question separate from everything else, my first thought
is to use a binary search tree with the sorting done according to the
hash. Of course, that's not really a /separate/ order, though. So I see
your point.

You should at least explain all of this in the class comment, though,
because this Collection is therefore really two coordinated collections: a
Set, and the sequence of element additions to it.

Of course, this is design issue is going to simmer in my head for a few
days until I find a palatable solution. At least it occurs to me that the
include: protocol (basically add: foo ifPresent: []) which I have seen
Richard mention would be useful for OrderedCollections (in Slate, this
makes a little more sense, because there is an ExtensibleCollection mixin
which ExtensibleSequence (OC) gets its include: from).

-- 
Brian T. Rice
LOGOS Research and Development
http://tunes.org/~water/



More information about the Squeak-dev mailing list