Stupid question

Why nil can be a key of Dictionary but not of LookupTable?

And why LookupTable behave so strange:

table := LookupTable new.
table at: #firstKey put: 'firstValue'.
table size. "1"

table at: nil put: 'valueAtNil'.
table keys "a Set(#firstKey)"
table size. "2 why?"

table at: #secondKey put: 'secondValue'.
table size. "2  why?????"

--
Dmitry Zamotkin

Dmitry,

> Why nil can be a key of Dictionary but not of LookupTable?

The physical reason is that the two classes store their collections
differently

Dictionary uses a collection of Associations and it is therefore possible to
add one with a key of nil, the Dictionary can cope as it just stores the
Association object and is not worried about it's contents.

LookupTables store their contents in two parallel arrays, one for the key
and one for the value, with the associated items being stored at the same
index in both collections. The indicator for an empty, unused slot in the
key table is nil. Trying to add an new entry with a key of nil breaks this,
the item is added but because the key entry is nil it is subsequently
ignored .

> table := LookupTable new.
> table at: #firstKey put: 'firstValue'.
> table size. "1"

works as expected

> table at: nil put: 'valueAtNil'.

the LookupTable thinks it has added a new entry and bumps it's tally instVar
by one

> table keys "a Set(#firstKey)"

the entry with the nil key is ignored in the enumeration as it's key is read
as an empty slot.

> table size. "2 why?"

the current tally instVar is 2 as the LookupTable thinks two items have been
added.

> table at: #secondKey put: 'secondValue'.

The initial default size (basicSize) for a LookupTable is 3 entries (allows
for 2 + 1 spare). As we have already (it thinks) got two entries it expands
the table to accommodate another and still leave a spare. This copying
process clears out the erroneous one, the one with a nil key is not copied
as it is apparently an empty slot.

> table size. "2  why?????"

Because now we have two valid entries in a table with room for 10 before it
needs to be expanded again. The tally instVar has been reset to the correct
value by the copying process.

There is a short thread in the archive about this (starts 12 July 2000). The
feeling (my reading of it anyway) was
- ANSI doesn't specify what should happen
- Adding nil as a key is probably not a good idea anyway
- It might be a good idea for LookupTable to use something else as a key for
an empty slot - but this may have performance impacts.

Regards
    Ian

Hello Ian,

Thanks for your response.

>> Why nil can be a key of Dictionary but not of LookupTable?

> LookupTables store their contents in two parallel arrays, one for the key
> and one for the value, with the associated items being stored at the same
> index in both collections. The indicator for an empty, unused slot in the
> key table is nil. Trying to add an new entry with a key of nil breaks
this,
> the item is added but because the key entry is nil it is subsequently
> ignored .

> There is a short thread in the archive about this (starts 12 July 2000).
The
> feeling (my reading of it anyway) was
> - ANSI doesn't specify what should happen
> - Adding nil as a key is probably not a good idea anyway

Why not? Is there any difference between nil and any other object? I can
imagine a lot of cases where nil need to be a key.

> - It might be a good idea for LookupTable to use something else as a key
for
> an empty slot - but this may have performance impacts.

I suppose not using nil as key in LookupTable is "by design" thing. Does
anybody know about realization LookupTable in other dialects?


--
Dmitry Zamotkin

Dmitry,

> Why not? Is there any difference between nil and any other object? I can
> imagine a lot of cases where nil need to be a key.

It's just nil's status as a "special" singleton object that, to my eyes at
least, makes it unsuitable as a key. It's just a feeling though and I
wouldn't try to defend it in a court of law :)

> I suppose not using nil as key in LookupTable is "by design" thing. Does
> anybody know about realization LookupTable in other dialects?

I haven't checked later versions but as I mentioned in the thread I
referenced VW5 doesn't allow nil as a key in Dictionary either. I'm not sure
if it, or other Smalltalks, have LookupTable though - isn't it just a
Dolphin class (it's not ANSI either)?

Regards
    Ian

Dmitry Zamotkin <[hidden email]> wrote in message
news:3c55bcc2$1@tobjects....
>
> I suppose not using nil as key in LookupTable is "by design" thing. Does
> anybody know about realization LookupTable in other dialects?
>
VAST uses two arrays to implement LookupTable. The presence of nil in a slot
in the key table indicates 'no object present'. Therefore it does not allow
nil as a key to a LookupTable entry. VAST does allow nil as a key in a
Dictionary.

Doug Swartz
[hidden email]

"Doug Swartz" <[hidden email]> wrote in message
news:3c570817@tobjects....
>
> Dmitry Zamotkin <[hidden email]> wrote in message
> news:3c55bcc2$1@tobjects....
> >
> > I suppose not using nil as key in LookupTable is "by design" thing. Does
> > anybody know about realization LookupTable in other dialects?
> >
> VAST uses two arrays to implement LookupTable. The presence of nil in a
slot
> in the key table indicates 'no object present'. Therefore it does not
allow
> nil as a key to a LookupTable entry. VAST does allow nil as a key in a
> Dictionary.

In QKS Smalltalk (91-98), and in SmallScript the <Map> class and its
numerous derivatives that include <Dictionary> are all implemented for
efficiency using an array of pair'ed (or arbitrarily tupled slots for
multi-key versions) slots (not Associations).

They allow any object to be stored within them, including <nil>. The
technique is to allocate a unique object that serves as the VOID_KEY. If an
entry contains the VOID_KEY then it is clear. Which means that the VOID_KEY
is the only object which cannot be contained within such a collection.
However the VOID_KEY is a private shared-variable within <KeyedCollection>
and would not (in a sensible way) be accessible. The use of <nil> as a key
can be crucial in a variety of applications.

Recent benchmarks on c.l.s. within the last 9-MOS or so seemed to indicate
that SmallScript's implementation was the fastest map/dictionary collection
available for any Smalltalk.


I.e., <Dictionary> within SmallScript, is what these other Smalltalks call
<LookupTable>. AssociationDictionary is the map/dictionary class built from
Associations. The core SmallScript library/module does not provide an
Association or AssociationDictionary; they are in the ANSI.Smalltalk
library. A significicantly richer enhancement to associations is used for
<Pool> namespace variable collections and their related <PoolVariable>
classes.

<Map> provides a synthetic association interface if needed. During the ANSI
process the general concensus was that use of Associations was innefficient
and should be deprecated within ANSI libraries for standard Map/Dictionary
forms.

-- Dave S. [www.smallscript.org]

>
> Doug Swartz
> [hidden email]
>
>
>