| 41 | from bisect import bisect_left, insort_left |
| 42 | |
| 43 | class Set(object): |
| 44 | |
| 45 | def __init__(self, iterable): |
| 46 | data = list(iterable) |
| 47 | data.sort() |
| 48 | result = data[:1] |
| 49 | for elem in data[1:]: |
| 50 | if elem == result[-1]: |
| 51 | continue |
| 52 | result.append(elem) |
| 53 | self.data = result |
| 54 | |
| 55 | def __repr__(self): |
| 56 | return 'Set(' + repr(self.data) + ')' |
| 57 | |
| 58 | def __iter__(self): |
| 59 | return iter(self.data) |
| 60 | |
| 61 | def __contains__(self, elem): |
| 62 | data = self.data |
| 63 | i = bisect_left(self.data, elem, 0) |
| 64 | return i<len(data) and data[i] == elem |
| 65 | |
| 66 | def add(self, elem): |
| 67 | if elem not in self: |
| 68 | insort_left(self.data, elem) |
| 69 | |
| 70 | def remove(self, elem): |
| 71 | data = self.data |
| 72 | i = bisect_left(self.data, elem, 0) |
| 73 | if i<len(data) and data[i] == elem: |
| 74 | del data[i] |
| 75 | |
| 76 | def _getotherdata(other): |
| 77 | if not isinstance(other, Set): |
| 78 | other = Set(other) |
| 79 | return other.data |
| 80 | _getotherdata = staticmethod(_getotherdata) |
| 81 | |
| 82 | def __cmp__(self, other, cmp=cmp): |
| 83 | return cmp(self.data, Set._getotherdata(other)) |
| 84 | |
| 85 | def union(self, other, find=bisect_left): |
| 86 | i = j = 0 |
| 87 | x = self.data |
| 88 | y = Set._getotherdata(other) |
| 89 | result = Set([]) |
| 90 | append = result.data.append |
| 91 | extend = result.data.extend |
| 92 | try: |
| 93 | while 1: |
| 94 | if x[i] == y[j]: |
| 95 | append(x[i]) |
| 96 | i += 1 |
| 97 | j += 1 |
| 98 | elif x[i] > y[j]: |
| 99 | cut = find(y, x[i], j) |
| 100 | extend(y[j:cut]) |
no outgoing calls
no test coverage detected