




from __future__ import annotations

from collections.abc import Iterable






class  SCREAMING_SNAKE_CASE__   :


						def __init__(							self			:     Optional[Any]  ,  lowerCAmelCase			:     Optional[Any]  ,  lowerCAmelCase			:     Optional[int]   ):
										lowerCAmelCase		=			float(SCREAMING_SNAKE_CASE__   ), float(SCREAMING_SNAKE_CASE__   )


						def __eq__(							self			:     Optional[Any]  ,  lowerCAmelCase			:     Optional[int]   ):
										return self.x == other.x and self.y == other.y


						def __ne__(							self			:     Optional[Any]  ,  lowerCAmelCase			:     Optional[int]   ):
										return not self == other


						def __gt__(							self			:     str  ,  lowerCAmelCase			:     int   ):
										if self.x > other.x:
														return True
										elif self.x == other.x:
														return self.y > other.y
										return False


						def __lt__(							self			:     List[Any]  ,  lowerCAmelCase			:     int   ):
										return not self > other


						def __ge__(							self			:     Any  ,  lowerCAmelCase			:     int   ):
										if self.x > other.x:
														return True
										elif self.x == other.x:
														return self.y >= other.y
										return False


						def __le__(							self			:     Optional[int]  ,  lowerCAmelCase			:     str   ):
										if self.x < other.x:
														return True
										elif self.x == other.x:
														return self.y <= other.y
										return False


						def __repr__(							self			:     Union[str, Any]   ):
										return f'''({self.x}, {self.y})'''




						def __hash__(							self			:     str   ):
										return hash(self.x   )





