Merge lp:~lifeless/lazr.batchnavigator/keyoffset into lp:lazr.batchnavigator

[Robert Collins]

Provide the necessary machinery (I hope!) to solve bug 752153 in Launchpad.

Essentially we change from assuming all collections are cheaply indexable by ints to assuming we can cheaply go forward or back a page of results in a SQL query. We'll need to write IRangeFactories for collections where this matters in LP, and there are some changes to URL generation (more consistency about when params are included/not included) that may cause test fallout when upgrading LP to use this version.

Care has been taken to check that existing urls will behave the same way.

[Steve Kowalik (stevenk)]

This looks great, if not a little like War and Peace to read.

I'd like to see some more real-world tests, batching something of 500-ish results, but I don't feel compelled to insist.

review: Approve (code)

[Robert Collins (lifeless)]

Thanks for the review; Once we're out of the boundary cases more results won't affect things, so I'll pass on those tests. I *may* revisit that based on experience in LP.

[lp:~lifeless/lazr.batchnavigator/keyoffset]

38. By Robert Collins on 2011-04-06

Release 1.2.3. Migrate from pure list-slicing to a more complex protocol friendly to databases.

=== modified file '.bzrignore'
--- .bzrignore	2009-03-23 16:14:28 +0000
+++ .bzrignore	2011-04-06 03:20:48 +0000
@@ -9,3 +9,5 @@
 build
 *.egg
 dist
+eggs
+.testrepository

=== added file '.testr.conf'
--- .testr.conf	1970-01-01 00:00:00 +0000
+++ .testr.conf	2011-04-06 03:20:48 +0000
@@ -0,0 +1,5 @@
+[DEFAULT]
+test_command=bin/py -m subunit.run -- $LISTOPT $IDOPTION lazr.batchnavigator.tests.test_suite
+test_id_option=--load-list $IDFILE
+test_list_option=--list
+

=== modified file 'setup.py'
--- setup.py	2011-04-03 22:07:03 +0000
+++ setup.py	2011-04-06 03:20:48 +0000
@@ -54,7 +54,9 @@
         'src/lazr/batchnavigator/NEWS.txt'),
     license='LGPL v3',
     install_requires=[
+        'fixtures',
         'setuptools',
+        'testtools',
         'zope.cachedescriptors',
         'zope.interface',
         'zope.publisher',

=== modified file 'src/lazr/batchnavigator/NEWS.txt'
--- src/lazr/batchnavigator/NEWS.txt	2010-08-19 14:23:41 +0000
+++ src/lazr/batchnavigator/NEWS.txt	2011-04-06 03:20:48 +0000
@@ -2,6 +2,14 @@
 NEWS for lazr.batchnavigator
 ============================
 
+1.2.3 (2011-04-06)
+==================
+
+- Add IRangeFactory and the ability to use backend database hints for efficient
+  retrieval of pages.
+
+- Remove terrible-scaling getBatchURLs method.
+
 1.2.2 (2010-08-19)
 ==================
 

=== modified file 'src/lazr/batchnavigator/README.txt'
--- src/lazr/batchnavigator/README.txt	2010-08-19 14:19:34 +0000
+++ src/lazr/batchnavigator/README.txt	2011-04-06 03:20:48 +0000
@@ -21,9 +21,17 @@
 page by providing URL links to the next, previous and numbered pages
 of results.
 
-It uses two arguments to control the batching:
+It uses four query/POST arguments to control the batching:
 
-  - start: The first item we should show in current batch, defaulting to 0.
+  - memo: A record of the underlying storage index pointer for the position of
+          the batch.
+  - direction: Indicates whether the memo is at the start or end of the batch.
+  - start: Cosmetic - used to calculate the apparent location (but note that
+           due to the concurrent nature of repeated visits to batches that the
+           true offset may differ - however the collection won't skip or show
+           items twice. For compatibility with saved URLs, if memo and
+           direction are both missing then start is used to do list slicing
+           into the collection.
   - batch: Controls the amount of items we are showing per batch. It will only
            appear if it's different from the default value set when the batch
            is created.
@@ -34,7 +42,7 @@
 
 Imports:
 
-    >>> from lazr.batchnavigator import BatchNavigator
+    >>> from lazr.batchnavigator import BatchNavigator, ListRangeFactory
     >>> from zope.publisher.browser import TestRequest
     >>> from zope.publisher.http import HTTPCharsets
     >>> from zope.component import getSiteManager
@@ -62,7 +70,17 @@
     >>> reindeer = ['Dasher', 'Dancer', 'Prancer', 'Vixen', 'Comet',
     ...             'Cupid', 'Donner', 'Blitzen', 'Rudolph']
 
-You can create a batch and a batch navigator like so:
+Because slicing large collections can be very expensive, BatchNavigator offers
+a non-slice protocol for determining the edge of batches. The range_factory
+supplies an object implementing IRangeFactory and manages this protocol.
+ListRangeFactory is a simple included implementation which BatchNavigator will
+use if no range_factory is supplied.
+
+    >>> _ = BatchNavigator(reindeer, build_request(),
+    ...     range_factory=ListRangeFactory(reindeer))
+
+For the examples in the documentation we let BatchNavigator construct a
+range_factory implicitly:
 
     >>> safe_reindeer = reindeer
     >>> safe_reindeer_batch_navigator = BatchNavigator(
@@ -119,14 +137,14 @@
     >>> reindeer_batch_navigator.prevBatchURL()
     ''
     >>> reindeer_batch_navigator.nextBatchURL()
-    'http://www.example.com/foo?start=3'
+    'http://www.example.com/foo?memo=3&start=3'
 
 There's no way to get the URL to the final batch without knowing the
 length of the entire list, so we'll use the safe batch navigator to
 demonstrate lastBatchURL():
 
     >>> safe_reindeer_batch_navigator.lastBatchURL()
-    'http://www.example.com/foo?start=6'
+    'http://www.example.com/foo?direction=backwards&start=6'
 
 The next link will be empty when there are no further results:
 
@@ -146,10 +164,10 @@
 one when we create the Batch object, by default, it's 5.
 
     >>> last_reindeer_batch_navigator.firstBatchURL()
-    'http://www.example.com/foo?start=0&batch=3'
+    'http://www.example.com/foo?batch=3'
 
     >>> last_reindeer_batch_navigator.prevBatchURL()
-    'http://www.example.com/foo?start=0&batch=3'
+    'http://www.example.com/foo?batch=3&direction=backwards&memo=2'
 
 This all works with other values in the query string, too:
 
@@ -167,28 +185,17 @@
 don't need to show 'batch' as part of the URL.
 
     >>> reindeer_batch_navigator_with_qs.firstBatchURL()
-    'http://www.example.com/foo?fnorb=bar&start=0'
+    'http://www.example.com/foo?fnorb=bar'
     >>> reindeer_batch_navigator_with_qs.prevBatchURL()
-    'http://www.example.com/foo?fnorb=bar&start=0'
+    'http://www.example.com/foo?fnorb=bar&direction=backwards&memo=3'
     >>> reindeer_batch_navigator_with_qs.nextBatchURL()
-    'http://www.example.com/foo?fnorb=bar&start=6'
+    'http://www.example.com/foo?fnorb=bar&memo=6&start=6'
 
 (Again, there's no way to get the last batch without knowing the size
 of the entire list.)
 
     >>> safe_reindeer_batch_navigator_with_qs.lastBatchURL()
-    'http://www.example.com/foo?fnorb=bar&start=6'
-
-You can ask for the links for each of the result pages:
-
-    >>> links = safe_reindeer_batch_navigator.batchPageURLs()
-    >>> for link in links:
-    ...     label, url = link.items()[0]
-    ...     print label, url
-    [1] http://www.example.com/foo?start=0
-    2 http://www.example.com/foo?start=3
-    3 http://www.example.com/foo?start=6
-    _last_ http://www.example.com/foo?start=6
+    'http://www.example.com/foo?fnorb=bar&direction=backwards&start=6'
 
 The ``force_start`` argument allows you to ignore the start value in the
 request.  This can be useful when, for instance, a filter has changed, and the
@@ -199,7 +206,7 @@
     >>> reindeer_batch_navigator_with_qs.currentBatch().start
     0
     >>> reindeer_batch_navigator_with_qs.nextBatchURL()
-    'http://www.example.com/foo?fnorb=bar&start=3'
+    'http://www.example.com/foo?fnorb=bar&memo=3&start=3'
     >>> reindeer[:3] == list(reindeer_batch_navigator_with_qs.currentBatch())
     True
 
@@ -215,7 +222,7 @@
     >>> reindeer_batch_navigator_post_with_qs.start
     3
     >>> reindeer_batch_navigator_post_with_qs.nextBatchURL()
-    'http://www.example.com/foo?fnorb=bar&start=6&batch=3'
+    'http://www.example.com/foo?fnorb=bar&batch=3&memo=6&start=6'
 
 We ensure that multiple size and batch arguments supplied in the URL don't
 blow up the application.  The first one is preferred.
@@ -224,7 +231,7 @@
     ...     [('batch', '1'), ('batch', '7'), ('start', '2'), ('start', '10')])
     >>> navigator = BatchNavigator(reindeer, request=request)
     >>> navigator.nextBatchURL()
-    'http://www.example.com/foo?start=3&batch=1'
+    'http://www.example.com/foo?batch=1&memo=3&start=3'
 
 The batch argument must be positive.  Other numbers are ignored, and the
 default batch size is used instead.
@@ -232,19 +239,13 @@
     >>> from cgi import parse_qs
     >>> request = build_request({'batch': '0'})
     >>> navigator = BatchNavigator(range(99), request=request)
-    >>> print navigator.default_batch_size
-    50
-    >>> for value in parse_qs(navigator.nextBatchURL())['batch']:
-    ...     print value
-    50
+    >>> print 'batch' in parse_qs(navigator.nextBatchURL())
+    False
 
     >>> request = build_request({'batch': '-1'})
     >>> navigator = BatchNavigator(range(99), request=request)
-    >>> print navigator.default_batch_size
-    50
-    >>> for value in parse_qs(navigator.nextBatchURL())['batch']:
-    ...     print value
-    50
+    >>> print 'batch' in parse_qs(navigator.nextBatchURL())
+    False
 
 
 =============
@@ -463,9 +464,9 @@
 the batch navigator.
 
     >>> navigator_with_parameters.nextBatchURL()
-    'http://www.example.com/foo?noisy=HELLO&start=3'
+    'http://www.example.com/foo?noisy=HELLO&memo=3&start=3'
     >>> safe_navigator_with_parameters.lastBatchURL()
-    'http://www.example.com/foo?noisy=HELLO&start=6'
+    'http://www.example.com/foo?noisy=HELLO&direction=backwards&start=6'
 
 The transient parameter is omitted, and the one that was never passed in
 in the first place does not magically appear.

=== modified file 'src/lazr/batchnavigator/_batchnavigator.py'
--- src/lazr/batchnavigator/_batchnavigator.py	2010-08-19 14:19:34 +0000
+++ src/lazr/batchnavigator/_batchnavigator.py	2011-04-06 03:20:48 +0000
@@ -24,9 +24,16 @@
 
 from lazr.batchnavigator.z3batching.batch import _Batch
 from lazr.batchnavigator.interfaces import (
-    IBatchNavigator, InvalidBatchSizeError, IBatchNavigatorFactory)
+    IBatchNavigator,
+    IBatchNavigatorFactory,
+    IRangeFactory,
+    InvalidBatchSizeError,
+    )
 
-__all__ = ['BatchNavigator']
+__all__ = [
+    'BatchNavigator', 
+    'ListRangeFactory',
+    ]
 
 class BatchNavigator:
 
@@ -38,6 +45,8 @@
 
     start_variable_name = 'start'
     batch_variable_name = 'batch'
+    memo_variable_name = 'memo'
+    direction_variable_name = 'direction'
 
     default_batch_size = 50
     max_batch_size = 300
@@ -66,10 +75,12 @@
         return cgi.parse_qs(query_string, keep_blank_values=True)
 
     def __init__(self, results, request, start=0, size=None, callback=None,
-                 transient_parameters=None, force_start=False):
+                 transient_parameters=None, force_start=False,
+                 range_factory=None):
         "See `IBatchNavigatorFactory.__call__`"
         self.request = request
