[Checkins] SVN: BTrees/branches/pure_python/ Move '___BTree.py' -> '_base.py'.
Tres Seaver
cvs-admin at zope.org
Mon Nov 12 18:37:29 UTC 2012
Log message for revision 128259:
Move '___BTree.py' -> '_base.py'.
Changed:
_U BTrees/branches/pure_python/
U BTrees/branches/pure_python/BTrees/IFBTree.py
U BTrees/branches/pure_python/BTrees/IIBTree.py
U BTrees/branches/pure_python/BTrees/IOBTree.py
U BTrees/branches/pure_python/BTrees/LFBTree.py
U BTrees/branches/pure_python/BTrees/LLBTree.py
U BTrees/branches/pure_python/BTrees/LOBTree.py
U BTrees/branches/pure_python/BTrees/OIBTree.py
U BTrees/branches/pure_python/BTrees/OLBTree.py
U BTrees/branches/pure_python/BTrees/OOBTree.py
D BTrees/branches/pure_python/BTrees/___BTree.py
A BTrees/branches/pure_python/BTrees/_base.py
U BTrees/branches/pure_python/BTrees/fsBTree.py
A BTrees/branches/pure_python/BTrees/tests/test__base.py
D BTrees/branches/pure_python/BTrees/tests/test_base.py
-=-
Modified: BTrees/branches/pure_python/BTrees/IFBTree.py
===================================================================
--- BTrees/branches/pure_python/BTrees/IFBTree.py 2012-11-12 18:37:28 UTC (rev 128258)
+++ BTrees/branches/pure_python/BTrees/IFBTree.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -20,23 +20,23 @@
from zope.interface import moduleProvides
-from BTrees.Interfaces import IIntegerFloatBTreeModule
-from BTrees.___BTree import Bucket
-from BTrees.___BTree import MERGE
-from BTrees.___BTree import MERGE_WEIGHT_numeric
-from BTrees.___BTree import MERGE_DEFAULT_float
-from BTrees.___BTree import Set
-from BTrees.___BTree import Tree as BTree
-from BTrees.___BTree import TreeSet
-from BTrees.___BTree import difference as _difference
-from BTrees.___BTree import intersection as _intersection
-from BTrees.___BTree import multiunion as _multiunion
-from BTrees.___BTree import setop as _setop
-from BTrees.___BTree import to_int as _to_key
-from BTrees.___BTree import to_float as _to_value
-from BTrees.___BTree import union as _union
-from BTrees.___BTree import weightedIntersection as _weightedIntersection
-from BTrees.___BTree import weightedUnion as _weightedUnion
+from .Interfaces import IIntegerFloatBTreeModule
+from ._base import Bucket
+from ._base import MERGE
+from ._base import MERGE_WEIGHT_numeric
+from ._base import MERGE_DEFAULT_float
+from ._base import Set
+from ._base import Tree as BTree
+from ._base import TreeSet
+from ._base import difference as _difference
+from ._base import intersection as _intersection
+from ._base import multiunion as _multiunion
+from ._base import setop as _setop
+from ._base import to_int as _to_key
+from ._base import to_float as _to_value
+from ._base import union as _union
+from ._base import weightedIntersection as _weightedIntersection
+from ._base import weightedUnion as _weightedUnion
_BUCKET_SIZE = 120
_TREE_SIZE = 500
Modified: BTrees/branches/pure_python/BTrees/IIBTree.py
===================================================================
--- BTrees/branches/pure_python/BTrees/IIBTree.py 2012-11-12 18:37:28 UTC (rev 128258)
+++ BTrees/branches/pure_python/BTrees/IIBTree.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -20,23 +20,23 @@
from zope.interface import moduleProvides
-from BTrees.Interfaces import IIntegerIntegerBTreeModule
-from BTrees.___BTree import Bucket
-from BTrees.___BTree import MERGE
-from BTrees.___BTree import MERGE_WEIGHT_numeric
-from BTrees.___BTree import MERGE_DEFAULT_int
-from BTrees.___BTree import Set
-from BTrees.___BTree import Tree as BTree
-from BTrees.___BTree import TreeSet
-from BTrees.___BTree import difference as _difference
-from BTrees.___BTree import intersection as _intersection
-from BTrees.___BTree import multiunion as _multiunion
-from BTrees.___BTree import setop as _setop
-from BTrees.___BTree import to_int as _to_key
-from BTrees.___BTree import to_int as _to_value
-from BTrees.___BTree import union as _union
-from BTrees.___BTree import weightedIntersection as _weightedIntersection
-from BTrees.___BTree import weightedUnion as _weightedUnion
+from .Interfaces import IIntegerIntegerBTreeModule
+from ._base import Bucket
+from ._base import MERGE
+from ._base import MERGE_WEIGHT_numeric
+from ._base import MERGE_DEFAULT_int
+from ._base import Set
+from ._base import Tree as BTree
+from ._base import TreeSet
+from ._base import difference as _difference
+from ._base import intersection as _intersection
+from ._base import multiunion as _multiunion
+from ._base import setop as _setop
+from ._base import to_int as _to_key
+from ._base import to_int as _to_value
+from ._base import union as _union
+from ._base import weightedIntersection as _weightedIntersection
+from ._base import weightedUnion as _weightedUnion
_BUCKET_SIZE = 120
_TREE_SIZE = 500
Modified: BTrees/branches/pure_python/BTrees/IOBTree.py
===================================================================
--- BTrees/branches/pure_python/BTrees/IOBTree.py 2012-11-12 18:37:28 UTC (rev 128258)
+++ BTrees/branches/pure_python/BTrees/IOBTree.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -19,19 +19,19 @@
from zope.interface import moduleProvides
-from BTrees.Interfaces import IIntegerObjectBTreeModule
-from BTrees.___BTree import Bucket
-from BTrees.___BTree import MERGE_WEIGHT_default
-from BTrees.___BTree import Set
-from BTrees.___BTree import Tree as BTree
-from BTrees.___BTree import TreeSet
-from BTrees.___BTree import difference as _difference
-from BTrees.___BTree import intersection as _intersection
-from BTrees.___BTree import multiunion as _multiunion
-from BTrees.___BTree import setop as _setop
-from BTrees.___BTree import to_int as _to_key
-from BTrees.___BTree import to_ob as _to_value
-from BTrees.___BTree import union as _union
+from .Interfaces import IIntegerObjectBTreeModule
+from ._base import Bucket
+from ._base import MERGE_WEIGHT_default
+from ._base import Set
+from ._base import Tree as BTree
+from ._base import TreeSet
+from ._base import difference as _difference
+from ._base import intersection as _intersection
+from ._base import multiunion as _multiunion
+from ._base import setop as _setop
+from ._base import to_int as _to_key
+from ._base import to_ob as _to_value
+from ._base import union as _union
_BUCKET_SIZE = 60
_TREE_SIZE = 500
Modified: BTrees/branches/pure_python/BTrees/LFBTree.py
===================================================================
--- BTrees/branches/pure_python/BTrees/LFBTree.py 2012-11-12 18:37:28 UTC (rev 128258)
+++ BTrees/branches/pure_python/BTrees/LFBTree.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -20,23 +20,23 @@
from zope.interface import moduleProvides
-from BTrees.Interfaces import IIntegerFloatBTreeModule
-from BTrees.___BTree import Bucket
-from BTrees.___BTree import MERGE
-from BTrees.___BTree import MERGE_WEIGHT_numeric
-from BTrees.___BTree import MERGE_DEFAULT_float
-from BTrees.___BTree import Set
-from BTrees.___BTree import Tree as BTree
-from BTrees.___BTree import TreeSet
-from BTrees.___BTree import difference as _difference
-from BTrees.___BTree import intersection as _intersection
-from BTrees.___BTree import multiunion as _multiunion
-from BTrees.___BTree import setop as _setop
-from BTrees.___BTree import to_long as _to_key
-from BTrees.___BTree import to_float as _to_value
-from BTrees.___BTree import union as _union
-from BTrees.___BTree import weightedIntersection as _weightedIntersection
-from BTrees.___BTree import weightedUnion as _weightedUnion
+from .Interfaces import IIntegerFloatBTreeModule
+from ._base import Bucket
+from ._base import MERGE
+from ._base import MERGE_WEIGHT_numeric
+from ._base import MERGE_DEFAULT_float
+from ._base import Set
+from ._base import Tree as BTree
+from ._base import TreeSet
+from ._base import difference as _difference
+from ._base import intersection as _intersection
+from ._base import multiunion as _multiunion
+from ._base import setop as _setop
+from ._base import to_long as _to_key
+from ._base import to_float as _to_value
+from ._base import union as _union
+from ._base import weightedIntersection as _weightedIntersection
+from ._base import weightedUnion as _weightedUnion
_BUCKET_SIZE = 120
_TREE_SIZE = 500
Modified: BTrees/branches/pure_python/BTrees/LLBTree.py
===================================================================
--- BTrees/branches/pure_python/BTrees/LLBTree.py 2012-11-12 18:37:28 UTC (rev 128258)
+++ BTrees/branches/pure_python/BTrees/LLBTree.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -20,23 +20,23 @@
from zope.interface import moduleProvides
-from BTrees.Interfaces import IIntegerIntegerBTreeModule
-from BTrees.___BTree import Bucket
-from BTrees.___BTree import MERGE
-from BTrees.___BTree import MERGE_WEIGHT_numeric
-from BTrees.___BTree import MERGE_DEFAULT_int
-from BTrees.___BTree import Set
-from BTrees.___BTree import Tree as BTree
-from BTrees.___BTree import TreeSet
-from BTrees.___BTree import difference as _difference
-from BTrees.___BTree import intersection as _intersection
-from BTrees.___BTree import multiunion as _multiunion
-from BTrees.___BTree import setop as _setop
-from BTrees.___BTree import to_long as _to_key
-from BTrees.___BTree import to_long as _to_value
-from BTrees.___BTree import union as _union
-from BTrees.___BTree import weightedIntersection as _weightedIntersection
-from BTrees.___BTree import weightedUnion as _weightedUnion
+from .Interfaces import IIntegerIntegerBTreeModule
+from ._base import Bucket
+from ._base import MERGE
+from ._base import MERGE_WEIGHT_numeric
+from ._base import MERGE_DEFAULT_int
+from ._base import Set
+from ._base import Tree as BTree
+from ._base import TreeSet
+from ._base import difference as _difference
+from ._base import intersection as _intersection
+from ._base import multiunion as _multiunion
+from ._base import setop as _setop
+from ._base import to_long as _to_key
+from ._base import to_long as _to_value
+from ._base import union as _union
+from ._base import weightedIntersection as _weightedIntersection
+from ._base import weightedUnion as _weightedUnion
_BUCKET_SIZE = 120
_TREE_SIZE = 500
Modified: BTrees/branches/pure_python/BTrees/LOBTree.py
===================================================================
--- BTrees/branches/pure_python/BTrees/LOBTree.py 2012-11-12 18:37:28 UTC (rev 128258)
+++ BTrees/branches/pure_python/BTrees/LOBTree.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -19,19 +19,19 @@
from zope.interface import moduleProvides
-from BTrees.Interfaces import IIntegerObjectBTreeModule
-from BTrees.___BTree import Bucket
-from BTrees.___BTree import MERGE_WEIGHT_default
-from BTrees.___BTree import Set
-from BTrees.___BTree import Tree as BTree
-from BTrees.___BTree import TreeSet
-from BTrees.___BTree import difference as _difference
-from BTrees.___BTree import intersection as _intersection
-from BTrees.___BTree import multiunion as _multiunion
-from BTrees.___BTree import setop as _setop
-from BTrees.___BTree import to_long as _to_key
-from BTrees.___BTree import to_ob as _to_value
-from BTrees.___BTree import union as _union
+from .Interfaces import IIntegerObjectBTreeModule
+from ._base import Bucket
+from ._base import MERGE_WEIGHT_default
+from ._base import Set
+from ._base import Tree as BTree
+from ._base import TreeSet
+from ._base import difference as _difference
+from ._base import intersection as _intersection
+from ._base import multiunion as _multiunion
+from ._base import setop as _setop
+from ._base import to_long as _to_key
+from ._base import to_ob as _to_value
+from ._base import union as _union
_BUCKET_SIZE = 60
_TREE_SIZE = 500
Modified: BTrees/branches/pure_python/BTrees/OIBTree.py
===================================================================
--- BTrees/branches/pure_python/BTrees/OIBTree.py 2012-11-12 18:37:28 UTC (rev 128258)
+++ BTrees/branches/pure_python/BTrees/OIBTree.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -20,22 +20,22 @@
from zope.interface import moduleProvides
-from BTrees.Interfaces import IObjectIntegerBTreeModule
-from BTrees.___BTree import Bucket
-from BTrees.___BTree import MERGE
-from BTrees.___BTree import MERGE_WEIGHT_numeric
-from BTrees.___BTree import MERGE_DEFAULT_float
-from BTrees.___BTree import Set
-from BTrees.___BTree import Tree as BTree
-from BTrees.___BTree import TreeSet
-from BTrees.___BTree import difference as _difference
-from BTrees.___BTree import intersection as _intersection
-from BTrees.___BTree import setop as _setop
-from BTrees.___BTree import to_ob as _to_key
-from BTrees.___BTree import to_int as _to_value
-from BTrees.___BTree import union as _union
-from BTrees.___BTree import weightedIntersection as _weightedIntersection
-from BTrees.___BTree import weightedUnion as _weightedUnion
+from .Interfaces import IObjectIntegerBTreeModule
+from ._base import Bucket
+from ._base import MERGE
+from ._base import MERGE_WEIGHT_numeric
+from ._base import MERGE_DEFAULT_float
+from ._base import Set
+from ._base import Tree as BTree
+from ._base import TreeSet
+from ._base import difference as _difference
+from ._base import intersection as _intersection
+from ._base import setop as _setop
+from ._base import to_ob as _to_key
+from ._base import to_int as _to_value
+from ._base import union as _union
+from ._base import weightedIntersection as _weightedIntersection
+from ._base import weightedUnion as _weightedUnion
_BUCKET_SIZE = 60
_TREE_SIZE = 250
Modified: BTrees/branches/pure_python/BTrees/OLBTree.py
===================================================================
--- BTrees/branches/pure_python/BTrees/OLBTree.py 2012-11-12 18:37:28 UTC (rev 128258)
+++ BTrees/branches/pure_python/BTrees/OLBTree.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -20,22 +20,22 @@
from zope.interface import moduleProvides
-from BTrees.Interfaces import IObjectIntegerBTreeModule
-from BTrees.___BTree import Bucket
-from BTrees.___BTree import MERGE
-from BTrees.___BTree import MERGE_WEIGHT_numeric
-from BTrees.___BTree import MERGE_DEFAULT_int
-from BTrees.___BTree import Set
-from BTrees.___BTree import Tree as BTree
-from BTrees.___BTree import TreeSet
-from BTrees.___BTree import difference as _difference
-from BTrees.___BTree import intersection as _intersection
-from BTrees.___BTree import setop as _setop
-from BTrees.___BTree import to_ob as _to_key
-from BTrees.___BTree import to_int as _to_value
-from BTrees.___BTree import union as _union
-from BTrees.___BTree import weightedIntersection as _weightedIntersection
-from BTrees.___BTree import weightedUnion as _weightedUnion
+from .Interfaces import IObjectIntegerBTreeModule
+from ._base import Bucket
+from ._base import MERGE
+from ._base import MERGE_WEIGHT_numeric
+from ._base import MERGE_DEFAULT_int
+from ._base import Set
+from ._base import Tree as BTree
+from ._base import TreeSet
+from ._base import difference as _difference
+from ._base import intersection as _intersection
+from ._base import setop as _setop
+from ._base import to_ob as _to_key
+from ._base import to_int as _to_value
+from ._base import union as _union
+from ._base import weightedIntersection as _weightedIntersection
+from ._base import weightedUnion as _weightedUnion
_BUCKET_SIZE = 60
_TREE_SIZE = 250
Modified: BTrees/branches/pure_python/BTrees/OOBTree.py
===================================================================
--- BTrees/branches/pure_python/BTrees/OOBTree.py 2012-11-12 18:37:28 UTC (rev 128258)
+++ BTrees/branches/pure_python/BTrees/OOBTree.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -19,17 +19,17 @@
from zope.interface import moduleProvides
-from BTrees.Interfaces import IObjectObjectBTreeModule
-from BTrees.___BTree import Bucket
-from BTrees.___BTree import Set
-from BTrees.___BTree import Tree as BTree
-from BTrees.___BTree import TreeSet
-from BTrees.___BTree import difference as _difference
-from BTrees.___BTree import intersection as _intersection
-from BTrees.___BTree import setop as _setop
-from BTrees.___BTree import to_ob as _to_key
-from BTrees.___BTree import to_ob as _to_value
-from BTrees.___BTree import union as _union
+from .Interfaces import IObjectObjectBTreeModule
+from ._base import Bucket
+from ._base import Set
+from ._base import Tree as BTree
+from ._base import TreeSet
+from ._base import difference as _difference
+from ._base import intersection as _intersection
+from ._base import setop as _setop
+from ._base import to_ob as _to_key
+from ._base import to_ob as _to_value
+from ._base import union as _union
_BUCKET_SIZE = 30
_TREE_SIZE = 250
Deleted: BTrees/branches/pure_python/BTrees/___BTree.py
===================================================================
--- BTrees/branches/pure_python/BTrees/___BTree.py 2012-11-12 18:37:28 UTC (rev 128258)
+++ BTrees/branches/pure_python/BTrees/___BTree.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -1,1150 +0,0 @@
-##############################################################################
-#
-# Copyright 2011 Zope Foundation and Contributors.
-# All Rights Reserved.
-#
-# This software is subject to the provisions of the Zope Public License,
-# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
-# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
-# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
-# FOR A PARTICULAR PURPOSE.
-#
-##############################################################################
-"""Python BTree implementation
-"""
-
-from struct import pack
-from struct import unpack
-from struct import error as struct_error
-
-import persistent
-
-from BTrees.Interfaces import BTreesConflictError
-
-_marker = object()
-
-
-class _Base(persistent.Persistent):
-
- _key_type = list
-
- def __init__(self, items=None):
- self.clear()
- if items:
- self.update(items)
-
-
-class _BucketBase(_Base):
-
- def clear(self):
- self._keys = self._key_type()
- self._next = None
-
- def __len__(self):
- return len(self._keys)
-
- @property
- def size(self):
- return len(self._keys)
-
- def _deleteNextBucket(self):
- next = self._next
- if next is not None:
- self._next = next._next
-
- def _search(self, key):
- # Return non-negative index on success
- # return -(insertion_index + 1) on fail
- low = 0
- keys = self._keys
- high = len(keys)
- while low < high:
- i = (low + high) // 2
- k = keys[i]
- if k == key:
- return i
- if k < key:
- low = i + 1
- else:
- high = i
- return -1 - low
-
- def minKey(self, key=_marker):
- if key is _marker:
- return self._keys[0]
- key = self._to_key(key)
- index = self._search(key)
- if index >- 0:
- return key
- else:
- index = -index - 1
- if index < len(self._keys):
- return self._keys[index]
- else:
- raise ValueError("no key satisfies the conditions")
-
- def maxKey(self, key=_marker):
- if key is _marker:
- return self._keys[-1]
- key = self._to_key(key)
- index = self._search(key)
- if index >= 0:
- return key
- else:
- index = -index-1
- if index:
- return self._keys[index-1]
- else:
- raise ValueError("no key satisfies the conditions")
-
- def _range(self, min=_marker, max=_marker,
- excludemin=False, excludemax=False):
- if min is _marker:
- start = 0
- if excludemin:
- start = 1
- else:
- min = self._to_key(min)
- start = self._search(min)
- if start >= 0:
- if excludemin:
- start += 1
- else:
- start = -start - 1
- if max is _marker:
- end = len(self._keys)
- if excludemax:
- end -= 1
- else:
- max = self._to_key(max)
- end = self._search(max)
- if end >= 0:
- if not excludemax:
- end += 1
- else:
- end = -end - 1
-
- return start, end
-
- def keys(self, *args, **kw):
- start, end = self._range(*args, **kw)
- return self._keys[start:end]
-
- def iterkeys(self, *args, **kw):
- if not (args or kw):
- return iter(self._keys)
- keys = self._keys
- return (keys[i] for i in xrange(*self._range(*args, **kw)))
-
- def __iter__(self):
- return iter(self._keys)
-
- def has_key(self, key):
- return (self._search(self._to_key(key)) >= 0) and 1
-
- __contains__ = has_key
-
- def _p_resolveConflict(self, *states):
- set = not hasattr(self, '_values')
-
- buckets = []
- for state in states:
- bucket = self.__class__()
- if state:
- bucket.__setstate__(state)
- buckets.append(bucket)
- if (buckets[1]._next != buckets[0]._next or
- buckets[2]._next != buckets[0]._next):
- raise BTreesConflictError(-1, -1, -1, 0)
-
- if not (buckets[1] and buckets[2]):
- raise BTreesConflictError(-1, -1, -1, 12)
-
- i1 = _SetIteration(buckets[0], True)
- i2 = _SetIteration(buckets[1], True)
- i3 = _SetIteration(buckets[2], True)
-
- def merge_error(reason):
- return BTreesConflictError(
- i1.position, i2.position, i3.position, reason)
-
- result = self.__class__()
-
- if set:
- def merge_output(it):
- result._keys.append(it.key)
- it.advance()
- else:
- def merge_output(it):
- result._keys.append(it.key)
- result._values.append(it.value)
- it.advance()
-
- while i1.active and i2.active and i3.active:
- cmp12 = cmp(i1.key, i2.key)
- cmp13 = cmp(i1.key, i3.key)
- if cmp12==0:
- if cmp13==0:
- if set:
- result.add(i1.key)
- elif i2.value == i1.value:
- result[i1.key] = i3.value
- elif i3.value == i1.value:
- result[i1.key] = i2.value
- else:
- raise merge_error(1)
- i1.advance()
- i2.advance()
- i3.advance()
- elif (cmp13 > 0): # insert in new
- merge_output(i3)
- elif set or i1.value == i2.value: # deleted new
- if i3.position == 1:
- # Deleted the first item. This will modify the
- # parent node, so we don't know if merging will be
- # safe
- raise merge_error(13)
- i1.advance()
- i2.advance()
- else:
- raise merge_error(2)
- elif cmp13 == 0:
- if cmp12 > 0: # insert committed
- merge_output(i2)
- elif set or i1.value == i3.value: # delete committed
- if i2.position == 1:
- # Deleted the first item. This will modify the
- # parent node, so we don't know if merging will be
- # safe
- raise merge_error(13)
- i1.advance()
- i3.advance()
- else:
- raise merge_error(3)
- else: # both keys changed
- cmp23 = cmp(i2.key, i3.key)
- if cmp23 == 0:
- raise merge_error(4)
- if cmp12 > 0: # insert committed
- if cmp23 > 0: # insert i3 first
- merge_output(i3)
- else:
- merge_output(i2)
- elif cmp13 > 0: # insert i3
- merge_output(i3)
- else:
- raise merge_error(5) # both deleted same key
-
- while i2.active and i3.active: # new inserts
- cmp23 = cmp(i2.key, i3.key)
- if cmp23 == 0:
- raise merge_error(6) # dueling insert
- if cmp23 > 0: # insert new
- merge_output(i3)
- else: # insert committed
- merge_output(i2)
-
- while i1.active and i2.active: # new deletes rest of original
- cmp12 = cmp(i1.key, i2.key)
- if cmp12 > 0: # insert committed
- merge_output(i2)
- elif cmp12 == 0 and (set or i1.value == i2.value): # deleted in new
- i1.advance()
- i2.advance()
- else: # dueling deletes or delete and change
- raise merge_error(7)
-
- while i1.active and i3.active: # committed deletes rest of original
- cmp13 = cmp(i1.key, i3.key)
- if cmp13 > 0: # insert new
- merge_output(i3)
- elif cmp13 == 0 and (set or i1.value == i3.value):
- # deleted in committed
- i1.advance()
- i3.advance()
- else: # dueling deletes or delete and change
- raise merge_error(8)
-
- if i1.active: # dueling deletes
- raise merge_error(9)
-
- while i2.active:
- merge_output(i2)
-
- while i3.active:
- merge_output(i3)
-
- if len(result._keys) == 0:
- # If the output bucket is empty, conflict resolution doesn't have
- # enough info to unlink it from its containing BTree correctly.
- raise merge_error(10)
-
- result._next = buckets[0]._next
- return result.__getstate__()
-
-
-class _SetIteration(object):
-
- def __init__(self, set, useValues=False, default=None):
- if set is None:
- set = ()
- self.set = set
- if useValues:
- try:
- itmeth = set.iteritems
- except AttributeError:
- itmeth = set.__iter__
- useValues = False
- else:
- self.value = None
- else:
- itmeth = set.__iter__
-
- self.useValues = useValues
- self._next = itmeth().next
- self.active = True
- self.position = 0
- self.value = default
- self.advance()
-
- def advance(self):
- try:
- if self.useValues:
- self.key, self.value = self._next()
- else:
- self.key = self._next()
- self.position += 1
- except StopIteration:
- self.active = False
- self.position = -1
-
- return self
-
-
-class _MappingBase(_Base):
-
- def setdefault(self, key, value):
- return self._set(self._to_key(key), self._to_value(value), True)[1]
-
- def pop(self, key, default=_marker):
- try:
- return self._del(self._to_key(key))[1]
- except KeyError:
- if default is _marker:
- raise
- return default
-
- def update(self, items):
- if hasattr(items, 'iteritems'):
- items = items.iteritems()
- elif hasattr(items, 'items'):
- items = items.items()
-
- set = self.__setitem__
- for i in items:
- set(*i)
-
- def __setitem__(self, key, value):
- # Enforce test that key has non-default comparison.
- if ( getattr(key, '__lt__', None) is None and
- getattr(key, '__cmp__', None) is None):
- raise TypeError("Can't use default __cmp__")
- self._set(self._to_key(key), self._to_value(value))
-
- def __delitem__(self, key):
- self._del(self._to_key(key))
-
-
-class _SetBase(_Base):
-
- def add(self, key):
- return self._set(self._to_key(key))[0]
-
- insert = add
-
- def remove(self, key):
- self._del(self._to_key(key))
-
- def update(self, items):
- add = self.add
- for i in items:
- add(i)
-
-
-class Bucket(_MappingBase, _BucketBase):
-
- _value_type = list
- _to_value = lambda x: x
- VALUE_SAME_CHECK = False
-
- def clear(self):
- _BucketBase.clear(self)
- self._values = self._value_type()
-
- def get(self, key, default=None):
- index = self._search(self._to_key(key))
- if index < 0:
- return default
- return self._values[index]
-
- def __getitem__(self, key):
- index = self._search(self._to_key(key))
- if index < 0:
- raise KeyError(key)
- return self._values[index]
-
- def _set(self, key, value, ifunset=False):
- """Set a value
-
- Return: status, value
-
- Status is:
- None if no change
- 0 if change, but not size change
- 1 if change and size change
- """
- index = self._search(key)
- if index >= 0:
- if (ifunset or
- self.VALUE_SAME_CHECK and value == self._values[index]
- ):
- return None, self._values[index]
- self._p_changed = True
- self._values[index] = value
- return 0, value
- else:
- self._p_changed = True
- index = -index - 1
- self._keys.insert(index, key)
- self._values.insert(index, value)
- return 1, value
-
- def _del(self, key):
- index = self._search(key)
- if index >= 0:
- self._p_changed = True
- del self._keys[index]
- return 0, self._values.pop(index)
- raise KeyError(key)
-
- def _split(self, index=-1):
- if index < 0 or index >= len(self._keys):
- index = len(self._keys) / 2
- new_instance = self.__class__()
- new_instance._keys = self._keys[index:]
- new_instance._values = self._values[index:]
- del self._keys[index:]
- del self._values[index:]
- new_instance._next = self._next
- self._next = new_instance
- return new_instance
-
- def values(self, *args, **kw):
- start, end = self._range(*args, **kw)
- return self._values[start:end]
-
- def itervalues(self, *args, **kw):
- values = self._values
- return (values[i] for i in xrange(*self._range(*args, **kw)))
-
- def items(self, *args, **kw):
- keys = self._keys
- values = self._values
- return [(keys[i], values[i]) for i in xrange(*self._range(*args, **kw))]
-
- def iteritems(self, *args, **kw):
- keys = self._keys
- values = self._values
- return ((keys[i], values[i]) for i in xrange(*self._range(*args, **kw)))
-
- def __getstate__(self):
- keys = self._keys
- values = self._values
- data = []
- for i in range(len(keys)):
- data.append(keys[i])
- data.append(values[i])
- data = tuple(data)
-
- if self._next:
- return data, self._next
- return (data, )
-
- def __setstate__(self, state):
- if not isinstance(state[0], tuple):
- raise TypeError("tuple required for first state element")
-
- self.clear()
- if len(state) == 2:
- state, self._next = state
- else:
- self._next = None
- state = state[0]
-
- keys = self._keys
- values = self._values
- for i in range(0, len(state), 2):
- keys.append(state[i])
- values.append(state[i+1])
-
-
-class Set(_SetBase, _BucketBase):
-
- def __getstate__(self):
- data = tuple(self._keys)
- if self._next:
- return data, self._next
- return (data, )
-
- def __setstate__(self, state):
- if not isinstance(state[0], tuple):
- raise TypeError('tuple required for first state element')
-
- self.clear()
- if len(state) == 2:
- state, self._next = state
- else:
- self._next = None
- state = state[0]
-
- self._keys.extend(state)
-
-
- def _set(self, key, value=None, ifunset=False):
- index = self._search(key)
- if index < 0:
- index = -index - 1
- self._keys.insert(index, key)
- return True, None
- return False, None
-
- def _del(self, key):
- index = self._search(key)
- if index >= 0:
- self._p_changed = True
- del self._keys[index]
- return 0, 0
- raise KeyError(key)
-
- def __getitem__(self, i):
- return self._keys[i]
-
- def _split(self, index=-1):
- if index < 0 or index >= len(self._keys):
- index = len(self._keys) / 2
- new_instance = self.__class__()
- new_instance._keys = self._keys[index:]
- del self._keys[index:]
- new_instance._next = self._next
- self._next = new_instance
- return new_instance
-
-
-class _TreeItem(object):
-
- __slots__ = 'key', 'child'
-
- def __init__(self, key, child):
- self.key = key
- self.child = child
-
-
-class _Tree(_MappingBase):
-
- def clear(self):
- self._data = []
- self._firstbucket = None
-
- def __nonzero__(self):
- return bool(self._data)
-
- def __len__(self):
- l = 0
- bucket = self._firstbucket
- while bucket is not None:
- l += len(bucket._keys)
- bucket = bucket._next
- return l
-
- @property
- def size(self):
- return len(self._data)
-
- def _search(self, key):
- data = self._data
- if data:
- lo = 0
- hi = len(data)
- i = hi//2
- while i > lo:
- cmp_ = cmp(data[i].key, key)
- if cmp_ < 0:
- lo = i
- elif cmp_ > 0:
- hi = i
- else:
- break
- i = (lo+hi)//2
- return i
- return -1
-
- def _findbucket(self, key):
- index = self._search(key)
- if index >= 0:
- child = self._data[index].child
- if isinstance(child, self._bucket_type):
- return child
- return child._findbucket(key)
-
- def __contains__(self, key):
- return key in (self._findbucket(self._to_key(key)) or ())
-
- def has_key(self, key):
- index = self._search(key)
- if index < 0:
- return False
- r = self._data[index].child.has_key(key)
- return r and r + 1
-
- def keys(self, min=_marker, max=_marker,
- excludemin=False, excludemax=False,
- itertype='iterkeys'):
- if not self._data:
- return ()
-
- if min != _marker:
- min = self._to_key(min)
- bucket = self._findbucket(min)
- else:
- bucket = self._firstbucket
-
- iterargs = min, max, excludemin, excludemax
-
- return _TreeItems(bucket, itertype, iterargs)
-
- def iterkeys(self, min=_marker, max=_marker,
- excludemin=False, excludemax=False):
- return iter(self.keys(min, max, excludemin, excludemax))
-
- def __iter__(self):
- return iter(self.keys())
-
- def minKey(self, min=_marker):
- if min is _marker:
- bucket = self._firstbucket
- else:
- min = self._to_key(min)
- bucket = self._findbucket(min)
- if bucket is not None:
- return bucket.minKey(min)
- raise ValueError('empty tree')
-
- def maxKey(self, max=_marker):
- data = self._data
- if not data:
- raise ValueError('empty tree')
- if max is _marker:
- return data[-1].child.maxKey()
-
- max = self._to_key(max)
- index = self._search(max)
- if index and data[index].child.minKey() > max:
- index -= 1
- return data[index].child.maxKey(max)
-
-
- def _set(self, key, value=None, ifunset=False):
- if (self._p_jar is not None and
- self._p_oid is not None and
- self._p_serial is not None):
- self._p_jar.readCurrent(self)
- data = self._data
- if data:
- index = self._search(key)
- child = data[index].child
- else:
- index = 0
- child = self._bucket_type()
- self._firstbucket = child
- data.append(_TreeItem(None, child))
-
- result = child._set(key, value, ifunset)
- grew = result[0]
- if grew and child.size > child.MAX_SIZE:
- self._grow(child, index)
- elif (grew is not None and
- child.__class__ is self._bucket_type and
- len(data) == 1 and
- child._p_oid is None
- ):
- self._p_changed = 1
- return result
-
- def _grow(self, child, index):
- self._p_changed = True
- new_child = child._split()
- self._data.insert(index+1, _TreeItem(new_child.minKey(), new_child))
- if len(self._data) > self.MAX_SIZE * 2:
- self._split_root()
-
- def _split_root(self):
- child = self.__class__()
- child._data = self._data
- child._firstbucket = self._firstbucket
- self._data = [_TreeItem(None, child)]
- self._grow(child, 0)
-
- def _split(self, index=None):
- data = self._data
- if index is None:
- index = len(data)//2
-
- next = self.__class__()
- next._data = data[index:]
- first = data[index]
- del data[index:]
- if isinstance(first.child, self.__class__):
- next._firstbucket = first.child._firstbucket
- else:
- next._firstbucket = first.child;
- return next
-
- def _del(self, key):
- if (self._p_jar is not None and
- self._p_oid is not None and
- self._p_serial is not None):
- self._p_jar.readCurrent(self)
- data = self._data
- if data:
- index = self._search(key)
- child = data[index].child
- else:
- raise KeyError(key)
-
- removed_first_bucket, value = child._del(key)
-
- if index and child.size and key == data[index].key:
- self._p_changed = True
- data[index].key = child.minKey()
-
- if removed_first_bucket:
- if index:
- data[index-1].child._deleteNextBucket()
- removed_first_bucket = False # clear flag
- else:
- self._firstbucket = child._firstbucket
-
- if not child.size:
- if child.__class__ is self._bucket_type:
- if index:
- data[index-1].child._deleteNextBucket()
- else:
- self._firstbucket = child._next
- removed_first_bucket = True
- del data[index]
-
- return removed_first_bucket, value
-
- def _deleteNextBucket(self):
- self._data[-1].child._deleteNextBucket()
-
- def __getstate__(self):
- data = self._data
-
- if not data:
- return None
-
- if (len(data) == 1 and
- data[0].child.__class__ is not self.__class__ and
- data[0].child._p_oid is None
- ):
- return ((data[0].child.__getstate__(), ), )
-
- sdata = []
- for item in data:
- if sdata:
- sdata.append(item.key)
- sdata.append(item.child)
- else:
- sdata.append(item.child)
-
- return tuple(sdata), self._firstbucket
-
- def __setstate__(self, state):
- if state and not isinstance(state[0], tuple):
- raise TypeError('tuple required for first state element')
-
- self.clear()
- if state is None:
- return
-
- if len(state) == 1:
- bucket = self._bucket_type()
- bucket.__setstate__(state[0][0])
- state = [bucket], bucket
-
- data, self._firstbucket = state
- data = list(reversed(data))
-
- self._data.append(_TreeItem(None, data.pop()))
- while data:
- key = data.pop()
- child = data.pop()
- self._data.append(_TreeItem(key, child))
-
- def _assert(self, condition, message):
- if not condition:
- raise AssertionError(message)
-
- def _check(self, nextbucket=None):
- data = self._data
- assert_ = self._assert
- if not data:
- assert_(self._firstbucket is None,
- "Empty BTree has non-NULL firstbucket")
- return
- assert_(self._firstbucket is not None,
- "Non-empty BTree has NULL firstbucket")
-
- child_class = data[0].child.__class__
- for i in data:
- assert_(i.child is not None, "BTree has NULL child")
- assert_(i.child.__class__ is child_class,
- "BTree children have different types");
- assert_(i.child.size, "Bucket length < 1")
-
- if child_class is self.__class__:
- assert_(self._firstbucket is data[0].child._firstbucket,
- "BTree has firstbucket different than "
- "its first child's firstbucket")
- for i in range(len(data)-1):
- data[i].child._check(data[i+1].child._firstbucket)
- data[-1].child._check(nextbucket)
- elif child_class is self._bucket_type:
- assert_(self._firstbucket is data[0].child,
- "Bottom-level BTree node has inconsistent firstbucket "
- "belief")
- for i in range(len(data)-1):
- assert_(data[i].child._next is data[i+1].child,
- "Bucket next pointer is damaged")
- assert_(data[-1].child._next is nextbucket,
- "Bucket next pointer is damaged")
- else:
- assert_(False, "Incorrect child type")
-
- def _p_resolveConflict(self, *states):
- states = map(_get_simple_btree_bucket_state, states)
- return ((self._bucket_type()._p_resolveConflict(*states), ), )
-
-
-def _get_simple_btree_bucket_state(state):
- if state is None:
- return state
-
- if not isinstance(state, tuple):
- raise TypeError("_p_resolveConflict: expected tuple or None for state")
- if len(state) == 2:
- raise BTreesConflictError(-1, -1, -1, 11)
-
- if len(state) != 1:
- raise TypeError("_p_resolveConflict: expected 1- or 2-tuple for state")
-
- state = state[0]
- if not isinstance(state, tuple) or len(state) != 1:
- raise TypeError("_p_resolveConflict: expected 1-tuple containing "
- "bucket state");
- state = state[0]
- if not isinstance(state, tuple):
- raise TypeError("_p_resolveConflict: expected tuple for bucket state")
-
- return state
-
-
-class _TreeItems(object):
-
- def __init__(self, firstbucket, itertype, iterargs):
- self.firstbucket = firstbucket
- self.itertype = itertype
- self.iterargs = iterargs
- self.index = -1
- self.it = iter(self)
-
- def __getitem__(self, i):
- if isinstance(i, slice):
- return list(self)[i]
- if i < 0:
- i = len(self) + i
- if i < 0:
- raise IndexError(i)
-
- if i < self.index:
- self.index = -1
- self.it = iter(self)
-
- while i > self.index:
- try:
- self.v = self.it.next()
- except StopIteration:
- raise IndexError(i)
- else:
- self.index += 1
- return self.v
-
- def __len__(self):
- try:
- return self._len
- except AttributeError:
- i = 0
- for _ in self:
- i += 1
- self._len = i
- return self._len
-
- def __iter__(self):
- bucket = self.firstbucket
- itertype = self.itertype
- iterargs = self.iterargs
- done = 0
- # Note that we don't mind if the first bucket yields no
- # results due to an idiosyncrasy in how range searches are done.
- while bucket is not None:
- for k in getattr(bucket, itertype)(*iterargs):
- yield k
- done = 0
- if done:
- return
- bucket = bucket._next
- done = 1
-
-
-class Tree(_Tree):
-
- def get(self, key, default=None):
- bucket = self._findbucket(key)
- if bucket:
- return bucket.get(key, default)
- return default
-
- def __getitem__(self, key):
- bucket = self._findbucket(key)
- if bucket:
- return bucket[key]
- raise KeyError(key)
-
- def values(self, min=_marker, max=_marker,
- excludemin=False, excludemax=False):
- return self.keys(min, max, excludemin, excludemax, 'itervalues')
-
- def itervalues(self, min=_marker, max=_marker,
- excludemin=False, excludemax=False):
- return iter(self.values(min, max, excludemin, excludemax))
-
- def items(self, min=_marker, max=_marker,
- excludemin=False, excludemax=False):
- return self.keys(min, max, excludemin, excludemax, 'iteritems')
-
- def iteritems(self, min=_marker, max=_marker,
- excludemin=False, excludemax=False):
- return iter(self.items(min, max, excludemin, excludemax))
-
- def byValue(self, min):
- return sorted((v, k) for (k, v) in self.iteritems() if v >= min)
-
- def insert(self, key, value):
- return bool(self._set(key, value, True)[0])
-
-
-class TreeSet(_SetBase, _Tree):
- pass
-
-
-def _set_operation(s1, s2,
- usevalues1=False, usevalues2=False,
- w1=1, w2=1,
- c1=True, c12=True, c2=True):
- MERGE_DEFAULT = getattr(s1, 'MERGE_DEFAULT', None)
- i1 = _SetIteration(s1, usevalues1, MERGE_DEFAULT)
- i2 = _SetIteration(s2, usevalues2, MERGE_DEFAULT)
- merge = i1.useValues or i2.useValues
- MERGE = getattr(s1, 'MERGE', None)
- if merge:
- MERGE_WEIGHT = getattr(s1, 'MERGE_WEIGHT')
- if MERGE is None and c12 and i1.useValues and i2.useValues:
- raise TypeError("invalid set operation")
-
- if (not i1.useValues) and i2.useValues:
- t = i1; i1 = i2; i2 = t
- t = w1; w1 = w2; w2 = t
- t = c1; c1 = c2; c2 = t
-
- if MERGE_DEFAULT is None:
- if i1.useValues:
- if (not i2.useValues) and c2:
- raise TypeError("invalid set operation")
- else:
- if c1 or c12:
- raise TypeError("invalid set operation")
-
- r = s1._mapping_type()
-
- def copy(i, w):
- r._keys.append(i.key)
- r._values.append(MERGE_WEIGHT(i.value, w))
- else:
- r = s1._set_type()
- def copy(i, w):
- r._keys.append(i.key)
-
- while i1.active and i2.active:
- cmp_ = cmp(i1.key, i2.key)
- if cmp_ < 0:
- if c1:
- copy(i1, w1)
- i1.advance()
- elif cmp_ == 0:
- if c12:
- r._keys.append(i1.key)
- if merge:
- r._values.append(MERGE(i1.value, w1, i2.value, w2))
- i1.advance()
- i2.advance()
- else:
- if c2:
- copy(i2, w2)
- i2.advance()
-
- if c1:
- while i1.active:
- copy(i1, w1)
- i1.advance()
- if c2:
- while i2.active:
- copy(i2, w2)
- i2.advance()
-
- return r
-
-
-class setop(object):
-
- def __init__(self, func, set_type):
- self.func = func
- self.set_type = set_type
-
- def __call__(self, *a, **k):
- return self.func(self.set_type, *a, **k)
-
-
-def difference(set_type, o1, o2):
- if o1 is None or o2 is None:
- return o1
- return _set_operation(o1, o2, 1, 0, 1, 0, 1, 0, 0)
-
-def union(set_type, o1, o2):
- if o1 is None:
- return o2
- if o2 is None:
- return o1
- return _set_operation(o1, o2, 0, 0, 1, 1, 1, 1, 1)
-
-def intersection(set_type, o1, o2):
- if o1 is None:
- return o2
- if o2 is None:
- return o1
- return _set_operation(o1, o2, 0, 0, 1, 1, 0, 1, 0)
-
-def weightedUnion(set_type, o1, o2, w1=1, w2=1):
- if o1 is None:
- if o2 is None:
- return 0, o2
- else:
- return w2, o2
- elif o2 is None:
- return w1, o1
- else:
- return 1, _set_operation(o1, o2, 1, 1, w1, w2, 1, 1, 1)
-
-def weightedIntersection(set_type, o1, o2, w1=1, w2=1):
- if o1 is None:
- if o2 is None:
- return 0, o2
- else:
- return w2, o2
- elif o2 is None:
- return w1, o1
- else:
- result = _set_operation(o1, o2, 1, 1, w1, w2, 0, 1, 0)
- return (w1 + w2 if isinstance(result, (Set, TreeSet)) else 1, result)
-
-def multiunion(set_type, seqs):
- # XXX simple/slow implementation. Goal is just to get tests to pass.
- if not seqs:
- return set_type()
- result = set_type()
- for s in seqs:
- try:
- iter(s)
- except TypeError:
- s = set_type((s, ))
- result.update(s)
- return result
-
-def to_ob(self, v):
- return v
-
-int_types = int, long
-def to_int(self, v):
- try:
- if not unpack("i", pack("i", v))[0] == v:
- raise TypeError('32-bit integer expected')
- except (struct_error,
- OverflowError, #PyPy
- ):
- raise TypeError('32-bit integer expected')
-
- return int(v)
-
-def to_float(self, v):
- try:
- pack("f", v)
- except struct_error:
- raise TypeError('float expected')
- return float(v)
-
-def to_long(self, v):
- try:
- if not unpack("q", pack("q", v))[0] == v:
- if isinstance(v, int_types):
- raise ValueError("Value out of range", v)
- raise TypeError('64-bit integer expected')
- except (struct_error,
- OverflowError, #PyPy
- ):
- if isinstance(v, int_types):
- raise ValueError("Value out of range", v)
- raise TypeError('64-bit integer expected')
-
- return int(v)
-
-def to_str(l):
- def to(self, v):
- if not (isinstance(v, str) and len(v) == l):
- raise TypeError("%s-character string expected" % l)
- return v
- return to
-
-tos = dict(I=to_int, L=to_long, F=to_float, O=to_ob)
-
-MERGE_DEFAULT_int = 1
-MERGE_DEFAULT_float = 1.0
-
-def MERGE(self, value1, weight1, value2, weight2):
- return (value1 * weight1) + (value2 * weight2)
-
-def MERGE_WEIGHT_default(self, value, weight):
- return value
-
-def MERGE_WEIGHT_numeric(self, value, weight):
- return value * weight
Copied: BTrees/branches/pure_python/BTrees/_base.py (from rev 128258, BTrees/branches/pure_python/BTrees/___BTree.py)
===================================================================
--- BTrees/branches/pure_python/BTrees/_base.py (rev 0)
+++ BTrees/branches/pure_python/BTrees/_base.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -0,0 +1,1150 @@
+##############################################################################
+#
+# Copyright 2011 Zope Foundation and Contributors.
+# All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+"""Python BTree implementation
+"""
+
+from struct import pack
+from struct import unpack
+from struct import error as struct_error
+
+import persistent
+
+from BTrees.Interfaces import BTreesConflictError
+
+_marker = object()
+
+
+class _Base(persistent.Persistent):
+
+ _key_type = list
+
+ def __init__(self, items=None):
+ self.clear()
+ if items:
+ self.update(items)
+
+
+class _BucketBase(_Base):
+
+ def clear(self):
+ self._keys = self._key_type()
+ self._next = None
+
+ def __len__(self):
+ return len(self._keys)
+
+ @property
+ def size(self):
+ return len(self._keys)
+
+ def _deleteNextBucket(self):
+ next = self._next
+ if next is not None:
+ self._next = next._next
+
+ def _search(self, key):
+ # Return non-negative index on success
+ # return -(insertion_index + 1) on fail
+ low = 0
+ keys = self._keys
+ high = len(keys)
+ while low < high:
+ i = (low + high) // 2
+ k = keys[i]
+ if k == key:
+ return i
+ if k < key:
+ low = i + 1
+ else:
+ high = i
+ return -1 - low
+
+ def minKey(self, key=_marker):
+ if key is _marker:
+ return self._keys[0]
+ key = self._to_key(key)
+ index = self._search(key)
+ if index >- 0:
+ return key
+ else:
+ index = -index - 1
+ if index < len(self._keys):
+ return self._keys[index]
+ else:
+ raise ValueError("no key satisfies the conditions")
+
+ def maxKey(self, key=_marker):
+ if key is _marker:
+ return self._keys[-1]
+ key = self._to_key(key)
+ index = self._search(key)
+ if index >= 0:
+ return key
+ else:
+ index = -index-1
+ if index:
+ return self._keys[index-1]
+ else:
+ raise ValueError("no key satisfies the conditions")
+
+ def _range(self, min=_marker, max=_marker,
+ excludemin=False, excludemax=False):
+ if min is _marker:
+ start = 0
+ if excludemin:
+ start = 1
+ else:
+ min = self._to_key(min)
+ start = self._search(min)
+ if start >= 0:
+ if excludemin:
+ start += 1
+ else:
+ start = -start - 1
+ if max is _marker:
+ end = len(self._keys)
+ if excludemax:
+ end -= 1
+ else:
+ max = self._to_key(max)
+ end = self._search(max)
+ if end >= 0:
+ if not excludemax:
+ end += 1
+ else:
+ end = -end - 1
+
+ return start, end
+
+ def keys(self, *args, **kw):
+ start, end = self._range(*args, **kw)
+ return self._keys[start:end]
+
+ def iterkeys(self, *args, **kw):
+ if not (args or kw):
+ return iter(self._keys)
+ keys = self._keys
+ return (keys[i] for i in xrange(*self._range(*args, **kw)))
+
+ def __iter__(self):
+ return iter(self._keys)
+
+ def has_key(self, key):
+ return (self._search(self._to_key(key)) >= 0) and 1
+
+ __contains__ = has_key
+
+ def _p_resolveConflict(self, *states):
+ set = not hasattr(self, '_values')
+
+ buckets = []
+ for state in states:
+ bucket = self.__class__()
+ if state:
+ bucket.__setstate__(state)
+ buckets.append(bucket)
+ if (buckets[1]._next != buckets[0]._next or
+ buckets[2]._next != buckets[0]._next):
+ raise BTreesConflictError(-1, -1, -1, 0)
+
+ if not (buckets[1] and buckets[2]):
+ raise BTreesConflictError(-1, -1, -1, 12)
+
+ i1 = _SetIteration(buckets[0], True)
+ i2 = _SetIteration(buckets[1], True)
+ i3 = _SetIteration(buckets[2], True)
+
+ def merge_error(reason):
+ return BTreesConflictError(
+ i1.position, i2.position, i3.position, reason)
+
+ result = self.__class__()
+
+ if set:
+ def merge_output(it):
+ result._keys.append(it.key)
+ it.advance()
+ else:
+ def merge_output(it):
+ result._keys.append(it.key)
+ result._values.append(it.value)
+ it.advance()
+
+ while i1.active and i2.active and i3.active:
+ cmp12 = cmp(i1.key, i2.key)
+ cmp13 = cmp(i1.key, i3.key)
+ if cmp12==0:
+ if cmp13==0:
+ if set:
+ result.add(i1.key)
+ elif i2.value == i1.value:
+ result[i1.key] = i3.value
+ elif i3.value == i1.value:
+ result[i1.key] = i2.value
+ else:
+ raise merge_error(1)
+ i1.advance()
+ i2.advance()
+ i3.advance()
+ elif (cmp13 > 0): # insert in new
+ merge_output(i3)
+ elif set or i1.value == i2.value: # deleted new
+ if i3.position == 1:
+ # Deleted the first item. This will modify the
+ # parent node, so we don't know if merging will be
+ # safe
+ raise merge_error(13)
+ i1.advance()
+ i2.advance()
+ else:
+ raise merge_error(2)
+ elif cmp13 == 0:
+ if cmp12 > 0: # insert committed
+ merge_output(i2)
+ elif set or i1.value == i3.value: # delete committed
+ if i2.position == 1:
+ # Deleted the first item. This will modify the
+ # parent node, so we don't know if merging will be
+ # safe
+ raise merge_error(13)
+ i1.advance()
+ i3.advance()
+ else:
+ raise merge_error(3)
+ else: # both keys changed
+ cmp23 = cmp(i2.key, i3.key)
+ if cmp23 == 0:
+ raise merge_error(4)
+ if cmp12 > 0: # insert committed
+ if cmp23 > 0: # insert i3 first
+ merge_output(i3)
+ else:
+ merge_output(i2)
+ elif cmp13 > 0: # insert i3
+ merge_output(i3)
+ else:
+ raise merge_error(5) # both deleted same key
+
+ while i2.active and i3.active: # new inserts
+ cmp23 = cmp(i2.key, i3.key)
+ if cmp23 == 0:
+ raise merge_error(6) # dueling insert
+ if cmp23 > 0: # insert new
+ merge_output(i3)
+ else: # insert committed
+ merge_output(i2)
+
+ while i1.active and i2.active: # new deletes rest of original
+ cmp12 = cmp(i1.key, i2.key)
+ if cmp12 > 0: # insert committed
+ merge_output(i2)
+ elif cmp12 == 0 and (set or i1.value == i2.value): # deleted in new
+ i1.advance()
+ i2.advance()
+ else: # dueling deletes or delete and change
+ raise merge_error(7)
+
+ while i1.active and i3.active: # committed deletes rest of original
+ cmp13 = cmp(i1.key, i3.key)
+ if cmp13 > 0: # insert new
+ merge_output(i3)
+ elif cmp13 == 0 and (set or i1.value == i3.value):
+ # deleted in committed
+ i1.advance()
+ i3.advance()
+ else: # dueling deletes or delete and change
+ raise merge_error(8)
+
+ if i1.active: # dueling deletes
+ raise merge_error(9)
+
+ while i2.active:
+ merge_output(i2)
+
+ while i3.active:
+ merge_output(i3)
+
+ if len(result._keys) == 0:
+ # If the output bucket is empty, conflict resolution doesn't have
+ # enough info to unlink it from its containing BTree correctly.
+ raise merge_error(10)
+
+ result._next = buckets[0]._next
+ return result.__getstate__()
+
+
+class _SetIteration(object):
+
+ def __init__(self, set, useValues=False, default=None):
+ if set is None:
+ set = ()
+ self.set = set
+ if useValues:
+ try:
+ itmeth = set.iteritems
+ except AttributeError:
+ itmeth = set.__iter__
+ useValues = False
+ else:
+ self.value = None
+ else:
+ itmeth = set.__iter__
+
+ self.useValues = useValues
+ self._next = itmeth().next
+ self.active = True
+ self.position = 0
+ self.value = default
+ self.advance()
+
+ def advance(self):
+ try:
+ if self.useValues:
+ self.key, self.value = self._next()
+ else:
+ self.key = self._next()
+ self.position += 1
+ except StopIteration:
+ self.active = False
+ self.position = -1
+
+ return self
+
+
+class _MappingBase(_Base):
+
+ def setdefault(self, key, value):
+ return self._set(self._to_key(key), self._to_value(value), True)[1]
+
+ def pop(self, key, default=_marker):
+ try:
+ return self._del(self._to_key(key))[1]
+ except KeyError:
+ if default is _marker:
+ raise
+ return default
+
+ def update(self, items):
+ if hasattr(items, 'iteritems'):
+ items = items.iteritems()
+ elif hasattr(items, 'items'):
+ items = items.items()
+
+ set = self.__setitem__
+ for i in items:
+ set(*i)
+
+ def __setitem__(self, key, value):
+ # Enforce test that key has non-default comparison.
+ if ( getattr(key, '__lt__', None) is None and
+ getattr(key, '__cmp__', None) is None):
+ raise TypeError("Can't use default __cmp__")
+ self._set(self._to_key(key), self._to_value(value))
+
+ def __delitem__(self, key):
+ self._del(self._to_key(key))
+
+
+class _SetBase(_Base):
+
+ def add(self, key):
+ return self._set(self._to_key(key))[0]
+
+ insert = add
+
+ def remove(self, key):
+ self._del(self._to_key(key))
+
+ def update(self, items):
+ add = self.add
+ for i in items:
+ add(i)
+
+
+class Bucket(_MappingBase, _BucketBase):
+
+ _value_type = list
+ _to_value = lambda x: x
+ VALUE_SAME_CHECK = False
+
+ def clear(self):
+ _BucketBase.clear(self)
+ self._values = self._value_type()
+
+ def get(self, key, default=None):
+ index = self._search(self._to_key(key))
+ if index < 0:
+ return default
+ return self._values[index]
+
+ def __getitem__(self, key):
+ index = self._search(self._to_key(key))
+ if index < 0:
+ raise KeyError(key)
+ return self._values[index]
+
+ def _set(self, key, value, ifunset=False):
+ """Set a value
+
+ Return: status, value
+
+ Status is:
+ None if no change
+ 0 if change, but not size change
+ 1 if change and size change
+ """
+ index = self._search(key)
+ if index >= 0:
+ if (ifunset or
+ self.VALUE_SAME_CHECK and value == self._values[index]
+ ):
+ return None, self._values[index]
+ self._p_changed = True
+ self._values[index] = value
+ return 0, value
+ else:
+ self._p_changed = True
+ index = -index - 1
+ self._keys.insert(index, key)
+ self._values.insert(index, value)
+ return 1, value
+
+ def _del(self, key):
+ index = self._search(key)
+ if index >= 0:
+ self._p_changed = True
+ del self._keys[index]
+ return 0, self._values.pop(index)
+ raise KeyError(key)
+
+ def _split(self, index=-1):
+ if index < 0 or index >= len(self._keys):
+ index = len(self._keys) / 2
+ new_instance = self.__class__()
+ new_instance._keys = self._keys[index:]
+ new_instance._values = self._values[index:]
+ del self._keys[index:]
+ del self._values[index:]
+ new_instance._next = self._next
+ self._next = new_instance
+ return new_instance
+
+ def values(self, *args, **kw):
+ start, end = self._range(*args, **kw)
+ return self._values[start:end]
+
+ def itervalues(self, *args, **kw):
+ values = self._values
+ return (values[i] for i in xrange(*self._range(*args, **kw)))
+
+ def items(self, *args, **kw):
+ keys = self._keys
+ values = self._values
+ return [(keys[i], values[i]) for i in xrange(*self._range(*args, **kw))]
+
+ def iteritems(self, *args, **kw):
+ keys = self._keys
+ values = self._values
+ return ((keys[i], values[i]) for i in xrange(*self._range(*args, **kw)))
+
+ def __getstate__(self):
+ keys = self._keys
+ values = self._values
+ data = []
+ for i in range(len(keys)):
+ data.append(keys[i])
+ data.append(values[i])
+ data = tuple(data)
+
+ if self._next:
+ return data, self._next
+ return (data, )
+
+ def __setstate__(self, state):
+ if not isinstance(state[0], tuple):
+ raise TypeError("tuple required for first state element")
+
+ self.clear()
+ if len(state) == 2:
+ state, self._next = state
+ else:
+ self._next = None
+ state = state[0]
+
+ keys = self._keys
+ values = self._values
+ for i in range(0, len(state), 2):
+ keys.append(state[i])
+ values.append(state[i+1])
+
+
+class Set(_SetBase, _BucketBase):
+
+ def __getstate__(self):
+ data = tuple(self._keys)
+ if self._next:
+ return data, self._next
+ return (data, )
+
+ def __setstate__(self, state):
+ if not isinstance(state[0], tuple):
+ raise TypeError('tuple required for first state element')
+
+ self.clear()
+ if len(state) == 2:
+ state, self._next = state
+ else:
+ self._next = None
+ state = state[0]
+
+ self._keys.extend(state)
+
+
+ def _set(self, key, value=None, ifunset=False):
+ index = self._search(key)
+ if index < 0:
+ index = -index - 1
+ self._keys.insert(index, key)
+ return True, None
+ return False, None
+
+ def _del(self, key):
+ index = self._search(key)
+ if index >= 0:
+ self._p_changed = True
+ del self._keys[index]
+ return 0, 0
+ raise KeyError(key)
+
+ def __getitem__(self, i):
+ return self._keys[i]
+
+ def _split(self, index=-1):
+ if index < 0 or index >= len(self._keys):
+ index = len(self._keys) / 2
+ new_instance = self.__class__()
+ new_instance._keys = self._keys[index:]
+ del self._keys[index:]
+ new_instance._next = self._next
+ self._next = new_instance
+ return new_instance
+
+
+class _TreeItem(object):
+
+ __slots__ = 'key', 'child'
+
+ def __init__(self, key, child):
+ self.key = key
+ self.child = child
+
+
+class _Tree(_MappingBase):
+
+ def clear(self):
+ self._data = []
+ self._firstbucket = None
+
+ def __nonzero__(self):
+ return bool(self._data)
+
+ def __len__(self):
+ l = 0
+ bucket = self._firstbucket
+ while bucket is not None:
+ l += len(bucket._keys)
+ bucket = bucket._next
+ return l
+
+ @property
+ def size(self):
+ return len(self._data)
+
+ def _search(self, key):
+ data = self._data
+ if data:
+ lo = 0
+ hi = len(data)
+ i = hi//2
+ while i > lo:
+ cmp_ = cmp(data[i].key, key)
+ if cmp_ < 0:
+ lo = i
+ elif cmp_ > 0:
+ hi = i
+ else:
+ break
+ i = (lo+hi)//2
+ return i
+ return -1
+
+ def _findbucket(self, key):
+ index = self._search(key)
+ if index >= 0:
+ child = self._data[index].child
+ if isinstance(child, self._bucket_type):
+ return child
+ return child._findbucket(key)
+
+ def __contains__(self, key):
+ return key in (self._findbucket(self._to_key(key)) or ())
+
+ def has_key(self, key):
+ index = self._search(key)
+ if index < 0:
+ return False
+ r = self._data[index].child.has_key(key)
+ return r and r + 1
+
+ def keys(self, min=_marker, max=_marker,
+ excludemin=False, excludemax=False,
+ itertype='iterkeys'):
+ if not self._data:
+ return ()
+
+ if min != _marker:
+ min = self._to_key(min)
+ bucket = self._findbucket(min)
+ else:
+ bucket = self._firstbucket
+
+ iterargs = min, max, excludemin, excludemax
+
+ return _TreeItems(bucket, itertype, iterargs)
+
+ def iterkeys(self, min=_marker, max=_marker,
+ excludemin=False, excludemax=False):
+ return iter(self.keys(min, max, excludemin, excludemax))
+
+ def __iter__(self):
+ return iter(self.keys())
+
+ def minKey(self, min=_marker):
+ if min is _marker:
+ bucket = self._firstbucket
+ else:
+ min = self._to_key(min)
+ bucket = self._findbucket(min)
+ if bucket is not None:
+ return bucket.minKey(min)
+ raise ValueError('empty tree')
+
+ def maxKey(self, max=_marker):
+ data = self._data
+ if not data:
+ raise ValueError('empty tree')
+ if max is _marker:
+ return data[-1].child.maxKey()
+
+ max = self._to_key(max)
+ index = self._search(max)
+ if index and data[index].child.minKey() > max:
+ index -= 1
+ return data[index].child.maxKey(max)
+
+
+ def _set(self, key, value=None, ifunset=False):
+ if (self._p_jar is not None and
+ self._p_oid is not None and
+ self._p_serial is not None):
+ self._p_jar.readCurrent(self)
+ data = self._data
+ if data:
+ index = self._search(key)
+ child = data[index].child
+ else:
+ index = 0
+ child = self._bucket_type()
+ self._firstbucket = child
+ data.append(_TreeItem(None, child))
+
+ result = child._set(key, value, ifunset)
+ grew = result[0]
+ if grew and child.size > child.MAX_SIZE:
+ self._grow(child, index)
+ elif (grew is not None and
+ child.__class__ is self._bucket_type and
+ len(data) == 1 and
+ child._p_oid is None
+ ):
+ self._p_changed = 1
+ return result
+
+ def _grow(self, child, index):
+ self._p_changed = True
+ new_child = child._split()
+ self._data.insert(index+1, _TreeItem(new_child.minKey(), new_child))
+ if len(self._data) > self.MAX_SIZE * 2:
+ self._split_root()
+
+ def _split_root(self):
+ child = self.__class__()
+ child._data = self._data
+ child._firstbucket = self._firstbucket
+ self._data = [_TreeItem(None, child)]
+ self._grow(child, 0)
+
+ def _split(self, index=None):
+ data = self._data
+ if index is None:
+ index = len(data)//2
+
+ next = self.__class__()
+ next._data = data[index:]
+ first = data[index]
+ del data[index:]
+ if isinstance(first.child, self.__class__):
+ next._firstbucket = first.child._firstbucket
+ else:
+ next._firstbucket = first.child;
+ return next
+
+ def _del(self, key):
+ if (self._p_jar is not None and
+ self._p_oid is not None and
+ self._p_serial is not None):
+ self._p_jar.readCurrent(self)
+ data = self._data
+ if data:
+ index = self._search(key)
+ child = data[index].child
+ else:
+ raise KeyError(key)
+
+ removed_first_bucket, value = child._del(key)
+
+ if index and child.size and key == data[index].key:
+ self._p_changed = True
+ data[index].key = child.minKey()
+
+ if removed_first_bucket:
+ if index:
+ data[index-1].child._deleteNextBucket()
+ removed_first_bucket = False # clear flag
+ else:
+ self._firstbucket = child._firstbucket
+
+ if not child.size:
+ if child.__class__ is self._bucket_type:
+ if index:
+ data[index-1].child._deleteNextBucket()
+ else:
+ self._firstbucket = child._next
+ removed_first_bucket = True
+ del data[index]
+
+ return removed_first_bucket, value
+
+ def _deleteNextBucket(self):
+ self._data[-1].child._deleteNextBucket()
+
+ def __getstate__(self):
+ data = self._data
+
+ if not data:
+ return None
+
+ if (len(data) == 1 and
+ data[0].child.__class__ is not self.__class__ and
+ data[0].child._p_oid is None
+ ):
+ return ((data[0].child.__getstate__(), ), )
+
+ sdata = []
+ for item in data:
+ if sdata:
+ sdata.append(item.key)
+ sdata.append(item.child)
+ else:
+ sdata.append(item.child)
+
+ return tuple(sdata), self._firstbucket
+
+ def __setstate__(self, state):
+ if state and not isinstance(state[0], tuple):
+ raise TypeError('tuple required for first state element')
+
+ self.clear()
+ if state is None:
+ return
+
+ if len(state) == 1:
+ bucket = self._bucket_type()
+ bucket.__setstate__(state[0][0])
+ state = [bucket], bucket
+
+ data, self._firstbucket = state
+ data = list(reversed(data))
+
+ self._data.append(_TreeItem(None, data.pop()))
+ while data:
+ key = data.pop()
+ child = data.pop()
+ self._data.append(_TreeItem(key, child))
+
+ def _assert(self, condition, message):
+ if not condition:
+ raise AssertionError(message)
+
+ def _check(self, nextbucket=None):
+ data = self._data
+ assert_ = self._assert
+ if not data:
+ assert_(self._firstbucket is None,
+ "Empty BTree has non-NULL firstbucket")
+ return
+ assert_(self._firstbucket is not None,
+ "Non-empty BTree has NULL firstbucket")
+
+ child_class = data[0].child.__class__
+ for i in data:
+ assert_(i.child is not None, "BTree has NULL child")
+ assert_(i.child.__class__ is child_class,
+ "BTree children have different types");
+ assert_(i.child.size, "Bucket length < 1")
+
+ if child_class is self.__class__:
+ assert_(self._firstbucket is data[0].child._firstbucket,
+ "BTree has firstbucket different than "
+ "its first child's firstbucket")
+ for i in range(len(data)-1):
+ data[i].child._check(data[i+1].child._firstbucket)
+ data[-1].child._check(nextbucket)
+ elif child_class is self._bucket_type:
+ assert_(self._firstbucket is data[0].child,
+ "Bottom-level BTree node has inconsistent firstbucket "
+ "belief")
+ for i in range(len(data)-1):
+ assert_(data[i].child._next is data[i+1].child,
+ "Bucket next pointer is damaged")
+ assert_(data[-1].child._next is nextbucket,
+ "Bucket next pointer is damaged")
+ else:
+ assert_(False, "Incorrect child type")
+
+ def _p_resolveConflict(self, *states):
+ states = map(_get_simple_btree_bucket_state, states)
+ return ((self._bucket_type()._p_resolveConflict(*states), ), )
+
+
+def _get_simple_btree_bucket_state(state):
+ if state is None:
+ return state
+
+ if not isinstance(state, tuple):
+ raise TypeError("_p_resolveConflict: expected tuple or None for state")
+ if len(state) == 2:
+ raise BTreesConflictError(-1, -1, -1, 11)
+
+ if len(state) != 1:
+ raise TypeError("_p_resolveConflict: expected 1- or 2-tuple for state")
+
+ state = state[0]
+ if not isinstance(state, tuple) or len(state) != 1:
+ raise TypeError("_p_resolveConflict: expected 1-tuple containing "
+ "bucket state");
+ state = state[0]
+ if not isinstance(state, tuple):
+ raise TypeError("_p_resolveConflict: expected tuple for bucket state")
+
+ return state
+
+
+class _TreeItems(object):
+
+ def __init__(self, firstbucket, itertype, iterargs):
+ self.firstbucket = firstbucket
+ self.itertype = itertype
+ self.iterargs = iterargs
+ self.index = -1
+ self.it = iter(self)
+
+ def __getitem__(self, i):
+ if isinstance(i, slice):
+ return list(self)[i]
+ if i < 0:
+ i = len(self) + i
+ if i < 0:
+ raise IndexError(i)
+
+ if i < self.index:
+ self.index = -1
+ self.it = iter(self)
+
+ while i > self.index:
+ try:
+ self.v = self.it.next()
+ except StopIteration:
+ raise IndexError(i)
+ else:
+ self.index += 1
+ return self.v
+
+ def __len__(self):
+ try:
+ return self._len
+ except AttributeError:
+ i = 0
+ for _ in self:
+ i += 1
+ self._len = i
+ return self._len
+
+ def __iter__(self):
+ bucket = self.firstbucket
+ itertype = self.itertype
+ iterargs = self.iterargs
+ done = 0
+ # Note that we don't mind if the first bucket yields no
+ # results due to an idiosyncrasy in how range searches are done.
+ while bucket is not None:
+ for k in getattr(bucket, itertype)(*iterargs):
+ yield k
+ done = 0
+ if done:
+ return
+ bucket = bucket._next
+ done = 1
+
+
+class Tree(_Tree):
+
+ def get(self, key, default=None):
+ bucket = self._findbucket(key)
+ if bucket:
+ return bucket.get(key, default)
+ return default
+
+ def __getitem__(self, key):
+ bucket = self._findbucket(key)
+ if bucket:
+ return bucket[key]
+ raise KeyError(key)
+
+ def values(self, min=_marker, max=_marker,
+ excludemin=False, excludemax=False):
+ return self.keys(min, max, excludemin, excludemax, 'itervalues')
+
+ def itervalues(self, min=_marker, max=_marker,
+ excludemin=False, excludemax=False):
+ return iter(self.values(min, max, excludemin, excludemax))
+
+ def items(self, min=_marker, max=_marker,
+ excludemin=False, excludemax=False):
+ return self.keys(min, max, excludemin, excludemax, 'iteritems')
+
+ def iteritems(self, min=_marker, max=_marker,
+ excludemin=False, excludemax=False):
+ return iter(self.items(min, max, excludemin, excludemax))
+
+ def byValue(self, min):
+ return sorted((v, k) for (k, v) in self.iteritems() if v >= min)
+
+ def insert(self, key, value):
+ return bool(self._set(key, value, True)[0])
+
+
+class TreeSet(_SetBase, _Tree):
+ pass
+
+
+def _set_operation(s1, s2,
+ usevalues1=False, usevalues2=False,
+ w1=1, w2=1,
+ c1=True, c12=True, c2=True):
+ MERGE_DEFAULT = getattr(s1, 'MERGE_DEFAULT', None)
+ i1 = _SetIteration(s1, usevalues1, MERGE_DEFAULT)
+ i2 = _SetIteration(s2, usevalues2, MERGE_DEFAULT)
+ merge = i1.useValues or i2.useValues
+ MERGE = getattr(s1, 'MERGE', None)
+ if merge:
+ MERGE_WEIGHT = getattr(s1, 'MERGE_WEIGHT')
+ if MERGE is None and c12 and i1.useValues and i2.useValues:
+ raise TypeError("invalid set operation")
+
+ if (not i1.useValues) and i2.useValues:
+ t = i1; i1 = i2; i2 = t
+ t = w1; w1 = w2; w2 = t
+ t = c1; c1 = c2; c2 = t
+
+ if MERGE_DEFAULT is None:
+ if i1.useValues:
+ if (not i2.useValues) and c2:
+ raise TypeError("invalid set operation")
+ else:
+ if c1 or c12:
+ raise TypeError("invalid set operation")
+
+ r = s1._mapping_type()
+
+ def copy(i, w):
+ r._keys.append(i.key)
+ r._values.append(MERGE_WEIGHT(i.value, w))
+ else:
+ r = s1._set_type()
+ def copy(i, w):
+ r._keys.append(i.key)
+
+ while i1.active and i2.active:
+ cmp_ = cmp(i1.key, i2.key)
+ if cmp_ < 0:
+ if c1:
+ copy(i1, w1)
+ i1.advance()
+ elif cmp_ == 0:
+ if c12:
+ r._keys.append(i1.key)
+ if merge:
+ r._values.append(MERGE(i1.value, w1, i2.value, w2))
+ i1.advance()
+ i2.advance()
+ else:
+ if c2:
+ copy(i2, w2)
+ i2.advance()
+
+ if c1:
+ while i1.active:
+ copy(i1, w1)
+ i1.advance()
+ if c2:
+ while i2.active:
+ copy(i2, w2)
+ i2.advance()
+
+ return r
+
+
+class setop(object):
+
+ def __init__(self, func, set_type):
+ self.func = func
+ self.set_type = set_type
+
+ def __call__(self, *a, **k):
+ return self.func(self.set_type, *a, **k)
+
+
+def difference(set_type, o1, o2):
+ if o1 is None or o2 is None:
+ return o1
+ return _set_operation(o1, o2, 1, 0, 1, 0, 1, 0, 0)
+
+def union(set_type, o1, o2):
+ if o1 is None:
+ return o2
+ if o2 is None:
+ return o1
+ return _set_operation(o1, o2, 0, 0, 1, 1, 1, 1, 1)
+
+def intersection(set_type, o1, o2):
+ if o1 is None:
+ return o2
+ if o2 is None:
+ return o1
+ return _set_operation(o1, o2, 0, 0, 1, 1, 0, 1, 0)
+
+def weightedUnion(set_type, o1, o2, w1=1, w2=1):
+ if o1 is None:
+ if o2 is None:
+ return 0, o2
+ else:
+ return w2, o2
+ elif o2 is None:
+ return w1, o1
+ else:
+ return 1, _set_operation(o1, o2, 1, 1, w1, w2, 1, 1, 1)
+
+def weightedIntersection(set_type, o1, o2, w1=1, w2=1):
+ if o1 is None:
+ if o2 is None:
+ return 0, o2
+ else:
+ return w2, o2
+ elif o2 is None:
+ return w1, o1
+ else:
+ result = _set_operation(o1, o2, 1, 1, w1, w2, 0, 1, 0)
+ return (w1 + w2 if isinstance(result, (Set, TreeSet)) else 1, result)
+
+def multiunion(set_type, seqs):
+ # XXX simple/slow implementation. Goal is just to get tests to pass.
+ if not seqs:
+ return set_type()
+ result = set_type()
+ for s in seqs:
+ try:
+ iter(s)
+ except TypeError:
+ s = set_type((s, ))
+ result.update(s)
+ return result
+
+def to_ob(self, v):
+ return v
+
+int_types = int, long
+def to_int(self, v):
+ try:
+ if not unpack("i", pack("i", v))[0] == v:
+ raise TypeError('32-bit integer expected')
+ except (struct_error,
+ OverflowError, #PyPy
+ ):
+ raise TypeError('32-bit integer expected')
+
+ return int(v)
+
+def to_float(self, v):
+ try:
+ pack("f", v)
+ except struct_error:
+ raise TypeError('float expected')
+ return float(v)
+
+def to_long(self, v):
+ try:
+ if not unpack("q", pack("q", v))[0] == v:
+ if isinstance(v, int_types):
+ raise ValueError("Value out of range", v)
+ raise TypeError('64-bit integer expected')
+ except (struct_error,
+ OverflowError, #PyPy
+ ):
+ if isinstance(v, int_types):
+ raise ValueError("Value out of range", v)
+ raise TypeError('64-bit integer expected')
+
+ return int(v)
+
+def to_str(l):
+ def to(self, v):
+ if not (isinstance(v, str) and len(v) == l):
+ raise TypeError("%s-character string expected" % l)
+ return v
+ return to
+
+tos = dict(I=to_int, L=to_long, F=to_float, O=to_ob)
+
+MERGE_DEFAULT_int = 1
+MERGE_DEFAULT_float = 1.0
+
+def MERGE(self, value1, weight1, value2, weight2):
+ return (value1 * weight1) + (value2 * weight2)
+
+def MERGE_WEIGHT_default(self, value, weight):
+ return value
+
+def MERGE_WEIGHT_numeric(self, value, weight):
+ return value * weight
Modified: BTrees/branches/pure_python/BTrees/fsBTree.py
===================================================================
--- BTrees/branches/pure_python/BTrees/fsBTree.py 2012-11-12 18:37:28 UTC (rev 128258)
+++ BTrees/branches/pure_python/BTrees/fsBTree.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -23,17 +23,17 @@
from zope.interface import moduleProvides
-from BTrees.Interfaces import IIntegerObjectBTreeModule
-from BTrees.___BTree import Bucket
-from BTrees.___BTree import Set
-from BTrees.___BTree import Tree as BTree
-from BTrees.___BTree import TreeSet
-from BTrees.___BTree import difference as _difference
-from BTrees.___BTree import intersection as _intersection
-from BTrees.___BTree import multiunion as _multiunion
-from BTrees.___BTree import setop as _setop
-from BTrees.___BTree import to_str as _to_str
-from BTrees.___BTree import union as _union
+from .Interfaces import IIntegerObjectBTreeModule
+from ._base import Bucket
+from ._base import Set
+from ._base import Tree as BTree
+from ._base import TreeSet
+from ._base import difference as _difference
+from ._base import intersection as _intersection
+from ._base import multiunion as _multiunion
+from ._base import setop as _setop
+from ._base import to_str as _to_str
+from ._base import union as _union
_BUCKET_SIZE = 500
_TREE_SIZE = 500
Copied: BTrees/branches/pure_python/BTrees/tests/test__base.py (from rev 128258, BTrees/branches/pure_python/BTrees/tests/test_base.py)
===================================================================
--- BTrees/branches/pure_python/BTrees/tests/test__base.py (rev 0)
+++ BTrees/branches/pure_python/BTrees/tests/test__base.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -0,0 +1,69 @@
+##############################################################################
+#
+# Copyright 2012 Zope Foundation and Contributors.
+# All Rights Reserved.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+import unittest
+
+
+
+class Test_BucketBase(unittest.TestCase):
+
+ def _getTargetClass(self):
+ from .._base import _BucketBase
+ return _BucketBase
+
+ def _makeOne(self, *args, **kw):
+ return self._getTargetClass()(*args, **kw)
+
+ def test_ctor_defaults(self):
+ bucket = self._makeOne()
+ self.assertEqual(bucket._keys, [])
+ self.assertEqual(bucket._next, None)
+ self.assertEqual(bucket.size, 0)
+
+ def test__deleteNextBucket_none(self):
+ bucket = self._makeOne()
+ bucket._deleteNextBucket() # no raise
+ self.assertTrue(bucket._next is None)
+
+ def test__deleteNextBucket_one(self):
+ bucket1 = self._makeOne()
+ bucket2 = bucket1._next = self._makeOne()
+ bucket1._deleteNextBucket() # no raise
+ self.assertTrue(bucket1._next is None)
+
+ def test__deleteNextBucket_two(self):
+ bucket1 = self._makeOne()
+ bucket2 = bucket1._next = self._makeOne()
+ bucket3 = bucket2._next = self._makeOne()
+ bucket1._deleteNextBucket() # no raise
+ self.assertTrue(bucket1._next is bucket3)
+
+ def test__search_empty(self):
+ bucket = self._makeOne()
+ self.assertEqual(bucket._search('nonesuch'), -1)
+
+ def test__search_nonempty_miss(self):
+ bucket = self._makeOne()
+ bucket._keys = ['alpha', 'bravo', 'charlie', 'delta', 'echo']
+ self.assertEqual(bucket._search('candy'), -3)
+
+ def test__search_nonempty_hit(self):
+ bucket = self._makeOne()
+ bucket._keys = ['alpha', 'bravo', 'charlie', 'delta', 'echo']
+ self.assertEqual(bucket._search('charlie'), 2)
+
+
+def test_suite():
+ return unittest.TestSuite((
+ unittest.makeSuite(Test_BucketBase),
+ ))
Deleted: BTrees/branches/pure_python/BTrees/tests/test_base.py
===================================================================
--- BTrees/branches/pure_python/BTrees/tests/test_base.py 2012-11-12 18:37:28 UTC (rev 128258)
+++ BTrees/branches/pure_python/BTrees/tests/test_base.py 2012-11-12 18:37:29 UTC (rev 128259)
@@ -1,69 +0,0 @@
-##############################################################################
-#
-# Copyright 2012 Zope Foundation and Contributors.
-# All Rights Reserved.
-#
-# This software is subject to the provisions of the Zope Public License,
-# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
-# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
-# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
-# FOR A PARTICULAR PURPOSE.
-#
-##############################################################################
-import unittest
-
-
-
-class Test_BucketBase(unittest.TestCase):
-
- def _getTargetClass(self):
- from BTrees.___BTree import _BucketBase
- return _BucketBase
-
- def _makeOne(self, *args, **kw):
- return self._getTargetClass()(*args, **kw)
-
- def test_ctor_defaults(self):
- bucket = self._makeOne()
- self.assertEqual(bucket._keys, [])
- self.assertEqual(bucket._next, None)
- self.assertEqual(bucket.size, 0)
-
- def test__deleteNextBucket_none(self):
- bucket = self._makeOne()
- bucket._deleteNextBucket() # no raise
- self.assertTrue(bucket._next is None)
-
- def test__deleteNextBucket_one(self):
- bucket1 = self._makeOne()
- bucket2 = bucket1._next = self._makeOne()
- bucket1._deleteNextBucket() # no raise
- self.assertTrue(bucket1._next is None)
-
- def test__deleteNextBucket_two(self):
- bucket1 = self._makeOne()
- bucket2 = bucket1._next = self._makeOne()
- bucket3 = bucket2._next = self._makeOne()
- bucket1._deleteNextBucket() # no raise
- self.assertTrue(bucket1._next is bucket3)
-
- def test__search_empty(self):
- bucket = self._makeOne()
- self.assertEqual(bucket._search('nonesuch'), -1)
-
- def test__search_nonempty_miss(self):
- bucket = self._makeOne()
- bucket._keys = ['alpha', 'bravo', 'charlie', 'delta', 'echo']
- self.assertEqual(bucket._search('candy'), -3)
-
- def test__search_nonempty_hit(self):
- bucket = self._makeOne()
- bucket._keys = ['alpha', 'bravo', 'charlie', 'delta', 'echo']
- self.assertEqual(bucket._search('charlie'), 2)
-
-
-def test_suite():
- return unittest.TestSuite((
- unittest.makeSuite(Test_BucketBase),
- ))
More information about the checkins
mailing list