6
\$\begingroup\$

This class is part of the Construct library.

Container is a dict that:

  1. turns attribute access into key access so con.a -> con["a"]
  2. preserves the order of keys

I know, this is similar to collections.OrderedDict but it isn't available in Python 2.6.

For anyone preferring more interactive code, you can pull the trunk and run nosetests.

def recursion_lock(retval="<recursion detected>", lock_name="__recursion_lock__"):
    def decorator(func):
        def wrapper(self, *args, **kw):
            if getattr(self, lock_name, False):
                return retval
            setattr(self, lock_name, True)
            try:
                return func(self, *args, **kw)
            finally:
                delattr(self, lock_name)

        wrapper.__name__ = func.__name__
        return wrapper

    return decorator


class Container(dict):
    r"""
    A generic container of attributes.

    Containers are dictionaries, translating attribute access into key access, and preserving key order.
    """
    __slots__ = ["__keys_order__","__recursion_lock__"]

    def __init__(self, *args, **kw):
        object.__setattr__(self, "__keys_order__", [])
        for arg in args:
            for k, v in arg.items():
                self[k] = v
        for k, v in kw.items():
            self[k] = v

    def __getattr__(self, name):
        try:
            return self[name]
        except KeyError:
            raise AttributeError(name)

    def __setitem__(self, key, val):
        if key not in self:
            self.__keys_order__.append(key)
        dict.__setitem__(self, key, val)

    def __delitem__(self, key):
        dict.__delitem__(self, key)
        self.__keys_order__.remove(key)

    __delattr__ = __delitem__
    __setattr__ = __setitem__

    def __call__(self, **kw):
        for k,v in kw.items():
            self.__setitem__(k, v)
        return self

    def clear(self):
        dict.clear(self)
        del self.__keys_order__[:]

    def pop(self, key, *default):
        val = dict.pop(self, key, *default)
        self.__keys_order__.remove(key)
        return val

    def popitem(self):
        k, v = dict.popitem(self)
        self.__keys_order__.remove(k)
        return k, v

    def update(self, seq, **kw):
        if hasattr(seq, "keys"):
            for k in seq.keys():
                self[k] = seq[k]
        else:
            for k, v in seq:
                self[k] = v
        dict.update(self, kw)

    def copy(self):
        inst = self.__class__()
        inst.update(self.iteritems())
        return inst

    def _search(self, name, search_all):
        items = []
        for key in self.keys():
            try:
                if key == name:
                    if search_all:
                        items.append(self[key])
                    else:
                        return self[key]
                if type(self[key]) == Container or type(self[key]) == ListContainer:
                    ret = self[key]._search(name, search_all)
                    if ret is not None:
                        if search_all:
                            items.extend(ret)
                        else:
                            return ret
            except:
                pass
        if search_all:
            return items
        else:
            return None

    def search(self, name):
        return self._search(name, False)

    def search_all(self, name):
        return self._search(name, True)

    __update__ = update
    __copy__ = copy

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

    iterkeys = __iter__

    def itervalues(self):
        return (self[k] for k in self.__keys_order__)

    def iteritems(self):
        return ((k, self[k]) for k in self.__keys_order__)

    def keys(self):
        return self.__keys_order__

    def values(self):
        return list(self.itervalues())

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

    @recursion_lock()
    def __repr__(self):
        parts = ["Container"]
        for k,v in self.iteritems():
            if not k.startswith("_"):
                parts.extend(["(",str(k),"=",repr(v),")"])
        if len(parts) == 1:
            parts.append("()")
        return "".join(parts)

    @recursion_lock()
    def __str__(self, indentation="\n    "):
        text = ["Container: "]
        for k,v in self.iteritems():
            if not k.startswith("_"):
                text.extend([indentation, k, " = "])
                text.append(indentation.join(str(v).split("\n")))
        return "".join(text)

Tests:

