





import unittest

import numpy as np
import timeout_decorator  # noqa

from transformers import OPTConfig, is_flax_available
from transformers.testing_utils import require_flax, require_sentencepiece, slow

from ...generation.test_flax_utils import FlaxGenerationTesterMixin
from ...test_modeling_flax_common import FlaxModelTesterMixin, ids_tensor


if is_flax_available():
      import os

      # The slow tests are often failing with OOM error on GPU
      # This makes JAX allocate exactly what is needed on demand, and deallocate memory that is no longer needed
      # but will be slower as stated here https://jax.readthedocs.io/en/latest/gpu_memory_allocation.html
      SCREAMING_SNAKE_CASE_		  =			"""platform"""

      import jax
      import jax.numpy as jnp

      from transformers import FlaxOPTForCausalLM, FlaxOPTModel, GPTaTokenizer



def   __lowercase  ( _SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE=None					,		_SCREAMING_SNAKE_CASE=None      )					->  str:


      '''simple docstring'''


      if attention_mask is None:
            SCREAMING_SNAKE_CASE						=		np.where(input_ids != config.pad_token_id					,		1					,		0      )
      return {
          "input_ids": input_ids,
          "attention_mask": attention_mask,
      }

@require_flax
class 						UpperCamelCase__					:



     '''simple docstring'''

     def __init__(				self		:       List[str]		,lowerCamelCase__		:       Any		,lowerCamelCase__		:       Tuple=13		,lowerCamelCase__		:       Dict=7		,lowerCamelCase__		:       Any=True		,lowerCamelCase__		:       Tuple=False		,lowerCamelCase__		:       Dict=99		,lowerCamelCase__		:       Any=16		,lowerCamelCase__		:       Tuple=2		,lowerCamelCase__		:       Optional[Any]=4		,lowerCamelCase__		:       List[Any]=4		,lowerCamelCase__		:       Union[str, Any]="gelu"		,lowerCamelCase__		:       Dict=0.1		,lowerCamelCase__		:       Any=0.1		,lowerCamelCase__		:       Tuple=20		,lowerCamelCase__		:       Dict=2		,lowerCamelCase__		:       Tuple=1		,lowerCamelCase__		:       Any=0		,lowerCamelCase__		:       Optional[Any]=16		,lowerCamelCase__		:       Tuple=16		,lowerCamelCase__		:       Dict=0.02		,)	->						Dict:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE						=		parent
           SCREAMING_SNAKE_CASE						=		batch_size
           SCREAMING_SNAKE_CASE						=		seq_length
           SCREAMING_SNAKE_CASE						=		is_training
           SCREAMING_SNAKE_CASE						=		use_labels
           SCREAMING_SNAKE_CASE						=		vocab_size
           SCREAMING_SNAKE_CASE						=		hidden_size
           SCREAMING_SNAKE_CASE						=		num_hidden_layers
           SCREAMING_SNAKE_CASE						=		num_attention_heads
           SCREAMING_SNAKE_CASE						=		intermediate_size
           SCREAMING_SNAKE_CASE						=		hidden_act
           SCREAMING_SNAKE_CASE						=		hidden_dropout_prob
           SCREAMING_SNAKE_CASE						=		attention_probs_dropout_prob
           SCREAMING_SNAKE_CASE						=		max_position_embeddings
           SCREAMING_SNAKE_CASE						=		eos_token_id
           SCREAMING_SNAKE_CASE						=		pad_token_id
           SCREAMING_SNAKE_CASE						=		bos_token_id
           SCREAMING_SNAKE_CASE						=		embed_dim
           SCREAMING_SNAKE_CASE						=		word_embed_proj_dim
           SCREAMING_SNAKE_CASE						=		initializer_range
           SCREAMING_SNAKE_CASE						=		False






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




           '''simple docstring'''


           SCREAMING_SNAKE_CASE						=		np.clip(ids_tensor([self.batch_size, self.seq_length - 1]		,self.vocab_size			)		,3		,self.vocab_size			)
           SCREAMING_SNAKE_CASE						=		np.concatenate((input_ids, 2 * np.ones((self.batch_size, 1)		,dtype=np.intaa			))		,-1			)

           SCREAMING_SNAKE_CASE						=		OPTConfig(
               vocab_size=self.vocab_size		,hidden_size=self.hidden_size		,num_hidden_layers=self.num_hidden_layers		,num_attention_heads=self.num_attention_heads		,ffn_dim=self.intermediate_size		,dropout=self.hidden_dropout_prob		,attention_dropout=self.attention_probs_dropout_prob		,max_position_embeddings=self.max_position_embeddings		,eos_token_id=self.eos_token_id		,bos_token_id=self.bos_token_id		,pad_token_id=self.pad_token_id		,embed_dim=self.embed_dim		,is_encoder_decoder=lowerCamelCase__		,word_embed_proj_dim=self.word_embed_proj_dim		,initializer_range=self.initializer_range		,use_cache=lowerCamelCase__		,)
           SCREAMING_SNAKE_CASE						=		prepare_opt_inputs_dict(lowerCamelCase__		,lowerCamelCase__			)
           return config, inputs_dict






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




           '''simple docstring'''


           SCREAMING_SNAKE_CASE,   SCREAMING_SNAKE_CASE						=		self.prepare_config_and_inputs()
           return config, inputs_dict






     def 							SCREAMING_SNAKE_CASE__    (				self		:       Dict		,lowerCamelCase__		:       str		,lowerCamelCase__		:       Any		,lowerCamelCase__		:       List[Any]			)	->						Optional[Any]:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE						=		20
           SCREAMING_SNAKE_CASE						=		model_class_name(lowerCamelCase__			)

           SCREAMING_SNAKE_CASE						=		inputs_dict["""input_ids"""]
           SCREAMING_SNAKE_CASE						=		inputs_dict["""attention_mask"""]

           SCREAMING_SNAKE_CASE						=		model.init_cache(input_ids.shape[0]		,lowerCamelCase__			)
           SCREAMING_SNAKE_CASE						=		jnp.ones((input_ids.shape[0], max_length)		,dtype="""i4"""			)

           SCREAMING_SNAKE_CASE						=		jnp.broadcast_to(
               jnp.arange(input_ids.shape[-1] - 1			)[None, :]		,(input_ids.shape[0], input_ids.shape[-1] - 1)		,)
           SCREAMING_SNAKE_CASE						=		model(
               input_ids[:, :-1]		,attention_mask=lowerCamelCase__		,past_key_values=lowerCamelCase__		,position_ids=lowerCamelCase__		,)

           SCREAMING_SNAKE_CASE						=		jnp.array(input_ids.shape[0] * [[input_ids.shape[-1] - 1]]		,dtype="""i4"""			)
           SCREAMING_SNAKE_CASE						=		model(
               input_ids[:, -1:]		,attention_mask=lowerCamelCase__		,past_key_values=outputs_cache.past_key_values		,position_ids=lowerCamelCase__		,)

           SCREAMING_SNAKE_CASE						=		model(lowerCamelCase__			)

           SCREAMING_SNAKE_CASE						=		np.max(np.abs((outputs_cache_next[0][:, -1, :5] - outputs[0][:, -1, :5])			)			)
           self.parent.assertTrue(diff < 1e-3		,msg=F"""Max diff is {diff}"""			)






     def 							SCREAMING_SNAKE_CASE__    (				self		:       List[Any]		,lowerCamelCase__		:       Tuple		,lowerCamelCase__		:       Dict		,lowerCamelCase__		:       Tuple			)	->						Dict:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE						=		20
           SCREAMING_SNAKE_CASE						=		model_class_name(lowerCamelCase__			)

           SCREAMING_SNAKE_CASE,   SCREAMING_SNAKE_CASE						=		(
               inputs_dict["""input_ids"""],
               inputs_dict["""attention_mask"""],
           )

           SCREAMING_SNAKE_CASE						=		jnp.concatenate(
               [
                   attention_mask,
                   jnp.zeros((attention_mask.shape[0], max_length - attention_mask.shape[1])			),
               ]		,axis=-1		,)

           SCREAMING_SNAKE_CASE						=		model.init_cache(input_ids.shape[0]		,lowerCamelCase__			)
           SCREAMING_SNAKE_CASE						=		jnp.broadcast_to(
               jnp.arange(input_ids.shape[-1] - 1			)[None, :]		,(input_ids.shape[0], input_ids.shape[-1] - 1)		,)

           SCREAMING_SNAKE_CASE						=		model(
               input_ids[:, :-1]		,attention_mask=lowerCamelCase__		,past_key_values=lowerCamelCase__		,position_ids=lowerCamelCase__		,)
           SCREAMING_SNAKE_CASE						=		jnp.array(input_ids.shape[0] * [[input_ids.shape[-1] - 1]]		,dtype="""i4"""			)
           SCREAMING_SNAKE_CASE						=		model(
               input_ids[:, -1:]		,past_key_values=outputs_cache.past_key_values		,attention_mask=lowerCamelCase__		,position_ids=lowerCamelCase__		,)

           SCREAMING_SNAKE_CASE						=		model(lowerCamelCase__		,attention_mask=lowerCamelCase__			)

           SCREAMING_SNAKE_CASE						=		np.max(np.abs((outputs_cache_next[0][:, -1, :5] - outputs[0][:, -1, :5])			)			)
           self.parent.assertTrue(diff < 1e-3		,msg=F"""Max diff is {diff}"""			)

