import collections
import inspect
import unittest

from transformers import FocalNetConfig
from transformers.testing_utils import 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 (
	    FocalNetBackbone,
	    FocalNetForImageClassification,
	    FocalNetForMaskedImageModeling,
	    FocalNetModel,
	)
	from transformers.models.focalnet.modeling_focalnet import FOCALNET_PRETRAINED_MODEL_ARCHIVE_LIST

if is_vision_available():
	from PIL import Image

	from transformers import AutoImageProcessor


class   lowercase      :




							def __init__(  self				:   str		,							_UpperCamelCase				:   Any		,							_UpperCamelCase				:   Optional[int]=13		,							_UpperCamelCase				:   List[Any]=32		,							_UpperCamelCase				:   Tuple=2		,							_UpperCamelCase				:   str=3		,							_UpperCamelCase				:   Dict=16		,							_UpperCamelCase				:   Optional[Any]=[32, 64, 128]		,							_UpperCamelCase				:   Dict=[1, 2, 1]		,							_UpperCamelCase				:   str=[2, 2, 4]		,							_UpperCamelCase				:   Optional[Any]=2		,							_UpperCamelCase				:   Dict=2.0		,							_UpperCamelCase				:   Any=True		,							_UpperCamelCase				:   List[Any]=0.0		,							_UpperCamelCase				:   int=0.0		,							_UpperCamelCase				:   Union[str, Any]=0.1		,							_UpperCamelCase				:   Tuple="gelu"		,							_UpperCamelCase				:   Tuple=False		,							_UpperCamelCase				:   List[str]=True		,							_UpperCamelCase				:   int=0.0_2		,							_UpperCamelCase				:   Optional[Any]=1e-5		,							_UpperCamelCase				:   Tuple=True		,							_UpperCamelCase				:   str=None		,							_UpperCamelCase				:   Dict=True		,							_UpperCamelCase				:   Optional[Any]=10		,							_UpperCamelCase				:   Optional[int]=8		,							_UpperCamelCase				:   Union[str, Any]=["stage1", "stage2"]		,							_UpperCamelCase				:   Tuple=[1, 2]		,							)   ->			Optional[int]:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    parent
												SCREAMING_SNAKE_CASE           =    batch_size
												SCREAMING_SNAKE_CASE           =    image_size
												SCREAMING_SNAKE_CASE           =    patch_size
												SCREAMING_SNAKE_CASE           =    num_channels
												SCREAMING_SNAKE_CASE           =    embed_dim
												SCREAMING_SNAKE_CASE           =    hidden_sizes
												SCREAMING_SNAKE_CASE           =    depths
												SCREAMING_SNAKE_CASE           =    num_heads
												SCREAMING_SNAKE_CASE           =    window_size
												SCREAMING_SNAKE_CASE           =    mlp_ratio
												SCREAMING_SNAKE_CASE           =    qkv_bias
												SCREAMING_SNAKE_CASE           =    hidden_dropout_prob
												SCREAMING_SNAKE_CASE           =    attention_probs_dropout_prob
												SCREAMING_SNAKE_CASE           =    drop_path_rate
												SCREAMING_SNAKE_CASE           =    hidden_act
												SCREAMING_SNAKE_CASE           =    use_absolute_embeddings
												SCREAMING_SNAKE_CASE           =    patch_norm
												SCREAMING_SNAKE_CASE           =    layer_norm_eps
												SCREAMING_SNAKE_CASE           =    initializer_range
												SCREAMING_SNAKE_CASE           =    is_training
												SCREAMING_SNAKE_CASE           =    scope
												SCREAMING_SNAKE_CASE           =    use_labels
												SCREAMING_SNAKE_CASE           =    type_sequence_label_size
												SCREAMING_SNAKE_CASE           =    encoder_stride
												SCREAMING_SNAKE_CASE           =    out_features
												SCREAMING_SNAKE_CASE           =    out_indices




							def 		__snake_case(  self				:   List[Any] )   ->			List[str]:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size] )

												SCREAMING_SNAKE_CASE           =    None
												if self.use_labels:
																	SCREAMING_SNAKE_CASE           =    ids_tensor([self.batch_size]		,							self.type_sequence_label_size )

												SCREAMING_SNAKE_CASE           =    self.get_config()

												return config, pixel_values, labels




							def 		__snake_case(  self				:   List[Any] )   ->			Tuple:



												'''simple docstring'''

												return FocalNetConfig(
												    image_size=self.image_size		,							patch_size=self.patch_size		,							num_channels=self.num_channels		,							embed_dim=self.embed_dim		,							hidden_sizes=self.hidden_sizes		,							depths=self.depths		,							num_heads=self.num_heads		,							window_size=self.window_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		,							use_absolute_embeddings=self.use_absolute_embeddings		,							path_norm=self.patch_norm		,							layer_norm_eps=self.layer_norm_eps		,							initializer_range=self.initializer_range		,							encoder_stride=self.encoder_stride		,							out_features=self.out_features		,							out_indices=self.out_indices		,							)




							def 		__snake_case(  self				:   Optional[Any]		,							_UpperCamelCase				:   str		,							_UpperCamelCase				:   Optional[int]		,							_UpperCamelCase				:   Optional[int] )   ->			Union[str, Any]:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    FocalNetModel(config=_UpperCamelCase )
												model.to(_UpperCamelCase )
												model.eval()
												SCREAMING_SNAKE_CASE           =    model(_UpperCamelCase )

												SCREAMING_SNAKE_CASE           =    ((config.image_size // config.patch_size) ** 2) // (4 ** (len(config.depths ) - 1))
												SCREAMING_SNAKE_CASE           =    int(config.embed_dim * 2 ** (len(config.depths ) - 1) )

												self.parent.assertEqual(result.last_hidden_state.shape		,							(self.batch_size, expected_seq_len, expected_dim) )




							def 		__snake_case(  self				:   Tuple		,							_UpperCamelCase				:   Optional[Any]		,							_UpperCamelCase				:   Optional[Any]		,							_UpperCamelCase				:   Dict )   ->			Tuple:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    FocalNetBackbone(config=_UpperCamelCase )
												model.to(_UpperCamelCase )
												model.eval()
												SCREAMING_SNAKE_CASE           =    model(_UpperCamelCase )

												# verify feature maps
												self.parent.assertEqual(len(result.feature_maps )		,							len(config.out_features ) )
												self.parent.assertListEqual(list(result.feature_maps[0].shape )		,							[self.batch_size, self.image_size, 8, 8] )

												# verify channels
												self.parent.assertEqual(len(model.channels )		,							len(config.out_features ) )
												self.parent.assertListEqual(model.channels		,							config.hidden_sizes[:-1] )

												# verify backbone works with out_features=None
												SCREAMING_SNAKE_CASE           =    None
												SCREAMING_SNAKE_CASE           =    FocalNetBackbone(config=_UpperCamelCase )
												model.to(_UpperCamelCase )
												model.eval()
												SCREAMING_SNAKE_CASE           =    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, self.image_size * 2, 4, 4] )

												# verify channels
												self.parent.assertEqual(len(model.channels )		,							1 )
												self.parent.assertListEqual(model.channels		,							[config.hidden_sizes[-1]] )




							def 		__snake_case(  self				:   Union[str, Any]		,							_UpperCamelCase				:   str		,							_UpperCamelCase				:   Any		,							_UpperCamelCase				:   str )   ->			Dict:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    FocalNetForMaskedImageModeling(config=_UpperCamelCase )
												model.to(_UpperCamelCase )
												model.eval()
												SCREAMING_SNAKE_CASE           =    model(_UpperCamelCase )
												self.parent.assertEqual(
												    result.reconstruction.shape		,							(self.batch_size, self.num_channels, self.image_size, self.image_size) )

												# test greyscale images
												SCREAMING_SNAKE_CASE           =    1
												SCREAMING_SNAKE_CASE           =    FocalNetForMaskedImageModeling(_UpperCamelCase )
												model.to(_UpperCamelCase )
												model.eval()

												SCREAMING_SNAKE_CASE           =    floats_tensor([self.batch_size, 1, self.image_size, self.image_size] )
												SCREAMING_SNAKE_CASE           =    model(_UpperCamelCase )
												self.parent.assertEqual(result.reconstruction.shape		,							(self.batch_size, 1, self.image_size, self.image_size) )




							def 		__snake_case(  self				:   Dict		,							_UpperCamelCase				:   str		,							_UpperCamelCase				:   Any		,							_UpperCamelCase				:   int )   ->			Optional[int]:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    self.type_sequence_label_size
												SCREAMING_SNAKE_CASE           =    FocalNetForImageClassification(_UpperCamelCase )
												model.to(_UpperCamelCase )
												model.eval()
												SCREAMING_SNAKE_CASE           =    model(_UpperCamelCase		,							labels=_UpperCamelCase )
												self.parent.assertEqual(result.logits.shape		,							(self.batch_size, self.type_sequence_label_size) )

												# test greyscale images
												SCREAMING_SNAKE_CASE           =    1
												SCREAMING_SNAKE_CASE           =    FocalNetForImageClassification(_UpperCamelCase )
												model.to(_UpperCamelCase )
												model.eval()

												SCREAMING_SNAKE_CASE           =    floats_tensor([self.batch_size, 1, self.image_size, self.image_size] )
												SCREAMING_SNAKE_CASE           =    model(_UpperCamelCase )
												self.parent.assertEqual(result.logits.shape		,							(self.batch_size, self.type_sequence_label_size) )





							def 		__snake_case(  self				:   Optional[int] )   ->			str:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    self.prepare_config_and_inputs()

												SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    config_and_inputs
												SCREAMING_SNAKE_CASE           =    {"pixel_values": pixel_values}
												return config, inputs_dict



