Rev 2257: Some cleanup, and switch to using slots and better variable names. in http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch

John Arbash Meinel john at arbash-meinel.com
Tue Jan 30 18:55:22 GMT 2007


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

------------------------------------------------------------
revno: 2257
revision-id: john at arbash-meinel.com-20070130185517-0ky3r2iqnyytftak
parent: john at arbash-meinel.com-20070130184657-vq3ftadvoywwmkjr
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: list_patch
timestamp: Tue 2007-01-30 12:55:17 -0600
message:
  Some cleanup, and switch to using slots and better variable names.
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 18:46:57 +0000
+++ b/bzrlib/hybrid_linked_list.py	2007-01-30 18:55:17 +0000
@@ -33,8 +33,17 @@
     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.
+
+    :ivar _counter: A counter so that all new ranges get their own handle.
+    :ivar _head: Pointer to the first range, may be None
+    :ivar _ranges: The map of ranges. This maps handle => (start, end, content)
+    :ivar _links: This maps each range to the next range. It could technically
+        be stored with _ranges, but it makes it easier to update links if they
+        are in a separate dict. (less tuple churn)
     """
 
+    __slots__ = ['_counter', '_head', '_ranges', '_links']
+
     def __init__(self, starting=[]):
         """Create a new HybridLinkedList.
 
@@ -44,7 +53,7 @@
 
     def _reset(self, starting):
         """Reset the internal structures to hold a single list."""
-        self._ranges_counter = -1
+        self._counter = -1
 
         # This uses 2 maps.
         # This is a map from range_id => (content_node_id, start, end)
@@ -52,7 +61,7 @@
         # Instead, we just keep updating the information about what content
         # should be extracted at the right time
         self._head = None
-        self._range_map = {}
+        self._ranges = {}
         # This is a singly linked list map for range to next range
         self._links = {}
 
@@ -64,7 +73,7 @@
         cur_range_id = self._head
 
         while cur_range_id is not None:
-            start, end, content = self._range_map[cur_range_id]
+            start, end, content = self._ranges[cur_range_id]
             for pos in xrange(start, end):
                 yield content[pos]
             cur_range_id = self._links[cur_range_id]
@@ -76,7 +85,7 @@
         cur_range_id = self._head
         length = 0
         while cur_range_id is not None:
-            start, end, content = self._range_map[cur_range_id]
+            start, end, content = self._ranges[cur_range_id]
             length += (end - start)
             cur_range_id = self._links[cur_range_id]
         return length
@@ -118,7 +127,7 @@
                     if cur_range_id is None:
                         content = None
                         break
-                    start, end, content = self._range_map[cur_range_id]
+                    start, end, content = self._ranges[cur_range_id]
                     offset += start
                 if content is None:
                     break
@@ -172,7 +181,7 @@
         content = start = end = None
 
         while cur_range_id is not None:
-            start, end, content = self._range_map[cur_range_id]
+            start, end, content = self._ranges[cur_range_id]
             next_pos = cur_pos + (end - start)
             if pos < next_pos:
                 break
@@ -185,9 +194,9 @@
 
     def _new_range_id(self, start, end, content):
         """Get a new range id."""
-        self._ranges_counter += 1
-        self._range_map[self._ranges_counter] = (start, end, content)
-        return self._ranges_counter
+        self._counter += 1
+        self._ranges[self._counter] = (start, end, content)
+        return self._counter
 
     def insert(self, start, content):
         """Insert a set of entries starting at the first position."""
@@ -206,33 +215,32 @@
             else:
                 self._links[new_range_id] = cur_range_id
                 self._links[prev_range_id] = new_range_id
+        # We are inserting inside an existing node
+        elif cur_range_id is not None:
+            # We need to break up the current node, and insert the
+            # requested one
+            break_point = start + offset
+            split_range_id = self._new_range_id(break_point, end, content)
+            next_range_id = self._links[cur_range_id]
+            self._links[split_range_id] = next_range_id
+            self._links[new_range_id] = split_range_id
+
+            # We could make this atomic by creating a new id for the
+            # initial range, and then the atomic step is
+            # self._links[prev_range_id] = new_head_range
+            # And then afterwards we would want to delete the cur_range_id
+            # entry in the map
+            self._ranges[cur_range_id] = (start, break_point, content)
+            self._links[cur_range_id] = new_range_id
         else:
