Rev 2249: Implement delete() and replace() 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:01:36 GMT 2007
At http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch
------------------------------------------------------------
revno: 2249
revision-id: john at arbash-meinel.com-20070130030128-fh616n0n3kmerab2
parent: john at arbash-meinel.com-20070130013333-kav0btyhjumdj0z1
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: list_patch
timestamp: Mon 2007-01-29 21:01:28 -0600
message:
Implement delete() and replace()
delete is tricky to get all the cases right, but replace can be
defined in terms of a delete + insert.
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 01:33:33 +0000
+++ b/bzrlib/hybrid_linked_list.py 2007-01-30 03:01:28 +0000
@@ -174,3 +174,114 @@
# entry in the map
self._range_map[cur_range_id] = (content_id, start, break_point)
self._links[cur_range_id] = new_range_id
+
+ def delete(self, start, end):
+ """Remove a section from the content.
+
+ This just removes all of the text from [start,end)
+ It is equivalent to "del list[start,end]"
+
+ :param start: The first offset to remove.
+ :param end: The last offset to remove (non-inclusive)
+ """
+ remove_length = end - start
+ if remove_length <= 0:
+ # Nothing to do
+ return
+
+ (prev_range_id, cur_range_id, offset,
+ content_id, cur_start, cur_end) = self._find_nodes_for_pos(start)
+
+ if cur_range_id is None:
+ # We fell off the end, nothing to do
+ # In python "del list[BIGNUM:BIGNUM]" does nothing
+ return
+
+ while cur_range_id is not None:
+ # There are 4 possible cases
+ # 1) We remove this node entirely
+ # when offset == 0 and remove_length >= node_length
+ # If remove_length == node_length we are done.
+ # 2) We save the beginning of this node
+ # when offset > 0 and remove_length >= (node_length - offset)
+ # we may need to keep going if there is any remove_length left
+ # 3) We save the end of this node
+ # when offset == 0 and remove_length < node_length
+ # we are done after this.
+ # 4) We save both the beginning and tail of this node
+ # when offset > 0 and remove_length < (node_length - offset)
+ # This requires creating a new node for one half of this split.
+
+ entry_length = cur_end - cur_start
+ possible_remove_length = entry_length - offset
+
+ if remove_length >= possible_remove_length:
+ next_range_id = self._links[cur_range_id]
+ if offset == 0:
+ # CASE 1: this node will be fully removed
+ if prev_range_id is None:
+ # Update _head
+ self._head = next_range_id
+ else:
+ self._links[prev_range_id] = next_range_id
+ del self._links[cur_range_id]
+ del self._range_map[cur_range_id]
+ else:
+ # CASE 2: we save the beginning, but remove the tail
+ # This only requires a node entry update
+ self._range_map[cur_range_id] = (content_id, cur_start,
+ cur_start + offset)
+ 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:
+ if offset == 0:
+ # CASE 3: We remove only the beginning of this node
+ # Only requires a node entry update
+ self._range_map[cur_range_id] = (content_id,
+ cur_start + remove_length, cur_end)
+ else:
+ # We have a beginning and a tail, we need to create a new
+ # record, and update the current one
+
+ # This will take [cur_start, cur_end) and break it up into
+ # [cur_start, new_end), [new_start, cur_end)
+ new_end = cur_start + offset
+ new_start = new_end + remove_length
+
+ new_tail_range_id = self._new_range_id(content_id,
+ new_start, cur_end)
+ next_range_id = self._links[cur_range_id]
+ self._links[new_tail_range_id] = next_range_id
+
+ self._links[cur_range_id] = new_tail_range_id
+ self._range_map[cur_range_id] = (content_id, cur_start,
+ new_end)
+ # We officially removed enough, so we are done
+ break
+ # we are not removing the start of this node
+ prev_range_id = cur_range_id
+
+ def replace(self, start, end, entries):
+ """Replace a section of existing content, with new content.
+
+ This is equivalent to: list[start, end] = entries
+
+ if start == end then content will just be inserted at start. If
+ entries is empty, then the range [start,end) will just be removed.
+
+ :param start: The starting location to be replaced
+ :param end: The last position to be removed (non_inclusive)
+ :param entries: An array of new content to use. This will not be
+ modified, so it is safe to pass a list or a tuple.
+ :return: None
+ """
+ if start != end:
+ self.delete(start, end)
+ if entries:
+ self.insert(start, entries)
=== modified file 'bzrlib/tests/test_hybrid_linked_list.py'
--- a/bzrlib/tests/test_hybrid_linked_list.py 2007-01-30 01:33:33 +0000
+++ b/bzrlib/tests/test_hybrid_linked_list.py 2007-01-30 03:01:28 +0000
@@ -85,36 +85,137 @@
hll.insert(5, [5])
self.assertEqual([0, 1, 2, 3, 4, 5], list(hll))
-# def test_delete(self):
-# hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
-# hll.delete(2, 3) # del list[2:3]
-# self.assertEqual([0, 1, 3, 4], list(hll))
-#
-# def test_delete_multi(self):
-# hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
-# hll.delete(1, 3) # del list[2:3]
-# self.assertEqual([0, 3, 4], 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])
-# hll.replace(0, 0, [5, 6, 7]) # list[0:0] = [5, 6, 7]
-# self.assertEqual([5, 6, 7, 0, 1, 2, 3, 4], list(hll))
-#
-# def test_replace_insert_middle(self):
-# """Test replacing when we are purely inserting."""
-# hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
-# hll.replace(3, 3, [5, 6, 7]) # list[3:3] = [5, 6, 7]
-# self.assertEqual([0, 1, 2, 5, 6, 7, 3, 4], list(hll))
-#
-# def test_replace_insert_end(self):
-# """Test replacing when we are purely inserting."""
-# hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
-# hll.replace(5, 5, [5, 6, 7]) # list[5:5] = [5, 6, 7]
-# self.assertEqual([0, 1, 2, 3, 4, 5, 6, 7], list(hll))
-#
-# def test_replace_beginning(self):
-# hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
-# hll.replace(0, 1, [5])
-# self.assertEqual([[5], [1, 2, 3, 4]], hll._nodes)
-# self.assertEqual([5, 1, 2, 3, 4], list(hll))
+ def get_sectioned_hll(self):
+ """Get a HybridLinkedList that is already broken into sections."""
+ hll = hybrid_linked_list.HybridLinkedList([0, 1, 2])
+ hll.insert(3, [3, 4])
+ hll.insert(5, [5, 6, 7])
+ hll.insert(8, [8])
+ return hll
+
+ def test_sectioned_hll(self):
+ hll = self.get_sectioned_hll()
+ self.assertEqual(9, len(hll))
+ self.assertEqual([0, 1, 2, 3, 4, 5, 6, 7, 8], list(hll))
+ self.assertEqual(3, hll._data_counter)
+ self.assertEqual({0:[0, 1, 2], 1:[3, 4], 2:[5, 6, 7], 3:[8]},
+ hll._content_map)
+ self.assertEqual(3, hll._ranges_counter)
+ self.assertEqual(0, hll._head)
+ self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
+ self.assertEqual({0:(0, 0, 3), 1:(1, 0, 2), 2:(2, 0, 3), 3:(3, 0, 1)},
+ hll._range_map)
+
+ def test_delete(self):
+ hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
+ hll.delete(2, 3) # del list[2:3]
+ self.assertEqual([0, 1, 3, 4], list(hll))
+
+ def test_delete_multi(self):
+ hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
+ hll.delete(1, 3) # del list[1:3]
+ self.assertEqual([0, 3, 4], list(hll))
+
+ def test_delete_first_range(self):
+ hll = self.get_sectioned_hll()
+ hll.delete(0, 3)
+ self.assertEqual([3, 4, 5, 6, 7, 8], list(hll))
+ self.assertEqual(3, hll._ranges_counter)
+ self.assertEqual(1, hll._head)
+ self.assertEqual({1:2, 2:3, 3:None}, hll._links)
+ self.assertEqual({1:(1, 0, 2), 2:(2, 0, 3), 3:(3, 0, 1)},
+ hll._range_map)
+
+ def test_delete_middle_range(self):
+ hll = self.get_sectioned_hll()
+ hll.delete(3, 5)
+ self.assertEqual([0, 1, 2, 5, 6, 7, 8], list(hll))
+ self.assertEqual(3, hll._ranges_counter)
+ self.assertEqual(0, hll._head)
+ self.assertEqual({0:2, 2:3, 3:None}, hll._links)
+ self.assertEqual({0:(0, 0, 3), 2:(2, 0, 3), 3:(3, 0, 1)},
+ hll._range_map)
+
+ def test_delete_last_range(self):
+ hll = self.get_sectioned_hll()
+ hll.delete(8, 9)
+ self.assertEqual([0, 1, 2, 3, 4, 5, 6, 7], list(hll))
+ self.assertEqual(3, hll._ranges_counter)
+ self.assertEqual(0, hll._head)
+ self.assertEqual({0:1, 1:2, 2:None}, hll._links)
+ self.assertEqual({0:(0, 0, 3), 1:(1, 0, 2), 2:(2, 0, 3)},
+ hll._range_map)
+
+ def test_delete_partial_beginning(self):
+ hll = self.get_sectioned_hll()
+ hll.delete(0, 2)
+ self.assertEqual([2, 3, 4, 5, 6, 7, 8], list(hll))
+ self.assertEqual(3, hll._ranges_counter)
+ self.assertEqual(0, hll._head)
+ self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
+ self.assertEqual({0:(0, 2, 3), 1:(1, 0, 2), 2:(2, 0, 3), 3:(3, 0, 1)},
+ hll._range_map)
+
+ def test_delete_partial_ending(self):
+ hll = self.get_sectioned_hll()
+ hll.delete(1, 3)
+ self.assertEqual([0, 3, 4, 5, 6, 7, 8], list(hll))
+ self.assertEqual(3, hll._ranges_counter)
+ self.assertEqual(0, hll._head)
+ self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
+ self.assertEqual({0:(0, 0, 1), 1:(1, 0, 2), 2:(2, 0, 3), 3:(3, 0, 1)},
+ hll._range_map)
+
+ def test_delete_middle_section(self):
+ hll = self.get_sectioned_hll()
+ hll.delete(1, 2)
+ self.assertEqual([0, 2, 3, 4, 5, 6, 7, 8], list(hll))
+ self.assertEqual(4, hll._ranges_counter)
+ self.assertEqual(0, hll._head)
+ self.assertEqual({0:4, 1:2, 2:3, 3:None, 4:1}, hll._links)
+ self.assertEqual({0:(0, 0, 1), 1:(1, 0, 2), 2:(2, 0, 3), 3:(3, 0, 1),
+ 4:(0, 2, 3)
+ }, hll._range_map)
+
+ def test_delete_middle(self):
+ hll = self.get_sectioned_hll()
+ hll.delete(3, 4)
+ self.assertEqual([0, 1, 2, 4, 5, 6, 7, 8], list(hll))
+ self.assertEqual(3, hll._ranges_counter)
+ self.assertEqual(0, hll._head)
+ self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
+ self.assertEqual({0:(0, 0, 3), 1:(1, 1, 2), 2:(2, 0, 3), 3:(3, 0, 1)},
+ hll._range_map)
+
+ def test_delete_across_sections(self):
+ hll = self.get_sectioned_hll()
+ hll.delete(1, 7)
+ self.assertEqual([0, 7, 8], list(hll))
+ self.assertEqual(3, hll._ranges_counter)
+ self.assertEqual(0, hll._head)
+ self.assertEqual({0:2, 2:3, 3:None}, hll._links)
+ self.assertEqual({0:(0, 0, 1), 2:(2, 2, 3), 3:(3, 0, 1)},
+ hll._range_map)
+
+ def test_replace_insert_beginning(self):
+ """Test replacing when we are purely inserting."""
+ hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
+ hll.replace(0, 0, [5, 6, 7]) # list[0:0] = [5, 6, 7]
+ self.assertEqual([5, 6, 7, 0, 1, 2, 3, 4], list(hll))
+
+ def test_replace_insert_middle(self):
+ """Test replacing when we are purely inserting."""
+ hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
+ hll.replace(3, 3, [5, 6, 7]) # list[3:3] = [5, 6, 7]
+ self.assertEqual([0, 1, 2, 5, 6, 7, 3, 4], list(hll))
+
+ def test_replace_insert_end(self):
+ """Test replacing when we are purely inserting."""
+ hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
+ hll.replace(5, 5, [5, 6, 7]) # list[5:5] = [5, 6, 7]
+ self.assertEqual([0, 1, 2, 3, 4, 5, 6, 7], list(hll))
+
+ def test_replace_beginning(self):
+ hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
+ hll.replace(0, 1, [5])
+ self.assertEqual([5, 1, 2, 3, 4], list(hll))
More information about the bazaar-commits
mailing list