-        local = (self.batch_variable_name, self.start_variable_name)
+        local = (self.batch_variable_name, self.start_variable_name,
+            self.memo_variable_name, self.direction_variable_name)
         self.transient_parameters = set(local)
         if transient_parameters is not None:
             self.transient_parameters.update(transient_parameters)
@@ -95,8 +106,10 @@
         # In this code we ignore invalid request variables since it
         # probably means the user finger-fumbled it in the request. We
         # could raise UnexpectedFormData, but is there a good reason?
-        request_start = batch_params_source.get(
-            self.start_variable_name, None)
+        def param_var(name):
+            return batch_params_source.get(name, None)
+        # -- start
+        request_start = param_var(self.start_variable_name)
         if force_start or request_start is None:
             self.start = start
         else:
@@ -104,15 +117,33 @@
                 self.start = int(request_start)
             except (ValueError, TypeError):
                 self.start = start
-
+        # -- size
         self.default_size = size
         request_size = self._getRequestedSize(batch_params_source)
         if request_size is not None:
             size = request_size
         if size is None:
             size = self.default_batch_size
+        # -- direction
+        direction = param_var(self.direction_variable_name)
+        if direction == 'backwards':
+            direction = False
+        else:
+            direction = None
+        # -- memo
+        memo = param_var(self.memo_variable_name)
+        if direction is not None and memo is None:
+            # Walking backwards from the end - the only case where we generate
+            # a url with no memo but a direction (and the only case where we
+            # need it: from the start with no memo is equivalent to a simple
+            # list slice anyway).
+            memo = ''
 
-        self.batch = self._batch_factory(results, start=self.start, size=size)
+        if range_factory is None:
+            range_factory = ListRangeFactory(results)
+        self.batch = self._batch_factory(results, range_factory,
+            start=self.start, size=size, range_forwards=direction,
+            range_memo=memo)
         if callback is not None:
             callback(self, self.batch)
         self.setHeadings(
@@ -161,7 +192,7 @@
         self._plural_heading = plural
 
     def getCleanQueryString(self, params=None):
-        """Removes start and batch params if present and returns a query
+        """Removes batch nav params if present and returns a query
         string.
 
         If ``params`` is None, uses the current query_string_params.
@@ -183,34 +214,35 @@
              if key not in self.transient_parameters],
              doseq=True)
 
