astdicts.py

Go to the documentation of this file.
00001 # Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pypy.
00002 # Passes Python2.7's test suite and incorporates all the latest updates.
00003 # copied from http://code.activestate.com/recipes/576693/
00004 
00005 try:
00006     from thread import get_ident as _get_ident
00007 except ImportError:
00008     from dummy_thread import get_ident as _get_ident
00009 
00010 try:
00011     from _abcoll import KeysView, ValuesView, ItemsView
00012 except ImportError:
00013     pass
00014 
00015 
00016 class OrderedDict(dict):
00017     'Dictionary that remembers insertion order'
00018     # An inherited dict maps keys to values.
00019     # The inherited dict provides __getitem__, __len__, __contains__, and get.
00020     # The remaining methods are order-aware.
00021     # Big-O running times for all methods are the same as for regular dictionaries.
00022 
00023     # The internal self.__map dictionary maps keys to links in a doubly linked list.
00024     # The circular doubly linked list starts and ends with a sentinel element.
00025     # The sentinel element never gets deleted (this simplifies the algorithm).
00026     # Each link is stored as a list of length three:  [PREV, NEXT, KEY].
00027 
00028     def __init__(self, *args, **kwds):
00029         '''Initialize an ordered dictionary.  Signature is the same as for
00030         regular dictionaries, but keyword arguments are not recommended
00031         because their insertion order is arbitrary.
00032 
00033         '''
00034         if len(args) > 1:
00035             raise TypeError('expected at most 1 arguments, got %d' % len(args))
00036         try:
00037             self.__root
00038         except AttributeError:
00039             self.__root = root = []                     # sentinel node
00040             root[:] = [root, root, None]
00041             self.__map = {}
00042         self.__update(*args, **kwds)
00043 
00044     def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
00045         'od.__setitem__(i, y) <==> od[i]=y'
00046         # Setting a new item creates a new link which goes at the end of the linked
00047         # list, and the inherited dictionary is updated with the new key/value pair.
00048         if key not in self:
00049             root = self.__root
00050             last = root[0]
00051             last[1] = root[0] = self.__map[key] = [last, root, key]
00052         dict_setitem(self, key, value)
00053 
00054     def __delitem__(self, key, dict_delitem=dict.__delitem__):
00055         'od.__delitem__(y) <==> del od[y]'
00056         # Deleting an existing item uses self.__map to find the link which is
00057         # then removed by updating the links in the predecessor and successor nodes.
00058         dict_delitem(self, key)
00059         link_prev, link_next, key = self.__map.pop(key)
00060         link_prev[1] = link_next
00061         link_next[0] = link_prev
00062 
00063     def __iter__(self):
00064         'od.__iter__() <==> iter(od)'
00065         root = self.__root
00066         curr = root[1]
00067         while curr is not root:
00068             yield curr[2]
00069             curr = curr[1]
00070 
00071     def __reversed__(self):
00072         'od.__reversed__() <==> reversed(od)'
00073         root = self.__root
00074         curr = root[0]
00075         while curr is not root:
00076             yield curr[2]
00077             curr = curr[0]
00078 
00079     def clear(self):
00080         'od.clear() -> None.  Remove all items from od.'
00081         try:
00082             for node in self.__map.itervalues():
00083                 del node[:]
00084             root = self.__root
00085             root[:] = [root, root, None]
00086             self.__map.clear()
00087         except AttributeError:
00088             pass
00089         dict.clear(self)
00090 
00091     def popitem(self, last=True):
00092         '''od.popitem() -> (k, v), return and remove a (key, value) pair.
00093         Pairs are returned in LIFO order if last is true or FIFO order if false.
00094 
00095         '''
00096         if not self:
00097             raise KeyError('dictionary is empty')
00098         root = self.__root
00099         if last:
00100             link = root[0]
00101             link_prev = link[0]
00102             link_prev[1] = root
00103             root[0] = link_prev
00104         else:
00105             link = root[1]
00106             link_next = link[1]
00107             root[1] = link_next
00108             link_next[0] = root
00109         key = link[2]
00110         del self.__map[key]
00111         value = dict.pop(self, key)
00112         return key, value
00113 
00114     # -- the following methods do not depend on the internal structure --
00115 
00116     def keys(self):
00117         'od.keys() -> list of keys in od'
00118         return list(self)
00119 
00120     def values(self):
00121         'od.values() -> list of values in od'
00122         return [self[key] for key in self]
00123 
00124     def items(self):
00125         'od.items() -> list of (key, value) pairs in od'
00126         return [(key, self[key]) for key in self]
00127 
00128     def iterkeys(self):
00129         'od.iterkeys() -> an iterator over the keys in od'
00130         return iter(self)
00131 
00132     def itervalues(self):
00133         'od.itervalues -> an iterator over the values in od'
00134         for k in self:
00135             yield self[k]
00136 
00137     def iteritems(self):
00138         'od.iteritems -> an iterator over the (key, value) items in od'
00139         for k in self:
00140             yield (k, self[k])
00141 
00142     def update(*args, **kwds):
00143         '''od.update(E, **F) -> None.  Update od from dict/iterable E and F.
00144 
00145         If E is a dict instance, does:           for k in E: od[k] = E[k]
00146         If E has a .keys() method, does:         for k in E.keys(): od[k] = E[k]
00147         Or if E is an iterable of items, does:   for k, v in E: od[k] = v
00148         In either case, this is followed by:     for k, v in F.items(): od[k] = v
00149 
00150         '''
00151         if len(args) > 2:
00152             raise TypeError('update() takes at most 2 positional '
00153                             'arguments (%d given)' % (len(args),))
00154         elif not args:
00155             raise TypeError('update() takes at least 1 argument (0 given)')
00156         self = args[0]
00157         # Make progressively weaker assumptions about "other"
00158         other = ()
00159         if len(args) == 2:
00160             other = args[1]
00161         if isinstance(other, dict):
00162             for key in other:
00163                 self[key] = other[key]
00164         elif hasattr(other, 'keys'):
00165             for key in other.keys():
00166                 self[key] = other[key]
00167         else:
00168             for key, value in other:
00169                 self[key] = value
00170         for key, value in kwds.items():
00171             self[key] = value
00172 
00173     __update = update  # let subclasses override update without breaking __init__
00174 
00175     __marker = object()
00176 
00177     def pop(self, key, default=__marker):
00178         '''od.pop(k[,d]) -> v, remove specified key and return the corresponding value.
00179         If key is not found, d is returned if given, otherwise KeyError is raised.
00180 
00181         '''
00182         if key in self:
00183             result = self[key]
00184             del self[key]
00185             return result
00186         if default is self.__marker:
00187             raise KeyError(key)
00188         return default
00189 
00190     def setdefault(self, key, default=None):
00191         'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
00192         if key in self:
00193             return self[key]
00194         self[key] = default
00195         return default
00196 
00197     def __repr__(self, _repr_running={}):
00198         'od.__repr__() <==> repr(od)'
00199         call_key = id(self), _get_ident()
00200         if call_key in _repr_running:
00201             return '...'
00202         _repr_running[call_key] = 1
00203         try:
00204             if not self:
00205                 return '%s()' % (self.__class__.__name__,)
00206             return '%s(%r)' % (self.__class__.__name__, self.items())
00207         finally:
00208             del _repr_running[call_key]
00209 
00210     def __reduce__(self):
00211         'Return state information for pickling'
00212         items = [[k, self[k]] for k in self]
00213         inst_dict = vars(self).copy()
00214         for k in vars(OrderedDict()):
00215             inst_dict.pop(k, None)
00216         if inst_dict:
00217             return (self.__class__, (items,), inst_dict)
00218         return self.__class__, (items,)
00219 
00220     def copy(self):
00221         'od.copy() -> a shallow copy of od'
00222         return self.__class__(self)
00223 
00224     @classmethod
00225     def fromkeys(cls, iterable, value=None):
00226         '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
00227         and values equal to v (which defaults to None).
00228 
00229         '''
00230         d = cls()
00231         for key in iterable:
00232             d[key] = value
00233         return d
00234 
00235     def __eq__(self, other):
00236         '''od.__eq__(y) <==> od==y.  Comparison to another OD is order-sensitive
00237         while comparison to a regular mapping is order-insensitive.
00238 
00239         '''
00240         if isinstance(other, OrderedDict):
00241             return len(self)==len(other) and self.items() == other.items()
00242         return dict.__eq__(self, other)
00243 
00244     def __ne__(self, other):
00245         return not self == other
00246 
00247     # -- the following methods are only used in Python 2.7 --
00248 
00249     def viewkeys(self):
00250         "od.viewkeys() -> a set-like object providing a view on od's keys"
00251         return KeysView(self)
00252 
00253     def viewvalues(self):
00254         "od.viewvalues() -> an object providing a view on od's values"
00255         return ValuesView(self)
00256 
00257     def viewitems(self):
00258         "od.viewitems() -> a set-like object providing a view on od's items"
00259         return ItemsView(self)
00260 
00261 ###############################################################################
00262 ### MultiOrderedDict
00263 ###############################################################################
00264 class MultiOrderedDict(OrderedDict):
00265     def __init__(self, *args, **kwds):
00266         OrderedDict.__init__(self, *args, **kwds)
00267 
00268     def __setitem__(self, key, val, i=None):
00269         if key not in self:
00270 #            print "__setitem__ key = ", key, " val = ", val
00271             OrderedDict.__setitem__(
00272                 self, key, val if isinstance(val, list) else [val])
00273             return
00274 #        print "inserting key = ", key, " val = ", val
00275         vals = self[key]
00276         if i is None:
00277             i = len(vals)
00278 
00279         if not isinstance(val, list):
00280             if val not in vals:
00281                 vals.insert(i, val)
00282         else:
00283             for j in val.reverse():
00284                 if j not in vals:
00285                     vals.insert(i, j)
00286 
00287 
00288     def insert(self, i, key, val):
00289         self.__setitem__(key, val, i)
00290 
00291     def copy(self):
00292         # TODO - find out why for some reason copies
00293         #        the [] as an [[]], so do manually
00294         c = MultiOrderedDict() #self.__class__(self)
00295         for key, val in self.iteritems():
00296             for v in val:
00297                 c[key] = v
00298         return c

Generated on Thu Apr 16 06:27:14 2015 for Asterisk - The Open Source Telephony Project by  doxygen 1.5.6