class TestContainer(unittest.TestCase):

    def test_getattr(self):
        c = Container(a=1)
        self.assertEqual(c["a"], 1)
        self.assertEqual(c.a, 1)

    def test_getattr_missing(self):
        c = Container(a=1)
        self.assertRaises(AttributeError, lambda: c.unknownkey)
        self.assertRaises(KeyError, lambda: c["unknownkey"])

    def test_setattr(self):
        c = Container()
        c.a = 1
        self.assertEqual(c.a, 1)
        self.assertEqual(c["a"], 1)
        c["a"] = 2
        self.assertEqual(c.a, 2)
        self.assertEqual(c["a"], 2)

    def test_delattr(self):
        c = Container(a=1)
        del c.a
        self.assertFalse("a" in c)
        self.assertRaises(AttributeError, lambda: c.a)
        self.assertRaises(KeyError, lambda: c["a"])
        self.assertEqual(c, Container())

    def test_update(self):
        c = Container(a=1)
        d = Container()
        d.update(c)
        self.assertEqual(d.a, 1)
        self.assertEqual(c, d)

    def test_items(self):
        c = Container(a=1)(b=2)(c=3)(d=4)
        self.assertEqual(c.keys(), ["a","b","c","d"])
        self.assertEqual(c.values(), [1,2,3,4])
        self.assertEqual(c.items(), [("a",1),("b",2),("c",3),("d",4)])

    def test_iters(self):
        c = Container(a=1)(b=2)(c=3)(d=4)
        self.assertEqual(list(c.iterkeys()), ["a","b","c","d"])
        self.assertEqual(list(c.itervalues()), [1,2,3,4])
        self.assertEqual(list(c.iteritems()), [("a",1),("b",2),("c",3),("d",4)])

    def test_order_randomized(self):
        print("WARNING: this test is randomized and may not be reproducible")
        c = Container()
        while True:
            words = [("".join(chr(randint(65, 97)) for _ in range(randint(3,7))), i) for i in range(20)]
            if words != list(dict(words).keys()):
                break
        c.update(words)
        self.assertEqual([k for k, _ in words], list(c.keys()))

    def test_eq_eq(self):
        # Note that eq does not check order, nor is implemented.
        c = Container(a=1,b=2,c=3,d=4,e=5)
        d = Container(c=3,a=1,b=2,e=5,d=4)
        self.assertEqual(c, d)

    def test_ne_wrong_type(self):
        c = Container(a=1)
        d = [("a", 1)]
        self.assertNotEqual(c, d)

    def test_ne_wrong_key(self):
        c = Container(a=1)
        d = Container(b=1)
        self.assertNotEqual(c, d)

    def test_ne_wrong_value(self):
        c = Container(a=1)
        d = Container(a=2)
        self.assertNotEqual(c, d)

    def test_copy(self):
        c = Container(a=1)
        d = c.copy()
        self.assertEqual(c, d)
        self.assertTrue(c is not d)

    def test_copy_module(self):
        c = Container(a=1)
        d = copy(c)
        self.assertEqual(c, d)
        self.assertTrue(c is not d)

    def test_bool_false(self):
        c = Container()
        self.assertFalse(c)

    def test_bool_false_regression(self):
        # recursion_lock() used to leave private keys
        c = Container()
        str(c); repr(c)
        self.assertFalse(c)

    def test_bool_true(self):
        c = Container(a=1)
        self.assertTrue(c)

    def test_in(self):
        c = Container(a=1)
        self.assertTrue("a" in c)

    def test_not_in(self):
        c = Container()
        self.assertTrue("a" not in c)

    def test_repr(self):
        c = Container(a=1)(b=2)(c=3)
        self.assertEqual(repr(c), "Container(a=1)(b=2)(c=3)")

    def test_repr_empty(self):
        c = Container()
        self.assertEqual(repr(c), "Container()")
        self.assertEqual(eval(repr(c)), c)

    def test_repr_nested(self):
        c = Container(a=1)(b=2)(c=Container())
        self.assertEqual(repr(c), "Container(a=1)(b=2)(c=Container())")
        self.assertEqual(eval(repr(c)), c)

    def test_repr_recursive(self):
        c = Container(a=1)(b=2)
        c.c = c
        self.assertEqual(repr(c), "Container(a=1)(b=2)(c=<recursion detected>)")

    def test_str(self):
        c = Container(a=1)(b=2)(c=3)
        self.assertEqual(str(c), "Container: \n    a = 1\n    b = 2\n    c = 3")

    def test_str_empty(self):
        c = Container()
        self.assertEqual(str(c), "Container: ")

    def test_str_nested(self):
        c = Container(a=1)(b=2)(c=Container())
        self.assertEqual(str(c), "Container: \n    a = 1\n    b = 2\n    c = Container: ")

    def test_str_recursive(self):
        c = Container(a=1)(b=2)
        c.c = c
        self.assertEqual(str(c), "Container: \n    a = 1\n    b = 2\n    c = <recursion detected>")

    def test_dict_arg(self):
        c = Container({'a': 1})
        d = Container(a=1)
        self.assertEqual(c, d)

    def test_multiple_dict_args(self):
        c = Container({'a': 1, 'b': 42}, {'b': 2})
        d = Container(a=1, b=2)
        self.assertEqual(c, d)

    def test_dict_and_kw_args(self):
        c = Container({'b': 42, 'c': 43}, {'a': 1, 'b': 2, 'c': 4}, c=3, d=4)
        d = Container(a=1, b=2, c=3, d=4)
        self.assertEqual(c, d)
