Mercurial > parpg-core

annotate src/parpg/common/ordereddict.py @ 31:ff198b1168af

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
TimeDelta parameter is now correct
author KarstenBock@gmx.net
date Thu, 14 Jul 2011 10:44:51 +0200
parents 1fd2201f5c36
children
rev   line source
0
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
1 # Copyright (c) 2009 Raymond Hettinger
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
2 #
1fd2201f5c36 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
1fd2201f5c36 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
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
5 # (the "Software"), to deal in the Software without restriction,
1fd2201f5c36 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,
1fd2201f5c36 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,
1fd2201f5c36 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,
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
9 # subject to the following conditions:
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
10 #
1fd2201f5c36 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
1fd2201f5c36 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.
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
13 #
1fd2201f5c36 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,
1fd2201f5c36 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
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
16 # OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
17 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
1fd2201f5c36 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,
1fd2201f5c36 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
1fd2201f5c36 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
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
21 # OTHER DEALINGS IN THE SOFTWARE.
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
22
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
23 from UserDict import DictMixin
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
24
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
25 class OrderedDict(dict, DictMixin):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
26
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
27 def __init__(self, *args, **kwds):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
28 if len(args) > 1:
1fd2201f5c36 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))
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
30 try:
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
31 self.__end
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
32 except AttributeError:
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
33 self.clear()
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
34 self.update(*args, **kwds)
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
35
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
36 def clear(self):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
37 self.__end = end = []
1fd2201f5c36 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
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
39 self.__map = {} # key --> [key, prev, next]
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
40 dict.clear(self)
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
41
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
42 def __setitem__(self, key, value):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
43 if key not in self:
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
44 end = self.__end
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
45 curr = end[1]
1fd2201f5c36 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]
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
47 dict.__setitem__(self, key, value)
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
48
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
49 def __delitem__(self, key):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
50 dict.__delitem__(self, key)
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
51 key, prev, next = self.__map.pop(key)
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
52 prev[2] = next
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
53 next[1] = prev
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
54
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
55 def __iter__(self):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
56 end = self.__end
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
57 curr = end[2]
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
58 while curr is not end:
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
59 yield curr[0]
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
60 curr = curr[2]
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
61
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
62 def __reversed__(self):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
63 end = self.__end
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
64 curr = end[1]
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
65 while curr is not end:
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
66 yield curr[0]
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
67 curr = curr[1]
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
68
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
69 def popitem(self, last=True):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
70 if not self:
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
71 raise KeyError('dictionary is empty')
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
72 if last:
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
73 key = reversed(self).next()
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
74 else:
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
75 key = iter(self).next()
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
76 value = self.pop(key)
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
77 return key, value
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
78
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
79 def __reduce__(self):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
80 items = [[k, self[k]] for k in self]
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
81 tmp = self.__map, self.__end
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
82 del self.__map, self.__end
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
83 inst_dict = vars(self).copy()
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
84 self.__map, self.__end = tmp
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
85 if inst_dict:
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
86 return (self.__class__, (items,), inst_dict)
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
87 return self.__class__, (items,)
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
88
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
89 def keys(self):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
90 return list(self)
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
91
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
92 setdefault = DictMixin.setdefault
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
93 update = DictMixin.update
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
94 pop = DictMixin.pop
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
95 values = DictMixin.values
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
96 items = DictMixin.items
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
97 iterkeys = DictMixin.iterkeys
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
98 itervalues = DictMixin.itervalues
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
99 iteritems = DictMixin.iteritems
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
100
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
101 def __repr__(self):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
102 if not self:
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
103 return '%s()' % (self.__class__.__name__,)
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
104 return '%s(%r)' % (self.__class__.__name__, self.items())
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
105
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
106 def copy(self):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
107 return self.__class__(self)
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
108
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
109 @classmethod
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
110 def fromkeys(cls, iterable, value=None):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
111 d = cls()
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
112 for key in iterable:
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
113 d[key] = value
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
114 return d
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
115
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
116 def __eq__(self, other):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
117 if isinstance(other, OrderedDict):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
118 if len(self) != len(other):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
119 return False
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
120 for p, q in zip(self.items(), other.items()):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
121 if p != q:
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
122 return False
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
123 return True
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
124 return dict.__eq__(self, other)
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
125
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
126 def __ne__(self, other):
1fd2201f5c36 Initial commit of parpg-core.
M. George Hansen <technopolitica@gmail.com>
parents:
diff changeset
127 return not self == other