[PATCH 1 of 9 RFC] revset: added generatorset class with cached __contains__ method

[Lucas Moscovicz]

# HG changeset patch
# User Lucas Moscovicz <lmoscovicz at fb.com>
# Date 1391642591 28800
#      Wed Feb 05 15:23:11 2014 -0800
# Node ID 31c4cb808b0c3fc6484ecde3be2c9f0bcd5cad0a
# Parent  d02fafbb4786f99c8fede16521d1532477fcfa25
revset: added generatorset class with cached __contains__ method

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -2147,6 +2147,39 @@
     def set(self):
         return set([r for r in self])
 
+class generatorset(object):
+    def __init__(self, gen):
+        self._gen = gen
+        self._iter = iter(gen)
+        self._pcache = set()
+        self._ncache = set()
+
+    def __contains__(self, x):
+        if x in self._pcache:
+            return True
+        if x in self._ncache:
+            return False
+
+        while True:
+            try:
+                l = self._iter.next()
+                self._pcache.add(l)
+                if l == x:
+                    return True
+            except (StopIteration):
+                break
+
+        self._ncache.add(x)
+        return False
+
+    def __iter__(self):
+        for item in self._gen:
+            self._pcache.add(item)
+            yield item
+
+    def set(self):
+        return self
+
 class spanset(object):
     """Duck type for baseset class which represents a range of revisions and
     can work lazily and without having all the range in memory