



import os
from pickle import UnpicklingError
from typing import Dict, Tuple

import jax
import jax.numpy as jnp
import numpy as np
from flax.serialization import from_bytes
from flax.traverse_util import flatten_dict, unflatten_dict

import transformers

from .utils import logging


a      :  str			     =			logging.get_logger(__name__)







def  lowerCAmelCase_	(lowerCAmelCase__:		Union[str, Any]		,						lowerCAmelCase__:		Any		,						lowerCAmelCase__:		Tuple		,						lowerCAmelCase__:		Optional[Any]=False  ):





			"""simple docstring"""


			try:
						import torch  # noqa: F401
			except ImportError:
						logger.error(
						    """Loading a PyTorch model in Flax, requires both PyTorch and Flax to be installed. Please see"""
						    """ https://pytorch.org/ and https://flax.readthedocs.io/en/latest/installation.html for installation"""
						    """ instructions."""  )
						raise

			if not is_sharded:
						UpperCAmelCase_:		str							      =     os.path.abspath(lowerCAmelCase__  )
						logger.info(F'Loading PyTorch weights from {pt_path}'  )

						UpperCAmelCase_:		Optional[Any]							      =     torch.load(lowerCAmelCase__		,						map_location="""cpu"""  )
						logger.info(F'PyTorch checkpoint contains {sum(t.numel() for t in pt_state_dict.values()  ):,} parameters.'  )

						UpperCAmelCase_:		Tuple							      =     convert_pytorch_state_dict_to_flax(lowerCAmelCase__		,						lowerCAmelCase__  )
			else:
						# model is sharded and pytorch_checkpoint_path already contains the list of .pt shard files
						UpperCAmelCase_:		Any							      =     convert_pytorch_sharded_state_dict_to_flax(lowerCAmelCase__		,						lowerCAmelCase__  )
			return flax_state_dict







def  lowerCAmelCase_	(lowerCAmelCase__:		Tuple[str]		,						lowerCAmelCase__:		np.ndarray		,						lowerCAmelCase__:		Dict[str, jnp.ndarray]		,						lowerCAmelCase__:		str		,						):





			"""simple docstring"""


			def is_key_or_prefix_key_in_dict(lowerCAmelCase__:		Tuple[str]  ) -> bool:
						return len(set(lowerCAmelCase__  ) & {key, (model_prefix,) + key}  ) > 0

			# layer norm
			UpperCAmelCase_:		Optional[Any]							      =     pt_tuple_key[:-1] + ("""scale""",)
			if pt_tuple_key[-1] in ["weight", "gamma"] and is_key_or_prefix_key_in_dict(lowerCAmelCase__  ):
						return renamed_pt_tuple_key, pt_tensor

			# batch norm layer mean
			UpperCAmelCase_:		Optional[int]							      =     pt_tuple_key[:-1] + ("""mean""",)
			if pt_tuple_key[-1] == "running_mean" and not is_key_or_prefix_key_in_dict(lowerCAmelCase__  ):
						return renamed_pt_tuple_key, pt_tensor

			# batch norm layer var
			UpperCAmelCase_:		str							      =     pt_tuple_key[:-1] + ("""var""",)
			if pt_tuple_key[-1] == "running_var" and not is_key_or_prefix_key_in_dict(lowerCAmelCase__  ):
						return renamed_pt_tuple_key, pt_tensor

			# embedding
			UpperCAmelCase_:		Optional[int]							      =     pt_tuple_key[:-1] + ("""embedding""",)
			if pt_tuple_key[-1] == "weight" and is_key_or_prefix_key_in_dict(lowerCAmelCase__  ):
						return renamed_pt_tuple_key, pt_tensor

			# conv layer
			UpperCAmelCase_:		Optional[int]							      =     pt_tuple_key[:-1] + ("""kernel""",)
			if pt_tuple_key[-1] == "weight" and pt_tensor.ndim == 4 and not is_key_or_prefix_key_in_dict(lowerCAmelCase__  ):
						UpperCAmelCase_:		Union[str, Any]							      =     pt_tensor.transpose(2		,						3		,						1		,						0  )
						return renamed_pt_tuple_key, pt_tensor

			# linear layer
			UpperCAmelCase_:		Tuple							      =     pt_tuple_key[:-1] + ("""kernel""",)
			if pt_tuple_key[-1] == "weight" and not is_key_or_prefix_key_in_dict(lowerCAmelCase__  ):
						UpperCAmelCase_:		int							      =     pt_tensor.T
						return renamed_pt_tuple_key, pt_tensor

			# old PyTorch layer norm weight
			UpperCAmelCase_:		int							      =     pt_tuple_key[:-1] + ("""weight""",)
			if pt_tuple_key[-1] == "gamma":
						return renamed_pt_tuple_key, pt_tensor

			# old PyTorch layer norm bias
			UpperCAmelCase_:		List[Any]							      =     pt_tuple_key[:-1] + ("""bias""",)
			if pt_tuple_key[-1] == "beta":
						return renamed_pt_tuple_key, pt_tensor

			# New `weight_norm` from https://github.com/huggingface/transformers/pull/24030
			UpperCAmelCase_:		Optional[Any]							      =     None
			if pt_tuple_key[-3::2] == ("parametrizations", "original0"):
						UpperCAmelCase_:		Any							      =     pt_tuple_key[-2] + """_g"""
			elif pt_tuple_key[-3::2] == ("parametrizations", "original1"):
						UpperCAmelCase_:		List[Any]							      =     pt_tuple_key[-2] + """_v"""
			if name is not None:
						UpperCAmelCase_:		int							      =     pt_tuple_key[:-3] + (name,)
						return renamed_pt_tuple_key, pt_tensor

			return pt_tuple_key, pt_tensor







