
from typing import Any


class Node:
   """ Linked list node. """

   def __init__(self, value):
      self.value: Any = value
      """ The node data. """
      self.next: Node | None = None
      """ The next node in the list, or None for the final node. """


class LinkedList:
   """ Linked list. """

   def __init__(self):
      self.size: int = 0
      """ The node count. """
      self.head: Node = None
      """ The head node, or None if the list is empty. """


   def __len__(self) -> int:
      """ Gets the list length.

   :return: The list length.
   :rtype: int """
      return self.size


   def add(self, value: Any, index: int | None = None) -> None:
      """ Adds a value to the list.

   :param value: the value to be added.

   :param index: the index at which the node will be inserted. The default is the end of the list.

   :raises IndexError: If the index is negative or greater than or equal to the list size. """
      if index is None:
         index = self.size

      if index < 0 or index > self.size:
         raise IndexError(f"List index out of range.")

      node: Node = Node(value)
      if index == 0:
         node.next = self.head
         self.head = node
      else:
         prev: Node = self.get_prev(index)
         node.next = prev.next
         prev.next = node

      self.size += 1


   def get_prev(self, index: int) -> Node:
      """ Gets the node before a specified index.

      :param index: the index of interest.

      :return: The node for which the next link is the node at the specified index.
      :rtype: Node """
      if index == 0:
         return None
      prev: Node = self.head
      for i in range(1, index):
         prev = prev.next
      return prev


   def remove(self, index: int) -> Any:
      """ Removes the node at a specified index.

   :param index: the index of interest.

   :return: The value of the removed node.
   :rtype: Any """
      if index == 0:
         result: Node | None = self.head
         self.size -= 1
         self.head = self.head.next
         return self.head.value

      prev: Node = self.get_prev(index)
      result: Node = prev.next
      self.size -= 1
      prev.next = prev.next.next
      return result.value


   def selection_sort(self) -> None:
      """ Sorts the list using a selection sort. """
      pos: Node = self.head
      posPrev: Node = None
      while (pos != None):
         min: Node = pos
         scanPrev: Node = min
         scan: Node = min.next
         while (scan != None):
            c1 = min.value
            c2 = scan.value
            if c2 < c1:
               min = scan
               minPrev: Node = scanPrev
            scanPrev = scan
            scan = scan.next
         if min is not pos:
            self.swap(min, minPrev, pos, posPrev)
            pos = min # Set breakpoint here for MusicalLinkedListSortExample.
         posPrev = pos
         pos = pos.next


   def swap(self, n1: Node, n1Prev: Node | None, n2: Node, n2Prev: Node | None) -> None:
      """ Swaps two nodes.

   :param n1: the first node to swap.

   :param n1Prev: the previous node to the first, or None if the first is the head node.

   :param n2: the second node to swap.

   :param n2Prev: the previous node to the second, or None if the second is the head node. """
      if n1Prev is not n2 and n2Prev is not n1:
      	#  Swap non-adjacent nodes.
         if n1Prev is not None:
            n1Prev.next = n2
         if n2Prev is not None:
            n2Prev.next = n1
         tmp = n1.next
         n1.next = n2.next
         n2.next = tmp
      else:
      	# Swap adjacent nodes.
         prev: Node = n2Prev if n1Prev is n2 else n1Prev
         swap1: Node = n2 if n1Prev is n2 else n1
         swap2: Node = n1 if n1Prev is n2 else n2
         if prev is not None:
            prev.next = swap2
         swap1.next = swap2.next
         swap2.next = swap1
      if self.head is n1:
         self.head = n2
      elif self.head is n2:
         self.head = n1


   def __str__(self):
      node: Node = self.head
      result: List[str] = []
      while node is not None:
         if node is not self.head:
            result.append(", ")
         result.append(str(node.value))
         node = node.next
      return "".join(result)


if __name__ == '__main__':
   list1: LinkedList = LinkedList()
   for v in [10, 5, 4, 12, 1, 9, 7, 8]:
      list1.add(v)

   list1.selection_sort()
   print(f"sorted values: {list1}")
