from bisect import bisect_left, bisect_right
class SortedCollection(object):
'''Sequence sorted by a key function.
SortedCollection() is much easier to work with than using bisect() directly.
The key function is automatically applied to each search. The results
are cached so that the key function is called exactly once for each item.
Instead of returning an insertion-point which can be hard to interpret, the
five find-methods return a specific item in the sequence. They can scan for
exact matches, the last item less-than-or-equal to a key, or the first item
greater-than-or-equal to a key.
Once found, an item's ordinal position can be located with the index() method.
New items can be added with the insert() and insert_right() methods.
Old items can be deleted with remove().
The usual sequence methods are provided to support indexing, slicing,
length lookup, clearing, copying, forward and reverse iteration, contains
checking, item counts, item removeal, and a nice looking repr.
Finding and indexing are O(log n) operations while iteration and insertion
are O(n). The initial sort is O(n log n).
The key function is stored in the 'key' attibute for easy introspection or
so that you can assign a new key function (triggering an automatic re-sort).
In short, the class was designed to handle all of the common use cases for
bisect but with a simpler API and support for key functions.
>>> from pprint import pprint
>>> from operator import itemgetter
>>> s = SortedCollection(key=itemgetter(2))
>>> for record in [
... ('roger', 'young', 30),
... ('angela', 'jones', 28),
... ('bill', 'smith', 22),
... ('david', 'thomas', 32)]:
... s.insert(record)
>>> pprint(list(s)) # show records sorted by age
[('bill', 'smith', 22),
('angela', 'jones', 28),
('roger', 'young', 30),
('david', 'thomas', 32)]
>>> s.find_le(29) # find oldest person aged 29 or younger
('angela', 'jones', 28)
>>> s.find_lt(28) # find oldest person under 28
('bill', 'smith', 22)
>>> s.find_gt(28) # find youngest person over 28
('roger', 'young', 30)
>>> r = s.find_ge(32) # find youngest person aged 32 or older
>>> s.index(r) # get the index of their record
3
>>> s[3] # fetch the record at that index
('david', 'thomas', 32)
>>> s.key = itemgetter(0) # now sort by first name
>>> pprint(list(s))
[('angela', 'jones', 28),
('bill', 'smith', 22),
('david', 'thomas', 32),
('roger', 'young', 30)]
'''
def __init__(self, iterable=(), key=None):
self._given_key = key
key = (lambda x: x) if key is None else key
decorated = sorted((key(item), item) for item in iterable)
self._keys = [k for k, item in decorated]
self._items = [item for k, item in decorated]
self._key = key
def _getkey(self):
return self._key
def _setkey(self, key):
if key is not self._key:
self.__init__(self._items, key=key)
def _delkey(self):
self._setkey(None)
key = property(_getkey, _setkey, _delkey, 'key function')
def clear(self):
self.__init__([], self._key)
def copy(self):
return self.__class__(self, self._key)
def __len__(self):
return len(self._items)
def __getitem__(self, i):
return self._items[i]
def __iter__(self):
return iter(self._items)
def __reversed__(self):
return reversed(self._items)
def __repr__(self):
return '%s(%r, key=%s)' % (
self.__class__.__name__,
self._items,
getattr(self._given_key, '__name__', repr(self._given_key))
)
def __reduce__(self):
return self.__class__, (self._items, self._given_key)
def __contains__(self, item):
key = self._key(item)
i = bisect_left(self._keys, key)
n = len(self)
while i < n and self._keys[i] == key:
if self._items[i] == item:
return True
i += 1
return False
def index(self, item):
'Find the position of an item. Raise ValueError if not found.'
key = self._key(item)
i = bisect_left(self._keys, key)
n = len(self)
while i < n and self._keys[i] == key:
if self._items[i] == item:
return i
i += 1
raise ValueError('No item equal to: %r' % (item,))
def count(self, item):
'Return number of occurrences of item'
k = self._key(item)
i = bisect_left(self._keys, k)
n = len(self)
cnt = 0
while i < n and self._keys[i] == k:
if self._items[i] == item:
cnt += 1
i += 1
return cnt
def insert(self, item):
'Insert a new item. If equal keys are found, add to the left'
k = self._key(item)
i = bisect_left(self._keys, k)
self._keys.insert(i, k)
self._items.insert(i, item)
def insert_right(self, item):
'Insert a new item. If equal keys are found, add to the right'
k = self._key(item)
i = bisect_right(self._keys, k)
self._keys.insert(i, k)
self._items.insert(i, item)
def remove(self, item):
'Remove first occurence of item. Raise ValueError if not found'
try:
i = self.index(item)
except ValueError:
raise ValueError('No item equal to: %r' % (item,))
del self._items[i]
del self._keys[i]
def find(self, k):
'Return first item with a key equal to k. Raise ValueError if not found.'
i = bisect_left(self._keys, k)
if i < len(self) and self._keys[i] == k:
return self._items[i]
raise ValueError('No item found with key equal to: %r' % (k,))
def find_le(self, k):
'Return last item with a key less-than or equal to k. Raise ValueError if not found.'
i = bisect_right(self._keys, k)
if i < len(self) and self._keys[i] == k:
return self._items[i]
if i == 0:
raise ValueError('No item found with key at or below: %r' % (k,))
return self._items[i-1]
def find_lt(self, k):
'Return last item with a key less-than k. Raise ValueError if not found.'
i = bisect_left(self._keys, k)
if i == 0:
raise ValueError('No item found with key below: %r' % (k,))
return self._items[i-1]
def find_ge(self, k):
'Return first item with a key greater-than or equal to k. Raise ValueError if not found'
i = bisect_left(self._keys, k)
if i >= len(self):
raise ValueError('No item found with key at or above: %r' % (k,))
return self._items[i]
def find_gt(self, k):
'Return first item with a key greater-than k. Raise ValueError if not found'
i = bisect_right(self._keys, k)
if i >= len(self):
raise ValueError('No item found with key above: %r' % (k,))
return self._items[i]
# --------------------------- Simple demo and tests -------------------------
if __name__ == '__main__':
def ve2no(f, *args):
'Convert ValueError result to -1'
try:
return f(*args)
except ValueError:
return -1
def slow_index(seq, k):
'Location of match or -1 if not found'
for i, item in enumerate(seq):
if item == k:
return i
return -1
def slow_find(seq, k):
'First item with a key equal to k. -1 if not found'
for item in seq:
if item == k:
return item
return -1
def slow_find_le(seq, k):
'Last item with a key less-than or equal to k.'
for item in reversed(seq):
if item <= k:
return item
return -1
def slow_find_lt(seq, k):
'Last item with a key less-than k.'
for item in reversed(seq):
if item < k:
return item
return -1
def slow_find_ge(seq, k):
'First item with a key-value greater-than or equal to k.'
for item in seq:
if item >= k:
return item
return -1
def slow_find_gt(seq, k):
'First item with a key-value greater-than or equal to k.'
for item in seq:
if item > k:
return item
return -1
from random import choice
pool = [1.5, 2, 2.0, 3, 3.0, 3.5, 4, 4.0, 4.5]
for i in range(500):
for n in range(6):
s = [choice(pool) for i in range(n)]
sc = SortedCollection(s)
s.sort()
for probe in pool:
assert repr(ve2no(sc.index, probe)) == repr(slow_index(s, probe))
assert repr(ve2no(sc.find, probe)) == repr(slow_find(s, probe))
assert repr(ve2no(sc.find_le, probe)) == repr(slow_find_le(s, probe))
assert repr(ve2no(sc.find_lt, probe)) == repr(slow_find_lt(s, probe))
assert repr(ve2no(sc.find_ge, probe)) == repr(slow_find_ge(s, probe))
assert repr(ve2no(sc.find_gt, probe)) == repr(slow_find_gt(s, probe))
for i, item in enumerate(s):
assert repr(item) == repr(sc[i]) # test __getitem__
assert item in sc # test __contains__ and __iter__
assert s.count(item) == sc.count(item) # test count()
assert len(sc) == n # test __len__
assert list(map(repr, reversed(sc))) == list(map(repr, reversed(s))) # test __reversed__
assert list(sc.copy()) == list(sc) # test copy()
sc.clear() # test clear()
assert len(sc) == 0
sd = SortedCollection('The quick Brown Fox jumped'.split(), key=str.lower)
assert sd._keys == ['brown', 'fox', 'jumped', 'quick', 'the']
assert sd._items == ['Brown', 'Fox', 'jumped', 'quick', 'The']
assert sd._key == str.lower
assert repr(sd) == "SortedCollection(['Brown', 'Fox', 'jumped', 'quick', 'The'], key=lower)"
sd.key = str.upper
assert sd._key == str.upper
assert len(sd) == 5
assert list(reversed(sd)) == ['The', 'quick', 'jumped', 'Fox', 'Brown']
for item in sd:
assert item in sd
for i, item in enumerate(sd):
assert item == sd[i]
sd.insert('jUmPeD')
sd.insert_right('QuIcK')
assert sd._keys ==['BROWN', 'FOX', 'JUMPED', 'JUMPED', 'QUICK', 'QUICK', 'THE']
assert sd._items == ['Brown', 'Fox', 'jUmPeD', 'jumped', 'quick', 'QuIcK', 'The']
assert sd.find_le('JUMPED') == 'jumped'
assert sd.find_ge('JUMPED') == 'jUmPeD'
assert sd.find_le('GOAT') == 'Fox'
assert sd.find_ge('GOAT') == 'jUmPeD'
assert sd.find('FOX') == 'Fox'
assert sd[3] == 'jumped'
assert sd[3:5] ==['jumped', 'quick']
assert sd[-2] == 'QuIcK'
assert sd[-4:-2] == ['jumped', 'quick']
for i, item in enumerate(sd):
assert sd.index(item) == i
try:
sd.index('xyzpdq')
except ValueError:
pass
else:
assert 0, 'Oops, failed to notify of missing value'
sd.remove('jumped')
assert list(sd) == ['Brown', 'Fox', 'jUmPeD', 'quick', 'QuIcK', 'The']
import doctest
from operator import itemgetter
print(doctest.testmod())
Diff to Previous Revision
--- revision 6 2010-08-30 01:09:21
+++ revision 7 2010-08-30 08:02:48
@@ -1,7 +1,7 @@
from bisect import bisect_left, bisect_right
class SortedCollection(object):
- '''Sequence sorted by a given key function.
+ '''Sequence sorted by a key function.
SortedCollection() is much easier to work with than using bisect() directly.
@@ -9,27 +9,26 @@
are cached so that the key function is called exactly once for each item.
Instead of returning an insertion-point which can be hard to interpret, the
- three find-methods return a specific item in the sequence. They can scan
- for exact matches, the last item less-than-or-equal to a key, or the
- first item greater-than-or-equal to a key.
+ five find-methods return a specific item in the sequence. They can scan for
+ exact matches, the last item less-than-or-equal to a key, or the first item
+ greater-than-or-equal to a key.
Once found, an item's ordinal position can be located with the index() method.
-
New items can be added with the insert() and insert_right() methods.
- Add items can be removed with remove().
+ Old items can be deleted with remove().
The usual sequence methods are provided to support indexing, slicing,
length lookup, clearing, copying, forward and reverse iteration, contains
checking, item counts, item removeal, and a nice looking repr.
- Finding and indexing are all O(log n) operations while iteration and
- insertion are O(n). The initial sort is O(n log n).
+ Finding and indexing are O(log n) operations while iteration and insertion
+ are O(n). The initial sort is O(n log n).
The key function is stored in the 'key' attibute for easy introspection or
so that you can assign a new key function (triggering an automatic re-sort).
In short, the class was designed to handle all of the common use cases for
- bisect but with a simpler API and with support for key functions.
+ bisect but with a simpler API and support for key functions.
>>> from pprint import pprint
>>> from operator import itemgetter
@@ -37,8 +36,8 @@
>>> s = SortedCollection(key=itemgetter(2))
>>> for record in [
... ('roger', 'young', 30),
+ ... ('angela', 'jones', 28),
... ('bill', 'smith', 22),
- ... ('angela', 'jones', 28),
... ('david', 'thomas', 32)]:
... s.insert(record)
@@ -50,8 +49,12 @@
>>> s.find_le(29) # find oldest person aged 29 or younger
('angela', 'jones', 28)
-
- >>> r = s.find_ge(31) # find first person aged 31 or older
+ >>> s.find_lt(28) # find oldest person under 28
+ ('bill', 'smith', 22)
+ >>> s.find_gt(28) # find youngest person over 28
+ ('roger', 'young', 30)
+
+ >>> r = s.find_ge(32) # find youngest person aged 32 or older
>>> s.index(r) # get the index of their record
3
>>> s[3] # fetch the record at that index
@@ -67,6 +70,7 @@
'''
def __init__(self, iterable=(), key=None):
+ self._given_key = key
key = (lambda x: x) if key is None else key
decorated = sorted((key(item), item) for item in iterable)
self._keys = [k for k, item in decorated]
@@ -107,8 +111,11 @@
return '%s(%r, key=%s)' % (
self.__class__.__name__,
self._items,
- getattr(self._key, '__name__', repr(self._key))
+ getattr(self._given_key, '__name__', repr(self._given_key))
)
+
+ def __reduce__(self):
+ return self.__class__, (self._items, self._given_key)
def __contains__(self, item):
key = self._key(item)
@@ -121,14 +128,7 @@
return False
def index(self, item):
- '''Find the position of an item. Raise a ValueError if not found.
-
- >>> db = [('bill', 22), ('angela', 28), ('roger', 30), ('david', 32)]
- >>> s = SortedCollection(db, key=itemgetter(1))
- >>> s.index(('angela', 28))
- 1
-
- '''
+ 'Find the position of an item. Raise ValueError if not found.'
key = self._key(item)
i = bisect_left(self._keys, key)
n = len(self)
@@ -174,32 +174,14 @@
del self._keys[i]
def find(self, k):
- '''Return first item with a key equal to k. (ValueError if not found)
-
- Raise ValueError if no such item exists.
-
- >>> db = [('bill', 22), ('angela', 28), ('roger', 30), ('david', 32)]
- >>> s = SortedCollection(db, key=itemgetter(1))
- >>> s.find(28)
- ('angela', 28)
-
- '''
+ 'Return first item with a key equal to k. Raise ValueError if not found.'
i = bisect_left(self._keys, k)
if i < len(self) and self._keys[i] == k:
return self._items[i]
raise ValueError('No item found with key equal to: %r' % (k,))
def find_le(self, k):
- '''Return last item with a key less-than or equal to k.
-
- Raise ValueError if no such item exists.
-
- >>> db = [('bill', 22), ('angela', 28), ('roger', 30), ('david', 32)]
- >>> s = SortedCollection(db, key=itemgetter(1))
- >>> s.find_le(29)
- ('angela', 28)
-
- '''
+ 'Return last item with a key less-than or equal to k. Raise ValueError if not found.'
i = bisect_right(self._keys, k)
if i < len(self) and self._keys[i] == k:
return self._items[i]
@@ -208,49 +190,21 @@
return self._items[i-1]
def find_lt(self, k):
- '''Return last item with a key less-than k.
-
- Raise ValueError if no such item exists.
-
- >>> db = [('bill', 22), ('angela', 28), ('roger', 30), ('david', 32)]
- >>> s = SortedCollection(db, key=itemgetter(1))
- >>> s.find_lt(28)
- ('bill', 22)
-
- '''
+ 'Return last item with a key less-than k. Raise ValueError if not found.'
i = bisect_left(self._keys, k)
if i == 0:
raise ValueError('No item found with key below: %r' % (k,))
return self._items[i-1]
-
def find_ge(self, k):
- '''Return first item with a key greater-than or equal to k.
-
- Raise ValueError if no such item exists.
-
- >>> db = [('bill', 22), ('angela', 28), ('roger', 30), ('david', 32)]
- >>> s = SortedCollection(db, key=itemgetter(1))
- >>> s.find_ge(27)
- ('angela', 28)
-
- '''
+ 'Return first item with a key greater-than or equal to k. Raise ValueError if not found'
i = bisect_left(self._keys, k)
if i >= len(self):
raise ValueError('No item found with key at or above: %r' % (k,))
return self._items[i]
def find_gt(self, k):
- '''Return first item with a key greater-than k.
-
- Raise ValueError if no such item exists.
-
- >>> db = [('bill', 22), ('angela', 28), ('roger', 30), ('david', 32)]
- >>> s = SortedCollection(db, key=itemgetter(1))
- >>> s.find_gt(28)
- ('roger', 30)
-
- '''
+ 'Return first item with a key greater-than k. Raise ValueError if not found'
i = bisect_right(self._keys, k)
if i >= len(self):
raise ValueError('No item found with key above: %r' % (k,))
@@ -323,12 +277,15 @@
assert repr(ve2no(sc.find_lt, probe)) == repr(slow_find_lt(s, probe))
assert repr(ve2no(sc.find_ge, probe)) == repr(slow_find_ge(s, probe))
assert repr(ve2no(sc.find_gt, probe)) == repr(slow_find_gt(s, probe))
- for item in s:
- assert item in sc # test __contains__ and __iter__
for i, item in enumerate(s):
- assert repr(item) == repr(sc[i]) # test __getitem__
- for item in s:
- assert s.count(item) == sc.count(item)
+ assert repr(item) == repr(sc[i]) # test __getitem__
+ assert item in sc # test __contains__ and __iter__
+ assert s.count(item) == sc.count(item) # test count()
+ assert len(sc) == n # test __len__
+ assert list(map(repr, reversed(sc))) == list(map(repr, reversed(s))) # test __reversed__
+ assert list(sc.copy()) == list(sc) # test copy()
+ sc.clear() # test clear()
+ assert len(sc) == 0
sd = SortedCollection('The quick Brown Fox jumped'.split(), key=str.lower)
assert sd._keys == ['brown', 'fox', 'jumped', 'quick', 'the']
