IdentitySet>>identityIncludes:

Just noticed this.

Shouldn't IdentitySet override #identityIncludes: back to

    ^ self includes: anObject.

rather than inherit the O(n) implementation ?

    -- chris

On Fri, 15 Oct 2004 12:16:00 +0100, Chris Uppal  
<[hidden email]> wrote:

> Just noticed this.
>
> Shouldn't IdentitySet override #identityIncludes: back to
>
>     ^ self includes: anObject.
>
> rather than inherit the O(n) implementation ?

Just curious, what about SortedCollection>>includes:?



--
Regards
HweeBoon
MotionObj

"Chris Uppal" <[hidden email]> wrote in message
news:[hidden email]...
I don't understand? As far as I can see the inherited implementation
performs a redundant identity test (necessary in Set of course), but is
otherwise the same, and is not in any case O(n).

Regards

Blair

Yar Hwee Boon wrote:

> Just curious, what about SortedCollection>>includes:?

I take it you mean that SortedCollection>>includes: could use a more efficient
binary chop to implement this ?

If so then the discussions of the point on c.l.s have convinced me that this,
though tempting, would not be a legal implementation.  The problem is that you
are allowed to test whether /any/ object is a member of the collection, not
just ones that are compatible with SortedCollection's comparison condition.

I suppose you /could/ get around that problem by wrapping an exception handler
around the binary chop loop (if an exception is thrown then clearly the object
could not have been added to the collection, and so we can assume that its not
in there), but that seems kind of kludgey to me.

Then too there's the problem (at least in theory) that if
    o1 = o2
that doesn't necessarily imply that
    o1 <= o2
(for whatever value of #<= the SortedCollection is using)

Here's a more-than-somewhat strained example:

Say we have Person objects which are loaded from a DB (or similar).  Suppose
that, to make fetching them from the DB more efficient, the designers have
decided /not/ to ensure that no row is represented by more than one Person
object (so they are created on-the-fly without checking to see if there's
already a Person for that row in the image).  The designers would obviously
give these Person objects an #= that reflected the reality, so that two objects
that both stood for 'John Smith' would compare #=.

Now suppose that in, some other context, the code is interested in these
objects just as objects rather than as representations of people (it might in
some O-R layer).  That code might want to create a collection sorted by some
property of the object itself, rather than of the real person -- say by the
timestamp when it was last accessed.  In that case you would have a
SortedCollection where the sort condition was incompatible with #=.

As I said, somewhat strained, but...

    -- chris

Blair,

> > Shouldn't IdentitySet override #identityIncludes: back to
> >
> >    ^ self includes: anObject.
> >
> > rather than inherit the O(n) implementation ?

> I don't understand?

Neither do I.  I was looking at timings showing that Array>>identityIncludes:
was scaling at the same rate as IdentitySet>>identityIncludes: as the size of
the collection increased (and was, in general, faster and more predictable). So
I traced into

    IdentitySet new identityIncludes: Object new

And found myself looking at the O(n) implementation.

But /now/ when I do it again, it's behaving perfectly correctly, and just as
you described !

I have no idea what I was doing wrong.  Obviously /something/, but I seem to
have stopped doing it now, so "panic" over...

Sorry for the false alarm.

    -- chris

On Sat, 16 Oct 2004 11:45:00 +0100, Chris Uppal  
<[hidden email]> wrote:

> Yar Hwee Boon wrote:
>
>> Just curious, what about SortedCollection>>includes:?
>
> I take it you mean that SortedCollection>>includes: could use a more  
> efficient
> binary chop to implement this ?

Yes.

> If so then the discussions of the point on c.l.s have convinced me that  
> this,
> though tempting, would not be a legal implementation.  The problem is

Thanks for explaining, it has puzzled me for sometime :) OTOH, I always  
thought that a common use for a sorted list is to facilitate faster  
search. So maybe a separate method might be useful.

--
Regards
HweeBoon
MotionObj