| 1 |
# Note: Taken from https://code.activestate.com/recipes/577197-sortedcollection/. |
| 2 |
# |
| 3 |
# Copyright 2010 Raymond Hettinger |
| 4 |
# |
| 5 |
# Permission is hereby granted, free of charge, to any person obtaining a copy of |
| 6 |
# this software and associated documentation files (the "Software"), to deal in the |
| 7 |
# Software without restriction, including without limitation the rights to use, copy, |
| 8 |
# modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, |
| 9 |
# and to permit persons to whom the Software is furnished to do so, subject to the |
| 10 |
# following conditions: |
| 11 |
# |
| 12 |
# The above copyright notice and this permission notice shall be included in all copies |
| 13 |
# or substantial portions of the Software. |
| 14 |
# |
| 15 |
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, |
| 16 |
# INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR |
| 17 |
# PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE |
| 18 |
# FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR |
| 19 |
# OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER |
| 20 |
# DEALINGS IN THE SOFTWARE. |
| 21 |
|
| 22 |
from bisect import bisect_left, bisect_right |
| 23 |
|
| 24 |
|
| 25 |
class SortedCollection(object): |
| 26 |
def __init__(self, iterable=(), key=None): |
| 27 |
self._given_key = key |
| 28 |
key = (lambda x: x) if key is None else key |
| 29 |
decorated = sorted((key(item), item) for item in iterable) |
| 30 |
self._keys = [k for k, item in decorated] |
| 31 |
self._items = [item for k, item in decorated] |
| 32 |
self._key = key |
| 33 |
|
| 34 |
def _getkey(self): |
| 35 |
return self._key |
| 36 |
|
| 37 |
def _setkey(self, key): |
| 38 |
if key is not self._key: |
| 39 |
self.__init__(self._items, key=key) |
| 40 |
|
| 41 |
def _delkey(self): |
| 42 |
self._setkey(None) |
| 43 |
|
| 44 |
key = property(_getkey, _setkey, _delkey, 'key function') |
| 45 |
|
| 46 |
def clear(self): |
| 47 |
self.__init__([], self._key) |
| 48 |
|
| 49 |
def copy(self): |
| 50 |
return self.__class__(self, self._key) |
| 51 |
|
| 52 |
def __len__(self): |
| 53 |
return len(self._items) |
| 54 |
|
| 55 |
def __getitem__(self, i): |
| 56 |
return self._items[i] |
| 57 |
|
| 58 |
def __iter__(self): |
| 59 |
return iter(self._items) |
| 60 |
|
| 61 |
def __reversed__(self): |
| 62 |
return reversed(self._items) |
| 63 |
|
| 64 |
def __repr__(self): |
| 65 |
return '%s(%r, key=%s)' % ( |
| 66 |
self.__class__.__name__, |
| 67 |
self._items, |
| 68 |
getattr(self._given_key, '__name__', repr(self._given_key)) |
| 69 |
) |
| 70 |
|
| 71 |
def __reduce__(self): |
| 72 |
return self.__class__, (self._items, self._given_key) |
| 73 |
|
| 74 |
def __contains__(self, item): |
| 75 |
k = self._key(item) |
| 76 |
i = bisect_left(self._keys, k) |
| 77 |
j = bisect_right(self._keys, k) |
| 78 |
return item in self._items[i:j] |
| 79 |
|
| 80 |
def index(self, item): |
| 81 |
'Find the position of an item. Raise ValueError if not found.' |
| 82 |
k = self._key(item) |
| 83 |
i = bisect_left(self._keys, k) |
| 84 |
j = bisect_right(self._keys, k) |
| 85 |
return self._items[i:j].index(item) + i |
| 86 |
|
| 87 |
def count(self, item): |
| 88 |
'Return number of occurrences of item' |
| 89 |
k = self._key(item) |
| 90 |
i = bisect_left(self._keys, k) |
| 91 |
j = bisect_right(self._keys, k) |
| 92 |
return self._items[i:j].count(item) |
| 93 |
|
| 94 |
def insert(self, item): |
| 95 |
'Insert a new item. If equal keys are found, add to the left' |
| 96 |
k = self._key(item) |
| 97 |
i = bisect_left(self._keys, k) |
| 98 |
self._keys.insert(i, k) |
| 99 |
self._items.insert(i, item) |
| 100 |
|
| 101 |
def insert_right(self, item): |
| 102 |
'Insert a new item. If equal keys are found, add to the right' |
| 103 |
k = self._key(item) |
| 104 |
i = bisect_right(self._keys, k) |
| 105 |
self._keys.insert(i, k) |
| 106 |
self._items.insert(i, item) |
| 107 |
|
| 108 |
def remove(self, item): |
| 109 |
'Remove first occurence of item. Raise ValueError if not found' |
| 110 |
i = self.index(item) |
| 111 |
del self._keys[i] |
| 112 |
del self._items[i] |
| 113 |
|
| 114 |
def find(self, k): |
| 115 |
'Return first item with a key == k. Raise ValueError if not found.' |
| 116 |
i = bisect_left(self._keys, k) |
| 117 |
if i != len(self) and self._keys[i] == k: |
| 118 |
return self._items[i] |
| 119 |
raise ValueError('No item found with key equal to: %r' % (k,)) |
| 120 |
|
| 121 |
def find_le(self, k): |
| 122 |
'Return last item with a key <= k. Raise ValueError if not found.' |
| 123 |
i = bisect_right(self._keys, k) |
| 124 |
if i: |
| 125 |
return self._items[i-1] |
| 126 |
raise ValueError('No item found with key at or below: %r' % (k,)) |
| 127 |
|
| 128 |
def find_lt(self, k): |
| 129 |
'Return last item with a key < k. Raise ValueError if not found.' |
| 130 |
i = bisect_left(self._keys, k) |
| 131 |
if i: |
| 132 |
return self._items[i-1] |
| 133 |
raise ValueError('No item found with key below: %r' % (k,)) |
| 134 |
|
| 135 |
def find_ge(self, k): |
| 136 |
'Return first item with a key >= equal to k. Raise ValueError if not found' |
| 137 |
i = bisect_left(self._keys, k) |
| 138 |
if i != len(self): |
| 139 |
return self._items[i] |
| 140 |
raise ValueError('No item found with key at or above: %r' % (k,)) |
| 141 |
|
| 142 |
def find_gt(self, k): |
| 143 |
'Return first item with a key > k. Raise ValueError if not found' |
| 144 |
i = bisect_right(self._keys, k) |
| 145 |
if i != len(self): |
| 146 |
return self._items[i] |
| 147 |
raise ValueError('No item found with key above: %r' % (k,)) |