
import unittest

import numpy as np

from transformers import is_flax_available
from transformers.testing_utils import require_flax

from ..test_modeling_flax_common import ids_tensor


if is_flax_available():
			import jax
			import jax.numpy as jnp

			from transformers.generation import (
			    FlaxForcedBOSTokenLogitsProcessor,
			    FlaxForcedEOSTokenLogitsProcessor,
			    FlaxLogitsProcessorList,
			    FlaxMinLengthLogitsProcessor,
			    FlaxTemperatureLogitsWarper,
			    FlaxTopKLogitsWarper,
			    FlaxTopPLogitsWarper,
			)





@require_flax
class 			_lowerCAmelCase      (			unittest.TestCase ):




				def   __a		(      self       ,       _UpperCamelCase       ,       _UpperCamelCase  )       ->   Optional[int]:
							lowerCAmelCase_      			=			jnp.ones((batch_size, length)  ) / length
							return scores




				def   __a		(      self  )       ->   str:
							lowerCAmelCase_      			=			None
							lowerCAmelCase_      			=			20

							lowerCAmelCase_      			=			self._get_uniform_logits(batch_size=2       ,       length=_UpperCamelCase  )

							# tweak scores to not be uniform anymore
							lowerCAmelCase_      			=			scores.at[1, 5].set((1 / length) + 0.1  )  # peak, 1st batch
							lowerCAmelCase_      			=			scores.at[1, 10].set((1 / length) - 0.4  )  # valley, 1st batch

							# compute softmax
							lowerCAmelCase_      			=			jax.nn.softmax(_UpperCamelCase       ,       axis=-1  )

							lowerCAmelCase_      			=			FlaxTemperatureLogitsWarper(temperature=0.5  )
							lowerCAmelCase_      			=			FlaxTemperatureLogitsWarper(temperature=1.3  )

							lowerCAmelCase_      			=			jax.nn.softmax(temp_dist_warper_sharper(_UpperCamelCase       ,       scores.copy()       ,       cur_len=_UpperCamelCase  )       ,       axis=-1  )
							lowerCAmelCase_      			=			jax.nn.softmax(temp_dist_warper_smoother(_UpperCamelCase       ,       scores.copy()       ,       cur_len=_UpperCamelCase  )       ,       axis=-1  )

							# uniform distribution stays uniform
							self.assertTrue(jnp.allclose(probs[0, :]       ,       warped_prob_sharp[0, :]       ,       atol=1e-3  )  )
							self.assertTrue(jnp.allclose(probs[0, :]       ,       warped_prob_smooth[0, :]       ,       atol=1e-3  )  )

							# sharp peaks get higher, valleys get lower
							self.assertLess(probs[1, :].max()       ,       warped_prob_sharp[1, :].max()  )
							self.assertGreater(probs[1, :].min()       ,       warped_prob_sharp[1, :].min()  )

							# smooth peaks get lower, valleys get higher
							self.assertGreater(probs[1, :].max()       ,       warped_prob_smooth[1, :].max()  )
							self.assertLess(probs[1, :].min()       ,       warped_prob_smooth[1, :].min()  )




				def   __a		(      self  )       ->   Dict:
							lowerCAmelCase_      			=			None
							lowerCAmelCase_      			=			10
							lowerCAmelCase_      			=			2

							# create ramp distribution
							lowerCAmelCase_      			=			np.broadcast_to(np.arange(_UpperCamelCase  )[None, :]       ,       (batch_size, vocab_size)  ).copy()
							lowerCAmelCase_      			=			ramp_logits[1:, : vocab_size // 2] + vocab_size

							lowerCAmelCase_      			=			FlaxTopKLogitsWarper(3  )

							lowerCAmelCase_      			=			top_k_warp(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )

							# check that correct tokens are filtered
							self.assertListEqual(jnp.isinf(scores[0]  ).tolist()       ,       7 * [True] + 3 * [False]  )
							self.assertListEqual(jnp.isinf(scores[1]  ).tolist()       ,       2 * [True] + 3 * [False] + 5 * [True]  )

							# check special case
							lowerCAmelCase_      			=			5
							lowerCAmelCase_      			=			FlaxTopKLogitsWarper(top_k=1       ,       filter_value=0.0       ,       min_tokens_to_keep=3  )

							lowerCAmelCase_      			=			np.broadcast_to(np.arange(_UpperCamelCase  )[None, :]       ,       (batch_size, length)  ).copy()
							lowerCAmelCase_      			=			top_k_warp_safety_check(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )

							# min_tokens overwrites k: 3 tokens are kept => 2 tokens are nullified
							self.assertListEqual((scores == 0.0).sum(axis=-1  ).tolist()       ,       [2, 2]  )




				def   __a		(      self  )       ->   List[Any]:
							lowerCAmelCase_      			=			None
							lowerCAmelCase_      			=			10
							lowerCAmelCase_      			=			2

							# create distribution and take log (inverse to Softmax as taken in TopPLogitsWarper)
							lowerCAmelCase_      			=			np.log(np.array([[0.3, 0.1, 0.1, 0.5], [0.15, 0.3, 0.3, 0.25]]  )  )

							lowerCAmelCase_      			=			FlaxTopPLogitsWarper(0.8  )
							lowerCAmelCase_      			=			np.exp(top_p_warp(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )  )

							# dist should be filtered to keep min num values so that sum is >= top_p
							# exp (-inf) => 0
							lowerCAmelCase_      			=			np.array([[0.3, 0.0, 0.0, 0.5], [0.0, 0.3, 0.3, 0.25]]  )
							self.assertTrue(np.allclose(_UpperCamelCase       ,       _UpperCamelCase       ,       atol=1e-3  )  )

							# check edge cases with negative and extreme logits
							lowerCAmelCase_      			=			np.broadcast_to(np.arange(_UpperCamelCase  )[None, :]       ,       (batch_size, vocab_size)  ).copy() - (
							    vocab_size // 2
							)

							# make ramp_logits more extreme
							lowerCAmelCase_      			=			ramp_logits[1] * 100.0

							# make sure at least 2 tokens are kept
							lowerCAmelCase_      			=			FlaxTopPLogitsWarper(0.9       ,       min_tokens_to_keep=2       ,       filter_value=0.0  )
							lowerCAmelCase_      			=			top_p_warp(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )

							# first batch should keep three tokens, second batch would keep only 1, but due to `min_tokens_to_keep=2` keeps 2.
							self.assertListEqual((filtered_dist != 0.0).sum(axis=-1  ).tolist()       ,       [3, 2]  )




				def   __a		(      self  )       ->   str:
							lowerCAmelCase_      			=			20
							lowerCAmelCase_      			=			4
							lowerCAmelCase_      			=			0

							lowerCAmelCase_      			=			FlaxMinLengthLogitsProcessor(min_length=10       ,       eos_token_id=_UpperCamelCase  )

							# check that min length is applied at length 5
							lowerCAmelCase_      			=			ids_tensor((batch_size, 20)       ,       vocab_size=20  )
							lowerCAmelCase_      			=			5
							lowerCAmelCase_      			=			self._get_uniform_logits(_UpperCamelCase       ,       _UpperCamelCase  )
							lowerCAmelCase_      			=			min_dist_processor(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
							self.assertListEqual(scores_before_min_length[:, eos_token_id].tolist()       ,       4 * [-float("inf"  )]  )

							# check that min length is not applied anymore at length 15
							lowerCAmelCase_      			=			self._get_uniform_logits(_UpperCamelCase       ,       _UpperCamelCase  )
							lowerCAmelCase_      			=			15
							lowerCAmelCase_      			=			min_dist_processor(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
							self.assertFalse(jnp.isinf(_UpperCamelCase  ).any()  )




				def   __a		(      self  )       ->   str:
							lowerCAmelCase_      			=			20
							lowerCAmelCase_      			=			4
							lowerCAmelCase_      			=			0

							lowerCAmelCase_      			=			FlaxForcedBOSTokenLogitsProcessor(bos_token_id=_UpperCamelCase  )

							# check that all scores are -inf except the bos_token_id score
							lowerCAmelCase_      			=			ids_tensor((batch_size, 1)       ,       vocab_size=20  )
							lowerCAmelCase_      			=			1
							lowerCAmelCase_      			=			self._get_uniform_logits(_UpperCamelCase       ,       _UpperCamelCase  )
							lowerCAmelCase_      			=			logits_processor(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
							self.assertTrue(jnp.isneginf(scores[:, bos_token_id + 1 :]  ).all()  )
							self.assertListEqual(scores[:, bos_token_id].tolist()       ,       4 * [0]  )  # score for bos_token_id shold be zero

							# check that bos_token_id is not forced if current length is greater than 1
							lowerCAmelCase_      			=			3
							lowerCAmelCase_      			=			self._get_uniform_logits(_UpperCamelCase       ,       _UpperCamelCase  )
							lowerCAmelCase_      			=			logits_processor(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
							self.assertFalse(jnp.isinf(_UpperCamelCase  ).any()  )




				def   __a		(      self  )       ->   Union[str, Any]:
							lowerCAmelCase_      			=			20
							lowerCAmelCase_      			=			4
							lowerCAmelCase_      			=			0
							lowerCAmelCase_      			=			5

							lowerCAmelCase_      			=			FlaxForcedEOSTokenLogitsProcessor(max_length=_UpperCamelCase       ,       eos_token_id=_UpperCamelCase  )

							# check that all scores are -inf except the eos_token_id when max_length is reached
							lowerCAmelCase_      			=			ids_tensor((batch_size, 4)       ,       vocab_size=20  )
							lowerCAmelCase_      			=			4
							lowerCAmelCase_      			=			self._get_uniform_logits(_UpperCamelCase       ,       _UpperCamelCase  )
							lowerCAmelCase_      			=			logits_processor(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
							self.assertTrue(jnp.isneginf(scores[:, eos_token_id + 1 :]  ).all()  )
							self.assertListEqual(scores[:, eos_token_id].tolist()       ,       4 * [0]  )  # score for eos_token_id should be zero

							# check that eos_token_id is not forced if max_length is not reached
							lowerCAmelCase_      			=			3
							lowerCAmelCase_      			=			self._get_uniform_logits(_UpperCamelCase       ,       _UpperCamelCase  )
							lowerCAmelCase_      			=			logits_processor(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
							self.assertFalse(jnp.isinf(_UpperCamelCase  ).any()  )




				def   __a		(      self  )       ->   Dict:
							lowerCAmelCase_      			=			4
							lowerCAmelCase_      			=			10
							lowerCAmelCase_      			=			15
							lowerCAmelCase_      			=			2
							lowerCAmelCase_      			=			1
							lowerCAmelCase_      			=			15

							# dummy input_ids and scores
							lowerCAmelCase_      			=			ids_tensor((batch_size, sequence_length)       ,       _UpperCamelCase  )
							lowerCAmelCase_      			=			input_ids.copy()

							lowerCAmelCase_      			=			self._get_uniform_logits(_UpperCamelCase       ,       _UpperCamelCase  )
							lowerCAmelCase_      			=			scores.copy()

							# instantiate all dist processors
							lowerCAmelCase_      			=			FlaxTemperatureLogitsWarper(temperature=0.5  )
							lowerCAmelCase_      			=			FlaxTopKLogitsWarper(3  )
							lowerCAmelCase_      			=			FlaxTopPLogitsWarper(0.8  )

							# instantiate all logits processors
							lowerCAmelCase_      			=			FlaxMinLengthLogitsProcessor(min_length=10       ,       eos_token_id=_UpperCamelCase  )
							lowerCAmelCase_      			=			FlaxForcedBOSTokenLogitsProcessor(bos_token_id=_UpperCamelCase  )
							lowerCAmelCase_      			=			FlaxForcedEOSTokenLogitsProcessor(max_length=_UpperCamelCase       ,       eos_token_id=_UpperCamelCase  )

							lowerCAmelCase_      			=			10

							# no processor list
							lowerCAmelCase_      			=			temp_dist_warp(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
							lowerCAmelCase_      			=			top_k_warp(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
							lowerCAmelCase_      			=			top_p_warp(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
							lowerCAmelCase_      			=			min_dist_proc(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
							lowerCAmelCase_      			=			bos_dist_proc(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
							lowerCAmelCase_      			=			eos_dist_proc(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )

							# with processor list
							lowerCAmelCase_      			=			FlaxLogitsProcessorList(
							    [temp_dist_warp, top_k_warp, top_p_warp, min_dist_proc, bos_dist_proc, eos_dist_proc]  )
							lowerCAmelCase_      			=			processor(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )

							# scores should be equal
							self.assertTrue(jnp.allclose(_UpperCamelCase       ,       _UpperCamelCase       ,       atol=1e-3  )  )

							# input_ids should never be changed
							self.assertListEqual(input_ids.tolist()       ,       input_ids_comp.tolist()  )




				def   __a		(      self  )       ->   int:
							lowerCAmelCase_      			=			4
							lowerCAmelCase_      			=			10
							lowerCAmelCase_      			=			15
							lowerCAmelCase_      			=			2
							lowerCAmelCase_      			=			1
							lowerCAmelCase_      			=			15

							# dummy input_ids and scores
							lowerCAmelCase_      			=			ids_tensor((batch_size, sequence_length)       ,       _UpperCamelCase  )
							lowerCAmelCase_      			=			input_ids.copy()

							lowerCAmelCase_      			=			self._get_uniform_logits(_UpperCamelCase       ,       _UpperCamelCase  )
							lowerCAmelCase_      			=			scores.copy()

							# instantiate all dist processors
							lowerCAmelCase_      			=			FlaxTemperatureLogitsWarper(temperature=0.5  )
							lowerCAmelCase_      			=			FlaxTopKLogitsWarper(3  )
							lowerCAmelCase_      			=			FlaxTopPLogitsWarper(0.8  )

							# instantiate all logits processors
							lowerCAmelCase_      			=			FlaxMinLengthLogitsProcessor(min_length=10       ,       eos_token_id=_UpperCamelCase  )
							lowerCAmelCase_      			=			FlaxForcedBOSTokenLogitsProcessor(bos_token_id=_UpperCamelCase  )
							lowerCAmelCase_      			=			FlaxForcedEOSTokenLogitsProcessor(max_length=_UpperCamelCase       ,       eos_token_id=_UpperCamelCase  )

							lowerCAmelCase_      			=			10

							# no processor list
							def run_no_processor_list(_UpperCamelCase       ,       _UpperCamelCase       ,       _UpperCamelCase  ):
										lowerCAmelCase_      			=			temp_dist_warp(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
										lowerCAmelCase_      			=			top_k_warp(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
										lowerCAmelCase_      			=			top_p_warp(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
										lowerCAmelCase_      			=			min_dist_proc(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
										lowerCAmelCase_      			=			bos_dist_proc(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
										lowerCAmelCase_      			=			eos_dist_proc(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
										return scores

							# with processor list
							def run_processor_list(_UpperCamelCase       ,       _UpperCamelCase       ,       _UpperCamelCase  ):
										lowerCAmelCase_      			=			FlaxLogitsProcessorList(
										    [temp_dist_warp, top_k_warp, top_p_warp, min_dist_proc, bos_dist_proc, eos_dist_proc]  )
										lowerCAmelCase_      			=			processor(_UpperCamelCase       ,       _UpperCamelCase       ,       cur_len=_UpperCamelCase  )
										return scores

							lowerCAmelCase_      			=			jax.jit(_UpperCamelCase  )
							lowerCAmelCase_      			=			jax.jit(_UpperCamelCase  )

							lowerCAmelCase_      			=			jitted_run_no_processor_list(_UpperCamelCase       ,       _UpperCamelCase       ,       _UpperCamelCase  )
							lowerCAmelCase_      			=			jitted_run_processor_list(_UpperCamelCase       ,       _UpperCamelCase       ,       _UpperCamelCase  )

							# scores should be equal
							self.assertTrue(jnp.allclose(_UpperCamelCase       ,       _UpperCamelCase       ,       atol=1e-3  )  )

							# input_ids should never be changed
							self.assertListEqual(input_ids.tolist()       ,       input_ids_comp.tolist()  )





import functools






def      lowerCamelCase__       (       __lowerCAmelCase						:						str					,							__lowerCAmelCase						:						str       ):




			"""simple docstring"""


			lowerCAmelCase_      			=			len(__lowerCAmelCase       )
			lowerCAmelCase_      			=			len(__lowerCAmelCase       )

			@functools.cache
			def min_distance(__lowerCAmelCase						:						int					,							__lowerCAmelCase						:						int       ) -> int:
						# if first word index is overflow - delete all from the second word
						if indexa >= len_worda:
									return len_worda - indexa
						# if second word index is overflow - delete all from the first word
						if indexa >= len_worda:
									return len_worda - indexa
						lowerCAmelCase_      			=			int(worda[indexa] != worda[indexa]       )  # current letters not identical
						return min(
						    1 + min_distance(indexa + 1					,							__lowerCAmelCase       )					,							1 + min_distance(__lowerCAmelCase					,							indexa + 1       )					,							diff + min_distance(indexa + 1					,							indexa + 1       )					,							)

			return min_distance(0					,							0       )


if __name__ == "__main__":
			import doctest

			doctest.testmod()