def 							lowercase   (snake_case__				:	Tuple ,    )       ->					Union[str, Any]:


				'''simple docstring'''






				lowerCAmelCase		=			[]
				if list_of_tuples:
								for p in list_of_tuples:
												if isinstance(snake_case__ ,    snake_case__	):
																points.append(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   (snake_case__				:	List[Any]	)       ->					Union[str, Any]:


				'''simple docstring'''






				if not hasattr(snake_case__ ,    """__iter__"""	):
								lowerCAmelCase		=			f'''Expecting an iterable object but got an non-iterable type {points}'''
								raise ValueError(snake_case__	)

				if not points:
								lowerCAmelCase		=			f'''Expecting a list of points but got {points}'''
								raise ValueError(snake_case__	)

				return _construct_points(snake_case__	)





def 							lowercase   (snake_case__				:	int ,    snake_case__				:	List[Any] ,    snake_case__				:	List[str]	)       ->					Dict:


				'''simple docstring'''






				lowerCAmelCase		=			(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   (snake_case__				:	Optional[Any]	)       ->					Tuple:


				'''simple docstring'''






				lowerCAmelCase		=			sorted(_validate_input(snake_case__	)	)
				lowerCAmelCase		=			len(snake_case__	)
				lowerCAmelCase		=			set()

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

																				if det_k > 0:
																								lowerCAmelCase		=			True
																				elif det_k < 0:
																								lowerCAmelCase		=			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]:
																												lowerCAmelCase		=			False
																												break

																if points_left_of_ij and points_right_of_ij:
																				lowerCAmelCase		=			False
																				break

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

				return sorted(snake_case__	)





def 							lowercase   (snake_case__				:	str	)       ->					List[Any]:


				'''simple docstring'''






				lowerCAmelCase		=			sorted(_validate_input(snake_case__	)	)
				lowerCAmelCase		=			len(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

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

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

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

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

				_construct_hull(snake_case__ ,    snake_case__ ,    snake_case__ ,    snake_case__	)
				_construct_hull(snake_case__ ,    snake_case__ ,    snake_case__ ,    snake_case__	)

				return sorted(snake_case__	)





def 							lowercase   (snake_case__				:	Optional[Any] ,    snake_case__				:	List[Any] ,    snake_case__				:	int ,    snake_case__				:	Optional[int]	)       ->					List[Any]:


				'''simple docstring'''






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

								for p in points:
												lowerCAmelCase		=			_det(snake_case__ ,    snake_case__ ,    snake_case__	)

												if det > 0:
																candidate_points.append(snake_case__	)

																if det > extreme_point_distance:
																				lowerCAmelCase		=			det
																				lowerCAmelCase		=			p

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





def 							lowercase   (snake_case__				:	int	)       ->					str:


				'''simple docstring'''






				lowerCAmelCase		=			sorted(_validate_input(snake_case__	)	)
				lowerCAmelCase		=			len(snake_case__	)

				lowerCAmelCase		=			points[:2]
				for i in range(2 ,    snake_case__	):
								lowerCAmelCase		=			_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:
												lowerCAmelCase		=			points[i]
				i += 1

				for j in range(snake_case__ ,    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(snake_case__	) > 3 else convex_hull	)





def 							lowercase   ()       ->					Dict:


				'''simple docstring'''






				lowerCAmelCase		=			[
				    (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)]
				lowerCAmelCase		=			convex_hull_bf(snake_case__	)

				lowerCAmelCase		=			convex_hull_recursive(snake_case__	)
				assert results_bf == results_recursive

				lowerCAmelCase		=			convex_hull_melkman(snake_case__	)
				assert results_bf == results_melkman

				print(snake_case__	)


if __name__ == "__main__":
		main()











"""simple docstring"""







from collections import OrderedDict
from typing import Any, Mapping, Optional

from ... import PreTrainedTokenizer
from ...configuration_utils import PretrainedConfig
from ...onnx import OnnxConfig, OnnxConfigWithPast, OnnxSeqaSeqConfigWithPast
from ...onnx.utils import compute_effective_axis_dimension
from ...utils import TensorType, is_torch_available, logging


a								=							logging.get_logger(__name__)

a								=							{
    'facebook/mbart-large-cc25': 'https://huggingface.co/facebook/mbart-large-cc25/resolve/main/config.json',
    # See all MBART models at https://huggingface.co/models?filter=mbart
}






class  SCREAMING_SNAKE_CASE__   (   _a   ):
						_a        =  'mbart'
						_a        =  ['past_key_values']
						_a        =  {'num_attention_heads': 'encoder_attention_heads', 'hidden_size': 'd_model'}


						def __init__(							self			:     Union[str, Any]  ,  lowerCAmelCase			:     Optional[Any]=5_0265  ,  lowerCAmelCase			:     str=1024  ,  lowerCAmelCase			:     str=12  ,  lowerCAmelCase			:     Any=4096  ,  lowerCAmelCase			:     str=16  ,  lowerCAmelCase			:     Optional[int]=12  ,  lowerCAmelCase			:     Optional[Any]=4096  ,  lowerCAmelCase			:     int=16  ,  lowerCAmelCase			:     Union[str, Any]=0.0  ,  lowerCAmelCase			:     List[str]=0.0  ,  lowerCAmelCase			:     int=True  ,  lowerCAmelCase			:     List[Any]=True  ,  lowerCAmelCase			:     Union[str, Any]="gelu"  ,  lowerCAmelCase			:     List[Any]=1024  ,  lowerCAmelCase			:     Optional[Any]=0.1  ,  lowerCAmelCase			:     List[str]=0.0  ,  lowerCAmelCase			:     str=0.0  ,  lowerCAmelCase			:     str=0.02  ,  lowerCAmelCase			:     int=0.0  ,  lowerCAmelCase			:     int=False  ,  lowerCAmelCase			:     Dict=1  ,  lowerCAmelCase			:     Tuple=0  ,  lowerCAmelCase			:     List[str]=2  ,  lowerCAmelCase			:     Union[str, Any]=2  ,  **lowerCAmelCase			:     Any  ,  ):
										lowerCAmelCase		=			vocab_size
										lowerCAmelCase		=			max_position_embeddings
										lowerCAmelCase		=			d_model
										lowerCAmelCase		=			encoder_ffn_dim
										lowerCAmelCase		=			encoder_layers
										lowerCAmelCase		=			encoder_attention_heads
										lowerCAmelCase		=			decoder_ffn_dim
										lowerCAmelCase		=			decoder_layers
										lowerCAmelCase		=			decoder_attention_heads
										lowerCAmelCase		=			dropout
										lowerCAmelCase		=			attention_dropout
										lowerCAmelCase		=			activation_dropout
										lowerCAmelCase		=			activation_function
										lowerCAmelCase		=			init_std
										lowerCAmelCase		=			encoder_layerdrop
										lowerCAmelCase		=			decoder_layerdrop
										lowerCAmelCase		=			classifier_dropout
										lowerCAmelCase		=			use_cache
										lowerCAmelCase		=			encoder_layers
										lowerCAmelCase		=			scale_embedding  # scale factor will be sqrt(d_model) if True
										super().__init__(
										    pad_token_id=lowerCAmelCase  ,  bos_token_id=lowerCAmelCase  ,  eos_token_id=lowerCAmelCase  ,  is_encoder_decoder=lowerCAmelCase  ,  forced_eos_token_id=lowerCAmelCase  ,  **lowerCAmelCase  ,  )






class  SCREAMING_SNAKE_CASE__   (   _a   ):


						@property
						def 					__lowercase	(							self			:     List[Any]   ):
										if self.task in ["default", "seq2seq-lm"]:
														lowerCAmelCase		=			OrderedDict(
														    [
														        ("""input_ids""", {0: """batch""", 1: """encoder_sequence"""}),
														        ("""attention_mask""", {0: """batch""", 1: """encoder_sequence"""}),
														    ]   )

														if self.use_past:
																		lowerCAmelCase		=			{0: """batch"""}
																		lowerCAmelCase		=			{0: """batch""", 1: """past_decoder_sequence + sequence"""}
														else:
																		lowerCAmelCase		=			{0: """batch""", 1: """decoder_sequence"""}
																		lowerCAmelCase		=			{0: """batch""", 1: """decoder_sequence"""}

														if self.use_past:
																		self.fill_with_past_key_values_(lowerCAmelCase  ,  direction="""inputs"""   )
										elif self.task == "causal-lm":
														# TODO: figure this case out.
														lowerCAmelCase		=			OrderedDict(
														    [
														        ("""input_ids""", {0: """batch""", 1: """encoder_sequence"""}),
														        ("""attention_mask""", {0: """batch""", 1: """encoder_sequence"""}),
														    ]   )
														if self.use_past:
																		lowerCAmelCase	,  lowerCAmelCase		=			self.num_layers
																		for i in range(lowerCAmelCase   ):
																						lowerCAmelCase		=			{0: """batch""", 2: """past_sequence + sequence"""}
																						lowerCAmelCase		=			{0: """batch""", 2: """past_sequence + sequence"""}
										else:
														lowerCAmelCase		=			OrderedDict(
														    [
														        ("""input_ids""", {0: """batch""", 1: """encoder_sequence"""}),
														        ("""attention_mask""", {0: """batch""", 1: """encoder_sequence"""}),
														        ("""decoder_input_ids""", {0: """batch""", 1: """decoder_sequence"""}),
														        ("""decoder_attention_mask""", {0: """batch""", 1: """decoder_sequence"""}),
														    ]   )

										return common_inputs


						@property
						def 					__lowercase	(							self			:     Optional[Any]   ):
										if self.task in ["default", "seq2seq-lm"]:
														lowerCAmelCase		=			super().outputs
										else:
														lowerCAmelCase		=			super(lowerCAmelCase  ,  self   ).outputs
														if self.use_past:
																		lowerCAmelCase	,  lowerCAmelCase		=			self.num_layers
																		for i in range(lowerCAmelCase   ):
																						lowerCAmelCase		=			{0: """batch""", 2: """past_sequence + sequence"""}
																						lowerCAmelCase		=			{0: """batch""", 2: """past_sequence + sequence"""}
										return common_outputs


						def 					__lowercase	(							self			:     Tuple  ,  lowerCAmelCase			:     PreTrainedTokenizer  ,  lowerCAmelCase			:     int = -1  ,  lowerCAmelCase			:     int = -1  ,  lowerCAmelCase			:     bool = False  ,  lowerCAmelCase			:     Optional[TensorType] = None  ,  ):
										lowerCAmelCase		=			self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
										    lowerCAmelCase  ,  lowerCAmelCase  ,  lowerCAmelCase  ,  lowerCAmelCase  ,  lowerCAmelCase   )

										# Generate decoder inputs
										lowerCAmelCase		=			seq_length if not self.use_past else 1
										lowerCAmelCase		=			self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
										    lowerCAmelCase  ,  lowerCAmelCase  ,  lowerCAmelCase  ,  lowerCAmelCase  ,  lowerCAmelCase   )
										lowerCAmelCase		=			{f'''decoder_{name}''': tensor for name, tensor in decoder_inputs.items()}
										lowerCAmelCase		=			dict(**lowerCAmelCase  ,  **lowerCAmelCase   )

										if self.use_past:
														if not is_torch_available():
																		raise ValueError("""Cannot generate dummy past_keys inputs without PyTorch installed."""   )
														else:
																		import torch
														lowerCAmelCase	,  lowerCAmelCase		=			common_inputs["""input_ids"""].shape
														lowerCAmelCase		=			common_inputs["""decoder_input_ids"""].shape[1]
														lowerCAmelCase	,  lowerCAmelCase		=			self.num_attention_heads
														lowerCAmelCase		=			(
														    batch,
														    num_encoder_attention_heads,
														    encoder_seq_length,
														    self._config.hidden_size // num_encoder_attention_heads,
														)
														lowerCAmelCase		=			decoder_seq_length + 3
														lowerCAmelCase		=			(
														    batch,
														    num_decoder_attention_heads,
														    decoder_past_length,
														    self._config.hidden_size // num_decoder_attention_heads,
														)

														lowerCAmelCase		=			torch.cat(
														    [common_inputs["""decoder_attention_mask"""], torch.ones(lowerCAmelCase  ,  lowerCAmelCase   )]  ,  dim=1   )

														lowerCAmelCase		=			[]
														# If the number of encoder and decoder layers are present in the model configuration, both are considered
														lowerCAmelCase	,  lowerCAmelCase		=			self.num_layers
														lowerCAmelCase		=			min(lowerCAmelCase  ,  lowerCAmelCase   )
														lowerCAmelCase		=			max(lowerCAmelCase  ,  lowerCAmelCase   ) - min_num_layers
														lowerCAmelCase		=			"""encoder""" if num_encoder_layers > num_decoder_layers else """decoder"""

														for _ in range(lowerCAmelCase   ):
																		common_inputs["past_key_values"].append(
																		    (
																		        torch.zeros(lowerCAmelCase   ),
																		        torch.zeros(lowerCAmelCase   ),
																		        torch.zeros(lowerCAmelCase   ),
																		        torch.zeros(lowerCAmelCase   ),
																		    )   )
														# TODO: test this.
														lowerCAmelCase		=			encoder_shape if remaining_side_name == """encoder""" else decoder_shape
														for _ in range(lowerCAmelCase  ,  lowerCAmelCase   ):
																		common_inputs["past_key_values"].append((torch.zeros(lowerCAmelCase   ), torch.zeros(lowerCAmelCase   ))   )
										return common_inputs


						def 					__lowercase	(							self			:     Dict  ,  lowerCAmelCase			:     PreTrainedTokenizer  ,  lowerCAmelCase			:     int = -1  ,  lowerCAmelCase			:     int = -1  ,  lowerCAmelCase			:     bool = False  ,  lowerCAmelCase			:     Optional[TensorType] = None  ,  ):
										lowerCAmelCase		=			self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
										    lowerCAmelCase  ,  lowerCAmelCase  ,  lowerCAmelCase  ,  lowerCAmelCase  ,  lowerCAmelCase   )

										if self.use_past:
														if not is_torch_available():
																		raise ValueError("""Cannot generate dummy past_keys inputs without PyTorch installed."""   )
														else:
																		import torch
														lowerCAmelCase	,  lowerCAmelCase		=			common_inputs["""input_ids"""].shape
														# Not using the same length for past_key_values
														lowerCAmelCase		=			seqlen + 2
														lowerCAmelCase	,  lowerCAmelCase		=			self.num_layers
														lowerCAmelCase	,  lowerCAmelCase		=			self.num_attention_heads
														lowerCAmelCase		=			(
														    batch,
														    num_encoder_attention_heads,
														    past_key_values_length,
														    self._config.hidden_size // num_encoder_attention_heads,
														)

														lowerCAmelCase		=			common_inputs["""attention_mask"""].dtype
														lowerCAmelCase		=			torch.cat(
														    [common_inputs["""attention_mask"""], torch.ones(lowerCAmelCase  ,  lowerCAmelCase  ,  dtype=lowerCAmelCase   )]  ,  dim=1   )
														lowerCAmelCase		=			[
														    (torch.zeros(lowerCAmelCase   ), torch.zeros(lowerCAmelCase   )) for _ in range(lowerCAmelCase   )
														]
										return common_inputs


						def 					__lowercase	(							self			:     str  ,  lowerCAmelCase			:     PreTrainedTokenizer  ,  lowerCAmelCase			:     int = -1  ,  lowerCAmelCase			:     int = -1  ,  lowerCAmelCase			:     bool = False  ,  lowerCAmelCase			:     Optional[TensorType] = None  ,  ):
										# Copied from OnnxConfig.generate_dummy_inputs
										# Did not use super(OnnxConfigWithPast, self).generate_dummy_inputs for code clarity.
										# If dynamic axis (-1) we forward with a fixed dimension of 2 samples to avoid optimizations made by ONNX
										lowerCAmelCase		=			compute_effective_axis_dimension(
										    lowerCAmelCase  ,  fixed_dimension=OnnxConfig.default_fixed_batch  ,  num_token_to_add=0   )

										# If dynamic axis (-1) we forward with a fixed dimension of 8 tokens to avoid optimizations made by ONNX
										lowerCAmelCase		=			tokenizer.num_special_tokens_to_add(lowerCAmelCase   )
										lowerCAmelCase		=			compute_effective_axis_dimension(
										    lowerCAmelCase  ,  fixed_dimension=OnnxConfig.default_fixed_sequence  ,  num_token_to_add=lowerCAmelCase   )

										# Generate dummy inputs according to compute batch and sequence
										lowerCAmelCase		=			[""" """.join([tokenizer.unk_token]   ) * seq_length] * batch_size
										lowerCAmelCase		=			dict(tokenizer(lowerCAmelCase  ,  return_tensors=lowerCAmelCase   )   )
										return common_inputs


						def 					__lowercase	(							self			:     int  ,  lowerCAmelCase			:     PreTrainedTokenizer  ,  lowerCAmelCase			:     int = -1  ,  lowerCAmelCase			:     int = -1  ,  lowerCAmelCase			:     bool = False  ,  lowerCAmelCase			:     Optional[TensorType] = None  ,  ):
										if self.task in ["default", "seq2seq-lm"]:
														lowerCAmelCase		=			self._generate_dummy_inputs_for_default_and_seqaseq_lm(
														    lowerCAmelCase  ,  batch_size=lowerCAmelCase  ,  seq_length=lowerCAmelCase  ,  is_pair=lowerCAmelCase  ,  framework=lowerCAmelCase   )

										elif self.task == "causal-lm":
														lowerCAmelCase		=			self._generate_dummy_inputs_for_causal_lm(
														    lowerCAmelCase  ,  batch_size=lowerCAmelCase  ,  seq_length=lowerCAmelCase  ,  is_pair=lowerCAmelCase  ,  framework=lowerCAmelCase   )
										else:
														lowerCAmelCase		=			self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
														    lowerCAmelCase  ,  batch_size=lowerCAmelCase  ,  seq_length=lowerCAmelCase  ,  is_pair=lowerCAmelCase  ,  framework=lowerCAmelCase   )

										return common_inputs




						def 					__lowercase	(							self			:     List[str]  ,  lowerCAmelCase			:     Optional[Any]  ,  lowerCAmelCase			:     List[Any]  ,  lowerCAmelCase			:     List[Any]  ,  lowerCAmelCase			:     int   ):
										if self.task in ["default", "seq2seq-lm"]:
														lowerCAmelCase		=			super()._flatten_past_key_values_(lowerCAmelCase  ,  lowerCAmelCase  ,  lowerCAmelCase  ,  lowerCAmelCase   )
										else:
														lowerCAmelCase		=			super(lowerCAmelCase  ,  self   )._flatten_past_key_values_(
														    lowerCAmelCase  ,  lowerCAmelCase  ,  lowerCAmelCase  ,  lowerCAmelCase   )





