ubelt.orderedset module

class ubelt.orderedset.OrderedSet(iterable=None)

Bases: collections.abc.MutableSet

Set the remembers the order elements were added

Big-O running times for all methods are the same as for regular sets. The internal self._map dictionary maps keys to links in a doubly linked list. The circular doubly linked list starts and ends with a sentinel element. The sentinel element never gets deleted (this simplifies the algorithm). The prev/next links are weakref proxies (to prevent circular references). Individual links are kept alive by the hard reference in self._map. Those hard references disappear when a key is deleted from an OrderedSet.

References

http://code.activestate.com/recipes/576696/ http://code.activestate.com/recipes/576694/ http://stackoverflow.com/questions/1653970/does-python-have-an-ordered-set

Example

>>> from ubelt.orderedset import *
>>> oset([1, 2, 3])
OrderedSet([1, 2, 3])

isdisjoint(other)

add(key)

Adds an element to the ends of the ordered set if it. This has no effect if the element is already present.

Example

>>> self = OrderedSet()
>>> self.append(3)
>>> print(self)
OrderedSet([3])

append(key)

Adds an element to the ends of the ordered set if it. This has no effect if the element is already present.

Notes

This is an alias of add for API compatibility with list

Example

>>> self = OrderedSet()
>>> self.append(3)
>>> self.append(2)
>>> self.append(5)
>>> print(self)
OrderedSet([3, 2, 5])

discard(key)

Remove an element from a set if it is a member. If the element is not a member, do nothing.

Example

>>> self = OrderedSet([1, 2, 3])
>>> self.discard(2)
>>> print(self)
OrderedSet([1, 3])
>>> self.discard(2)
>>> print(self)
OrderedSet([1, 3])

pop(last=True)

Remove and return a the first or last element in the ordered set. Raises KeyError if the set is empty.

Parameters:last (bool) – if True return the last element otherwise the first (defaults to True).

Example

>>> import pytest
>>> self = oset([2, 3, 1])
>>> assert self.pop(last=True) == 1
>>> assert self.pop(last=False) == 2
>>> assert self.pop() == 3
>>> with pytest.raises(KeyError):
...     self.pop()

union(*sets)

Combines all unique items. Each items order is defined by its first appearance.

Example

>>> self = OrderedSet.union(oset([3, 1, 4, 1, 5]), [1, 3], [2, 0])
>>> print(self)
OrderedSet([3, 1, 4, 5, 2, 0])
>>> self.union([8, 9])
OrderedSet([3, 1, 4, 5, 2, 0, 8, 9])
>>> self | {10}
OrderedSet([3, 1, 4, 5, 2, 0, 10])

intersection(*sets)

Returns elements in common between all sets. Order is defined only by the first set.

Example

>>> self = OrderedSet.intersection(oset([0, 1, 2, 3]), [1, 2, 3])
>>> print(self)
OrderedSet([1, 2, 3])
>>> self.intersection([2, 4, 5], [1, 2, 3, 4])
OrderedSet([2])

update(other)

Update a set with the union of itself and others. Preserves ordering of other.

Example

>>> self = OrderedSet([1, 2, 3])
>>> self.update([3, 1, 5, 1, 4])
>>> print(self)
OrderedSet([1, 2, 3, 5, 4])

extend(other)

Update a set with the union of itself and others. Preserves ordering of other.

Example

>>> self = OrderedSet([1, 2, 3])
>>> self.update([3, 1, 5, 1, 4])
>>> print(self)
OrderedSet([1, 2, 3, 5, 4])

index(item)

Find the index of item in the OrderedSet

Example

>>> import pytest
>>> self = oset([1, 2, 3])
>>> assert self.index(1) == 0
>>> assert self.index(2) == 1
>>> assert self.index(3) == 2
>>> with pytest.raises(IndexError):
...     self[4]

copy()

Return a shallow copy of the ordered set.

Example

>>> self = OrderedSet([1, 2, 3])
>>> other = self.copy()
>>> assert self == other and self is not other

difference(*sets)

Returns all elements that are in this set but not the others.

Example

>>> OrderedSet([1, 2, 3]).difference(OrderedSet([2]))
OrderedSet([1, 3])
>>> OrderedSet([1, 2, 3]) - OrderedSet([2])
OrderedSet([1, 3])

issubset(other)

Report whether another set contains this set.

Example

>>> OrderedSet([1, 2, 3]).issubset({1, 2})
False
>>> OrderedSet([1, 2, 3]).issubset({1, 2, 3, 4})
True
>>> OrderedSet([1, 2, 3]).issubset({1, 4, 3, 5})
False

issuperset(other)

Report whether this set contains another set.

Example

>>> OrderedSet([1, 2]).issuperset([1, 2, 3])
False
>>> OrderedSet([1, 2, 3, 4]).issuperset({1, 2, 3})
True
>>> OrderedSet([1, 4, 3, 5]).issuperset({1, 2, 3})
False

symmetric_difference(other)

Return the symmetric difference of two sets as a new set. (I.e. all elements that are in exactly one of the sets.)

Example

>>> self = OrderedSet([1, 4, 3, 5, 7])
>>> other = OrderedSet([9, 7, 1, 3, 2])
>>> self.symmetric_difference(other)
OrderedSet([4, 5, 9, 2])

difference_update(*sets)

Returns a copy of self with items from other removed

Example

>>> self = OrderedSet([1, 2, 3])
>>> self.difference_update(OrderedSet([2]))
>>> print(self)
OrderedSet([1, 3])

intersection_update(other)

Update a set with the intersection of itself and another. Order depends only on the first element

Example

>>> self = OrderedSet([1, 4, 3, 5, 7])
>>> other = OrderedSet([9, 7, 1, 3, 2])
>>> self.intersection_update(other)
>>> print(self)
OrderedSet([1, 3, 7])

symmetric_difference_update(other)

Update a set with the intersection of itself and another. Order depends only on the first element

Example

>>> self = OrderedSet([1, 4, 3, 5, 7])
>>> other = OrderedSet([9, 7, 1, 3, 2])
>>> self.symmetric_difference_update(other)
>>> print(self)
OrderedSet([4, 5, 9, 2])

ubelt.orderedset.oset

alias of OrderedSet