-            # We are inserting inside an existing node
-            if cur_range_id is None:
-                # We are appending a node
-                # python lists have the property that x[BIG_NUM:BIGNUM] = [10]
-                # will always append 10 to the list, even though it is out of
-                # range
-                # TODO: For now, I'm duplicating that, but it seems to make
-                #   more sense to raise IndexError or something
-                self._links[new_range_id] = None
-                self._links[prev_range_id] = new_range_id
-            else:
-                # We need to break up the current node, and insert the
-                # requested one
-                break_point = start + offset
-                split_range_id = self._new_range_id(break_point, end, content)
-                next_range_id = self._links[cur_range_id]
-                self._links[split_range_id] = next_range_id
-                self._links[new_range_id] = split_range_id
-
-                # We could make this atomic by creating a new id for the
-                # initial range, and then the atomic step is
-                # self._links[prev_range_id] = new_head_range
-                # And then afterwards we would want to delete the cur_range_id
-                # entry in the map
-                self._range_map[cur_range_id] = (start, break_point, content)
-                self._links[cur_range_id] = new_range_id
+            # We are appending a node
+            # python lists have the property that x[BIG_NUM:BIGNUM] = [10]
+            # will always append 10 to the list, even though it is out of
+            # range
+            # TODO: For now, I'm duplicating that, but it seems to make
+            #   more sense to raise IndexError or something
+            self._links[new_range_id] = None
+            self._links[prev_range_id] = new_range_id
 
     def delete(self, start, end):
         """Remove a section from the content.
@@ -284,11 +292,11 @@
                     else:
                         self._links[prev_range_id] = next_range_id
                     del self._links[cur_range_id]
-                    del self._range_map[cur_range_id]
+                    del self._ranges[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] = (cur_start,
+                    self._ranges[cur_range_id] = (cur_start,
                                                      cur_start + offset,
                                                      content)
                     prev_range_id = cur_range_id
@@ -298,12 +306,12 @@
                 # step to next
                 offset = 0
                 cur_range_id = next_range_id
-                cur_start, cur_end, content = self._range_map[next_range_id]
+                cur_start, cur_end, content = self._ranges[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] = (cur_start + remove_length,
+                    self._ranges[cur_range_id] = (cur_start + remove_length,
                                                      cur_end, content)
                 else:
                     # We have a beginning and a tail, we need to create a new
@@ -320,7 +328,7 @@
                     self._links[new_tail_range_id] = next_range_id
 
                     self._links[cur_range_id] = new_tail_range_id
-                    self._range_map[cur_range_id] = (cur_start, new_end,
+                    self._ranges[cur_range_id] = (cur_start, new_end,
                                                      content)
                 # We officially removed enough, so we are done
                 break
@@ -354,8 +362,8 @@
         that should be fine.
         """
         new_hll = HybridLinkedList()
-        new_hll._ranges_counter = self._ranges_counter
+        new_hll._counter = self._counter
         new_hll._head = self._head
-        new_hll._range_map = self._range_map.copy()
+        new_hll._ranges = self._ranges.copy()
         new_hll._links = self._links.copy()
         return new_hll

=== modified file 'bzrlib/tests/test_hybrid_linked_list.py'
--- a/bzrlib/tests/test_hybrid_linked_list.py	2007-01-30 18:46:57 +0000
+++ b/bzrlib/tests/test_hybrid_linked_list.py	2007-01-30 18:55:17 +0000
@@ -157,14 +157,14 @@
         hll = self.get_sectioned_hll()
         self.assertEqual(9, len(hll))
         self.assertEqual([0, 1, 2, 3, 4, 5, 6, 7, 8], hll)