@require_flax
class 						UpperCamelCase__					( lowerCAmelCase_				, unittest.TestCase				, lowerCAmelCase_  ):



     '''simple docstring'''

     __snake_case       :      List[str]						      =     (FlaxOPTModel, FlaxOPTForCausalLM) if is_flax_available() else ()
     __snake_case       :      Union[str, Any]						      =     () if is_flax_available() else ()






     def 							SCREAMING_SNAKE_CASE__    (				self		:       Optional[Any]			)	->						Optional[int]:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE						=		FlaxOPTModelTester(self			)






     def 							SCREAMING_SNAKE_CASE__    (				self		:       Optional[int]			)	->						Optional[int]:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE,   SCREAMING_SNAKE_CASE						=		self.model_tester.prepare_config_and_inputs()
           for model_class in self.all_model_classes:
                 self.model_tester.check_use_cache_forward(lowerCamelCase__		,lowerCamelCase__		,lowerCamelCase__			)






     def 							SCREAMING_SNAKE_CASE__    (				self		:       Optional[Any]			)	->						int:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE,   SCREAMING_SNAKE_CASE						=		self.model_tester.prepare_config_and_inputs()
           for model_class in self.all_model_classes:
                 self.model_tester.check_use_cache_forward_with_attn_mask(lowerCamelCase__		,lowerCamelCase__		,lowerCamelCase__			)






     @slow
     def 							SCREAMING_SNAKE_CASE__    (				self		:       Optional[int]			)	->						Union[str, Any]:




           '''simple docstring'''


           for model_class_name in self.all_model_classes:
                 SCREAMING_SNAKE_CASE						=		model_class_name.from_pretrained("""facebook/opt-125m"""			)
                 SCREAMING_SNAKE_CASE						=		np.ones((1, 1)			) * model.config.eos_token_id
                 SCREAMING_SNAKE_CASE						=		model(lowerCamelCase__			)
                 self.assertIsNotNone(lowerCamelCase__			)

