"""simple docstring"""




from __future__ import annotations

from typing import Generic, TypeVar

__lowerCamelCase									=	TypeVar("T")
class      UpperCamelCase__(      __A			):
						pass






class      UpperCamelCase__(      __A			):
						pass






class      UpperCamelCase__(      Generic[T]			):





						def __init__(							self		,__UpperCAmelCase = 10  )       ->					Optional[Any]:
													A__						  =				[]
													A__						  =				limit





						def __bool__(							self  )       ->					List[str]:
													return bool(self.stack  )





						def __str__(							self  )       ->					Dict:
													return str(self.stack  )





						def 					snake_case__						(							self		,__UpperCAmelCase  )       ->					Optional[int]:







													if len(self.stack  ) >= self.limit:
																				raise StackOverflowError
													self.stack.append(__UpperCAmelCase  )





						def 					snake_case__						(							self  )       ->					Tuple:







													if not self.stack:
																				raise StackUnderflowError
													return self.stack.pop()





						def 					snake_case__						(							self  )       ->					List[str]:







													if not self.stack:
																				raise StackUnderflowError
													return self.stack[-1]





						def 					snake_case__						(							self  )       ->					Any:
													return not bool(self.stack  )





						def 					snake_case__						(							self  )       ->					Tuple:
													return self.size() == self.limit





						def 					snake_case__						(							self  )       ->					Any:
													return len(self.stack  )





						def __contains__(							self		,__UpperCAmelCase  )       ->					Any:
													return item in self.stack






def 	UpperCAmelCase       (						):






							"""simple docstring"""





							A__						  =				Stack(10					)
							assert bool(UpperCamelCase__					) is False
							assert stack.is_empty() is True
							assert stack.is_full() is False
							assert str(UpperCamelCase__					) == "[]"

							try:
														A__						  =				stack.pop()
														raise AssertionError  # This should not happen
							except StackUnderflowError:
														assert True  # This should happen

							try:
														A__						  =				stack.peek()
														raise AssertionError  # This should not happen
							except StackUnderflowError:
														assert True  # This should happen

							for i in range(10					):
														assert stack.size() == i
														stack.push(UpperCamelCase__					)

							assert bool(UpperCamelCase__					)
							assert not stack.is_empty()
							assert stack.is_full()
							assert str(UpperCamelCase__					) == str(list(range(10					)					)					)
							assert stack.pop() == 9
							assert stack.peek() == 8

							stack.push(100					)
							assert str(UpperCamelCase__					) == str([0, 1, 2, 3, 4, 5, 6, 7, 8, 100]					)

							try:
														stack.push(200					)
														raise AssertionError  # This should not happen
							except StackOverflowError:
														assert True  # This should happen

							assert not stack.is_empty()
							assert stack.size() == 10

							assert 5 in stack
							assert 55 not in stack


if __name__ == "__main__":
				test_stack()













"""simple docstring"""





class   _lowercase			:


      def __init__(     self					:						Optional[Any]				, a					:						Union[str, Any]    ):





            """simple docstring"""







            __snake_case   :     Union[str, Any]	      =data
            __snake_case   :     Optional[Any]	      =None
            __snake_case   :     Any	      =None







      def __str__(     self					:						Any    ):





            """simple docstring"""







            return f'''{self.data}'''



