code: 
  
  
  
  
  
  import collections
  import inspect
  import unittest
  
  from transformers import NatConfig
  from transformers.testing_utils import require_natten, require_torch, require_vision, slow, torch_device
  from transformers.utils import cached_property, is_torch_available, is_vision_available
  
  from ...test_backbone_common import BackboneTesterMixin
  from ...test_configuration_common import ConfigTester
  from ...test_modeling_common import ModelTesterMixin, _config_zero_init, floats_tensor, ids_tensor
  from ...test_pipeline_mixin import PipelineTesterMixin
  
  
  if is_torch_available():
       import torch
       from torch import nn
  
       from transformers import NatBackbone, NatForImageClassification, NatModel
       from transformers.models.nat.modeling_nat import NAT_PRETRAINED_MODEL_ARCHIVE_LIST
  
  if is_vision_available():
       from PIL import Image
  
       from transformers import AutoImageProcessor
  
  
  
  
  class 				_lowerCamelCase :
  
  
  
        """simple docstring"""
  
  
  
  
  
  
        def __init__( self				,						UpperCAmelCase				,						UpperCAmelCase=13				,						UpperCAmelCase=64				,						UpperCAmelCase=4				,						UpperCAmelCase=3				,						UpperCAmelCase=16				,						UpperCAmelCase=[1, 2, 1]				,						UpperCAmelCase=[2, 4, 8]				,						UpperCAmelCase=3				,						UpperCAmelCase=2.0				,						UpperCAmelCase=True				,						UpperCAmelCase=0.0				,						UpperCAmelCase=0.0				,						UpperCAmelCase=0.1				,						UpperCAmelCase="gelu"				,						UpperCAmelCase=True				,						UpperCAmelCase=0.02				,						UpperCAmelCase=1E-5				,						UpperCAmelCase=True				,						UpperCAmelCase=None				,						UpperCAmelCase=True				,						UpperCAmelCase=10				,						UpperCAmelCase=["stage1", "stage2"]				,						UpperCAmelCase=[1, 2]				,						)       ->   int:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				int        =       parent
          __snake_case   :				int        =       batch_size
          __snake_case   :				Tuple        =       image_size
          __snake_case   :				Optional[int]        =       patch_size
          __snake_case   :				Tuple        =       num_channels
          __snake_case   :				str        =       embed_dim
          __snake_case   :				str        =       depths
          __snake_case   :				int        =       num_heads
          __snake_case   :				Tuple        =       kernel_size
          __snake_case   :				Union[str, Any]        =       mlp_ratio
          __snake_case   :				Any        =       qkv_bias
          __snake_case   :				str        =       hidden_dropout_prob
          __snake_case   :				int        =       attention_probs_dropout_prob
          __snake_case   :				str        =       drop_path_rate
          __snake_case   :				Tuple        =       hidden_act
          __snake_case   :				Any        =       patch_norm
          __snake_case   :				List[Any]        =       layer_norm_eps
          __snake_case   :				Tuple        =       initializer_range
          __snake_case   :				Union[str, Any]        =       is_training
          __snake_case   :				Optional[int]        =       scope
          __snake_case   :				int        =       use_labels
          __snake_case   :				str        =       num_labels
          __snake_case   :				List[Any]        =       out_features
          __snake_case   :				int        =       out_indices
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   int:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				List[Any]        =       floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]   )
  
          __snake_case   :				Any        =       None
          if self.use_labels:
            __snake_case   :				List[Any]        =       ids_tensor([self.batch_size]				,						self.num_labels   )
  
          __snake_case   :				Any        =       self.get_config()
  
          return config, pixel_values, labels
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   Optional[Any]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          return NatConfig(
              num_labels=self.num_labels				,						image_size=self.image_size				,						patch_size=self.patch_size				,						num_channels=self.num_channels				,						embed_dim=self.embed_dim				,						depths=self.depths				,						num_heads=self.num_heads				,						kernel_size=self.kernel_size				,						mlp_ratio=self.mlp_ratio				,						qkv_bias=self.qkv_bias				,						hidden_dropout_prob=self.hidden_dropout_prob				,						attention_probs_dropout_prob=self.attention_probs_dropout_prob				,						drop_path_rate=self.drop_path_rate				,						hidden_act=self.hidden_act				,						patch_norm=self.patch_norm				,						layer_norm_eps=self.layer_norm_eps				,						initializer_range=self.initializer_range				,						out_features=self.out_features				,						out_indices=self.out_indices				,						)
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self				,						UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase   )       ->   int:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				Tuple        =       NatModel(config=UpperCAmelCase   )
          model.to(UpperCAmelCase   )
          model.eval()
          __snake_case   :				List[str]        =       model(UpperCAmelCase   )
  
          __snake_case   :				Union[str, Any]        =       (config.image_size // config.patch_size) // (2 ** (len(config.depths   ) - 1))
          __snake_case   :				str        =       int(config.embed_dim * 2 ** (len(config.depths   ) - 1)   )
  
          self.parent.assertEqual(
              result.last_hidden_state.shape				,						(self.batch_size, expected_height, expected_width, expected_dim)   )
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self				,						UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase   )       ->   Tuple:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				List[Any]        =       NatForImageClassification(UpperCAmelCase   )
          model.to(UpperCAmelCase   )
          model.eval()
          __snake_case   :				int        =       model(UpperCAmelCase				,						labels=UpperCAmelCase   )
          self.parent.assertEqual(result.logits.shape				,						(self.batch_size, self.num_labels)   )
  
          # test greyscale images
          __snake_case   :				Union[str, Any]        =       1
          __snake_case   :				Optional[int]        =       NatForImageClassification(UpperCAmelCase   )
          model.to(UpperCAmelCase   )
          model.eval()
  
          __snake_case   :				List[Any]        =       floats_tensor([self.batch_size, 1, self.image_size, self.image_size]   )
          __snake_case   :				str        =       model(UpperCAmelCase   )
          self.parent.assertEqual(result.logits.shape				,						(self.batch_size, self.num_labels)   )
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self				,						UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase   )       ->   Optional[int]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				Union[str, Any]        =       NatBackbone(config=UpperCAmelCase   )
          model.to(UpperCAmelCase   )
          model.eval()
          __snake_case   :				Tuple        =       model(UpperCAmelCase   )
  
          # verify hidden states
          self.parent.assertEqual(len(result.feature_maps   )				,						len(config.out_features   )   )
          self.parent.assertListEqual(list(result.feature_maps[0].shape   )				,						[self.batch_size, model.channels[0], 16, 16]   )
  
          # verify channels
          self.parent.assertEqual(len(model.channels   )				,						len(config.out_features   )   )
  
          # verify backbone works with out_features=None
          __snake_case   :				Optional[Any]        =       None
          __snake_case   :				List[Any]        =       NatBackbone(config=UpperCAmelCase   )
          model.to(UpperCAmelCase   )
          model.eval()
          __snake_case   :				Any        =       model(UpperCAmelCase   )
  
          # verify feature maps
          self.parent.assertEqual(len(result.feature_maps   )				,						1   )
          self.parent.assertListEqual(list(result.feature_maps[0].shape   )				,						[self.batch_size, model.channels[-1], 4, 4]   )
  
          # verify channels
          self.parent.assertEqual(len(model.channels   )				,						1   )
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   List[Any]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				Optional[int]        =       self.prepare_config_and_inputs()
          __snake_case    ,   __snake_case    ,   __snake_case   :				Any        =       config_and_inputs
          __snake_case   :				Union[str, Any]        =       {"pixel_values": pixel_values}
          return config, inputs_dict
  
  
  
  
  @require_natten
  @require_torch
  class 				_lowerCamelCase (    a ,   a ,   unittest.TestCase    ):
  
  
  
        """simple docstring"""
  
  
  
  
  
  
        UpperCAmelCase_						:      List[str]       =(
            (
                NatModel,
                NatForImageClassification,
                NatBackbone,
            )
            if is_torch_available()
            else ()
        )
        UpperCAmelCase_						:      Optional[Any]       =(
            {"feature-extraction": NatModel, "image-classification": NatForImageClassification}
            if is_torch_available()
            else {}
        )
        UpperCAmelCase_						:      Tuple       =False
  
        UpperCAmelCase_						:      Any       =False
        UpperCAmelCase_						:      Union[str, Any]       =False
        UpperCAmelCase_						:      List[str]       =False
        UpperCAmelCase_						:      Tuple       =False
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   List[Any]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				Optional[Any]        =       NatModelTester(self   )
          __snake_case   :				int        =       ConfigTester(self				,						config_class=UpperCAmelCase				,						embed_dim=37   )
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   List[str]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          self.create_and_test_config_common_properties()
          self.config_tester.create_and_test_config_to_json_string()
          self.config_tester.create_and_test_config_to_json_file()
          self.config_tester.create_and_test_config_from_and_save_pretrained()
          self.config_tester.create_and_test_config_with_num_labels()
          self.config_tester.check_config_can_be_init_without_params()
          self.config_tester.check_config_arguments_init()
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   Optional[int]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          return
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   List[str]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				Any        =       self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_model(*UpperCAmelCase   )
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   int:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				Optional[Any]        =       self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_for_image_classification(*UpperCAmelCase   )
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   int:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				Dict        =       self.model_tester.prepare_config_and_inputs()
          self.model_tester.create_and_check_backbone(*UpperCAmelCase   )
  
  
  
  
  
  
  
        @unittest.skip(reason="Nat does not use inputs_embeds"   )
        def 						UpperCAmelCase		( self   )       ->   List[Any]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          pass
  
  
  
  
  
  
  
        @unittest.skip(reason="Nat does not use feedforward chunking"   )
        def 						UpperCAmelCase		( self   )       ->   Tuple:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          pass
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   List[Any]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case    ,   __snake_case   :				Optional[Any]        =       self.model_tester.prepare_config_and_inputs_for_common()
  
          for model_class in self.all_model_classes:
            __snake_case   :				List[Any]        =       model_class(UpperCAmelCase   )
            self.assertIsInstance(model.get_input_embeddings()				,						(nn.Module)   )
            __snake_case   :				Union[str, Any]        =       model.get_output_embeddings()
            self.assertTrue(x is None or isinstance(UpperCAmelCase				,						nn.Linear   )   )
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   Optional[Any]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case    ,   __snake_case   :				Any        =       self.model_tester.prepare_config_and_inputs_for_common()
  
          for model_class in self.all_model_classes:
            __snake_case   :				List[Any]        =       model_class(UpperCAmelCase   )
            __snake_case   :				Tuple        =       inspect.signature(model.forward   )
            # signature.parameters is an OrderedDict => so arg_names order is deterministic
            __snake_case   :				List[str]        =       [*signature.parameters.keys()]
  
            __snake_case   :				List[str]        =       ["pixel_values"]
            self.assertListEqual(arg_names[:1]				,						UpperCAmelCase   )
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   List[Any]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          self.skipTest("Nat's attention operation is handled entirely by NATTEN."   )
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self				,						UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase   )       ->   Any:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				int        =       model_class(UpperCAmelCase   )
          model.to(UpperCAmelCase   )
          model.eval()
  
          with torch.no_grad():
            __snake_case   :				Optional[Any]        =       model(**self._prepare_for_class(UpperCAmelCase				,						UpperCAmelCase   )   )
  
          __snake_case   :				Union[str, Any]        =       outputs.hidden_states
  
          __snake_case   :				int        =       getattr(
              self.model_tester				,						"expected_num_hidden_layers"				,						len(self.model_tester.depths   ) + 1   )
          self.assertEqual(len(UpperCAmelCase   )				,						UpperCAmelCase   )
  
          # Nat has a different seq_length
          __snake_case   :				Any        =       (
              config.patch_size
              if isinstance(config.patch_size				,						collections.abc.Iterable   )
              else (config.patch_size, config.patch_size)
          )
  
          __snake_case   :				List[str]        =       image_size[0] // patch_size[0]
          __snake_case   :				Any        =       image_size[1] // patch_size[1]
  
          self.assertListEqual(
              list(hidden_states[0].shape[-3:]   )				,						[height, width, self.model_tester.embed_dim]				,						)
  
          if model_class.__name__ != "NatBackbone":
            __snake_case   :				Union[str, Any]        =       outputs.reshaped_hidden_states
            self.assertEqual(len(UpperCAmelCase   )				,						UpperCAmelCase   )
  
            __snake_case    ,   __snake_case    ,   __snake_case    ,   __snake_case   :				Dict        =       reshaped_hidden_states[0].shape
            __snake_case   :				Dict        =       (
                reshaped_hidden_states[0].view(UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase   ).permute(0				,						2				,						3				,						1   )
            )
            self.assertListEqual(
                list(reshaped_hidden_states.shape[-3:]   )				,						[height, width, self.model_tester.embed_dim]				,						)
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   Optional[int]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case    ,   __snake_case   :				List[Any]        =       self.model_tester.prepare_config_and_inputs_for_common()
  
          __snake_case   :				int        =       (
              self.model_tester.image_size
              if isinstance(self.model_tester.image_size				,						collections.abc.Iterable   )
              else (self.model_tester.image_size, self.model_tester.image_size)
          )
  
          for model_class in self.all_model_classes:
            __snake_case   :				Any        =       True
            self.check_hidden_states_output(UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase   )
  
            # check that output_hidden_states also work using config
            del inputs_dict["output_hidden_states"]
            __snake_case   :				Tuple        =       True
  
            self.check_hidden_states_output(UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase				,						UpperCAmelCase   )
  
  
  
  
  
  
  
        @slow
        def 						UpperCAmelCase		( self   )       ->   Any:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          for model_name in NAT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
            __snake_case   :				Union[str, Any]        =       NatModel.from_pretrained(UpperCAmelCase   )
            self.assertIsNotNone(UpperCAmelCase   )
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   Union[str, Any]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case    ,   __snake_case   :				List[Any]        =       self.model_tester.prepare_config_and_inputs_for_common()
  
          __snake_case   :				Tuple        =       _config_zero_init(UpperCAmelCase   )
          for model_class in self.all_model_classes:
            __snake_case   :				Optional[int]        =       model_class(config=UpperCAmelCase   )
            for name, param in model.named_parameters():
              if "embeddings" not in name and param.requires_grad:
                self.assertIn(
                    ((param.data.mean() * 1E9).round() / 1E9).item()				,						[0.0, 1.0]				,						msg=F"""Parameter {name} of model {model_class} seems not properly initialized"""				,						)
  
  
  
  
  @require_natten
  @require_vision
  @require_torch
  class 				_lowerCamelCase (    unittest.TestCase    ):
  
  
  
        """simple docstring"""
  
  
  
  
  
  
        @cached_property
        def 						UpperCAmelCase		( self   )       ->   Tuple:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          return AutoImageProcessor.from_pretrained("shi-labs/nat-mini-in1k-224"   ) if is_vision_available() else None
  
  
  
  
  
  
  
        @slow
        def 						UpperCAmelCase		( self   )       ->   Any:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				Optional[Any]        =       NatForImageClassification.from_pretrained("shi-labs/nat-mini-in1k-224"   ).to(UpperCAmelCase   )
          __snake_case   :				int        =       self.default_image_processor
  
          __snake_case   :				Optional[int]        =       Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"   )
          __snake_case   :				List[Any]        =       image_processor(images=UpperCAmelCase				,						return_tensors="pt"   ).to(UpperCAmelCase   )
  
          # forward pass
          with torch.no_grad():
            __snake_case   :				Optional[Any]        =       model(**UpperCAmelCase   )
  
          # verify the logits
          __snake_case   :				int        =       torch.Size((1, 1000)   )
          self.assertEqual(outputs.logits.shape				,						UpperCAmelCase   )
          __snake_case   :				Dict        =       torch.tensor([0.3_805, -0.8_676, -0.3_912]   ).to(UpperCAmelCase   )
          self.assertTrue(torch.allclose(outputs.logits[0, :3]				,						UpperCAmelCase				,						atol=1E-4   )   )
  
  
  
  
  @require_torch
  @require_natten
  class 				_lowerCamelCase (    unittest.TestCase ,   a    ):
  
  
  
        """simple docstring"""
  
  
  
  
  
  
        UpperCAmelCase_						:      Union[str, Any]       =(NatBackbone,) if is_torch_available() else ()
        UpperCAmelCase_						:      List[str]       =NatConfig
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self   )       ->   Tuple:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				Tuple        =       NatModelTester(self   )
  
  
style_context: 
  
  
  
  
  
  from __future__ import annotations
  
  from collections.abc import Callable
  from typing import Generic, TypeVar
  
  _UpperCamelCase       = TypeVar('''T''')
  _UpperCamelCase       = TypeVar('''U''')
  
  
  
  
  class 				_lowerCamelCase (    Generic[T, U]    ):
  
  
  
        """simple docstring"""
  
  
  
  
  
  
        def __init__( self				,						UpperCAmelCase				,						UpperCAmelCase   )       ->   Dict:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				Any        =       key
          __snake_case   :				Tuple        =       val
          __snake_case   :				int        =       0
          __snake_case   :				DoubleLinkedListNode[T, U] | None        =       None
          __snake_case   :				DoubleLinkedListNode[T, U] | None        =       None
  
  
  
  
  
  
  
        def __repr__( self   )       ->   str:
  
  
  
  
  
  
          '''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   )       ->   None:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				DoubleLinkedListNode[T, U]        =       DoubleLinkedListNode(UpperCAmelCase				,						UpperCAmelCase   )
          __snake_case   :				DoubleLinkedListNode[T, U]        =       DoubleLinkedListNode(UpperCAmelCase				,						UpperCAmelCase   )
          __snake_case    ,   __snake_case   :				Any        =       self.rear, self.head
  
  
  
  
  
  
  
        def __repr__( self   )       ->   str:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				Union[str, Any]        =       ["DoubleLinkedList"]
          __snake_case   :				List[Any]        =       self.head
          while node.next is not None:
            rep.append(str(UpperCAmelCase   )   )
            __snake_case   :				List[Any]        =       node.next
          rep.append(str(self.rear   )   )
          return ",\n    ".join(UpperCAmelCase   )
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self				,						UpperCAmelCase   )       ->   None:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				Dict        =       self.rear.prev
  
          # All nodes other than self.head are guaranteed to have non-None previous
          assert previous is not None
  
          __snake_case   :				int        =       node
          __snake_case   :				List[str]        =       previous
          __snake_case   :				Optional[int]        =       node
          __snake_case   :				int        =       self.rear
          node.freq += 1
          self._position_node(UpperCAmelCase   )
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self				,						UpperCAmelCase   )       ->   None:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          while node.prev is not None and node.prev.freq > node.freq:
            # swap node with previous node
            __snake_case   :				List[Any]        =       node.prev
  
            __snake_case   :				Dict        =       previous_node.prev
            __snake_case   :				Union[str, Any]        =       node.prev
            __snake_case   :				Union[str, Any]        =       previous_node
            __snake_case   :				int        =       node
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self				,						UpperCAmelCase   )       ->   DoubleLinkedListNode[T, U] | None:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          if node.prev is None or node.next is None:
            return None
  
          __snake_case   :				Optional[int]        =       node.next
          __snake_case   :				Optional[Any]        =       node.prev
          __snake_case   :				Optional[int]        =       None
          __snake_case   :				Any        =       None
          return node
  
  
  
  
  class 				_lowerCamelCase (    Generic[T, U]    ):
  
  
  
        """simple docstring"""
  
  
  
  
  
  
        UpperCAmelCase_						:      dict[Callable[[T], U], LFUCache[T, U]]       ={}
  
  
  
  
  
  
  
        def __init__( self				,						UpperCAmelCase   )       ->   Tuple:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          __snake_case   :				DoubleLinkedList[T, U]        =       DoubleLinkedList()
          __snake_case   :				str        =       capacity
          __snake_case   :				str        =       0
          __snake_case   :				Optional[int]        =       0
          __snake_case   :				Any        =       0
          __snake_case   :				dict[T, DoubleLinkedListNode[T, U]]        =       {}
  
  
  
  
  
  
  
        def __repr__( self   )       ->   str:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          return (
              F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
              F"""capacity={self.capacity}, current_size={self.num_keys})"""
          )
  
  
  
  
  
  
  
        def __contains__( self				,						UpperCAmelCase   )       ->   bool:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          return key in self.cache
  
  
  
  
  
  
  
        def 						UpperCAmelCase		( self				,						UpperCAmelCase   )       ->   U | None:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          if key in self.cache:
            self.hits += 1
            __snake_case   :				DoubleLinkedListNode[T, U]        =       self.cache[key]
            __snake_case   :				Union[str, Any]        =       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 						UpperCAmelCase		( self				,						UpperCAmelCase				,						UpperCAmelCase   )       ->   None:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          if key not in self.cache:
            if self.num_keys >= self.capacity:
              # delete first node when over capacity
              __snake_case   :				Optional[Any]        =       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
              # first_node guaranteed to be in list
  
              del self.cache[first_node.key]
              self.num_keys -= 1
            __snake_case   :				Union[str, Any]        =       DoubleLinkedListNode(UpperCAmelCase				,						UpperCAmelCase   )
            self.list.add(self.cache[key]   )
            self.num_keys += 1
  
          else:
            __snake_case   :				Union[str, Any]        =       self.list.remove(self.cache[key]   )
            assert node is not None  # node guaranteed to be in list
            __snake_case   :				Optional[Any]        =       value
            self.list.add(UpperCAmelCase   )
  
  
  
  
  
  
  
        @classmethod
        def 						UpperCAmelCase		( cls				,						UpperCAmelCase = 128   )       ->   Callable[[Callable[[T], U]], Callable[..., U]]:
  
  
  
  
  
  
          '''simple docstring'''
  
  
  
  
  
  
          def cache_decorator_inner(UpperCAmelCase   ) -> Callable[..., U]:
            def cache_decorator_wrapper(*UpperCAmelCase   ) -> U:
              if func not in cls.decorator_function_to_instance_map:
                __snake_case   :				str        =       LFUCache(UpperCAmelCase   )
  
              __snake_case   :				Dict        =       cls.decorator_function_to_instance_map[func].get(args[0]   )
              if result is None:
                __snake_case   :				Optional[int]        =       func(*UpperCAmelCase   )
                cls.decorator_function_to_instance_map[func].put(args[0]				,						UpperCAmelCase   )
              return result
  
            def cache_info() -> LFUCache[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()
  
  