





"""simple docstring"""





from typing import Any




class 							snake_case							:

      '''simple docstring'''



      def __init__(							self       :      Optional[Any]						,				__lowercase       :      Any ):


        '''simple docstring'''




        __UpperCAmelCase    :						str       =						data
        __UpperCAmelCase    :						Dict       =						None







      def __repr__(							self       :      str ):


        '''simple docstring'''




        return f'''Node({self.data})'''




class 							snake_case							:

      '''simple docstring'''



      def __init__(							self       :      Dict ):


        '''simple docstring'''




        __UpperCAmelCase    :						Optional[int]       =						None

      def __iter__(							self       :      int ):


        '''simple docstring'''




        __UpperCAmelCase    :						Union[str, Any]       =						self.head
        while node:
          yield node.data
          __UpperCAmelCase    :						List[Any]       =						node.next

      def __len__(							self       :      Optional[int] ):


        '''simple docstring'''




        return sum(1 for _ in self )

      def __repr__(							self       :      str ):


        '''simple docstring'''




        return "->".join([str(__lowercase ) for item in self] )

      def __getitem__(							self       :      Dict						,				__lowercase       :      int ):


        '''simple docstring'''




        if not 0 <= index < len(self ):
          raise ValueError('''list index out of range.''' )
        for i, node in enumerate(self ):
          if i == index:
            return node
        return None

      def __setitem__(							self       :      List[str]						,				__lowercase       :      int						,				__lowercase       :      Any ):


        '''simple docstring'''




        if not 0 <= index < len(self ):
          raise ValueError('''list index out of range.''' )
        __UpperCAmelCase    :						Any       =						self.head
        for _ in range(__lowercase ):
          __UpperCAmelCase    :						Any       =						current.next
        __UpperCAmelCase    :						Union[str, Any]       =						data

      def       A_					(							self       :      int						,				__lowercase       :      Any ):


        '''simple docstring'''




        self.insert_nth(len(self )						,				__lowercase )

      def       A_					(							self       :      int						,				__lowercase       :      Any ):


        '''simple docstring'''




        self.insert_nth(0						,				__lowercase )

      def       A_					(							self       :      List[Any]						,				__lowercase       :      int						,				__lowercase       :      Any ):


        '''simple docstring'''




        if not 0 <= index <= len(self ):
          raise IndexError('''list index out of range''' )
        __UpperCAmelCase    :						List[str]       =						Node(__lowercase )
        if self.head is None:
          __UpperCAmelCase    :						Optional[int]       =						new_node
        elif index == 0:
          __UpperCAmelCase    :						Union[str, Any]       =						self.head  # link new_node to head
          __UpperCAmelCase    :						List[str]       =						new_node
        else:
          __UpperCAmelCase    :						Dict       =						self.head
          for _ in range(index - 1 ):
            __UpperCAmelCase    :						Optional[Any]       =						temp.next
          __UpperCAmelCase    :						List[Any]       =						temp.next
          __UpperCAmelCase    :						Optional[Any]       =						new_node

      def       A_					(							self       :      Union[str, Any] ):  # print every node data


        '''simple docstring'''




        print(self )

      def       A_					(							self       :      List[Any] ):


        '''simple docstring'''




        return self.delete_nth(0 )

      def       A_					(							self       :      Any ):  # delete from tail


        '''simple docstring'''




        return self.delete_nth(len(self ) - 1 )

      def       A_					(							self       :      Optional[Any]						,				__lowercase       :      int = 0 ):


        '''simple docstring'''




        if not 0 <= index <= len(self ) - 1:  # test if index is valid
          raise IndexError('''List index out of range.''' )
        __UpperCAmelCase    :						str       =						self.head  # default first node
        if index == 0:
          __UpperCAmelCase    :						Any       =						self.head.next
        else:
          __UpperCAmelCase    :						Dict       =						self.head
          for _ in range(index - 1 ):
            __UpperCAmelCase    :						Dict       =						temp.next
          __UpperCAmelCase    :						Union[str, Any]       =						temp.next
          __UpperCAmelCase    :						str       =						temp.next.next
        return delete_node.data

      def       A_					(							self       :      Union[str, Any] ):


        '''simple docstring'''




        return self.head is None







      def       A_					(							self       :      Any ):


        '''simple docstring'''




        __UpperCAmelCase    :						List[str]       =						None
        __UpperCAmelCase    :						List[str]       =						self.head

        while current:
          # Store the current node's next node.
          __UpperCAmelCase    :						int       =						current.next
          # Make the current node's next point backwards
          __UpperCAmelCase    :						List[Any]       =						prev
          # Make the previous node be the current node
          __UpperCAmelCase    :						List[Any]       =						current
          # Make the current node the next node (to progress iteration)
          __UpperCAmelCase    :						Dict       =						next_node
        # Return prev in order to put the head at the end
        __UpperCAmelCase    :						Optional[int]       =						prev


