# Repository: https://gitlab.com/qblox/packages/software/qblox-scheduler
# Licensed according to the LICENSE file on the main branch
#
# Copyright 2025, Qblox B.V.
"""Doubly linked list."""
from __future__ import annotations
from collections.abc import Callable, Iterable, Iterator, MutableSequence
from itertools import islice
from typing import Any, Generic, TypeVar, overload
[docs]
class DLinkedListNode(Generic[T]):
"""A node in a ``DLinkedList``."""
__slots__ = ["__next", "__prev", "value"]
def __init__(
self,
value: T,
prev: DLinkedListNode[T] | None = None,
next: DLinkedListNode[T] | None = None, # noqa: A002
) -> None:
if self.__prev is not None:
self.__prev.__next = self
if self.__next is not None:
self.__next.__prev = self
@property
[docs]
def prev(self) -> DLinkedListNode[T] | None:
"""The node before this one."""
return self.__prev
@property
[docs]
def next(self) -> DLinkedListNode[T] | None:
"""The node after this one."""
return self.__next
def __del__(self) -> None:
if self.__prev and self.__next:
self.__prev.__next = self.__next
self.__next.__prev = self.__prev
elif self.__prev:
self.__prev.__next = None
elif self.__next:
self.__next.__prev = None
self.__prev = None
self.__next = None
self.value = None # type: ignore
[docs]
def reverse_from_head(self) -> None:
"""
If this node is the head of the list, reverse the list, turning this node into
the tail.
Note: if this node is not the head, throw an error.
"""
if self.prev is not None:
raise RuntimeError(
"Calling `reverse` on a node that is not the head of the list is not allowed."
)
current = self
while current:
current.__prev, current.__next = current.__next, current.__prev
current = current.__prev
def __str__(self) -> str:
return str(self.value)
def __repr__(self) -> str:
return f"<DLinkedListNode({self.value!r}, prev={self.prev!s}, next={self.next!s})>"
[docs]
class DLinkedList(MutableSequence[T]):
"""A doubly linked list."""
__slots__ = ["__head", "__size_cache", "__tail"]
def __init__(self, from_iterable: Iterable[T] | None = None) -> None:
[docs]
self.__head: DLinkedListNode[T] | None = None
[docs]
self.__tail: DLinkedListNode[T] | None = None
[docs]
self.__size_cache: int | None = None
if from_iterable is None:
return
for value in from_iterable:
node = DLinkedListNode(value, self.__tail, None)
if self.__head is None:
self.__head = node
self.__tail = node
def __str__(self) -> str:
return f"DLinkedList({self.__get_content_str(str)})"
def __repr__(self) -> str:
return f"<DLinkedList({self.__get_content_str(repr)})>"
[docs]
def __get_content_str(self, format_fn: Callable[[object], str]) -> str:
if self.__head is None:
return ""
node = self.__head
content_str = format_fn(node)
i = 1
while node.next and i < 10:
content_str += ", " + format_fn(node.next)
node = node.next
i += 1
if node.next:
content_str += ", ..."
return content_str
@property
[docs]
def size(self) -> int:
"""The length of this list."""
if self.__size_cache is not None:
return self.__size_cache
count = sum(1 for _ in self)
self.__size_cache = count
return count
[docs]
def _reset_size_cache(self) -> None:
self.__size_cache = None
[docs]
def node_at(self, index: int) -> DLinkedListNode[T]:
"""Return the ``DLinkedListNode`` at the index."""
if index < 0:
index = self.size + index
if not 0 <= index < self.size:
raise IndexError("Linked list index out of range")
middle = self.size // 2
if index <= middle:
current = self.__head
for _ in range(index):
assert current is not None
current = current.next
assert current is not None
return current
else:
current = self.__tail
for _ in range(self.size - 1 - index):
assert current is not None
current = current.prev
assert current is not None
return current
@overload
def __getitem__(self, index: int) -> T: ...
@overload
def __getitem__(self, index: slice[Any, Any, Any]) -> DLinkedList[T]: ...
def __getitem__(self, index):
if isinstance(index, int):
return self.node_at(index).value
elif isinstance(index, slice):
new_list = DLinkedList()
for val in islice(self, index.start, index.stop, index.step):
new_list.append(val)
return new_list
raise IndexError(index)
@overload
def __setitem__(self, key: int, newvalue: T) -> None: ...
@overload
def __setitem__(self, key: slice[Any, Any, Any], newvalue: Iterable[T]) -> None: ...
def __setitem__(self, key, newvalue):
if isinstance(key, int):
node = self.node_at(key)
node.value = newvalue
elif isinstance(key, slice):
for node, new_val in zip(
islice(self.iter_nodes(), key.start, key.stop, key.step), newvalue, strict=True
):
node.value = new_val
else:
raise IndexError(key)
@overload
def __delitem__(self, key: int) -> None: ...
@overload
def __delitem__(self, key: slice[Any, Any, Any]) -> None: ...
def __delitem__(self, key):
if isinstance(key, int):
node = self.node_at(key)
node.__del__()
elif isinstance(key, slice):
# Note: cannot delete while iterating, because we iterate by the next pointer.
nodes_to_del = list(islice(self.iter_nodes(), key.start, key.stop, key.step))
for node in nodes_to_del:
node.__del__()
else:
raise IndexError(key)
self._reset_size_cache()
def __len__(self) -> int:
return self.size
def __reversed__(self) -> Iterator[T]:
current = self.__tail
while current:
yield current.value
current = current.prev
def __contains__(self, item: object) -> bool:
return any(value is item or value == item for value in self)
def __hash__(self) -> int:
return hash(self)
def __eq__(self, value: object) -> bool:
if not isinstance(value, DLinkedList) or len(self) != len(value):
return False
return all(left == right for left, right in zip(self, value, strict=True))
def __iter__(self) -> Iterator[T]:
current = self.__head
while current:
yield current.value
current = current.next
[docs]
def iter_nodes(self, *, reverse: bool = False) -> Iterator[DLinkedListNode[T]]:
"""Return an iterator of the nodes of the list."""
current = self.__head if not reverse else self.__tail
if current is None:
raise StopIteration
while current:
yield current
current = current.next if not reverse else current.prev
def __iadd__(self, other: Iterable[T]) -> DLinkedList[T]:
for item in other:
self.append(item)
return self
[docs]
def insert(self, index: int, value: T) -> None:
"""Insert `value` into the list at the given `index`."""
node = self.node_at(index)
self.insert_before(node, value)
[docs]
def insert_after(self, node: DLinkedListNode[T], value: T) -> None:
"""Insert `value` into the list after the given `node`."""
new_node = DLinkedListNode(value, prev=node, next=node.next)
if node is self.__tail:
self.__tail = new_node
if self.__size_cache is not None:
self.__size_cache += 1
[docs]
def insert_before(self, node: DLinkedListNode[T], value: T) -> None:
"""Insert `value` into the list before the given `node`."""
new_node = DLinkedListNode(value, prev=node.prev, next=node)
if node is self.__head:
self.__head = new_node
if self.__size_cache is not None:
self.__size_cache += 1
[docs]
def index(self, value: T, start: int = 0, stop: int = ...) -> int: # type: ignore
"""
Return first `index` of `value`.
Raises ValueError if the value is not present. Optional arguments `start`
and `end` are interpreted as in slice notation.
"""
if stop is ...:
stop = self.size
if start < 0:
start = self.size + start
if stop < 0:
stop = self.size + stop
for i, val in enumerate(self):
if i >= stop - 1:
break
if i >= start and (val is value or val == value):
return i
raise ValueError(f"{value} is not in list")
[docs]
def count(self, value: T) -> int:
"""Count the number of list elements equal to `value`."""
return sum(1 for val in self if val is value or val == value)
[docs]
def append(self, value: T) -> None:
"""Add `value` to the right side of the list."""
if self.__head is None:
self.__head = self.__tail = DLinkedListNode(value)
else:
self.__tail = DLinkedListNode(value, prev=self.__tail)
if self.__size_cache is not None:
self.__size_cache += 1
[docs]
def clear(self) -> None:
"""Remove all elements from the list leaving it with length 0."""
if self.__head:
self.__head.__del__()
if self.__tail:
self.__tail.__del__()
self.__head = None
self.__tail = None
self.__size_cache = 0
[docs]
def reverse(self) -> None:
"""Reverse the elements of the list in-place and then return ``None``."""
if self.__head:
self.__head.reverse_from_head()
self.__head, self.__tail = self.__tail, self.__head
[docs]
def extend(self, values: Iterable[T]) -> None:
"""Extend the right side of the list by appending elements from the iterable argument."""
for value in values:
self.append(value)
[docs]
def pop(self, index: int = -1) -> T:
"""
Remove and return an element from the list at `index`.
By default, removes from the right side of the list. If no elements are
present, raises an IndexError.
"""
node = self.node_at(index)
if len(self) == 1:
self.__head = self.__tail = None
elif node is self.__tail:
self.__tail = node.prev
elif node is self.__head:
self.__head = node.next
value = node.value
node.__del__()
if self.__size_cache is not None:
self.__size_cache -= 1
return value
[docs]
def remove(self, value: T) -> None:
"""Remove the first occurrence of value. If not found, raises a ValueError."""
index = self.index(value)
del self[index]
[docs]
def appendleft(self, value: T) -> None:
"""Add value to the left side of the linked list."""
if self.__head is None:
self.__head = self.__tail = DLinkedListNode(value)
else:
self.__head = DLinkedListNode(value, next=self.__head)
[docs]
def copy(self) -> DLinkedList[T]:
"""Create a shallow copy of the linked list."""
return DLinkedList(self)
[docs]
def extendleft(self, values: Iterable[T]) -> None:
"""
Extend the left side of the linked list by appending elements from iterable.
Note, the series of left appends results in reversing the order of
elements in the iterable argument.
"""
for value in values:
self.appendleft(value)
[docs]
def popleft(self) -> T:
"""
Remove and return an element from the left side of the linked list.
If no elements are present, raises an IndexError.
"""
return self.pop(0)
