from collections import Sequence
from bisect import bisect_left, bisect_right

class SortedCollection(Sequence):
    # XXX should the find methods return a key, item, or index?

    def __init__(self, iterable=(), key=None):
        self._keyfunc = (lambda x: x) if key is None else key
        self._items = sorted(iterable, key=self._keyfunc)
        self._keys = map(self._keyfunc, self._items)

    def _getkeyfunc(self):
        return self._keyfunc

    def _setkeyfunc(self, keyfunc):
        if keyfunc is not self._keyfunc:
            self.__init__(self._items, keyfunc)

    keyfunc = property(_getkeyfunc, _setkeyfunc, None, 'ordering function')

    def clear(self):
        self.__init__([], self._keyfunc)

    def __len__(self):
        return len(self._items)

    def __getitem__(self, i):
        return self._items[i]

    def __contains__(self, key):
        return key in self._items

    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._keyfunc, '__name__', repr(self._keyfunc))
        )

    def insert_left(self, item):
        'Insert a new item.  If equal keys are found, add to the left'
        key = self._keyfunc(item)
        i = bisect_left(self._keys, key)
        self._keys.insert(i, key)
        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._keyfunc(item)
        i = bisect_right(self._keys, key)
        self._keys.insert(i, key)
        self._items.insert(i, item)

    def find_le(self, key):
        '''Find item with key-value less-than or equal to key.
        Raise ValueError if no such item exists.
        If multiple key-values are equal, return the leftmost.

        '''
        i = bisect_left(self._keys, key)
        if self._keys[i] == key:
            return self._items[i]
        if i == 0:
            raise ValueError('No item found with key at or below: %r' % (key,))
        return self._items[i-1]

    def find_ge(self, key):
        '''Find item with key-value greater-than or equal to key.
        Raise ValueError if no such item exists.
        If multiple key-values are equal, return the rightmost.

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

    def find(self, key):
        '''Find item with key-value equal to key.
        Raise ValueError if no such item exists.

        '''
        i = bisect_left(self._keys, key)
        if self._keys[i] == key:
            return self._items[i]
        raise ValueError('No item found with key equal to: %r' % (key,))

if __name__ == '__main__':
    sd = SortedCollection('The quick Brown Fox jumped'.split(), key=str.lower)
    print sd._keys
    print sd._items
    print sd._keyfunc
    print repr(sd)
    print sd.keyfunc
    sd.keyfunc = str.upper
    print sd.keyfunc
    print len(sd)
    print list(sd)
    print list(reversed(sd))
    for item in sd:
        assert item in sd
    for i, item in enumerate(sd):
        assert item == sd[i]
    sd.insert_left('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]