"""simple docstring"""
from __future__ import annotations

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

SCREAMING_SNAKE_CASE__       =	TypeVar("T")
SCREAMING_SNAKE_CASE__       =	TypeVar("U")



class 	lowerCAmelCase_     (      Generic[T, U]       ):



				"""simple docstring"""

				def __init__(					self		,     lowerCAmelCase		,     lowerCAmelCase     ):






										"""simple docstring"""

										snake_case             =      key
										snake_case             =      val
										snake_case             =      0
										snake_case             =      None
										snake_case             =      None

				def __repr__(					self     ):






										"""simple docstring"""

										return "Node: key: {}, val: {}, freq: {}, has next: {}, has prev: {}".format(
										    self.key		,     self.val		,     self.freq		,     self.next is not None		,     self.prev is not None     )





class 	lowerCAmelCase_     (      Generic[T, U]       ):



				"""simple docstring"""

				def __init__(					self     ):






										"""simple docstring"""

										snake_case             =      DoubleLinkedListNode(lowerCAmelCase		,     lowerCAmelCase     )
										snake_case             =      DoubleLinkedListNode(lowerCAmelCase		,     lowerCAmelCase     )
										snake_case       ,snake_case             =      self.rear, self.head

				def __repr__(					self     ):






										"""simple docstring"""

										snake_case             =      ['DoubleLinkedList']
										snake_case             =      self.head
										while node.next is not None:
																rep.append(str(lowerCAmelCase     )     )
																snake_case             =      node.next
										rep.append(str(self.rear     )     )
										return ",\n    ".join(lowerCAmelCase     )

				def 		snake_case			(					self		,     lowerCAmelCase     ):






										"""simple docstring"""

										snake_case             =      self.rear.prev

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

										snake_case             =      node
										snake_case             =      previous
										snake_case             =      node
										snake_case             =      self.rear
										node.freq += 1
										self._position_node(lowerCAmelCase     )

				def 		snake_case			(					self		,     lowerCAmelCase     ):






										"""simple docstring"""

										while node.prev is not None and node.prev.freq > node.freq:
																# swap node with previous node
																snake_case             =      node.prev

																snake_case             =      previous_node.prev
																snake_case             =      node.prev
																snake_case             =      previous_node
																snake_case             =      node

				def 		snake_case			(					self		,     lowerCAmelCase     ):






										"""simple docstring"""

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

										snake_case             =      node.next
										snake_case             =      node.prev
										snake_case             =      None
										snake_case             =      None
										return node





class 	lowerCAmelCase_     (      Generic[T, U]       ):



				"""simple docstring"""
				_lowerCAmelCase  :     dict[Callable[[T], U], LFUCache[T, U]]      	=    {}

				def __init__(					self		,     lowerCAmelCase     ):






										"""simple docstring"""

										snake_case             =      DoubleLinkedList()
										snake_case             =      capacity
										snake_case             =      0
										snake_case             =      0
										snake_case             =      0
										snake_case             =      {}

				def __repr__(					self     ):






										"""simple docstring"""

										return (
										    F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
										    F"""capacity={self.capacity}, current_size={self.num_keys})"""
										)

				def __contains__(					self		,     lowerCAmelCase     ):






										"""simple docstring"""

										return key in self.cache

				def 		snake_case			(					self		,     lowerCAmelCase     ):






										"""simple docstring"""

										if key in self.cache:
																self.hits += 1
																snake_case             =      self.cache[key]
																snake_case             =      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(lowerCAmelCase     )
																return node.val
										self.miss += 1
										return None

				def 		snake_case			(					self		,     lowerCAmelCase		,     lowerCAmelCase     ):






										"""simple docstring"""

										if key not in self.cache:
																if self.num_keys >= self.capacity:
																						# delete first node when over capacity
																						snake_case             =      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(lowerCAmelCase     ) is not None
																						# first_node guaranteed to be in list

																						del self.cache[first_node.key]
																						self.num_keys -= 1
																snake_case             =      DoubleLinkedListNode(lowerCAmelCase		,     lowerCAmelCase     )
																self.list.add(self.cache[key]     )
																self.num_keys += 1

										else:
																snake_case             =      self.list.remove(self.cache[key]     )
																assert node is not None  # node guaranteed to be in list
																snake_case             =      value
																self.list.add(lowerCAmelCase     )

				@classmethod
				def 		snake_case			(					cls		,     lowerCAmelCase = 1_28     ):






										"""simple docstring"""

										def cache_decorator_inner(lowerCAmelCase     ) -> Callable[..., U]:
																def cache_decorator_wrapper(*lowerCAmelCase     ) -> U:
																						if func not in cls.decorator_function_to_instance_map:
																												snake_case             =      LFUCache(lowerCAmelCase     )

																						snake_case             =      cls.decorator_function_to_instance_map[func].get(args[0]     )
																						if result is None:
																												snake_case             =      func(*lowerCAmelCase     )
																												cls.decorator_function_to_instance_map[func].put(args[0]		,     lowerCAmelCase     )
																						return result

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

																setattr(lowerCAmelCase		,     'cache_info'		,     lowerCAmelCase     )  # noqa: B010

																return cache_decorator_wrapper

										return cache_decorator_inner


if __name__ == "__main__":
					import doctest

					doctest.testmod()



"""simple docstring"""
from typing import TYPE_CHECKING

from ...utils import _LazyModule


SCREAMING_SNAKE_CASE__       =	{"tokenization_bert_japanese": ["BertJapaneseTokenizer", "CharacterTokenizer", "MecabTokenizer"]}


if TYPE_CHECKING:
					from .tokenization_bert_japanese import BertJapaneseTokenizer, CharacterTokenizer, MecabTokenizer

else:
					import sys

					SCREAMING_SNAKE_CASE__       =	_LazyModule(__name__, globals()["__file__"], _import_structure, module_spec=__spec__)