-        self.assertEqual(3, hll._ranges_counter)
+        self.assertEqual(3, hll._counter)
         self.assertEqual(0, hll._head)
         self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
         self.assertEqual({0:(0, 3, [0, 1, 2]),
                           1:(0, 2, [3, 4]),
                           2:(0, 3, [5, 6, 7]),
                           3:(0, 1, [8]),
-                         }, hll._range_map)
+                         }, hll._ranges)
 
     def test_copy(self):
         hll = hybrid_linked_list.HybridLinkedList([0, 1, 2])
@@ -176,14 +176,14 @@
         self.assertEqual([0, 1, 2, 3, 4, 5], hll2)
 
         # After copying, the contents should be identical
-        self.assertEqual(hll._ranges_counter, hll2._ranges_counter)
+        self.assertEqual(hll._counter, hll2._counter)
         self.assertEqual(hll._head, hll2._head)
-        self.assertEqual(hll._range_map, hll2._range_map)
+        self.assertEqual(hll._ranges, hll2._ranges)
         self.assertEqual(hll._links, hll2._links)
 
         # The content entries should be identical items, but the rest are not
-        for range_id, (start, end, content) in hll._range_map.iteritems():
-            start2, end2, content2 = hll2._range_map[range_id]
+        for range_id, (start, end, content) in hll._ranges.iteritems():
+            start2, end2, content2 = hll2._ranges[range_id]
             self.assertEqual(id(content), id(content2))
 
         # Now modifying one should not effect the other
@@ -209,69 +209,69 @@
         hll = self.get_sectioned_hll()
         hll.delete(0, 3)
         self.assertEqual([3, 4, 5, 6, 7, 8], hll)
-        self.assertEqual(3, hll._ranges_counter)
+        self.assertEqual(3, hll._counter)
         self.assertEqual(1, hll._head)
         self.assertEqual({1:2, 2:3, 3:None}, hll._links)
         self.assertEqual({1:(0, 2, [3, 4]),
                           2:(0, 3, [5, 6, 7]),
                           3:(0, 1, [8]),
-                         }, hll._range_map)
+                         }, hll._ranges)
 
     def test_delete_middle_range(self):
         hll = self.get_sectioned_hll()
         hll.delete(3, 5)
         self.assertEqual([0, 1, 2, 5, 6, 7, 8], hll)
-        self.assertEqual(3, hll._ranges_counter)
+        self.assertEqual(3, hll._counter)
         self.assertEqual(0, hll._head)
         self.assertEqual({0:2, 2:3, 3:None}, hll._links)
         self.assertEqual({0:(0, 3, [0, 1, 2]),
                           2:(0, 3, [5, 6, 7]),
                           3:(0, 1, [8]),
-                         }, hll._range_map)
+                         }, hll._ranges)
 
     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], hll)
-        self.assertEqual(3, hll._ranges_counter)
+        self.assertEqual(3, hll._counter)
         self.assertEqual(0, hll._head)
         self.assertEqual({0:1, 1:2, 2:None}, hll._links)
         self.assertEqual({0:(0, 3, [0, 1, 2]),
                           1:(0, 2, [3, 4]),
                           2:(0, 3, [5, 6, 7]),
-                         }, hll._range_map)
+                         }, hll._ranges)
 
     def test_delete_partial_beginning(self):
         hll = self.get_sectioned_hll()
         hll.delete(0, 2)
         self.assertEqual([2, 3, 4, 5, 6, 7, 8], hll)
-        self.assertEqual(3, hll._ranges_counter)
+        self.assertEqual(3, hll._counter)
         self.assertEqual(0, hll._head)
         self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
         self.assertEqual({0:(2, 3, [0, 1, 2]),
                           1:(0, 2, [3, 4]),
                           2:(0, 3, [5, 6, 7]),
                           3:(0, 1, [8]),
-                         }, hll._range_map)
+                         }, hll._ranges)
 
     def test_delete_partial_ending(self):
         hll = self.get_sectioned_hll()
         hll.delete(1, 3)
         self.assertEqual([0, 3, 4, 5, 6, 7, 8], hll)