-    def generateBatchURL(self, batch):
+    def generateBatchURL(self, batch, backwards=False):
         url = ""
         if batch is None:
             return url
 
         qs = self.getCleanQueryString()
         if qs:
-            qs += "&"
+            elements = [qs]
+        else:
+            elements = []
 
-        start = batch.startNumber() - 1
         size = batch.size
-        base_url = str(self.request.URL)
-        url = "%s?%s%s=%d" % (base_url, qs, self.start_variable_name, start)
         if size != self.default_size:
             # The current batch size should only be part of the URL if it's
             # different from the default batch size.
-            url = "%s&%s=%d" % (url, self.batch_variable_name, size)
-        return url
-
-    def getBatches(self):
-        batch = self.batch.firstBatch()
-        batches = [batch]
-        while 1:
-            batch = batch.nextBatch()
-            if not batch:
-                break
-            batches.append(batch)
-        return batches
+            elements.append("%s=%s" % (self.batch_variable_name, size))
+
+        if backwards:
+            elements.append("%s=backwards" % (self.direction_variable_name,))
+
+        if batch.range_memo:
+            elements.append("%s=%s" % (self.memo_variable_name, batch.range_memo))
+
+        start = batch.startNumber() - 1
+        if start:
+            elements.append("%s=%s" % (self.start_variable_name, start))
+
+        base_url = str(self.request.URL)
+        return "%s?%s" % (base_url, '&'.join(elements))
 
     def firstBatchURL(self):
         batch = self.batch.firstBatch()
@@ -220,7 +252,7 @@
         return self.generateBatchURL(batch)
 
     def prevBatchURL(self):
-        return self.generateBatchURL(self.batch.prevBatch())
+        return self.generateBatchURL(self.batch.prevBatch(), backwards=True)
 
     def nextBatchURL(self):
         return self.generateBatchURL(self.batch.nextBatch())
@@ -230,52 +262,43 @@
         if self.start == batch.start:
             # We are already on the last batch.
             batch = None
-        return self.generateBatchURL(batch)
-
-    def batchPageURLs(self):
-        batches = self.getBatches()
-        urls = []
-        size = len(batches)
-
-        nextb = self.batch.nextBatch()
-
-        # Find the current page
-        if nextb:
-            current = nextb.start/nextb.size
-        else:
-            current = size
-
-        self.current = current
-        # Find the start page to show
-        if (current - 5) > 0:
-            start = current-5
-        else:
-            start = 0
-
-        # Find the last page to show
-        if (start + 10) < size:
-            stop = start + 10
-        else:
-            stop = size
-
-        initial = start
-        while start < stop:
-            this_batch = batches[start]
-            url = self.generateBatchURL(this_batch)
-            if (start+1) == current:
-                urls.append({'['+str(start + 1)+']' : url})
-            else:
-                urls.append({start + 1 : url})
-            start += 1
-
-        if current != 1:
-            url = self.generateBatchURL(batches[0])
-            urls.insert(0, {'_first_' : url})
-        if current != size:
-            url = self.generateBatchURL(batches[size-1])
-            urls.append({'_last_':url})
-
-        return urls
+        return self.generateBatchURL(batch, backwards=True)
 
     def currentBatch(self):
         return self.batch
+
+
+class ListRangeFactory:
+    """Implements an IRangeFactory for lists (and list-like objects).
+
+    This uses the slice protocol index as its memos: 'up to and not including
+    low', 'from this point and up'.
+    """
+
+    implements(IRangeFactory)
+
+    def __init__(self, results):
+        self.results = results
+
+    def getEndpointMemos(self, batch):
+        """See `IRangeFactory`
+        
+        Most implementations will want to use batch.sliced_list to retrieve
+        database keys.
+        """
+        end_idx = batch.trueSize + batch.start
+        return (str(batch.start), str(end_idx))
+
+    def getSlice(self, endpoint_memo=None, forwards=True):
+        """See `IRangeFactory`"""
+        if endpoint_memo:
+            try:
+                offset = int(endpoint_memo)
+            except ValueError:
+                raise InvalidBatchSizeError('not an int')
+        else:
+            offset = None
+        if forwards:
+            return self.results[offset:]
+        else:
+            return list(reversed(self.results[:offset]))

=== modified file 'src/lazr/batchnavigator/interfaces.py'
--- src/lazr/batchnavigator/interfaces.py	2009-03-23 16:14:28 +0000
+++ src/lazr/batchnavigator/interfaces.py	2011-04-06 03:20:48 +0000
@@ -20,7 +20,40 @@
 
 
 class InvalidBatchSizeError(AssertionError):
-    """Received a batch parameter that exceed our configured max size."""
+    """Received a batch parameter that was invalid (e.g. exceeds our configured max size)."""
+
+
+class IRangeFactory(Interface):
+    """A helper used to construct better backend queries for batches.
+    
+    IRangeFactory instances are paired with a result object that the
+    BatchNavigator was constructed with. Generally they will be curried
+    as part of determining what backend query to run for the thing being
+    batched.
+    """
+
+    def getEndpointMemos(batch):
+        """Converts a batch to a pair of (lower, upper) endpoint memos.
+
+        :return: A tuple of bytestrings suitable for inclusion in URLs.
+        """
+
+    def getSlice(endpoint_memo='', forwards=True):
+        """Returns a slice of the results starting after endpoint_memo.
+
+        Note that endpoint_memo should be a simple string and is untrusted.
+
+        :param endpoint_memo: An endpoint memo as returned by getEndpointMemos.
+            If None or '', the edge of the results is used.
+        :param forwards: If True, slice forwards from endpoint_memo. Otherwise
+            slice backwards from endpoint_memo (e.g. ascending indices in the
+            result will indicate earlier items in the results collection).
+        :return: An object honouring the tuple protocol, just like 'results' in
+            the IBatchNavigatorFactory constructor call. If forwards was not
+            True, the order will be reversed vs the 'results' object, otherwise
+            it is identical.
+        """
+
 
 class IBatchNavigator(Interface):
     """A batch navigator for a specified set of results."""
@@ -39,22 +72,32 @@
     def nextBatchURL():
         """Return a URL to the next chunk of results."""
 
-    def batchPageURLs():
-        """Return a list of links representing URLs to pages of
-        results."""
 
 class IBatchNavigatorFactory(Interface):
     def __call__(results, request, start=0, size=None, callback=None,
-                 transient_parameters=None, force_start=False):
+                 transient_parameters=None, force_start=False,
+                 range_factory=None):
         """Constructs an `IBatchNavigator` instance.
 
         :param results: is an iterable of results.
 
-        :param request: will be inspected for a start variable; if set,
-            it indicates which point we are currently displaying at. It
-            will also be inspected for a batch variable; if set, it will
-            be used instead of the size supplied in the callsite.  Expected to
-            confirm to zope.publisher.interfaces.IRequest.
+        :param request: Expected to confirm to
+            zope.publisher.interfaces.IRequest.
+            The following variables are pulled out of the request to control
+            the batch navigator:
+              - memo: A record of the underlying storage index pointer for the
+                position of the batch.
+              - direction: Indicates whether the memo is at the start or end of
+                the batch.
+              - start: Cosmetic - used to calculate the apparent location (but
+                note that due to the concurrent nature of repeated visits to
+                batches that the true offset may differ - however the
+                collection won't skip or show items twice. For compatibility
+                with saved URLs, if memo and direction are both missing then
+                start is used to do list slicing into the collection.
+              - batch: Controls the amount of items we are showing per batch.
+                It will only appear if it's different from the default value
+                set when the batch is created.
 
         :param size: is the default batch size, to fall back to if the
             request does not specify one.  If no size can be determined
@@ -74,6 +117,10 @@
         :param force_start: if True, the given `start` argument has
             precedence over the start value in the request, if any.
 
+        :param range_factory: An IRangeFactory paired with results, or None.
+            If None, a default IRangeFactory is constructed which simply adapts
+            results.
+
         :raises InvalidBatchSizeError: if the requested batch size is higher
             than the maximum allowed.
         """

