from bisect import bisect_left, bisect_right
class SortedCollection(object):
'''Sequence sorted by a given 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
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.
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().
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).
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.
>>> from pprint import pprint
>>> from operator import itemgetter
>>> s = SortedCollection(key=itemgetter(2))
>>> for record in [
... ('roger', 'young', 30),
... ('bill', 'smith', 22),
... ('angela', 'jones', 28),
... ('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)
>>> r = s.find_ge(31) # find first person aged 31 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):
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._key, '__name__', repr(self._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 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
'''
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. (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)
'''
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)
'''
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 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)
'''
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)
'''
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)
'''
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 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)
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 5 2010-08-30 00:13:49
+++ revision 6 2010-08-30 01:09:21
@@ -16,6 +16,7 @@
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().
The usual sequence methods are provided to support indexing, slicing,
length lookup, clearing, copying, forward and reverse iteration, contains
@@ -127,15 +128,6 @@
>>> s.index(('angela', 28))
1
- >>> s = SortedCollection([5, 5.0, 10, 10.0, 15, 15.0])
- >>> [s.index(k) for k in 5, 10, 15]
- [0, 2, 4]
-
- >>> s.index(100)
- Traceback (most recent call last):
- ...
- ValueError: No item equal to: 100
-
'''
key = self._key(item)
i = bisect_left(self._keys, key)
@@ -182,22 +174,14 @@
del self._keys[i]
def find(self, k):
- '''Return first item with a key equal to 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)
-
- >>> s.find(29)
- Traceback (most recent call last):
- ...
- ValueError: No item found with key equal to: 29
-
- >>> s = SortedCollection([5, 5.0, 10, 10.0, 15, 15.0])
- >>> [s.find(k) for k in 5, 10, 15]
- [5, 10, 15]
'''
i = bisect_left(self._keys, k)
@@ -207,20 +191,13 @@
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)
-
- >>> s = SortedCollection([5, 5.0, 10, 10.0, 15, 15.0])
- >>> [s.find_le(k) for k in 5, 7, 10, 13, 15, 17]
- [5.0, 5.0, 10.0, 10.0, 15.0, 15.0]
- >>> s.find_le(3)
- Traceback (most recent call last):
- ...
- ValueError: No item found with key at or below: 3
'''
i = bisect_right(self._keys, k)
@@ -230,22 +207,32 @@
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 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)
+
+ '''
+ 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)
-
- >>> s = SortedCollection([5, 5.0, 10, 10.0, 15, 15.0])
- >>> [s.find_ge(k) for k in 3, 5, 7, 10, 13, 15]
- [5, 5, 10, 10, 15, 15]
- >>> s.find_ge(17)
- Traceback (most recent call last):
- ...
- ValueError: No item found with key at or above: 17
'''
i = bisect_left(self._keys, k)
@@ -253,6 +240,21 @@
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)
+
+ '''
+ 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 -------------------------
@@ -265,31 +267,45 @@
except ValueError:
return -1
- def slow_index(seq, key):
+ def slow_index(seq, k):
'Location of match or -1 if not found'
for i, item in enumerate(seq):
- if item == key:
+ if item == k:
return i
return -1
- def slow_find(seq, key):
- 'First item with a key-value equal to key. -1 if not found'
+ def slow_find(seq, k):
+ 'First item with a key equal to k. -1 if not found'
for item in seq:
- if item == key:
- return item
- return -1
-
- def slow_find_le(seq, key):
- 'Last item with a key-value less-than or equal to key.'
+ 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 <= key:
- return item
- return -1
-
- def slow_find_ge(seq, key):
- 'First item with a key-value greater-than or equal to key.'
+ 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 >= key:
+ 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
@@ -304,7 +320,9 @@
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 item in s:
assert item in sc # test __contains__ and __iter__
for i, item in enumerate(s):
