/[theodore]/pyBB/modules/odict.py


UCC Code Repository

Contents of /pyBB/modules/odict.py

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1 - (show annotations) (download) (as text)
Tue Jan 29 14:32:01 2008 UTC (12 years, 2 months ago) by svn-admin
File MIME type: text/x-python
File size: 12483 byte(s)
Re-import of repository after repository database corruption.

1 # odict.py
2 # An Ordered Dictionary object
3 # Copyright (C) 2005 Nicola Larosa, Michael Foord
4 # E-mail: nico-NoSp@m-tekNico.net, fuzzyman AT voidspace DOT org DOT uk
5
6 # This software is licensed under the terms of the BSD license.
7 # http://www.voidspace.org.uk/documents/BSD-LICENSE.txt
8 # Basically you're free to copy, modify, distribute and relicense it,
9 # So long as you keep a copy of the license with it.
10
11 # Scripts maintained at http://www.voidspace.org.uk/python/index.shtml
12 # For information about bugfixes, updates and support, please join the
13 # Rest2Web mailing list:
14 # http://lists.sourceforge.net/lists/listinfo/rest2web-develop
15 # Comments, suggestions and bug reports welcome.
16
17 """A dict that keeps keys in insertion order"""
18
19 __author__ = ('Nicola Larosa <nico-NoSp@m-tekNico.net>,'
20 'Michael Foord <fuzzyman AT voidspace DOT org DOT uk>')
21
22 __docformat__ = "restructuredtext en"
23
24 __revision__ = '$Id: odict.py 129 2005-09-12 18:15:28Z teknico $'
25
26 __version__ = '0.1.2'
27
28 __all__ = ['OrderedDict']
29
30 from __future__ import generators
31
32 import sys
33 INTP_VER = sys.version_info[:2]
34 if INTP_VER < (2, 2):
35 raise RuntimeError("Python v.2.2 or later needed")
36
37 class OrderedDict(dict):
38 """
39 A class of dictionary that keeps the insertion order of keys.
40
41 All appropriate methods return keys, items, or values in an ordered way,
42 following the order of the ``sequence`` attribute.
43
44 All normal dictionary methods are available. Update and comparison is
45 restricted to other OrderedDict objects.
46
47 __contains__ tests:
48
49 >>> d = OrderedDict(((1, 3),))
50 >>> 1 in d
51 1
52 >>> 4 in d
53 0
54
55 __getitem__ tests:
56
57 >>> OrderedDict(((1, 3), (3, 2), (2, 1)))[2]
58 1
59 >>> OrderedDict(((1, 3), (3, 2), (2, 1)))[4]
60 Traceback (most recent call last):
61 KeyError: 4
62
63 __len__ tests:
64
65 >>> len(OrderedDict())
66 0
67 >>> len(OrderedDict(((1, 3), (3, 2), (2, 1))))
68 3
69
70 get tests:
71
72 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
73 >>> d.get(1)
74 3
75 >>> d.get(4) is None
76 1
77
78 has_key tests:
79
80 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
81 >>> d.has_key(1)
82 1
83 >>> d.has_key(4)
84 0
85 """
86
87 def __init__(self, init_val = ()):
88 """
89 Create a new ordered dictionary. Cannot init from a normal dict,
90 nor from kwargs, since items order is undefined in those cases.
91
92 >>> OrderedDict()
93 {}
94 >>> OrderedDict({1: 1})
95 Traceback (most recent call last):
96 TypeError: undefined order, cannot get items from dict
97 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
98 >>> d
99 {1: 3, 3: 2, 2: 1}
100 >>> OrderedDict(d)
101 {1: 3, 3: 2, 2: 1}
102 """
103 dict.__init__(self)
104 self.sequence = []
105 self.update(init_val)
106
107 ### Special methods ###
108
109 def __cmp__(self, other):
110 """
111 Inequality undefined for OrderedDicts; equality managed by __eq__
112
113 >>> OrderedDict() < OrderedDict()
114 Traceback (most recent call last):
115 TypeError: Inequality undefined for OrderedDicts
116 >>> OrderedDict() < {}
117 Traceback (most recent call last):
118 TypeError: Inequality undefined for OrderedDicts
119 >>> {} < OrderedDict()
120 Traceback (most recent call last):
121 TypeError: Inequality undefined for OrderedDicts
122 """
123 raise TypeError('Inequality undefined for OrderedDicts')
124
125 def __delitem__(self, key):
126 """
127 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
128 >>> del d[3]
129 >>> d
130 {1: 3, 2: 1}
131 >>> del d[3]
132 Traceback (most recent call last):
133 KeyError: 3
134 """
135 # do the dict.__delitem__ *first* as it raises
136 # the more appropriate error
137 dict.__delitem__(self, key)
138 self.sequence.remove(key)
139
140 def __eq__(self, other):
141 """
142 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
143 >>> d == OrderedDict(d)
144 1
145 >>> d == OrderedDict(((1, 3), (2, 1), (3, 2)))
146 0
147 >>> d == OrderedDict(((1, 0), (3, 2), (2, 1)))
148 0
149 >>> d == OrderedDict(((0, 3), (3, 2), (2, 1)))
150 0
151 >>> d == dict(d)
152 Traceback (most recent call last):
153 TypeError: Can only compare with other OrderedDicts
154 """
155 if not isinstance(other, OrderedDict):
156 raise TypeError('Can only compare with other OrderedDicts')
157 return (self.items() == other.items())
158
159 def __repr__(self):
160 """
161 Used for __repr__ and __str__
162
163 >>> r1 = repr(OrderedDict((('a', 'b'), ('c', 'd'), ('e', 'f'))))
164 >>> r1
165 "{'a': 'b', 'c': 'd', 'e': 'f'}"
166 >>> r2 = repr(OrderedDict((('a', 'b'), ('e', 'f'), ('c', 'd'))))
167 >>> r2
168 "{'a': 'b', 'e': 'f', 'c': 'd'}"
169 >>> r1 == str(OrderedDict((('a', 'b'), ('c', 'd'), ('e', 'f'))))
170 1
171 >>> r2 == str(OrderedDict((('a', 'b'), ('e', 'f'), ('c', 'd'))))
172 1
173 """
174 return '{%s}' % ', '.join(
175 ['%r: %r' % (key, self[key]) for key in self.sequence])
176
177 def __setitem__(self, key, val):
178 """
179 >>> d = OrderedDict()
180 >>> d['a'] = 'b'
181 >>> d['b'] = 'a'
182 >>> d[3] = 12
183 >>> d
184 {'a': 'b', 'b': 'a', 3: 12}
185 """
186 if not self.has_key(key):
187 self.sequence.append(key)
188 dict.__setitem__(self, key, val)
189
190 __str__ = __repr__
191
192 ### Read-only methods ###
193
194 def copy(self):
195 """
196 >>> OrderedDict(((1, 3), (3, 2), (2, 1))).copy()
197 {1: 3, 3: 2, 2: 1}
198 """
199 return OrderedDict(self)
200
201 def items(self):
202 """
203 >>> OrderedDict(((1, 3), (3, 2), (2, 1))).items()
204 [(1, 3), (3, 2), (2, 1)]
205 """
206 return zip(self.sequence, self.values())
207
208 def keys(self):
209 """
210 >>> OrderedDict(((1, 3), (3, 2), (2, 1))).keys()
211 [1, 3, 2]
212 """
213 return self.sequence[:]
214
215 def values(self):
216 """
217 >>> OrderedDict(((1, 3), (3, 2), (2, 1))).values()
218 [3, 2, 1]
219 """
220 return [self[key] for key in self.sequence]
221
222 def iteritems(self):
223 """
224 >>> ii = OrderedDict(((1, 3), (3, 2), (2, 1))).iteritems()
225 >>> ii.next()
226 (1, 3)
227 >>> ii.next()
228 (3, 2)
229 >>> ii.next()
230 (2, 1)
231 >>> ii.next()
232 Traceback (most recent call last):
233 StopIteration
234 """
235 def make_iter(self=self):
236 keys = self.iterkeys()
237 while True:
238 key = keys.next()
239 yield (key, self[key])
240 return make_iter()
241
242 def iterkeys(self):
243 """
244 >>> ii = OrderedDict(((1, 3), (3, 2), (2, 1))).iterkeys()
245 >>> ii.next()
246 1
247 >>> ii.next()
248 3
249 >>> ii.next()
250 2
251 >>> ii.next()
252 Traceback (most recent call last):
253 StopIteration
254 """
255 return iter(self.sequence)
256
257 __iter__ = iterkeys
258
259 def itervalues(self):
260 """
261 >>> iv = OrderedDict(((1, 3), (3, 2), (2, 1))).itervalues()
262 >>> iv.next()
263 3
264 >>> iv.next()
265 2
266 >>> iv.next()
267 1
268 >>> iv.next()
269 Traceback (most recent call last):
270 StopIteration
271 """
272 def make_iter(self=self):
273 keys = self.iterkeys()
274 while True:
275 yield self[keys.next()]
276 return make_iter()
277
278 ### Read-write methods ###
279
280 def clear(self):
281 """
282 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
283 >>> d.clear()
284 >>> d
285 {}
286 """
287 dict.clear(self)
288 self.sequence = []
289
290 def pop(self, key, *args):
291 """
292 No dict.pop in Python 2.2, gotta reimplement it
293
294 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
295 >>> d.pop(3)
296 2
297 >>> d
298 {1: 3, 2: 1}
299 >>> d.pop(4)
300 Traceback (most recent call last):
301 KeyError: 4
302 >>> d.pop(4, 0)
303 0
304 >>> d.pop(4, 0, 1)
305 Traceback (most recent call last):
306 TypeError: pop expected at most 2 arguments, got 3
307 """
308 if len(args) > 1:
309 raise TypeError, ('pop expected at most 2 arguments, got %s' %
310 (len(args) + 1))
311 if key in self:
312 val = self[key]
313 del self[key]
314 else:
315 try:
316 val = args[0]
317 except IndexError:
318 raise KeyError(key)
319 return val
320
321 def popitem(self):
322 """
323 Always delete and return the last item, not a random one as in dict
324
325 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
326 >>> d.popitem()
327 (2, 1)
328 >>> d
329 {1: 3, 3: 2}
330 >>> OrderedDict().popitem()
331 Traceback (most recent call last):
332 KeyError
333 """
334 try:
335 key = self.sequence[-1]
336 except IndexError:
337 raise KeyError
338 val = self[key]
339 del self[key]
340 return (key, val)
341
342 def setdefault(self, key, defval = None):
343 """
344 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
345 >>> d.setdefault(1)
346 3
347 >>> d.setdefault(4) is None
348 1
349 >>> d
350 {1: 3, 3: 2, 2: 1, 4: None}
351 >>> d.setdefault(5, 0)
352 0
353 >>> d
354 {1: 3, 3: 2, 2: 1, 4: None, 5: 0}
355 """
356 if key in self:
357 return self[key]
358 else:
359 self[key] = defval
360 return defval
361
362 def update(self, from_od):
363 """
364 Update from another OrderedDict or sequence of (key, value) pairs
365
366 >>> d = OrderedDict()
367 >>> d.update(OrderedDict(((1, 3), (3, 2), (2, 1))))
368 >>> d
369 {1: 3, 3: 2, 2: 1}
370 >>> d.update({4: 4})
371 Traceback (most recent call last):
372 TypeError: undefined order, cannot get items from dict
373 >>> d.update((4, 4))
374 Traceback (most recent call last):
375 TypeError: cannot convert dictionary update sequence element #0 to a sequence
376 """
377 if isinstance(from_od, OrderedDict):
378 for key, val in from_od.items():
379 self[key] = val
380 elif isinstance(from_od, dict):
381 # we lose compatibility with other ordered dict types this way
382 raise TypeError('undefined order, cannot get items from dict')
383 else:
384 idx = 0
385 # sequence of 2-item sequences, or error
386 for item in from_od:
387 try:
388 key, val = item
389 except TypeError:
390 raise TypeError('cannot convert dictionary update'
391 ' sequence element #%d to a sequence' % idx)
392 self[key] = val
393 idx += 1
394
395 if __name__ == '__main__':
396 # run the code tests in doctest format
397 import doctest
398 m = sys.modules.get('__main__')
399 globs = m.__dict__.copy()
400 globs.update({
401 'INTP_VER': INTP_VER,
402 })
403 doctest.testmod(m, globs=globs)
404
405 """
406 CHANGELOG
407 =========
408
409 2005/09/10
410 ----------
411
412 By Nicola Larosa, based on code from Tim Wegener
413 <twegener AT radlogic DOT com DOT au>
414
415 Create itervalues and iteritems without creating the list up-front
416
417 Added doctests for iter methods, and others.
418
419 Optimized __setitem__ to be O(1) rather than O(N)
420
421 Removed redefined methods that did not alter dict method behaviour,
422 related doctests moved to the class docstring
423
424 Added support for sequences of (key, value) pairs to update
425
426 Removed redundant condition from __eq__
427
428 Removed incorrect implementation of __str__
429
430 2005/08/28
431 ----------
432
433 By Michael Foord
434
435 Added __all__
436
437 More than two arguments to ``pop`` now raises an error
438
439 Version 0.1.0 finalised
440
441 2005/08/13
442 ----------
443
444 By Nicola Larosa
445
446 Added doctests everywhere, fixed much part of implementation
447
448 Added comments at top, other doc vars
449
450 2005/08/01
451 ----------
452
453 By Michael Foord
454
455 Type tests changed to isinstance
456
457 _keys changed to sequence attribute
458
459 Allowed creating a dictionary by passing keyword arguments
460
461 Shortened __repr__
462
463 Fixed bug in popitem
464
465 Other minor changes
466 """
467

Managed by UCC Webmasters ViewVC Help
Powered by ViewVC 1.1.26