=== modified file 'src/lazr/batchnavigator/tests/__init__.py'
--- src/lazr/batchnavigator/tests/__init__.py	2009-03-23 16:14:28 +0000
+++ src/lazr/batchnavigator/tests/__init__.py	2011-04-06 03:20:48 +0000
@@ -14,3 +14,19 @@
 # You should have received a copy of the GNU Lesser General Public License
 # along with lazr.batchnavigator. If not, see <http://www.gnu.org/licenses/>.
 "The lazr.batchnavigator tests."
+
+import unittest
+
+from lazr.batchnavigator.tests import (
+    test_docs,
+    )
+
+def test_suite():
+    # Discovery would be nice, but needs python2.7 for use with subunit &
+    # testrepository.
+    result = unittest.TestSuite()
+    result.addTests(test_docs.additional_tests())
+    modules = ['batchnavigator', 'z3batching']
+    result.addTests(unittest.TestLoader().loadTestsFromNames([
+        'lazr.batchnavigator.tests.test_' + name for name in modules]))
+    return result

=== added file 'src/lazr/batchnavigator/tests/test_batchnavigator.py'
--- src/lazr/batchnavigator/tests/test_batchnavigator.py	1970-01-01 00:00:00 +0000
+++ src/lazr/batchnavigator/tests/test_batchnavigator.py	2011-04-06 03:20:48 +0000
@@ -0,0 +1,216 @@
+# Copyright 2011 Canonical Ltd.  All rights reserved.
+#
+# This file is part of lazr.batchnavigator
+#
+# lazr.batchnavigator is free software: you can redistribute it and/or modify
+# it under the terms of the GNU Lesser General Public License as published by
+# the Free Software Foundation, version 3 of the License.
+#
+# lazr.batchnavigator is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
+# License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public License
+# along with lazr.batchnavigator. If not, see <http://www.gnu.org/licenses/>.
+
+"""Unit tests for lazr.batchnavigator.BatchNavigator."""
+
+import testtools
+from testtools.matchers import Equals
+from zope.interface.verify import verifyObject
+from zope.publisher.browser import TestRequest
+
+from lazr.batchnavigator import BatchNavigator, ListRangeFactory
+from lazr.batchnavigator.interfaces import (
+    IRangeFactory,
+    InvalidBatchSizeError,
+    )
+from lazr.batchnavigator.z3batching.batch import _Batch
+from lazr.batchnavigator.tests.test_z3batching import RecordingFactory
+
+SERVER_URL = 'http://www.example.com/foo'
+
+
+def query_string(start=None, batch=None, memo=None, direction=None):
+    query_string_args = {}
+    params = locals()
+    def maybe(arg):
+        if params[arg] is not None:
+            query_string_args[arg] = params[arg]
+    maybe('batch')
+    maybe('direction')
+    maybe('start')
+    maybe('memo')
+    query_string = "&".join(["%s=%s" % item for item
+        in sorted(query_string_args.items())])
+    return query_string
+
+
+def query_url(start=None, batch=None, memo=None, direction=None):
+    return SERVER_URL + '?' + query_string(start=start, batch=batch,
+        memo=memo,direction=direction)
+
+
+def batchnav_request(start=None, batch=None, memo=None, direction=None):
+    return TestRequest(SERVER_URL=SERVER_URL,
+        method='GET', environ={'QUERY_STRING': query_string(start=start,
+        batch=batch, memo=memo,direction=direction)})
+
+
+def sample_batchnav(start=None, batch=None, memo=None, direction=None):
+    collection = range(1, 11)
+    request = batchnav_request(start=start, batch=batch, memo=memo,
+        direction=direction)
+    range_factory = RecordingFactory(collection)
+    return BatchNavigator(collection, request, range_factory=range_factory)
+
+
+class EqualsQuery(Equals):
+
+    def __init__(self, start=None, batch=None, direction=None, memo=None):
+        Equals.__init__(self, query_url(start=start, batch=batch,
+            direction=direction, memo=memo))
+
+
+class TestBatchFactory(testtools.TestCase):
+
+    def test_accepts_range_factory(self):
+        # A BatchNavigator can be instantiated with a RangeFactory.
+        results = [1, 2, 3, 4]
+        range_factory = ListRangeFactory(results)
+        request = batchnav_request()
+        batchnav = BatchNavigator(results, request, range_factory=range_factory)
+        self.assertEqual(batchnav.batch.range_factory, range_factory)
+
+    def test_without_memo_direction_gets_non_factory_batch(self):
+        # memo and direction were added after the core was developed; for
+        # compatability with bookmarks when they are missing the old behaviour
+        # is invoked even when an explicit range factory is supplied
+        batchnav = sample_batchnav(start=3, batch=3)
+        self.assertEqual(range(4,7), list(batchnav.currentBatch()))
+        self.assertEqual([], batchnav.batch.range_factory.calls)
+
+    def test_without_memo_with_backwards_direction_gets_reverse_batch(self):
+        # When direction is specified backwards without memo the batch seeks
+        # backwards rather than doing a big list protocol slice.
+        batchnav = sample_batchnav(start=3, batch=3, direction='backwards')
+        self.assertEqual(range(10,11), list(batchnav.currentBatch()))
+        self.assertEqual([('getSlice', '', False)],
+            batchnav.batch.range_factory.calls)
+
+    def test_memo_used_for_middle_batch_forwards(self):
+        # If we have a memo for a batch, it is used.
+        batchnav = sample_batchnav(start=3, batch=3, memo='3')
+        self.assertEqual(range(4,7), list(batchnav.currentBatch()))
+        self.assertEqual([('getSlice', '3', True)],
+            batchnav.batch.range_factory.calls)
+
+    def test_memo_used_for_middle_batch_backwards(self):
+        # If we have a memo for a batch, it is used.
+        batchnav = sample_batchnav(start=3, batch=3, memo='6',
+            direction='backwards')
+        self.assertEqual(range(4,7), list(batchnav.currentBatch()))
+        self.assertEqual([('getSlice', '6', False)],
+            batchnav.batch.range_factory.calls)
+
+    def test_lastBatchURL_sets_direction(self):
+        batchnav = sample_batchnav(batch=3)
+        self.assertThat(batchnav.lastBatchURL(),
+            EqualsQuery(start=9, batch=3, direction='backwards'))
+
+    def test_firstBatchURL_is_trivial(self):
+        batchnav = sample_batchnav(start=3, batch=3, memo='3')
+        self.assertThat(batchnav.firstBatchURL(), EqualsQuery(batch=3))
+
+    def test_nextBatchURL_has_memo(self):
+        batchnav = sample_batchnav(start=3, batch=3, memo='3')
+        self.assertThat(batchnav.nextBatchURL(),
+            EqualsQuery(start=6, batch=3, memo='6'))
+
+    def test_prevBatchURL_has_memo_direction(self):
+        batchnav = sample_batchnav(start=6, batch=3, memo='6')
+        self.assertThat(batchnav.prevBatchURL(),
+            EqualsQuery(start=3, batch=3, memo='6', direction='backwards'))
+
+
+class TestListRangeFactory(testtools.TestCase):
+
+    def test_valid_object(self):
+        verifyObject(IRangeFactory, ListRangeFactory([]))
+
+    def test_getEndpointMemos_empty(self):
+        batch = _Batch([], ListRangeFactory([]))
+        self.assertEqual(('0', '0'),
+            batch.range_factory.getEndpointMemos(batch))
+
+    def test_getEndpointMemos_one_item(self):
+        results = [0, 1, 2]
+        batch = _Batch(results, ListRangeFactory(results), start=1, size=1)
+        self.assertEqual(('1', '2'),
+            batch.range_factory.getEndpointMemos(batch))
+
+    def test_getEndpointMemos_two_items(self):
+        results = [0, 1, 2, 3]
+        batch = _Batch(results, ListRangeFactory(results), start=1, size=2)
+        self.assertEqual(('1', '3'),
+            batch.range_factory.getEndpointMemos(batch))
+
+    def test_getEndpointMemos_three_items(self):
+        results = [0, 1, 2, 3, 4]
+        batch = _Batch(results, ListRangeFactory(results), start=1, size=3)
+        self.assertEqual(('1', '4'),
+            batch.range_factory.getEndpointMemos(batch))
+
+    def test_getEndpointMemos_start_border(self):
+        results = [0, 1]
+        batch = _Batch(results, ListRangeFactory(results), size=1)
+        self.assertEqual(('0', '1'),
+            batch.range_factory.getEndpointMemos(batch))
+
+    def test_getEndpointMemos_end_border(self):
+        results = [0, 1]
+        batch = _Batch(results, ListRangeFactory(results), start=1, size=1)
+        self.assertEqual(('1', '2'),
+            batch.range_factory.getEndpointMemos(batch))
+
+    def test_getEndpointMemos_last_batch_end_border(self):
+        results = [0, 1, 2, 3]
+        batch = _Batch(results, ListRangeFactory(results), start=4, size=1)
+        self.assertEqual(('4', '4'),
+            batch.range_factory.getEndpointMemos(batch))
+
+    def test_getslice_bad_memo(self):
+        self.assertRaises(InvalidBatchSizeError,
+            ListRangeFactory([]).getSlice, 'foo')
+
+    def test_getslice_next_end(self):
+        # at the end, crickets...
+        results = [0, 1, 2, 3, 4, 5]
+        slice = ListRangeFactory(results).getSlice('6')
+        self.assertEqual([], slice)
+
+    def test_getslice_before_start(self):
+        # at the end, crickets...
+        results = [0, 1, 2, 3, 4, 5]
+        slice = list(ListRangeFactory(results).getSlice('0', forwards=False))
+        self.assertEqual([], slice)
+
+    def test_getslice_before_end(self):
+        results = [0, 1, 2, 3, 4, 5]
+        slice = list(ListRangeFactory(results).getSlice('6', forwards=False))
+        self.assertEqual([5, 4, 3, 2, 1, 0], slice)
+
+    def test_getslice_next(self):
+        # The slice returned starts where indicated but continues on.
+        results = [0, 1, 2, 3, 4, 5]
+        slice = ListRangeFactory(results).getSlice('3')
+        self.assertEqual([3, 4, 5], slice)
+
+    def test_getslice_before_middle(self):
+        # Going backwards does not include the anchor (because going forwards
+        # includes it)
+        results = [0, 1, 2, 3, 4, 5]
+        slice = list(ListRangeFactory(results).getSlice('3', forwards=False))
+        self.assertEqual([2, 1, 0], slice)
+