@require_sentencepiece
@require_flax
class 						UpperCamelCase__					( unittest.TestCase  ):



     '''simple docstring'''

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




           '''simple docstring'''


           SCREAMING_SNAKE_CASE						=		FlaxOPTModel.from_pretrained("""facebook/opt-350m"""			)
           SCREAMING_SNAKE_CASE						=		jnp.array([[0, 31414, 232, 328, 740, 1140, 12695, 69, 46078, 1588, 2]]			)
           SCREAMING_SNAKE_CASE						=		model(input_ids=lowerCamelCase__			).last_hidden_state
           SCREAMING_SNAKE_CASE						=		(1, 11, 512)
           self.assertEqual(output.shape		,lowerCamelCase__			)
           SCREAMING_SNAKE_CASE						=		jnp.array(
               [[-0.2867, -1.9256, -0.3062], [-1.2711, -0.1337, -0.1897], [0.4109, 0.1187, -1.3142]]			)
           self.assertTrue(jnp.allclose(output[:, :3, :3]		,lowerCamelCase__		,atol=4e-2			)			)

@require_flax
@slow
class 						UpperCamelCase__					( unittest.TestCase  ):



     '''simple docstring'''

     def 							SCREAMING_SNAKE_CASE__    (				self		:       str			)	->						str:




           '''simple docstring'''


           super().setUp()
           SCREAMING_SNAKE_CASE						=		"""facebook/opt-350m"""






     def 							SCREAMING_SNAKE_CASE__    (				self		:       Any			)	->						Any:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE						=		FlaxOPTForCausalLM.from_pretrained(self.path_model			)
           SCREAMING_SNAKE_CASE						=		GPTaTokenizer.from_pretrained(self.path_model			)

           SCREAMING_SNAKE_CASE						=		[
               """Today is a beautiful day and I want to""",
               """In the city of""",
               """Paris is the capital of France and""",
               """Computers and mobile phones have taken""",
           ]
           # verify that prompt without BOS token is identical to Metaseq -> add_special_tokens=False
           SCREAMING_SNAKE_CASE						=		tokenizer(lowerCamelCase__		,return_tensors="""jax"""		,padding=lowerCamelCase__		,add_special_tokens=lowerCamelCase__			)
           SCREAMING_SNAKE_CASE						=		model(inputs.input_ids		,attention_mask=inputs.attention_mask			)[0].mean(axis=-1			)
           SCREAMING_SNAKE_CASE						=		jnp.array(
               [
                   [1.3851, -13.8923, -10.5229, -10.7533, -0.2309, -10.2384, -0.5365, -9.0947, -5.1670],
                   [-4.7073, -10.6276, -3.9415, -21.5242, -0.2822, -0.2822, -0.2822, -0.2822, -0.2822],
                   [0.6247, -3.4229, -8.9179, -1.4297, -14.1650, 1.4146, -9.0218, -0.2703, -0.2703],
                   [6.4783, -1.9913, -10.7926, -2.3336, 1.5092, -0.9974, -6.8213, 1.3477, 1.3477],
               ]			)
           self.assertTrue(jnp.allclose(lowerCamelCase__		,lowerCamelCase__		,atol=4e-2			)			)

           SCREAMING_SNAKE_CASE						=		jax.jit(lowerCamelCase__			)
           SCREAMING_SNAKE_CASE						=		model(inputs.input_ids		,attention_mask=inputs.attention_mask			)[0].mean(axis=-1			)
           self.assertTrue(jnp.allclose(lowerCamelCase__		,lowerCamelCase__		,atol=4e-2			)			)

