





"""simple docstring"""




from __future__ import annotations

import inspect
import unittest
from math import floor

import numpy as np

from transformers import CvtConfig
from transformers.testing_utils import require_tf, require_vision, slow
from transformers.utils import cached_property, is_tf_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
     import tensorflow as tf

     from transformers import TFCvtForImageClassification, TFCvtModel
     from transformers.models.cvt.modeling_tf_cvt import TF_CVT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
     from PIL import Image

     from transformers import AutoImageProcessor



class     _UpperCAmelCase   (   __lowercase   ):

  """simple docstring"""


  def     lowercase		(    self			:		Tuple					)							->						Any:
     __lowerCAmelCase							     =     self.config_class(**self.inputs_dict					)
     self.parent.assertTrue(hasattr(_a ,  'embed_dim'					)					)
     self.parent.assertTrue(hasattr(_a ,  'num_heads'					)					)





class     _UpperCAmelCase   :

  """simple docstring"""


  def __init__(    self			:		Any ,  lowerCAmelCase_			:		Optional[Any] ,  lowerCAmelCase_			:		Union[str, Any]=1_3 ,  lowerCAmelCase_			:		str=6_4 ,  lowerCAmelCase_			:		str=3 ,  lowerCAmelCase_			:		Any=[1_6, 4_8, 9_6] ,  lowerCAmelCase_			:		List[Any]=[1, 3, 6] ,  lowerCAmelCase_			:		Optional[int]=[1, 2, 1_0] ,  lowerCAmelCase_			:		str=[7, 3, 3] ,  lowerCAmelCase_			:		Any=[4, 2, 2] ,  lowerCAmelCase_			:		Dict=[2, 1, 1] ,  lowerCAmelCase_			:		Optional[int]=[2, 2, 2] ,  lowerCAmelCase_			:		Tuple=[False, False, True] ,  lowerCAmelCase_			:		str=[0.0, 0.0, 0.0] ,  lowerCAmelCase_			:		int=0.02 ,  lowerCAmelCase_			:		Optional[Any]=1e-12 ,  lowerCAmelCase_			:		List[Any]=True ,  lowerCAmelCase_			:		Optional[Any]=True ,  lowerCAmelCase_			:		Tuple=2 ,  )							->						int:
     __lowerCAmelCase							     =     parent
     __lowerCAmelCase							     =     batch_size
     __lowerCAmelCase							     =     image_size
     __lowerCAmelCase							     =     patch_sizes
     __lowerCAmelCase							     =     patch_stride
     __lowerCAmelCase							     =     patch_padding
     __lowerCAmelCase							     =     is_training
     __lowerCAmelCase							     =     use_labels
     __lowerCAmelCase							     =     num_labels
     __lowerCAmelCase							     =     num_channels
     __lowerCAmelCase							     =     embed_dim
     __lowerCAmelCase							     =     num_heads
     __lowerCAmelCase							     =     stride_kv
     __lowerCAmelCase							     =     depth
     __lowerCAmelCase							     =     cls_token
     __lowerCAmelCase							     =     attention_drop_rate
     __lowerCAmelCase							     =     initializer_range
     __lowerCAmelCase							     =     layer_norm_eps






  def     lowercase		(    self			:		int					)							->						Any:
     __lowerCAmelCase							     =     floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size]					)

     __lowerCAmelCase							     =     None
     if self.use_labels:
        # create a random int32 tensor of given shape
        __lowerCAmelCase							     =     ids_tensor([self.batch_size] ,  self.num_labels					)

     __lowerCAmelCase							     =     self.get_config()
     return config, pixel_values, labels






  def     lowercase		(    self			:		str					)							->						List[Any]:
     return CvtConfig(
         image_size=self.image_size ,  num_labels=self.num_labels ,  num_channels=self.num_channels ,  embed_dim=self.embed_dim ,  num_heads=self.num_heads ,  patch_sizes=self.patch_sizes ,  patch_padding=self.patch_padding ,  patch_stride=self.patch_stride ,  stride_kv=self.stride_kv ,  depth=self.depth ,  cls_token=self.cls_token ,  attention_drop_rate=self.attention_drop_rate ,  initializer_range=self.initializer_range ,  )






  def     lowercase		(    self			:		List[str] ,  lowerCAmelCase_			:		str ,  lowerCAmelCase_			:		List[str] ,  lowerCAmelCase_			:		Optional[int]					)							->						List[str]:
     __lowerCAmelCase							     =     TFCvtModel(config=_a					)
     __lowerCAmelCase							     =     model(_a ,  training=_a					)
     __lowerCAmelCase							     =     (self.image_size, self.image_size)
     __lowerCAmelCase							     =     image_size[0], image_size[1]
     for i in range(len(self.depth					)					):
        __lowerCAmelCase							     =     floor(((height + 2 * self.patch_padding[i] - self.patch_sizes[i]) / self.patch_stride[i]) + 1					)
        __lowerCAmelCase							     =     floor(((width + 2 * self.patch_padding[i] - self.patch_sizes[i]) / self.patch_stride[i]) + 1					)
     self.parent.assertEqual(result.last_hidden_state.shape ,  (self.batch_size, self.embed_dim[-1], height, width)					)






  def     lowercase		(    self			:		Optional[int] ,  lowerCAmelCase_			:		Optional[Any] ,  lowerCAmelCase_			:		List[str] ,  lowerCAmelCase_			:		Union[str, Any]					)							->						List[Any]:
     __lowerCAmelCase							     =     self.num_labels
     __lowerCAmelCase							     =     TFCvtForImageClassification(_a					)
     __lowerCAmelCase							     =     model(_a ,  labels=_a ,  training=_a					)
     self.parent.assertEqual(result.logits.shape ,  (self.batch_size, self.num_labels)					)






  def     lowercase		(    self			:		str					)							->						List[Any]:
     __lowerCAmelCase							     =     self.prepare_config_and_inputs()
     __lowerCAmelCase							     =     config_and_inputs
     __lowerCAmelCase							     =     {'''pixel_values''': pixel_values}
     return config, inputs_dict





