Mercurial > repos > guerler > springsuite
comparison planemo/lib/python3.7/site-packages/galaxy/util/oset.py @ 1:56ad4e20f292 draft
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
| author | guerler |
|---|---|
| date | Fri, 31 Jul 2020 00:32:28 -0400 |
| parents | |
| children |
comparison
equal
deleted
inserted
replaced
| 0:d30785e31577 | 1:56ad4e20f292 |
|---|---|
| 1 """ | |
| 2 Ordered set implementation from https://code.activestate.com/recipes/576694/ | |
| 3 """ | |
| 4 import collections | |
| 5 | |
| 6 | |
| 7 class OrderedSet(collections.MutableSet): | |
| 8 def __init__(self, iterable=None): | |
| 9 self.end = end = [] | |
| 10 end += [None, end, end] # sentinel node for doubly linked list | |
| 11 self.map = {} # key --> [key, prev, next] | |
| 12 if iterable is not None: | |
| 13 self |= iterable | |
| 14 | |
| 15 def __len__(self): | |
| 16 return len(self.map) | |
| 17 | |
| 18 def __contains__(self, key): | |
| 19 return key in self.map | |
| 20 | |
| 21 def add(self, key): | |
| 22 if key not in self.map: | |
| 23 end = self.end | |
| 24 curr = end[1] | |
| 25 curr[2] = end[1] = self.map[key] = [key, curr, end] | |
| 26 | |
| 27 def discard(self, key): | |
| 28 if key in self.map: | |
| 29 key, prev, next = self.map.pop(key) | |
| 30 prev[2] = next | |
| 31 next[1] = prev | |
| 32 | |
| 33 def __iter__(self): | |
| 34 end = self.end | |
| 35 curr = end[2] | |
| 36 while curr is not end: | |
| 37 yield curr[0] | |
| 38 curr = curr[2] | |
| 39 | |
| 40 def __reversed__(self): | |
| 41 end = self.end | |
| 42 curr = end[1] | |
| 43 while curr is not end: | |
| 44 yield curr[0] | |
| 45 curr = curr[1] | |
| 46 | |
| 47 def pop(self, last=True): | |
| 48 if not self: | |
| 49 raise KeyError('set is empty') | |
| 50 key = self.end[1][0] if last else self.end[2][0] | |
| 51 self.discard(key) | |
| 52 return key | |
| 53 | |
| 54 def __repr__(self): | |
| 55 if not self: | |
| 56 return '%s()' % (self.__class__.__name__,) | |
| 57 return '%s(%r)' % (self.__class__.__name__, list(self)) | |
| 58 | |
| 59 def __eq__(self, other): | |
| 60 if isinstance(other, OrderedSet): | |
| 61 return len(self) == len(other) and list(self) == list(other) | |
| 62 return set(self) == set(other) |