@require_flax
@slow
class 						UpperCamelCase__					( unittest.TestCase  ):



     '''simple docstring'''

     @property
     def 							SCREAMING_SNAKE_CASE__    (				self		:       Tuple			)	->						int:




           '''simple docstring'''


           return [
               "Today is a beautiful day and I want",
               "In the city of",
               "Paris is the capital of France and",
               "Computers and mobile phones have taken",
           ]






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




           '''simple docstring'''


           SCREAMING_SNAKE_CASE						=		"""facebook/opt-125m"""

           SCREAMING_SNAKE_CASE						=		[
               """Today is a beautiful day and I want to""",
               """In the city of New York, the city""",
               """Paris is the capital of France and the capital""",
               """Computers and mobile phones have taken over the""",
           ]

           SCREAMING_SNAKE_CASE						=		[]

           SCREAMING_SNAKE_CASE						=		FlaxOPTForCausalLM.from_pretrained(lowerCamelCase__			)
           SCREAMING_SNAKE_CASE						=		GPTaTokenizer.from_pretrained(lowerCamelCase__			)

           for prompt in self.prompts:
                 SCREAMING_SNAKE_CASE						=		tokenizer(lowerCamelCase__		,return_tensors="""jax"""			).input_ids

                 SCREAMING_SNAKE_CASE						=		model.generate(lowerCamelCase__		,max_length=10			)
                 SCREAMING_SNAKE_CASE						=		generated_ids[0]

                 SCREAMING_SNAKE_CASE						=		tokenizer.batch_decode(lowerCamelCase__		,skip_special_tokens=lowerCamelCase__			)
                 predicted_outputs += generated_string

           self.assertListEqual(lowerCamelCase__		,lowerCamelCase__			)






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




           '''simple docstring'''


           SCREAMING_SNAKE_CASE						=		"""facebook/opt-350m"""

           SCREAMING_SNAKE_CASE						=		[
               """Today is a beautiful day and I want to""",
               """In the city of San Francisco, the city""",
               """Paris is the capital of France and the capital""",
               """Computers and mobile phones have taken over the""",
           ]

           SCREAMING_SNAKE_CASE						=		[]
           SCREAMING_SNAKE_CASE						=		FlaxOPTForCausalLM.from_pretrained(lowerCamelCase__			)
           SCREAMING_SNAKE_CASE						=		GPTaTokenizer.from_pretrained(lowerCamelCase__			)

           for prompt in self.prompts:
                 SCREAMING_SNAKE_CASE						=		tokenizer(lowerCamelCase__		,return_tensors="""jax"""			).input_ids

                 SCREAMING_SNAKE_CASE						=		model.generate(lowerCamelCase__		,max_length=10			)
                 SCREAMING_SNAKE_CASE						=		generated_ids[0]

                 SCREAMING_SNAKE_CASE						=		tokenizer.batch_decode(lowerCamelCase__		,skip_special_tokens=lowerCamelCase__			)
                 predicted_outputs += generated_string

           self.assertListEqual(lowerCamelCase__		,lowerCamelCase__			)






     def 							SCREAMING_SNAKE_CASE__    (				self		:       Dict			)	->						Any:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE						=		"""facebook/opt-125m"""
           SCREAMING_SNAKE_CASE						=		[
               """Today is a beautiful day and I want to thank""",
               """In the city of Rome Canaver Canaver Canaver Canaver""",
           ]
           SCREAMING_SNAKE_CASE						=		FlaxOPTForCausalLM.from_pretrained(lowerCamelCase__			)
           SCREAMING_SNAKE_CASE						=		GPTaTokenizer.from_pretrained(lowerCamelCase__			)
           SCREAMING_SNAKE_CASE						=		tokenizer(
               [
                   """Today is a beautiful day and I want to""",
                   """In the city of""",
               ]		,return_tensors="""jax"""		,padding=lowerCamelCase__		,)

           SCREAMING_SNAKE_CASE						=		jax.jit(model.generate			)

           SCREAMING_SNAKE_CASE						=		jit_generate(inputs["""input_ids"""]		,attention_mask=inputs["""attention_mask"""]			).sequences

           SCREAMING_SNAKE_CASE						=		tokenizer.batch_decode(lowerCamelCase__		,skip_special_tokens=lowerCamelCase__			)

           self.assertIsNotNone(lowerCamelCase__		,lowerCamelCase__			)






     def 							SCREAMING_SNAKE_CASE__    (				self		:       str			)	->						Optional[Any]:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE						=		"""facebook/opt-350m"""

           SCREAMING_SNAKE_CASE						=		GPTaTokenizer.from_pretrained(lowerCamelCase__			)
           SCREAMING_SNAKE_CASE						=		FlaxOPTForCausalLM.from_pretrained(lowerCamelCase__			)

           SCREAMING_SNAKE_CASE						=		"""left"""

           # use different length sentences to test batching
           SCREAMING_SNAKE_CASE						=		[
               """Hello, my dog is a little""",
               """Today, I""",
           ]

           SCREAMING_SNAKE_CASE						=		tokenizer(lowerCamelCase__		,return_tensors="""jax"""		,padding=lowerCamelCase__			)
           SCREAMING_SNAKE_CASE						=		inputs["""input_ids"""]

           SCREAMING_SNAKE_CASE						=		model.generate(input_ids=lowerCamelCase__		,attention_mask=inputs["""attention_mask"""]		,trace=lowerCamelCase__			)

           SCREAMING_SNAKE_CASE						=		tokenizer(sentences[0]		,return_tensors="""jax"""			).input_ids
           SCREAMING_SNAKE_CASE						=		model.generate(input_ids=lowerCamelCase__			)

           SCREAMING_SNAKE_CASE						=		inputs_non_padded.shape[-1] - inputs["""attention_mask"""][-1].sum()
           SCREAMING_SNAKE_CASE						=		tokenizer(sentences[1]		,return_tensors="""jax"""			).input_ids
           SCREAMING_SNAKE_CASE						=		model.generate(input_ids=lowerCamelCase__		,max_length=model.config.max_length - num_paddings			)

           SCREAMING_SNAKE_CASE						=		tokenizer.batch_decode(outputs[0]		,skip_special_tokens=lowerCamelCase__			)
           SCREAMING_SNAKE_CASE						=		tokenizer.decode(output_non_padded[0][0]		,skip_special_tokens=lowerCamelCase__			)
           SCREAMING_SNAKE_CASE						=		tokenizer.decode(output_padded[0][0]		,skip_special_tokens=lowerCamelCase__			)

           SCREAMING_SNAKE_CASE						=		[
               """Hello, my dog is a little bit of a dork.\nI'm a little bit""",
               """Today, I was in the middle of a conversation with a friend about the""",
           ]
           self.assertListEqual(lowerCamelCase__		,lowerCamelCase__			)
           self.assertListEqual(lowerCamelCase__		,[non_padded_sentence, padded_sentence]			)









