Rev 2256: Implement equality for lists and tuples and other hlls. 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:47:02 GMT 2007
At http://bzr.arbash-meinel.com/branches/bzr/0.15-dev/list_patch
------------------------------------------------------------
revno: 2256
revision-id: john at arbash-meinel.com-20070130184657-vq3ftadvoywwmkjr
parent: john at arbash-meinel.com-20070130183358-hom3lwhr0sew9so0
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: list_patch
timestamp: Tue 2007-01-30 12:46:57 -0600
message:
Implement equality for lists and tuples and other hlls.
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:33:58 +0000
+++ b/bzrlib/hybrid_linked_list.py 2007-01-30 18:46:57 +0000
@@ -16,6 +16,8 @@
"""A hybrid between linked lists and straight arrays."""
+from itertools import izip
+
class HybridLinkedList(object):
"""A hybrid between linked lists and straight arrays.
@@ -79,6 +81,20 @@
cur_range_id = self._links[cur_range_id]
return length
+ def __eq__(self, other):
+ """Check for equality"""
+ if isinstance(other, (list, tuple, HybridLinkedList)):
+ # Equality is determined based on content, not on exact definitions
+ other_length = len(other)
+ self_length = len(self)
+ if other_length != self_length:
+ return False
+ for self_val, other_val in izip(self, other):
+ if self_val != other_val:
+ return False
+ return True
+ return False
+
def __getitem__(self, pos):
if isinstance(pos, slice):
# cur, stop, stride are in terms of location in the output list.
=== modified file 'bzrlib/tests/test_hybrid_linked_list.py'
--- a/bzrlib/tests/test_hybrid_linked_list.py 2007-01-30 18:33:58 +0000
+++ b/bzrlib/tests/test_hybrid_linked_list.py 2007-01-30 18:46:57 +0000
@@ -26,20 +26,20 @@
def test_create_and_iterate(self):
hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
- self.assertEqual([0, 1, 2, 3, 4], list(hll))
+ self.assertEqual([0, 1, 2, 3, 4], hll)
self.assertEqual(5, len(hll))
def test_empty(self):
hll = hybrid_linked_list.HybridLinkedList([])
self.assertEqual(0, len(hll))
- self.assertEqual([], list(hll))
+ self.assertEqual([], hll)
def test__find_nodes_for_pos(self):
content = [0, 1, 2, 3, 4, 5, 6, 7, 8]
hll = hybrid_linked_list.HybridLinkedList(content)
hll.delete(2, 3)
hll.delete(5, 7)
- self.assertEqual([0, 1, 3, 4, 5, 8], list(hll))
+ self.assertEqual([0, 1, 3, 4, 5, 8], hll)
self.assertEqual((None, 0, 0, 0, 2, content), hll._find_nodes_for_pos(0))
self.assertEqual((None, 0, 1, 0, 2, content), hll._find_nodes_for_pos(1))
self.assertEqual((0, 1, 0, 3, 6, content), hll._find_nodes_for_pos(2))
@@ -51,26 +51,43 @@
self.assertEqual((2, None, 1, None, None, None),
hll._find_nodes_for_pos(7))
+ def test__eq__(self):
+ """Test for equality"""
+ hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4, 5, 6, 7, 8])
+ hll2 = hybrid_linked_list.HybridLinkedList()
+ hll2.insert(0, [0, 1, 2, 3, 4])
+ hll2.insert(5, [5, 6, 8])
+ hll2.insert(7, [7])
+
+ self.assertEqual(hll, hll2)
+ self.assertEqual([0, 1, 2, 3, 4, 5, 6, 7, 8], hll)
+ self.assertEqual([0, 1, 2, 3, 4, 5, 6, 7, 8], hll2)
+ # This is a little unorthodox because (0, 1) != [0, 1]
+ # however, internally HybridLinkedList might be using tuples or lists,
+ # so we may as well support comparisons
+ self.assertEqual((0, 1, 2, 3, 4, 5, 6, 7, 8), hll)
+ self.assertEqual((0, 1, 2, 3, 4, 5, 6, 7, 8), hll2)
+
def test__delitem__(self):
hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4, 5, 6, 7, 8])
del hll[2]
- self.assertEqual([0, 1, 3, 4, 5, 6, 7, 8], list(hll))
+ self.assertEqual([0, 1, 3, 4, 5, 6, 7, 8], hll)
del hll[5:7]
- self.assertEqual([0, 1, 3, 4, 5, 8], list(hll))
+ self.assertEqual([0, 1, 3, 4, 5, 8], hll)
del hll[-1]
- self.assertEqual([0, 1, 3, 4, 5], list(hll))
+ self.assertEqual([0, 1, 3, 4, 5], hll)
# Do nothing when the range == same
del hll[-1:-1]
- self.assertEqual([0, 1, 3, 4, 5], list(hll))
+ self.assertEqual([0, 1, 3, 4, 5], hll)
def test__getitem__(self):
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([0, 1, 3, 4, 5, 8], hll)
for expected, pos in zip([0, 1, 3, 4, 5, 8], xrange(0,5)):
self.assertEqual(expected, hll[pos])
@@ -89,44 +106,44 @@
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([0, 1, 3, 4, 5, 8], hll)
# Set a single item
hll[1] = 9
- self.assertEqual([0, 9, 3, 4, 5, 8], list(hll))
+ self.assertEqual([0, 9, 3, 4, 5, 8], hll)
# Set a range of items
hll[1:3] = [10]
- self.assertEqual([0, 10, 4, 5, 8], list(hll))
+ self.assertEqual([0, 10, 4, 5, 8], hll)
# Delete a range
hll[2:4] = []
- self.assertEqual([0, 10, 8], list(hll))
+ self.assertEqual([0, 10, 8], hll)
# Set using negative values
hll[-1] = 11
- self.assertEqual([0, 10, 11], list(hll))
+ self.assertEqual([0, 10, 11], hll)
# Set using negative values
hll[-2:-1] = [12, 13]
- self.assertEqual([0, 12, 13, 11], list(hll))
+ self.assertEqual([0, 12, 13, 11], hll)
def test_insert(self):
hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
hll.insert(3, [5, 6, 7])
- self.assertEqual([0, 1, 2, 5, 6, 7, 3, 4], list(hll))
+ self.assertEqual([0, 1, 2, 5, 6, 7, 3, 4], hll)
self.assertEqual(8, len(hll))
hll.flatten()
def test_insert_beginning(self):
hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
hll.insert(0, [5])
- self.assertEqual([5, 0, 1, 2, 3, 4], list(hll))
+ self.assertEqual([5, 0, 1, 2, 3, 4], hll)
def test_insert_end(self):
hll = hybrid_linked_list.HybridLinkedList([0, 1, 2, 3, 4])
hll.insert(5, [5])
- self.assertEqual([0, 1, 2, 3, 4, 5], list(hll))
+ self.assertEqual([0, 1, 2, 3, 4, 5], hll)
def get_sectioned_hll(self):
"""Get a HybridLinkedList that is already broken into sections."""
@@ -139,7 +156,7 @@
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([0, 1, 2, 3, 4, 5, 6, 7, 8], hll)
self.assertEqual(3, hll._ranges_counter)
self.assertEqual(0, hll._head)
self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
@@ -153,10 +170,10 @@
hll = hybrid_linked_list.HybridLinkedList([0, 1, 2])
hll.insert(3, [3, 4])
hll.insert(5, [5])
- self.assertEqual([0, 1, 2, 3, 4, 5], list(hll))
+ self.assertEqual([0, 1, 2, 3, 4, 5], hll)
hll2 = hll.copy()
- self.assertEqual([0, 1, 2, 3, 4, 5], list(hll2))
+ self.assertEqual([0, 1, 2, 3, 4, 5], hll2)
# After copying, the contents should be identical
self.assertEqual(hll._ranges_counter, hll2._ranges_counter)
@@ -171,27 +188,27 @@
# Now modifying one should not effect the other
hll.delete(3, 5)
- self.assertEqual([0, 1, 2, 5], list(hll))
- self.assertEqual([0, 1, 2, 3, 4, 5], list(hll2))
+ self.assertEqual([0, 1, 2, 5], hll)
+ self.assertEqual([0, 1, 2, 3, 4, 5], hll2)
hll2.insert(4, [6])
- self.assertEqual([0, 1, 2, 5], list(hll))
- self.assertEqual([0, 1, 2, 3, 6, 4, 5], list(hll2))
+ self.assertEqual([0, 1, 2, 5], hll)
+ self.assertEqual([0, 1, 2, 3, 6, 4, 5], hll2)
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))
+ self.assertEqual([0, 1, 3, 4], 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))
+ self.assertEqual([0, 3, 4], 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, 4, 5, 6, 7, 8], hll)
self.assertEqual(3, hll._ranges_counter)
self.assertEqual(1, hll._head)
self.assertEqual({1:2, 2:3, 3:None}, hll._links)
@@ -203,7 +220,7 @@
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([0, 1, 2, 5, 6, 7, 8], hll)
self.assertEqual(3, hll._ranges_counter)
self.assertEqual(0, hll._head)
self.assertEqual({0:2, 2:3, 3:None}, hll._links)
@@ -215,7 +232,7 @@
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([0, 1, 2, 3, 4, 5, 6, 7], hll)
self.assertEqual(3, hll._ranges_counter)
self.assertEqual(0, hll._head)
self.assertEqual({0:1, 1:2, 2:None}, hll._links)
@@ -227,7 +244,7 @@
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([2, 3, 4, 5, 6, 7, 8], hll)
self.assertEqual(3, hll._ranges_counter)
self.assertEqual(0, hll._head)
self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
@@ -240,7 +257,7 @@
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([0, 3, 4, 5, 6, 7, 8], hll)
self.assertEqual(3, hll._ranges_counter)
self.assertEqual(0, hll._head)
self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
@@ -253,7 +270,7 @@
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([0, 2, 3, 4, 5, 6, 7, 8], 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)
@@ -270,7 +287,7 @@
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([0, 1, 2, 4, 5, 6, 7, 8], hll)
self.assertEqual(3, hll._ranges_counter)
self.assertEqual(0, hll._head)
self.assertEqual({0:1, 1:2, 2:3, 3:None}, hll._links)
@@ -283,7 +300,7 @@
def test_delete_across_sections(self):
hll = self.get_sectioned_hll()
hll.delete(1, 7)
- self.assertEqual([0, 7, 8], list(hll))
+ self.assertEqual([0, 7, 8], hll)
self.assertEqual(3, hll._ranges_counter)
self.assertEqual(0, hll._head)
self.assertEqual({0:2, 2:3, 3:None}, hll._links)
@@ -295,7 +312,7 @@
def test_delete_off_end(self):
hll = self.get_sectioned_hll()
hll.delete(1, 9)
- self.assertEqual([0], list(hll))
+ self.assertEqual([0], hll)
self.assertEqual(3, hll._ranges_counter)
self.assertEqual(0, hll._head)
self.assertEqual({0:None}, hll._links)
@@ -305,34 +322,52 @@
def test_delete_all(self):
hll = self.get_sectioned_hll()
hll.delete(0, 9)
- self.assertEqual([], list(hll))
+ self.assertEqual([], 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))
+ self.assertEqual([1], hll)
+
+ def test_using_tuples(self):
+ """HybridLinkedList should work just fine with tuples.
+
+ Because it never modifies contents, it can use tuples internally rather
+ than using lists that can be modified. If it is determined that tuples
+ are faster in practise, we can switch over to them.
+ """
+ hll = hybrid_linked_list.HybridLinkedList((0, 1, 2, 3, 4))
+ hll.insert(5, (5,))
+ hll[6:6] = (6, 7)
+ self.assertEqual([0, 1, 2, 3, 4, 5, 6, 7], hll)
+ self.assertEqual((0, 1, 2, 3, 4, 5, 6, 7), hll)
+
+ hll[3:6] = (8, 9)
+ 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], list(hll))
+ 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], list(hll))
+ 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], list(hll))
+ 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], list(hll))
+ self.assertEqual([5, 1, 2, 3, 4], hll)
More information about the bazaar-commits
mailing list