Implemented InsertionOrderedMapping class to be used by the new
authorJoel Rosdahl <joel@rosdahl.net>
Sun, 4 Dec 2005 13:32:41 +0000 (13:32 +0000)
committerJoel Rosdahl <joel@rosdahl.net>
Sun, 4 Dec 2005 13:32:41 +0000 (13:32 +0000)
caching image loader.

src/packages/kofoto/insertionorderedmapping.py [new file with mode: 0644]
src/test/alltests.py
src/test/iomtests.py [new file with mode: 0644]

diff --git a/src/packages/kofoto/insertionorderedmapping.py b/src/packages/kofoto/insertionorderedmapping.py
new file mode 100644 (file)
index 0000000..b748c75
--- /dev/null
@@ -0,0 +1,194 @@
+"""This module contains the InsertionOrderedMapping class."""
+
+__all__ = ["InsertionOrderedMapping"]
+
+class _KeyListNode:
+    def __init__(self, key=None):
+        self.key = key
+        self.prev = None
+        self.next = None
+
+    def insert_after(self, node):
+        assert self.prev is None
+        assert self.next is None
+        if node.next:
+            node.next.prev = self
+            self.next = node.next
+        self.prev = node
+        node.next = self
+
+    def insert_before(self, node):
+        assert self.prev is None
+        assert self.next is None
+        if node.prev:
+            node.prev.next = self
+            self.prev = node.prev
+        self.next = node
+        node.prev = self
+
+    def unlink(self):
+        if self.prev:
+            self.prev.next = self.next
+        if self.next:
+            self.next.prev = self.prev
+        self.prev = None
+        self.next = None
+
+class InsertionOrderedMapping:
+    """A mapping datatype with keys sorted in insertion order."""
+
+    def __init__(self, items=None):
+        self._map = {} # key --> (keylistnode, value)
+        self._keylist_head = _KeyListNode()
+        self._keylist_tail = _KeyListNode()
+        self._keylist_tail.insert_after(self._keylist_head)
+        if items is not None:
+            self.update(items)
+
+    def __cmp__(self, other):
+        snode = self._keylist_head.next
+        onode = other._keylist_head.next
+        while True:
+            if snode is self._keylist_tail:
+                if onode is other._keylist_tail:
+                    return 0
+                else:
+                    return -1
+            elif onode is other._keylist_tail:
+                return 1
+            elif snode.key != onode.key:
+                return cmp(snode.key, onode.key)
+            else:
+                sval = self._map[snode.key][1]
+                oval = other._map[onode.key][1]
+                if sval != oval:
+                    return cmp(sval, oval)
+            snode = snode.next
+            onode = onode.next
+
+    def __contains__(self, key):
+        return key in self._map
+
+    def __delitem__(self, key):
+        self._map[key][0].unlink()
+        del self._map[key]
+
+    def __getitem__(self, key):
+        return self._map[key][1]
+
+    def __iter__(self):
+        return self.iterkeys()
+
+    def __len__(self):
+        return len(self._map)
+
+    def __repr__(self):
+        return "InsertionOrderedMapping(%r)" % self.items()
+
+    def __setitem__(self, key, value):
+        if key in self._map:
+            node = self._map[key][0]
+            node.unlink()
+        else:
+            node = _KeyListNode(key)
+        self._map[key] = (node, value)
+        node.insert_after(self._keylist_head)
+
+    def clear(self):
+        self._map.clear()
+
+        # Break reference cycles:
+        node = self._keylist_head
+        while node is not None:
+            node.prev = None
+            node = node.next
+        self._keylist_head.unlink()
+        self._keylist_tail.unlink()
+        self._keylist_tail.insert_after(self._keylist_head)
+
+    def copy(self):
+        return InsertionOrderedMapping(self.reviteritems())
+
+    def get(self, key, default=None):
+        if key in self._map:
+            return self._map[key][1]
+        else:
+            return default
+
+    def has_key(self, key):
+        return self._map.has_key(key)
+
+    def items(self):
+        return list(self.iteritems())
+
+    def iteritems(self):
+        node = self._keylist_head.next
+        while node is not self._keylist_tail:
+            yield (node.key, self._map[node.key][1])
+            node = node.next
+
+    def iterkeys(self):
+        node = self._keylist_head.next
+        while node is not self._keylist_tail:
+            yield node.key
+            node = node.next
+
+    def itervalues(self):
+        node = self._keylist_head.next
+        while node is not self._keylist_tail:
+            yield self._map[node.key][1]
+            node = node.next
+
+    def keys(self):
+        return list(self.iterkeys())
+
+    def pop(self, key, default=None):
+        if key in self._map:
+            value = self[key]
+            del self[key]
+            return value
+        else:
+            if default is None:
+                raise KeyError(key)
+            else:
+                return default
+
+    def popitem(self):
+        if len(self) == 0:
+            raise KeyError
+        else:
+            key = self._keylist_head.next.key
+            value = self.pop(key)
+            return (key, value)
+
+    def reviteritems(self):
+        node = self._keylist_tail.prev
+        while node is not self._keylist_head:
+            yield (node.key, self._map[node.key][1])
+            node = node.prev
+
+    def reviterkeys(self):
+        node = self._keylist_tail.prev
+        while node is not self._keylist_head:
+            yield node.key
+            node = node.prev
+
+    def revitervalues(self):
+        node = self._keylist_tail.prev
+        while node is not self._keylist_head:
+            yield self._map[node.key][1]
+            node = node.prev
+
+    def setdefault(self, key, value=None):
+        if key in self._map:
+            return self[key]
+        else:
+            self[key] = value
+            return value
+
+    def update(self, items):
+        for key, value in items:
+            self[key] = value
+
+    def values(self):
+        return list(self.itervalues())
index 47d404f..5f008c1 100755 (executable)
@@ -2,7 +2,7 @@ import os
 import sys
 import unittest
 
