
'''simple docstring'''

import unittest

from transformers import AutoTokenizer, FalconConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
	import torch

	from transformers import (
	    FalconForCausalLM,
	    FalconForQuestionAnswering,
	    FalconForSequenceClassification,
	    FalconForTokenClassification,
	    FalconModel,
	)

class       UpperCAmelCase					:





		"""simple docstring"""





		def __init__(     self	,       _snake_case	,       _snake_case=3	,       _snake_case=7	,       _snake_case=True	,       _snake_case=True	,       _snake_case=False	,       _snake_case=True	,       _snake_case=99	,       _snake_case=32	,       _snake_case=5	,       _snake_case=4	,       _snake_case=37	,       _snake_case="gelu"	,       _snake_case=0.1	,       _snake_case=0.1	,       _snake_case=512	,       _snake_case=16	,       _snake_case=2	,       _snake_case=0.02	,       _snake_case=3	,       _snake_case=4	,       _snake_case=None	,       )					->     int:
				_UpperCamelCase							:			Tuple     =   parent
				_UpperCamelCase							:			Dict     =   batch_size
				_UpperCamelCase							:			Optional[int]     =   seq_length
				_UpperCamelCase							:			List[Any]     =   is_training
				_UpperCamelCase							:			Optional[Any]     =   use_input_mask
				_UpperCamelCase							:			List[Any]     =   use_token_type_ids
				_UpperCamelCase							:			Optional[int]     =   use_labels
				_UpperCamelCase							:			str     =   vocab_size
				_UpperCamelCase							:			Any     =   hidden_size
				_UpperCamelCase							:			Union[str, Any]     =   num_hidden_layers
				_UpperCamelCase							:			Any     =   num_attention_heads
				_UpperCamelCase							:			Dict     =   intermediate_size
				_UpperCamelCase							:			List[str]     =   hidden_act
				_UpperCamelCase							:			Optional[Any]     =   hidden_dropout_prob
				_UpperCamelCase							:			List[str]     =   attention_probs_dropout_prob
				_UpperCamelCase							:			str     =   max_position_embeddings
				_UpperCamelCase							:			Union[str, Any]     =   type_vocab_size
				_UpperCamelCase							:			Optional[Any]     =   type_sequence_label_size
				_UpperCamelCase							:			Dict     =   initializer_range
				_UpperCamelCase							:			Any     =   num_labels
				_UpperCamelCase							:			Union[str, Any]     =   num_choices
				_UpperCamelCase							:			List[str]     =   scope
		def _lowercase	(     self  )					->     List[str]:
				_UpperCamelCase							:			int     =   ids_tensor([self.batch_size, self.seq_length]	,       self.vocab_size  )

				_UpperCamelCase							:			List[Any]     =   None
				if self.use_input_mask:
						_UpperCamelCase							:			Tuple     =   random_attention_mask([self.batch_size, self.seq_length]  )

				_UpperCamelCase							:			Optional[Any]     =   None

				_UpperCamelCase							:			Optional[int]     =   None
				_UpperCamelCase							:			Tuple     =   None
				_UpperCamelCase							:			Optional[int]     =   None
				if self.use_labels:
						_UpperCamelCase							:			Union[str, Any]     =   ids_tensor([self.batch_size]	,       self.type_sequence_label_size  )
						_UpperCamelCase							:			Any     =   ids_tensor([self.batch_size, self.seq_length]	,       self.num_labels  )
						_UpperCamelCase							:			Optional[Any]     =   ids_tensor([self.batch_size]	,       self.num_choices  )

				_UpperCamelCase							:			Any     =   self.get_config()

				return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels
		def _lowercase	(     self  )					->     Optional[Any]:
				return FalconConfig(
				    vocab_size=self.vocab_size	,       hidden_size=self.hidden_size	,       num_hidden_layers=self.num_hidden_layers	,       num_attention_heads=self.num_attention_heads	,       intermediate_size=self.intermediate_size	,       hidden_act=self.hidden_act	,       hidden_dropout_prob=self.hidden_dropout_prob	,       attention_probs_dropout_prob=self.attention_probs_dropout_prob	,       max_position_embeddings=self.max_position_embeddings	,       type_vocab_size=self.type_vocab_size	,       is_decoder=_snake_case	,       initializer_range=self.initializer_range	,       pad_token_id=1	,       new_decoder_architecture=_snake_case	,       )
		def _lowercase	(     self	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case  )					->     str:
				_UpperCamelCase							:			List[Any]     =   FalconModel(config=_snake_case  )
				model.to(_snake_case  )
				model.eval()
				_UpperCamelCase							:			str     =   model(_snake_case	,       attention_mask=_snake_case  )
				_UpperCamelCase							:			List[str]     =   model(_snake_case  )
				self.parent.assertEqual(result.last_hidden_state.shape	,       (self.batch_size, self.seq_length, self.hidden_size)  )
		def _lowercase	(     self	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       )					->     List[Any]:
				_UpperCamelCase							:			List[Any]     =   True
				_UpperCamelCase							:			Any     =   FalconModel(_snake_case  )
				model.to(_snake_case  )
				model.eval()
				_UpperCamelCase							:			Any     =   model(
				    _snake_case	,       attention_mask=_snake_case	,       encoder_hidden_states=_snake_case	,       encoder_attention_mask=_snake_case	,       )
				_UpperCamelCase							:			int     =   model(
				    _snake_case	,       attention_mask=_snake_case	,       encoder_hidden_states=_snake_case	,       )
				_UpperCamelCase							:			Optional[int]     =   model(_snake_case	,       attention_mask=_snake_case  )
				self.parent.assertEqual(result.last_hidden_state.shape	,       (self.batch_size, self.seq_length, self.hidden_size)  )
		def _lowercase	(     self	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       )					->     int:
				_UpperCamelCase							:			Optional[int]     =   FalconForCausalLM(config=_snake_case  )
				model.to(_snake_case  )
				model.eval()
				_UpperCamelCase							:			str     =   model(_snake_case	,       attention_mask=_snake_case	,       labels=_snake_case  )
				self.parent.assertEqual(result.logits.shape	,       (self.batch_size, self.seq_length, self.vocab_size)  )
		def _lowercase	(     self	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       _snake_case	,       )					->     Union[str, Any]:
				_UpperCamelCase							:			Dict     =   True
				_UpperCamelCase							:			Dict     =   True
				_UpperCamelCase							:			Union[str, Any]     =   FalconForCausalLM(config=_snake_case  )
				model.to(_snake_case  )
				model.eval()

				# first forward pass
				_UpperCamelCase							:			List[str]     =   model(
				    _snake_case	,       attention_mask=_snake_case	,       encoder_hidden_states=_snake_case	,       encoder_attention_mask=_snake_case	,       use_cache=_snake_case	,       )
				_UpperCamelCase							:			int     =   outputs.past_key_values

				# create hypothetical multiple next token and extent to next_input_ids
				_UpperCamelCase							:			List[Any]     =   ids_tensor((self.batch_size, 3)	,       config.vocab_size  )
				_UpperCamelCase							:			Optional[int]     =   ids_tensor((self.batch_size, 3)	,       vocab_size=2  )

				# append to next input_ids and
				_UpperCamelCase							:			List[str]     =   torch.cat([input_ids, next_tokens]	,       dim=-1  )
				_UpperCamelCase							:			Optional[Any]     =   torch.cat([input_mask, next_mask]	,       dim=-1  )

				_UpperCamelCase							:			Tuple     =   model(
				    _snake_case	,       attention_mask=_snake_case	,       encoder_hidden_states=_snake_case	,       encoder_attention_mask=_snake_case	,       output_hidden_states=_snake_case	,       )['''hidden_states'''][0]
				_UpperCamelCase							:			Optional[Any]     =   model(
				    _snake_case	,       attention_mask=_snake_case	,       encoder_hidden_states=_snake_case	,       encoder_attention_mask=_snake_case	,       past_key_values=_snake_case	,       output_hidden_states=_snake_case	,       )['''hidden_states'''][0]

				# select random slice
				_UpperCamelCase							:			List[Any]     =   ids_tensor((1,)	,       output_from_past.shape[-1]  ).item()
				_UpperCamelCase							:			Tuple     =   output_from_no_past[:, -3:, random_slice_idx].detach()
				_UpperCamelCase							:			int     =   output_from_past[:, :, random_slice_idx].detach()

				self.parent.assertTrue(output_from_past_slice.shape[1] == next_tokens.shape[1]  )

				# test that outputs are equal for slice
				self.parent.assertTrue(torch.allclose(_snake_case	,       _snake_case	,       atol=1E-3  )  )




		def _lowercase	(     self  )					->     Tuple:
				_UpperCamelCase							:			Union[str, Any]     =   self.prepare_config_and_inputs()
				(
				    (
				    _UpperCamelCase						
				),				(
				    _UpperCamelCase						
				),				(
				    _UpperCamelCase						
				),				(
				    _UpperCamelCase						
				),				(
				    _UpperCamelCase						
				),				(
				    _UpperCamelCase						
				),				(
				    _UpperCamelCase						
				),										
				)							:			int     =   config_and_inputs
				_UpperCamelCase							:			Optional[int]     =   {'''input_ids''': input_ids, '''attention_mask''': input_mask}
				return config, inputs_dict







