LinkedList

Summary

Package:

pyTooling

Doc-string:

documented

File	Expected	Covered	Uncovered	Coverage
__init__.py	56	54	2	96.4%
Overall (1 files)	56	54	2	96.4%

Source

pyTooling/LinkedList/__init__.pydocumentedundocumentedignoredexcludednot counted

"""
An object-oriented doubly linked-list data structure for Python.

.. seealso::

   :mod:`pyTooling.Tree`
      |rarr| A tree data structure.
   :mod:`pyTooling.Graph`
      |rarr| A graph data structure.
"""
...

_NodeKey =   TypeVar("_NodeKey")
_NodeValue = TypeVar("_NodeValue")

@export
class LinkedListError(ToolingException):
	"""Base-exception of all exceptions raised by :mod:`pyTooling.LinkedList`."""

@export
class InternalError(LinkedListError):
	"""
	The exception is raised when the linked list's internal state became inconsistent.

	The exception message states the discovered inconsistency. Please create a
	:gh:`bug report <pyTooling/pyTooling/issues>` if this exception is raised.
	"""

@export
class NotInAListError(LinkedListError):
	"""The exception is raised when a node is not assigned to any linked list."""

	_unlinkedNode: Node  #: Node that isn't part of a linked list.

	def __init__(self, message: str, /, *, unlinkedNode: Node) -> None:
		"""
		Initializes the exception with the node that isn't part of a linked list.

		:param message:      The exception's message.
		:param unlinkedNode: The node that isn't part of a linked list.
		"""
		...

	@readonly
	def UnlinkedNode(self) -> Node:
		"""
		Read-only property to access the node that isn't part of a linked list (:attr:`_unlinkedNode`).

		:returns: The node.
		"""
		...

@export
class NotInSameListError(LinkedListError, NotInSameHierarchyError):
	"""The exception is raised when a node is assigned to a different linked list than expected."""

@export
class EmptyListError(LinkedListError):
	"""The exception is raised when an operation needs at least one element, but the linked list is empty."""

@export
class NodeNotFoundError(LinkedListError):
	"""The exception is raised when no node matching the search criterion was found."""

@export
class Node(Generic[_NodeKey, _NodeValue], metaclass=ExtendedType, slots=True):
	"""
	The node in an object-oriented doubly linked-list.

	It contains a reference to the doubly linked list (:attr:`_list`), the previous node (:attr:`_previous`), the next
	node (:attr:`_next`) and the data (:attr:`_value`). Optionally, a key (:attr:`_key`) can be stored for sorting
	purposes.

	The :attr:`_previous` field of the **first node** in a doubly linked list is ``None``. Similarly, the :attr:`_next`
	field of the **last node** is ``None``. ``None`` represents the end of the linked list when iterating it node-by-node.
	"""

	_linkedList:   Nullable[LinkedList[_NodeKey, _NodeValue]]  #: Reference to the doubly linked list instance.
	_previousNode: Nullable[Node[_NodeKey, _NodeValue]]        #: Reference to the previous node.
	_nextNode:     Nullable[Node[_NodeKey, _NodeValue]]        #: Reference to the next node.
	_key:          Nullable[_NodeKey]                          #: The sortable key of the node.
	_value:        _NodeValue                                  #: The value of the node.

	def __init__(
		self,
		value:        _NodeValue,
		key:          Nullable[_NodeKey] = None,
		previousNode: Nullable[Node[_NodeKey, _NodeValue]] = None,
		nextNode:     Nullable[Node[_NodeKey, _NodeValue]] = None
	) -> None:
		"""
		Initialize a linked list node.

		:param value:        Value to store in the node.
		:param key:          Optional, sortable key to store in the node.
		:param previousNode: Optional, reference to the previous node.
		:param nextNode:     Optional, reference to the next node.
		:raises TypeError:   If parameter 'previous' is not of type :class:`Node`.
		:raises TypeError:   If parameter 'next' is not of type :class:`Node`.
		:raises ValueError:  If parameter 'value' is None.
		:raises ValueError:  If ``previous`` and ``next`` belong to different linked lists. |br|
		                     A node can only be inserted between two neighbours of the same linked list.
		"""
		...

	@readonly
	def List(self) -> Nullable[LinkedList[_NodeKey, _NodeValue]]:
		"""
		Read-only property to access the linked list, this node belongs to.

		:returns: The linked list, this node is part of, or ``None``.
		"""
		...

	@readonly
	def PreviousNode(self) -> Nullable[Node[_NodeKey, _NodeValue]]:
		"""
		Read-only property to access node's predecessor.

		This reference is ``None`` if the node is the first node in the doubly linked list.

		:returns: The node before the current node or ``None``.
		"""
		...

	@readonly
	def NextNode(self) -> Nullable[Node[_NodeKey, _NodeValue]]:
		"""
		Read-only property to access node's successor.

		This reference is ``None`` if the node is the last node in the doubly linked list.

		:returns: The node after the current node or ``None``.
		"""
		...

	@property
	def Key(self) -> _NodeKey:
		"""
		Property to access the node's internal key.

		The key can be a scalar or a reference to an object.

		:returns: The node's key.
		"""
		...

	@Key.setter
	def Key(self, key: _NodeKey) -> None:
		...

	@property
	def Value(self) -> _NodeValue:
		"""
		Property to access the node's internal data.

		The data can be a scalar or a reference to an object.

		:returns: The node's value.
		"""
		...

	@Value.setter
	def Value(self, value: _NodeValue) -> None:
		...

	def InsertNodeBefore(self, node: Node[_NodeKey, _NodeValue]) -> None:
		"""
		Insert a node before this node.

		:param node:                Node to insert.
		:raises ValueError:         If parameter 'node' is ``None``.
		:raises TypeError:          If parameter 'node' is not of type :class:`Node`.
		:raises NotInSameListError: If parameter 'node' is already part of another linked list.
		:raises NotInAListError:    If this node is not part of a linked list.
		"""
		...

	def InsertNodeAfter(self, node: Node[_NodeKey, _NodeValue]) -> None:
		"""
		Insert a node after this node.

		:param node:                Node to insert.
		:raises ValueError:         If parameter 'node' is ``None``.
		:raises TypeError:          If parameter 'node' is not of type :class:`Node`.
		:raises NotInSameListError: If parameter 'node' is already part of another linked list.
		:raises NotInAListError:    If this node is not part of a linked list.
		"""
		...

	def Remove(self) -> _NodeValue:
		"""
		Remove this node from the linked list.

		:returns: The value of the removed node.
		"""
		...

	def IterateToFirst(self, includeSelf: bool = False) -> Generator[Node[_NodeKey, _NodeValue], None, None]:
		"""
		Return a generator iterating backward from this node to the list's first node.

		Optionally, this node can be included into the generated sequence.

		:param includeSelf: Optional, if ``True``, include this node into the sequence, otherwise start at previous node.
		:returns:           A sequence of nodes towards the list's first node.
		"""
		...

	def IterateToLast(self, includeSelf: bool = False) -> Generator[Node[_NodeKey, _NodeValue], None, None]:
		"""
		Return a generator iterating forward from this node to the list's last node.

		Optionally, this node can be included into the generated sequence by setting.

		:param includeSelf: Optional, if ``True``, include this node into the sequence, otherwise start at next node.
		:returns:           A sequence of nodes towards the list's last node.
		"""
		...

	def __repr__(self) -> str:
		"""
		Return a detailed string representation of this node.

		:returns: The node's value, prefixed by its kind.
		"""
		...

