Rev 2254: Implement support for slicing ranges in http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch

------------------------------------------------------------
revno: 2254
revision-id: john at arbash-meinel.com-20070130175551-v30z9f40xpvx2m4v
parent: john at arbash-meinel.com-20070130170743-8d4lsxgevxk4dspc
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: list_patch
timestamp: Tue 2007-01-30 11:55:51 -0600
message:
  Implement support for slicing ranges
modified:
  bzrlib/hybrid_linked_list.py   hybrid_linked_list.p-20070130001028-zlexwz74tzo56o2t-1
  bzrlib/tests/test_hybrid_linked_list.py test_hybrid_linked_l-20070130001028-zlexwz74tzo56o2t-2
-------------- next part --------------
=== modified file 'bzrlib/hybrid_linked_list.py'
--- a/bzrlib/hybrid_linked_list.py	2007-01-30 17:07:43 +0000
+++ b/bzrlib/hybrid_linked_list.py	2007-01-30 17:55:51 +0000
@@ -68,6 +68,9 @@
             cur_range_id = self._links[cur_range_id]
 
     def __len__(self):
+        # TODO: jam 20070130 Should we fast path __len__? We could always just
+        #       keep a reference of the current length, and updated it when we
+        #       add or delete entries. list() uses it, as does __getitem__
         cur_range_id = self._head
         length = 0
         while cur_range_id is not None:
@@ -77,9 +80,40 @@
         return length
 
     def __getitem__(self, pos):
-        (prev_range_id, cur_range_id, offset,
-         start, end, content) = self._find_nodes_for_pos(pos)
-        return content[start+offset]
+        if isinstance(pos, slice):
+            # cur, stop, stride are in terms of location in the output list.
+            cur, stop, stride = pos.indices(len(self))
+            result = []
+
+            # offset, start, end are in terms of the current content
+            (prev_range_id, cur_range_id, offset,
+             start, end, content) = self._find_nodes_for_pos(cur)
+
+            # They requested something out of range
+            if content is None:
+                return result
+
+            offset += start
+            while cur < stop:
+                while offset >= end:
+                    # Keep skipping until we find next
+                    offset -= end
+                    cur_range_id = self._links[cur_range_id]
+                    if cur_range_id is None:
+                        content = None
+                        break
+                    start, end, content = self._range_map[cur_range_id]
+                    offset += start
+                if content is None:
+                    break
+                result.append(content[offset])
+                offset += stride
+                cur += stride
+            return result
+        else:
+            (prev_range_id, cur_range_id, offset,
+             start, end, content) = self._find_nodes_for_pos(pos)
+            return content[start+offset]
 
     def flatten(self):
         """Flatten the linked structure into a single list."""

=== modified file 'bzrlib/tests/test_hybrid_linked_list.py'
--- a/bzrlib/tests/test_hybrid_linked_list.py	2007-01-30 17:07:43 +0000
+++ b/bzrlib/tests/test_hybrid_linked_list.py	2007-01-30 17:55:51 +0000
@@ -59,6 +59,17 @@
         for expected, pos in zip([0, 1, 3, 4, 5, 8], xrange(0,5)):
             self.assertEqual(expected, hll[pos])
 
+        # Test that we support extracting ranges
+        self.assertEqual([0, 1, 3], hll[0:3])
+        self.assertEqual([0, 3], hll[0:3:2])
+        self.assertEqual([0, 1, 3, 4, 5, 8], hll[:])
+        self.assertEqual([0, 1, 3, 4, 5, 8], hll[0:20])
+        self.assertEqual([4, 5], hll[-3:-1])
+
+        # Slicing off the end returns an empty list
+        self.assertEqual([], hll[20:])
+        self.assertEqual([], hll[20:21])
+
     def test_insert(self):
         hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
         hll.insert(3, [5, 6, 7])