Mercurial > parpg-source

annotate common/ordereddict.py @ 115:26e65f27dbd7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"Open" will now not be shown in the context menu when the lockable is locked. "Lock" will not not be shown in the context menu when the lockable is open.
author KarstenBock@gmx.net
date Mon, 03 Oct 2011 14:12:17 +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