b748c7531dcde1bbfecb952f6704c700e13c7c80
[joel/kofoto.git] / src / packages / kofoto / insertionorderedmapping.py
1 """This module contains the InsertionOrderedMapping class."""
2
3 __all__ = ["InsertionOrderedMapping"]
4
5 class _KeyListNode:
6     def __init__(self, key=None):
7         self.key = key
8         self.prev = None
9         self.next = None
10
11     def insert_after(self, node):
12         assert self.prev is None
13         assert self.next is None
14         if node.next:
15             node.next.prev = self
16             self.next = node.next
17         self.prev = node
18         node.next = self
19
20     def insert_before(self, node):
21         assert self.prev is None
22         assert self.next is None
23         if node.prev:
24             node.prev.next = self
25             self.prev = node.prev
26         self.next = node
27         node.prev = self
28
29     def unlink(self):
30         if self.prev:
31             self.prev.next = self.next
32         if self.next:
33             self.next.prev = self.prev
34         self.prev = None
35         self.next = None
36
37 class InsertionOrderedMapping:
38     """A mapping datatype with keys sorted in insertion order."""
39
40     def __init__(self, items=None):
41         self._map = {} # key --> (keylistnode, value)
42         self._keylist_head = _KeyListNode()
43         self._keylist_tail = _KeyListNode()
44         self._keylist_tail.insert_after(self._keylist_head)
45         if items is not None:
46             self.update(items)
47
48     def __cmp__(self, other):
49         snode = self._keylist_head.next
50         onode = other._keylist_head.next
51         while True:
52             if snode is self._keylist_tail:
53                 if onode is other._keylist_tail:
54                     return 0
55                 else:
56                     return -1
57             elif onode is other._keylist_tail:
58                 return 1
59             elif snode.key != onode.key:
60                 return cmp(snode.key, onode.key)
61             else:
62                 sval = self._map[snode.key][1]
63                 oval = other._map[onode.key][1]
64                 if sval != oval:
65                     return cmp(sval, oval)
66             snode = snode.next
67             onode = onode.next
68
69     def __contains__(self, key):
70         return key in self._map
71
72     def __delitem__(self, key):
73         self._map[key][0].unlink()
74         del self._map[key]
75
76     def __getitem__(self, key):
77         return self._map[key][1]
78
79     def __iter__(self):
80         return self.iterkeys()
81
82     def __len__(self):
83         return len(self._map)
84
85     def __repr__(self):
86         return "InsertionOrderedMapping(%r)" % self.items()
87
88     def __setitem__(self, key, value):
89         if key in self._map:
90             node = self._map[key][0]
91             node.unlink()
92         else:
93             node = _KeyListNode(key)
94         self._map[key] = (node, value)
95         node.insert_after(self._keylist_head)
96
97     def clear(self):
98         self._map.clear()
99
100         # Break reference cycles:
101         node = self._keylist_head
102         while node is not None:
103             node.prev = None
104             node = node.next
105         self._keylist_head.unlink()
106         self._keylist_tail.unlink()
107         self._keylist_tail.insert_after(self._keylist_head)
108
109     def copy(self):
110         return InsertionOrderedMapping(self.reviteritems())
111
112     def get(self, key, default=None):
113         if key in self._map:
114             return self._map[key][1]
115         else:
116             return default
117
118     def has_key(self, key):
119         return self._map.has_key(key)
120
121     def items(self):
122         return list(self.iteritems())
123
124     def iteritems(self):
125         node = self._keylist_head.next
126         while node is not self._keylist_tail:
127             yield (node.key, self._map[node.key][1])
128             node = node.next
129
130     def iterkeys(self):
131         node = self._keylist_head.next
132         while node is not self._keylist_tail:
133             yield node.key
134             node = node.next
135
136     def itervalues(self):
137         node = self._keylist_head.next
138         while node is not self._keylist_tail:
139             yield self._map[node.key][1]
140             node = node.next
141
142     def keys(self):
143         return list(self.iterkeys())
144
145     def pop(self, key, default=None):
146         if key in self._map:
147             value = self[key]
148             del self[key]
149             return value
150         else:
151             if default is None:
152                 raise KeyError(key)
153             else:
154                 return default
155
156     def popitem(self):
157         if len(self) == 0:
158             raise KeyError
159         else:
160             key = self._keylist_head.next.key
161             value = self.pop(key)
162             return (key, value)
163
164     def reviteritems(self):
165         node = self._keylist_tail.prev
166         while node is not self._keylist_head:
167             yield (node.key, self._map[node.key][1])
168             node = node.prev
169
170     def reviterkeys(self):
171         node = self._keylist_tail.prev
172         while node is not self._keylist_head:
173             yield node.key
174             node = node.prev
175
176     def revitervalues(self):
177         node = self._keylist_tail.prev
178         while node is not self._keylist_head:
179             yield self._map[node.key][1]
180             node = node.prev
181
182     def setdefault(self, key, value=None):
183         if key in self._map:
184             return self[key]
185         else:
186             self[key] = value
187             return value
188
189     def update(self, items):
190         for key, value in items:
191             self[key] = value
192
193     def values(self):
194         return list(self.itervalues())