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