@require_tf
class     _UpperCAmelCase   (   __lowercase		,   __lowercase		,   unittest.TestCase   ):

  """simple docstring"""


  a_      =			(TFCvtModel, TFCvtForImageClassification) if is_tf_available() else ()
  a_      =			(
      {"feature-extraction": TFCvtModel, "image-classification": TFCvtForImageClassification}
      if is_tf_available()
      else {}
  )
  a_      =			False
  a_      =			False
  a_      =			False
  a_      =			False
  a_      =			False






  def     lowercase		(    self			:		Union[str, Any]					)							->						Union[str, Any]:
     __lowerCAmelCase							     =     TFCvtModelTester(self					)
     __lowerCAmelCase							     =     TFCvtConfigTester(self ,  config_class=_a ,  has_text_modality=_a ,  hidden_size=3_7					)






  def     lowercase		(    self			:		Optional[int]					)							->						Any:
     self.config_tester.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()






  @unittest.skip(reason='Cvt does not output attentions'					)
  def     lowercase		(    self			:		Any					)							->						List[Any]:
     pass






  @unittest.skip(reason='Cvt does not use inputs_embeds'					)
  def     lowercase		(    self			:		Dict					)							->						str:
     pass






  @unittest.skip(reason='Cvt does not support input and output embeddings'					)
  def     lowercase		(    self			:		int					)							->						Union[str, Any]:
     pass






  @unittest.skipIf(
      not is_tf_available() or len(tf.config.list_physical_devices('GPU'					)					) == 0 ,  reason='TF does not support backprop for grouped convolutions on CPU.' ,  )
  def     lowercase		(    self			:		Dict					)							->						Tuple:
     super().test_dataset_conversion()






  @unittest.skipIf(
      not is_tf_available() or len(tf.config.list_physical_devices('GPU'					)					) == 0 ,  reason='TF does not support backprop for grouped convolutions on CPU.' ,  )
  @slow
  def     lowercase		(    self			:		str					)							->						Optional[Any]:
     super().test_keras_fit()






  @unittest.skip(reason='Get `Failed to determine best cudnn convolution algo.` error after using TF 2.12+cuda 11.8'					)
  def     lowercase		(    self			:		List[Any]					)							->						str:
     __lowerCAmelCase							     =     tf.keras.mixed_precision.Policy('mixed_float16'					)
     tf.keras.mixed_precision.set_global_policy(_a					)
     super().test_keras_fit()
     tf.keras.mixed_precision.set_global_policy('float32'					)






  def     lowercase		(    self			:		Dict					)							->						Tuple:
     __lowerCAmelCase							     =     self.model_tester.prepare_config_and_inputs_for_common()

     for model_class in self.all_model_classes:
        __lowerCAmelCase							     =     model_class(_a					)
        __lowerCAmelCase							     =     inspect.signature(model.call					)
        # signature.parameters is an OrderedDict => so arg_names order is deterministic
        __lowerCAmelCase							     =     [*signature.parameters.keys()]

        __lowerCAmelCase							     =     ['''pixel_values''']
        self.assertListEqual(arg_names[:1] ,  _a					)






  def     lowercase		(    self			:		int					)							->						Dict:
     def check_hidden_states_output(lowerCAmelCase_			:		Optional[int] ,  lowerCAmelCase_			:		Tuple ,  lowerCAmelCase_			:		List[str]					):
        __lowerCAmelCase							     =     model_class(_a					)

        __lowerCAmelCase							     =     model(**self._prepare_for_class(_a ,  _a					)					)
        __lowerCAmelCase							     =     outputs.hidden_states

        __lowerCAmelCase							     =     len(self.model_tester.depth					)
        self.assertEqual(len(_a					) ,  _a					)

        # verify the first hidden states (first block)
        self.assertListEqual(
            list(hidden_states[0].shape[-3:]					) ,  [
                self.model_tester.embed_dim[0],
                self.model_tester.image_size // 4,
                self.model_tester.image_size // 4,
            ] ,  )

     __lowerCAmelCase							     =     self.model_tester.prepare_config_and_inputs_for_common()

     for model_class in self.all_model_classes:
        __lowerCAmelCase							     =     True
        check_hidden_states_output(_a ,  _a ,  _a					)

        # check that output_hidden_states also work using config
        del inputs_dict["output_hidden_states"]
        __lowerCAmelCase							     =     True

        check_hidden_states_output(_a ,  _a ,  _a					)






  def     lowercase		(    self			:		int					)							->						Optional[int]:
     __lowerCAmelCase							     =     self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_model(*_a					)






  def     lowercase		(    self			:		str					)							->						Optional[int]:
     __lowerCAmelCase							     =     self.model_tester.prepare_config_and_inputs()
     self.model_tester.create_and_check_for_image_classification(*_a					)






  @slow
  def     lowercase		(    self			:		List[Any]					)							->						Optional[Any]:
     for model_name in TF_CVT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
        __lowerCAmelCase							     =     TFCvtModel.from_pretrained(_a					)
        self.assertIsNotNone(_a					)





