
'''simple docstring'''






from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

UpperCAmelCase_       :   int   =       TypeVar('T')
UpperCAmelCase_       :   Any   =       TypeVar('U')

class  UpperCAmelCase__						(       Generic[T, U] ):



    def __init__(	self      :       Any,__A      :       T | None,__A      :       U | None     ):
          _lowerCamelCase				:   Optional[Any]								=   key
          _lowerCamelCase				:   int								=   val
          _lowerCamelCase				:   DoubleLinkedListNode[T, U] | None								=   None
          _lowerCamelCase				:   DoubleLinkedListNode[T, U] | None								=   None



    def __repr__(	self      :       int     ):
          return (
              f'Node: key: {self.key}, val: {self.val}, '
              f'has next: {bool(self.next     )}, has prev: {bool(self.prev     )}'
          )


class  UpperCAmelCase__						(       Generic[T, U] ):



    def __init__(	self      :       Any     ):
          _lowerCamelCase				:   DoubleLinkedListNode[T, U]								=   DoubleLinkedListNode(__A,__A     )
          _lowerCamelCase				:   DoubleLinkedListNode[T, U]								=   DoubleLinkedListNode(__A,__A     )
          _lowerCamelCase						,		_lowerCamelCase				:   List[str]								=   self.rear, self.head



    def __repr__(	self      :       Tuple     ):
          _lowerCamelCase				:   str								=   ["DoubleLinkedList"]
          _lowerCamelCase				:   Union[str, Any]								=   self.head
          while node.next is not None:
                rep.append(str(__A     )     )
                _lowerCamelCase				:   Optional[Any]								=   node.next
          rep.append(str(self.rear     )     )
          return ",\n    ".join(__A     )



    def   lowerCamelCase_  (	self      :       Any,__A      :       DoubleLinkedListNode[T, U]     ):
          _lowerCamelCase				:   List[Any]								=   self.rear.prev

          # All nodes other than self.head are guaranteed to have non-None previous
          assert previous is not None

          _lowerCamelCase				:   Dict								=   node
          _lowerCamelCase				:   Optional[Any]								=   previous
          _lowerCamelCase				:   int								=   node
          _lowerCamelCase				:   int								=   self.rear



    def   lowerCamelCase_  (	self      :       Union[str, Any],__A      :       DoubleLinkedListNode[T, U]     ):

          if node.prev is None or node.next is None:
                return None

          _lowerCamelCase				:   List[Any]								=   node.next
          _lowerCamelCase				:   Any								=   node.prev
          _lowerCamelCase				:   Any								=   None
          _lowerCamelCase				:   Optional[Any]								=   None
          return node


