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.
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
>>> 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)
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 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)
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)
>>> 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)
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_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)
if i >= len(self):
raise ValueError('No item found with key at or 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, key):
'Location of match or -1 if not found'
for i, item in enumerate(seq):
if item == key:
return i
return -1
def slow_find(seq, key):
'First item with a key-value equal to key. -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.'
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.'
for item in seq:
if item >= key:
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_ge, probe)) == repr(slow_find_ge(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 4 2010-08-07 07:53:02
+++ revision 5 2010-08-30 00:13:49
@@ -1,25 +1,25 @@
from bisect import bisect_left, bisect_right
class SortedCollection(object):
- '''Encapsulates a sequence sorted by a given key function.
+ '''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 a difficult to interpret insertion-point, the three
- find-methods return a specific item in the sequence. They can scan for exact
- matches, the largest item less-than-or-equal to a key, or the smallest item
- greater-than-or-equal to a key.
-
- Once found, an item's ordinal position can be found with the index() method.
+ 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.
- The usual sequence methods are provided to support indexing, slicing, length
- lookup, clearing, forward and reverse iteration, contains checking, and a
- nice repr.
+ 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).
@@ -28,7 +28,7 @@
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 automatic support for key functions.
+ bisect but with a simpler API and with support for key functions.
>>> from pprint import pprint
>>> from operator import itemgetter
@@ -66,9 +66,11 @@
'''
def __init__(self, iterable=(), key=None):
- self._key = (lambda x: x) if key is None else key
- self._items = sorted(iterable, key=self._key)
- self._keys = list(map(self._key, self._items))
+ 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
@@ -85,16 +87,14 @@
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 __contains__(self, key):
- return key in self._items
- i = bisect_left(self._keys, key)
- return self._keys[i] == key
def __iter__(self):
return iter(self._items)
@@ -109,8 +109,34 @@
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'''
+ '''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
+
+ >>> 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)
n = len(self)
@@ -118,100 +144,211 @@
if self._items[i] == item:
return i
i += 1
- raise ValueError('No item found with key equal to: %r' % (key,))
+ 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'
- key = self._key(item)
- i = bisect_left(self._keys, key)
- self._keys.insert(i, key)
+ 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'
- key = self._key(item)
- i = bisect_right(self._keys, key)
- self._keys.insert(i, key)
+ k = self._key(item)
+ i = bisect_right(self._keys, k)
+ self._keys.insert(i, k)
self._items.insert(i, item)
- def find(self, key):
- '''Find item with a key-value equal to key.
+ 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 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, key)
- if self._keys[i] == key:
+ 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' % (key,))
-
- def find_le(self, key):
- '''Find item with a key-value less-than or equal to key.
+ 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.
- If multiple key-values are equal, return the leftmost.
+
+ >>> 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_left(self._keys, key)
- if self._keys[i] == key:
+ 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' % (key,))
+ raise ValueError('No item found with key at or below: %r' % (k,))
return self._items[i-1]
- def find_ge(self, key):
- '''Find item with a key-value greater-than or equal to key.
+ def find_ge(self, k):
+ '''Return first item with a key greater-than or equal to k.
Raise ValueError if no such item exists.
- If multiple key-values are equal, return the rightmost.
+
+ >>> 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_right(self._keys, key)
- if i == 0:
- raise ValueError('No item found with key at or above: %r' % (key,))
- if self._keys[i-1] == key:
- return self._items[i-1]
+ 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]
+
+
+
+# --------------------------- Simple demo and tests -------------------------
+if __name__ == '__main__':
+
+ def ve2no(f, *args):
+ 'Convert ValueError result to -1'
try:
- return self._items[i]
- except IndexError:
- raise ValueError('No item found with key at or above: %r' % (key,))
-
-
-if __name__ == '__main__':
+ return f(*args)
+ except ValueError:
+ return -1
+
+ def slow_index(seq, key):
+ 'Location of match or -1 if not found'
+ for i, item in enumerate(seq):
+ if item == key:
+ return i
+ return -1
+
+ def slow_find(seq, key):
+ 'First item with a key-value equal to key. -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.'
+ 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.'
+ for item in seq:
+ if item >= key:
+ 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_ge, probe)) == repr(slow_find_ge(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)
- print(sd._keys)
- print(sd._items)
- print(sd._key)
- print(repr(sd))
- print(sd.key)
+ 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
- print(sd.key)
- print(len(sd))
- print(list(sd))
- print(list(reversed(sd)))
+ 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')
- print(sd._keys)
- print(sd._items)
- print(sd.find_le('JUMPED'), 'jUmPeD')
- print(sd.find_ge('JUMPED'), 'jumped')
- print(sd.find_le('GOAT'), 'Fox')
- print(sd.find_ge('GOAT'), 'jUmPeD')
- print(sd.find('FOX'))
- print(sd[3])
- print(sd[3:5])
- print(sd[-2])
- print(sd[-4:-2])
+ 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):
- print(sd.index(item), i)
+ assert sd.index(item) == i
try:
sd.index('xyzpdq')
except ValueError:
pass
else:
- print('Oops, failed to notify of missing value')
-
+ 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())