=== modified file 'src/lazr/batchnavigator/tests/test_z3batching.py'
--- src/lazr/batchnavigator/tests/test_z3batching.py	2010-08-18 11:38:56 +0000
+++ src/lazr/batchnavigator/tests/test_z3batching.py	2011-04-06 03:20:48 +0000
@@ -18,6 +18,7 @@
 
 from lazr.batchnavigator.z3batching.batch import _Batch, BATCH_SIZE
 from lazr.batchnavigator.z3batching.interfaces import IBatch
+from lazr.batchnavigator import ListRangeFactory
 
 
 class ListWithExplosiveLen(list):
@@ -49,6 +50,20 @@
             operator.getitem, ListAllergicToNegativeIndexes([1,2,3]), -1)
 
 
+class RecordingFactory(ListRangeFactory):
+    def __init__(self, results):
+        ListRangeFactory.__init__(self, results)
+        self.calls = []
+
+    def getEndpointMemos(self, batch):
+        self.calls.append('getEndpointMemos')
+        return ListRangeFactory.getEndpointMemos(self, batch)
+
+    def getSlice(self, memo, forwards):
+        self.calls.append(('getSlice', memo, forwards))
+        return ListRangeFactory.getSlice(self, memo, forwards)
+
+
 class BatchTest(unittest.TestCase):
 
     def getData(self):
@@ -56,87 +71,95 @@
                 'seven', 'eight', 'nine', 'ten']
 
     def test_Interface(self):
-        self.failUnless(IBatch.providedBy(_Batch([], 0, 0)))
+        self.failUnless(IBatch.providedBy(self.getBatch()))
+
+    def getBatch(self, start=0, size=None):
+        return _Batch(self.getData(), ListRangeFactory(self.getData()), start,
+            size)
+
+    def getRecordingBatch(self, start=0, size=None, memo=None, forwards=True):
+        range_factory = RecordingFactory(self.getData())
+        batch = _Batch(range_factory.results, range_factory, start=start,
+            size=size, range_forwards=forwards, range_memo=memo)
+        return batch
 
     def test_constructor(self):
-        _Batch(self.getData(), 9, 3)
-        # A start that's larger than the length should still construct a working
-        # (but empty) batch.
-        _Batch(self.getData(), start=99, size=3)
+        self.getBatch(9, 3)
+        # A start that's larger than the length should still construct a
+        # working (but empty) batch.
+        self.getBatch(99, 3)
         # If no size is provided a default is used.
-        _Batch(self.getData())
+        _Batch(self.getData(), ListRangeFactory(self.getData()))
 
     def test_default_batch_size(self):
         # If we don't specify a batch size, a default one is chosen for us.
-        batch = _Batch(self.getData())
+        batch = _Batch(self.getData(), ListRangeFactory(self.getData()))
         self.assertEqual(batch.size, BATCH_SIZE)
 
     def test__len__(self):
-        batch = _Batch(self.getData(), 99, 3)
-        self.assertEqual(len(batch), 0)
-
-        batch = _Batch(self.getData(), 0, 3)
+        batch = self.getBatch(0, 3)
         self.assertEqual(len(batch), 3)
 
-        batch = _Batch(self.getData(), 9, 3)
+        batch = self.getBatch(9, 3)
         self.assertEqual(len(batch), 1)
 
