



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

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

__SCREAMING_SNAKE_CASE  :						Optional[Any]    							=      TypeVar('''T''')
__SCREAMING_SNAKE_CASE  :						List[str]    							=      TypeVar('''U''')


class 							lowerCamelCase_(   Generic[T, U]    ):





					'''simple docstring'''



					def __init__(    self				,       lowerCamelCase__				,       lowerCamelCase__   ):
									_lowerCamelCase        =				key
									_lowerCamelCase        =				val
									_lowerCamelCase        =				None
									_lowerCamelCase        =				None





					def __repr__(    self   ):
									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]    ):





					'''simple docstring'''



					def __init__(    self   ):
									_lowerCamelCase        =				DoubleLinkedListNode(lowerCamelCase__				,       lowerCamelCase__   )
									_lowerCamelCase        =				DoubleLinkedListNode(lowerCamelCase__				,       lowerCamelCase__   )
									_lowerCamelCase  ,     _lowerCamelCase        =				self.rear, self.head

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

					def 			snake_case__      (    self				,       lowerCamelCase__   ):
									_lowerCamelCase        =				self.rear.prev

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

									_lowerCamelCase        =				node
									_lowerCamelCase        =				previous
									_lowerCamelCase        =				node
									_lowerCamelCase        =				self.rear





					def 			snake_case__      (    self				,       lowerCamelCase__   ):

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

									_lowerCamelCase        =				node.next
									_lowerCamelCase        =				node.prev
									_lowerCamelCase        =				None
									_lowerCamelCase        =				None
									return node


class 							lowerCamelCase_(   Generic[T, U]    ):





					'''simple docstring'''



					lowercase__   :       dict[Callable[[T], U], LRUCache[T, U]]										= {}

					def __init__(    self				,       lowerCamelCase__   ):
									_lowerCamelCase        =				DoubleLinkedList()
									_lowerCamelCase        =				capacity
									_lowerCamelCase        =				0
									_lowerCamelCase        =				0
									_lowerCamelCase        =				0
									_lowerCamelCase        =				{}

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

					def __contains__(    self				,       lowerCamelCase__   ):
									return key in self.cache

					def 			snake_case__      (    self				,       lowerCamelCase__   ):
									# Note: pythonic interface would throw KeyError rather than return None

									if key in self.cache:
													self.hits += 1
													_lowerCamelCase        =				self.cache[key]
													_lowerCamelCase        =				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__   ):

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

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

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





					@classmethod
					def 			snake_case__      (    cls				,       lowerCamelCase__ = 1_2_8   ):

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

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

													def cache_info() -> LRUCache[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 __future__ import annotations

import matplotlib.pyplot as plt  # type: ignore
import numpy

# initial triangle of Koch snowflake
__SCREAMING_SNAKE_CASE  :						List[str]    							=      numpy.array([0, 0])
__SCREAMING_SNAKE_CASE  :						Optional[Any]    							=      numpy.array([0.5, 0.866_0254])
__SCREAMING_SNAKE_CASE  :						Tuple    							=      numpy.array([1, 0])
__SCREAMING_SNAKE_CASE  :						List[Any]    							=      [VECTOR_1, VECTOR_2, VECTOR_3, VECTOR_1]



def        lowerCAmelCase_(   lowercase_     :							list[numpy.ndarray]						,   lowercase_     :							int							)	->       list[numpy.ndarray]:
				_lowerCamelCase        =				initial_vectors
				for _ in range(lowercase_							):
								_lowerCamelCase        =				iteration_step(lowercase_							)
				return vectors



def        lowerCAmelCase_(   lowercase_     :							list[numpy.ndarray]							)	->       list[numpy.ndarray]:
				_lowerCamelCase        =				[]
				for i, start_vector in enumerate(vectors[:-1]							):
								_lowerCamelCase        =				vectors[i + 1]
								new_vectors.append(lowercase_							)
								_lowerCamelCase        =				end_vector - start_vector
								new_vectors.append(start_vector + difference_vector / 3							)
								new_vectors.append(
								    start_vector + difference_vector / 3 + rotate(difference_vector / 3						,   60							)							)
								new_vectors.append(start_vector + difference_vector * 2 / 3							)
				new_vectors.append(vectors[-1]							)
				return new_vectors



def        lowerCAmelCase_(   lowercase_     :							numpy.ndarray						,   lowercase_     :							float							)	->       numpy.ndarray:
				_lowerCamelCase        =				numpy.radians(lowercase_							)
				_lowerCamelCase  ,     _lowerCamelCase        =				numpy.cos(lowercase_							), numpy.sin(lowercase_							)
				_lowerCamelCase        =				numpy.array(((c, -s), (s, c))							)
				return numpy.dot(lowercase_						,   lowercase_							)



def        lowerCAmelCase_(   lowercase_     :							list[numpy.ndarray]							)	->       None:
				_lowerCamelCase        =				plt.gca()
				axes.set_aspect('''equal'''							)

				# matplotlib.pyplot.plot takes a list of all x-coordinates and a list of all
				# y-coordinates as inputs, which are constructed from the vector-list using
				# zip()
				_lowerCamelCase  ,     _lowerCamelCase        =				zip(*lowercase_							)
				plt.plot(lowercase_						,   lowercase_							)
				plt.show()


if __name__ == "__main__":
			import doctest

			doctest.testmod()

			__SCREAMING_SNAKE_CASE  :						str    							=      iterate(INITIAL_VECTORS, 5)
			plot(processed_vectors)
