8
\$\begingroup\$

I'm trying to learn to program on my own with the help of books and the Internet and thought I'd start a project (a sub-project for a project).

I want to build a dictionary that allows multiple keys for one value:

d = mkdict()
d['what', 'ever'] = 'testing'
d['what'] is d['ever'] # True

I thought it would be good to get some advice from other programmers to better myself, and so I would like it if you were to give your honest opinion on how I've implemented it (the dos and don'ts) and possibly how you would approach things.

# -*- coding: utf-8 -*-

class mkdict(object):
    """ A dictionary that allows multiple keys for one value """


    class _Container(object):
        """ This is used to wrap an object to avoid infinite
        recursion when calling my own methods from the inside.

        If a method sees this container, it assumes it has been
        called from the inside and not the user.
        """

        def __init__(self, _object):
            self.object = _object


    class dict(object):
        """ Interface for mkdict.dict for dict-like behaviour """

        def __init__(self, d={}, **kwargs):
            """ Using an mkdict._Container to avoid infinite
            recursion when allowing:

            >>> d = mkdict({'what': 'ever'})
            >>> d = mkdict.dict({'what': 'ever'})
            """
            if isinstance(d, mkdict._Container):
                self.mkdict = d.object
            else:
                self.mkdict = mkdict(mkdict._Container(self))
                self.update(d, **kwargs)

        def __str__(self):
            return str(self.mkdict._dict)

        def __repr__(self):
            return str(self)

        def __len__(self):
            return len(self.mkdict._dict)

        def __setitem__(self, key, value):
            """ Desired behaviour:

            >>> d = mkdict()
            >>>
            >>> d['what', 'ever'] = 'testing'
            >>> d
            {'what': 'testing', 'ever': 'testing'}
            >>> d.dict
            {('what', 'ever'): 'testing'}
            >>> d['what'] is d['ever']
            True
            >>>
            >>> d.dict['what'] = 'new value'
            >>> d
            {'what': 'new value', 'ever': 'testing'}
            >>> d.dict
            {'what': 'new value', 'ever': 'testing'}
            >>> d['what'] is d['ever']
            False
            """
            if key not in self and key in self.mkdict:
                self.mkdict._key_already_set(key)

            self.mkdict[key] = value

        def __getitem__(self, key):
            return self.mkdict._dict[key]

        def __contains__(self, key):
            return key in self.mkdict._dict

        def __delitem__(self, key):
            if key not in self:
                raise KeyError(key)

            if isinstance(key, tuple):
                key = key[0]

            del self.mkdict[key]

        def clear(self):
            self.mkdict.clear()

        def update(self, d, **kwargs):
            if isinstance(d, mkdict.dict):
                d = d.mkdict._dict
            elif isinstance(d, mkdict):
                d = d._dict

            d.update(kwargs):
            for k, v in d.items():
                self[k] = v


    class _FullKeyPtr(object):
        """ Desired behaviour:

        full_key_ptr1 = _FullKeyPtr()
        mkdict._key_map -> {'key1', full_key_ptr1,
                            'key2', full_key_ptr1}

        >>> d = mkdict()
        >>> d['what', 'ever'] = 'testing'
        >>> d._key_map
        >>>
        >>> # d._key_map:
        >>> # {'what': full_key_ptr1, 'ever': full_key_ptr1}
        >>> d._key_map
        >>> {'what': ('what', 'ever'), 'ever': ('what', 'ever')}
        >>>
        >>> d['what']
        >>> 'testing'
        >>>
        >>> # full_key = _key_map['ever'].full_key
        >>> # i.e. full_key = ('what', 'ever')
        >>> # _dict[full_key] = 'test'
        >>> d['ever'] = 'test'
        >>>
        >>>
        >>> d['what']
        >>> 'test'
        """

        def __init__(self, full_key):
            self.full_key = full_key

        def __str__(self):
            return str(self.full_key)

        def __repr__(self):
            return str(self)


    def __init__(self, d={}, **kwargs):
        self._dict = dict()
        self._key_map = dict()
        self._dict_backup = None
        self._key_map_backup = None

        if isinstance(d, mkdict._Container):
            self.dict = d.object
        else:
            self.dict = mkdict.dict(mkdict._Container(self))
            self.update(d, **kwargs)

    def __str__(self):
        return str(dict(self.items()))

    def __repr__(self):
        return str(self)

    def __len__(self):
        return len(self._key_map)

    def __iter__(self):
        return iter(self.keys())

    def __getitem__(self, key):
        full_key = self.full_key(key)
        return self.dict[full_key]

    def __setitem__(self, key, value):
        """ Desired behaviour:

        >>> d = mkdict()
        >>> d['what', 'ever'] = 'testing'
        >>>
        >>> d
        {'what': 'testing', 'ever': 'testing'}
        >>>
        >>> d.dict
        {('what', 'ever'): 'testing'}
        >>> d['what'] is d['ever']
        True
        >>>
        >>> d['what'] = 'new value'
        >>> d
        {'what': 'new value', 'ever': 'new value'}
        >>>
        >>> d.dict
        {('what', 'ever'): 'new value'}
        >>> d['what'] is d['ever']
        True
        """
        if key in self:
            key = self.full_key(key)

        if key not in self._dict:
            if isinstance(key, tuple):
                full_key_ptr = self._FullKeyPtr(key)
                for k in key:
                    if k in self:
                        self._key_already_set(k)
                    self._key_map[k] = full_key_ptr
            else:
                self._key_map[key] = self._FullKeyPtr(key)

        self._dict[key] = value

    def __delitem__(self, key):
        full_key = self.full_key(key)

        if isinstance(full_key, tuple):
            for k in full_key:
                del self._key_map[k]
        else:
            del self._key_map[full_key]

        del self._dict[full_key]

    def __contains__(self, key):
        return key in self._key_map

    def items(self):
        return [(k, self[k]) for k, v in self._key_map.items()]

    def iteritems(self):
        return iter(self.items())

    def update(self, d={}, **kwargs):
        if isinstance(d, mkdict.dict):
            d = d.mkdict._dict
        elif isinstance(d, mkdict):
            d = d._dict

        d.update(kwargs)
        for k, v in d.items():
            self[k] = v

    def clear(self):
        self._dict.clear()
        self._key_map.clear()

    def keys(self):
        return self._key_map.keys()

    def full_key(self, key):
        return self._key_map[key].full_key

    def has_key(self, key):
        return key in self

    def append(self, key, otherkey):
        pass

    def remove(self, key):
        full_key = self.full_key(key)

        if not isinstance(full_key, tuple):
            del self._dict[full_key]
            del self._key_map[full_key]
            return

        new_full_key = list(full_key)
        new_full_key.remove(key)

        if len(new_full_key) == 1:
            new_full_key = new_full_key[0]
        else:
            new_full_key = tuple(new_full_key)

        self._dict[new_full_key] = self.dict[full_key]
        del self._dict[full_key]
        self._key_map[key].full_key = new_full_key
        del self._key_map[key]

    def aliases(self, key):
        full_key = self.full_key(key)
        if isinstance(full_key, tuple):
            aliases = list(full_key)
            aliases.remove(key)
            return aliases
        return list()

    def backup(self):
        pass

    def revert(self):
        pass

    def _key_already_set(self, key):
        self.remove(key)