-        batch = _Batch(self.getData(), 99, 3)
+        batch = self.getBatch(99, 3)
         self.assertEqual(len(batch), 0)
 
         # If the entire set of contents fits into a single batch, the result
         # of len() is correct.
-        batch = _Batch(self.getData(), size=999)
+        batch = self.getBatch(size=999)
         self.assertEqual(len(batch), 10)
 
         # If the entire set of contents fits into a single batch, and we've
         # iterated over the items, the result of len() is correct.
-        batch = _Batch(self.getData(), size=999)
+        batch = self.getBatch(size=999)
         list(batch)
         self.assertEqual(len(batch), 10)
 
     def test__getitem__(self):
-        batch = _Batch(self.getData(), 0, 3)
+        batch = self.getBatch(0, 3)
         self.assertEqual(batch[0], 'one')
         self.assertEqual(batch[1], 'two')
         self.assertEqual(batch[2], 'three')
-        batch = _Batch(self.getData(), 3, 3)
+        batch = self.getBatch(3, 3)
         self.assertEqual(batch[0], 'four')
         self.assertEqual(batch[1], 'five')
         self.assertEqual(batch[2], 'six')
-        batch = _Batch(self.getData(), 9, 3)
+        batch = self.getBatch(9, 3)
         self.assertRaises(IndexError, batch.__getitem__, 3)
 
         # If the batch is "off the end" and we've materialized the underlying
         # list (by iterating over the batch) we will get an IndexError if we
         # pass in a negative item index.
-        batch = _Batch(self.getData(), 99, 3)
+        batch = self.getBatch(99, 3)
         list(iter(batch))
         self.assertRaises(IndexError, batch.__getitem__, -1)
 
     def test__iter__(self):
-        batch = _Batch(self.getData(), 0, 3)
+        batch = self.getBatch(0, 3)
         self.assertEqual(list(iter(batch)), ['one', 'two', 'three'])
-        batch = _Batch(self.getData(), 9, 3)
+        batch = self.getBatch(9, 3)
         self.assertEqual(list(iter(batch)), ['ten'])
-        batch = _Batch(self.getData(), 99, 3)
+        batch = self.getBatch(99, 3)
         self.assertEqual(list(iter(batch)), [])
 
     def test__getitem__does_not_use_negative_indices(self):
         # Some collections don't implement __len__, so slicing them doesn't
         # work, therefore we want to be sure negative slices are not passed
         # through to the underlying collection.
-        batch = _Batch(ListAllergicToNegativeIndexes(self.getData()), 99, 3)
+        data = ListAllergicToNegativeIndexes(self.getData())
+        batch = _Batch(data, ListRangeFactory(data), 99, 3)
         list(iter(batch))
         self.assertRaises(IndexError, batch.__getitem__, -1)
 
     def test__contains__(self):
-        batch = _Batch(self.getData(), 0, 3)
+        batch = self.getBatch(0, 3)
         self.assert_(batch.__contains__('one'))
         self.assert_(batch.__contains__('two'))
         self.assert_(batch.__contains__('three'))
         self.assert_(not batch.__contains__('four'))
-        batch = _Batch(self.getData(), 6, 3)
+        batch = self.getBatch(6, 3)
         self.assert_(not batch.__contains__('one'))
         self.assert_(batch.__contains__('seven'))
         self.assert_(not batch.__contains__('ten'))
@@ -145,7 +168,8 @@
         # If the current batch is known to be the last batch, then we can
         # calculate the total number of items without calling len() on the
         # underlying collection.
-        batch = _Batch(ListWithExplosiveLen(self.getData()), 0, 20)
+        data = ListWithExplosiveLen(self.getData())
+        batch = _Batch(data, ListRangeFactory(data), 0, 20)
 
         # If we get the total number of items before accessing the underlying
         # data, we'll call len() on the collection object.
@@ -165,45 +189,45 @@
         will not be None ever.
         """
         # first batch when we are at the beginning of the batch.
-        first = _Batch(self.getData(), 0, 3).firstBatch()
+        first = self.getBatch(0, 3).firstBatch()
         self.assertEqual(list(iter(first)), ['one', 'two', 'three'])
         # first batch when we are in the second set of items of the batch.
-        first = _Batch(self.getData(), 3, 3).firstBatch()
+        first = self.getBatch(3, 3).firstBatch()
         self.assertEqual(list(iter(first)), ['one', 'two', 'three'])
         # first batch when we are in the third set of items of the batch.
-        first = _Batch(self.getData(), 6, 3).firstBatch()
+        first = self.getBatch(6, 3).firstBatch()
         self.assertEqual(list(iter(first)), ['one', 'two', 'three'])
         # first batch when we are at the end of the batch.
-        first = _Batch(self.getData(), 9, 3).firstBatch()
+        first = self.getBatch(9, 3).firstBatch()
         self.assertEqual(list(iter(first)), ['one', 'two', 'three'])
         # first batch when we get a request for an out of range item.
-        first = _Batch(self.getData(), 99, 3).firstBatch()
+        first = self.getBatch(99, 3).firstBatch()
         self.assertEqual(list(iter(first)), ['one', 'two', 'three'])
 
     def test_nextBatch(self):
-        next = _Batch(self.getData(), 0, 3).nextBatch()
+        next = self.getBatch(0, 3).nextBatch()
         self.assertEqual(list(iter(next)), ['four', 'five', 'six'])
         nextnext = next.nextBatch()
         self.assertEqual(list(iter(nextnext)), ['seven', 'eight', 'nine'])
-        next = _Batch(self.getData(), 9, 3).nextBatch()
+        next = self.getBatch(9, 3).nextBatch()
         self.assertEqual(next, None)
-        next = _Batch(self.getData(), 99, 3).nextBatch()
+        next = self.getBatch(99, 3).nextBatch()
         self.assertEqual(next, None)
 
     def test_prevBatch(self):
-        prev = _Batch(self.getData(), 9, 3).prevBatch()
+        prev = self.getBatch(9, 3).prevBatch()
         self.assertEqual(list(iter(prev)), ['seven', 'eight', 'nine'])
         prevprev = prev.prevBatch()
         self.assertEqual(list(iter(prevprev)), ['four', 'five', 'six'])
-        prev = _Batch(self.getData(), 0, 3).prevBatch()
+        prev = self.getBatch(0, 3).prevBatch()
         self.assertEqual(prev, None)
-        prev = _Batch(self.getData(), 2, 3).prevBatch()
+        prev = self.getBatch(2, 3).prevBatch()
         self.assertEqual(list(iter(prev)), ['one', 'two', 'three'])
 
         # If we create a batch that's out of range, and don't get its
         # length or any of its data, its previous batch will also be
         # out of range.
-        out_of_range = _Batch(self.getData(), 99, 3)
+        out_of_range = self.getBatch(99, 3)
         out_of_range_2 = out_of_range.prevBatch()
         self.assertEqual(out_of_range_2.start, 96)
 
@@ -215,19 +239,19 @@
         will not be None ever.
         """
         # last batch when we are at the beginning of the batch.
-        last = _Batch(self.getData(), 0, 3).lastBatch()
+        last = self.getBatch(0, 3).lastBatch()
         self.assertEqual(list(iter(last)), ['ten'])
         # last batch when we are in the second set of items of the batch.
-        last = _Batch(self.getData(), 3, 3).lastBatch()
+        last = self.getBatch(3, 3).lastBatch()
         self.assertEqual(list(iter(last)), ['ten'])
         # last batch when we are in the third set of items of the batch.
