| 1 |
#!/usr/bin/env python |
| 2 |
# vim:fileencoding=utf-8 |
| 3 |
|
| 4 |
|
| 5 |
__license__ = 'GPL v3' |
| 6 |
__copyright__ = '2015, Kovid Goyal <kovid at kovidgoyal.net>' |
| 7 |
|
| 8 |
import collections.abc |
| 9 |
|
| 10 |
from polyglot.builtins import string_or_bytes |
| 11 |
|
| 12 |
SLICE_ALL = slice(None) |
| 13 |
|
| 14 |
|
| 15 |
def is_iterable(obj): |
| 16 |
""" |
| 17 |
Are we being asked to look up a list of things, instead of a single thing? |
| 18 |
We check for the `__iter__` attribute so that this can cover types that |
| 19 |
don't have to be known by this module, such as NumPy arrays. |
| 20 |
|
| 21 |
Strings, however, should be considered as atomic values to look up, not |
| 22 |
iterables. |
| 23 |
""" |
| 24 |
return hasattr(obj, '__iter__') and not isinstance(obj, string_or_bytes) |
| 25 |
|
| 26 |
|
| 27 |
class OrderedSet(collections.abc.MutableSet): |
| 28 |
""" |
| 29 |
An OrderedSet is a custom MutableSet that remembers its order, so that |
| 30 |
every entry has an index that can be looked up. |
| 31 |
""" |
| 32 |
def __init__(self, iterable=None): |
| 33 |
self.items = [] |
| 34 |
self.map = {} |
| 35 |
if iterable is not None: |
| 36 |
for item in iterable: |
| 37 |
idx = self.map.get(item) |
| 38 |
if idx is None: |
| 39 |
self.map[item] = len(self.items) |
| 40 |
self.items.append(item) |
| 41 |
|
| 42 |
def __len__(self): |
| 43 |
return len(self.items) |
| 44 |
|
| 45 |
def __getitem__(self, index): |
| 46 |
""" |
| 47 |
Get the item at a given index. |
| 48 |
|
| 49 |
If `index` is a slice, you will get back that slice of items. If it's |
| 50 |
the slice [:], exactly the same object is returned. (If you want an |
| 51 |
independent copy of an OrderedSet, use `OrderedSet.copy()`.) |
| 52 |
|
| 53 |
If `index` is an iterable, you'll get the OrderedSet of items |
| 54 |
corresponding to those indices. This is similar to NumPy's |
| 55 |
"fancy indexing". |
| 56 |
""" |
| 57 |
if index == SLICE_ALL: |
| 58 |
return self |
| 59 |
elif hasattr(index, '__index__') or isinstance(index, slice): |
| 60 |
result = self.items[index] |
| 61 |
if isinstance(result, list): |
| 62 |
return OrderedSet(result) |
| 63 |
else: |
| 64 |
return result |
| 65 |
elif is_iterable(index): |
| 66 |
return OrderedSet([self.items[i] for i in index]) |
| 67 |
else: |
| 68 |
raise TypeError("Don't know how to index an OrderedSet by %r" % |
| 69 |
index) |
| 70 |
|
| 71 |
def copy(self): |
| 72 |
return OrderedSet(self) |
| 73 |
|
| 74 |
def __getstate__(self): |
| 75 |
return tuple(self) |
| 76 |
|
| 77 |
def __setstate__(self, state): |
| 78 |
self.__init__(state) |
| 79 |
|
| 80 |
def __contains__(self, key): |
| 81 |
return key in self.map |
| 82 |
|
| 83 |
def add(self, key): |
| 84 |
""" |
| 85 |
Add `key` as an item to this OrderedSet, then return its index. |
| 86 |
|
| 87 |
If `key` is already in the OrderedSet, return the index it already |
| 88 |
had. |
| 89 |
""" |
| 90 |
index = self.map.get(key) |
| 91 |
if index is None: |
| 92 |
self.map[key] = index = len(self.items) |
| 93 |
self.items.append(key) |
| 94 |
return index |
| 95 |
|
| 96 |
def index(self, key): |
| 97 |
""" |
| 98 |
Get the index of a given entry, raising an IndexError if it's not |
| 99 |
present. |
| 100 |
|
| 101 |
`key` can be an iterable of entries that is not a string, in which case |
| 102 |
this returns a list of indices. |
| 103 |
""" |
| 104 |
if is_iterable(key): |
| 105 |
return [self.index(subkey) for subkey in key] |
| 106 |
return self.map[key] |
| 107 |
|
| 108 |
def discard(self, key): |
| 109 |
index = self.map.get(key) |
| 110 |
if index is not None: |
| 111 |
self.items.pop(index) |
| 112 |
for item in self.items[index:]: |
| 113 |
self.map[item] -= 1 |
| 114 |
return True |
| 115 |
return False |
| 116 |
|
| 117 |
def __iter__(self): |
| 118 |
return iter(self.items) |
| 119 |
|
| 120 |
def __reversed__(self): |
| 121 |
return reversed(self.items) |
| 122 |
|
| 123 |
def __repr__(self): |
| 124 |
if not self: |
| 125 |
return '%s()' % (self.__class__.__name__,) |
| 126 |
return '%s(%r)' % (self.__class__.__name__, list(self)) |
| 127 |
|
| 128 |
def __eq__(self, other): |
| 129 |
if isinstance(other, OrderedSet): |
| 130 |
return len(self) == len(other) and self.items == other.items |
| 131 |
try: |
| 132 |
return type(other)(self.map) == other |
| 133 |
except TypeError: |
| 134 |
return False |