tools/gyp/pylib/gyp/ordered_dict.py

   1 # Unmodified from http://code.activestate.com/recipes/576693/
   2 # other than to add MIT license header (as specified on page, but not in code).
   3 # Linked from Python documentation here:
   4 # http://docs.python.org/2/library/collections.html#collections.OrderedDict
   5 #
   6 # This should be deleted once Py2.7 is available on all bots, see
   7 # http://crbug.com/241769.
   8 #
   9 # Copyright (c) 2009 Raymond Hettinger.
  10 #
  11 # Permission is hereby granted, free of charge, to any person obtaining a copy
  12 # of this software and associated documentation files (the "Software"), to deal
  13 # in the Software without restriction, including without limitation the rights
  14 # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  15 # copies of the Software, and to permit persons to whom the Software is
  16 # furnished to do so, subject to the following conditions:
  17 #
  18 # The above copyright notice and this permission notice shall be included in
  19 # all copies or substantial portions of the Software.
  20 #
  21 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  22 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  23 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  24 # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  25 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  26 # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  27 # THE SOFTWARE.
  28
  29 # Backport of OrderedDict() class that runs on Python 2.4, 2.5, 2.6, 2.7 and pypy.
  30 # Passes Python2.7's test suite and incorporates all the latest updates.
  31
  32 try:
  33     from thread import get_ident as _get_ident
  34 except ImportError:
  35     from dummy_thread import get_ident as _get_ident
  36
  37 try:
  38     from _abcoll import KeysView, ValuesView, ItemsView
  39 except ImportError:
  40     pass
  41
  42
  43 class OrderedDict(dict):
  44     'Dictionary that remembers insertion order'
  45     # An inherited dict maps keys to values.
  46     # The inherited dict provides __getitem__, __len__, __contains__, and get.
  47     # The remaining methods are order-aware.
  48     # Big-O running times for all methods are the same as for regular dictionaries.
  49
  50     # The internal self.__map dictionary maps keys to links in a doubly linked list.
  51     # The circular doubly linked list starts and ends with a sentinel element.
  52     # The sentinel element never gets deleted (this simplifies the algorithm).
  53     # Each link is stored as a list of length three:  [PREV, NEXT, KEY].
  54
  55     def __init__(self, *args, **kwds):
  56         '''Initialize an ordered dictionary.  Signature is the same as for
  57         regular dictionaries, but keyword arguments are not recommended
  58         because their insertion order is arbitrary.
  59
  60         '''
  61         if len(args) > 1:
  62             raise TypeError('expected at most 1 arguments, got %d' % len(args))
  63         try:
  64             self.__root
  65         except AttributeError:
  66             self.__root = root = []                     # sentinel node
  67             root[:] = [root, root, None]
  68             self.__map = {}
  69         self.__update(*args, **kwds)
  70
  71     def __setitem__(self, key, value, dict_setitem=dict.__setitem__):
  72         'od.__setitem__(i, y) <==> od[i]=y'
  73         # Setting a new item creates a new link which goes at the end of the linked
  74         # list, and the inherited dictionary is updated with the new key/value pair.
  75         if key not in self:
  76             root = self.__root
  77             last = root[0]
  78             last[1] = root[0] = self.__map[key] = [last, root, key]
  79         dict_setitem(self, key, value)
  80
  81     def __delitem__(self, key, dict_delitem=dict.__delitem__):
  82         'od.__delitem__(y) <==> del od[y]'
  83         # Deleting an existing item uses self.__map to find the link which is
  84         # then removed by updating the links in the predecessor and successor nodes.
  85         dict_delitem(self, key)
  86         link_prev, link_next, key = self.__map.pop(key)
  87         link_prev[1] = link_next
  88         link_next[0] = link_prev
  89
  90     def __iter__(self):
  91         'od.__iter__() <==> iter(od)'
  92         root = self.__root
  93         curr = root[1]
  94         while curr is not root:
  95             yield curr[2]
  96             curr = curr[1]
  97
  98     def __reversed__(self):
  99         'od.__reversed__() <==> reversed(od)'
 100         root = self.__root
 101         curr = root[0]
 102         while curr is not root:
 103             yield curr[2]
 104             curr = curr[0]
 105
 106     def clear(self):
 107         'od.clear() -> None.  Remove all items from od.'
 108         try:
 109             for node in self.__map.itervalues():
 110                 del node[:]
 111             root = self.__root
 112             root[:] = [root, root, None]
 113             self.__map.clear()
 114         except AttributeError:
 115             pass
 116         dict.clear(self)
 117
 118     def popitem(self, last=True):
 119         '''od.popitem() -> (k, v), return and remove a (key, value) pair.
 120         Pairs are returned in LIFO order if last is true or FIFO order if false.
 121
 122         '''
 123         if not self:
 124             raise KeyError('dictionary is empty')
 125         root = self.__root
 126         if last:
 127             link = root[0]
 128             link_prev = link[0]
 129             link_prev[1] = root
 130             root[0] = link_prev
 131         else:
 132             link = root[1]
 133             link_next = link[1]
 134             root[1] = link_next
 135             link_next[0] = root
 136         key = link[2]
 137         del self.__map[key]
 138         value = dict.pop(self, key)
 139         return key, value
 140
 141     # -- the following methods do not depend on the internal structure --
 142
 143     def keys(self):
 144         'od.keys() -> list of keys in od'
 145         return list(self)
 146
 147     def values(self):
 148         'od.values() -> list of values in od'
 149         return [self[key] for key in self]
 150
 151     def items(self):
 152         'od.items() -> list of (key, value) pairs in od'
 153         return [(key, self[key]) for key in self]
 154
 155     def iterkeys(self):
 156         'od.iterkeys() -> an iterator over the keys in od'
 157         return iter(self)
 158
 159     def itervalues(self):
 160         'od.itervalues -> an iterator over the values in od'
 161         for k in self:
 162             yield self[k]
 163
 164     def iteritems(self):
 165         'od.iteritems -> an iterator over the (key, value) items in od'
 166         for k in self:
 167             yield (k, self[k])
 168
 169     def update(*args, **kwds):
 170         '''od.update(E, **F) -> None.  Update od from dict/iterable E and F.
 171
 172         If E is a dict instance, does:           for k in E: od[k] = E[k]
 173         If E has a .keys() method, does:         for k in E.keys(): od[k] = E[k]
 174         Or if E is an iterable of items, does:   for k, v in E: od[k] = v
 175         In either case, this is followed by:     for k, v in F.items(): od[k] = v
 176
 177         '''
 178         if len(args) > 2:
 179             raise TypeError('update() takes at most 2 positional '
 180                             'arguments (%d given)' % (len(args),))
 181         elif not args:
 182             raise TypeError('update() takes at least 1 argument (0 given)')
 183         self = args[0]
 184         # Make progressively weaker assumptions about "other"
 185         other = ()
 186         if len(args) == 2:
 187             other = args[1]
 188         if isinstance(other, dict):
 189             for key in other:
 190                 self[key] = other[key]
 191         elif hasattr(other, 'keys'):
 192             for key in other.keys():
 193                 self[key] = other[key]
 194         else:
 195             for key, value in other:
 196                 self[key] = value
 197         for key, value in kwds.items():
 198             self[key] = value
 199
 200     __update = update  # let subclasses override update without breaking __init__
 201
 202     __marker = object()
 203
 204     def pop(self, key, default=__marker):
 205         '''od.pop(k[,d]) -> v, remove specified key and return the corresponding value.
 206         If key is not found, d is returned if given, otherwise KeyError is raised.
 207
 208         '''
 209         if key in self:
 210             result = self[key]
 211             del self[key]
 212             return result
 213         if default is self.__marker:
 214             raise KeyError(key)
 215         return default
 216
 217     def setdefault(self, key, default=None):
 218         'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
 219         if key in self:
 220             return self[key]
 221         self[key] = default
 222         return default
 223
 224     def __repr__(self, _repr_running={}):
 225         'od.__repr__() <==> repr(od)'
 226         call_key = id(self), _get_ident()
 227         if call_key in _repr_running:
 228             return '...'
 229         _repr_running[call_key] = 1
 230         try:
 231             if not self:
 232                 return '%s()' % (self.__class__.__name__,)
 233             return '%s(%r)' % (self.__class__.__name__, self.items())
 234         finally:
 235             del _repr_running[call_key]
 236
 237     def __reduce__(self):
 238         'Return state information for pickling'
 239         items = [[k, self[k]] for k in self]
 240         inst_dict = vars(self).copy()
 241         for k in vars(OrderedDict()):
 242             inst_dict.pop(k, None)
 243         if inst_dict:
 244             return (self.__class__, (items,), inst_dict)
 245         return self.__class__, (items,)
 246
 247     def copy(self):
 248         'od.copy() -> a shallow copy of od'
 249         return self.__class__(self)
 250
 251     @classmethod
 252     def fromkeys(cls, iterable, value=None):
 253         '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
 254         and values equal to v (which defaults to None).
 255
 256         '''
 257         d = cls()
 258         for key in iterable:
 259             d[key] = value
 260         return d
 261
 262     def __eq__(self, other):
 263         '''od.__eq__(y) <==> od==y.  Comparison to another OD is order-sensitive
 264         while comparison to a regular mapping is order-insensitive.
 265
 266         '''
 267         if isinstance(other, OrderedDict):
 268             return len(self)==len(other) and self.items() == other.items()
 269         return dict.__eq__(self, other)
 270
 271     def __ne__(self, other):
 272         return not self == other
 273
 274     # -- the following methods are only used in Python 2.7 --
 275
 276     def viewkeys(self):
 277         "od.viewkeys() -> a set-like object providing a view on od's keys"
 278         return KeysView(self)
 279
 280     def viewvalues(self):
 281         "od.viewvalues() -> an object providing a view on od's values"
 282         return ValuesView(self)
 283
 284     def viewitems(self):
 285         "od.viewitems() -> a set-like object providing a view on od's items"
 286         return ItemsView(self)
 287