def   a_   (			):
   __lowerCAmelCase							     =     Image.open('./tests/fixtures/tests_samples/COCO/000000039769.png'     )
   return image




@require_tf
@require_vision
class     _UpperCAmelCase   (   unittest.TestCase   ):

  """simple docstring"""


  @cached_property
  def     lowercase		(    self			:		int					)							->						Tuple:
     return AutoImageProcessor.from_pretrained(TF_CVT_PRETRAINED_MODEL_ARCHIVE_LIST[0]					)






  @slow
  def     lowercase		(    self			:		Union[str, Any]					)							->						Tuple:
     __lowerCAmelCase							     =     TFCvtForImageClassification.from_pretrained(TF_CVT_PRETRAINED_MODEL_ARCHIVE_LIST[0]					)

     __lowerCAmelCase							     =     self.default_image_processor
     __lowerCAmelCase							     =     prepare_img()
     __lowerCAmelCase							     =     image_processor(images=_a ,  return_tensors='tf'					)

     # forward pass
     __lowerCAmelCase							     =     model(**_a					)

     # verify the logits
     __lowerCAmelCase							     =     tf.TensorShape((1, 1_0_0_0)					)
     self.assertEqual(outputs.logits.shape ,  _a					)

     __lowerCAmelCase							     =     tf.constant([0.92_85, 0.90_15, -0.31_50]					)
     self.assertTrue(np.allclose(outputs.logits[0, :3].numpy() ,  _a ,  atol=1e-4					)					)








from __future__ import annotations

import time
from math import sqrt

# 1 for manhattan, 0 for euclidean
_snake_case  :   Dict						   =  0