from __future__ import annotations

from collections.abc import Iterable

class 						UpperCamelCase__					:



     '''simple docstring'''

     def __init__(				self		:       Optional[Any]		,lowerCamelCase__		:       Optional[int]		,lowerCamelCase__		:       List[Any]			)	->						int:




           '''simple docstring'''


           SCREAMING_SNAKE_CASE,   SCREAMING_SNAKE_CASE						=		float(lowerCamelCase__			), float(lowerCamelCase__			)






     def __eq__(				self		:       int		,lowerCamelCase__		:       Union[str, Any]			)	->						List[str]:




           '''simple docstring'''


           return self.x == other.x and self.y == other.y






     def __ne__(				self		:       Optional[int]		,lowerCamelCase__		:       int			)	->						Dict:




           '''simple docstring'''


           return not self == other






     def __gt__(				self		:       Optional[Any]		,lowerCamelCase__		:       Optional[Any]			)	->						List[Any]:




           '''simple docstring'''


           if self.x > other.x:
                 return True
           elif self.x == other.x:
                 return self.y > other.y
           return False






     def __lt__(				self		:       Union[str, Any]		,lowerCamelCase__		:       Optional[Any]			)	->						Optional[Any]:




           '''simple docstring'''


           return not self > other






     def __ge__(				self		:       Optional[Any]		,lowerCamelCase__		:       Tuple			)	->						Optional[Any]:




           '''simple docstring'''


           if self.x > other.x:
                 return True
           elif self.x == other.x:
                 return self.y >= other.y
           return False






     def __le__(				self		:       Tuple		,lowerCamelCase__		:       int			)	->						Dict:




           '''simple docstring'''


           if self.x < other.x:
                 return True
           elif self.x == other.x:
                 return self.y <= other.y
           return False






     def __repr__(				self		:       Dict			)	->						Any:




           '''simple docstring'''


           return F"""({self.x}, {self.y})"""






     def __hash__(				self		:       List[Any]			)	->						List[Any]:




           '''simple docstring'''


           return hash(self.x			)



