[Checkins] SVN: Sandbox/poster/zc.blist/trunk/src/zc/blist/
checkpoint
Gary Poster
gary at zope.com
Wed May 7 05:50:28 EDT 2008
Log message for revision 86526:
checkpoint
Changed:
U Sandbox/poster/zc.blist/trunk/src/zc/blist/README.txt
U Sandbox/poster/zc.blist/trunk/src/zc/blist/TODO.txt
U Sandbox/poster/zc.blist/trunk/src/zc/blist/__init__.py
A Sandbox/poster/zc.blist/trunk/src/zc/blist/testing.py
U Sandbox/poster/zc.blist/trunk/src/zc/blist/tests.py
-=-
Modified: Sandbox/poster/zc.blist/trunk/src/zc/blist/README.txt
===================================================================
--- Sandbox/poster/zc.blist/trunk/src/zc/blist/README.txt 2008-05-07 09:38:04 UTC (rev 86525)
+++ Sandbox/poster/zc.blist/trunk/src/zc/blist/README.txt 2008-05-07 09:50:27 UTC (rev 86526)
@@ -30,7 +30,7 @@
are frequently iterating or changing.
These sequences return slices as iterators, and add some helpful iteration
-methods.
+methods. __eq__ compares identity.
Other than that, these sequences work like a standard Python sequence. Therefore
this file is not geared towards users of the data structure but implementers.
@@ -90,178 +90,14 @@
=========
- ``count``, ``__eq__``, and other methods load all buckets and items, and are
- brute force in Python. Lists and tuples will load all items, and is brute
- force in C.
+ brute force, and in Python. In contrast, lists and tuples will load all
+ items, and is brute force in C.
The Bad
=======
-- This will create a lot of Persistent objects for one blist, which can cause
- cache eviction problems.
+- This will create a lot of Persistent objects for one blist, which may cause
+ cache eviction problems depending on circumstances and usage.
-==================
-Regression Testing
-==================
+- Did I mention that this was in Python, not C? That's fixable, at least.
-We'll use a `matches` function to compare a bucket sequence with a standard
-Python list to which the same modifications have made. This also checks for
-bucket health [#matches]_.
-
- >>> import zc.blist
- >>> b = zc.blist.BList(bucket_size=5, index_size=4) # we want > 3 so min is > 1
- >>> matches(b, [])
- True
- >>> b.append(0)
- >>> matches(b, [0])
- True
- >>> del b[0]
- >>> matches(b, [])
- True
- >>> b.extend(range(10))
- >>> comparison = range(10)
- >>> matches(b, comparison)
- True
- >>> b.reverse()
- >>> comparison.reverse()
- >>> matches(b, comparison)
- True
- >>> for i in range(10):
- ... b[i] = i+10
- ... comparison[i] = i+10
- ...
- >>> matches(b, comparison)
- True
- >>> b[5:10] = [9, 8, 7, 6, 5]
- >>> comparison[5:10] = [9, 8, 7, 6, 5]
- >>> matches(b, comparison)
- True
- >>> b[0:0] = [-3, -2, -1]
- >>> comparison[0:0] = [-3, -2, -1]
- >>> matches(b, comparison)
- True
- >>> b.extend(range(90, 100))
- >>> comparison.extend(range(90,100))
- >>> matches(b, comparison)
- True
- >>> b[10:10] = range(20, 90)
- >>> comparison[10:10] = range(20, 90)
- >>> matches(b, comparison)
- True
- >>> b[b.index(82)]
- 82
- >>> del b[:4]
- >>> del comparison[:4]
- >>> matches(b, comparison)
- True
- >>> comparison[2:10:2] = [100, 102, 104, 106]
- >>> b[2:10:2] = [100, 102, 104, 106]
- >>> matches(b, comparison)
- True
- >>> del b[1:88]
- >>> del comparison[1:88]
- >>> matches(b, comparison)
- True
- >>> list(b[:])
- [11, 99]
- >>> b[0] = 0
- >>> b[2] = 100
- >>> b[3] = 101
- >>> b[4] = 102
- >>> matches(b, [0, 99, 100, 101, 102])
- True
-
-Switching two values is most efficiently done with slice notation.
-
- >>> b[:] = range(1000)
- >>> b[5:996:990] = (b[995], b[5])
- >>> list(b[:7])
- [0, 1, 2, 3, 4, 995, 6]
- >>> list(b[994:])
- [994, 5, 996, 997, 998, 999]
- >>> comparison = range(1000)
- >>> comparison[5] = 995
- >>> comparison[995] = 5
- >>> matches(b, comparison)
- True
-
-We'll test some of the other methods
-
- >>> b.pop(995) == comparison.pop(995)
- True
- >>> matches(b, comparison)
- True
- >>> b.insert(995, 5)
- >>> comparison.insert(995, 5)
- >>> matches(b, comparison)
- True
-
-These are some more stress and regression tests.
-
- >>> del b[900:]
- >>> del comparison[900:]
- >>> matches(b, comparison)
- True
-
- >>> del comparison[::2]
- >>> del b[::2] # 1
- >>> matches(b, comparison)
- True
- >>> del b[::2] # 2
- >>> del comparison[::2]
- >>> matches(b, comparison)
- True
- >>> del b[::2] # 3
- >>> del comparison[::2]
- >>> matches(b, comparison)
- True
-
-XXX lots more to test, especially exceptions.
-
-.. [#matches]
- >>> def checkIndex(ix, b, previous, previous_ix=0):
- ... computed = 0
- ... if len(previous) < previous_ix+1:
- ... previous.append(None)
- ... assert len(previous) >= previous_ix + 1
- ... # assert isinstance(ix, zc.blist.Index)
- ... assert b.data is ix or len(ix) <= b.index_size
- ... assert b.data is ix or len(ix) >= b.index_size // 2
- ... assert ix.minKey() == 0
- ... for k, v in ix.items():
- ... v = b._mapping[v]
- ... assert computed == k
- ... assert v.parent == ix.identifier
- ... p = previous[previous_ix]
- ... if p is not None:
- ... p = p.identifier
- ... assert v.previous == p
- ... assert (v.previous is None or
- ... previous[previous_ix].next == v.identifier)
- ... assert (v.next is None or
- ... b._mapping[v.next].previous == v.identifier)
- ... computed += v.contained_len(b)
- ... if isinstance(v, zc.blist.Index):
- ... checkIndex(v, b, previous, previous_ix+1)
- ... else:
- ... assert isinstance(v, zc.blist.Bucket)
- ... assert len(v) <= b.bucket_size
- ... assert len(v) >= b.bucket_size // 2
- ... previous[previous_ix] = v
- ...
- >>> def matches(b, result):
- ... assert list(b) == result, repr(list(b)) + ' != ' + repr(result)
- ... res = []
- ... for i in range(len(b)):
- ... res.append(b[i])
- ... assert res == result, repr(res) + ' != ' + repr(result)
- ... #assert set(result) == set(b.children)
- ... #children_errors = [(k, [b._mapping.get(i) for i in v]) for k, v in
- ... # b.children.items() if len(v) != 1]
- ... #assert children_errors == [], repr(children_errors)
- ... # we'll check the buckets internally while we are here
- ... assert b.data.parent is None
- ... assert b.data.previous is None and b.data.next is None
- ... if isinstance(b.data, zc.blist.Index):
- ... checkIndex(b.data, b, [None])
- ... return True
- ...
Modified: Sandbox/poster/zc.blist/trunk/src/zc/blist/TODO.txt
===================================================================
--- Sandbox/poster/zc.blist/trunk/src/zc/blist/TODO.txt 2008-05-07 09:38:04 UTC (rev 86525)
+++ Sandbox/poster/zc.blist/trunk/src/zc/blist/TODO.txt 2008-05-07 09:50:27 UTC (rev 86526)
@@ -1,3 +1,4 @@
-- need much better tests
+- need much better tests. Leaning towards randomly-generated test suite, in
+ part.
-- no tests at all for lazy ``copy`` right now, which is a delicate dance!
+- ...someday... maybe push some of this to C.
\ No newline at end of file
Modified: Sandbox/poster/zc.blist/trunk/src/zc/blist/__init__.py
===================================================================
--- Sandbox/poster/zc.blist/trunk/src/zc/blist/__init__.py 2008-05-07 09:38:04 UTC (rev 86525)
+++ Sandbox/poster/zc.blist/trunk/src/zc/blist/__init__.py 2008-05-07 09:50:27 UTC (rev 86526)
@@ -13,7 +13,9 @@
##############################################################################
import sys
import random
+import itertools
+import ZODB.POSException
import persistent
import persistent.list
import BTrees.OOBTree
@@ -72,7 +74,7 @@
return iter(self._collections)
def add(self, collection):
- if collection not in self._collections:
+ if collection not in self:
self._collections += (collection,)
def remove(self, collection):
@@ -92,6 +94,15 @@
def __getitem__(self, key):
return self._collections.__getitem__(key)
+ def __contains__(self, val):
+ for item in self._collections:
+ if val is item:
+ return True
+ return False
+
+ def __nonzero__(self):
+ return bool(self._collections)
+
class AbstractData(persistent.Persistent):
def __init__(self, collection, identifier=None, previous=None, next=None,
parent=None):
@@ -155,12 +166,12 @@
# move some right
moved = self[move_index:]
right[0:0] = moved
- del left[move_index:]
+ del self[move_index:]
else:
# move some left
move_index -= len_left
moved = right[:move_index]
- left.extend(moved)
+ self.extend(moved)
del right[:move_index]
@method
@@ -213,6 +224,11 @@
AbstractData.__init__(
self, collection, identifier, previous, next, parent)
+ def _p_resolveConflict(self, oldstate, committedstate, newstate):
+ # disable conflict resolution; thinking about its effect in terms of
+ # balancing the tree makes my head hurt.
+ raise ZODB.POSException.ConflictError()
+
def index(self, other):
for k, v in self.items():
if v == other:
@@ -317,7 +333,7 @@
res.index_size = self.index_size
res.family = self.family
res._mapping = self.family.IO.BTree()
- res._top_index = 0
+ res._top_index = self._top_index
res._mapping.update(self._mapping)
for v in self._mapping.values():
v.collections.add(res)
@@ -496,12 +512,14 @@
# __setitem__ helpers
- def _reindex(self, start_bucket, stop_bucket, recurse=False):
- bucket = start_bucket
+ def _reindex(self, start_bucket, stop_bucket_id, recurse=False):
+ if start_bucket is None:
+ return
+ bucket = self._mapping[start_bucket.identifier]
k = None
stopped = False
while bucket is not None and bucket.identifier != self._top_index:
- stopped = stopped or bucket is stop_bucket
+ stopped = stopped or bucket.identifier == stop_bucket_id
parent = self._mapping[bucket.parent]
if k is None:
k = parent.index(bucket.identifier)
@@ -516,8 +534,8 @@
except ValueError:
k = None
if recurse:
- self._reindex(parent, self._mapping[stop_bucket.parent],
- recurse)
+ self._reindex(
+ parent, self._mapping[stop_bucket_id].parent, recurse)
if stopped:
break
else:
@@ -593,15 +611,17 @@
self._top_index = 0
start_bucket = self._mapping[
self._top_index] = Bucket(self, self._top_index)
+ start_bucket_id = self._top_index
start_ix = 0
elif stop != start:
# we're supposed to delete
- start_bucket, start_ix = self._get_bucket(start)
- stop_bucket, stop_ix = self._get_bucket(stop)
- bucket = start_bucket
+ bucket, start_ix = self._get_bucket(start)
+ start_bucket_id = bucket.identifier
+ _stop_bucket, stop_ix = self._get_bucket(stop)
+ stop_bucket_id = _stop_bucket.identifier
ix = start_ix
while True:
- if bucket is stop_bucket:
+ if bucket.identifier == stop_bucket_id:
removed = bucket[ix:stop_ix]
if removed:
bucket = self._mutable(bucket)
@@ -616,15 +636,16 @@
break
bucket = self._mapping[bucket_ix]
ix = 0
- bucket = start_bucket
+ bucket = self._mapping[start_bucket_id]
ix = start_ix
# populate old buckets with new values, until we are out of
# new values or old buckets
while value:
items = shift_sequence(
value, self.bucket_size - len(bucket))
+ bucket = self._mutable(bucket)
bucket[ix:ix] = items
- if bucket is stop_bucket or not value:
+ if bucket.identifier == stop_bucket_id or not value:
stop_ix = len(items)
break
bucket = self._mapping[bucket.next]
@@ -654,9 +675,9 @@
fill_maximum = self.bucket_size
fill_minimum = fill_maximum // 2
- original_stop_bucket = stop_bucket
+ original_stop_bucket_id = stop_bucket_id
- while start_bucket is not None:
+ while start_bucket_id is not None:
# We'll get the buckets rotated so that any
# bucket that has members will be above the fill ratio
@@ -676,11 +697,14 @@
# fill_minimum
len_bucket = len(bucket)
+ stop_bucket = self._mapping[stop_bucket_id]
len_stop = len(stop_bucket)
if (bucket is not stop_bucket and
len_stop and (
len_bucket < fill_minimum or
len_stop < fill_minimum)):
+ bucket = self._mutable(bucket)
+ stop_bucket = self._mutable(stop_bucket)
bucket.rotate(stop_bucket)
len_bucket = len(bucket)
len_stop = len(stop_bucket)
@@ -692,15 +716,19 @@
if ((bucket is stop_bucket or not len_stop) and
bucket.previous is None and stop_bucket.next is None):
- if self.data is not bucket:
- self._mapping.clear()
- self._mapping[bucket.identifier] = bucket
+ if bucket.identifier != self._top_index:
+ # get rid of unnecessary parents
+ p = bucket
+ while p.identifier != self._top_index:
+ p = self._mapping[p.parent]
+ del self._mapping[p.identifier]
+ # this is now the top of the tree
self._top_index = bucket.identifier
bucket.parent = None
else:
assert bucket.parent is None
bucket.next = None
- stop_bucket = None
+ stop_bucket = stop_bucket_id = None
break
# now these are the possible states:
@@ -734,22 +762,34 @@
previous is not None and
len(next) + len_bucket > fill_maximum):
# work with previous
- previous = self._mapping[previous]
+ previous = self._mutable(self._mapping[previous])
+ bucket = self._mutable(bucket)
previous.rotate(bucket)
- if bucket is start_bucket:
- bucket = start_bucket = previous
+ if bucket.identifier == start_bucket_id:
+ bucket = previous
+ start_bucket_id = previous.identifier
if not bucket:
bucket = previous
assert bucket
else:
# work with next
+ bucket = self._mutable(bucket)
+ next = self._mutable(next)
bucket.rotateRight(next)
- stop_bucket = next
+ stop_bucket_id = next.identifier
# OK, now we need to adjust pointers and get rid of
# empty buckets. We'll go level-by-level.
- reindex_start = start_bucket
+ # we keep track of the bucket to reindex on separately from
+ # the start_index because we may have to move it to a
+ # previous bucket if the start_bucket is deleted to make
+ # sure that the next bucket is indexed correctly all the
+ # way up.
+ reindex_start = self._mapping[start_bucket_id]
+ # we need to stash these because they may be removed
+ start_bucket_parent = self._mapping[start_bucket_id].parent
+ stop_bucket_parent = self._mapping[stop_bucket_id].parent
b = bucket
while b is not None:
@@ -757,37 +797,41 @@
if next is not None:
next = self._mapping[next]
if not b: # it is empty
- parent = self._mapping[b.parent]
+ parent = self._mutable(self._mapping[b.parent])
ix = parent.index(b.identifier)
del parent[ix]
- if b.previous is not None:
- self._mapping[b.previous].next = b.next
+ previous = b.previous
+ if previous is not None:
+ previous = self._mutable(
+ self._mapping[previous])
+ previous.next = b.next
if next is not None: # next defined at loop start
+ next = self._mutable(next)
next.previous = b.previous
- if b is reindex_start:
- reindex_start = next
+ if b.identifier == reindex_start.identifier:
+ if previous is not None:
+ reindex_start = previous
+ else:
+ reindex_start = next
+ assert not b.shared
del self._mapping[b.identifier]
- if b is stop_bucket:
+ if b.identifier == stop_bucket_id:
break
b = next
- self._reindex(reindex_start, stop_bucket)
+ self._reindex(reindex_start, stop_bucket_id)
# now we get ready for the next round...
- start_bucket = start_bucket.parent
- if start_bucket is not None:
- start_bucket = self._mapping[start_bucket]
- stop_bucket = stop_bucket.parent
- if stop_bucket is not None:
- stop_bucket = self._mapping[stop_bucket]
+ start_bucket_id = start_bucket_parent
+ stop_bucket_id = stop_bucket_parent
bucket = bucket.parent
if bucket is not None:
bucket = self._mapping[bucket]
fill_maximum = self.index_size
fill_minimum = fill_maximum // 2
- assert stop_bucket is None
+ assert stop_bucket_id is None
if not value:
return # we're done; don't fall through to add story
@@ -796,12 +840,13 @@
# some more left. we'll set things up so the
# standard insert story should work for the remaining
# values.
- start_bucket = original_stop_bucket
+ start_bucket_id = original_stop_bucket_id
start_ix = stop_ix
# ...now continue with add story
else:
- start_bucket, start_ix = self._get_bucket(start)
+ _start_bucket, start_ix = self._get_bucket(start)
+ start_bucket_id = _start_bucket.identifier
# this is the add story.
# So, we have a start_bucket and a start_ix: we're supposed
@@ -811,15 +856,15 @@
fill_maximum = self.bucket_size
fill_minimum = fill_maximum // 2
- # Clean out the ones after start_ix in the start_bucket, if
+ # Clean out the ones after start_ix in the start bucket, if
# any.
- moved = start_bucket[start_ix:]
+ bucket = self._mapping[start_bucket_id]
+ moved = bucket[start_ix:]
value.extend(moved)
- start_bucket = self._mutable(start_bucket)
- del start_bucket[start_ix:]
+ bucket = self._mutable(bucket)
+ del bucket[start_ix:]
ix = start_ix
- bucket = start_bucket
created = []
# Start filling at the ix. Fill until we reached len
@@ -851,6 +896,7 @@
# contents of the previous bucket and this one--that way
# there's not any empty bucket to have to handle.
previous = self._mapping[bucket.previous]
+ assert not previous.shared
assert len(previous) + len(bucket) >= 2 * fill_minimum
previous.balance(bucket)
@@ -861,15 +907,17 @@
# we add a level at the top and continue.
if not created:
- self._reindex(start_bucket, bucket)
+ self._reindex(
+ self._mapping[start_bucket_id], bucket.identifier)
return
value = created
fill_maximum = self.index_size
fill_minimum = fill_maximum // 2
+ start_bucket = self._mutable(self._mapping[start_bucket_id])
while value:
- if start_bucket.identifier == self._top_index: # the top
+ if start_bucket_id == self._top_index: # the top
assert start_bucket.parent is None
self._top_index = identifier = self._generateId()
parent = self._mapping[identifier] = Index(
@@ -878,10 +926,12 @@
start_bucket.parent = parent.identifier
start_ix = 0
bucket = start_bucket = parent
+ start_bucket_id = identifier
else:
- parent = self._mapping[start_bucket.parent]
+ parent = self._mutable(self._mapping[start_bucket.parent])
start_ix = parent.index(start_bucket.identifier)
bucket = start_bucket = parent
+ start_bucket_id = start_bucket.identifier
value.extend(
self._mapping[i] for i in
start_bucket.values(start_ix, excludemin=True))
@@ -901,6 +951,7 @@
length = fill_maximum - len(bucket)
while value:
for o in shift_sequence(value, length):
+ assert not o.shared # these are newly created
bucket[ix] = o.identifier
o.parent = bucket.identifier
ix += o.contained_len(self)
@@ -925,21 +976,21 @@
# just split the contents of the previous bucket and
# this one--that way there's not any empty bucket to
# have to handle.
- assert (len(self._mapping[bucket.previous]) + len(bucket) >=
- 2 * fill_minimum)
- self._mapping[bucket.previous].balance(bucket)
+ previous = self._mapping[bucket.previous]
+ assert (len(previous) + len(bucket) >= 2 * fill_minimum)
+ assert not previous.shared # I *think* this is an
+ # invariant; otherwise need to doublecheck and then use
+ # _mutable
+ previous.balance(bucket)
value = created
if start_bucket.identifier != self._top_index:
# we need to correct the indices of the parents.
- self._reindex(start_bucket, bucket, recurse=True)
+ self._reindex(start_bucket, bucket.identifier, recurse=True)
else:
# replace one set with a set of equal length
changed = []
index = start
- removed = {}
- problems = set()
- added = {}
error = None
value_ct = 0
for v in value:
@@ -952,14 +1003,6 @@
break
bucket, ix = self._get_bucket(index)
old = bucket[ix]
- if old in removed:
- removed[old].add(bucket)
- else:
- removed[old] = set((bucket,))
- if v in added:
- added[v].add(bucket.identifier)
- else:
- added[v] = set((bucket.identifier,))
bucket[ix] = v
changed.append((bucket, ix, old))
index += stride
@@ -969,11 +1012,6 @@
'attempt to assign sequence of size %d to '
'extended slice of size %d' % (
value_ct, (stop - start) / stride))
- if not error and problems:
- problems.difference_update(removed)
- if problems:
- error = ValueError('item(s) already in collection',
- problems)
if error:
for bucket, ix, old in changed:
bucket[ix] = old
@@ -982,7 +1020,12 @@
# I want eq and ne but don't care much about the rest
def __eq__(self, other):
- return isinstance(other, Sequence) and tuple(self) == tuple(other)
+ if self.__class__ is not other.__class__ or len(self) != len(other):
+ return False
+ for s, o in itertools.izip(self, other):
+ if s != o:
+ return False
+ return True
def __ne__(self, other):
return not self.__eq__(other)
Added: Sandbox/poster/zc.blist/trunk/src/zc/blist/testing.py
===================================================================
--- Sandbox/poster/zc.blist/trunk/src/zc/blist/testing.py (rev 0)
+++ Sandbox/poster/zc.blist/trunk/src/zc/blist/testing.py 2008-05-07 09:50:27 UTC (rev 86526)
@@ -0,0 +1,73 @@
+import zc.blist
+
+def checkIndex(ix, b, previous, previous_ix=0):
+ computed = 0
+ if len(previous) < previous_ix+1:
+ previous.append(None)
+ assert len(previous) >= previous_ix + 1
+ # assert isinstance(ix, zc.blist.Index)
+ assert b.data is ix or len(ix) <= b.index_size
+ assert b.data is ix or len(ix) >= b.index_size // 2
+ assert ix.minKey() == 0
+ for k, v in ix.items():
+ v = b._mapping[v]
+ assert computed == k
+ assert v.parent == ix.identifier
+ p = previous[previous_ix]
+ if p is not None:
+ p = p.identifier
+ assert v.previous == p
+ assert (v.previous is None or
+ previous[previous_ix].next == v.identifier)
+ assert (v.next is None or
+ b._mapping[v.next].previous == v.identifier)
+ computed += v.contained_len(b)
+ if isinstance(v, zc.blist.Index):
+ checkIndex(v, b, previous, previous_ix+1)
+ else:
+ assert isinstance(v, zc.blist.Bucket)
+ assert len(v) <= b.bucket_size
+ assert (len(v) >= b.bucket_size // 2)
+ previous[previous_ix] = v
+
+def matches(b, result):
+ assert list(b) == result, repr(list(b)) + ' != ' + repr(result)
+ res = []
+ for i in range(len(b)):
+ res.append(b[i])
+ assert res == result, repr(res) + ' != ' + repr(result)
+ # we'll check the buckets internally while we are here
+ assert b.data.parent is None
+ assert b.data.previous is None and b.data.next is None
+ if isinstance(b.data, zc.blist.Index):
+ checkIndex(b.data, b, [None])
+ return True
+
+def checkCopies(one, two):
+ one_diff = list(
+ one.family.IO.difference(one._mapping, two._mapping))
+ for k in one_diff:
+ data = one._mapping[k]
+ assert one in data.collections
+ assert two not in data.collections
+ two_diff = list(
+ one.family.IO.difference(two._mapping, one._mapping))
+ for k in two_diff:
+ data = two._mapping[k]
+ assert two in data.collections
+ assert one not in data.collections
+ diff = []
+ for k, v in one._mapping.items():
+ alt = two._mapping.get(k)
+ if alt is None:
+ assert k in one_diff
+ continue
+ if alt is v:
+ assert one in v.collections and two in v.collections
+ else:
+ assert (one in v.collections and
+ one not in alt.collections and
+ two in alt.collections and
+ two not in v.collections)
+ diff.append((k, v, alt))
+ return one_diff, two_diff, diff
Modified: Sandbox/poster/zc.blist/trunk/src/zc/blist/tests.py
===================================================================
--- Sandbox/poster/zc.blist/trunk/src/zc/blist/tests.py 2008-05-07 09:38:04 UTC (rev 86525)
+++ Sandbox/poster/zc.blist/trunk/src/zc/blist/tests.py 2008-05-07 09:50:27 UTC (rev 86526)
@@ -16,11 +16,198 @@
from zope.testing import doctest
+def by_hand_regression_test():
+ """
+ ==================
+ Regression Testing
+ ==================
+
+ We'll use a `matches` function to compare a bucket sequence with a standard
+ Python list to which the same modifications have made. This also checks for
+ bucket health.
+
+ >>> import zc.blist
+ >>> from zc.blist.testing import matches, checkIndex
+ >>> b = zc.blist.BList(bucket_size=5, index_size=4) # we want > 3 so min is > 1
+ >>> matches(b, [])
+ True
+ >>> b.append(0)
+ >>> matches(b, [0])
+ True
+ >>> del b[0]
+ >>> matches(b, [])
+ True
+ >>> b.extend(range(10))
+ >>> comparison = range(10)
+ >>> matches(b, comparison)
+ True
+ >>> b.reverse()
+ >>> comparison.reverse()
+ >>> matches(b, comparison)
+ True
+ >>> for i in range(10):
+ ... b[i] = i+10
+ ... comparison[i] = i+10
+ ...
+ >>> matches(b, comparison)
+ True
+ >>> b[5:10] = [9, 8, 7, 6, 5]
+ >>> comparison[5:10] = [9, 8, 7, 6, 5]
+ >>> matches(b, comparison)
+ True
+ >>> b[0:0] = [-3, -2, -1]
+ >>> comparison[0:0] = [-3, -2, -1]
+ >>> matches(b, comparison)
+ True
+ >>> b.extend(range(90, 100))
+ >>> comparison.extend(range(90,100))
+ >>> matches(b, comparison)
+ True
+ >>> b[10:10] = range(20, 90)
+ >>> comparison[10:10] = range(20, 90)
+ >>> matches(b, comparison)
+ True
+ >>> b[b.index(82)]
+ 82
+ >>> del b[:4]
+ >>> del comparison[:4]
+ >>> matches(b, comparison)
+ True
+ >>> comparison[2:10:2] = [100, 102, 104, 106]
+ >>> b[2:10:2] = [100, 102, 104, 106]
+ >>> matches(b, comparison)
+ True
+ >>> del b[1:88]
+ >>> del comparison[1:88]
+ >>> matches(b, comparison)
+ True
+ >>> list(b[:])
+ [11, 99]
+ >>> b[0] = 0
+ >>> b[2] = 100
+ >>> b[3] = 101
+ >>> b[4] = 102
+ >>> matches(b, [0, 99, 100, 101, 102])
+ True
+
+ Switching two values is most efficiently done with slice notation.
+
+ >>> b[:] = range(1000)
+ >>> b[5:996:990] = (b[995], b[5])
+ >>> list(b[:7])
+ [0, 1, 2, 3, 4, 995, 6]
+ >>> list(b[994:])
+ [994, 5, 996, 997, 998, 999]
+ >>> comparison = range(1000)
+ >>> comparison[5] = 995
+ >>> comparison[995] = 5
+ >>> matches(b, comparison)
+ True
+
+ We'll test some of the other methods
+
+ >>> b.pop(995) == comparison.pop(995)
+ True
+ >>> matches(b, comparison)
+ True
+ >>> b.insert(995, 5)
+ >>> comparison.insert(995, 5)
+ >>> matches(b, comparison)
+ True
+
+ These are some more stress and regression tests.
+
+ >>> del b[900:]
+ >>> del comparison[900:]
+ >>> matches(b, comparison)
+ True
+
+ >>> del comparison[::2]
+ >>> del b[::2] # 1
+ >>> matches(b, comparison)
+ True
+ >>> del b[::2] # 2
+ >>> del comparison[::2]
+ >>> matches(b, comparison)
+ True
+ >>> del b[::2] # 3
+ >>> del comparison[::2]
+ >>> matches(b, comparison)
+ True
+
+ >>> alt = zc.blist.BList(b)
+ >>> alt_comp = comparison[:]
+ >>> matches(b, comparison)
+ True
+ >>> del alt[::3]
+ >>> del alt_comp[::3]
+ >>> matches(alt, alt_comp)
+ True
+ >>> del alt[::3]
+ >>> del alt_comp[::3]
+ >>> matches(alt, alt_comp)
+ True
+ >>> del alt[-1:5:-2]
+ >>> del alt_comp[-1:5:-2]
+ >>> matches(alt, alt_comp)
+ True
+
+ The ``copy`` method gives a complete copy, reusing buckets and indexes.
+
+ >>> from zc.blist.testing import checkCopies
+ >>> old_comparison = comparison[:]
+ >>> new = b.copy()
+ >>> new == b
+ True
+ >>> def check():
+ ... assert matches(new, comparison)
+ ... assert matches(b, old_comparison)
+ ... return checkCopies(b, new)
+ ...
+ >>> check()
+ ([], [], [])
+ >>> del new[4]
+ >>> del comparison[4]
+ >>> [len(v) for v in check()] # 4 = 1 bucket, 3 indexes
+ [0, 0, 4]
+ >>> del old_comparison[10]
+ >>> del b[10]
+ >>> [len(v) for v in check()]
+ [0, 1, 9]
+ >>> new.append(999999999)
+ >>> comparison.append(999999999)
+ >>> [len(v) for v in check()]
+ [0, 1, 10]
+ >>> new.extend(range(5000, 5100))
+ >>> comparison.extend(range(5000, 5100))
+ >>> [len(v) for v in check()]
+ [0, 27, 13]
+ >>> del new[15:50]
+ >>> del comparison[15:50]
+ >>> [len(v) for v in check()]
+ [20, 27, 16]
+ >>> del new[::3]
+ >>> del comparison[::3]
+ >>> [len(v) for v in check()]
+ [34, 26, 32]
+ >>> del new[::2]
+ >>> del comparison[::2]
+ >>> [len(v) for v in check()]
+ [55, 19, 11]
+ >>> del new[-1:5:-2]
+ >>> del comparison[-1:5:-2]
+ >>> [len(v) for v in check()]
+ [55, 6, 11]
+
+ XXX lots more to test, especially exceptions.
+ """
+
def test_suite():
return unittest.TestSuite((
doctest.DocFileSuite(
'README.txt',
optionflags=doctest.INTERPRET_FOOTNOTES),
+ doctest.DocTestSuite()
))
More information about the Checkins
mailing list