| 24 | |
| 25 | |
| 26 | class OrderedSet(MutableSet): |
| 27 | def __init__(self, iterable=None): |
| 28 | self.end = end = [] |
| 29 | end += [None, end, end] # sentinel node for doubly linked list |
| 30 | self.map = {} # key --> [key, prev, next] |
| 31 | if iterable is not None: |
| 32 | self |= iterable |
| 33 | |
| 34 | def __len__(self): |
| 35 | return len(self.map) |
| 36 | |
| 37 | def __contains__(self, key): |
| 38 | return key in self.map |
| 39 | |
| 40 | def add(self, key): |
| 41 | if key not in self.map: |
| 42 | end = self.end |
| 43 | curr = end[1] |
| 44 | curr[2] = end[1] = self.map[key] = [key, curr, end] |
| 45 | |
| 46 | def discard(self, key): |
| 47 | if key in self.map: |
| 48 | key, prev, next = self.map.pop(key) |
| 49 | prev[2] = next |
| 50 | next[1] = prev |
| 51 | |
| 52 | def __iter__(self): |
| 53 | end = self.end |
| 54 | curr = end[2] |
| 55 | while curr is not end: |
| 56 | yield curr[0] |
| 57 | curr = curr[2] |
| 58 | |
| 59 | def __reversed__(self): |
| 60 | end = self.end |
| 61 | curr = end[1] |
| 62 | while curr is not end: |
| 63 | yield curr[0] |
| 64 | curr = curr[1] |
| 65 | |
| 66 | def pop(self, last=True): |
| 67 | if not self: |
| 68 | raise KeyError("set is empty") |
| 69 | key = self.end[1][0] if last else self.end[2][0] |
| 70 | self.discard(key) |
| 71 | return key |
| 72 | |
| 73 | def __repr__(self): |
| 74 | if not self: |
| 75 | return "%s()" % (self.__class__.__name__,) |
| 76 | return "%s(%r)" % (self.__class__.__name__, list(self)) |
| 77 | |
| 78 | def __eq__(self, other): |
| 79 | if isinstance(other, OrderedSet): |
| 80 | return len(self) == len(other) and list(self) == list(other) |
| 81 | return set(self) == set(other) |
no outgoing calls