




"""simple docstring"""


from __future__ import annotations

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

_A													=      TypeVar("""T""")
_A													=      TypeVar("""U""")


class _lowerCamelCase    (					Generic[T, U]						):






   def __init__(		self       :		Tuple   ,     UpperCamelCase       :		T | None   ,     UpperCamelCase       :		U | None   )			->						List[str]:

         """simple docstring"""
         lowerCAmelCase__      :			int   =	key
         lowerCAmelCase__      :			Any   =	val
         lowerCAmelCase__      :			DoubleLinkedListNode[T, U] | None   =	None
         lowerCAmelCase__      :			DoubleLinkedListNode[T, U] | None   =	None






   def __repr__(		self       :		Optional[Any]   )			->						str:

         """simple docstring"""
         return (
             f"""Node: key: {self.key}, val: {self.val}, """
             f"""has next: {bool(self.next   )}, has prev: {bool(self.prev   )}"""
         )






class _lowerCamelCase    (					Generic[T, U]						):






   def __init__(		self       :		Dict   )			->						None:

         """simple docstring"""
         lowerCAmelCase__      :			DoubleLinkedListNode[T, U]   =	DoubleLinkedListNode(UpperCamelCase   ,     UpperCamelCase   )
         lowerCAmelCase__      :			DoubleLinkedListNode[T, U]   =	DoubleLinkedListNode(UpperCamelCase   ,     UpperCamelCase   )
         lowerCAmelCase__ ,   lowerCAmelCase__      :			Any   =	self.rear, self.head






   def __repr__(		self       :		int   )			->						str:

         """simple docstring"""
         lowerCAmelCase__      :			str   =	["""DoubleLinkedList"""]
         lowerCAmelCase__      :			List[str]   =	self.head
         while node.next is not None:
               rep.append(str(UpperCamelCase   )   )
               lowerCAmelCase__      :			Optional[int]   =	node.next
         rep.append(str(self.rear   )   )
         return ",\n    ".join(UpperCamelCase   )






   def 	_lowerCAmelCase   (		self       :		Optional[int]   ,     UpperCamelCase       :		DoubleLinkedListNode[T, U]   )			->						None:

         """simple docstring"""
         lowerCAmelCase__      :			Dict   =	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[int]   =	previous
         lowerCAmelCase__      :			Any   =	node
         lowerCAmelCase__      :			str   =	self.rear






   def 	_lowerCAmelCase   (		self       :		Any   ,     UpperCamelCase       :		DoubleLinkedListNode[T, U]   )			->						DoubleLinkedListNode[T, U] | None:

         """simple docstring"""

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

         lowerCAmelCase__      :			List[Any]   =	node.next
         lowerCAmelCase__      :			Optional[int]   =	node.prev
         lowerCAmelCase__      :			Union[str, Any]   =	None
         lowerCAmelCase__      :			Any   =	None
         return node






class _lowerCamelCase    (					Generic[T, U]						):
   _lowerCamelCase    :dict[Callable[[T], U], LRUCache[T, U]]     				=     {}






   def __init__(		self       :		List[str]   ,     UpperCamelCase       :		int   )			->						int:

         """simple docstring"""
         lowerCAmelCase__      :			DoubleLinkedList[T, U]   =	DoubleLinkedList()
         lowerCAmelCase__      :			List[str]   =	capacity
         lowerCAmelCase__      :			Optional[Any]   =	0
         lowerCAmelCase__      :			List[str]   =	0
         lowerCAmelCase__      :			Tuple   =	0
         lowerCAmelCase__      :			dict[T, DoubleLinkedListNode[T, U]]   =	{}






   def __repr__(		self       :		Tuple   )			->						str:

         """simple docstring"""
         return (
             f"""CacheInfo(hits={self.hits}, misses={self.miss}, """
             f"""capacity={self.capacity}, current size={self.num_keys})"""
         )






   def __contains__(		self       :		Optional[Any]   ,     UpperCamelCase       :		T   )			->						bool:

         """simple docstring"""
         return key in self.cache






   def 	_lowerCAmelCase   (		self       :		Tuple   ,     UpperCamelCase       :		T   )			->						U | None:

         """simple docstring"""
         # 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__      :			List[str]   =	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(UpperCamelCase   )
               return node.val
         self.miss += 1
         return None






   def 	_lowerCAmelCase   (		self       :		Any   ,     UpperCamelCase       :		T   ,     UpperCamelCase       :		U   )			->						None:

         """simple docstring"""

         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(UpperCamelCase   ) 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__      :			str   =	DoubleLinkedListNode(UpperCamelCase   ,     UpperCamelCase   )
               self.list.add(self.cache[key]   )
               self.num_keys += 1

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






   @classmethod
   def 	_lowerCAmelCase   (		cls       :		Dict   ,     UpperCamelCase       :		int = 1_28   )			->						Callable[[Callable[[T], U]], Callable[..., U]]:

         """simple docstring"""

         def cache_decorator_inner(UpperCamelCase       :		Callable[[T], U]   ) -> Callable[..., U]:
               def cache_decorator_wrapper(*UpperCamelCase       :		T   ) -> U:
                     if func not in cls.decorator_function_to_instance_map:
                           lowerCAmelCase__      :			List[Any]   =	LRUCache(UpperCamelCase   )

                     lowerCAmelCase__      :			List[str]   =	cls.decorator_function_to_instance_map[func].get(args[0]   )
                     if result is None:
                           lowerCAmelCase__      :			List[str]   =	func(*UpperCamelCase   )
                           cls.decorator_function_to_instance_map[func].put(args[0]   ,     UpperCamelCase   )
                     return result

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

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

               return cache_decorator_wrapper

         return cache_decorator_inner