def  lowerCAmelCase_	(lowerCAmelCase__:		Dict		,						lowerCAmelCase__:		Optional[Any]  ):





			"""simple docstring"""


			UpperCAmelCase_:		Optional[int]							      =     {k: v.numpy() for k, v in pt_state_dict.items()}

			UpperCAmelCase_:		List[Any]							      =     flax_model.base_model_prefix

			# use params dict if the model contains batch norm layers
			if "params" in flax_model.params:
						UpperCAmelCase_:		Optional[Any]							      =     flax_model.params["""params"""]
			else:
						UpperCAmelCase_:		Union[str, Any]							      =     flax_model.params
			UpperCAmelCase_:		List[Any]							      =     flatten_dict(lowerCAmelCase__  )

			# add batch_stats keys,values to dict
			if "batch_stats" in flax_model.params:
						UpperCAmelCase_:		List[str]							      =     flatten_dict(flax_model.params["""batch_stats"""]  )
						random_flax_state_dict.update(lowerCAmelCase__  )

			UpperCAmelCase_:		Optional[int]							      =     {}

			UpperCAmelCase_:		Any							      =     (model_prefix not in flax_model_params) and (
			    model_prefix in {k.split("""."""  )[0] for k in pt_state_dict.keys()}
			)
			UpperCAmelCase_:		Tuple							      =     (model_prefix in flax_model_params) and (
			    model_prefix not in {k.split("""."""  )[0] for k in pt_state_dict.keys()}
			)

			# Need to change some parameters name to match Flax names
			for pt_key, pt_tensor in pt_state_dict.items():
						UpperCAmelCase_:		Any							      =     tuple(pt_key.split("""."""  )  )

						# remove base model prefix if necessary
						UpperCAmelCase_:		Dict							      =     pt_tuple_key[0] == model_prefix
						if load_model_with_head_into_base_model and has_base_model_prefix:
									UpperCAmelCase_:		Optional[Any]							      =     pt_tuple_key[1:]

						# Correctly rename weight parameters
						UpperCAmelCase_      ,							UpperCAmelCase_:		int							      =     rename_key_and_reshape_tensor(
						    lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__  )

						# add model prefix if necessary
						UpperCAmelCase_:		Optional[int]							      =     (model_prefix,) + flax_key in random_flax_state_dict
						if load_base_model_into_model_with_head and require_base_model_prefix:
									UpperCAmelCase_:		Dict							      =     (model_prefix,) + flax_key

						if flax_key in random_flax_state_dict:
									if flax_tensor.shape != random_flax_state_dict[flax_key].shape:
												raise ValueError(
												    F'PyTorch checkpoint seems to be incorrect. Weight {pt_key} was expected to be of shape '
												    F'{random_flax_state_dict[flax_key].shape}, but is {flax_tensor.shape}.'  )

        # add batch stats if the model contains batchnorm layers
						if "batch_stats" in flax_model.params:
									if "mean" in flax_key[-1] or "var" in flax_key[-1]:
												UpperCAmelCase_:		Optional[int]							      =     jnp.asarray(lowerCAmelCase__  )
												continue
									# remove num_batches_tracked key
									if "num_batches_tracked" in flax_key[-1]:
												flax_state_dict.pop(lowerCAmelCase__		,						lowerCAmelCase__  )
												continue

									# also add unexpected weight so that warning is thrown
									UpperCAmelCase_:		Dict							      =     jnp.asarray(lowerCAmelCase__  )

						else:
									# also add unexpected weight so that warning is thrown
									UpperCAmelCase_:		List[str]							      =     jnp.asarray(lowerCAmelCase__  )

			return unflatten_dict(lowerCAmelCase__  )