class  UpperCAmelCase__						(       Generic[T, U] ):
    lowerCAmelCase_				    =		{}



    def __init__(	self      :       str,__A      :       int     ):
          _lowerCamelCase				:   DoubleLinkedList[T, U]								=   DoubleLinkedList()
          _lowerCamelCase				:   Dict								=   capacity
          _lowerCamelCase				:   List[Any]								=   0
          _lowerCamelCase				:   int								=   0
          _lowerCamelCase				:   Optional[int]								=   0
          _lowerCamelCase				:   dict[T, DoubleLinkedListNode[T, U]]								=   {}



    def __repr__(	self      :       Any     ):
          return (
              f'CacheInfo(hits={self.hits}, misses={self.miss}, '
              f'capacity={self.capacity}, current size={self.num_keys})'
          )



    def __contains__(	self      :       Union[str, Any],__A      :       T     ):
          return key in self.cache



    def   lowerCamelCase_  (	self      :       List[Any],__A      :       T     ):
          # Note: pythonic interface would throw KeyError rather than return None

          if key in self.cache:
                self.hits += 1
                _lowerCamelCase				:   DoubleLinkedListNode[T, U]								=   self.cache[key]
                _lowerCamelCase				:   int								=   self.list.remove(self.cache[key]     )
                assert node == value_node

                # node is guaranteed not None because it is in self.cache
                assert node is not None
                self.list.add(__A     )
                return node.val
          self.miss += 1
          return None



    def   lowerCamelCase_  (	self      :       int,__A      :       T,__A      :       U     ):

          if key not in self.cache:
                if self.num_keys >= self.capacity:
                      # delete first node (oldest) when over capacity
                      _lowerCamelCase				:   Dict								=   self.list.head.next

                      # guaranteed to have a non-None first node when num_keys > 0
                      # explain to type checker via assertions
                      assert first_node is not None
                      assert first_node.key is not None
                      assert (
                          self.list.remove(__A     ) is not None
                      )  # node guaranteed to be in list assert node.key is not None

                      del self.cache[first_node.key]
                      self.num_keys -= 1
                _lowerCamelCase				:   Optional[Any]								=   DoubleLinkedListNode(__A,__A     )
                self.list.add(self.cache[key]     )
                self.num_keys += 1

          else:
                # bump node to the end of the list, update value
                _lowerCamelCase				:   Union[str, Any]								=   self.list.remove(self.cache[key]     )
                assert node is not None  # node guaranteed to be in list
                _lowerCamelCase				:   List[Any]								=   value
                self.list.add(__A     )



    @classmethod
    def   lowerCamelCase_  (	cls      :       Tuple,__A      :       int = 1_2_8     ):

          def cache_decorator_inner(__A      :       Callable[[T], U]     ) -> Callable[..., U]:
                def cache_decorator_wrapper(*__A      :       T     ) -> U:
                      if func not in cls.decorator_function_to_instance_map:
                            _lowerCamelCase				:   Tuple								=   LRUCache(__A     )

                      _lowerCamelCase				:   str								=   cls.decorator_function_to_instance_map[func].get(args[0]     )
                      if result is None:
                            _lowerCamelCase				:   Optional[int]								=   func(*__A     )
                            cls.decorator_function_to_instance_map[func].put(args[0],__A     )
                      return result

                def cache_info() -> LRUCache[T, U]:
                      return cls.decorator_function_to_instance_map[func]

                setattr(__A,"cache_info",__A     )  # noqa: B010

                return cache_decorator_wrapper

          return cache_decorator_inner


if __name__ == "__main__":
 import doctest

 doctest.testmod()

'''simple docstring'''






from __future__ import annotations

from collections.abc import Iterable, Iterator
from dataclasses import dataclass

UpperCAmelCase_       :   str   =       (3, 9, -11, 0, 7, 5, 1, -1)
UpperCAmelCase_       :   int   =       (4, 6, 2, 0, 8, 10, 3, -2)

@dataclass
class  UpperCAmelCase__						:
    lowerCAmelCase_				    =		42
    lowerCAmelCase_				    =		42


class  UpperCAmelCase__						:



    def __init__(	self      :       Optional[int],__A      :       Iterable[int]     ):
          _lowerCamelCase				:   Node | None								=   None
          for i in sorted(__A,reverse=__A     ):
                _lowerCamelCase				:   Dict								=   Node(__A,self.head     )



    def __iter__(	self      :       str     ):
          _lowerCamelCase				:   Dict								=   self.head
          while node:
                yield node.data
                _lowerCamelCase				:   Optional[Any]								=   node.next_node



    def __len__(	self      :       str     ):
          return sum(1 for _ in self     )



    def __str__(	self      :       str     ):
          return " -> ".join([str(__A     ) for node in self]     )







def 		A_       (	_lowerCAmelCase   :    SortedLinkedList				,	_lowerCAmelCase   :    SortedLinkedList							):



      """simple docstring"""




      return SortedLinkedList(list(_lowerCAmelCase							) + list(_lowerCAmelCase							)							)


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 UpperCAmelCase_       :   List[str]   =       SortedLinkedList
 print(merge_lists(SSL(test_data_odd), SSL(test_data_even)))