python sorted collection module by raymond hettinger copied from http code activestate comrecipes577197sortedcollection retrieved on april 22 2018 sequence sorted by a key function sortedcollection is much easier to work with than using bisect directly it supports key functions like those use in sorted min and max the result of the key function call is saved so that keys can be searched efficiently instead of returning an insertionpoint which can be hard to interpret the five findmethods return a specific item in the sequence they can scan for exact matches the last item lessthanorequal to a key or the first item greaterthanorequal 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 insertright methods old items can be deleted with the remove method the usual sequence methods are provided to support indexing slicing length lookup clearing copying forward and reverse iteration contains checking item counts item removal and a nice looking repr finding and indexing are olog n operations while iteration and insertion are on the initial sort is on 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 resort 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 sortedcollectionkeyitemgetter2 for record in roger young 30 angela jones 28 bill smith 22 david thomas 32 s insertrecord pprintlists show records sorted by age bill smith 22 angela jones 28 roger young 30 david thomas 32 s findle29 find oldest person aged 29 or younger angela jones 28 s findlt28 find oldest person under 28 bill smith 22 s findgt28 find youngest person over 28 roger young 30 r s findge32 find youngest person aged 32 or older s indexr get the index of their record 3 s3 fetch the record at that index david thomas 32 s key itemgetter0 now sort by first name pprintlists angela jones 28 bill smith 22 david thomas 32 roger young 30 grantj 051618 additions for benchmarking simple demo and tests sequence sorted by a key function sortedcollection is much easier to work with than using bisect directly it supports key functions like those use in sorted min and max the result of the key function call is saved so that keys can be searched efficiently 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 the remove method the usual sequence methods are provided to support indexing slicing length lookup clearing copying forward and reverse iteration contains checking item counts item removal 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 grantj 05 16 18 additions for benchmarking simple demo and tests test __getitem__ test __contains__ and __iter__ test count test __len__ test __reversed__ test copy test clear
from bisect import bisect_left, bisect_right

class SortedCollection(object):
    

    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):
        k = self._key(item)
        i = bisect_left(self._keys, k)
        j = bisect_right(self._keys, k)
        return item in self._items[i:j]

    def index(self, item):
        'Find the position of an item.  Raise ValueError if not found.'
        k = self._key(item)
        i = bisect_left(self._keys, k)
        j = bisect_right(self._keys, k)
        return self._items[i:j].index(item) + i

    def count(self, item):
        'Return number of occurrences of item'
        k = self._key(item)
        i = bisect_left(self._keys, k)
        j = bisect_right(self._keys, k)
        return self._items[i:j].count(item)

    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 occurrence of item.  Raise ValueError if not found'
        i = self.index(item)
        del self._keys[i]
        del self._items[i]

    def find(self, k):
        'Return first item with a key == 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 <= k.  Raise ValueError if not found.'
        i = bisect_right(self._keys, k)
        if i:
            return self._items[i-1]
        raise ValueError('No item found with key at or below: %r' % (k,))

    def find_lt(self, k):
        'Return last item with a key < k.  Raise ValueError if not found.'
        i = bisect_left(self._keys, k)
        if i:
            return self._items[i-1]
        raise ValueError('No item found with key below: %r' % (k,))

    def find_ge(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):
            return self._items[i]
        raise ValueError('No item found with key at or above: %r' % (k,))

    def find_gt(self, k):
        'Return first item with a key > k.  Raise ValueError if not found'
        i = bisect_right(self._keys, k)
        if i != len(self):
            return self._items[i]
        raise ValueError('No item found with key above: %r' % (k,))

    

    add = insert

    def update(self, iterable):
        for value in iterable:
            self.insert(value)

    def bisect(self, item):
        key = self._key(item)
        pos = bisect_left(self._keys, key)
        return pos

    def pop(self):
        self._keys.pop()
        return self._items.pop()

    def discard(self, item):
        try:
            self.remove(item)
        except ValueError:
            pass

    def __delitem__(self, index):
        del self._keys[index]
        del self._items[index]



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])        
                assert item in sc                       
                assert s.count(item) == sc.count(item)  
            assert len(sc) == n                         
            assert list(map(repr, reversed(sc))) == list(map(repr, reversed(s)))    
            assert list(sc.copy()) == list(sc)          
            sc.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', sd.find_le('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())