-        last = _Batch(self.getData(), 6, 3).lastBatch()
+        last = self.getBatch(6, 3).lastBatch()
         self.assertEqual(list(iter(last)), ['ten'])
         # last batch when we are at the end of the batch.
-        last = _Batch(self.getData(), 9, 3).lastBatch()
+        last = self.getBatch(9, 3).lastBatch()
         self.assertEqual(list(iter(last)), ['ten'])
         # last batch when we get a request for an out of range item.
-        last = _Batch(self.getData(), 99, 3).lastBatch()
+        last = self.getBatch(99, 3).lastBatch()
         self.assertEqual(list(iter(last)), ['ten'])
 
         # We are going to test now the same, but when we get a request of 5
@@ -236,93 +260,133 @@
         # size that is multiple of the item list length.
 
         # last batch when we are at the beginning of the batch.
-        last = _Batch(self.getData(), 0, 5).lastBatch()
+        last = self.getBatch(0, 5).lastBatch()
         self.assertEqual(
             list(iter(last)), ['six', 'seven', 'eight', 'nine', 'ten'])
         # last batch when we are in the second set of items of the batch.
-        last = _Batch(self.getData(), 5, 5).lastBatch()
+        last = self.getBatch(5, 5).lastBatch()
         self.assertEqual(
             list(iter(last)), ['six', 'seven', 'eight', 'nine', 'ten'])
         # last batch when we get a request for an out of range item.
-        last = _Batch(self.getData(), 99, 5).lastBatch()
+        last = self.getBatch(99, 5).lastBatch()
         self.assertEqual(
             list(iter(last)), ['six', 'seven', 'eight', 'nine', 'ten'])
 
     def test_batchRoundTrip(self):
-        batch = _Batch(self.getData(), 0, 3).nextBatch()
+        batch = self.getBatch(0, 3).nextBatch()
         self.assertEqual(list(iter(batch.nextBatch().prevBatch())),
                          list(iter(batch)))
 
     def test_first_last(self):
-        batch = _Batch(self.getData(), 0, 3)
+        batch = self.getBatch(0, 3)
         self.assertEqual(batch.first(), 'one')
         self.assertEqual(batch.last(), 'three')
-        batch = _Batch(self.getData(), 9, 3)
+        batch = self.getBatch(9, 3)
         self.assertEqual(batch.first(), 'ten')
         self.assertEqual(batch.last(), 'ten')
-        batch = _Batch(self.getData(), 99, 3)
+        batch = self.getBatch(99, 3)
         self.assertRaises(IndexError, batch.first)
         self.assertRaises(IndexError, batch.last)
 
     def test_total(self):
-        batch = _Batch(self.getData(), 0, 3)
-        self.assertEqual(batch.total(), 10)
-        batch = _Batch(self.getData(), 6, 3)
-        self.assertEqual(batch.total(), 10)
-        batch = _Batch(self.getData(), 99, 3)
+        batch = self.getBatch(0, 3)
+        self.assertEqual(batch.total(), 10)
+        batch = self.getBatch(6, 3)
+        self.assertEqual(batch.total(), 10)
+        batch = self.getBatch(99, 3)
         self.assertEqual(batch.total(), 10)
 
     def test_trueSize_of_full_batch(self):
         # The .trueSize property reports how many items are in the batch.
-        batch = _Batch(self.getData(), 0, 3)
+        batch = self.getBatch(0, 3)
         self.assertEqual(batch.trueSize, 3)
 
     def test_trueSize_of_last_batch(self):
         # If the current batch contains fewer than a full batch, .trueSize
         # reports how many items are in the batch.
-        batch = _Batch(self.getData(), 9, 3)
+        batch = self.getBatch(9, 3)
         self.assertEqual(batch.trueSize, 1)
 
     def test_optimized_trueSize_of_full_batch(self):
         # If the unerlying items in the batch have been materialized, there is
         # a code path that avoids calling len() on the underlying collection.
-        batch = _Batch(ListWithExplosiveLen(self.getData()), 0, 3)
+        data = ListWithExplosiveLen(self.getData())
+        batch = _Batch(data, ListRangeFactory(data), 0, 3)
         next(iter(batch)) # Materialize the items.
         self.assertEqual(batch.trueSize, 3)
 
     def test_optimized_trueSize_of_last_batch(self):
         # If the current batch contains fewer than a full batch, .trueSize
         # reports how many items are in the batch.
-        batch = _Batch(ListWithExplosiveLen(self.getData()), 9, 3)
+        data = ListWithExplosiveLen(self.getData())
+        batch = _Batch(data, ListRangeFactory(data), 9, 3)
         next(iter(batch)) # Materialize the items.
         self.assertEqual(batch.trueSize, 1)
 
     def test_startNumber(self):
-        batch = _Batch(self.getData(), 0, 3)
+        batch = self.getBatch(0, 3)
         self.assertEqual(batch.startNumber(), 1)
-        batch = _Batch(self.getData(), 9, 3)
+        batch = self.getBatch(9, 3)
         self.assertEqual(batch.startNumber(), 10)
-        batch = _Batch(self.getData(), 99, 3)
+        batch = self.getBatch(99, 3)
         self.assertEqual(batch.startNumber(), 100)
 
     def test_endNumber(self):
         # If a batch of size 3 starts at index 0, the human-friendly numbering
         # of the last item should be 3.
-        batch = _Batch(self.getData(), 0, 3)
+        batch = self.getBatch(0, 3)
         self.assertEqual(batch.endNumber(), 3)
         # If a batch of size 3 starts at index 9 and has just 1 item in it
         # (because there are 10 items total), the human-friendly numbering
         # of the last item should be 10.
-        batch = _Batch(self.getData(), 9, 3)
+        batch = self.getBatch(9, 3)
         self.assertEqual(batch.endNumber(), 10)
         # If the batch start exceeds the number number of items, then the
         # endNumber will be None to indicate that it makes no sense to ask.
-        batch = _Batch(self.getData(), 99, 3)
+        batch = self.getBatch(99, 3)
         self.assertEqual(batch.endNumber(), None)
 
-
-def additional_tests():
-    return unittest.TestSuite((
-        unittest.makeSuite(BatchTest),
-        unittest.makeSuite(TestingInfrastructureTest),
-        ))
+    def test_sliced_list_uses_range_factory(self):
+        batch = self.getRecordingBatch(memo='', forwards=False)
+        list(batch)
+        self.assertEqual([('getSlice', '', False)], batch.range_factory.calls)
+
+    def test_firstBatch_generates_memo_None(self):
+        batch = self.getRecordingBatch(start=3, size=3, memo='3')
+        first = batch.firstBatch()
+        self.assertEqual('', first.range_memo)
+        self.assertEqual(True, first.range_forwards)
+        self.assertEqual(0, first.start)
+        self.assertEqual(3, first.size)
+        self.assertEqual(['one', 'two', 'three'], list(first))
+
+    def test_lastBatch_generates_memo_None_backwards(self):
+        batch = self.getRecordingBatch(start=3, size=3, memo='3')
+        last = batch.lastBatch()
+        self.assertEqual('', last.range_memo)
+        self.assertEqual(False, last.range_forwards)
+        # len() is known, and size() is known, so the last batch starts at
+        # len-size
+        self.assertEqual(9, last.start)
+        self.assertEqual(3, last.size)
+        self.assertEqual(['ten'], list(last))
+
+    def test_nextBatch_generates_upper_memo(self):
+        batch = self.getRecordingBatch(start=3, size=3, memo='3')
+        next = batch.nextBatch()
+        self.assertEqual('6', next.range_memo)
+        self.assertEqual(True, next.range_forwards)
+        self.assertEqual(6, next.start)
+        self.assertEqual(3, next.size)
+        self.assertEqual(['seven', 'eight', 'nine'], list(next))
+
+    def test_prevBatch_generates_lower_memo_backwards(self):
+        batch = self.getRecordingBatch(start=6, size=3, memo='3')
+        prev = batch.prevBatch()
+        self.assertEqual('6', prev.range_memo)
+        self.assertEqual(False, prev.range_forwards)
+        # len() is known, and size() is known, so the prev batch starts at
+        # len-size
+        self.assertEqual(3, prev.start)
+        self.assertEqual(3, prev.size)
+        self.assertEqual(['four', 'five', 'six'], list(prev))