def   __lowercase  ( _SCREAMING_SNAKE_CASE					,		)					->  list[Point]:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE						=		[]
      if list_of_tuples:
            for p in list_of_tuples:
                  if isinstance(_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE      ):
                        points.append(_SCREAMING_SNAKE_CASE      )
                  else:
                        try:
                              points.append(Point(p[0]					,		p[1]      )      )
                        except (IndexError, TypeError):
                              print(
                                  F"""Ignoring deformed point {p}. All points"""
                                  """ must have at least 2 coordinates."""      )
      return points



def   __lowercase  ( _SCREAMING_SNAKE_CASE      )					->  list[Point]:


      '''simple docstring'''


      if not hasattr(_SCREAMING_SNAKE_CASE					,		"""__iter__"""      ):
            SCREAMING_SNAKE_CASE						=		F"""Expecting an iterable object but got an non-iterable type {points}"""
            raise ValueError(_SCREAMING_SNAKE_CASE      )

      if not points:
            SCREAMING_SNAKE_CASE						=		F"""Expecting a list of points but got {points}"""
            raise ValueError(_SCREAMING_SNAKE_CASE      )

      return _construct_points(_SCREAMING_SNAKE_CASE      )



def   __lowercase  ( _SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE      )					->  float:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE						=		(a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x)
      return det



