Mercurial > parpg-source

annotate common/ordereddict.py @ 24:eab8af30dfc7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
get_free_slot no raises an exception instead of appending a slot to the container.
author KarstenBock@gmx.net
date Fri, 02 Sep 2011 12:54:43 +0200
parents 7a89ea5404b1
children
rev   line source
0
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
1 # Copyright (c) 2009 Raymond Hettinger
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
2 #
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
3 # Permission is hereby granted, free of charge, to any person
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
4 # obtaining a copy of this software and associated documentation files
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
5 # (the "Software"), to deal in the Software without restriction,
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
6 # including without limitation the rights to use, copy, modify, merge,
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
7 # publish, distribute, sublicense, and/or sell copies of the Software,
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
8 # and to permit persons to whom the Software is furnished to do so,
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
9 # subject to the following conditions:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
10 #
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
11 # The above copyright notice and this permission notice shall be
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
12 # included in all copies or substantial portions of the Software.
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
13 #
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
14 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
15 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
16 # OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
17 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
18 # HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
19 # WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
20 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
21 # OTHER DEALINGS IN THE SOFTWARE.
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
22
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
23 from UserDict import DictMixin
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
24
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
25 class OrderedDict(dict, DictMixin):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
26
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
27 def __init__(self, *args, **kwds):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
28 if len(args) > 1:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
29 raise TypeError('expected at most 1 arguments, got %d' % len(args))
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
30 try:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
31 self.__end
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
32 except AttributeError:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
33 self.clear()
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
34 self.update(*args, **kwds)
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
35
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
36 def clear(self):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
37 self.__end = end = []
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
38 end += [None, end, end] # sentinel node for doubly linked list
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
39 self.__map = {} # key --> [key, prev, next]
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
40 dict.clear(self)
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
41
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
42 def __setitem__(self, key, value):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
43 if key not in self:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
44 end = self.__end
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
45 curr = end[1]
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
46 curr[2] = end[1] = self.__map[key] = [key, curr, end]
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
47 dict.__setitem__(self, key, value)
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
48
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
49 def __delitem__(self, key):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
50 dict.__delitem__(self, key)
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
51 key, prev, next = self.__map.pop(key)
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
52 prev[2] = next
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
53 next[1] = prev
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
54
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
55 def __iter__(self):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
56 end = self.__end
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
57 curr = end[2]
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
58 while curr is not end:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
59 yield curr[0]
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
60 curr = curr[2]
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
61
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
62 def __reversed__(self):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
63 end = self.__end
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
64 curr = end[1]
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
65 while curr is not end:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
66 yield curr[0]
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
67 curr = curr[1]
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
68
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
69 def popitem(self, last=True):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
70 if not self:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
71 raise KeyError('dictionary is empty')
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
72 if last:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
73 key = reversed(self).next()
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
74 else:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
75 key = iter(self).next()
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
76 value = self.pop(key)
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
77 return key, value
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
78
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
79 def __reduce__(self):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
80 items = [[k, self[k]] for k in self]
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
81 tmp = self.__map, self.__end
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
82 del self.__map, self.__end
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
83 inst_dict = vars(self).copy()
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
84 self.__map, self.__end = tmp
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
85 if inst_dict:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
86 return (self.__class__, (items,), inst_dict)
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
87 return self.__class__, (items,)
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
88
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
89 def keys(self):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
90 return list(self)
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
91
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
92 setdefault = DictMixin.setdefault
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
93 update = DictMixin.update
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
94 pop = DictMixin.pop
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
95 values = DictMixin.values
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
96 items = DictMixin.items
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
97 iterkeys = DictMixin.iterkeys
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
98 itervalues = DictMixin.itervalues
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
99 iteritems = DictMixin.iteritems
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
100
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
101 def __repr__(self):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
102 if not self:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
103 return '%s()' % (self.__class__.__name__,)
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
104 return '%s(%r)' % (self.__class__.__name__, self.items())
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
105
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
106 def copy(self):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
107 return self.__class__(self)
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
108
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
109 @classmethod
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
110 def fromkeys(cls, iterable, value=None):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
111 d = cls()
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
112 for key in iterable:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
113 d[key] = value
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
114 return d
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
115
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
116 def __eq__(self, other):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
117 if isinstance(other, OrderedDict):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
118 if len(self) != len(other):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
119 return False
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
120 for p, q in zip(self.items(), other.items()):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
121 if p != q:
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
122 return False
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
123 return True
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
124 return dict.__eq__(self, other)
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
125
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
126 def __ne__(self, other):
7a89ea5404b1 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
127 return not self == other