Why are there no ordered dictionaries?

[Christoph Zwerschke]

Bengt Richter wrote:

>>d.keys[:] = newkeyseq
> 
> Do you really mean just re-ordering the keys without a corresponding reording of values??
> That would be a weird renaming of all values. Or do you means that any key should still
> retrieve the same value as before if used as d[key]? In which case the values must undergo
> the same permutation as the keys. I.e., you are assuming key->value pairings remain stable
> through any key reorderings?

Since it is considered as being a dictionary in the first place, the 
key->value pairings should of course stay stable. In the usual 
implementation based on an ordinary dictionary with an additional key 
list ("sequence" in the Foord/Larosa and "_keys" in the Bejamin/Winter 
implementation), you would only set the key list, since the value list 
is generated dynamically. But if your implementation keeps internal 
values or items lists, these need to be adjusted as well.

I will assume that d has is a Foord/Larosa ordered dict with "sequence" 
attribute in the following.

Then, with other words,

d.keys[:] = newkeyseq

should do the same as:

d.sequence = newkeyseq

> Exactly what, though? should e.g.
>     d.keys[3] =  newk3
> mean (not a suggested implementation, just to define semantics)
>     keys = d.keys()
>     if newk3 in keys and keys.index(newk3)!=3:
>         raise ValueError,'Attempt to introduce duplicate key'
>     items = d.items()
>     items[3] = (newk3, items[3][1])
>     d.clear()
>     d.update(items)

Yes, that would be the correct semantics. Of course this should not be 
the real implementation and use KeyError instead of ValueError. With 
other words,

d.keys[i] = newkey

sould be the same as:

if d.sequence[i] != newkey:
     if newkey in d.sequence:
          raise KeyError,'Attempt to introduce duplicate key'
     else:
          d.sequence[i] = newkey

> This would allow what you might call renaming in place.
> Similarly
>     d.keys[i:j] = newkeysij
> might have the semantics of
>     keys = d.keys()
>     outside = set(keys[:i])+set(keys[j:])
>     if outside & set(newkeysij) or len(newkeysij) != len(set(newkeysij)):
>         raise ValueError,'Attempt to introduce duplicate key(s)'
>     items = d.items()
>     items[i:j] = [(k, items[kx+i][1]) for kx,k in enumerate(newkeysij)]
>     d.clear()
>     d.update(items)
> 
> Is this what is desired?

Not quite, because it does not preserve the key->value pairings (see 
above) and it would behave strangely or raise an exception if the new 
slice is larger. The following code would do:

keys = d.keys()
outside = set(keys[:i])|set(keys[j:])
if outside & set(newkeysij) or len(newkeysij) != len(set(newkeysij)):
     raise ValueError,'Attempt to introduce duplicate key(s)'
items = d.items()
items[i:j] = [(k, d.get(k, None)) for k in newkeysij]
d.clear()
d.update(items)

(Note that there was a bug in the second line. You cannot add sets.)

Again, this would be equivalent to:

seq = d.sequence
newseq = seq[:]
newseq[i:j] = newkeysij
if len(newseq) != len(set(newseq)):
     raise KeyError,'Attempt to introduce duplicate key(s)'
for k in set(seq[i:j]) - set(newkeysij):
     del d[k]
for k in set(newkeysij) - set(seq[i:j]):
     d[k] = None
d.sequence = newseq

>>You don't keep track of the item lists, they need to be built on every 
>>occasion.
> 
> That depends on how you implement ;-)

Ok, I was thinking of the usual implementations.

> Back from holiday, so maybe I'll hack something out.

Let us know when you have something to check out.

Maybe Fuzzyman can make some moderate improvements to the existing 
odict.py, and you can do something more "radical". Then we have two 
"reference implementations" and can compare how they prove regarding 
performance and usability.

-- Christoph