diff options
Diffstat (limited to 'deps/gyp/pylib/gyp/common.py')
-rw-r--r-- | deps/gyp/pylib/gyp/common.py | 67 |
1 files changed, 67 insertions, 0 deletions
diff --git a/deps/gyp/pylib/gyp/common.py b/deps/gyp/pylib/gyp/common.py index f9c6c6f3a8..df71d973e1 100644 --- a/deps/gyp/pylib/gyp/common.py +++ b/deps/gyp/pylib/gyp/common.py @@ -4,6 +4,7 @@ from __future__ import with_statement +import collections import errno import filecmp import os.path @@ -472,6 +473,72 @@ def uniquer(seq, idfun=None): return result +# Based on http://code.activestate.com/recipes/576694/. +class OrderedSet(collections.MutableSet): + def __init__(self, iterable=None): + self.end = end = [] + end += [None, end, end] # sentinel node for doubly linked list + self.map = {} # key --> [key, prev, next] + if iterable is not None: + self |= iterable + + def __len__(self): + return len(self.map) + + def __contains__(self, key): + return key in self.map + + def add(self, key): + if key not in self.map: + end = self.end + curr = end[1] + curr[2] = end[1] = self.map[key] = [key, curr, end] + + def discard(self, key): + if key in self.map: + key, prev_item, next_item = self.map.pop(key) + prev_item[2] = next_item + next_item[1] = prev_item + + def __iter__(self): + end = self.end + curr = end[2] + while curr is not end: + yield curr[0] + curr = curr[2] + + def __reversed__(self): + end = self.end + curr = end[1] + while curr is not end: + yield curr[0] + curr = curr[1] + + # The second argument is an addition that causes a pylint warning. + def pop(self, last=True): # pylint: disable=W0221 + if not self: + raise KeyError('set is empty') + key = self.end[1][0] if last else self.end[2][0] + self.discard(key) + return key + + def __repr__(self): + if not self: + return '%s()' % (self.__class__.__name__,) + return '%s(%r)' % (self.__class__.__name__, list(self)) + + def __eq__(self, other): + if isinstance(other, OrderedSet): + return len(self) == len(other) and list(self) == list(other) + return set(self) == set(other) + + # Extensions to the recipe. + def update(self, iterable): + for i in iterable: + if i not in self: + self.add(i) + + class CycleError(Exception): """An exception raised when an unexpected cycle is detected.""" def __init__(self, nodes): |