def  lowerCAmelCase_	(lowerCAmelCase__:		Union[str, Any]		,						lowerCAmelCase__:		str  ):





			"""simple docstring"""


			import torch

			# Load the index
			UpperCAmelCase_:		Optional[Any]							      =     {}
			for shard_file in shard_filenames:
						# load using msgpack utils
						UpperCAmelCase_:		int							      =     torch.load(lowerCAmelCase__  )
						UpperCAmelCase_:		str							      =     {k: v.numpy() for k, v in pt_state_dict.items()}

						UpperCAmelCase_:		Any							      =     flax_model.base_model_prefix

						# use params dict if the model contains batch norm layers and then add batch_stats keys,values to dict
						if "batch_stats" in flax_model.params:
									UpperCAmelCase_:		int							      =     flax_model.params["""params"""]

									UpperCAmelCase_:		List[Any]							      =     flatten_dict(lowerCAmelCase__  )
									random_flax_state_dict.update(flatten_dict(flax_model.params["""batch_stats"""]  )  )
						else:
									UpperCAmelCase_:		Tuple							      =     flax_model.params
									UpperCAmelCase_:		Optional[Any]							      =     flatten_dict(lowerCAmelCase__  )

						UpperCAmelCase_:		List[Any]							      =     (model_prefix not in flax_model_params) and (
						    model_prefix in {k.split("""."""  )[0] for k in pt_state_dict.keys()}
						)
						UpperCAmelCase_:		Optional[int]							      =     (model_prefix in flax_model_params) and (
						    model_prefix not in {k.split("""."""  )[0] for k in pt_state_dict.keys()}
						)
						# Need to change some parameters name to match Flax names
						for pt_key, pt_tensor in pt_state_dict.items():
									UpperCAmelCase_:		Union[str, Any]							      =     tuple(pt_key.split("""."""  )  )

									# remove base model prefix if necessary
									UpperCAmelCase_:		Tuple							      =     pt_tuple_key[0] == model_prefix
									if load_model_with_head_into_base_model and has_base_model_prefix:
												UpperCAmelCase_:		str							      =     pt_tuple_key[1:]

									# Correctly rename weight parameters
									UpperCAmelCase_      ,							UpperCAmelCase_:		Dict							      =     rename_key_and_reshape_tensor(
									    lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__  )
									# add model prefix if necessary
									UpperCAmelCase_:		int							      =     (model_prefix,) + flax_key in random_flax_state_dict
									if load_base_model_into_model_with_head and require_base_model_prefix:
												UpperCAmelCase_:		str							      =     (model_prefix,) + flax_key

									if flax_key in random_flax_state_dict:
												if flax_tensor.shape != random_flax_state_dict[flax_key].shape:
															raise ValueError(
															    F'PyTorch checkpoint seems to be incorrect. Weight {pt_key} was expected to be of shape '
															    F'{random_flax_state_dict[flax_key].shape}, but is {flax_tensor.shape}.'  )

            # add batch stats if the model contains batchnorm layers
									if "batch_stats" in flax_model.params:
												if "mean" in flax_key[-1]:
															UpperCAmelCase_:		List[Any]							      =     jnp.asarray(lowerCAmelCase__  )
															continue
												if "var" in flax_key[-1]:
															UpperCAmelCase_:		Union[str, Any]							      =     jnp.asarray(lowerCAmelCase__  )
															continue
												# remove num_batches_tracked key
												if "num_batches_tracked" in flax_key[-1]:
															flax_state_dict.pop(lowerCAmelCase__		,						lowerCAmelCase__  )
															continue

												# also add unexpected weight so that warning is thrown
												UpperCAmelCase_:		Tuple							      =     jnp.asarray(lowerCAmelCase__  )

									else:
												# also add unexpected weight so that warning is thrown
												UpperCAmelCase_:		Optional[Any]							      =     jnp.asarray(lowerCAmelCase__  )
			return unflatten_dict(lowerCAmelCase__  )