I've been having a lot of infinite recursion problems because of the following desired behaviour:

>>> d = mkdict()
>>> d = mkdict.dict()
>>>
>>> d = mkdict()
>>> d
{}
>>> d.dict
{}
>>>
>>> d['what', 'ever'] = 'test'
>>> d
{'what': 'test', 'ever': 'test'}
>>> d.dict
{('what', 'ever'): 'test'}
>>> d['what'] is d['ever']
True
>>>
>>> d['what'] = 'testing'
>>> d
{'what': 'testing', 'ever': 'testing'}
>>> d.dict
{('what', 'ever'): 'testing'}
>>>
>>> d.dict['what'] = 'new value'
>>> d
{'what': 'new value', 'ever': 'testing'}
>>> d.dict
{'what': 'new value', 'ever': 'testing'}
>>> d['what'] is d['ever']
False

I don't like the way I've dealt with this infinite recursion problem because, to me, the code looks messy and unmaintainable.

Could I please have some advice on where to go with this project?

if advice:
    print 'Thank you!'
else:
    print 'Ok, no problem'
\$\endgroup\$
  • \$\begingroup\$ Your desired behaviour is not clear. Is it a sequence of steps that you have given? If yes then doing d['what', 'ever'] = 'test' is doing what? I am asking this because the comments seem to be showing no change after it is done. \$\endgroup\$ – Aseem Bansal Apr 4 '15 at 12:09
  • 1
    \$\begingroup\$ Please add the code to be reviewed in the question. \$\endgroup\$ – Janne Karila Apr 4 '15 at 12:49
  • \$\begingroup\$ @ratherlargeguy - Please see, and follow the help page on merging accounts \$\endgroup\$ – rolfl Apr 4 '15 at 14:54
  • 1
    \$\begingroup\$ Isn't it pretty normal for a dictionary to already allow multiple keys to have the same value? Is this not how Python dictionaries work...? \$\endgroup\$ – nhgrif Apr 5 '15 at 15:03
  • \$\begingroup\$ @nhgrif No, Python dictionaries don't support multiple keys for the same value. \$\endgroup\$ – Ethan Bierlein Jul 2 '15 at 22:12
8
\$\begingroup\$

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()
\$\endgroup\$
  • \$\begingroup\$ This method essentially uses the dictionaries (which I assume are hashtables) to index all the keys and all the values. It's pretty simple and useful! In comparison to real databases, which I think usually has many more values than they want indexed, they would prefer to store the data as simply an list of tuples (row oriented), and index into this data structure using secondary indexes like hashtables for a particular column and btrees for other columns. \$\endgroup\$ – CMCDragonkai Dec 13 '17 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.