Mercurial > parpg-core

comparison src/parpg/common/ordereddict.py @ 0:1fd2201f5c36

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