def  lowerCAmelCase_	(lowerCAmelCase__:		List[str]		,						lowerCAmelCase__:		List[Any]  ):





			"""simple docstring"""


			UpperCAmelCase_:		Union[str, Any]							      =     os.path.abspath(lowerCAmelCase__  )
			logger.info(F'Loading Flax weights from {flax_checkpoint_path}'  )

			# import correct flax class
			UpperCAmelCase_:		List[Any]							      =     getattr(lowerCAmelCase__		,						"""Flax""" + model.__class__.__name__  )

			# load flax weight dict
			with open(lowerCAmelCase__		,						"""rb"""  ) as state_f:
						try:
									UpperCAmelCase_:		Optional[int]							      =     from_bytes(lowerCAmelCase__		,						state_f.read()  )
						except UnpicklingError:
									raise EnvironmentError(F'Unable to convert {flax_checkpoint_path} to Flax deserializable object. '  )

			return load_flax_weights_in_pytorch_model(lowerCAmelCase__		,						lowerCAmelCase__  )







def  lowerCAmelCase_	(lowerCAmelCase__:		str		,						lowerCAmelCase__:		Union[str, Any]  ):





			"""simple docstring"""


			try:
						import torch  # noqa: F401
			except ImportError:
						logger.error(
						    """Loading a Flax weights in PyTorch, requires both PyTorch and Flax to be installed. Please see"""
						    """ https://pytorch.org/ and https://flax.readthedocs.io/en/latest/installation.html for installation"""
						    """ instructions."""  )
						raise

			# check if we have bf16 weights
			UpperCAmelCase_:		str							      =     flatten_dict(jax.tree_util.tree_map(lambda lowerCAmelCase__  : x.dtype == jnp.bfloataa		,						lowerCAmelCase__  )  ).values()
			if any(lowerCAmelCase__  ):
						# convert all weights to fp32 if the are bf16 since torch.from_numpy can-not handle bf16
						# and bf16 is not fully supported in PT yet.
						logger.warning(
						    """Found ``bfloat16`` weights in Flax model. Casting all ``bfloat16`` weights to ``float32`` """
						    """before loading those in PyTorch model."""  )
						UpperCAmelCase_:		List[str]							      =     jax.tree_util.tree_map(
						    lambda lowerCAmelCase__  : params.astype(np.floataa  ) if params.dtype == jnp.bfloataa else params		,						lowerCAmelCase__  )

			UpperCAmelCase_:		List[Any]							      =     flatten_dict(lowerCAmelCase__  )
			UpperCAmelCase_:		List[Any]							      =     pt_model.state_dict()

			UpperCAmelCase_:		Dict							      =     (pt_model.base_model_prefix in flax_state) and (
			    pt_model.base_model_prefix not in {k.split("""."""  )[0] for k in pt_model_dict.keys()}
			)
			UpperCAmelCase_:		Union[str, Any]							      =     (pt_model.base_model_prefix not in flax_state) and (
			    pt_model.base_model_prefix in {k.split("""."""  )[0] for k in pt_model_dict.keys()}
			)

			# keep track of unexpected & missing keys
			UpperCAmelCase_:		List[str]							      =     []
			UpperCAmelCase_:		Optional[Any]							      =     set(pt_model_dict.keys()  )

			for flax_key_tuple, flax_tensor in flax_state_dict.items():
						UpperCAmelCase_:		str							      =     flax_key_tuple[0] == pt_model.base_model_prefix
						UpperCAmelCase_:		Optional[int]							      =     """.""".join((pt_model.base_model_prefix,) + flax_key_tuple  ) in pt_model_dict

						# adapt flax_key to prepare for loading from/to base model only
						if load_model_with_head_into_base_model and has_base_model_prefix:
									UpperCAmelCase_:		Optional[Any]							      =     flax_key_tuple[1:]
						elif load_base_model_into_model_with_head and require_base_model_prefix:
									UpperCAmelCase_:		Optional[Any]							      =     (pt_model.base_model_prefix,) + flax_key_tuple

						# rename flax weights to PyTorch format
						if flax_key_tuple[-1] == "kernel" and flax_tensor.ndim == 4 and ".".join(lowerCAmelCase__  ) not in pt_model_dict:
									# conv layer
									UpperCAmelCase_:		Optional[Any]							      =     flax_key_tuple[:-1] + ("""weight""",)
									UpperCAmelCase_:		List[str]							      =     jnp.transpose(lowerCAmelCase__		,						(3, 2, 0, 1)  )
						elif flax_key_tuple[-1] == "kernel" and ".".join(lowerCAmelCase__  ) not in pt_model_dict:
									# linear layer
									UpperCAmelCase_:		Tuple							      =     flax_key_tuple[:-1] + ("""weight""",)
									UpperCAmelCase_:		Union[str, Any]							      =     flax_tensor.T
						elif flax_key_tuple[-1] in ["scale", "embedding"]:
									UpperCAmelCase_:		Optional[int]							      =     flax_key_tuple[:-1] + ("""weight""",)

						# adding batch stats from flax batch norm to pt
						elif "mean" in flax_key_tuple[-1]:
									UpperCAmelCase_:		Dict							      =     flax_key_tuple[:-1] + ("""running_mean""",)
						elif "var" in flax_key_tuple[-1]:
									UpperCAmelCase_:		Union[str, Any]							      =     flax_key_tuple[:-1] + ("""running_var""",)

						if "batch_stats" in flax_state:
									UpperCAmelCase_:		Optional[Any]							      =     """.""".join(flax_key_tuple[1:]  )  # Remove the params/batch_stats header
						else:
									UpperCAmelCase_:		Optional[Any]							      =     """.""".join(lowerCAmelCase__  )

						# We also need to look at `pt_model_dict` and see if there are keys requiring further transformation.
						UpperCAmelCase_:		str							      =     {}
						# New `weight_norm` from https://github.com/huggingface/transformers/pull/24030
						for key in pt_model_dict:
									UpperCAmelCase_:		Tuple							      =     key.split("""."""  )
									UpperCAmelCase_:		str							      =     None
									if key_components[-3::2] == ["parametrizations", "original0"]:
												UpperCAmelCase_:		int							      =     key_components[-2] + """_g"""
									elif key_components[-3::2] == ["parametrizations", "original1"]:
												UpperCAmelCase_:		List[str]							      =     key_components[-2] + """_v"""
									if name is not None:
												UpperCAmelCase_:		Dict							      =     key_components[:-3] + [name]
												UpperCAmelCase_:		List[Any]							      =     """.""".join(lowerCAmelCase__  )
												UpperCAmelCase_:		Union[str, Any]							      =     key

						if flax_key in special_pt_names:
									UpperCAmelCase_:		int							      =     special_pt_names[flax_key]

						if flax_key in pt_model_dict:
									if flax_tensor.shape != pt_model_dict[flax_key].shape:
												raise ValueError(
												    F'Flax checkpoint seems to be incorrect. Weight {flax_key_tuple} was expected '
												    F'to be of shape {pt_model_dict[flax_key].shape}, but is {flax_tensor.shape}.'  )
									else:
												# add weight to pytorch dict
												UpperCAmelCase_:		Union[str, Any]							      =     np.asarray(lowerCAmelCase__  ) if not isinstance(lowerCAmelCase__		,						np.ndarray  ) else flax_tensor
												UpperCAmelCase_:		Optional[Any]							      =     torch.from_numpy(lowerCAmelCase__  )
												# remove from missing keys
												missing_keys.remove(lowerCAmelCase__  )
						else:
									# weight is not expected by PyTorch model
									unexpected_keys.append(lowerCAmelCase__  )

			pt_model.load_state_dict(lowerCAmelCase__  )

			# re-transform missing_keys to list
			UpperCAmelCase_:		int							      =     list(lowerCAmelCase__  )

			if len(lowerCAmelCase__  ) > 0:
						logger.warning(
						    """Some weights of the Flax model were not used when initializing the PyTorch model"""
						    F' {pt_model.__class__.__name__}: {unexpected_keys}\n- This IS expected if you are initializing'
						    F' {pt_model.__class__.__name__} from a Flax model trained on another task or with another architecture'
						    """ (e.g. initializing a BertForSequenceClassification model from a FlaxBertForPreTraining model).\n- This"""
						    F' IS NOT expected if you are initializing {pt_model.__class__.__name__} from a Flax model that you expect'
						    """ to be exactly identical (e.g. initializing a BertForSequenceClassification model from a"""
						    """ FlaxBertForSequenceClassification model)."""  )
			else:
						logger.warning(F'All Flax model weights were used when initializing {pt_model.__class__.__name__}.\n'  )
			if len(lowerCAmelCase__  ) > 0:
						logger.warning(
						    F'Some weights of {pt_model.__class__.__name__} were not initialized from the Flax model and are newly'
						    F' initialized: {missing_keys}\nYou should probably TRAIN this model on a down-stream task to be able to'
						    """ use it for predictions and inference."""  )
			else:
						logger.warning(
						    F'All the weights of {pt_model.__class__.__name__} were initialized from the Flax model.\n'
						    """If your task is similar to the task the model of the checkpoint was trained on, """
						    F'you can already use {pt_model.__class__.__name__} for predictions without further training.'  )

			return pt_model











