API reference

class linkedset.DoublyLinkedSet(values=None)

Bases: Sequence[_T], MutableSet[_T], Generic[_T]

A doubly linked ordered set of nodes.

The container is both a collections.abc.Sequence (ordered, indexable) and a collections.abc.MutableSet. It does not allow duplicate values and maintains insertion order. One can treat it as a doubly linked list with list-like methods, or as a mutable set supporting &, |, -, ^ and their in-place variants.

Adding and removing elements from the set during iteration is safe. Moving elements from one set to another is also safe.

During the iteration:

• If new elements are inserted after the current node, the iterator will iterate over them as well.

• If new elements are inserted before the current node, they will not be iterated over in this iteration.

• If the current node is lifted and inserted in a different location, iteration will start from the “next” node at the _original_ location.

Time complexity:

Inserting and removing nodes from the set is O(1). Accessing nodes by index is O(n), although accessing nodes at either end of the set is O(1). I.e. linked_set[0] and linked_set[-1] are O(1).

Membership, uniqueness and set operations are based on value equality (==), not object identity. Two objects that compare equal are treated as the same element, and elements must be hashable (they are used as keys in an internal dict that gives O(1) membership and mutation). Because it is a mutable set, instances of DoublyLinkedSet are themselves not hashable. Since the set is ordered, == is order-sensitive: two sets are equal only when they hold the same elements (by value) in the same order. None is not a valid value in the set.

Parameters:

values (Iterable[_T] | None)

__iter__()

Iterate over the elements in the list.

• If new elements are inserted after the current node, the iterator will iterate over them as well.

• If new elements are inserted before the current node, they will not be iterated over in this iteration.

• If the current node is lifted and inserted in a different location, iteration will start from the “next” node at the _original_ location.

Return type:

Iterator[_T]

__reversed__()

Iterate over the elements in the list in reverse order.

Return type:

Iterator[_T]

__contains__(value)

Return whether value is in the set using value equality (O(1)).

Parameters:

value (object)

Return type:

bool

__eq__(other)

Return whether other is an equal, equally-ordered set.

Because DoublyLinkedSet is ordered, equality is order-sensitive (unlike a plain set). Two sets are equal only when they contain the same elements by value equality, in the same order. Only another DoublyLinkedSet can compare equal.

Parameters:

other (object)

Return type:

bool

count(value)

Return the number of occurrences of value (0 or 1) using value equality (O(1)).

Parameters:

value (object)

Return type:

int

index(value, start=0, stop=None)

Return the index of value in the set using value equality.

Raises:

ValueError – If value is not present in self[start:stop].

Parameters:

• value (object)

• start (int)

• stop (int | None)

Return type:

int

__getitem__(index: int) → _T

__getitem__(index: slice) → Sequence[_T]

Get the node at the given index.

Complexity is O(n).

remove(value)

Remove a node from the list.

Parameters:

value (_T)

Return type:

None

add(value)

Add value to the end of the set if it is not already present.

Unlike append(), this is idempotent: if value (by equality) is already in the set, its position is left unchanged. This implements collections.abc.MutableSet.add().

Parameters:

value (_T)

Return type:

None

discard(value)

Remove value from the set if it is present, without raising otherwise.

This implements collections.abc.MutableSet.discard().

Parameters:

value (_T)

Return type:

None

append(value)

Append a node to the list.

Parameters:

value (_T)

Return type:

None

appendleft(value)

Add value to the front of the set (deque-style).

If value is already present (by equality), it is moved to the front.

Parameters:

value (_T)

Return type:

None

extendleft(values)

Prepend each value in values to the front of the set (deque-style).

As with collections.deque.extendleft(), the prepended items end up in reverse order relative to values.

Parameters:

values (Iterable[_T])

Return type:

None

insert(index, value)

Insert value before position index (list/deque-style).

index is clamped like list.insert(). If value is already present it is removed first, so index refers to a position in the resulting sequence.

Parameters:

• index (int)

• value (_T)

Return type:

None

pop(index=-1)

Remove and return the value at index (default: the last one, list-style).

Raises:

IndexError – If the set is empty or index is out of range.

Parameters:

index (int)

Return type:

_T

popleft()

Remove and return the first value (deque-style).

Raises:

IndexError – If the set is empty.

Return type:

_T

clear()

Remove all elements from the set.

Safe to call during iteration: existing nodes are marked erased (so a live iterator stops yielding them) before the set is reset.

Return type:

None

reverse()

Reverse the elements of the set in place.

Note

Unlike per-element mutation, this is a global reorder and is not safe to call while iterating over the set: an in-progress iterator may then skip or repeat elements.

Return type:

None

rotate(n=1)

Rotate the set n steps to the right (deque-style).

Negative n rotates to the left. rotate(1) moves the last element to the front.

Note

Like reverse(), this is a global reorder and is not safe to call while iterating over the set.

Parameters:

n (int)

Return type:

None

copy()

Return a shallow copy of the set, preserving order.

Return type:

DoublyLinkedSet[_T]

isdisjoint(other)

Return True if the set has no elements (by equality) in common with other.

Parameters:

other (Iterable[_T])

Return type:

bool

insert_after(value, new_values)

Insert new nodes after the given node.

Parameters:

• value (_T) – The value after which the new values are to be inserted.

• new_values (Iterable[_T]) – The new values to be inserted.

Return type:

None

insert_before(value, new_values)

Insert new nodes before the given node.

Parameters:

• value (_T) – The value before which the new values are to be inserted.

• new_values (Iterable[_T]) – The new values to be inserted.

Return type:

None