\$\endgroup\$
  • 1
    \$\begingroup\$ You might want to compare your implementation's performance against this implementation of an ordereddict to see how it holds up: pypi.python.org/pypi/ordereddict \$\endgroup\$ – Graipher Sep 5 '16 at 10:23
  • \$\begingroup\$ Thanks, but its implementation is not clearer than what I have. I am more concerned with correctness than performance. \$\endgroup\$ – ArekBulski Sep 5 '16 at 12:47
  • \$\begingroup\$ Yeah, the double-linked list approach is not very clear, I agree. But it does have the advantage of keeping the time complexity of a dictionary in all cases. Whereas I'm not sure of the time complexities of your implementations, hence the recommendation to compare the performances :). \$\endgroup\$ – Graipher Sep 5 '16 at 12:54
4
\$\begingroup\$

While the performance of your container seems to be not your major concern, it is always nice to know where you are standing. Therefore I would compare it to this implementation of an OrderedDict for 2.4 <= python <= 2.6.


In addition, what your container seems to lack is to give it an ordered sequence on initialization. It can only take an iterable which has the method items defined. But it would be nice to be able to give it an iterable of 2-tuples, so something like:

c = Container([("a", 1), ("b", 2), ("c", 3), ...])

collections.OrderedDict offers this, therefore a user might expect your implementation to also have it. Without it, the ordering will not give you any advantage, because as soon as you do:

c = Container({"a": 1, "b": 2, "c": 3, ...})
c = Container(a=1, b=2, c=3, ...) 

you loose the order, because of python dicts disorderedness. You try to get around this with __call__, allowing you to do:

c = Container(a=1)(b=2)(c=3)

but in my opinion this is less clean and clear than using e.g. a list of tuples. The latter also simplifies your copy:

def copy(self):
    return inst = self.__class__(self.iteritems())

__copy__ = copy

The implementation for this is actually already in your update method.

I also added __copy__ = copy here to allow usage of the copy module.


In your _search method, you are doing a return None at the end. This is superfluous as that is the default return value of a python function.


It is better to ask forgiveness than permission, so I would use try..except in update:

def update(self, seq, **kw):
    try:
        for k in seq.keys():
            self[k] = seq[k]
    except AttributeError:
        for k, v in seq:
            self[k] = v
    dict.update(self, kw)

I would also think about which you want to put in the try clause (the one that fails less often, which depends on you usage of this class).


dict.pop() (without a key) is not defined, because the 'last' element in a dict is of course not well-defined. For an ordered dict, it might make sense, however, to allow it (and collections.OrderedDict does, with its pop method):

def pop(self, key=None, *default):
    if not key:
        key = self.__keys_order__.pop()
    else:
        self.__keys_order__.remove(key)
    val = dict.pop(self, key, *default)
    return val

This takes advantage of the fact that list.pop is O(1), whereas list.remove is O(n) if the last element is the one you want to remove (because it needs to search through the whole list to find the last element).

Your popitem also seems to be randomly ordered, because it directly uses dict.popitem. It should be:

def popitem(self):
    k = self.__keys_order__.pop()
    v = dict.pop(self, k)
    return k, v
\$\endgroup\$
  • \$\begingroup\$ The problem is that dict.pop fails if key is not given, not pop any entry. So either I diverge from the established semantic and provide pop any or I stick to what the dict does. On the other hand, List provides pop as in pop last. Rememeber that Container derives from dict, so it kind of inherits the semantics as well. I am still thinking about it. collections.OrderedDict.pop has dict semantics. dict.popitem does return random entry tho. \$\endgroup\$ – ArekBulski Sep 5 '16 at 18:12
  • \$\begingroup\$ Why does update check for keys? Either it is given a dict or Container, either have keys method. \$\endgroup\$ – ArekBulski Sep 5 '16 at 18:18
  • \$\begingroup\$ @ArekBulski Yes, dict.pop fails without a key argument. dict.popitem and collections.OrderedDict.popitem do not, however. i don't understand your comment regarding update. I just meant that the code needed to read an iterable containing a 2-tuple with key, value pairs is already in your implementation of update, so you just need to copy & paste that. \$\endgroup\$ – Graipher Sep 5 '16 at 20:20
  • \$\begingroup\$ I just figured it out. Update can take both a list of tuples or a dict. I will make it more explicit and test whether argument is a dict or not. \$\endgroup\$ – ArekBulski Sep 5 '16 at 21:00

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.