def  lowerCAmelCase_	(lowerCAmelCase__:		Union[str, Any]		,						lowerCAmelCase__:		Optional[int]  ):





			"""simple docstring"""


			UpperCAmelCase_:		List[str]							      =     0
			UpperCAmelCase_:		Tuple							      =     len(lowerCAmelCase__  ) - 1

			while left <= right:
						# avoid divided by 0 during interpolation
						if sorted_collection[left] == sorted_collection[right]:
									if sorted_collection[left] == item:
												return left
									else:
												return None

						UpperCAmelCase_:		Dict							      =     left + ((item - sorted_collection[left]) * (right - left)) // (
						    sorted_collection[right] - sorted_collection[left]
						)

						# out of range check
						if point < 0 or point >= len(lowerCAmelCase__  ):
									return None

						UpperCAmelCase_:		str							      =     sorted_collection[point]
						if current_item == item:
									return point
						else:
									if point < left:
												UpperCAmelCase_:		int							      =     left
												UpperCAmelCase_:		str							      =     point
									elif point > right:
												UpperCAmelCase_:		List[str]							      =     right
												UpperCAmelCase_:		Optional[int]							      =     point
									else:
												if item < current_item:
															UpperCAmelCase_:		Optional[Any]							      =     point - 1
												else:
															UpperCAmelCase_:		Any							      =     point + 1
			return None