@require_torch
class       UpperCAmelCase					(       snake_case_	,		snake_case_	,		snake_case_	,		unittest.TestCase			):





		"""simple docstring"""





		A__	: Any    =     (
		    (
		        FalconModel,
		        FalconForCausalLM,
		        FalconForSequenceClassification,
		        FalconForTokenClassification,
		        FalconForQuestionAnswering,
		    )
		    if is_torch_available()
		    else ()
		)
		A__	: List[str]    =     (FalconForCausalLM,) if is_torch_available() else ()
		A__	: Dict    =     (
		    {
		        'feature-extraction': FalconModel,
		        'text-classification': FalconForSequenceClassification,
		        'text-generation': FalconForCausalLM,
		        'question-answering': FalconForQuestionAnswering,
		        'token-classification': FalconForTokenClassification,
		        'zero-shot': FalconForSequenceClassification,
		    }
		    if is_torch_available()
		    else {}
		)
		A__	: Dict    =     False
		A__	: Optional[int]    =     False
		def _lowercase	(     self  )					->     Optional[int]:
				_UpperCamelCase							:			Dict     =   FalconModelTester(self  )
				_UpperCamelCase							:			List[Any]     =   ConfigTester(self	,       config_class=_snake_case	,       hidden_size=37  )
		def _lowercase	(     self  )					->     Union[str, Any]:
				self.config_tester.run_common_tests()
		def _lowercase	(     self  )					->     List[str]:
				_UpperCamelCase							:			int     =   self.model_tester.prepare_config_and_inputs()
				self.model_tester.create_and_check_model(*_snake_case  )
		def _lowercase	(     self  )					->     str:
				_UpperCamelCase,				*_UpperCamelCase							:			Tuple     =   self.model_tester.prepare_config_and_inputs()
				for alibi in [True, False]:
						_UpperCamelCase							:			Optional[Any]     =   alibi
						self.model_tester.create_and_check_model(_snake_case	,       *_snake_case  )
		def _lowercase	(     self  )					->     str:
				_UpperCamelCase,				_UpperCamelCase							:			List[Any]     =   self.model_tester.prepare_config_and_inputs_for_common()
				_UpperCamelCase							:			Any     =   3
				_UpperCamelCase							:			Any     =   input_dict['''input_ids''']
				_UpperCamelCase							:			List[Any]     =   input_ids.ne(1  ).to(_snake_case  )
				_UpperCamelCase							:			str     =   ids_tensor([self.model_tester.batch_size]	,       self.model_tester.type_sequence_label_size  )
				_UpperCamelCase							:			Dict     =   FalconForSequenceClassification(_snake_case  )
				model.to(_snake_case  )
				model.eval()
				_UpperCamelCase							:			Union[str, Any]     =   model(_snake_case	,       attention_mask=_snake_case	,       labels=_snake_case  )
				self.assertEqual(result.logits.shape	,       (self.model_tester.batch_size, self.model_tester.num_labels)  )
		def _lowercase	(     self  )					->     Union[str, Any]:
				_UpperCamelCase,				_UpperCamelCase							:			int     =   self.model_tester.prepare_config_and_inputs_for_common()
				_UpperCamelCase							:			Optional[Any]     =   3
				_UpperCamelCase							:			Any     =   '''single_label_classification'''
				_UpperCamelCase							:			Optional[int]     =   input_dict['''input_ids''']
				_UpperCamelCase							:			Optional[Any]     =   input_ids.ne(1  ).to(_snake_case  )
				_UpperCamelCase							:			str     =   ids_tensor([self.model_tester.batch_size]	,       self.model_tester.type_sequence_label_size  )
				_UpperCamelCase							:			Dict     =   FalconForSequenceClassification(_snake_case  )
				model.to(_snake_case  )
				model.eval()
				_UpperCamelCase							:			Tuple     =   model(_snake_case	,       attention_mask=_snake_case	,       labels=_snake_case  )
				self.assertEqual(result.logits.shape	,       (self.model_tester.batch_size, self.model_tester.num_labels)  )
		def _lowercase	(     self  )					->     List[str]:
				_UpperCamelCase,				_UpperCamelCase							:			Dict     =   self.model_tester.prepare_config_and_inputs_for_common()
				_UpperCamelCase							:			Union[str, Any]     =   input_dict['''input_ids''']
				_UpperCamelCase							:			Optional[Any]     =   FalconForCausalLM(_snake_case  )
				model.to(_snake_case  )
				model.eval()
				_UpperCamelCase							:			str     =   model(_snake_case	,       use_cache=_snake_case  )
				_UpperCamelCase							:			str     =   input_ids.shape[0]
				_UpperCamelCase							:			Union[str, Any]     =   model._convert_to_rw_cache(result.past_key_values  )
				_UpperCamelCase							:			str     =   model._convert_cache_to_standard_format(_snake_case	,       _snake_case  )
				for layer in range(len(_snake_case  )  ):
						for tensor_idx in range(2  ):
								self.assertTrue(rw_cache[layer][tensor_idx].ndim == 3  )
								self.assertTrue(result.past_key_values[layer][tensor_idx].ndim == 4  )
								self.assertTrue(
								    torch.all(result.past_key_values[layer][tensor_idx] == standard_cache[layer][tensor_idx]  )  )
		def _lowercase	(     self  )					->     Optional[Any]:
				_UpperCamelCase,				_UpperCamelCase							:			Any     =   self.model_tester.prepare_config_and_inputs_for_common()
				_UpperCamelCase							:			Optional[Any]     =   3
				_UpperCamelCase							:			Tuple     =   '''multi_label_classification'''
				_UpperCamelCase							:			Optional[Any]     =   input_dict['''input_ids''']
				_UpperCamelCase							:			Dict     =   input_ids.ne(1  ).to(_snake_case  )
				_UpperCamelCase							:			Dict     =   ids_tensor(
				    [self.model_tester.batch_size, config.num_labels]	,       self.model_tester.type_sequence_label_size  ).to(torch.float  )
				_UpperCamelCase							:			Dict     =   FalconForSequenceClassification(_snake_case  )
				model.to(_snake_case  )
				model.eval()
				_UpperCamelCase							:			Optional[Any]     =   model(_snake_case	,       attention_mask=_snake_case	,       labels=_snake_case  )
				self.assertEqual(result.logits.shape	,       (self.model_tester.batch_size, self.model_tester.num_labels)  )




		def _lowercase	(     self  )					->     List[str]:
				# Falcon can have different numbers of KV-heads than the number of query heads, so we need
				# to override this test to use the right head counts.
				for model_class in self.all_generative_model_classes:
						_UpperCamelCase,				_UpperCamelCase							:			int     =   self.model_tester.prepare_config_and_inputs_for_common()

						# If it doesn't support cache, pass the test
						if not hasattr(_snake_case	,       '''use_cache'''  ):
								return

						_UpperCamelCase							:			Optional[Any]     =   model_class(_snake_case  ).to(_snake_case  )
						if "use_cache" not in inputs:
								_UpperCamelCase							:			int     =   True
						_UpperCamelCase							:			Union[str, Any]     =   model(**_snake_case  )

						# If "past_key_values" is not returned, pass the test (e.g. RWKV uses a different cache name and format)
						if "past_key_values" not in outputs:
								return

						_UpperCamelCase							:			Tuple     =   (
						    getattr(_snake_case	,       '''decoder_layers'''	,       _snake_case  )
						    or getattr(_snake_case	,       '''num_decoder_layers'''	,       _snake_case  )
						    or config.num_hidden_layers
						)
						_UpperCamelCase							:			Dict     =   getattr(_snake_case	,       '''num_kv_heads'''	,       config.num_attention_heads  )
						_UpperCamelCase							:			Tuple     =   getattr(_snake_case	,       '''d_model'''	,       config.hidden_size  )
						_UpperCamelCase							:			Tuple     =   embed_dim // num_attention_heads

						_UpperCamelCase							:			Optional[int]     =   outputs['''past_key_values''']
						self.assertEqual(len(_snake_case  )	,       _snake_case  )

						_UpperCamelCase,				_UpperCamelCase							:			List[str]     =   inputs['''input_ids'''].shape
						for i in range(_snake_case  ):
								if config.new_decoder_architecture:
										_UpperCamelCase							:			Dict     =   config.num_attention_heads
								elif config.multi_query:
										_UpperCamelCase							:			Optional[Any]     =   1
								self.assertEqual(len(past_kv[0]  )	,       2  )  # K V for the decoder = 2
								self.assertEqual(
								    past_kv[i][0].shape	,       (batch_size, num_attention_heads, seq_length, per_head_embed_dim)  )
								self.assertEqual(
								    past_kv[i][1].shape	,       (batch_size, num_attention_heads, seq_length, per_head_embed_dim)  )







