Created
July 31, 2023 17:29
-
-
Save mnogom/37dc68663745f6d91c6394ad4231df36 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from __future__ import annotations | |
| from dataclasses import dataclass | |
| from typing import Generic, TypeVar | |
| _HEAD_VALUE = "HEAD" | |
| class CantGoBackError(Exception): | |
| pass | |
| class CantGoNextError(Exception): | |
| pass | |
| class LostHeadError(Exception): | |
| pass | |
| T = TypeVar("T") | |
| @dataclass | |
| class Node(Generic[T]): | |
| node_value: T | |
| prev_node: Node[T] | None = None | |
| next_node: Node[T] | None = None | |
| def get_node_value(self) -> T: | |
| return self.node_value | |
| def __str__(self) -> str: | |
| return str(self.node_value) | |
| # TODO: Add limiter | |
| class DoublyLinkedList(Generic[T]): | |
| def __init__(self) -> None: | |
| self.__dummy_head: Node[T] = Node(node_value=_HEAD_VALUE) # type: ignore[arg-type] | |
| self.__current_node: Node[T] = self.__dummy_head | |
| def is_head(self) -> bool: | |
| return self.__current_node is self.__dummy_head | |
| def is_tail(self) -> bool: | |
| return self.__current_node.next_node is None | |
| def drop_tail(self) -> None: | |
| self.__current_node.next_node = None | |
| def add(self, value: T) -> None: | |
| node = Node(node_value=value, prev_node=self.__current_node) | |
| self.__current_node.next_node = node | |
| self.__current_node = node | |
| def go_back(self) -> None: | |
| if self.__current_node.node_value == _HEAD_VALUE: | |
| raise CantGoBackError | |
| if self.__current_node.prev_node is None: | |
| raise LostHeadError | |
| self.__current_node = self.__current_node.prev_node | |
| def go_next(self) -> None: | |
| if self.__current_node.next_node is None: | |
| raise CantGoNextError | |
| self.__current_node = self.__current_node.next_node | |
| @property | |
| def current(self) -> T: | |
| return self.__current_node.node_value | |
| def __render_node(self, node: Node[T]) -> str: | |
| if node is self.__current_node: | |
| return f"[{node}]" | |
| return f"{node}" | |
| def __str__(self) -> str: | |
| head = self.__dummy_head | |
| values = [] | |
| while head.next_node is not None: | |
| values.append(self.__render_node(head)) | |
| head = head.next_node | |
| else: | |
| values.append(self.__render_node(head)) | |
| return " <-> ".join(values) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment