Rev 2250: Don't move the prev_range_id if we are completely removing the current node. in http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch
John Arbash Meinel
john at arbash-meinel.com
Tue Jan 30 03:50:45 GMT 2007
At http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch
------------------------------------------------------------
revno: 2250
revision-id: john at arbash-meinel.com-20070130035040-sd7e63bpxs1xw4n6
parent: john at arbash-meinel.com-20070130030128-fh616n0n3kmerab2
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: list_patch
timestamp: Mon 2007-01-29 21:50:40 -0600
message:
Don't move the prev_range_id if we are completely removing the current node.
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 03:01:28 +0000
+++ b/bzrlib/hybrid_linked_list.py 2007-01-30 03:50:40 +0000
@@ -28,14 +28,17 @@
node stores a pointer to the other nodes. However, this is inefficient at
random access, because you have to iterate over all of the nodes.
- This class attempts to create a hybrid between them. Which creates nodes
- during insert, update, delete, but generally stores things as arrays.
-
- The current structure is optimized for being able to modify small sections
- at a time. But not really move hunks around. (so you can remove a few
- lines, and add a few lines, but not really move lines around).
+ This class creates an linked-list of ranges into a set of content maps. As
+ entries are inserted or removed, the range list is updated, but the content
+ nodes themselves are never modified.
"""
+ # TODO: jam 20060129 Right now this class holds onto all content, even
+ # after it is no longer being referenced. This is mostly because of
+ # the internal content_id => content mapping.
+ # It should actually be possible to use a reference to the content
+ # directly, though it makes testing a little bit clumsier.
+
def __init__(self, starting=[]):
"""Create a new HybridLinkedList.
@@ -45,21 +48,24 @@
def _reset(self, starting):
"""Reset the internal structures to hold a single list."""
- self._data_counter = 0
- self._ranges_counter = 0
+ self._data_counter = -1
+ self._ranges_counter = -1
# This uses 3 maps.
# one map is just from simple id => content
- self._content_map = {0:starting}
+ self._content_map = {}
# This is a map from range_id => (content_node_id, start, end)
# This allows us to avoid doing any work on the supplied content.
# Instead, we just keep updating the information about what content
# should be extracted at the right time
- self._head = 0
- self._range_map = {self._head:(0, 0, len(starting))}
+ self._head = None
+ self._range_map = {}
# This is a singly linked list map for range to next range
- self._links = {0:None}
+ self._links = {}
+
+ if starting:
+ self.insert(0, starting)
def __iter__(self):
"""Iterate over the final content."""
@@ -231,12 +237,12 @@
# This only requires a node entry update
self._range_map[cur_range_id] = (content_id, cur_start,
cur_start + offset)
+ prev_range_id = cur_range_id
remove_length -= possible_remove_length
if remove_length == 0:
break
# step to next
offset = 0
- prev_range_id = cur_range_id
cur_range_id = next_range_id
content_id, cur_start, cur_end = self._range_map[next_range_id]
else:
=== modified file 'bzrlib/tests/test_hybrid_linked_list.py'
--- a/bzrlib/tests/test_hybrid_linked_list.py 2007-01-30 03:01:28 +0000
+++ b/bzrlib/tests/test_hybrid_linked_list.py 2007-01-30 03:50:40 +0000
@@ -35,35 +35,27 @@
self.assertEqual([], list(hll))
def test__find_nodes_for_pos(self):
- hll = hybrid_linked_list.HybridLinkedList([])
- hll._range_map = {0:(0, 0, 2),
- 1:(0, 3, 6),
- 2:(0, 6, 7),
- }
- hll._links = {0:1, 1:2, 2:None}
- hll._content_map = {0:[0, 1, 2, 3, 4, 5, 6, 7, 8]}
- self.assertEqual([0, 1, 3, 4, 5, 6], list(hll))
+ hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4, 5, 6, 7, 8])
+ hll.delete(2, 3)
+ hll.delete(5, 7)
+ self.assertEqual([0, 1, 3, 4, 5, 8], list(hll))
self.assertEqual((None, 0, 0, 0, 0, 2), hll._find_nodes_for_pos(0))
self.assertEqual((None, 0, 1, 0, 0, 2), hll._find_nodes_for_pos(1))
self.assertEqual((0, 1, 0, 0, 3, 6), hll._find_nodes_for_pos(2))
self.assertEqual((0, 1, 1, 0, 3, 6), hll._find_nodes_for_pos(3))
self.assertEqual((0, 1, 2, 0, 3, 6), hll._find_nodes_for_pos(4))
- self.assertEqual((1, 2, 0, 0, 6, 7), hll._find_nodes_for_pos(5))
+ self.assertEqual((1, 2, 0, 0, 8, 9), hll._find_nodes_for_pos(5))
self.assertEqual((2, None, 0, None, None, None),
hll._find_nodes_for_pos(6))
self.assertEqual((2, None, 1, None, None, None),
hll._find_nodes_for_pos(7))
def test__getitem__(self):
- hll = hybrid_linked_list.HybridLinkedList([])
- hll._range_map = {0:(0, 0, 2),
- 1:(0, 3, 6),
- 2:(0, 6, 7),
- }
- hll._links = {0:1, 1:2, 2:None}
- hll._content_map = {0:[0, 1, 2, 3, 4, 5, 6, 7, 8]}
- self.assertEqual([0, 1, 3, 4, 5, 6], list(hll))
- for expected, pos in zip([0, 1, 3, 4, 5, 6], xrange(0,5)):
+ hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4, 5, 6, 7, 8])
+ hll.delete(2, 3)
+ hll.delete(5, 7)
+ self.assertEqual([0, 1, 3, 4, 5, 8], list(hll))
+ for expected, pos in zip([0, 1, 3, 4, 5, 8], xrange(0,5)):
self.assertEqual(expected, hll[pos])
def test_insert(self):
@@ -197,6 +189,27 @@
self.assertEqual({0:(0, 0, 1), 2:(2, 2, 3), 3:(3, 0, 1)},
hll._range_map)
+ def test_delete_off_end(self):
+ hll = self.get_sectioned_hll()
+ hll.delete(1, 9)
+ self.assertEqual([0], list(hll))
+ self.assertEqual(3, hll._ranges_counter)
+ self.assertEqual(0, hll._head)
+ self.assertEqual({0:None}, hll._links)
+ self.assertEqual({0:(0, 0, 1)}, hll._range_map)
+
+ def test_delete_all(self):
+ hll = self.get_sectioned_hll()
+ hll.delete(0, 9)
+ self.assertEqual([], list(hll))
+ self.assertEqual(3, hll._ranges_counter)
+ self.assertEqual(None, hll._head)
+ self.assertEqual({}, hll._links)
+ self.assertEqual({}, hll._range_map)
+
+ hll.insert(0, [1])
+ self.assertEqual([1], list(hll))
+
def test_replace_insert_beginning(self):
"""Test replacing when we are purely inserting."""
hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
More information about the bazaar-commits
mailing list