@require_torch
class       UpperCAmelCase					(       unittest.TestCase			):





		"""simple docstring"""





		@slow
		def _lowercase	(     self  )					->     Optional[Any]:
				_UpperCamelCase							:			Union[str, Any]     =   AutoTokenizer.from_pretrained('''Rocketknight1/falcon-rw-1b'''  )
				_UpperCamelCase							:			Tuple     =   FalconForCausalLM.from_pretrained('''Rocketknight1/falcon-rw-1b'''  )
				model.eval()
				model.to(_snake_case  )
				_UpperCamelCase							:			Dict     =   tokenizer('''My favorite food is'''	,       return_tensors='''pt'''  ).to(_snake_case  )

				_UpperCamelCase							:			Dict     =   (
				    '''My favorite food is pizza. I love it so much that I have a pizza party every year for my birthday.'''
				)

				_UpperCamelCase							:			Optional[Any]     =   model.generate(**_snake_case	,       do_sample=_snake_case	,       max_new_tokens=19  )
				_UpperCamelCase							:			List[str]     =   tokenizer.batch_decode(_snake_case  )[0]

				self.assertEqual(_snake_case	,       _snake_case  )
		@slow
		def _lowercase	(     self  )					->     Any:
				# The big models are way too big for the CI, so we use tiny random models that resemble their
				# architectures but with much smaller and fewer layers
				for repo in ["Rocketknight1/tiny-random-falcon-7b", "Rocketknight1/tiny-random-falcon-40b"]:
						_UpperCamelCase							:			int     =   AutoTokenizer.from_pretrained(_snake_case  )
						_UpperCamelCase							:			List[Any]     =   FalconForCausalLM.from_pretrained(_snake_case  )
						model.eval()
						model.to(_snake_case  )
						_UpperCamelCase							:			Union[str, Any]     =   tokenizer('''My favorite food is'''	,       return_tensors='''pt'''  ).to(_snake_case  )

						# We just test that these run without errors - the models are randomly initialized
						# and so the actual text outputs will be garbage
						model.generate(**_snake_case	,       do_sample=_snake_case	,       max_new_tokens=4  )
						model.generate(**_snake_case	,       do_sample=_snake_case	,       max_new_tokens=4  )
						model.generate(**_snake_case	,       num_beams=2	,       max_new_tokens=4  )




		@slow
		def _lowercase	(     self  )					->     str:
				# The big models are way too big for the CI, so we use tiny random models that resemble their
				# architectures but with much smaller and fewer layers
				with torch.no_grad():
						for repo in [
						    "Rocketknight1/falcon-rw-1b",
						    "Rocketknight1/tiny-random-falcon-7b",
						    "Rocketknight1/tiny-random-falcon-40b",
						]:
								_UpperCamelCase							:			List[Any]     =   AutoTokenizer.from_pretrained(_snake_case  )
								_UpperCamelCase							:			List[Any]     =   FalconForCausalLM.from_pretrained(_snake_case  )
								model.eval()
								model.to(device=_snake_case  )
								_UpperCamelCase							:			List[str]     =   tokenizer('''My favorite food is'''	,       return_tensors='''pt'''  ).to(_snake_case  )

								# Test results are the same with and without cache
								_UpperCamelCase							:			Any     =   model.generate(**_snake_case	,       do_sample=_snake_case	,       max_new_tokens=20	,       use_cache=_snake_case  )
								_UpperCamelCase							:			str     =   model.generate(**_snake_case	,       do_sample=_snake_case	,       max_new_tokens=20	,       use_cache=_snake_case  )
								self.assertTrue((outputs_cache - outputs_no_cache).sum().item() == 0  )













