I want to build a dictionary that allows multiple keys for one value:
This is a very basic relational database.
So the first piece of feedback is that new programmers often start coding with poorly defined test-cases or non-normalised test-cases whereby they get lost developing their test portfolio. If you would have started with clarifying your case, I'm sure you would have cracked this problem.
Let's start defining our operations from examples
Sometimes we will have the database maintaining links:
- from 1 key to 1 value
- from 1 key to N values
- from N keys to 1 value
- from N keys to N values
A dictionary can hold 1 key to N values, but not N keys to 1 value.
Fortunately the reverse operation of N keys to 1 value is the reverse of the dictionary, so we can trick around this by creating a class:
class Database(object):
""" A dictionary that allows multiple keys for one value """
def __init__(self):
self.keys = {}
self.values = {}
Next we need figure out how to get data into the database. This is similar to the SQL INSERT STATEMENT, where we maintain both our keys and values in single transactions:
def __setitem__(self, key, value):
Lets first insert a new key, whilst keeping in mind that the value might already exist:
if key not in self.keys:
if value not in self.values: # it's a new value
self.keys[key] = set() # a new set
self.keys[key].add(value)
self.values[value] = set() # a new set
self.values[value].add(key)
elif value in self.values:
self.keys[key] = set() # a new set
self.keys[key].add(value)
self.values[value].add(key) # (1)
(1) a new key to a known value only means an update to the values.
Next we worry about if it's a new relationship with a new value:
elif key in self.keys: #
self.keys[key].add(value)
if value not in self.values:
self.values[value] = set()
self.values[value].add(key)
elif value in self.values:
self.values[value].add(key)
We have now implemented the INSERT STATEMENT in our database.
Now it's time to worry about how to delete records and relationships. For this we hack the __delitem__ function to both take a key and a value. Why? Because otherwise we won't know whether the user wants to delete a single relationship only, OR all entries associated with the key
I thereby choose that:
- if the value is
None I delete every relationship associated with the key.
- if the value is a valid relationship between the key and value, then I only delete that specific relationship.
This is how it works:
def __delitem__(self, key, value=None):
if value is None:
# All the keys relations are to be deleted.
try:
value_set = self.keys[key]
for value in value_set:
self.values[value].remove(key)
if not self.values[value]:
del self.values[value]
del self.keys[key] # then we delete the key.
except KeyError:
raise KeyError("key not found")
else: # then only a single relationships is being removed.
try:
if value in self.keys[key]: # this is a set.
self.keys[key].remove(value)
self.values[value].remove(key)
if not self.keys[key]: # if the set is empty, we remove the key
del self.keys[key]
if not self.values[value]: # if the set is empty, we remove the value
del self.values[value]
except KeyError:
raise KeyError("key not found")
Now we can add and delete. But how about bulk updates? They constitute a special case because __setitem__ can't see that you want to propagate your update onto multiple values. So we need to tell it WHAT to update. Here is a proposal that uses the relationship between the key, the old value and the new value that should be accessible to all keys that other would have a relationship with the old value:
def update(self, key, old_value, new_value):
if old_value in self.keys[key]:
affected_keys = self.values[old_value]
for key in affected_keys:
self.__setitem__(key, new_value)
self.keys[key].remove(old_value)
del self.values[old_value]
else:
raise KeyError("key: {} does not have value: {}".format(key,old_value))
So far so good. A slightly annoying thing is that we can't really read what is in the database even though we can get things in and delete them. This calls for the SELECT STATEMENT - or python's __getitem__ method. But(!) we need to be careful, as our database stores data internally as a sets that are accessible from keys. So we need to unpack them onto something useful. As I like working with lists, I have chosen to provide lists, unless its a single value, whereby I only return the value itself:
def __getitem__(self, item):
values = self.keys[item]
if len(values) > 1:
return sorted(list(values))
elif len(values) == 1:
return list(values)[0]
Now we just miss one thing to pass all your test: The bulk loading method where you map N keys to M values. This is a "cartesian" product, which is a fancy word all N's maps to all M's. In Python this is a walk in the park as we can iterate over both and reuse our __setitem__ method:
def iterload(self, key_list, value_list):
for key in key_list:
for value in value_list:
self.__setitem__(key, value)
At this point we have implemented:
- A class for our database
- A "select" method that is compatible with python d[key]
- An "insert" method that is compatible with python d[key] = value
- An "update" method that maintains the relationship to multiple keys.
- A "delete" method that can both delete a relationship and all entries associated with a key.
Testing
Now I need to test this.
First we load a single key:value pair, where the key is a hashable structure. I chose a tuple with 3 integers:
def test01()
# hashable key - a tuple
d = Database()
k, v = (1, 2, 3), 'magic'
d[k] = v
print(d)
print(d[k])
That works fine as we can see our database object and the value
# print(d)
<__main__.Database object at 0x7fd9c3d17048>
# print(d[k])
magic
Next we can test our bulk-load method: iterload together with the "many keys - shared value" which is focal in your problem:
def test02():
# non-hashable key - a list - becomes a many-key shared value
d = Database()
keys, value = [1, 2, 3], ['magic']
d.iterload(keys, value)
assert d[1] == d[2] == d[3]
This also works as our assertion in the last line doesn't complain: The value of d[1]...d[3] are the same: The text string magic
I add two more tests, which should look very familiar to you, though with minor exceptions:
def test03():
d = Database()
k, v = ['what', 'ever'], ['test']
d.iterload(k,v)
assert d['what'] == d['ever']
d['what'] = 'testing'
try:
assert d['what'] == d['ever']
except AssertionError:
assert True
In test03 I need to pack the value into a list, because iterload needs two iterables. I could made my code much harder to read by accounting for many different cases, but I think the programmer should build a function for one thing and make it clear for future recall of what the function is supposed to do.
In test04 - below - I have added the usage of the update function.
def test04():
d = Database()
v = 'test'
keys, values = ['what', 'ever'], [v]
d.iterload(keys, values)
d['whatever'] = 'test'
assert v == d['whatever']
assert v == d['what']
assert d['whatever'] == d['what']
d.update('whatever', 'test', 'new test')
a, b = d['whatever'], d['what']
assert a == b
Everything Together
Here you go:
__author__ = 'root-11'
class Database(object):
""" A dictionary that allows multiple keys for one value """
def __init__(self):
self.keys = {}
self.values = {}
def __getitem__(self, item): # <---SQL SELECT statement
values = self.keys[item]
if len(values) > 1:
return sorted(list(values))
elif len(values) == 1:
return list(values)[0]
def __setitem__(self, key, value):
if key not in self.keys: # it's a new key <---SQL INSERT statement
if value not in self.values: # it's a new value
self.keys[key] = set() # a new set
self.keys[key].add(value)
self.values[value] = set() # a new set
self.values[value].add(key)
elif value in self.values:
self.keys[key] = set() # a new set
self.keys[key].add(value) # a new key
self.values[value].add(key) # but just an update to the values
elif key in self.keys: # it's a new relationships
self.keys[key].add(value)
if value not in self.values:
self.values[value] = set()
self.values[value].add(key)
elif value in self.values:
self.values[value].add(key)
def update(self, key, old_value, new_value):
"""update is a special case because __setitem__ can't see that
you want to propagate your update onto multiple values. """
if old_value in self.keys[key]:
affected_keys = self.values[old_value]
for key in affected_keys:
self.__setitem__(key, new_value)
self.keys[key].remove(old_value)
del self.values[old_value]
else:
raise KeyError("key: {} does not have value: {}".format(key,old_value))
def __delitem__(self, key, value=None): # <---SQL DELETE statement
if value is None:
# All the keys relations are to be deleted.
try:
value_set = self.keys[key]
for value in value_set:
self.values[value].remove(key)
if not self.values[value]:
del self.values[value]
del self.keys[key] # then we delete the key.
except KeyError:
raise KeyError("key not found")
else: # then only a single relationships is being removed.
try:
if value in self.keys[key]: # this is a set.
self.keys[key].remove(value)
self.values[value].remove(key)
if not self.keys[key]: # if the set is empty, we remove the key
del self.keys[key]
if not self.values[value]: # if the set is empty, we remove the value
del self.values[value]
except KeyError:
raise KeyError("key not found")
def iterload(self, key_list, value_list):
for key in key_list:
for value in value_list:
self.__setitem__(key, value)
def test01():
# hashable key - a tuple
d = Database()
k, v = (1, 2, 3), 'magic'
d[k] = v
print(d)
print(d[k])
def test02():
# non-hashable key - a list - becomes a many-key shared value
d = Database()
keys, value = [1, 2, 3], ['magic']
d.iterload(keys, value)
assert d[1] == d[2] == d[3]
def test03():
d = Database()
k, v = ['what', 'ever'], ['test']
d.iterload(k,v)
assert d['what'] == d['ever']
d['what'] = 'testing'
try:
assert d['what'] == d['ever']
except AssertionError:
assert True
def test04():
d = Database()
v = 'test'
keys, values = ['what', 'ever'], [v]
d.iterload(keys, values)
d['whatever'] = 'test'
assert v == d['whatever']
assert v == d['what']
assert d['whatever'] == d['what']
d.update('whatever', 'test', 'new test')
a, b = d['whatever'], d['what']
assert a == b
def do_all():
for k, v in sorted(globals().items()):
if k.startswith("test") and callable(v):
v()
if __name__ == "__main__":
do_all()
