util: subclass deque for Python 2.4 backwards compatibility

util: subclass deque for Python 2.4 backwards compatibility

It turns out that Python 2.4's deque type is lacking a remove method.
We can't implement remove in terms of find, because it doesn't have
find either.

--- a/mercurial/hbisect.py	Sat Jun 02 15:35:53 2012 -0500
+++ b/mercurial/hbisect.py	Fri Jun 01 17:05:31 2012 -0700
@@ -11,7 +11,7 @@
 import os, error
 from i18n import _
 from node import short, hex
-import collections, util
+import util
 
 def bisect(changelog, state):
     """find the next node (if any) for testing during a bisect search.
@@ -69,7 +69,7 @@
 
     # build children dict
     children = {}
-    visit = collections.deque([badrev])
+    visit = util.deque([badrev])
     candidates = []
     while visit:
         rev = visit.popleft()

--- a/mercurial/patch.py	Sat Jun 02 15:35:53 2012 -0500
+++ b/mercurial/patch.py	Fri Jun 01 17:05:31 2012 -0700
@@ -12,7 +12,7 @@
 from i18n import _
 from node import hex, nullid, short
 import base85, mdiff, scmutil, util, diffhelpers, copies, encoding, error
-import collections, context
+import context
 
 gitre = re.compile('diff --git a/(.*) b/(.*)')
 
@@ -1597,7 +1597,7 @@
 
     def lrugetfilectx():
         cache = {}
-        order = collections.deque()
+        order = util.deque()
         def getfilectx(f, ctx):
             fctx = ctx.filectx(f, filelog=cache.get(f))
             if f not in cache:

--- a/mercurial/revlog.py	Sat Jun 02 15:35:53 2012 -0500
+++ b/mercurial/revlog.py	Fri Jun 01 17:05:31 2012 -0700
@@ -15,7 +15,7 @@
 from node import bin, hex, nullid, nullrev
 from i18n import _
 import ancestor, mdiff, parsers, error, util, dagutil
-import struct, zlib, errno, collections
+import struct, zlib, errno
 
 _pack = struct.pack
 _unpack = struct.unpack
@@ -362,7 +362,7 @@
         """return the set of all nodes ancestral to a given node, including
          the node itself, stopping when stop is matched"""
         reachable = set((node,))
-        visit = collections.deque([node])
+        visit = util.deque([node])
         if stop:
             stopn = self.rev(stop)
         else:
@@ -389,7 +389,7 @@
         an ancestor of itself.  Results are in breadth-first order:
         parents of each rev in revs, then parents of those, etc.  Result
         does not include the null revision."""
-        visit = collections.deque(revs)
+        visit = util.deque(revs)
         seen = set([nullrev])
         while visit:
             for parent in self.parentrevs(visit.popleft()):
@@ -447,7 +447,7 @@
 
         # take all ancestors from heads that aren't in has
         missing = set()
-        visit = collections.deque(r for r in heads if r not in has)
+        visit = util.deque(r for r in heads if r not in has)
         while visit:
             r = visit.popleft()
             if r in missing:

--- a/mercurial/revset.py	Sat Jun 02 15:35:53 2012 -0500
+++ b/mercurial/revset.py	Fri Jun 01 17:05:31 2012 -0700
@@ -5,7 +5,7 @@
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
 
-import re, collections
+import re
 import parser, util, error, discovery, hbisect, phases
 import node
 import bookmarks as bookmarksmod
@@ -17,7 +17,7 @@
     """Like revlog.ancestors(), but supports followfirst."""
     cut = followfirst and 1 or None
     cl = repo.changelog
-    visit = collections.deque(revs)
+    visit = util.deque(revs)
     seen = set([node.nullrev])
     while visit:
         for parent in cl.parentrevs(visit.popleft())[:cut]:

--- a/mercurial/setdiscovery.py	Sat Jun 02 15:35:53 2012 -0500
+++ b/mercurial/setdiscovery.py	Fri Jun 01 17:05:31 2012 -0700
@@ -8,7 +8,7 @@
 
 from node import nullid
 from i18n import _
-import random, collections, util, dagutil
+import random, util, dagutil
 import phases
 
 def _updatesample(dag, nodes, sample, always, quicksamplesize=0):
@@ -18,7 +18,7 @@
     else:
         heads = dag.heads()
     dist = {}
-    visit = collections.deque(heads)
+    visit = util.deque(heads)
     seen = set()
     factor = 1
     while visit:

--- a/mercurial/treediscovery.py	Sat Jun 02 15:35:53 2012 -0500
+++ b/mercurial/treediscovery.py	Fri Jun 01 17:05:31 2012 -0700
@@ -7,7 +7,7 @@
 
 from node import nullid, short
 from i18n import _
-import util, error, collections
+import util, error
 
 def findcommonincoming(repo, remote, heads=None, force=False):
     """Return a tuple (common, fetch, heads) used to identify the common
@@ -56,7 +56,7 @@
     # a 'branch' here is a linear segment of history, with four parts:
     # head, root, first parent, second parent
     # (a branch always has two parents (or none) by definition)
-    unknown = collections.deque(remote.branches(unknown))
+    unknown = util.deque(remote.branches(unknown))
     while unknown:
         r = []
         while unknown:

--- a/mercurial/util.py	Sat Jun 02 15:35:53 2012 -0500
+++ b/mercurial/util.py	Fri Jun 01 17:05:31 2012 -0700
@@ -202,10 +202,22 @@
 
     return f
 
+try:
+    collections.deque.remove
+    deque = collections.deque
+except AttributeError:
+    # python 2.4 lacks deque.remove
+    class deque(collections.deque):
+        def remove(self, val):
+            for i, v in enumerate(self):
+                if v == val:
+                    del self[i]
+                    break
+
 def lrucachefunc(func):
     '''cache most recent results of function calls'''
     cache = {}
-    order = collections.deque()
+    order = deque()
     if func.func_code.co_argcount == 1:
         def f(arg):
             if arg not in cache:
@@ -865,7 +877,7 @@
         Returns less than L bytes if the iterator runs dry."""
         left = l
         buf = ''
-        queue = collections.deque(self._queue)
+        queue = deque(self._queue)
         while left > 0:
             # refill the queue
             if not queue: