SeriesPlugin 1.0: First public version
[enigma2-plugins.git] / seriesplugin / src / OrderedDict.py
1 # Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pypy.
2 # Passes Python2.7's test suite and incorporates all the latest updates.
3
4 try:
5     from thread import get_ident as _get_ident
6 except ImportError:
7     from dummy_thread import get_ident as _get_ident
8
9 try:
10     from _abcoll import KeysView, ValuesView, ItemsView
11 except ImportError:
12     pass
13
14
15 class OrderedDict(dict):
16     'Dictionary that remembers insertion order'
17     # An inherited dict maps keys to values.
18     # The inherited dict provides __getitem__, __len__, __contains__, and get.
19     # The remaining methods are order-aware.
20     # Big-O running times for all methods are the same as for regular dictionaries.
21
22     # The internal self.__map dictionary maps keys to links in a doubly linked list.
23     # The circular doubly linked list starts and ends with a sentinel element.
24     # The sentinel element never gets deleted (this simplifies the algorithm).
25     # Each link is stored as a list of length three:  [PREV, NEXT, KEY].
26
27     def __init__(self, *args, **kwds):
28         '''Initialize an ordered dictionary.  Signature is the same as for
29         regular dictionaries, but keyword arguments are not recommended
30         because their insertion order is arbitrary.
31
32         '''
33         if len(args) > 1:
34             raise TypeError('expected at most 1 arguments, got %d' % len(args))
35         try:
36             self.__root
37         except AttributeError:
38             self.__root = root = []                     # sentinel node
39             root[:] = [root, root, None]
40             self.__map = {}
41         self.__update(*args, **kwds)
42
43     def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
44         'od.__setitem__(i, y) <==> od[i]=y'
45         # Setting a new item creates a new link which goes at the end of the linked
46         # list, and the inherited dictionary is updated with the new key/value pair.
47         if key not in self:
48             root = self.__root
49             last = root[0]
50             last[1] = root[0] = self.__map[key] = [last, root, key]
51         dict_setitem(self, key, value)
52
53     def __delitem__(self, key, dict_delitem=dict.__delitem__):
54         'od.__delitem__(y) <==> del od[y]'
55         # Deleting an existing item uses self.__map to find the link which is
56         # then removed by updating the links in the predecessor and successor nodes.
57         dict_delitem(self, key)
58         link_prev, link_next, key = self.__map.pop(key)
59         link_prev[1] = link_next
60         link_next[0] = link_prev
61
62     def __iter__(self):
63         'od.__iter__() <==> iter(od)'
64         root = self.__root
65         curr = root[1]
66         while curr is not root:
67             yield curr[2]
68             curr = curr[1]
69
70     def __reversed__(self):
71         'od.__reversed__() <==> reversed(od)'
72         root = self.__root
73         curr = root[0]
74         while curr is not root:
75             yield curr[2]
76             curr = curr[0]
77
78     def clear(self):
79         'od.clear() -> None.  Remove all items from od.'
80         try:
81             for node in self.__map.itervalues():
82                 del node[:]
83             root = self.__root
84             root[:] = [root, root, None]
85             self.__map.clear()
86         except AttributeError:
87             pass
88         dict.clear(self)
89
90     def popitem(self, last=True):
91         '''od.popitem() -> (k, v), return and remove a (key, value) pair.
92         Pairs are returned in LIFO order if last is true or FIFO order if false.
93
94         '''
95         if not self:
96             raise KeyError('dictionary is empty')
97         root = self.__root
98         if last:
99             link = root[0]
100             link_prev = link[0]
101             link_prev[1] = root
102             root[0] = link_prev
103         else:
104             link = root[1]
105             link_next = link[1]
106             root[1] = link_next
107             link_next[0] = root
108         key = link[2]
109         del self.__map[key]
110         value = dict.pop(self, key)
111         return key, value
112
113     # -- the following methods do not depend on the internal structure --
114
115     def keys(self):
116         'od.keys() -> list of keys in od'
117         return list(self)
118
119     def values(self):
120         'od.values() -> list of values in od'
121         return [self[key] for key in self]
122
123     def items(self):
124         'od.items() -> list of (key, value) pairs in od'
125         return [(key, self[key]) for key in self]
126
127     def iterkeys(self):
128         'od.iterkeys() -> an iterator over the keys in od'
129         return iter(self)
130
131     def itervalues(self):
132         'od.itervalues -> an iterator over the values in od'
133         for k in self:
134             yield self[k]
135
136     def iteritems(self):
137         'od.iteritems -> an iterator over the (key, value) items in od'
138         for k in self:
139             yield (k, self[k])
140
141     def update(*args, **kwds):
142         '''od.update(E, **F) -> None.  Update od from dict/iterable E and F.
143
144         If E is a dict instance, does:           for k in E: od[k] = E[k]
145         If E has a .keys() method, does:         for k in E.keys(): od[k] = E[k]
146         Or if E is an iterable of items, does:   for k, v in E: od[k] = v
147         In either case, this is followed by:     for k, v in F.items(): od[k] = v
148
149         '''
150         if len(args) > 2:
151             raise TypeError('update() takes at most 2 positional '
152                             'arguments (%d given)' % (len(args),))
153         elif not args:
154             raise TypeError('update() takes at least 1 argument (0 given)')
155         self = args[0]
156         # Make progressively weaker assumptions about "other"
157         other = ()
158         if len(args) == 2:
159             other = args[1]
160         if isinstance(other, dict):
161             for key in other:
162                 self[key] = other[key]
163         elif hasattr(other, 'keys'):
164             for key in other.keys():
165                 self[key] = other[key]
166         else:
167             for key, value in other:
168                 self[key] = value
169         for key, value in kwds.items():
170             self[key] = value
171
172     __update = update  # let subclasses override update without breaking __init__
173
174     __marker = object()
175
176     def pop(self, key, default=__marker):
177         '''od.pop(k[,d]) -> v, remove specified key and return the corresponding value.
178         If key is not found, d is returned if given, otherwise KeyError is raised.
179
180         '''
181         if key in self:
182             result = self[key]
183             del self[key]
184             return result
185         if default is self.__marker:
186             raise KeyError(key)
187         return default
188
189     def setdefault(self, key, default=None):
190         'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
191         if key in self:
192             return self[key]
193         self[key] = default
194         return default
195
196     def __repr__(self, _repr_running={}):
197         'od.__repr__() <==> repr(od)'
198         call_key = id(self), _get_ident()
199         if call_key in _repr_running:
200             return '...'
201         _repr_running[call_key] = 1
202         try:
203             if not self:
204                 return '%s()' % (self.__class__.__name__,)
205             return '%s(%r)' % (self.__class__.__name__, self.items())
206         finally:
207             del _repr_running[call_key]
208
209     def __reduce__(self):
210         'Return state information for pickling'
211         items = [[k, self[k]] for k in self]
212         inst_dict = vars(self).copy()
213         for k in vars(OrderedDict()):
214             inst_dict.pop(k, None)
215         if inst_dict:
216             return (self.__class__, (items,), inst_dict)
217         return self.__class__, (items,)
218
219     def copy(self):
220         'od.copy() -> a shallow copy of od'
221         return self.__class__(self)
222
223     @classmethod
224     def fromkeys(cls, iterable, value=None):
225         '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
226         and values equal to v (which defaults to None).
227
228         '''
229         d = cls()
230         for key in iterable:
231             d[key] = value
232         return d
233
234     def __eq__(self, other):
235         '''od.__eq__(y) <==> od==y.  Comparison to another OD is order-sensitive
236         while comparison to a regular mapping is order-insensitive.
237
238         '''
239         if isinstance(other, OrderedDict):
240             return len(self)==len(other) and self.items() == other.items()
241         return dict.__eq__(self, other)
242
243     def __ne__(self, other):
244         return not self == other
245
246     # -- the following methods are only used in Python 2.7 --
247
248     def viewkeys(self):
249         "od.viewkeys() -> a set-like object providing a view on od's keys"
250         return KeysView(self)
251
252     def viewvalues(self):
253         "od.viewvalues() -> an object providing a view on od's values"
254         return ValuesView(self)
255
256     def viewitems(self):
257         "od.viewitems() -> a set-like object providing a view on od's items"
258         return ItemsView(self)