diff options
author | Benjamin Schwartz <bens@alum.mit.edu> | 2008-02-16 16:40:30 (GMT) |
---|---|---|
committer | Benjamin Schwartz <bens@alum.mit.edu> | 2008-02-16 16:40:30 (GMT) |
commit | 36d533def2139ccb93e46a97c70fa2865d34b44c (patch) | |
tree | 8d0524f5fbf2f21ea31f56e62a3f226818493123 | |
parent | b46d6e16e08f70ceeb1adc97287cdc3ce39ebd77 (diff) |
Add file dobject_helpers
-rw-r--r-- | dobject_helpers.py | 401 |
1 files changed, 401 insertions, 0 deletions
diff --git a/dobject_helpers.py b/dobject_helpers.py new file mode 100644 index 0000000..2c5ba86 --- /dev/null +++ b/dobject_helpers.py @@ -0,0 +1,401 @@ +""" +Copyright 2008 Benjamin M. Schwartz + +This file is LGPLv2+. This file, dobject_helpers.py, is part of DObject. + +DObject is free software: you can redistribute it and/or modify +it under the terms of the GNU Lesser General Public License as published by +the Free Software Foundation, either version 2 of the License, or +(at your option) any later version. + +DObject is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU Lesser General Public License +along with DObject. If not, see <http://www.gnu.org/licenses/>. +""" + +import bisect + +""" +dobject_helpers is a collection of functions and data structures that are useful +to DObject, but are not specific to DBus or networked applications. +""" + +def merge(a, b, l=True, g=True, e=True): + """Internal helper function for combining sets represented as sorted lists""" + x = 0 + X = len(a) + if X == 0: + if g: + return list(b) + else: + return [] + y = 0 + Y = len(b) + if Y == 0: + if l: + return list(a) + else: + return [] + out = [] + p = a[x] + q = b[y] + while x < X and y < Y: + if p < q: + if l: out.append(p) + x += 1 + if x < X: p = a[x] + elif p > q: + if g: out.append(q) + y += 1 + if y < Y: q = b[y] + else: + if e: out.append(p) + x += 1 + if x < X: p = a[x] + y += 1 + if y < Y: q = b[y] + if x < X: + if l: out.extend(a[x:]) + else: + if g: out.extend(b[y:]) + return out + +def merge_or(a,b): + return merge(a,b, True, True, True) + +def merge_xor(a,b): + return merge(a, b, True, True, False) + +def merge_and(a,b): + return merge(a, b, False, False, True) + +def merge_sub(a,b): + return merge(a, b, True, False, False) + +def kill_dupes(a): #assumes a is sorted + """Internal helper function for removing duplicates in a sorted list""" + prev = a[0] + out = [prev] + for i in xrange(1, len(a)): + item = a[i] + if item != prev: + out.append(item) + prev = item + return out + +class Comparable: + """Currently, ListSet does not provide a mechanism for specifying a + comparator. Users who would like to specify a comparator other than the one + native to the item may do so by wrapping the item in a Comparable. + """ + def __init__(self, item, comparator): + self.item = item + self._cmp = comparator + + def __cmp__(self, other): + return self._cmp(self.item, other) + +class ListSet: + """ListSet is a sorted set for comparable items. It is inspired by the + Java Standard Library's TreeSet. However, it is implemented by a sorted + list. This implementation is much slower than a balanced binary tree, but + has the distinct advantage that I can actually implement it. + + The methods of ListSet are all drawn directly from Python's set API, + Python's list API, and Java's SortedSet API. + """ + def __init__(self, seq=[]): + L = list(seq) + if len(L) > 1: + L.sort() + L = kill_dupes(L) + self._list = L + + def __and__(self, someset): + if someset.__class__ == self.__class__: + L = merge_and(self._list, someset._list) + else: + L = [] + for x in self._list: + if x in someset: + L.append(x) + a = ListSet() + a._list = L + return a + + def __contains__(self, item): + if len(self._list) == 0: + return False + if self._list[0] <= item <= self._list[-1]: + a = bisect.bisect_left(self._list, item) + return item == self._list[a] + else: + return False + + def __eq__(self, someset): + if someset.__class__ == self.__class__: + return self._list == someset._list + else: + return len(self.symmetric_difference(someset)) == 0 + + def __ge__(self, someset): + if someset.__class__ == self.__class__: + return len(merge_or(self._list, someset._list)) == len(self._list) + else: + a = len(someset) + k = 0 + for i in self._list: + if i in someset: + k += 1 + return k == a + + def __gt__(self, someset): + return (len(self) > len(someset)) and (self >= someset) + + def __iand__(self, someset): + if someset.__class__ == self.__class__: + self._list = merge_and(self._list, someset._list) + else: + L = [] + for i in self._list: + if i in someset: + L.append(i) + self._list = L + + def __ior__(self, someset): + if someset.__class__ == self.__class__: + self._list = merge_or(self._list, someset._list) + else: + self.update(someset) + + def __isub__(self, someset): + if someset.__class__ == self.__class__: + self._list = merge_sub(self._list, someset._list) + else: + L = [] + for i in self._list: + if i in someset: + L.append(i) + self._list = merge_sub(self._list, L) + + def __iter__(self): + return self._list.__iter__() + + def __ixor__(self, someset): + if someset.__class__ == self.__class__: + self._list = merge_xor(self._list, someset._list) + else: + L = [] + for i in self._list: + if i in someset: + L.append(i) + self._list = merge_sub(self._list, L) + + def __le__(self, someset): + if someset.__class__ == self.__class__: + return len(merge_or(self._list, someset._list)) == len(someset._list) + else: + for i in self._list: + if i not in someset: + return False + return True + + def __lt__(self, someset): + return (len(self) < len(someset)) and (self <= someset) + + def __ne__(self, someset): + return not (self == someset) + + def __len__(self): + return len(self._list) + + def __or__(self, someset): + a = ListSet() + if someset.__class__ == self.__class__: + a._list = merge_or(self._list, someset._list) + else: + a._list = self._list + a.update(someset) + return a + + __rand__ = __and__ + + def __repr__(self): + return "ListSet(" + repr(self._list) +")" + + __ror__ = __or__ + + def __rsub__(self, someset): + if someset.__class__ == self.__class__: + a = ListSet() + a._list = merge_sub(someset._list, self._list) + else: + a = ListSet(someset) + a._list = merge_sub(a._list, self._list) + return a + + def __sub__(self, someset): + a = ListSet() + if someset.__class__ == self.__class__: + a._list = merge_sub(self._list, someset._list) + else: + L = [] + for i in self._list: + if i in someset: + L.append(i) + a._list = merge_sub(self._list, L) + return a + + def __xor__(self, someset): + a = ListSet() + if someset.__class__ == self.__class__: + a._list = merge_xor(self._list, someset._list) + else: + a = self.symmetric_difference(someset) + return a + + __rxor__ = __xor__ + + def add(self, item): + if (len(self._list) > 0) and (item <= self._list[-1]): + a = bisect.bisect_left(self._list, item) + if self._list[a] != item: + self._list.insert(a, item) + else: + self._list.append(item) + + def clear(self): + self._list = [] + + def copy(self): + a = ListSet() + a._list = list(self._list) #shallow copy + return a + + def difference(self, iterable): + L = list(iterable) + L.sort() + a = ListSet() + a._list = merge_sub(self._list, kill_dupes(L)) + return a + + def difference_update(self, iterable): + L = list(iterable) + L.sort() + self._list = merge_sub(self._list, kill_dupes(L)) + + def discard(self, item): + if (len(self._list) > 0) and (item <= self._list[-1]): + a = bisect.bisect_left(self._list, item) + if self._list[a] == item: + self._list.remove(a) + + def intersection(self, iterable): + L = list(iterable) + L.sort() + a = ListSet() + a._list = merge_and(self._list, kill_dupes(L)) + + def intersection_update(self, iterable): + L = list(iterable) + L.sort() + self._list = merge_and(self._list, kill_dupes(L)) + + def issuperset(self, iterable): + L = list(iterable) + L.sort() + m = merge_or(self._list, kill_dupes(L)) + return len(m) == len(self._list) + + def issubset(self, iterable): + L = list(iterable) + L.sort() + L = kill_dupes(L) + m = merge_or(self._list, L) + return len(m) == len(L) + + def pop(self, i = None): + if i == None: + return self._list.pop() + else: + return self._list.pop(i) + + def remove(self, item): + if (len(self._list) > 0) and (item <= self._list[-1]): + a = bisect.bisect_left(self._list, item) + if self._list[a] == item: + self._list.remove(a) + return + raise KeyError("Item is not in the set") + + def symmetric_difference(self, iterable): + L = list(iterable) + L.sort() + a = ListSet() + a._list = merge_xor(self._list, kill_dupes(L)) + return a + + def symmetric_difference_update(self, iterable): + L = list(iterable) + L.sort() + self._list = merge_xor(self._list, kill_dupes(L)) + + def union(self, iterable): + L = list(iterable) + L.sort() + a = ListSet() + a._list = merge_or(self._list, kill_dupes(L)) + + def update(self, iterable): + L = list(iterable) + L.sort() + self._list = merge_or(self._list, kill_dupes(L)) + + def __getitem__(self, key): + if type(key) == int: + return self._list.__getitem__(key) + elif type(key) == slice: + a = ListSet() + L = self._list.__getitem__(key) + if key.step < 0: + L.reverse() + a._list = L + return a + + def __delitem__(self, key): + self._list.__delitem__(key) + + def index(self, x, i=0, j=-1): + if (len(self._list) > 0) and (x <= self._list[-1]): + a = bisect.bisect_left(self._list, x, i, j) + if self._list[a] == x: + return a + raise ValueError("Item not found") + + def position(self, x, i=0, j=-1): + return bisect.bisect_left(self._list, x, i, j) + + def subset(self, x, y): + a = bisect.bisect_left(self._list, x) + b = bisect.bisect_left(self._list, y) + s = ListSet() + s._list = self._list[a:b] + return s + + def first(self): + return self._list[0] + + def last(self): + return self._list[-1] + + def headset(self, x): + a = bisect.bisect_left(self._list, x, i, j) + return self[:a] + + def tailset(self, x): + a = bisect.bisect_left(self._list, x, i, j) + return self[a:] |