_snake_case  :   Dict						   =  [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],  # 0 are free path whereas 1's are obstacles
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0],
]

_snake_case  :   List[str]						   =  [[-1, 0], [0, -1], [1, 0], [0, 1]]  # up, left, down, right

_snake_case  :   Tuple						   =  tuple[int, int]



class     _UpperCAmelCase   :

  """simple docstring"""


  def __init__(    self			:		Dict ,  lowerCAmelCase_			:		int ,  lowerCAmelCase_			:		int ,  lowerCAmelCase_			:		int ,  lowerCAmelCase_			:		int ,  lowerCAmelCase_			:		int ,  lowerCAmelCase_			:		Node | None ,  )							->						None:
     __lowerCAmelCase							     =     pos_x
     __lowerCAmelCase							     =     pos_y
     __lowerCAmelCase							     =     (pos_y, pos_x)
     __lowerCAmelCase							     =     goal_x
     __lowerCAmelCase							     =     goal_y
     __lowerCAmelCase							     =     g_cost
     __lowerCAmelCase							     =     parent
     __lowerCAmelCase							     =     self.calculate_heuristic()
     __lowerCAmelCase							     =     self.g_cost + self.h_cost






  def     lowercase		(    self			:		Any					)							->						float:
     __lowerCAmelCase							     =     self.pos_x - self.goal_x
     __lowerCAmelCase							     =     self.pos_y - self.goal_y
     if HEURISTIC == 1:
        return abs(lowerCAmelCase_					) + abs(lowerCAmelCase_					)
     else:
        return sqrt(dy**2 + dx**2					)






  def __lt__(    self			:		Union[str, Any] ,  lowerCAmelCase_			:		Node					)							->						bool:
     return self.f_cost < other.f_cost





class     _UpperCAmelCase   :

  """simple docstring"""


  def __init__(    self			:		List[str] ,  lowerCAmelCase_			:		TPosition ,  lowerCAmelCase_			:		TPosition					)							->						Tuple:
     __lowerCAmelCase							     =     Node(start[1] ,  start[0] ,  goal[1] ,  goal[0] ,  0 ,  lowerCAmelCase_					)
     __lowerCAmelCase							     =     Node(goal[1] ,  goal[0] ,  goal[1] ,  goal[0] ,  9_9_9_9_9 ,  lowerCAmelCase_					)

     __lowerCAmelCase							     =     [self.start]
     __lowerCAmelCase							     =     []

     __lowerCAmelCase							     =     False






  def     lowercase		(    self			:		str					)							->						list[TPosition]:
     while self.open_nodes:
        # Open Nodes are sorted using __lt__
        self.open_nodes.sort()
        __lowerCAmelCase							     =     self.open_nodes.pop(0					)

        if current_node.pos == self.target.pos:
           return self.retrace_path(lowerCAmelCase_					)

        self.closed_nodes.append(lowerCAmelCase_					)
        __lowerCAmelCase							     =     self.get_successors(lowerCAmelCase_					)

        for child_node in successors:
           if child_node in self.closed_nodes:
              continue

           if child_node not in self.open_nodes:
              self.open_nodes.append(lowerCAmelCase_					)
           else:
              # retrieve the best current path
              __lowerCAmelCase							     =     self.open_nodes.pop(self.open_nodes.index(lowerCAmelCase_					)					)

              if child_node.g_cost < better_node.g_cost:
                 self.open_nodes.append(lowerCAmelCase_					)
              else:
                 self.open_nodes.append(lowerCAmelCase_					)

     return [self.start.pos]






  def     lowercase		(    self			:		Optional[Any] ,  lowerCAmelCase_			:		Node					)							->						list[Node]:
     __lowerCAmelCase							     =     []
     for action in delta:
        __lowerCAmelCase							     =     parent.pos_x + action[1]
        __lowerCAmelCase							     =     parent.pos_y + action[0]
        if not (0 <= pos_x <= len(grid[0]					) - 1 and 0 <= pos_y <= len(lowerCAmelCase_					) - 1):
           continue

        if grid[pos_y][pos_x] != 0:
           continue

        successors.append(
            Node(
                lowerCAmelCase_ ,  lowerCAmelCase_ ,  self.target.pos_y ,  self.target.pos_x ,  parent.g_cost + 1 ,  lowerCAmelCase_ ,  )					)
     return successors






  def     lowercase		(    self			:		Tuple ,  lowerCAmelCase_			:		Node | None					)							->						list[TPosition]:
     __lowerCAmelCase							     =     node
     __lowerCAmelCase							     =     []
     while current_node is not None:
        path.append((current_node.pos_y, current_node.pos_x)					)
        __lowerCAmelCase							     =     current_node.parent
     path.reverse()
     return path





