[Checkins] SVN: zc.dict/trunk/src/zc/dict/ make ordered dict tests
mirror normal dict tests. add support for old location of
ordered dict.
Gary Poster
gary at zope.com
Wed Mar 5 17:17:48 EST 2008
Log message for revision 84483:
make ordered dict tests mirror normal dict tests. add support for old location of ordered dict.
Changed:
U zc.dict/trunk/src/zc/dict/dict.py
A zc.dict/trunk/src/zc/dict/ordered.py
U zc.dict/trunk/src/zc/dict/ordered.txt
-=-
Modified: zc.dict/trunk/src/zc/dict/dict.py
===================================================================
--- zc.dict/trunk/src/zc/dict/dict.py 2008-03-05 19:09:14 UTC (rev 84482)
+++ zc.dict/trunk/src/zc/dict/dict.py 2008-03-05 22:17:47 UTC (rev 84483)
@@ -126,7 +126,6 @@
del self[k]
return (k, v)
-
class OrderedDict(Dict):
"""A Ordered BTree-based dict-like persistent object that can be safely
inherited from.
@@ -173,7 +172,7 @@
order_set = set(order)
if len(order) != len(order_set):
- raise ValueError("Duplicate keys in order")
+ raise ValueError("Duplicate keys in order.")
if order_set.difference(self._order):
raise ValueError("Incompatible key set.")
Added: zc.dict/trunk/src/zc/dict/ordered.py
===================================================================
--- zc.dict/trunk/src/zc/dict/ordered.py (rev 0)
+++ zc.dict/trunk/src/zc/dict/ordered.py 2008-03-05 22:17:47 UTC (rev 84483)
@@ -0,0 +1,4 @@
+# re-export for backwards database compatibility. This support may be removed
+# for a future release.
+
+from zc.dict import OrderedDict
Modified: zc.dict/trunk/src/zc/dict/ordered.txt
===================================================================
--- zc.dict/trunk/src/zc/dict/ordered.txt 2008-03-05 19:09:14 UTC (rev 84482)
+++ zc.dict/trunk/src/zc/dict/ordered.txt 2008-03-05 22:17:47 UTC (rev 84483)
@@ -6,97 +6,237 @@
It also provides the API to reorder the items.
Importantly, the OrderedDict currently uses a PersistentList to store
-the order, which does not have good behavior for large sets, because the
-entire collection of keys must be pickled every time any key, or
-ordering, changes. A BList would be a preferred data structure, but
-that has not yet been released.
+the order, which does not have good behavior for large collections,
+because the entire collection of keys must be pickled every time any
+key, or ordering, changes. A BList would be a preferred data structure,
+but that has not yet been released.
- >>> from zc.dict import OrderedDict
- >>> d = OrderedDict()
- >>> d
- <zc.dict.dict.OrderedDict object at ...>
+ >>> from zc.dict import OrderedDict
+ >>> d = OrderedDict()
+ >>> d
+ <zc.dict.dict.OrderedDict object at ...>
+
+ >>> d['foo'] = 'bar'
+ >>> len(d)
+ 1
+
+ >>> d['bar'] = 'baz'
+ >>> len(d)
+ 2
-Let us add a couple of items
+ >>> d['foo']
+ 'bar'
+ >>> d['bar']
+ 'baz'
- >>> d['one'] = 'One'
- >>> len(d)
- 1
+The keys are currently in the order added.
- >>> d['two'] = 'Two'
- >>> len(d)
- 2
+ >>> list(d)
+ ['foo', 'bar']
- >>> d.keys()
- ['one', 'two']
+Note that an important difference between the Python dict and the
+OrderedDict is that the Python dict uses hashes, and this uses BTree
+comparisons. Practically, this means that your keys should be of
+homogenous types. We use strings in these examples.
- >>> d.values()
- ['One', 'Two']
+Length is maintained separately, because len on a BTree is inefficient,
+as it has to wake up all buckets in the tree from the database.
-The order can be changed easily
+ >>> d._len
+ <BTrees.Length.Length object at ...>
+ >>> d._len()
+ 2
- >>> d.updateOrder(['two', 'one'])
- >>> d.keys()
- ['two', 'one']
+In order to keep updates efficient for small changes, we unroll them
+as a series of setitems.
- >>> d.values()
- ['Two', 'One']
+ >>> d.update({'bar': 'moo', 'ding': 'dong', 'beep': 'beep'})
+ >>> len(d)
+ 4
+Note that the result of an update of multiple new items in a data
+structure without order will add the new items to the end of the ordered
+dict in an undefined order. To set our order, we need to introduce a new
+method: ``updateOrder``. This method is a heavy-handed approach to changing
+the order: supply a new one.
+ >>> list(d) == ['bar', 'beep', 'ding', 'foo']
+ False
+ >>> d.updateOrder(('bar', 'beep', 'ding', 'foo'))
+ >>> d.keys()
+ ['bar', 'beep', 'ding', 'foo']
+
+
`updateOrder` expects the entire list of keys in the new order
- >>> d.updateOrder(['two'])
- Traceback (most recent call last):
- ...
- ValueError: Incompatible key set.
+ >>> d.updateOrder(['bar', 'beep', 'ding'])
+ Traceback (most recent call last):
+ ...
+ ValueError: Incompatible key set.
+ >>> d.updateOrder(['bar', 'beep', 'ding', 'sha', 'foo'])
+ Traceback (most recent call last):
+ ...
+ ValueError: Incompatible key set.
-Length is implemented in the same way as a Dict
+ >>> d.updateOrder(['bar', 'beep', 'ding', 'sha'])
+ Traceback (most recent call last):
+ ...
+ ValueError: Incompatible key set.
- >>> d._len
- <BTrees.Length.Length object at ...>
- >>> d._len()
- 2
+ >>> d.updateOrder(['bar', 'beep', 'ding', 'ding'])
+ Traceback (most recent call last):
+ ...
+ ValueError: Duplicate keys in order.
+The Dict supports the full ``update`` interface. If the input values are
+ordered, the result will be as well.
-OrderedDict also provides API that return iterators of the above methods.
+ >>> d.update([['sha', 'zam'], ['ka', 'pow']])
+ >>> len(d)
+ 6
+ >>> d['ka']
+ 'pow'
+ >>> d.keys()
+ ['bar', 'beep', 'ding', 'foo', 'sha', 'ka']
- >>> iter(d)
- <iterator object at ...>
- >>> d.iterkeys()
- <iterator object at ...>
+If keyword arguments are used, no order to the new items is implied, but
+it otherwise works as expected.
- >>> d.iteritems()
- <generator object at ...>
+ >>> d.update(left='hook', right='jab')
+ >>> len(d)
+ 8
+ >>> d['left']
+ 'hook'
- >>> d.itervalues()
- <generator object at ...>
+``pop`` needs to update the length, and maintain the order.
+ >>> d.pop('sha')
+ 'zam'
+ >>> d.pop('ka')
+ 'pow'
+ >>> d.pop('left')
+ 'hook'
+ >>> d.pop('right')
+ 'jab'
+ >>> len(d)
+ 4
+ >>> d.keys()
+ ['bar', 'beep', 'ding', 'foo']
-OrderedDict also provides a copy method
+...except when it doesn't.
- >>> c = d.copy()
- >>> c.items() == d.items()
- True
+ >>> d.pop('nonexistent')
+ Traceback (most recent call last):
+ ...
+ KeyError: 'nonexistent'
+ >>> d.pop('nonexistent', 42)
+ 42
+ >>> len(d)
+ 4
-The `update` method is also provided. If it is provided with an OrderedDict,
-then the new elements are added in the same order as in the argument.
+``setdefault`` also sometimes needs to update the length.
- >>> d2 = OrderedDict()
- >>> d2['five'] = 'Five'
- >>> d2['six'] = 'Six'
- >>> d.update(d2)
- >>> d.items()
- [('two', 'Two'), ('one', 'One'), ('five', 'Five'), ('six', 'Six')]
+ >>> len(d)
+ 4
+ >>> d.setdefault('newly created', 'value')
+ 'value'
+ >>> d['newly created']
+ 'value'
+ >>> len(d)
+ 5
+ >>> d.keys()
+ ['bar', 'beep', 'ding', 'foo', 'newly created']
+ >>> d.setdefault('newly created', 'other')
+ 'value'
+ >>> d['newly created']
+ 'value'
+ >>> len(d)
+ 5
-But if the argument is a non-ordered dict, then the order of the newly added
-elements in the resulting OrderedDict object cannot be guaranteed.
+ >>> del d['newly created'] # set things back to the way they were...
+``keys``, ``values`` and ``items`` return normal Python lists. Because of
+the underlying BTree, these are always in sort order of the keys.
+
+ >>> d.keys()
+ ['bar', 'beep', 'ding', 'foo']
+
+ >>> d.values()
+ ['moo', 'beep', 'dong', 'bar']
+
+ >>> d.items()
+ [('bar', 'moo'), ('beep', 'beep'), ('ding', 'dong'), ('foo', 'bar')]
+
+However, efficient iterators are available via the iter methods:
+
+ >>> iter(d)
+ <iterator object at ...>
+ >>> d.iterkeys()
+ <iterator object at ...>
+
+ >>> d.iteritems()
+ <generator object at ...>
+
+ >>> d.itervalues()
+ <generator object at ...>
+
+popitem removes an item from the dict and returns a key-value pair:
+
+ >>> len(d)
+ 4
+
+ >>> d.popitem()
+ ('bar', 'moo')
+
+ >>> len(d)
+ 3
+
+The copy method creates a copy of a Dict:
+
+ >>> c = d.copy()
+ >>> c.items() == d.items()
+ True
+
+However we don't support comparison, except for identity, because of
+cowardice:
+
+ >>> c == d
+ False
+ >>> OrderedDict() == {}
+ False
+ >>> d == d
+ True
+
clear removes all the keys from the dict:
- >>> d.clear()
- >>> d.keys()
- []
- >>> len(d)
- 0
+ >>> d.clear()
+ >>> d.keys()
+ []
+ >>> len(d)
+ 0
+The rest of the dict methods are delegated to the underlying BTree:
+
+ >>> c.has_key('beep')
+ True
+ >>> 'BEEP' in c
+ False
+ >>> c.get('nonexistent', 'default')
+ 'default'
+
+
+Regression tests
+----------------
+
+When setting an item that's already in the dict, the length is not
+increased:
+
+ >>> d.clear()
+ >>> d['foo'] = 'bar'
+ >>> d['foo'] = 'baz'
+ >>> len(d)
+ 1
+
+
More information about the Checkins
mailing list