"Fossies" - the Fresh Open Source Software Archive

Member "Atom/resources/app/apm/node_modules/node-gyp/gyp/pylib/gyp/ordered_dict.py" (11 Apr 2017, 10366 Bytes) of package /windows/misc/atom-windows.zip:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Python source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

    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