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