[Checkins] SVN: zope.bforest/trunk/ add BTree-like features like
minKey, maxKey, and arguments to itervalues, iterkeys,
and iteritems. Wake up buckets more gradually for the iter[...]
methods. prepare for 1.2
Gary Poster
gary at zope.com
Thu May 8 23:04:42 EDT 2008
Log message for revision 86553:
add BTree-like features like minKey, maxKey, and arguments to itervalues, iterkeys, and iteritems. Wake up buckets more gradually for the iter[...] methods. prepare for 1.2
Changed:
_U zope.bforest/trunk/
U zope.bforest/trunk/CHANGES.txt
U zope.bforest/trunk/buildout.cfg
U zope.bforest/trunk/setup.py
U zope.bforest/trunk/src/zope/bforest/bforest.py
U zope.bforest/trunk/src/zope/bforest/bforest.txt
U zope.bforest/trunk/src/zope/bforest/periodic.py
U zope.bforest/trunk/src/zope/bforest/periodic.txt
-=-
Property changes on: zope.bforest/trunk
___________________________________________________________________
Name: svn:ignore
- develop-eggs
bin
parts
.installed.cfg
build
dist
+ develop-eggs
bin
parts
.installed.cfg
build
dist
TEST_THIS_REST_BEFORE_REGISTERING.txt
*.kpf
Modified: zope.bforest/trunk/CHANGES.txt
===================================================================
--- zope.bforest/trunk/CHANGES.txt 2008-05-09 02:57:06 UTC (rev 86552)
+++ zope.bforest/trunk/CHANGES.txt 2008-05-09 03:04:42 UTC (rev 86553)
@@ -2,6 +2,28 @@
CHANGES
=======
+1.2 (2008-05-09)
+----------------
+
+Bugfixes:
+
+- added omitted __ne__ implementation.
+
+Features:
+
+- added minKey, maxKey, like BTrees.
+
+- gave itervalues, iteritems, and iterkeys same extra arguments as BTrees'
+ values, items, and keys: min, max, excludemin, excludemax.
+
+- changed implementation of iter[...] functions to try to only wake up buckets
+ as needed.
+
+Incompatible Changes:
+
+- changed definition of __eq__: now compares contents *and* order. Tries to
+ only wake up buckets as needed.
+
1.1.1 (2008-04-09)
------------------
Modified: zope.bforest/trunk/buildout.cfg
===================================================================
--- zope.bforest/trunk/buildout.cfg 2008-05-09 02:57:06 UTC (rev 86552)
+++ zope.bforest/trunk/buildout.cfg 2008-05-09 03:04:42 UTC (rev 86553)
@@ -7,6 +7,8 @@
[test]
recipe = zc.recipe.testrunner
eggs = zope.bforest
+defaults = '--tests-pattern ^[fn]?tests --exit-with-status -1'.split()
+working-directory = ${buildout:directory}
[py]
recipe = zc.recipe.egg
Modified: zope.bforest/trunk/setup.py
===================================================================
--- zope.bforest/trunk/setup.py 2008-05-09 02:57:06 UTC (rev 86552)
+++ zope.bforest/trunk/setup.py 2008-05-09 03:04:42 UTC (rev 86553)
@@ -1,15 +1,85 @@
-from setuptools import setup
+##############################################################################
+#
+# Copyright (c) 2006-2008 Zope Corporation 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 os
+from setuptools import setup, find_packages
+# generic helpers primarily for the long_description
+try:
+ import docutils
+except ImportError:
+ import warnings
+ def validateReST(text):
+ return ''
+else:
+ import docutils.utils
+ import docutils.parsers.rst
+ import StringIO
+ def validateReST(text):
+ doc = docutils.utils.new_document('validator')
+ # our desired settings
+ doc.reporter.halt_level = 5
+ doc.reporter.report_level = 1
+ stream = doc.reporter.stream = StringIO.StringIO()
+ # docutils buglets (?)
+ doc.settings.tab_width = 2
+ doc.settings.pep_references = doc.settings.rfc_references = False
+ doc.settings.trim_footnote_reference_space = None
+ # and we're off...
+ parser = docutils.parsers.rst.Parser()
+ parser.parse(text, doc)
+ return stream.getvalue()
+
+def text(*args, **kwargs):
+ # note: distutils explicitly disallows unicode for setup values :-/
+ # http://docs.python.org/dist/meta-data.html
+ tmp = []
+ for a in args:
+ if a.endswith('.txt'):
+ f = open(os.path.join(*a.split('/')))
+ tmp.append(f.read())
+ f.close()
+ tmp.append('\n\n')
+ else:
+ tmp.append(a)
+ if len(tmp) == 1:
+ res = tmp[0]
+ else:
+ res = ''.join(tmp)
+ out = kwargs.get('out')
+ if out is True:
+ out = 'TEST_THIS_REST_BEFORE_REGISTERING.txt'
+ if out:
+ f = open(out, 'w')
+ f.write(res)
+ f.close()
+ report = validateReST(res)
+ if report:
+ print report
+ raise ValueError('ReST validation error')
+ return res
+# end helpers; below this line should be code custom to this package
+
setup(
name="zope.bforest",
- version="1.1.1",
+ version="1.2",
license="ZPL 2.1",
- author="Zope Project",
- author_email="zope3-dev at zope.org",
+ author='Gary Poster',
+ author_email='gary at zope.com',
namespace_packages=["zope"],
- packages=["zope", "zope.bforest"],
- package_dir={"": "src"},
+ packages=find_packages('src'),
+ package_dir={'':'src'},
include_package_data=True,
install_requires=[
"zope.interface",
@@ -18,7 +88,11 @@
],
tests_require=["zope.testing"],
description=open('README.txt').read(),
- long_description=open("src/zope/bforest/bforest.txt").read(),
+ long_description=text(
+ "src/zope/bforest/bforest.txt",
+ "\n\n",
+ 'CHANGES.txt',
+ out=True),
keywords="zope zope3",
zip_safe=False
)
Modified: zope.bforest/trunk/src/zope/bforest/bforest.py
===================================================================
--- zope.bforest/trunk/src/zope/bforest/bforest.py 2008-05-09 02:57:06 UTC (rev 86552)
+++ zope.bforest/trunk/src/zope/bforest/bforest.py 2008-05-09 03:04:42 UTC (rev 86553)
@@ -11,8 +11,6 @@
#
##############################################################################
"""objects with dict API comprised of multiple btrees.
-
-$Id: bforest.py 33325 2005-07-15 01:09:43Z poster $
"""
import persistent
@@ -64,6 +62,7 @@
def __delitem__(self, key):
found = False
for b in self.buckets:
+ # we delete all, in case one bucket is masking an old value
try:
del b[key]
except KeyError:
@@ -77,11 +76,13 @@
self.buckets[0].update(d)
def keys(self):
- union = self._treemodule.union
buckets = self.buckets
if len(buckets) == 1:
res = buckets[0].keys()
- else: # TODO: use multiunion for I* flavors
+ elif getattr(self._treemodule, 'multiunion', None) is not None:
+ return self._treemodule.multiunion(buckets)
+ else:
+ union = self._treemodule.union
res = union(buckets[0], buckets[1])
for b in buckets[2:]:
res = union(res, b)
@@ -100,40 +101,110 @@
def values(self):
return self.tree().values()
+
+ def maxKey(self, key=None):
+ res = m = self._marker
+ if key is None:
+ args = ()
+ else:
+ args = (key,)
+ for b in self.buckets:
+ try:
+ v = b.maxKey(*args)
+ except ValueError:
+ pass
+ else:
+ if res is m or v > res:
+ res = v
+ if res is m:
+ raise ValueError('no key')
+ return res
+
+ def minKey(self, key=None):
+ res = m = self._marker
+ if key is None:
+ args = ()
+ else:
+ args = (key,)
+ for b in self.buckets:
+ try:
+ v = b.minKey(*args)
+ except ValueError:
+ pass
+ else:
+ if res is m or v < res:
+ res = v
+ if res is m:
+ raise ValueError('no key')
+ return res
+
+ def iteritems(self, min=None, max=None, excludemin=False, excludemax=False):
+ # this approach might be slower than simply iterating over self.keys(),
+ # but it has a chance of waking up fewer objects in the ZODB, if the
+ # iteration stops early.
+ sources = []
+ for b in self.buckets:
+ i = iter(b.items(min, max, excludemin, excludemax))
+ try:
+ first = i.next()
+ except StopIteration:
+ pass
+ else:
+ sources.append([first, i])
+ scratch = self._treemodule.Bucket()
+ while sources:
+ for ((k, v), i) in sources:
+ scratch.setdefault(k, v)
+ k = scratch.minKey()
+ yield k, scratch[k]
+ for i in range(len(sources)-1, -1, -1):
+ source = sources[i]
+ if source[0][0] == k:
+ try:
+ source[0] = source[1].next()
+ except StopIteration:
+ del sources[i]
+ scratch.clear()
- def iteritems(self):
- for key in self.keys():
- yield key, self[key]
+ def iterkeys(self,
+ min=None, max=None, excludemin=False, excludemax=False):
+ return (k for k, v in self.iteritems(min, max, excludemin, excludemax))
- def iterkeys(self):
- return iter(self.keys())
-
__iter__ = iterkeys
- def itervalues(self):
- for key in self.keys():
- yield self[key]
+ def itervalues(self,
+ min=None, max=None, excludemin=False, excludemax=False):
+ return (v for k, v in self.iteritems(min, max, excludemin, excludemax))
- def has_key(self, key):
- try:
- self[key]
- except KeyError:
+ def __eq__(self, other):
+ # we will declare contents and its ordering to define equality. More
+ # restrictive definitions can be wrapped around this one.
+ if getattr(other, 'iteritems', None) is None:
return False
- else:
- return True
-
- def __eq__(self, other):
- if not isinstance(other, dict):
- if (isinstance(other, AbstractBForest) and
- self._treemodule is not other._treemodule):
+ si = self.iteritems()
+ so = other.iteritems()
+ while 1:
+ try:
+ k, v = si.next()
+ except StopIteration:
+ try:
+ so.next()
+ except StopIteration:
+ return True
return False
try:
- other = dict(other)
- except (TypeError, ValueError):
+ ok, ov = so.next()
+ except StopIteration:
return False
- return dict(self)==other # :-/
-
+ else:
+ if ok != k or ov != v:
+ return False
+
+ def __ne__(self, other):
+ return not self.__eq__(other)
+
def __gt__(self, other):
+ # TODO blech, change this
if not isinstance(other, dict):
try:
other = dict(other)
@@ -142,6 +213,7 @@
return dict(self) > other
def __lt__(self, other):
+ # TODO blech, change this
if not isinstance(other, dict):
try:
other = dict(other)
@@ -150,6 +222,7 @@
return dict(self) < other
def __ge__(self, other):
+ # TODO blech, change this
if not isinstance(other, dict):
try:
other = dict(other)
@@ -158,6 +231,7 @@
return dict(self) >= other
def __le__(self, other):
+ # TODO blech, change this
if not isinstance(other, dict):
try:
other = dict(other)
@@ -166,6 +240,15 @@
return dict(self) <= other
def __len__(self):
+ # keeping track of a separate length is currently considered to be
+ # somewhat expensive per write and not necessarily always valuable
+ # (that is, we don't always care what the length is). Therefore, we
+ # have this quite expensive default approach. If you need a len often
+ # and cheaply then you'll need to wrap the BForest and keep track of it
+ # yourself. This is expensive both because it wakes up every BTree and
+ # bucket in the BForest, which might be quite a few objects; and
+ # because of the merge necessary to create the composite tree (which
+ # eliminates duplicates from the count).
return len(self.tree())
def setdefault(self, key, failobj=None):
@@ -188,24 +271,18 @@
return res
def popitem(self):
- for b in self.buckets:
- try:
- key = b.minKey()
- except ValueError:
- pass
- else:
- val = b[key]
- del b[key]
- return key, val
- else:
- raise KeyError('popitem():dictionary is empty')
-
+ key = self.minKey()
+ val = self.pop(key)
+ return key, val
+
def __contains__(self, key):
for b in self.buckets:
if b.has_key(key):
return True
return False
-
+
+ has_key = __contains__
+
def copy(self):
# this makes an exact copy, including the individual state of each
# bucket. If you want a dict, cast it to a dict, or if you want
Modified: zope.bforest/trunk/src/zope/bforest/bforest.txt
===================================================================
--- zope.bforest/trunk/src/zope/bforest/bforest.txt 2008-05-09 02:57:06 UTC (rev 86552)
+++ zope.bforest/trunk/src/zope/bforest/bforest.txt 2008-05-09 03:04:42 UTC (rev 86553)
@@ -31,39 +31,29 @@
>>> d.get(dummy_key, 42)
42
-Now we'll populate it. We'll first create a dictionary we'll use to compare.
+Now we'll populate it. We'll first create a BTree we'll use to compare.
- >>> original = {}
+ >>> original = BForest._treemodule.BTree()
>>> for i in range(10):
... original[KeyGenerator()] = ValueGenerator()
...
>>> d.update(original)
>>> d == original
True
- >>> d_keys = list(d.keys())
- >>> d_keys.sort()
- >>> o_keys = original.keys()
- >>> o_keys.sort()
- >>> d_keys == o_keys
+ >>> list(d) == list(original)
True
- >>> d_values = list(d.values())
- >>> d_values.sort()
- >>> o_values = original.values()
- >>> o_values.sort()
- >>> o_values == d_values
+ >>> list(d.keys()) == list(original.keys())
True
- >>> d_items = list(d.items())
- >>> d_items.sort()
- >>> o_items = original.items()
- >>> o_items.sort()
- >>> o_items == d_items
+ >>> list(d.values()) == list(original.values())
True
- >>> key, value = d.popitem()
- >>> value == original.pop(key)
+ >>> list(d.items()) == list(original.items())
True
- >>> key, value = original.popitem()
- >>> value == d.pop(key)
+ >>> original_min = original.minKey()
+ >>> d.popitem() == (original_min, original.pop(original_min))
True
+ >>> original_min = original.minKey()
+ >>> d.pop(original_min) == original.pop(original_min)
+ True
>>> len(d) == len(original)
True
@@ -75,37 +65,27 @@
>>> d == original
True
- >>> d_keys = list(d.keys())
- >>> d_keys.sort()
- >>> o_keys = original.keys()
- >>> o_keys.sort()
- >>> d_keys == o_keys
+ >>> list(d) == list(original)
True
- >>> d_values = list(d.values())
- >>> d_values.sort()
- >>> o_values = original.values()
- >>> o_values.sort()
- >>> o_values == d_values
+ >>> list(d.keys()) == list(original.keys())
True
- >>> d_items = list(d.items())
- >>> d_items.sort()
- >>> o_items = original.items()
- >>> o_items.sort()
- >>> o_items == d_items
+ >>> list(d.values()) == list(original.values())
True
- >>> key, value = d.popitem()
- >>> value == original.pop(key)
+ >>> list(d.items()) == list(original.items())
True
- >>> key, value = original.popitem()
- >>> value == d.pop(key)
+ >>> original_min = original.minKey()
+ >>> d.popitem() == (original_min, original.pop(original_min))
True
+ >>> original_min = original.minKey()
+ >>> d.pop(original_min) == original.pop(original_min)
+ True
>>> len(d) == len(original)
True
Now we'll make a new dictionary to represent changes made after the bucket
rotation.
- >>> second = {}
+ >>> second = BForest._treemodule.BTree()
>>> for i in range(10):
... key = KeyGenerator()
... value = ValueGenerator()
@@ -114,39 +94,87 @@
...
>>> original.update(second)
-...and we'll do almost the exact same test as above, first.
+...and we'll do the exact same test as above, first.
>>> d == original
True
- >>> d_keys = list(d.keys())
- >>> d_keys.sort()
- >>> o_keys = original.keys()
- >>> o_keys.sort()
- >>> d_keys == o_keys
+ >>> list(d) == list(original)
True
- >>> d_values = list(d.values())
- >>> d_values.sort()
- >>> o_values = original.values()
- >>> o_values.sort()
- >>> o_values == d_values
+ >>> list(d.keys()) == list(original.keys())
True
- >>> d_items = list(d.items())
- >>> d_items.sort()
- >>> o_items = original.items()
- >>> o_items.sort()
- >>> o_items == d_items
+ >>> list(d.values()) == list(original.values())
True
- >>> key, value = d.popitem()
- >>> ignore = second.pop(key, None) # keep second up-to-date
- >>> value == original.pop(key)
+ >>> list(d.items()) == list(original.items())
True
- >>> key, value = original.popitem()
- >>> ignore = second.pop(key, None) # keep second up-to-date
- >>> value == d.pop(key)
+ >>> original_min = original.minKey()
+ >>> d.popitem() == (original_min, original.pop(original_min))
True
+ >>> if original_min in second:
+ ... _ = second.pop(original_min)
+ >>> original_min = original.minKey()
+ >>> d.pop(original_min) == original.pop(original_min)
+ True
+ >>> if original_min in second:
+ ... _ = second.pop(original_min)
>>> len(d) == len(original)
True
+The bforest offers ``itervalues``, ``iterkeys``, and ``iteritems`` that have
+the same extended arguments as BTrees' ``values``, ``keys``, and ``items``.
+
+ >>> list(d.itervalues()) == list(original.values())
+ True
+ >>> list(d.iteritems()) == list(original.items())
+ True
+ >>> list(d.iterkeys()) == list(original.keys())
+ True
+
+ >>> keys = list(original)
+ >>> mid = keys[len(keys)//2]
+ >>> list(d.itervalues(min=mid)) == list(original.itervalues(min=mid))
+ True
+ >>> list(d.itervalues(max=mid)) == list(original.itervalues(max=mid))
+ True
+ >>> list(d.itervalues(min=mid, excludemin=True)) == list(
+ ... original.itervalues(min=mid, excludemin=True))
+ True
+ >>> list(d.itervalues(max=mid, excludemax=True)) == list(
+ ... original.itervalues(max=mid, excludemax=True))
+ True
+
+ >>> list(d.iterkeys(min=mid)) == list(original.iterkeys(min=mid))
+ True
+ >>> list(d.iterkeys(max=mid)) == list(original.iterkeys(max=mid))
+ True
+ >>> list(d.iterkeys(min=mid, excludemin=True)) == list(
+ ... original.iterkeys(min=mid, excludemin=True))
+ True
+ >>> list(d.iterkeys(max=mid, excludemax=True)) == list(
+ ... original.iterkeys(max=mid, excludemax=True))
+ True
+
+ >>> list(d.iteritems(min=mid)) == list(original.iteritems(min=mid))
+ True
+ >>> list(d.iteritems(max=mid)) == list(original.iteritems(max=mid))
+ True
+ >>> list(d.iteritems(min=mid, excludemin=True)) == list(
+ ... original.iteritems(min=mid, excludemin=True))
+ True
+ >>> list(d.iteritems(max=mid, excludemax=True)) == list(
+ ... original.iteritems(max=mid, excludemax=True))
+ True
+
+It also offers maxKey and minKey, like BTrees.
+
+ >>> d.maxKey() == original.maxKey()
+ True
+ >>> d.minKey() == original.minKey()
+ True
+ >>> d.maxKey(mid) == original.maxKey(mid)
+ True
+ >>> d.minKey(mid) == original.minKey(mid)
+ True
+
Now if we rotate the buckets, the first set of items will be gone, but the
second will remain.
@@ -158,7 +186,7 @@
Let's set a value, check the copy behavior, and then rotate it one more time.
- >>> third = {KeyGenerator(): ValueGenerator()}
+ >>> third = BForest._treemodule.BTree({KeyGenerator(): ValueGenerator()})
>>> d.update(third)
>>> copy = d.copy()
>>> copy == d
@@ -192,8 +220,8 @@
>>> second == d
True
-The tree method converts the bforest to a btree as efficiently as I know how
-for a common case of more items in buckets than buckets.
+The tree method converts the bforest to a btree efficiently for a common case
+of more items in buckets than buckets.
>>> tree = d.tree()
>>> d_items = list(d.items())
@@ -233,7 +261,9 @@
False
>>> d > dict(second)
False
- >>> second.popitem()[0] in d
+ >>> original_min = second.minKey()
+ >>> del second[original_min]
+ >>> original_min in d
True
>>> d > second
True
Modified: zope.bforest/trunk/src/zope/bforest/periodic.py
===================================================================
--- zope.bforest/trunk/src/zope/bforest/periodic.py 2008-05-09 02:57:06 UTC (rev 86552)
+++ zope.bforest/trunk/src/zope/bforest/periodic.py 2008-05-09 03:04:42 UTC (rev 86553)
@@ -1,3 +1,16 @@
+##############################################################################
+#
+# Copyright (c) 2006-2008 Zope Corporation 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 datetime
import BTrees
import zope.bforest.bforest
Modified: zope.bforest/trunk/src/zope/bforest/periodic.txt
===================================================================
--- zope.bforest/trunk/src/zope/bforest/periodic.txt 2008-05-09 02:57:06 UTC (rev 86552)
+++ zope.bforest/trunk/src/zope/bforest/periodic.txt 2008-05-09 03:04:42 UTC (rev 86553)
@@ -36,7 +36,7 @@
>>> setNow(datetime.datetime.now(utils.UTC) + datetime.timedelta(hours=1))
>>> third_hour = {KeyGenerator(): ValueGenerator()}
>>> d.update(third_hour)
- >>> current = first_hour.copy()
+ >>> current = BForest._treemodule.BTree(first_hour.copy())
>>> current.update(fifty_minutes_in_to_first_hour)
>>> current.update(second_hour)
>>> current.update(third_hour)
@@ -89,7 +89,7 @@
True
>>> setNow(datetime.datetime.now(utils.UTC) + datetime.timedelta(hours=1))
>>> del d[sixth_hour.keys()[0]] # __delitem__
- >>> current = fourth_hour.copy()
+ >>> current = BForest._treemodule.BTree(fourth_hour.copy())
>>> current.update(fifth_hour)
>>> d == current
True
@@ -98,7 +98,7 @@
>>> setNow(datetime.datetime.now(utils.UTC) + datetime.timedelta(hours=1))
>>> d.pop(seventh_hour.keys()[0]) == seventh_hour.values()[0] # pop
True
- >>> d == fifth_hour
+ >>> d == BForest._treemodule.BTree(fifth_hour)
True
>>> eighth_hour = {KeyGenerator(): ValueGenerator()}
>>> d[eighth_hour.keys()[0]] = eighth_hour.values()[0]
@@ -109,8 +109,8 @@
>>> d[tenth_hour.keys()[0]] = tenth_hour.values()[0]
>>> setNow(datetime.datetime.now(utils.UTC) + datetime.timedelta(hours=1))
>>> out = dict((d.popitem(),))
- >>> out == tenth_hour
+ >>> d == BForest._treemodule.BTree(tenth_hour)
True
- >>> d == eighth_hour
+ >>> out == eighth_hour
True
More information about the Checkins
mailing list