def  lowerCAmelCase_	(lowerCAmelCase__:		Dict		,						lowerCAmelCase__:		List[Any]		,						lowerCAmelCase__:		Any		,						lowerCAmelCase__:		Any  ):





			"""simple docstring"""


			if sorted_collection[left] == sorted_collection[right]:
						if sorted_collection[left] == item:
									return left
						else:
									return None

			UpperCAmelCase_:		Union[str, Any]							      =     left + ((item - sorted_collection[left]) * (right - left)) // (
			    sorted_collection[right] - sorted_collection[left]
			)

			# out of range check
			if point < 0 or point >= len(lowerCAmelCase__  ):
						return None

			if sorted_collection[point] == item:
						return point
			elif point < left:
						return interpolation_search_by_recursion(lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__  )
			elif point > right:
						return interpolation_search_by_recursion(lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__  )
			else:
						if sorted_collection[point] > item:
									return interpolation_search_by_recursion(
									    lowerCAmelCase__		,						lowerCAmelCase__		,						lowerCAmelCase__		,						point - 1  )
						else:
									return interpolation_search_by_recursion(
									    lowerCAmelCase__		,						lowerCAmelCase__		,						point + 1		,						lowerCAmelCase__  )







def  lowerCAmelCase_	(lowerCAmelCase__:		Dict  ):





			"""simple docstring"""


			if collection != sorted(lowerCAmelCase__  ):
						raise ValueError("""Collection must be ascending sorted"""  )
			return True


if __name__ == "__main__":
	import sys
	a      :  Optional[Any]			     =			0
	if debug == 1:
		a      :  int			     =			[10, 30, 40, 45, 50, 66, 77, 93]
		try:
			__assert_sorted(collection)
		except ValueError:
			sys.exit('Sequence must be ascending sorted to apply interpolation search')
		a      :  int			     =			67

	a      :  Any			     =			interpolation_search(collection, target)
	if result is not None:
		print(F'''{target} found at positions: {result}''')
	else:
		print('Not found')






