key - key pairs

[Florian Lindner]

Hello,
is there in python a kind of dictionary that supports key - key pairs?
I need a dictionary in which I can access a certain element using two
different keys, both unique.

For example:

I've a dictionary with strings and times. Sometimes I have the string and I
want to have the time, other time I've the time and I want the string. It
is important that one of the keys supports the min/max builtin function.

Thanks,

Florian

 

[Scott David Daniels]

Hello,
is there in python a kind of dictionary that supports key - key pairs?
I need a dictionary in which I can access a certain element using two
different keys, both unique.

For example:

I've a dictionary with strings and times. Sometimes I have the string and I
want to have the time, other time I've the time and I want the string. It
is important that one of the keys supports the min/max builtin function.

Thanks,

Florian

As Claudio suggests, you probably want to make a class with (at least)
a pair of dictionaries. Are the strings one-to-one with the times?

I am unsure of what you mean by "supports the min/max builtin function."
If all you mean is, "can I get the min and/or max of the keys (strings
or times), then a pair of dictionaries does it. If you mean "finds
faster than linear," you need to say what operations are to be fastest,
and whether you mean worst case or amortized. It is possible to make
the fast operations most combinations of:
"find least",
"find greatest",
"remove least",
"remove greatest",
"find arbitrary",
"remove arbitrary",
"add entry"

Depending on your choice on costs, the data structure changes.

--Scott David Daniels
(e-mail address removed)

 

[sameer_deshpande]

Just an example of dictionary object in python.

PythonWin 2.4.1 (#65, Mar 30 2005, 09:33:37) [MSC v.1310 32 bit
(Intel)] on win32.
Portions Copyright 1994-2004 Mark Hammond ([email protected]) -
see 'Help/About PythonWin' for further copyright information.

d = {}
d["key1"] = "value1"
d["key2"] = "value2"
d["key3"] = "value3"
d["key3"] = "value3"

for i, j in d.items():

.... print i, j
....
key3 value3
key2 value2
key1 value1.... print d["key1"]
.... else:
.... print "no key"
....
value1.... print d["key1"]
.... else:
.... print "no key"
....
no key
HTH

Sameer

 

[Terry Hancock]

is there in python a kind of dictionary that supports key - key pairs?
I need a dictionary in which I can access a certain element using two
different keys, both unique.

For example:

I've a dictionary with strings and times. Sometimes I have the string and I
want to have the time, other time I've the time and I want the string. It
is important that one of the keys supports the min/max builtin function.

Well, really, you're always using one or the other as the "key" and the other
as the "value". Furthermore, it is not in the general case assured that you
can do this --- the keys may not really be 1:1.

If you are content to restrict yourself to the 1:1 case, you can construct
an inverse dictionary from the first dictionary like this:

time2string = dict([ (b,a) for a,b in string2time.items() ])

Note that if string2time has duplicate values, this will arbitrarily pick
one (in a consistent, but implementation dependent way) to use as
the key in the inverse mapping.

 

[Ivan Van Laningham]

Hi All--

is there in python a kind of dictionary that supports key - key pairs?
I need a dictionary in which I can access a certain element using two
different keys, both unique.

For example:

I've a dictionary with strings and times. Sometimes I have the string and I
want to have the time, other time I've the time and I want the string. It
is important that one of the keys supports the min/max builtin function.

Well, really, you're always using one or the other as the "key" and the other
as the "value". Furthermore, it is not in the general case assured that you
can do this --- the keys may not really be 1:1.

If you are content to restrict yourself to the 1:1 case, you can construct
an inverse dictionary from the first dictionary like this:

time2string = dict([ (b,a) for a,b in string2time.items() ])

Note that if string2time has duplicate values, this will arbitrarily pick
one (in a consistent, but implementation dependent way) to use as
the key in the inverse mapping.

Well, Florian said, "using two different keys, both unique"; if that is
true, then a single key maps to a single value & vice versa. Easiest
way, it seems to me, would be to subclass dict and provide get/set that
always insert the value as a key. So that dict["string"]=time also
means dict[time]="string". Only one dict required then.

Or am I missing something?

Metta,
Ivan
----------------------------------------------
Ivan Van Laningham
God N Locomotive Works
http://www.andi-holmes.com/
http://www.foretec.com/python/workshops/1998-11/proceedings.html
Army Signal Corps: Cu Chi, Class of '70
Author: Teach Yourself Python in 24 Hours

 

[Claudio Grondi]

is there in python a kind of dictionary that supports key - key pairs?

I need a dictionary in which I can access a certain element using two
different keys, both unique.

A Python dictionary needs a unique key, so a pair
of keys is still one unique key, but probably it is some
kind of misunderstanding here, because a dictionary
is not a database which needs a key to quickly find
an entry, so it can have as many keys as required.

What about two dictionaries where each has as a value
a key to the target dictionary with the actual values?

For example:

I've a dictionary with strings and times. Sometimes I have the string and I
want to have the time, other time I've the time and I want the string. It
is important that one of the keys supports the min/max builtin function.

From this example it seems, that what is needed is
a two-way dictionary. I don't know about a special
kind of dictionary for this, so maybe someone else
knows about such.
I can only recommend to use two dictionaries,
where the second one is created out of the first one,
so that they key, value pair is reversed.
If you need some code for the latter, let me know.

Claudio

 

[Scott David Daniels]

Well, Florian said, "using two different keys, both unique"; if that is
true, then a single key maps to a single value & vice versa.

Of course you are right. I got caught up in the problem I imagined (the
pair being unique).

> ... subclass dict and provide get/set that always insert the value
> as a key. So dict["string"]=time also means dict[time]="string".
Or am I missing something?

Yup, getting to min and max. I presume that will be key-dependent.

--Scott David Daniels
(e-mail address removed)

 

[Paul McGuire]

No need to update __getitem__, since the modified __setitem__ drops in
the reverse values. But __delitem__ needs overriding, and some special
guard needs to be added to __setitem__ to prevent orphaning any old
value:key entries.

-- Paul


Here's one possible solution:

class SymmetricDict(dict):
def __delitem__(self,x):
v = self[x]
super(SymmetricDict,self).__delitem__(x)
super(SymmetricDict,self).__delitem__(v)
def __setitem__(self,k,v):
if k in self:
del self[k]
if v in self:
del self[v]
super(SymmetricDict,self).__setitem__(k,v)
super(SymmetricDict,self).__setitem__(v,k)

sd = SymmetricDict()

sd["A"] = 1
print sd["A"]
print sd[1]
sd["A"] = 2
print sd["A"]
print sd[2]
print sd[1]

prints:

1
A
2
A
Traceback (most recent call last):
File "symmetricDict.py", line 25, in ?
print sd[1]
KeyError: 1

 

[Paul McGuire]

Man, this is not my week! Another bug in my posted code! The posted
version of SymmetricDict fails when adding an entry in which the key
equals the value. First bug is in __setitem__ in which the insertion
is done twice, which is wasteful but benign. The second bug is in
__delitem__, which throws an exception when we try to delete the
back-pointing entry - which was already deleted since there is only one
entry.

Another cautionary tale on the value of testing...

Here it the improved SymmetricDict code.

-- Paul


class SymmetricDict(dict):
def __delitem__(self,k):
v = self[k]
super(SymmetricDict,self).__delitem__(k)
if not v==k:
super(SymmetricDict,self).__delitem__(v)

def __setitem__(self,k,v):
if k in self:
del self[k]
if v in self:
del self[v]
super(SymmetricDict,self).__setitem__(k,v)
if not v==k:
super(SymmetricDict,self).__setitem__(v,k)