from __future__ import annotations

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

lowercase    				=   TypeVar("T")
lowercase    				=   TypeVar("U")




class 					UpperCamelCase_ (     Generic[T, U]							):



	'''simple docstring'''




	def __init__(			self			,     a			,     a   )			->       List[Any]:
								snake_case_           =				key
								snake_case_           =				val
								snake_case_           =				None
								snake_case_           =				None






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



	'''simple docstring'''




	def __init__(			self   )			->       None:
								snake_case_           =				DoubleLinkedListNode(a			,     a   )
								snake_case_           =				DoubleLinkedListNode(a			,     a   )
								snake_case_     ,						snake_case_           =				self.rear, self.head




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




	def 				_UpperCamelCase     (			self			,     a   )			->       None:
								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






	def 				_UpperCamelCase     (			self			,     a   )			->       DoubleLinkedListNode[T, U] | None:

								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 					UpperCamelCase_ (     Generic[T, U]							):



	'''simple docstring'''




	lowerCAmelCase						=					{}




	def __init__(			self			,     a   )			->       str:
								snake_case_           =				DoubleLinkedList()
								snake_case_           =				capacity
								snake_case_           =				0
								snake_case_           =				0
								snake_case_           =				0
								snake_case_           =				{}




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




	def __contains__(			self			,     a   )			->       bool:
								return key in self.cache




	def 				_UpperCamelCase     (			self			,     a   )			->       U | None:
								# Note: pythonic interface would throw KeyError rather than return None

								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(a   )
															return node.val
								self.miss += 1
								return None




	def 				_UpperCamelCase     (			self			,     a			,     a   )			->       None:

								if key not in self.cache:
															if self.num_keys >= self.capacity:
																						# delete first node (oldest) 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(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
															snake_case_           =				DoubleLinkedListNode(a			,     a   )
															self.list.add(self.cache[key]   )
															self.num_keys += 1

								else:
															# bump node to the end of the list, update value
															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(a   )






	@classmethod
	def 				_UpperCamelCase     (			cls			,     a = 1_28   )			->       Callable[[Callable[[T], U]], Callable[..., U]]:

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

																						snake_case_           =				cls.decorator_function_to_instance_map[func].get(args[0]   )
																						if result is None:
																													snake_case_           =				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()





