Index: testing_support/git/util.py |
diff --git a/testing_support/git/util.py b/testing_support/git/util.py |
new file mode 100644 |
index 0000000000000000000000000000000000000000..1a102a4d7274037fea484b65d29b5b040510ae53 |
--- /dev/null |
+++ b/testing_support/git/util.py |
@@ -0,0 +1,76 @@ |
+# Copyright 2014 The Chromium Authors. All rights reserved. |
+# Use of this source code is governed by a BSD-style license that can be |
+# found in the LICENSE file. |
+ |
+import collections |
+ |
+class OrderedSet(collections.MutableSet): |
+ # from http://code.activestate.com/recipes/576694/ |
+ def __init__(self, iterable=None): |
+ self.end = end = [] |
+ end += [None, end, end] # sentinel node for doubly linked list |
+ self.data = {} # key --> [key, prev, next] |
+ if iterable is not None: |
+ self |= iterable |
+ |
+ def __contains__(self, key): |
+ return key in self.data |
+ |
+ def __eq__(self, other): |
+ if isinstance(other, OrderedSet): |
+ return len(self) == len(other) and list(self) == list(other) |
+ return set(self) == set(other) |
+ |
+ def __ne__(self, other): |
+ if isinstance(other, OrderedSet): |
+ return len(self) != len(other) or list(self) != list(other) |
+ return set(self) != set(other) |
+ |
+ def __len__(self): |
+ return len(self.data) |
+ |
+ def __iter__(self): |
+ end = self.end |
+ curr = end[2] |
+ while curr is not end: |
+ yield curr[0] |
+ curr = curr[2] |
+ |
+ def __repr__(self): |
+ if not self: |
+ return '%s()' % (self.__class__.__name__,) |
+ return '%s(%r)' % (self.__class__.__name__, list(self)) |
+ |
+ def __reversed__(self): |
+ end = self.end |
+ curr = end[1] |
+ while curr is not end: |
+ yield curr[0] |
+ curr = curr[1] |
+ |
+ def add(self, key): |
+ if key not in self.data: |
+ end = self.end |
+ curr = end[1] |
+ curr[2] = end[1] = self.data[key] = [key, curr, end] |
+ |
+ def difference_update(self, *others): |
+ for other in others: |
+ for i in other: |
+ self.discard(i) |
+ |
+ def discard(self, key): |
+ if key in self.data: |
+ key, prev, nxt = self.data.pop(key) |
+ prev[2] = nxt |
+ nxt[1] = prev |
+ |
+ 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 |
+ |
+ |
+ |