def       lowerCamelCase_       (   )						->None:





  """simple docstring"""


  __UpperCAmelCase    :						Tuple       =						LinkedList()
  assert linked_list.is_empty() is True
  assert str(UpperCAmelCase_  ) == ""

  try:
    linked_list.delete_head()
    raise AssertionError  # This should not happen.
  except IndexError:
    assert True  # This should happen.

  try:
    linked_list.delete_tail()
    raise AssertionError  # This should not happen.
  except IndexError:
    assert True  # This should happen.

  for i in range(10  ):
    assert len(UpperCAmelCase_  ) == i
    linked_list.insert_nth(UpperCAmelCase_  ,			i + 1  )
  assert str(UpperCAmelCase_  ) == "->".join(str(UpperCAmelCase_  ) for i in range(1  ,			11  )  )

  linked_list.insert_head(0  )
  linked_list.insert_tail(11  )
  assert str(UpperCAmelCase_  ) == "->".join(str(UpperCAmelCase_  ) for i in range(0  ,			12  )  )

  assert linked_list.delete_head() == 0
  assert linked_list.delete_nth(9  ) == 10
  assert linked_list.delete_tail() == 11
  assert len(UpperCAmelCase_  ) == 9
  assert str(UpperCAmelCase_  ) == "->".join(str(UpperCAmelCase_  ) for i in range(1  ,			10  )  )

  assert all(linked_list[i] == i + 1 for i in range(0  ,			9  )  ) is True

  for i in range(0  ,			9  ):
    __UpperCAmelCase    :						Tuple       =						-i
  assert all(linked_list[i] == -i for i in range(0  ,			9  )  ) is True

  linked_list.reverse()
  assert str(UpperCAmelCase_  ) == "->".join(str(UpperCAmelCase_  ) for i in range(-8  ,			1  )  )