class     _UpperCAmelCase   :

  """simple docstring"""


  def __init__(    self			:		int ,  lowerCAmelCase_			:		TPosition ,  lowerCAmelCase_			:		TPosition					)							->						None:
     __lowerCAmelCase							     =     AStar(lowerCAmelCase_ ,  lowerCAmelCase_					)
     __lowerCAmelCase							     =     AStar(lowerCAmelCase_ ,  lowerCAmelCase_					)
     __lowerCAmelCase							     =     False






  def     lowercase		(    self			:		Dict					)							->						list[TPosition]:
     while self.fwd_astar.open_nodes or self.bwd_astar.open_nodes:
        self.fwd_astar.open_nodes.sort()
        self.bwd_astar.open_nodes.sort()
        __lowerCAmelCase							     =     self.fwd_astar.open_nodes.pop(0					)
        __lowerCAmelCase							     =     self.bwd_astar.open_nodes.pop(0					)

        if current_bwd_node.pos == current_fwd_node.pos:
           return self.retrace_bidirectional_path(
               lowerCAmelCase_ ,  lowerCAmelCase_					)

        self.fwd_astar.closed_nodes.append(lowerCAmelCase_					)
        self.bwd_astar.closed_nodes.append(lowerCAmelCase_					)

        __lowerCAmelCase							     =     current_bwd_node
        __lowerCAmelCase							     =     current_fwd_node

        __lowerCAmelCase							     =     {
            self.fwd_astar: self.fwd_astar.get_successors(lowerCAmelCase_					),
            self.bwd_astar: self.bwd_astar.get_successors(lowerCAmelCase_					),
        }

        for astar in [self.fwd_astar, self.bwd_astar]:
           for child_node in successors[astar]:
              if child_node in astar.closed_nodes:
                 continue

              if child_node not in astar.open_nodes:
                 astar.open_nodes.append(lowerCAmelCase_					)
              else:
                 # retrieve the best current path
                 __lowerCAmelCase							     =     astar.open_nodes.pop(
                     astar.open_nodes.index(lowerCAmelCase_					)					)

                 if child_node.g_cost < better_node.g_cost:
                    astar.open_nodes.append(lowerCAmelCase_					)
                 else:
                    astar.open_nodes.append(lowerCAmelCase_					)

     return [self.fwd_astar.start.pos]






  def     lowercase		(    self			:		Dict ,  lowerCAmelCase_			:		Node ,  lowerCAmelCase_			:		Node					)							->						list[TPosition]:
     __lowerCAmelCase							     =     self.fwd_astar.retrace_path(lowerCAmelCase_					)
     __lowerCAmelCase							     =     self.bwd_astar.retrace_path(lowerCAmelCase_					)
     bwd_path.pop()
     bwd_path.reverse()
     __lowerCAmelCase							     =     fwd_path + bwd_path
     return path


if __name__ == "__main__":
     # all coordinates are given in format [y,x]
     _snake_case  :   List[Any]						   =  (0, 0)
     _snake_case  :   Union[str, Any]						   =  (len(grid) - 1, len(grid[0]) - 1)
     for elem in grid:
          print(elem)

     _snake_case  :   int						   =  time.time()
     _snake_case  :   Optional[int]						   =  AStar(init, goal)
     _snake_case  :   int						   =  a_star.search()
     _snake_case  :   Union[str, Any]						   =  time.time() - start_time
     print(F"""AStar execution time = {end_time:f} seconds""")

     _snake_case  :   Any						   =  time.time()
     _snake_case  :   Dict						   =  BidirectionalAStar(init, goal)
     _snake_case  :   Optional[int]						   =  time.time() - bd_start_time
     print(F"""BidirectionalAStar execution time = {bd_end_time:f} seconds""")