def   __lowercase  ( _SCREAMING_SNAKE_CASE      )					->  list[Point]:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE						=		sorted(_validate_input(_SCREAMING_SNAKE_CASE      )      )
      SCREAMING_SNAKE_CASE						=		len(_SCREAMING_SNAKE_CASE      )
      SCREAMING_SNAKE_CASE						=		set()

      for i in range(n - 1      ):
            for j in range(i + 1					,		_SCREAMING_SNAKE_CASE      ):
                  SCREAMING_SNAKE_CASE						=		SCREAMING_SNAKE_CASE						=		False
                  SCREAMING_SNAKE_CASE						=		True
                  for k in range(_SCREAMING_SNAKE_CASE      ):
                        if k != i and k != j:
                              SCREAMING_SNAKE_CASE						=		_det(points[i]					,		points[j]					,		points[k]      )

                              if det_k > 0:
                                    SCREAMING_SNAKE_CASE						=		True
                              elif det_k < 0:
                                    SCREAMING_SNAKE_CASE						=		True
                              else:
                                    # point[i], point[j], point[k] all lie on a straight line
                                    # if point[k] is to the left of point[i] or it's to the
                                    # right of point[j], then point[i], point[j] cannot be
                                    # part of the convex hull of A
                                    if points[k] < points[i] or points[k] > points[j]:
                                          SCREAMING_SNAKE_CASE						=		False
                                          break

                        if points_left_of_ij and points_right_of_ij:
                              SCREAMING_SNAKE_CASE						=		False
                              break

                  if ij_part_of_convex_hull:
                        convex_set.update([points[i], points[j]]      )

      return sorted(_SCREAMING_SNAKE_CASE      )



def   __lowercase  ( _SCREAMING_SNAKE_CASE      )					->  list[Point]:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE						=		sorted(_validate_input(_SCREAMING_SNAKE_CASE      )      )
      SCREAMING_SNAKE_CASE						=		len(_SCREAMING_SNAKE_CASE      )

      # divide all the points into an upper hull and a lower hull
      # the left most point and the right most point are definitely
      # members of the convex hull by definition.
      # use these two anchors to divide all the points into two hulls,
      # an upper hull and a lower hull.

      # all points to the left (above) the line joining the extreme points belong to the
      # upper hull
      # all points to the right (below) the line joining the extreme points below to the
      # lower hull
      # ignore all points on the line joining the extreme points since they cannot be
      # part of the convex hull

      SCREAMING_SNAKE_CASE						=		points[0]
      SCREAMING_SNAKE_CASE						=		points[n - 1]

      SCREAMING_SNAKE_CASE						=		{left_most_point, right_most_point}
      SCREAMING_SNAKE_CASE						=		[]
      SCREAMING_SNAKE_CASE						=		[]

      for i in range(1					,		n - 1      ):
            SCREAMING_SNAKE_CASE						=		_det(_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		points[i]      )

            if det > 0:
                  upper_hull.append(points[i]      )
            elif det < 0:
                  lower_hull.append(points[i]      )

      _construct_hull(_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE      )
      _construct_hull(_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE      )

      return sorted(_SCREAMING_SNAKE_CASE      )