if __name__ == "__main__":
  import doctest

  doctest.testmod()











"""simple docstring"""


from __future__ import annotations

import math
from collections import Counter
from string import ascii_lowercase



def 	lowercase_				(			__UpperCAmelCase				)						->    None:
      lowerCAmelCase__ ,   lowerCAmelCase__      :			int   =	analyze_text(__UpperCAmelCase				)
      lowerCAmelCase__      :			Optional[Any]   =	list(""" """ + ascii_lowercase				)
      # what is our total sum of probabilities.
      lowerCAmelCase__      :			List[str]   =	sum(single_char_strings.values()				)

      # one length string
      lowerCAmelCase__      :			List[str]   =	0
      # for each alpha we go in our dict and if it is in it we calculate entropy
      for ch in my_alphas:
            if ch in single_char_strings:
                  lowerCAmelCase__      :			List[Any]   =	single_char_strings[ch]
                  lowerCAmelCase__      :			int   =	my_str / all_sum
                  my_fir_sum += prob * math.loga(__UpperCAmelCase				)  # entropy formula.

    # print entropy
      print(f"""{round(-1 * my_fir_sum				):.1f}"""				)

      # two len string
      lowerCAmelCase__      :			Tuple   =	sum(two_char_strings.values()				)
      lowerCAmelCase__      :			str   =	0
      # for each alpha (two in size) calculate entropy.
      for cha in my_alphas:
            for cha in my_alphas:
                  lowerCAmelCase__      :			Optional[int]   =	cha + cha
                  if sequence in two_char_strings:
                        lowerCAmelCase__      :			int   =	two_char_strings[sequence]
                        lowerCAmelCase__      :			str   =	int(__UpperCAmelCase				) / all_sum
                        my_sec_sum += prob * math.loga(__UpperCAmelCase				)

    # print second entropy
      print(f"""{round(-1 * my_sec_sum				):.1f}"""				)

      # print the difference between them
      print(f"""{round((-1 * my_sec_sum) - (-1 * my_fir_sum)				):.1f}"""				)



def 	lowercase_				(			__UpperCAmelCase				)						->    tuple[dict, dict]:
      lowerCAmelCase__      :			Any   =	Counter()  # type: ignore
      lowerCAmelCase__      :			Tuple   =	Counter()  # type: ignore
      single_char_strings[text[-1]] += 1

      # first case when we have space at start.
      two_char_strings[" " + text[0]] += 1
      for i in range(0    ,		len(__UpperCAmelCase				) - 1				):
            single_char_strings[text[i]] += 1
            two_char_strings[text[i : i + 2]] += 1
      return single_char_strings, two_char_strings



def 	lowercase_				(			)						->    Any:
      import doctest

      doctest.testmod()
      # text = (
      #     "Had repulsive dashwoods suspicion sincerity but advantage now him. Remark "
      #     "easily garret nor nay. Civil those mrs enjoy shy fat merry. You greatest "
      #     "jointure saw horrible. He private he on be imagine suppose. Fertile "
      #     "beloved evident through no service elderly is. Blind there if every no so "
      #     "at. Own neglected you preferred way sincerity delivered his attempted. To "
      #     "of message cottage windows do besides against uncivil.  Delightful "
      #     "unreserved impossible few estimating men favourable see entreaties. She "
      #     "propriety immediate was improving. He or entrance humoured likewise "
      #     "moderate. Much nor game son say feel. Fat make met can must form into "
      #     "gate. Me we offending prevailed discovery. "
      # )

      # calculate_prob(text)


if __name__ == "__main__":
  main()