-        self.assertEqual(3, hll._ranges_counter)
+        self.assertEqual(3, hll._counter)
         self.assertEqual(0, hll._head)
         self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
         self.assertEqual({0:(0, 1, [0, 1, 2]),
                           1:(0, 2, [3, 4]),
                           2:(0, 3, [5, 6, 7]),
                           3:(0, 1, [8]),
-                         }, hll._range_map)
+                         }, hll._ranges)
 
     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], hll)
-        self.assertEqual(4, hll._ranges_counter)
+        self.assertEqual(4, hll._counter)
         self.assertEqual(0, hll._head)
         self.assertEqual({0:4, 1:2, 2:3, 3:None, 4:1}, hll._links)
         self.assertEqual({0:(0, 1, [0, 1, 2]),
@@ -279,58 +279,81 @@
                           2:(0, 3, [5, 6, 7]),
                           3:(0, 1, [8]),
                           4:(2, 3, [0, 1, 2]),
-                         }, hll._range_map)
+                         }, hll._ranges)
         # Make sure that even though we have 2 entries with the same content,
         # it just copied a reference, not the actual content.
-        self.assertEqual(id(hll._range_map[0][2]), id(hll._range_map[4][2]))
+        self.assertEqual(id(hll._ranges[0][2]), id(hll._ranges[4][2]))
 
     def test_delete_middle(self):
         hll = self.get_sectioned_hll()
         hll.delete(3, 4)
         self.assertEqual([0, 1, 2, 4, 5, 6, 7, 8], hll)
-        self.assertEqual(3, hll._ranges_counter)
+        self.assertEqual(3, hll._counter)
         self.assertEqual(0, hll._head)
         self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
         self.assertEqual({0:(0, 3, [0, 1, 2]),
                           1:(1, 2, [3, 4]),
                           2:(0, 3, [5, 6, 7]),
                           3:(0, 1, [8]),
-                         }, hll._range_map)
+                         }, hll._ranges)
 
     def test_delete_across_sections(self):
         hll = self.get_sectioned_hll()
         hll.delete(1, 7)
         self.assertEqual([0, 7, 8], hll)
-        self.assertEqual(3, hll._ranges_counter)
+        self.assertEqual(3, hll._counter)
         self.assertEqual(0, hll._head)
         self.assertEqual({0:2, 2:3, 3:None}, hll._links)
         self.assertEqual({0:(0, 1, [0, 1, 2]),
                           2:(2, 3, [5, 6, 7]),
                           3:(0, 1, [8]),
-                         }, hll._range_map)
+                         }, hll._ranges)
 
     def test_delete_off_end(self):
         hll = self.get_sectioned_hll()
         hll.delete(1, 9)
         self.assertEqual([0], hll)
-        self.assertEqual(3, hll._ranges_counter)
+        self.assertEqual(3, hll._counter)
         self.assertEqual(0, hll._head)
         self.assertEqual({0:None}, hll._links)
         self.assertEqual({0:(0, 1, [0, 1, 2]),
-                         }, hll._range_map)
+                         }, hll._ranges)
 
     def test_delete_all(self):
         hll = self.get_sectioned_hll()
         hll.delete(0, 9)
         self.assertEqual([], hll)
-        self.assertEqual(3, hll._ranges_counter)
+        self.assertEqual(3, hll._counter)
         self.assertEqual(None, hll._head)
         self.assertEqual({}, hll._links)
-        self.assertEqual({}, hll._range_map)
+        self.assertEqual({}, hll._ranges)
 
         hll.insert(0, [1])
         self.assertEqual([1], 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], 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], 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], 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)
+
     def test_using_tuples(self):
         """HybridLinkedList should work just fine with tuples.
 
@@ -348,26 +371,3 @@
         self.assertEqual((0, 1, 2, 8, 9, 6, 7), hll)
         # Because we use __iter__ tuple() or list() should work fine
         self.assertEqual((0, 1, 2, 8, 9, 6, 7), tuple(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], 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], 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], 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)



More information about the bazaar-commits mailing list