def   __lowercase  ( _SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE      )					->  None:


      '''simple docstring'''


      if points:
            SCREAMING_SNAKE_CASE						=		None
            SCREAMING_SNAKE_CASE						=		float("""-inf"""      )
            SCREAMING_SNAKE_CASE						=		[]

            for p in points:
                  SCREAMING_SNAKE_CASE						=		_det(_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE      )

                  if det > 0:
                        candidate_points.append(_SCREAMING_SNAKE_CASE      )

                        if det > extreme_point_distance:
                              SCREAMING_SNAKE_CASE						=		det
                              SCREAMING_SNAKE_CASE						=		p

            if extreme_point:
                  _construct_hull(_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE      )
                  convex_set.add(_SCREAMING_SNAKE_CASE      )
                  _construct_hull(_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE      )



def   __lowercase  ( _SCREAMING_SNAKE_CASE      )					->  list[Point]:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE						=		sorted(_validate_input(_SCREAMING_SNAKE_CASE      )      )
      SCREAMING_SNAKE_CASE						=		len(_SCREAMING_SNAKE_CASE      )

      SCREAMING_SNAKE_CASE						=		points[:2]
      for i in range(2					,		_SCREAMING_SNAKE_CASE      ):
            SCREAMING_SNAKE_CASE						=		_det(convex_hull[1]					,		convex_hull[0]					,		points[i]      )
            if det > 0:
                  convex_hull.insert(0					,		points[i]      )
                  break
            elif det < 0:
                  convex_hull.append(points[i]      )
                  break
            else:
                  SCREAMING_SNAKE_CASE						=		points[i]
      i += 1

      for j in range(_SCREAMING_SNAKE_CASE					,		_SCREAMING_SNAKE_CASE      ):
            if (
                _det(convex_hull[0]					,		convex_hull[-1]					,		points[j]      ) > 0
                and _det(convex_hull[-1]					,		convex_hull[0]					,		points[1]      ) < 0
            ):
                  # The point lies within the convex hull
                  continue

            convex_hull.insert(0					,		points[j]      )
            convex_hull.append(points[j]      )
            while _det(convex_hull[0]					,		convex_hull[1]					,		convex_hull[2]      ) >= 0:
                  del convex_hull[1]
            while _det(convex_hull[-1]					,		convex_hull[-2]					,		convex_hull[-3]      ) <= 0:
                  del convex_hull[-2]

    # `convex_hull` is contains the convex hull in circular order
      return sorted(convex_hull[1:] if len(_SCREAMING_SNAKE_CASE      ) > 3 else convex_hull      )



def   __lowercase  ( )					->  Any:


      '''simple docstring'''


      SCREAMING_SNAKE_CASE						=		[
          (0, 3),
          (2, 2),
          (1, 1),
          (2, 1),
          (3, 0),
          (0, 0),
          (3, 3),
          (2, -1),
          (2, -4),
          (1, -3),
      ]
      # the convex set of points is
      # [(0, 0), (0, 3), (1, -3), (2, -4), (3, 0), (3, 3)]
      SCREAMING_SNAKE_CASE						=		convex_hull_bf(_SCREAMING_SNAKE_CASE      )

      SCREAMING_SNAKE_CASE						=		convex_hull_recursive(_SCREAMING_SNAKE_CASE      )
      assert results_bf == results_recursive

      SCREAMING_SNAKE_CASE						=		convex_hull_melkman(_SCREAMING_SNAKE_CASE      )
      assert results_bf == results_melkman

      print(_SCREAMING_SNAKE_CASE      )


if __name__ == "__main__":
      main()