=== modified file 'src/lazr/batchnavigator/version.txt'
--- src/lazr/batchnavigator/version.txt	2010-08-18 11:38:56 +0000
+++ src/lazr/batchnavigator/version.txt	2011-04-06 03:20:48 +0000
@@ -1,1 +1,1 @@
-1.2.2
+1.2.3

=== modified file 'src/lazr/batchnavigator/z3batching/batch.py'
--- src/lazr/batchnavigator/z3batching/batch.py	2010-08-18 18:57:39 +0000
+++ src/lazr/batchnavigator/z3batching/batch.py	2011-04-06 03:20:48 +0000
@@ -76,7 +76,23 @@
             return self.listlength - self.start
         return self.size
 
-    def __init__(self, results, start=0, size=None, _listlength=None):
+    def __init__(self, results, range_factory, start=0, size=None,
+        range_forwards=None, range_memo=None, _listlength=None):
+        """Create a _Batch.
+
+        :param start: Cosmetic indicator of the start of the batch. Has *no*
+            effect on returned data.
+        :param range_factory: A factory used to construct efficient views of
+            the results.
+        :param range_forwards: True if the range memo is at or before the start
+            of the batch.
+        :param range_memo: An endpoint memo from the range factory describing
+            how to get a slice from the factory which will have offset 0
+            contain the first element of the batch (or the list, if not
+            range_forwards). '' for the extreme edge of the range, None to
+            have the start parameter take precedence and cause actual
+            slicing of results.
+        """
         if results is None:
             results = []
         self.list = results
@@ -93,6 +109,11 @@
 
         self.start = start
         self.end = start + size
+        self.range_factory = range_factory
+        self.range_memo = range_memo
+        if range_forwards is None:
+            range_forwards = True
+        self.range_forwards = range_forwards
 
     def __len__(self):
         assert self.trueSize >= 0, ('The number of items in a batch should '
@@ -108,7 +129,12 @@
         # __len__, raise a mysterious exception directly from python.
         if self.start < 0:
             raise IndexError, 'batch is empty'
-        return self.list[self.start+key]
+        # We delegate to self.sliced_list because:
+        # - usually folk will be walking the batch and sliced_list optimises
+        #   that.
+        # - if they aren't, the overhead of duplicating one batch of results in
+        #   memory is small
+        return self.sliced_list[key]
 
     @Lazy
     def sliced_list(self):
@@ -116,12 +142,47 @@
         # time; in certain cases (such as when database access is necessary)
         # this can be expensive.
         #
-        # We get one more item than we need, so that we can detect
-        # cases where the underlying list ends on a batch boundary
-        # without having to check the total size of the list (another
-        # expensive operation).
-        sliced = list(self.list[self.start:self.end+1])
-
+        if self.range_memo is None:
+            # Legacyy mode - use the slice protocol on results.
+            sliced = list(self.list[self.start:self.end+1])
+        else:
+            # The range factory gives us a partition on results starting from
+            # the previous actual result.
+            partition = self.range_factory.getSlice(
+                self.range_memo, self.range_forwards)
+            if self.range_memo is '' and not self.range_forwards:
+                # As a special case, when getting the last batch (range_memo
+                # None, range_forwards False) we calculate the number of items
+                # we would expect from the size of the collection. This is done
+                # because that is what the older code did when range_factory
+                # was added.
+                size = self.listlength % self.size
+                if not size:
+                    size = self.size
+            else:
+                # We get one more item than we need, so that we can detect
+                # cases where the underlying list ends on a batch boundary
+                # without having to check the total size of the list (an
+                # expensive operation).
+                size = self.size + 1
+            sliced = list(partition[:size])
+            if not self.range_forwards:
+                sliced.reverse()
+                if self.range_memo is not '' and len(sliced) <= size:
+                    if len(sliced) == size:
+                        # sliced is meant to have an extra element *after* the
+                        # content for end-of-collection-detection, but the
+                        # partitioner has just walked backwards, so shuffle things
+                        # around to suit. If we didn't get as much data as we asked
+                        # for we are at the beginning of the collection and all
+                        # elements are needed.
+                        sliced = sliced[1:] + sliced[:1]
+                    else:
+                        # If we got fewer than expected walking backwards, the
+                        # range memo may have constrained us. So we need to get
+                        # some more results:
+                        partition = self.range_factory.getSlice(self.range_memo)
+                        sliced = sliced + partition[:size - len(sliced)]
         # This is the first time we get an inkling of (approximately)
         # how many items are in the list. This is the appropriate time
         # to handle edge cases.
@@ -175,8 +236,10 @@
         if len(self.sliced_list) <= self.size:
             return None
 
-        return _Batch(
-            self.list, start, self.size, _listlength=self._listlength)
+        memos = self.range_factory.getEndpointMemos(self)
+        return _Batch(self.list, self.range_factory, start, self.size,
+            range_memo=memos[1], range_forwards=True,
+            _listlength=self._listlength)
 
     def prevBatch(self):
         # The only case in which we should /not/ offer a previous batch
@@ -191,12 +254,14 @@
             # in this case, hopping back one batch would be starting at
             # -5, which doesn't really make sense.
             start = 0
-        return _Batch(self.list, start, self.size,
-                      _listlength=self._listlength)
+        memos = self.range_factory.getEndpointMemos(self)
+        return _Batch(self.list, self.range_factory, start, self.size,
+            range_memo=memos[0], range_forwards=False,
+            _listlength=self._listlength)
 
     def firstBatch(self):
-        return _Batch(self.list, 0, size=self.size,
-                      _listlength=self._listlength)
+        return _Batch(self.list, self.range_factory, 0, size=self.size,
+            range_memo='', range_forwards=True, _listlength=self._listlength)
 
     def lastBatch(self):
         # Return the last possible batch for this dataset, at the
@@ -205,8 +270,9 @@
         last_batch_start = last_index - (last_index % self.size)
         if last_batch_start < 0:
             last_batch_start = 0
-        return _Batch(self.list, last_batch_start, size=self.size,
-                      _listlength=self.listlength)
+        return _Batch(self.list, self.range_factory, last_batch_start,
+            size=self.size, range_memo='', range_forwards=False,
+            _listlength=self._listlength)
 
     def total(self):
         return self.listlength