www.aleph1.co.uk Git - yaffs-website/blob - node_modules/node-gyp/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     # Suppress 'OrderedDict.update: Method has no argument':
 170     # pylint: disable=E0211
 171     def update(*args, **kwds):
 172         '''od.update(E, **F) -> None.  Update od from dict/iterable E and F.
 173
 174         If E is a dict instance, does:           for k in E: od[k] = E[k]
 175         If E has a .keys() method, does:         for k in E.keys(): od[k] = E[k]
 176         Or if E is an iterable of items, does:   for k, v in E: od[k] = v
 177         In either case, this is followed by:     for k, v in F.items(): od[k] = v
 178
 179         '''
 180         if len(args) > 2:
 181             raise TypeError('update() takes at most 2 positional '
 182                             'arguments (%d given)' % (len(args),))
 183         elif not args:
 184             raise TypeError('update() takes at least 1 argument (0 given)')
 185         self = args[0]
 186         # Make progressively weaker assumptions about "other"
 187         other = ()
 188         if len(args) == 2:
 189             other = args[1]
 190         if isinstance(other, dict):
 191             for key in other:
 192                 self[key] = other[key]
 193         elif hasattr(other, 'keys'):
 194             for key in other.keys():
 195                 self[key] = other[key]
 196         else:
 197             for key, value in other:
 198                 self[key] = value
 199         for key, value in kwds.items():
 200             self[key] = value
 201
 202     __update = update  # let subclasses override update without breaking __init__
 203
 204     __marker = object()
 205
 206     def pop(self, key, default=__marker):
 207         '''od.pop(k[,d]) -> v, remove specified key and return the corresponding value.
 208         If key is not found, d is returned if given, otherwise KeyError is raised.
 209
 210         '''
 211         if key in self:
 212             result = self[key]
 213             del self[key]
 214             return result
 215         if default is self.__marker:
 216             raise KeyError(key)
 217         return default
 218
 219     def setdefault(self, key, default=None):
 220         'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'
 221         if key in self:
 222             return self[key]
 223         self[key] = default
 224         return default
 225
 226     def __repr__(self, _repr_running={}):
 227         'od.__repr__() <==> repr(od)'
 228         call_key = id(self), _get_ident()
 229         if call_key in _repr_running:
 230             return '...'
 231         _repr_running[call_key] = 1
 232         try:
 233             if not self:
 234                 return '%s()' % (self.__class__.__name__,)
 235             return '%s(%r)' % (self.__class__.__name__, self.items())
 236         finally:
 237             del _repr_running[call_key]
 238
 239     def __reduce__(self):
 240         'Return state information for pickling'
 241         items = [[k, self[k]] for k in self]
 242         inst_dict = vars(self).copy()
 243         for k in vars(OrderedDict()):
 244             inst_dict.pop(k, None)
 245         if inst_dict:
 246             return (self.__class__, (items,), inst_dict)
 247         return self.__class__, (items,)
 248
 249     def copy(self):
 250         'od.copy() -> a shallow copy of od'
 251         return self.__class__(self)
 252
 253     @classmethod
 254     def fromkeys(cls, iterable, value=None):
 255         '''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S
 256         and values equal to v (which defaults to None).
 257
 258         '''
 259         d = cls()
 260         for key in iterable:
 261             d[key] = value
 262         return d
 263
 264     def __eq__(self, other):
 265         '''od.__eq__(y) <==> od==y.  Comparison to another OD is order-sensitive
 266         while comparison to a regular mapping is order-insensitive.
 267
 268         '''
 269         if isinstance(other, OrderedDict):
 270             return len(self)==len(other) and self.items() == other.items()
 271         return dict.__eq__(self, other)
 272
 273     def __ne__(self, other):
 274         return not self == other
 275
 276     # -- the following methods are only used in Python 2.7 --
 277
 278     def viewkeys(self):
 279         "od.viewkeys() -> a set-like object providing a view on od's keys"
 280         return KeysView(self)
 281
 282     def viewvalues(self):
 283         "od.viewvalues() -> an object providing a view on od's values"
 284         return ValuesView(self)
 285
 286     def viewitems(self):
 287         "od.viewitems() -> a set-like object providing a view on od's items"
 288         return ItemsView(self)
 289