-testModules = ["dagtests", "shelftests", "searchtests"]
+testModules = ["dagtests", "iomtests", "shelftests", "searchtests"]
 
 cwd = os.getcwd()
 libdir = unicode(os.path.realpath(
diff --git a/src/test/iomtests.py b/src/test/iomtests.py
new file mode 100644 (file)
index 0000000..6905d58
--- /dev/null
@@ -0,0 +1,172 @@
+#! /usr/bin/env python
+
+import os
+import sys
+import unittest
+
+if __name__ == "__main__":
+    cwd = os.getcwd()
+    libdir = unicode(os.path.realpath(
+        os.path.join(os.path.dirname(sys.argv[0]), "..", "packages")))
+    os.chdir(libdir)
+    sys.path.insert(0, libdir)
+from kofoto.insertionorderedmapping import *
+
+class TestInsertionOrderedMapping(unittest.TestCase):
+    def setUp(self):
+        self.iom = InsertionOrderedMapping([
+            (1, "a"),
+            (3, "c"),
+            (2, "b"),
+            ])
+
+    def tearDown(self):
+        del self.iom
+
+    def test___cmp__(self):
+        assert(cmp(self.iom, self.iom) == 0)
+        iom2 = self.iom.copy()
+        assert(cmp(self.iom, iom2) == 0)
+        del iom2[3]
+        assert(cmp(self.iom, iom2) == 1)
+        del self.iom[2]
+        del self.iom[3]
+        assert(cmp(self.iom, iom2) == -1)
+
+    def test___contains__(self):
+        assert(0 not in self.iom)
+        assert("a" not in self.iom)
+        assert(1 in self.iom)
+        assert(2 in self.iom)
+        assert(3 in self.iom)
+
+    def test___delitem__(self):
+        try:
+            del self.iom[0]
+        except KeyError:
+            pass
+        else:
+            assert False
+        assert 0 not in self.iom
+        assert len(self.iom) == 3
+        del self.iom[1]
+        assert 1 not in self.iom
+        assert len(self.iom) == 2
+        del self.iom[2]
+        del self.iom[3]
+        assert self.iom._keylist_head.next is self.iom._keylist_tail
+        assert self.iom._keylist_tail.prev is self.iom._keylist_head
+        assert len(self.iom) == 0
+
+    def test___getitem__(self):
+        try:
+            self.iom[0]
+        except KeyError:
+            pass
+        else:
+            assert False
+        assert self.iom[1] == "a"
+        assert self.iom[2] == "b"
+        assert self.iom[3] == "c"
+
+    def test___iter__(self):
+        assert list(self.iom) == [2, 3, 1]
+
+    def test___repr__(self):
+        assert \
+            repr(self.iom) == \
+            "InsertionOrderedMapping([(2, 'b'), (3, 'c'), (1, 'a')])"
+
+    def test___setitem__(self):
+        self.iom[0] = "-"
+        assert self.iom.keys() == [0, 2, 3, 1]
+        self.iom[4] = "d"
+        assert self.iom.keys() == [4, 0, 2, 3, 1]
+
+    def test_clear(self):
+        self.iom.clear()
+        assert 1 not in self.iom
+        assert 2 not in self.iom
+        assert 3 not in self.iom
+        assert self.iom._keylist_head.next is self.iom._keylist_tail
+        assert self.iom._keylist_tail.prev is self.iom._keylist_head
+        assert len(self.iom) == 0
+
+    def test_copy(self):
+        assert self.iom.copy() == self.iom
+
+    def test_get(self):
+        assert self.iom.get(0) is None
+        assert self.iom.get(0, "x") is "x"
+        assert self.iom.get(1) == "a"
+
+    def test_has_key(self):
+        assert not self.iom.has_key(0)
+        assert self.iom.has_key(1)
+        assert self.iom.has_key(2)
+        assert self.iom.has_key(3)
+
+    def test_items(self):
+        assert self.iom.items() == [(2, "b"), (3, "c"), (1, "a")]
+
+    def test_iteritems(self):
+        assert list(self.iom.iteritems()) == [(2, "b"), (3, "c"), (1, "a")]
+
+    def test_iterkeys(self):
+        assert list(self.iom.iterkeys()) == [2, 3, 1]
+
+    def test_itervalues(self):
+        assert list(self.iom.itervalues()) == ["b", "c", "a"]
+
+    def test_keys(self):
+        assert self.iom.keys() == [2, 3, 1]
+
+    def test_pop(self):
+        try:
+            self.iom.pop(0)
+        except KeyError:
+            pass
+        else:
+            assert False
+        assert self.iom.pop(0, "x") == "x"
+        assert self.iom.pop(1) == "a"
+        assert 1 not in self.iom
+        assert len(self.iom) == 2
+
+    def test_popitem(self):
+        assert self.iom.popitem() == (2, "b")
+        assert self.iom.popitem() == (3, "c")
+        assert self.iom.popitem() == (1, "a")
+        try:
+            self.iom.popitem()
+        except KeyError:
+            pass
+        else:
+            assert False
+
+    def test_reviteritems(self):
+        assert list(self.iom.reviteritems()) == [(1, "a"), (3, "c"), (2, "b")]
+
+    def test_reviterkeys(self):
+        assert list(self.iom.reviterkeys()) == [1, 3, 2]
+
+    def test_revitervalues(self):
+        assert list(self.iom.revitervalues()) == ["a", "c", "b"]
+
+    def test_setdefault(self):
+        assert self.iom.setdefault(0, "x") == "x"
+        assert self.iom.setdefault(1, "x") == "a"
+        assert self.iom.setdefault(4) is None
+
+    def test_update(self):
+        self.iom.update([(0, "x"), (4, "d")])
+        assert self.iom.items() == [
+            (4, "d"), (0, "x"), (2, "b"), (3, "c"), (1, "a")]
+
+    def test_values(self):
+        assert self.iom.values() == ["b", "c", "a"]
+
+######################################################################
+
+if __name__ == "__main__":
+    unittest.main()