@export
class LinkedList(Generic[_NodeKey, _NodeValue], metaclass=ExtendedType, slots=True):
	"""An object-oriented doubly linked-list."""

	_firstNode: Nullable[Node[_NodeKey, _NodeValue]]  #: Reference to the first node of the linked list.
	_lastNode:  Nullable[Node[_NodeKey, _NodeValue]]  #: Reference to the last node of the linked list.
	_count:     int                                   #: Number of nodes in the linked list.

	def __init__(self, nodes: Nullable[Iterable[Node[_NodeKey, _NodeValue]]] = None) -> None:
		"""
		Initialize an empty linked list.

		Optionally, an iterable can be given to initialize the linked list. The order is preserved.

		:param nodes:               Optional, iterable to initialize the linked list.
		:raises TypeError:          If parameter 'nodes' is not an :class:`iterable <typing.Iterable>`.
		:raises TypeError:          If parameter 'nodes' items are not of type :class:`Node`.
		:raises NotInSameListError: If parameter 'nodes' contains items which are already part of another linked list.
		"""
		...

	@readonly
	def IsEmpty(self) -> int:
		"""
		Read-only property to return the number of .

		This reference is ``None`` if the node is the last node in the doubly linked list.

		:returns: ``True`` if linked list is empty, otherwise ``False``
		"""
		...

	@readonly
	def Count(self) -> int:
		"""
		Read-only property to access the number of nodes in the linked list.

		:returns: Number of nodes.
		"""
		...

	@readonly
	def FirstNode(self) -> Nullable[Node[_NodeKey, _NodeValue]]:
		"""
		Read-only property to access the first node in the linked list.

		In case the list is empty, ``None`` is returned.

		:returns: First node.
		"""
		...

	@readonly
	def LastNode(self) -> Nullable[Node[_NodeKey, _NodeValue]]:
		"""
		Read-only property to access the last node in the linked list.

		In case the list is empty, ``None`` is returned.

		:returns: Last node.
		"""
		...

	def Clear(self) -> None:
		"""
		Clear the linked list.

		Every node is removed: afterwards, it belongs to no linked list and has neither a previous nor a next node, so it
		can be inserted into a linked list again.
		"""
		...

	def InsertBeforeFirst(self, node: Node[_NodeKey, _NodeValue]) -> None:
		"""
		Insert a node before the first node.

		:param node:                Node to insert.
		:raises ValueError:         If parameter 'node' is ``None``.
		:raises TypeError:          If parameter 'node' is not of type :class:`Node`.
		:raises NotInSameListError: If parameter 'node' is already part of another linked list.
		"""
		...

	def InsertAfterLast(self, node: Node[_NodeKey, _NodeValue]) -> None:
		"""
		Insert a node after the last node.

		:param node:                Node to insert.
		:raises ValueError:         If parameter 'node' is ``None``.
		:raises TypeError:          If parameter 'node' is not of type :class:`Node`.
		:raises NotInSameListError: If parameter 'node' is already part of another linked list.
		"""
		...

	def RemoveFirst(self) -> Node[_NodeKey, _NodeValue]:
		"""
		Remove first node from linked list.

		:returns:               First node.
		:raises EmptyListError: If linked list is empty.
		"""
		...

	def RemoveLast(self) -> Node[_NodeKey, _NodeValue]:
		"""
		Remove last node from linked list.

		:returns:               Last node.
		:raises EmptyListError: If linked list is empty.
		"""
		...

	def GetNodeByIndex(self, index: int) -> Node[_NodeKey, _NodeValue]:
		"""
		Access a node in the linked list by position.

		:param index:          Node position to access.
		:returns:              Node at the given position.
		:raises ValueError:    If parameter 'position' is out of range, which includes an empty list.
		:raises InternalError: If the node at that position could not be reached, so the list's internal state is
		                       inconsistent.

		.. note::

		   The algorithm starts iterating nodes from the shorter end.
		"""
		...

	def Search(self, predicate: Predicate[Node], reverse: bool = False) -> Node[_NodeKey, _NodeValue]:
		"""
		Search the list for the first node matching a predicate.

		:param predicate:          Filter function accepting a node and returning a boolean.
		:param reverse:            Optional, if ``True``, search from the last node towards the first.
		:returns:                  The first matching node.
		:raises EmptyListError:    If the list is empty.
		:raises NodeNotFoundError: If no node matches the predicate.
		"""
		...

	def Reverse(self) -> None:
		"""
		Reverse the order of nodes in the linked list.
		"""
		...

	def Sort(self, key: Nullable[Callable[[Node[_NodeKey, _NodeValue]], Any]] = None, reverse: bool = False) -> None:
		"""
		Sort the linked list in ascending or descending order.

		The sort operation is **stable**.

		:param key:     Optional, function to access a user-defined key for sorting.
		:param reverse: Optional, parameter, if ``True`` sort in descending order, otherwise in ascending order.

		.. note::

		   The linked list is converted to an array, which is sorted by quicksort using the builtin :meth:`~list.sort`.
		   Afterward, the sorted array is used to reconstruct the linked list in requested order.
		"""
		...

	def IterateFromFirst(self) -> Generator[Node[_NodeKey, _NodeValue], None, None]:
		"""
		Return a generator iterating forward from list's first node to list's last node.

		:returns: A sequence of nodes towards the list's last node.
		"""
		...

	def IterateFromLast(self) -> Generator[Node[_NodeKey, _NodeValue], None, None]:
		"""
		Return a generator iterating backward from list's last node to list's first node.

		:returns: A sequence of nodes towards the list's first node.
		"""
		...

	def ToList(self, reverse: bool = False) -> list[Node[_NodeKey, _NodeValue]]:
		"""
		Convert the linked list to a :class:`list`.

		Optionally, the resulting list can be constructed in reverse order.

		:param reverse: Optional, parameter, if ``True`` return in reversed order, otherwise in normal order.
		:returns:       A list (array) of this linked list's values.
		"""
		...

	def ToTuple(self, reverse: bool = False) -> tuple[Node[_NodeKey, _NodeValue], ...]:
		"""
		Convert the linked list to a :class:`tuple`.

		Optionally, the resulting tuple can be constructed in reverse order.

		:param reverse: Optional, parameter, if ``True`` return in reversed order, otherwise in normal order.
		:returns:       A tuple of this linked list's values.
		"""
		...

	def __len__(self) -> int:
		"""
		Returns the number of nodes in the linked list.

		:returns: Number of nodes.
		"""
		...

	def __getitem__(self, index: int) -> _NodeValue:
		"""
		Access a node's value by its index.

		:param index:       Node index to access.
		:returns:           Node's value at the given index.
		:raises ValueError: If parameter 'index' is out of range.

		.. note::

		   The algorithm starts iterating nodes from the shorter end.
		"""
		...

	def __setitem__(self, index: int, value: _NodeValue) -> None:
		"""
		Set the value of node at the given position.

		:param index: Index of the node to modify.
		:param value: New value for the node's value addressed by index.
		"""
		...

	def __delitem__(self, index: int) -> Node[_NodeKey, _NodeValue]:
		"""
		Remove a node at the given index.

		:param index: Index of the node to remove.
		:returns:     Removed node.
		"""
		...