diff options
Diffstat (limited to 'blist/_sortedlist.py')
| -rw-r--r-- | blist/_sortedlist.py | 647 |
1 files changed, 647 insertions, 0 deletions
diff --git a/blist/_sortedlist.py b/blist/_sortedlist.py new file mode 100644 index 0000000..b34f69e --- /dev/null +++ b/blist/_sortedlist.py @@ -0,0 +1,647 @@ +from blist._blist import blist +import collections, bisect, weakref, operator, itertools, sys, threading +try: # pragma: no cover + izip = itertools.izip +except AttributeError: # pragma: no cover + izip = zip + +__all__ = ['sortedlist', 'weaksortedlist', 'sortedset', 'weaksortedset'] + +class ReprRecursion(object): + local = threading.local() + def __init__(self, ob): + if not hasattr(self.local, 'repr_count'): + self.local.repr_count = collections.defaultdict(int) + self.ob_id = id(ob) + self.value = self.ob_id in self.local.repr_count + + def __enter__(self): + self.local.repr_count[self.ob_id] += 1 + return self.value + + def __exit__(self, exc_type, exc_val, exc_tb): + self.local.repr_count[self.ob_id] -= 1 + if self.local.repr_count[self.ob_id] == 0: + del self.local.repr_count[self.ob_id] + return False + +class _sortedbase(collections.Sequence): + def __init__(self, iterable=(), key=None): + self._key = key + if key is not None and not hasattr(key, '__call__'): + raise TypeError("'%s' object is not callable" % str(type(key))) + if ((isinstance(iterable,type(self)) + or isinstance(self,type(iterable))) + and iterable._key is key): + self._blist = blist(iterable._blist) + else: + self._blist = blist() + for v in iterable: + self.add(v) + + def _from_iterable(self, iterable): + return self.__class__(iterable, self._key) + + def _u2key(self, value): + "Convert a user-object to the key" + if self._key is None: + return value + else: + return self._key(value) + + def _u2i(self, value): + "Convert a user-object to the internal representation" + if self._key is None: + return value + else: + return (self._key(value), value) + + def _i2u(self, value): + "Convert an internal object to a user-object" + if self._key is None: + return value + else: + return value[1] + + def _i2key(self, value): + "Convert an internal object to the key" + if self._key is None: + return value + else: + return value[0] + + def _bisect_left(self, v): + """Locate the point in the list where v would be inserted. + + Returns an (i, value) tuple: + - i is the position where v would be inserted + - value is the current user-object at position i + + This is the key function to override in subclasses. They must + accept a user-object v and return a user-object value. + """ + + key = self._u2key(v) + lo = 0 + hi = len(self._blist) + while lo < hi: + mid = (lo+hi)//2 + v = self._i2key(self._blist[mid]) + if v < key: lo = mid + 1 + else: hi = mid + if lo < len(self._blist): + return lo, self._i2u(self._blist[lo]) + return lo, None + + def _bisect_right(self, v): + """Same as _bisect_left, but go to the right of equal values""" + + key = self._u2key(v) + lo = 0 + hi = len(self._blist) + while lo < hi: + mid = (lo+hi)//2 + v = self._i2key(self._blist[mid]) + if key < v: hi = mid + else: lo = mid + 1 + if lo < len(self._blist): + return lo, self._i2u(self._blist[lo]) + return lo, None + + def bisect_left(self, v): + """L.bisect_left(v) -> index + + The return value i is such that all e in L[:i] have e < v, and + all e in a[i:] have e >= v. So if v already appears in the + list, i points just before the leftmost v already there. + """ + return self._bisect_left(v)[0] + + def bisect_right(self, v): + """L.bisect_right(v) -> index + + Return the index where to insert item v in the list. + + The return value i is such that all e in a[:i] have e <= v, + and all e in a[i:] have e > v. So if v already appears in the + list, i points just beyond the rightmost v already there. + """ + return self._bisect_right(v)[0] + + bisect = bisect_right + + def add(self, value): + """Add an element.""" + # Will throw a TypeError when trying to add an object that + # cannot be compared to objects already in the list. + i, _ = self._bisect_right(value) + self._blist.insert(i, self._u2i(value)) + + def discard(self, value): + """Remove an element if it is a member. + + If the element is not a member, do nothing. + + """ + + try: + i, v = self._bisect_left(value) + except TypeError: + # Value cannot be compared with values already in the list. + # Ergo, value isn't in the list. + return + i = self._advance(i, value) + if i >= 0: + del self._blist[i] + + def __contains__(self, value): + """x.__contains__(y) <==> y in x""" + try: + i, v = self._bisect_left(value) + except TypeError: + # Value cannot be compared with values already in the list. + # Ergo, value isn't in the list. + return False + i = self._advance(i, value) + return i >= 0 + + def __len__(self): + """x.__len__() <==> len(x)""" + return len(self._blist) + + def __iter__(self): + """ x.__iter__() <==> iter(x)""" + return (self._i2u(v) for v in self._blist) + + def __getitem__(self, index): + """x.__getitem__(y) <==> x[y]""" + if isinstance(index, slice): + rv = self.__class__() + rv._blist = self._blist[index] + rv._key = self._key + return rv + return self._i2u(self._blist[index]) + + def _advance(self, i, value): + "Do a linear search through all items with the same key" + key = self._u2key(value) + while i < len(self._blist): + if self._i2u(self._blist[i]) == value: + return i + elif key < self._i2key(self._blist[i]): + break + i += 1 + return -1 + + def __reversed__(self): + """L.__reversed__() -- return a reverse iterator over the list""" + return (self._i2u(v) for v in reversed(self._blist)) + + def index(self, value): + """L.index(value) -> integer -- return first index of value. + + Raises ValueError if the value is not present. + + """ + + try: + i, v = self._bisect_left(value) + except TypeError: + raise ValueError + i = self._advance(i, value) + if i >= 0: + return i + raise ValueError + + def count(self, value): + """L.count(value) -> integer -- return number of occurrences of value""" + try: + i, _ = self._bisect_left(value) + except TypeError: + return 0 + key = self._u2key(value) + count = 0 + while True: + i = self._advance(i, value) + if i == -1: + return count + count += 1 + i += 1 + + def pop(self, index=-1): + """L.pop([index]) -> item -- remove and return item at index (default last). + + Raises IndexError if list is empty or index is out of range. + + """ + + rv = self[index] + del self[index] + return rv + + def __delslice__(self, i, j): + """x.__delslice__(i, j) <==> del x[i:j] + + Use of negative indices is not supported. + + """ + del self._blist[i:j] + + def __delitem__(self, i): + """x.__delitem__(y) <==> del x[y]""" + del self._blist[i] + +class _weaksortedbase(_sortedbase): + def _bisect_left(self, value): + key = self._u2key(value) + lo = 0 + hi = len(self._blist) + while lo < hi: + mid = (lo+hi)//2 + n, v = self._squeeze(mid) + hi -= n + if n and hi == len(self._blist): + continue + if self._i2key(self._blist[mid]) < key: lo = mid+1 + else: hi = mid + n, v = self._squeeze(lo) + return lo, v + + def _bisect_right(self, value): + key = self._u2key(value) + lo = 0 + hi = len(self._blist) + while lo < hi: + mid = (lo+hi)//2 + n, v = self._squeeze(mid) + hi -= n + if n and hi == len(self._blist): + continue + if key < self._i2key(self._blist[mid]): hi = mid + else: lo = mid+1 + n, v = self._squeeze(lo) + return lo, v + + _bisect = _bisect_right + + def _u2i(self, value): + if self._key is None: + return weakref.ref(value) + else: + return (self._key(value), weakref.ref(value)) + + def _i2u(self, value): + if self._key is None: + return value() + else: + return value[1]() + + def _i2key(self, value): + if self._key is None: + return value() + else: + return value[0] + + def __iter__(self): + """ x.__iter__() <==> iter(x)""" + i = 0 + while i < len(self._blist): + n, v = self._squeeze(i) + if v is None: break + yield v + i += 1 + + def _squeeze(self, i): + n = 0 + while i < len(self._blist): + v = self._i2u(self._blist[i]) + if v is None: + del self._blist[i] + n += 1 + else: + return n, v + return n, None + + def __getitem__(self, index): + """x.__getitem__(y) <==> x[y]""" + if isinstance(index, slice): + return _sortedbase.__getitem__(self, index) + n, v = self._squeeze(index) + if v is None: + raise IndexError('list index out of range') + return v + + def __reversed__(self): + """L.__reversed__() -- return a reverse iterator over the list""" + i = len(self._blist)-1 + while i >= 0: + n, v = self._squeeze(i) + if not n: + yield v + i -= 1 + + def _advance(self, i, value): + "Do a linear search through all items with the same key" + key = self._u2key(value) + while i < len(self._blist): + n, v = self._squeeze(i) + if v is None: + break + if v == value: + return i + elif key < self._i2key(self._blist[i]): + break + i += 1 + return -1 + +class _listmixin(object): + def remove(self, value): + """L.remove(value) -- remove first occurrence of value. + + Raises ValueError if the value is not present. + """ + + del self[self.index(value)] + + def update(self, iterable): + """L.update(iterable) -- add all elements from iterable into the list""" + + for item in iterable: + self.add(item) + + def __mul__(self, k): + if not isinstance(k, int): + raise TypeError("can't multiply sequence by non-int of type '%s'" + % str(type(int))) + rv = self.__class__() + rv._key = self._key + rv._blist = sum((blist([x])*k for x in self._blist), blist()) + return rv + __rmul__ = __mul__ + + def __imul__(self, k): + if not isinstance(k, int): + raise TypeError("can't multiply sequence by non-int of type '%s'" + % str(type(int))) + self._blist = sum((blist([x])*k for x in self._blist), blist()) + return self + + def __eq__(self, other): + """x.__eq__(y) <==> x==y""" + return self._cmp_op(other, operator.eq) + def __ne__(self, other): + """x.__ne__(y) <==> x!=y""" + return self._cmp_op(other, operator.ne) + def __lt__(self, other): + """x.__lt__(y) <==> x<y""" + return self._cmp_op(other, operator.lt) + def __gt__(self, other): + """x.__gt__(y) <==> x>y""" + return self._cmp_op(other, operator.gt) + def __le__(self, other): + """x.__le__(y) <==> x<=y""" + return self._cmp_op(other, operator.le) + def __ge__(self, other): + """x.__ge__(y) <==> x>=y""" + return self._cmp_op(other, operator.ge) + +class _setmixin(object): + "Methods that override our base class" + + def add(self, value): + """Add an element to the set. + + This has no effect if the element is already present. + + """ + if value in self: return + super(_setmixin, self).add(value) + + def __iter__(self): + it = super(_setmixin, self).__iter__() + while True: + item = next(it) + n = len(self) + yield item + if n != len(self): + raise RuntimeError('Set changed size during iteration') + +def safe_cmp(f): + def g(self, other): + if not isinstance(other, collections.Set): + raise TypeError("can only compare to a set") + return f(self, other) + return g + +class _setmixin2(collections.MutableSet): + "methods that override or supplement the collections.MutableSet methods" + + __ror__ = collections.MutableSet.__or__ + __rand__ = collections.MutableSet.__and__ + __rxor__ = collections.MutableSet.__xor__ + + if sys.version_info[0] < 3: # pragma: no cover + __lt__ = safe_cmp(collections.MutableSet.__lt__) + __gt__ = safe_cmp(collections.MutableSet.__gt__) + __le__ = safe_cmp(collections.MutableSet.__le__) + __ge__ = safe_cmp(collections.MutableSet.__ge__) + + def __ior__(self, it): + if self is it: + return self + for value in it: + self.add(value) + return self + + def __isub__(self, it): + if self is it: + self.clear() + return self + for value in it: + self.discard(value) + return self + + def __ixor__(self, it): + if self is it: + self.clear() + return self + for value in it: + if value in self: + self.discard(value) + else: + self.add(value) + return self + + def __rsub__(self, other): + return self._from_iterable(other) - self + + def _make_set(self, iterable): + if isinstance(iterable, collections.Set): + return iterable + return self._from_iterable(iterable) + + def difference(self, *args): + """Return a new set with elements in the set that are not in the others.""" + rv = self.copy() + rv.difference_update(*args) + return rv + + def intersection(self, *args): + """Return a new set with elements common to the set and all others.""" + rv = self.copy() + rv.intersection_update(*args) + return rv + + def issubset(self, other): + """Test whether every element in the set is in *other*.""" + return self <= self._make_set(other) + + def issuperset(self, other): + """Test whether every element in *other* is in the set.""" + return self >= self._make_set(other) + + def symmetric_difference(self, other): + """Return a new set with elements in either the set or *other* + but not both.""" + + return self ^ self._make_set(other) + + def union(self, *args): + """Return the union of sets as a new set. + + (i.e. all elements that are in either set.) + + """ + rv = self.copy() + for arg in args: + rv |= self._make_set(arg) + return rv + + def update(self, *args): + """Update the set, adding elements from all others.""" + for arg in args: + self |= self._make_set(arg) + + def difference_update(self, *args): + """Update the set, removing elements found in others.""" + for arg in args: + self -= self._make_set(arg) + + def intersection_update(self, *args): + """Update the set, keeping only elements found in it and all others.""" + for arg in args: + self &= self._make_set(arg) + + def symmetric_difference_update(self, other): + """Update the set, keeping only elements found in either set, + but not in both.""" + + self ^= self._make_set(other) + + def clear(self): + """Remove all elements""" + del self._blist[:] + + def copy(self): + return self[:] + +class sortedlist(_sortedbase, _listmixin): + """sortedlist(iterable=(), key=None) -> new sorted list + + Keyword arguments: + iterable -- items used to initially populate the sorted list + key -- a function to return the sort key of an item + + A sortedlist is indexable like a list, but always keeps its + members in sorted order. + + """ + + def __repr__(self): + """x.__repr__() <==> repr(x)""" + if not self: return 'sortedlist()' + with ReprRecursion(self) as r: + if r: return 'sortedlist(...)' + return ('sortedlist(%s)' % repr(list(self))) + + def _cmp_op(self, other, op): + if not (isinstance(other,type(self)) or isinstance(self,type(other))): + return NotImplemented + if len(self) != len(other): + if op is operator.eq: + return False + if op is operator.ne: + return True + for x, y in izip(self, other): + if x != y: + return op(x, y) + return op in (operator.eq, operator.le, operator.ge) + +class weaksortedlist(_listmixin, _weaksortedbase): + """weaksortedlist(iterable=(), key=None) -> new sorted weak list + + Keyword arguments: + iterable -- items used to initially populate the sorted list + key -- a function to return the sort key of an item + + A weaksortedlist is indexable like a list, but always keeps its + items in sorted order. The weaksortedlist weakly references its + members, so items will be discarded after there is no longer a + strong reference to the item. + + """ + + def __repr__(self): + """x.__repr__() <==> repr(x)""" + if not self: return 'weaksortedlist()' + with ReprRecursion(self) as r: + if r: return 'weaksortedlist(...)' + return 'weaksortedlist(%s)' % repr(list(self)) + + def _cmp_op(self, other, op): + if not (isinstance(other,type(self)) or isinstance(self,type(other))): + return NotImplemented + for x, y in izip(self, other): + if x != y: + return op(x, y) + return op in (operator.eq, operator.le, operator.ge) + +class sortedset(_setmixin, _sortedbase, _setmixin2): + """sortedset(iterable=(), key=None) -> new sorted set + + Keyword arguments: + iterable -- items used to initially populate the sorted set + key -- a function to return the sort key of an item + + A sortedset is similar to a set but is also indexable like a list. + Items are maintained in sorted order. + + """ + + def __repr__(self): + """x.__repr__() <==> repr(x)""" + if not self: return 'sortedset()' + with ReprRecursion(self) as r: + if r: return 'sortedset(...)' + return ('sortedset(%s)' % repr(list(self))) + +class weaksortedset(_setmixin, _weaksortedbase, _setmixin2): + """weaksortedset(iterable=(), key=None) -> new sorted weak set + + Keyword arguments: + iterable -- items used to initially populate the sorted set + key -- a function to return the sort key of an item + + A weaksortedset is similar to a set but is also indexable like a + list. Items are maintained in sorted order. The weaksortedset + weakly references its members, so items will be discarded after + there is no longer a strong reference to the item. + + """ + + def __repr__(self): + """x.__repr__() <==> repr(x)""" + if not self: return 'weaksortedset()' + with ReprRecursion(self) as r: + if r: return 'weaksortedset(...)' + return 'weaksortedset(%s)' % repr(list(self)) |