Copy git tooling into testing_support.

testing_support/git/util.py

+# 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
+
+
+