@require_torch
class   lowercase      (       _lowerCamelCase			,    _lowerCamelCase			,    unittest.TestCase       ):
							lowercase__  :    int									=							(
							    (
							        FocalNetModel,
							        FocalNetForImageClassification,
							        FocalNetForMaskedImageModeling,
							        FocalNetBackbone,
							    )
							    if is_torch_available()
							    else ()
							)
							lowercase__  :    Tuple									=							(
							    {"""feature-extraction""": FocalNetModel, """image-classification""": FocalNetForImageClassification}
							    if is_torch_available()
							    else {}
							)
							lowercase__  :    Dict									=							False

							lowercase__  :    Optional[int]									=							False
							lowercase__  :    Optional[int]									=							False
							lowercase__  :    int									=							False
							lowercase__  :    Union[str, Any]									=							False




							def 		__snake_case(  self				:   Optional[int] )   ->			List[str]:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    FocalNetModelTester(self )
												SCREAMING_SNAKE_CASE           =    ConfigTester(self		,							config_class=_UpperCamelCase		,							embed_dim=37		,							has_text_modality=_UpperCamelCase )




							def 		__snake_case(  self				:   Dict )   ->			Dict:



												'''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 		__snake_case(  self				:   Dict )   ->			str:



												'''simple docstring'''

												return




							def 		__snake_case(  self				:   Tuple )   ->			List[str]:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_model(*_UpperCamelCase )




							def 		__snake_case(  self				:   List[Any] )   ->			Union[str, Any]:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_backbone(*_UpperCamelCase )




							def 		__snake_case(  self				:   int )   ->			Dict:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_for_masked_image_modeling(*_UpperCamelCase )




							def 		__snake_case(  self				:   Optional[Any] )   ->			Dict:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_for_image_classification(*_UpperCamelCase )




							@unittest.skip(reason="FocalNet does not use inputs_embeds" )
							def 		__snake_case(  self				:   Optional[int] )   ->			Dict:



												'''simple docstring'''

												pass




							@unittest.skip(reason="FocalNet does not use feedforward chunking" )
							def 		__snake_case(  self				:   Dict )   ->			str:



												'''simple docstring'''

												pass




							def 		__snake_case(  self				:   Dict )   ->			Optional[int]:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.model_tester.prepare_config_and_inputs_for_common()

												for model_class in self.all_model_classes[:-1]:
																	SCREAMING_SNAKE_CASE           =    model_class(_UpperCamelCase )
																	self.assertIsInstance(model.get_input_embeddings()		,							(nn.Module) )
																	SCREAMING_SNAKE_CASE           =    model.get_output_embeddings()
																	self.assertTrue(x is None or isinstance(_UpperCamelCase		,							nn.Linear ) )




							def 		__snake_case(  self				:   Union[str, Any] )   ->			Any:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.model_tester.prepare_config_and_inputs_for_common()

												for model_class in self.all_model_classes[:-1]:
																	SCREAMING_SNAKE_CASE           =    model_class(_UpperCamelCase )
																	SCREAMING_SNAKE_CASE           =    inspect.signature(model.forward )
																	# signature.parameters is an OrderedDict => so arg_names order is deterministic
																	SCREAMING_SNAKE_CASE           =    [*signature.parameters.keys()]

																	SCREAMING_SNAKE_CASE           =    ["pixel_values"]
																	self.assertListEqual(arg_names[:1]		,							_UpperCamelCase )




							def 		__snake_case(  self				:   Tuple		,							_UpperCamelCase				:   Optional[int]		,							_UpperCamelCase				:   List[str]		,							_UpperCamelCase				:   Dict		,							_UpperCamelCase				:   int )   ->			Optional[Any]:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    model_class(_UpperCamelCase )
												model.to(_UpperCamelCase )
												model.eval()

												with torch.no_grad():
																	SCREAMING_SNAKE_CASE           =    model(**self._prepare_for_class(_UpperCamelCase		,							_UpperCamelCase ) )

												SCREAMING_SNAKE_CASE           =    outputs.hidden_states

												SCREAMING_SNAKE_CASE           =    getattr(
												    self.model_tester		,							"expected_num_hidden_layers"		,							len(self.model_tester.depths ) + 1 )
												self.assertEqual(len(_UpperCamelCase )		,							_UpperCamelCase )

												# FocalNet has a different seq_length
												SCREAMING_SNAKE_CASE           =    (
												    config.patch_size
												    if isinstance(config.patch_size		,							collections.abc.Iterable )
												    else (config.patch_size, config.patch_size)
												)

												SCREAMING_SNAKE_CASE           =    (image_size[1] // patch_size[1]) * (image_size[0] // patch_size[0])

												self.assertListEqual(
												    list(hidden_states[0].shape[-2:] )		,							[num_patches, self.model_tester.embed_dim]		,							)

												SCREAMING_SNAKE_CASE           =    outputs.reshaped_hidden_states
												self.assertEqual(len(_UpperCamelCase )		,							_UpperCamelCase )

												SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    reshaped_hidden_states[0].shape
												SCREAMING_SNAKE_CASE           =    (
												    reshaped_hidden_states[0].view(_UpperCamelCase		,							_UpperCamelCase		,							height * width ).permute(0		,							2		,							1 )
												)
												self.assertListEqual(
												    list(reshaped_hidden_states.shape[-2:] )		,							[num_patches, self.model_tester.embed_dim]		,							)




							def 		__snake_case(  self				:   List[str] )   ->			Tuple:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.model_tester.prepare_config_and_inputs_for_common()

												SCREAMING_SNAKE_CASE           =    (
												    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[:-1]:
																	SCREAMING_SNAKE_CASE           =    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"]
																	SCREAMING_SNAKE_CASE           =    True

																	self.check_hidden_states_output(_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase )




							def 		__snake_case(  self				:   str )   ->			List[Any]:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.model_tester.prepare_config_and_inputs_for_common()
												SCREAMING_SNAKE_CASE           =    3

												SCREAMING_SNAKE_CASE           =    (
												    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)
												)
												SCREAMING_SNAKE_CASE           =    (
												    config.patch_size
												    if isinstance(config.patch_size		,							collections.abc.Iterable )
												    else (config.patch_size, config.patch_size)
												)

												SCREAMING_SNAKE_CASE           =    image_size[0] + patch_size[0] - (image_size[0] % patch_size[0])
												SCREAMING_SNAKE_CASE           =    image_size[1] + patch_size[1] - (image_size[1] % patch_size[1])

												for model_class in self.all_model_classes[:-1]:
																	SCREAMING_SNAKE_CASE           =    True
																	self.check_hidden_states_output(_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							(padded_height, padded_width) )

																	# check that output_hidden_states also work using config
																	del inputs_dict["output_hidden_states"]
																	SCREAMING_SNAKE_CASE           =    True
																	self.check_hidden_states_output(_UpperCamelCase		,							_UpperCamelCase		,							_UpperCamelCase		,							(padded_height, padded_width) )




							@slow
							def 		__snake_case(  self				:   str )   ->			Union[str, Any]:



												'''simple docstring'''

												for model_name in FOCALNET_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																	SCREAMING_SNAKE_CASE           =    FocalNetModel.from_pretrained(_UpperCamelCase )
																	self.assertIsNotNone(_UpperCamelCase )





							def 		__snake_case(  self				:   Tuple )   ->			Dict:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE     ,				SCREAMING_SNAKE_CASE           =    self.model_tester.prepare_config_and_inputs_for_common()

												SCREAMING_SNAKE_CASE           =    _config_zero_init(_UpperCamelCase )
												for model_class in self.all_model_classes:
																	SCREAMING_SNAKE_CASE           =    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_vision
@require_torch
class   lowercase      (       unittest.TestCase       ):




							@cached_property
							def 		__snake_case(  self				:   Optional[Any] )   ->			List[Any]:



												'''simple docstring'''

												return AutoImageProcessor.from_pretrained("microsoft/focalnet-tiny" ) if is_vision_available() else None





							@slow
							def 		__snake_case(  self				:   List[str] )   ->			Optional[Any]:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    FocalNetForImageClassification.from_pretrained("microsoft/focalnet-tiny" ).to(_UpperCamelCase )
												SCREAMING_SNAKE_CASE           =    self.default_image_processor

												SCREAMING_SNAKE_CASE           =    Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png" )
												SCREAMING_SNAKE_CASE           =    image_processor(images=_UpperCamelCase		,							return_tensors="pt" ).to(_UpperCamelCase )

												# forward pass
												with torch.no_grad():
																	SCREAMING_SNAKE_CASE           =    model(**_UpperCamelCase )

												# verify the logits
												SCREAMING_SNAKE_CASE           =    torch.Size((1, 1_000) )
												self.assertEqual(outputs.logits.shape		,							_UpperCamelCase )
												SCREAMING_SNAKE_CASE           =    torch.tensor([0.2_1_6_6, -0.4_3_6_8, 0.2_1_9_1] ).to(_UpperCamelCase )
												self.assertTrue(torch.allclose(outputs.logits[0, :3]		,							_UpperCamelCase		,							atol=1e-4 ) )
												self.assertTrue(outputs.logits.argmax(dim=-1 ).item()		,							281 )



@require_torch
class   lowercase      (       _lowerCamelCase			,    unittest.TestCase       ):
							lowercase__  :    Dict									=							(FocalNetBackbone,) if is_torch_available() else ()
							lowercase__  :    Union[str, Any]									=							FocalNetConfig

							lowercase__  :    Optional[int]									=							False




							def 		__snake_case(  self				:   Tuple )   ->			Optional[Any]:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE           =    FocalNetModelTester(self )





from random import randint, random





def 		__lowerCamelCase							(UpperCAmelCase__       :							int ,	UpperCAmelCase__       :							int ,	UpperCAmelCase__       :							int ,	UpperCAmelCase__       :							bool = False ,	UpperCAmelCase__       :							bool = False ,	UpperCAmelCase__       :							int = 5 ,	):
					SCREAMING_SNAKE_CASE           =    [[-1] * number_of_cells]  # Create a highway without any car
					SCREAMING_SNAKE_CASE           =    0
					SCREAMING_SNAKE_CASE           =    max(UpperCAmelCase__ ,	0					)
					while i < number_of_cells:
										SCREAMING_SNAKE_CASE           =    (
										    randint(0 ,	UpperCAmelCase__					) if random_speed else initial_speed
										)  # Place the cars
										i += (
										    randint(1 ,	max_speed * 2					) if random_frequency else frequency
										)  # Arbitrary number, may need tuning
					return highway





def 		__lowerCamelCase							(UpperCAmelCase__       :							list ,	UpperCAmelCase__       :							int					):
					SCREAMING_SNAKE_CASE           =    0
					SCREAMING_SNAKE_CASE           =    highway_now[car_index + 1 :]
					for cell in range(len(UpperCAmelCase__					)					):  # May need a better name for this
										if cells[cell] != -1:  # If the cell is not empty then
															return distance  # we have the distance we wanted
										distance += 1
					# Here if the car is near the end of the highway
					return distance + get_distance(UpperCAmelCase__ ,	-1					)





def 		__lowerCamelCase							(UpperCAmelCase__       :							list ,	UpperCAmelCase__       :							float ,	UpperCAmelCase__       :							int					):
					SCREAMING_SNAKE_CASE           =    len(UpperCAmelCase__					)
					# Beforce calculations, the highway is empty
					SCREAMING_SNAKE_CASE           =    [-1] * number_of_cells

					for car_index in range(UpperCAmelCase__					):
										if highway_now[car_index] != -1:
															# Add 1 to the current speed of the car and cap the speed
															SCREAMING_SNAKE_CASE           =    min(highway_now[car_index] + 1 ,	UpperCAmelCase__					)
															# Number of empty cell before the next car
															SCREAMING_SNAKE_CASE           =    get_distance(UpperCAmelCase__ ,	UpperCAmelCase__					) - 1
															# We can't have the car causing an accident
															SCREAMING_SNAKE_CASE           =    min(next_highway[car_index] ,	UpperCAmelCase__					)
															if random() < probability:
																				# Randomly, a driver will slow down
																				SCREAMING_SNAKE_CASE           =    max(next_highway[car_index] - 1 ,	0					)
					return next_highway





def 		__lowerCamelCase							(UpperCAmelCase__       :							list ,	UpperCAmelCase__       :							int ,	UpperCAmelCase__       :							float ,	UpperCAmelCase__       :							int					):
					SCREAMING_SNAKE_CASE           =    len(highway[0]					)

					for i in range(UpperCAmelCase__					):
										SCREAMING_SNAKE_CASE           =    update(highway[i] ,	UpperCAmelCase__ ,	UpperCAmelCase__					)
										SCREAMING_SNAKE_CASE           =    [-1] * number_of_cells

										for car_index in range(UpperCAmelCase__					):
															SCREAMING_SNAKE_CASE           =    next_speeds_calculated[car_index]
															if speed != -1:
																				# Change the position based on the speed (with % to create the loop)
																				SCREAMING_SNAKE_CASE           =    (car_index + speed) % number_of_cells
																				# Commit the change of position
																				SCREAMING_SNAKE_CASE           =    speed
										highway.append(UpperCAmelCase__					)

					return highway


if __name__ == "__main__":
							import doctest

							doctest.testmod()




