Skip to content

Instantly share code, notes, and snippets.

@Zearin

Zearin/OrderedSet.py

Last active December 17, 2015 01:09
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Zearin/5526263 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Zearin/5526263 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Tony revised this gist May 6, 2013. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion OrderedSet.py
    View file
    Original file line number Diff line number Diff line change
    @@ -6,7 +6,7 @@
    try:
    import collections.abc as collections # Python 3
    except ImportError:
    import collections as # Python 2
    import collections # Python 2


    class OrderedSet(collections.MutableSet):
  2. Tony renamed this gist May 6, 2013. 1 changed file with 0 additions and 0 deletions.
    0 python-OrderedSet → OrderedSet.py
    View file
    File renamed without changes.
  3. Tony created this gist May 6, 2013.
    85 changes: 85 additions & 0 deletions python-OrderedSet
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,85 @@
    # -*- 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 as # 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"