class   _lowercase			:


      def __init__(     self					:						Optional[int]    ):





            """simple docstring"""







            __snake_case   :     Any	      =None
            __snake_case   :     int	      =None


      def __iter__(     self					:						int    ):





            """simple docstring"""







            __snake_case   :     List[str]	      =self.head
            while node:
                  yield node.data
                  __snake_case   :     str	      =node.next


      def __str__(     self					:						Optional[int]    ):





            """simple docstring"""







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


      def __len__(     self					:						str    ):





            """simple docstring"""







            return sum(1 for _ in self    )


      def _UpperCamelCase    (     self					:						int				, a					:						List[Any]    ):





            """simple docstring"""







            self.insert_at_nth(0				, a    )


      def _UpperCamelCase    (     self					:						str				, a					:						Optional[int]    ):





            """simple docstring"""







            self.insert_at_nth(len(self    )				, a    )


      def _UpperCamelCase    (     self					:						Optional[Any]				, a					:						int				, a					:						Tuple    ):





            """simple docstring"""







            __snake_case   :     List[str]	      =len(self    )

            if not 0 <= index <= length:
                  raise IndexError('''list index out of range'''    )
            __snake_case   :     List[Any]	      =Node(a    )
            if self.head is None:
                  __snake_case   :     Dict	      =new_node
            elif index == 0:
                  __snake_case   :     Union[str, Any]	      =new_node
                  __snake_case   :     Any	      =self.head
                  __snake_case   :     List[Any]	      =new_node
            elif index == length:
                  __snake_case   :     int	      =new_node
                  __snake_case   :     Optional[Any]	      =self.tail
                  __snake_case   :     Optional[Any]	      =new_node
            else:
                  __snake_case   :     Any	      =self.head
                  for _ in range(0				, a    ):
                        __snake_case   :     Optional[Any]	      =temp.next
                  __snake_case   :     Optional[Any]	      =new_node
                  __snake_case   :     Union[str, Any]	      =temp.previous
                  __snake_case   :     List[Any]	      =temp
                  __snake_case   :     str	      =new_node


      def _UpperCamelCase    (     self					:						List[str]    ):





            """simple docstring"""







            return self.delete_at_nth(0    )


      def _UpperCamelCase    (     self					:						List[Any]    ):





            """simple docstring"""







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


      def _UpperCamelCase    (     self					:						Optional[int]				, a					:						int    ):





            """simple docstring"""







            __snake_case   :     Tuple	      =len(self    )

            if not 0 <= index <= length - 1:
                  raise IndexError('''list index out of range'''    )
            __snake_case   :     str	      =self.head  # default first node
            if length == 1:
                  __snake_case   :     List[Any]	      =None
            elif index == 0:
                  __snake_case   :     List[Any]	      =self.head.next
                  __snake_case   :     Optional[int]	      =None
            elif index == length - 1:
                  __snake_case   :     str	      =self.tail
                  __snake_case   :     Union[str, Any]	      =self.tail.previous
                  __snake_case   :     Optional[Any]	      =None
            else:
                  __snake_case   :     Optional[int]	      =self.head
                  for _ in range(0				, a    ):
                        __snake_case   :     List[Any]	      =temp.next
                  __snake_case   :     Union[str, Any]	      =temp
                  __snake_case   :     Optional[int]	      =temp.previous
                  __snake_case   :     int	      =temp.next
            return delete_node.data


      def _UpperCamelCase    (     self					:						List[Any]				, a					:						Any    ):





            """simple docstring"""







            __snake_case   :     Optional[int]	      =self.head

            while current.data != data:  # Find the position to delete
                  if current.next:
                        __snake_case   :     Dict	      =current.next
                  else:  # We have reached the end an no value matches
                        raise ValueError('''No data matching given value'''    )

            if current == self.head:
                  self.delete_head()

            elif current == self.tail:
                  self.delete_tail()

            else:  # Before: 1 <--> 2(current) <--> 3
                  __snake_case   :     Tuple	      =current.next  # 1 --> 3
                  __snake_case   :     Optional[Any]	      =current.previous  # 1 <--> 3
            return data







      def _UpperCamelCase    (     self					:						int    ):





            """simple docstring"""







            return len(self    ) == 0



def      __lowercase       (     )       ->       None:
      __snake_case   :     List[str]	      =DoublyLinkedList()
      assert linked_list.is_empty() is True
      assert str(a			) == ""

      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(a			) == i
            linked_list.insert_at_nth(a							,		i + 1			)
      assert str(a			) == "->".join(str(a			) for i in range(1							,		11			)			)

      linked_list.insert_at_head(0			)
      linked_list.insert_at_tail(11			)
      assert str(a			) == "->".join(str(a			) for i in range(0							,		12			)			)

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


if __name__ == "__main__":
    from doctest import testmod

    testmod()


