from __future__ import annotations

from collections.abc import Iterator
from dataclasses import dataclass


@dataclass(order=True)
class Node:
    """
    A class representing a node in a linked list.

    Attributes:
        data: The data stored in the node.
        next: A reference to the next node in the linked list.

    >>> Node(1, Node(2, Node(3)))
    Node(data=1, next=Node(data=2, next=Node(data=3, next=None)))
    """

    data: int
    next: Node | None = None


class SortedLinkedList:
    """This class  represents a sorted linked list."""

    def __init__(self) -> None:
        """
        Create and initialize LinkedList class instance.
        >>> linked_list = SortedLinkedList()
        >>> linked_list.head is None
        True
        """
        self.head: Node | None = None
        self.tail: Node | None = None

    def __iter__(self) -> Iterator[int]:
        """Iterate over the data of the nodes in the linked list.

        >>> linked_list = SortedLinkedList()
        >>> linked_list.insert(3)
        >>> linked_list.insert(1)
        >>> linked_list.insert(2)
        >>> tuple(linked_list)
        (1, 2, 3)
        """
        current = self.head
        while current:
            yield current.data
            current = current.next

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

        >>> linked_list = SortedLinkedList()
        >>> len(linked_list)
        0
        >>> linked_list.insert(3)
        >>> len(linked_list)
        1
        >>> linked_list.insert(1)
        >>> linked_list.insert(2)
        >>> len(linked_list)
        3
        """
        return len(tuple(self))

    def __contains__(self, data: int) -> bool:
        """Check if a node with the given data exists in the linked list.

        >>> linked_list = SortedLinkedList()
        >>> linked_list.insert(3)
        >>> 3 in linked_list
        True
        >>> 1 in linked_list
        False
        """
        return data in tuple(self)

    def insert(self, data: int) -> None:
        """Inserts a node in its sorted position
        This function can be rewritten for any data type, but
        the comparator here must be changed

        Args:
            data (int): the data of the linked list

        Doctests
        >>> linked_list = SortedLinkedList()
        >>> linked_list.insert(32)
        >>> linked_list.insert(57)
        >>> linked_list.insert(45)
        >>> tuple(linked_list)
        (32, 45, 57)
        """
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        elif new_node < self.head:
            new_node.next = self.head
            self.head = new_node
        else:
            temp_node: Node | None = self.head
            if temp_node:
                while temp_node.next and temp_node.next.data < data:
                    temp_node = temp_node.next
                new_node.next = temp_node.next
                temp_node.next = new_node
                if new_node.next is None:
                    self.tail = new_node

    def delete(self, data: int) -> bool:
        """This Function deletes first appearance of node with
        data from it's sorted position

        This function can be re written for any data type but
        the comparator her must have to be changed

        Args:
            data (int): the data of the node that is needed to be deleted

        Returns:
            bool: status whether the node got deleted or not

        Doctests

        >>> linkedList=SortedLinkedList()
        >>> linkedList.insert(32)
        >>> linkedList.insert(57)
        >>> linkedList.insert(45)
        >>> tuple(linkedList)
        (32, 45, 57)
        >>> linkedList.delete(45)
        True
        >>> tuple(linkedList)
        (32, 57)
        """
        if self.head is None:
            return False

        if self.head.data == data:
            self.head = self.head.next
            if self.head is None:
                self.tail = None
            return True

        temp_node: Node | None = self.head
        if temp_node:
            while temp_node.next:
                if temp_node.next.data == data:
                    temp_node.next = temp_node.next.next
                    if temp_node.next is None:
                        self.tail = temp_node
                    return True
                temp_node = temp_node.next

        return False

    def search(self, data: int) -> bool:
        """This function searches the data given input from user
        and return whether the data exists or not

        Args:
            data (int): Data to be searched

        Returns:
            bool: flag indicating whether data exists or not

        Doctests
        >>> linkedList=SortedLinkedList()
        >>> linkedList.insert(32)
        >>> linkedList.insert(57)
        >>> linkedList.insert(45)
        >>> tuple(linkedList)
        (32, 45, 57)
        >>> linkedList.search(45)
        True
        >>> linkedList.search(90)
        False
        """
        return data in self

    def is_empty(self) -> bool:
        """This function will check whether the list is empty or not

        Returns:
            bool: flag indicating whether list is empty or not

        Doctests

        >>> linkedList=SortedLinkedList()
        >>> linkedList.is_empty()
        True
        >>> linkedList.insert(32)
        >>> linkedList.insert(57)
        >>> linkedList.insert(45)
        >>> linkedList.is_empty()
        False
        """
        return not self

    def min_value(self) -> int | None:
        """This function will return minimum value

        Returns:
            int | None: min value or None if list is empty

        Doctests

        >>> linkedList=SortedLinkedList()
        >>> linkedList.min_value() is None
        True
        >>> linkedList.insert(32)
        >>> linkedList.insert(57)
        >>> linkedList.insert(45)
        >>> linkedList.min_value()
        32
        """
        return min(self) if self.head else None

    def max_value(self) -> int | None:
        """This function  will return maximum value


        Returns:
            int | None: max value or None if list is empty

        Doctests

        >>> linkedList=SortedLinkedList()
        >>> linkedList.max_value() is None
        True
        >>> linkedList.insert(32)
        >>> linkedList.insert(57)
        >>> linkedList.insert(45)
        >>> linkedList.max_value()
        57
        """
        return max(self) if self.head else None

    def remove_duplicates(self) -> None:
        """
        This Function will remove the duplicates from the list

        Doctests

        >>> linkedList=SortedLinkedList()
        >>> linkedList.insert(32)
        >>> linkedList.insert(57)
        >>> linkedList.insert(45)
        >>> linkedList.insert(45)
        >>> tuple(linkedList)
        (32, 45, 45, 57)
        >>> linkedList.remove_duplicates()
        >>> tuple(linkedList)
        (32, 45, 57)
        """

        temp: Node | None = self.head
        while temp and temp.next:
            if temp.data == temp.next.data:
                temp.next = temp.next.next
            else:
                temp = temp.next

    def merge(self, other_list: SortedLinkedList) -> None:
        """This Function will merge the input list with current list

        Args:
            other_list (SortedLinkedList): The list to be merged

        Doctests

        >>> linkedList=SortedLinkedList()
        >>> linkedList.insert(32)
        >>> linkedList.insert(57)
        >>> linkedList.insert(45)
        >>> tuple(linkedList)
        (32, 45, 57)
        >>> linkedList2=SortedLinkedList()
        >>> linkedList2.insert(23)
        >>> linkedList2.insert(47)
        >>> linkedList2.insert(95)
        >>> tuple(linkedList2)
        (23, 47, 95)
        >>> linkedList.merge(linkedList2)
        >>> tuple(linkedList)
        (23, 32, 45, 47, 57, 95)
        """
        if other_list.head is None:
            return
        elif self.head is None:
            self.head = other_list.head
            self.tail = other_list.tail
            return
        else:
            temp: Node | None = other_list.head

            while temp:
                self.insert(temp.data)
                temp = temp.next


if __name__ == "__main__":
    linked_list = SortedLinkedList()
    while True:
        print("Enter")
        print("1.  Insert")
        print("2.  Display")
        print("3.  Delete")
        print("4.  Exit")
        choice = input("Enter your choice: ")

        if choice == "1":
            node_data = int(input("Enter a number: "))
            linked_list.insert(node_data)
        elif choice == "2":
            linked_list.display()
        elif choice == "3":
            node_data = int(input("Enter the data to delete: "))
            if linked_list.delete(node_data):
                print(f"Node with data {node_data} deleted successfully")
            else:
                print(f"Node with data {node_data} not found in the list")
        elif choice == "4":
            break
        else:
            print("Wrong input")