def       lowerCamelCase_       (   )						->None:





  """simple docstring"""


  __UpperCAmelCase    :						int       =						[
      -9,
      1_00,
      Node(77_34_51_12  ),
      '''dlrow olleH''',
      7,
      55_55,
      0,
      -192.55_555,
      '''Hello, world!''',
      77.9,
      Node(10  ),
      None,
      None,
      12.20,
  ]
  __UpperCAmelCase    :						List[Any]       =						LinkedList()

  for i in test_input:
    linked_list.insert_tail(UpperCAmelCase_  )

  # Check if it's empty or not
  assert linked_list.is_empty() is False
  assert (
      str(UpperCAmelCase_  ) == "-9->100->Node(77345112)->dlrow olleH->7->5555->0->"
      "-192.55555->Hello, world!->77.9->Node(10)->None->None->12.2"
  )

  # Delete the head
  __UpperCAmelCase    :						Optional[int]       =						linked_list.delete_head()
  assert result == -9
  assert (
      str(UpperCAmelCase_  ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
      "Hello, world!->77.9->Node(10)->None->None->12.2"
  )

  # Delete the tail
  __UpperCAmelCase    :						Optional[int]       =						linked_list.delete_tail()
  assert result == 12.2
  assert (
      str(UpperCAmelCase_  ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
      "Hello, world!->77.9->Node(10)->None->None"
  )

  # Delete a node in specific location in linked list
  __UpperCAmelCase    :						Dict       =						linked_list.delete_nth(10  )
  assert result is None
  assert (
      str(UpperCAmelCase_  ) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
      "Hello, world!->77.9->Node(10)->None"
  )

  # Add a Node instance to its head
  linked_list.insert_head(Node('''Hello again, world!'''  )  )
  assert (
      str(UpperCAmelCase_  )
      == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
      "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None"
  )

  # Add None to its tail
  linked_list.insert_tail(UpperCAmelCase_  )
  assert (
      str(UpperCAmelCase_  )
      == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
      "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None->None"
  )

  # Reverse the linked list
  linked_list.reverse()
  assert (
      str(UpperCAmelCase_  )
      == "None->None->Node(10)->77.9->Hello, world!->-192.55555->0->5555->"
      "7->dlrow olleH->Node(77345112)->100->Node(Hello again, world!)"
  )


def       lowerCamelCase_       (   )						->Optional[int]:





  """simple docstring"""


  from doctest import testmod

  testmod()

  __UpperCAmelCase    :						str       =						LinkedList()
  linked_list.insert_head(input('''Inserting 1st at head '''  ).strip()  )
  linked_list.insert_head(input('''Inserting 2nd at head '''  ).strip()  )
  print('''\nPrint list:'''  )
  linked_list.print_list()
  linked_list.insert_tail(input('''\nInserting 1st at tail '''  ).strip()  )
  linked_list.insert_tail(input('''Inserting 2nd at tail '''  ).strip()  )
  print('''\nPrint list:'''  )
  linked_list.print_list()
  print('''\nDelete head'''  )
  linked_list.delete_head()
  print('''Delete tail'''  )
  linked_list.delete_tail()
  print('''\nPrint list:'''  )
  linked_list.print_list()
  print('''\nReverse linked list'''  )
  linked_list.reverse()
  print('''\nPrint list:'''  )
  linked_list.print_list()
  print('''\nString representation of linked list:'''  )
  print(UpperCAmelCase_  )
  print('''\nReading/changing Node data using indexing:'''  )
  print(f'''Element at Position 1: {linked_list[1]}'''  )
  __UpperCAmelCase    :						Tuple       =						input('''Enter New Value: '''  ).strip()
  print('''New list:'''  )
  print(UpperCAmelCase_  )
  print(f'''length of linked_list is : {len(UpperCAmelCase_  )}'''  )


if __name__ == "__main__":
  main()






"""simple docstring"""





def       lowerCamelCase_       (   UpperCAmelCase_  )						->float:





  """simple docstring"""


  return 10 - x * x


def       lowerCamelCase_       (   UpperCAmelCase_  ,			UpperCAmelCase_  )						->float:





  """simple docstring"""


  if equation(UpperCAmelCase_  ) * equation(UpperCAmelCase_  ) >= 0:
    raise ValueError('''Wrong space!'''  )

  __UpperCAmelCase    :						Tuple       =						a
  while (b - a) >= 0.01:
    # Find middle point
    __UpperCAmelCase    :						List[str]       =						(a + b) / 2
    # Check if middle point is root
    if equation(UpperCAmelCase_  ) == 0.0:
      break
    # Decide the side to repeat the steps
    if equation(UpperCAmelCase_  ) * equation(UpperCAmelCase_  ) < 0:
      __UpperCAmelCase    :						Union[str, Any]       =						c
    else:
      __UpperCAmelCase    :						str       =						c
  return c


if __name__ == "__main__":
  import doctest

  doctest.testmod()

  print(bisection(-2, 5))
  print(bisection(0, 6))