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


UCC Code Repository

Contents of /bunnyblog/modules/odict.py

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1 - (hide 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 svn-admin 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