Last active
December 17, 2015 01:09
-
-
Save Zearin/5526263 to your computer and use it in GitHub Desktop.
An OrderedSet for Python.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # -*- coding: utf-8 -*- | |
| # Modified from original source, available here: | |
| # http://code.activestate.com/recipes/577624-orderedset/ | |
| try: | |
| import collections.abc as collections # Python 3 | |
| except ImportError: | |
| import collections # Python 2 | |
| class OrderedSet(collections.MutableSet): | |
| '''Set that remembers original insertion order.''' | |
| KEY, PREV, NEXT = range(3) | |
| def __init__(self, iterable=None): | |
| self.end = end = [] | |
| end += [None, end, end] # sentinel node for doubly linked list | |
| self.map = {} # key --> [key, prev, next] | |
| if iterable is not None: | |
| self |= iterable | |
| ### Collection Methods | |
| def __contains__(self, key): | |
| return key in self.map | |
| def __eq__(self, other): | |
| if isinstance(other, OrderedSet): | |
| return len(self) == len(other) and list(self) == list(other) | |
| return set(self) == set(other) | |
| def __iter__(self): | |
| end = self.end | |
| curr = end[self.NEXT] | |
| while curr is not end: | |
| yield curr[self.KEY] | |
| curr = curr[self.NEXT] | |
| def __len__(self): | |
| return len(self.map) | |
| def __reversed__(self): | |
| end = self.end | |
| curr = end[self.PREV] | |
| while curr is not end: | |
| yield curr[self.KEY] | |
| curr = curr[self.PREV] | |
| def add(self, key): | |
| if key not in self.map: | |
| end = self.end | |
| curr = end[self.PREV] | |
| curr[self.NEXT] = end[self.PREV] = self.map[key] = [key, curr, end] | |
| def discard(self, key): | |
| if key in self.map: | |
| key, prev, next = self.map.pop(key) | |
| prev[self.NEXT] = next | |
| next[self.PREV] = prev | |
| def pop(self, last=True): | |
| if not self: | |
| raise KeyError('set is empty') | |
| key = next(reversed(self)) if last else next(iter(self)) | |
| self.discard(key) | |
| return key | |
| ### General Methods | |
| def __del__(self): | |
| self.clear() # remove circular references | |
| def __repr__(self): | |
| class_name = self.__class__.__name__ | |
| if not self: | |
| return '{0!s}()'.format(class_name) | |
| return '{0!s}({1!r})'.format(class_name, list(self)) | |
| if __name__ == '__main__': | |
| print(OrderedSet('abracadaba')) | |
| print(OrderedSet('simsalabim')) | |
| x = OrderedSet('abracadaba') | |
| # doesn't raise "Exception TypeError: TypeError('list indices must be integers, not NoneType',) in ignored" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment