



'''simple docstring'''

from __future__ import annotations






def 		_snake_case		(					_SCREAMING_SNAKE_CASE     :						list							,		_SCREAMING_SNAKE_CASE     :						list							)			->						list:







	"""simple docstring"""
	lowerCAmelCase    =	[None] * (len(_SCREAMING_SNAKE_CASE							) + len(_SCREAMING_SNAKE_CASE							))

	lowerCAmelCase    =	0  # pointer to current index for left Half
	lowerCAmelCase    =	0  # pointer to current index for the right Half
	lowerCAmelCase    =	0  # pointer to current index for the sorted array Half

	while pointera < len(_SCREAMING_SNAKE_CASE							) and pointera < len(_SCREAMING_SNAKE_CASE							):
		if left_half[pointera] < right_half[pointera]:
			lowerCAmelCase    =	left_half[pointera]
			pointera += 1
			index += 1
		else:
			lowerCAmelCase    =	right_half[pointera]
			pointera += 1
			index += 1
	while pointera < len(_SCREAMING_SNAKE_CASE							):
		lowerCAmelCase    =	left_half[pointera]
		pointera += 1
		index += 1

	while pointera < len(_SCREAMING_SNAKE_CASE							):
		lowerCAmelCase    =	right_half[pointera]
		pointera += 1
		index += 1

	return sorted_array






def 		_snake_case		(					_SCREAMING_SNAKE_CASE     :						list							)			->						list:







	"""simple docstring"""
	if len(_SCREAMING_SNAKE_CASE							) <= 1:
		return array
	# the actual formula to calculate the middle element = left + (right - left) // 2
	# this avoids integer overflow in case of large N
	lowerCAmelCase    =	0 + (len(_SCREAMING_SNAKE_CASE							) - 0) // 2

	# Split the array into halves till the array length becomes equal to One
	# merge the arrays of single length returned by mergeSort function and
	# pass them into the merge arrays function which merges the array
	lowerCAmelCase    =	array[:middle]
	lowerCAmelCase    =	array[middle:]

	return merge(merge_sort(_SCREAMING_SNAKE_CASE							)							,		merge_sort(_SCREAMING_SNAKE_CASE							)							)


if __name__ == "__main__":
				import doctest

				doctest.testmod()




'''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


UpperCAmelCase			=    logging.get_logger(__name__)

UpperCAmelCase			=    {
    'google/bigbird-pegasus-large-arxiv': (
        'https://huggingface.co/google/bigbird-pegasus-large-arxiv/resolve/main/config.json'
    ),
    'google/bigbird-pegasus-large-pubmed': (
        'https://huggingface.co/google/bigbird-pegasus-large-pubmed/resolve/main/config.json'
    ),
    'google/bigbird-pegasus-large-bigpatent': (
        'https://huggingface.co/google/bigbird-pegasus-large-bigpatent/resolve/main/config.json'
    ),
    # See all BigBirdPegasus models at https://huggingface.co/models?filter=bigbird_pegasus
}

class __snake_case(      _lowerCAmelCase					):


						'''simple docstring'''



						UpperCAmelCase							:    Union[str, Any]           =		"bigbird_pegasus"
						UpperCAmelCase							:    Optional[Any]           =		["past_key_values"]
						UpperCAmelCase							:    Optional[Any]           =		{
						    "num_attention_heads": "encoder_attention_heads",
						    "hidden_size": "d_model",
						    "attention_probs_dropout_prob": "attention_dropout",
						}


						def __init__(					self	,       A_=9_6103	,       A_=4096	,       A_=16	,       A_=4096	,       A_=16	,       A_=16	,       A_=4096	,       A_=16	,       A_=0.0	,       A_=0.0	,       A_=True	,       A_=True	,       A_="gelu_new"	,       A_=1024	,       A_=0.1	,       A_=0.0	,       A_=0.0	,       A_=0.0_2	,       A_=2	,       A_=0.0	,       A_=True	,       A_=0	,       A_=2	,       A_=1	,       A_="block_sparse"	,       A_=64	,       A_=3	,       A_=False	,       **A_	,       )	->	List[str]:
							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

							# extra config
							lowerCAmelCase    =	attention_type
							lowerCAmelCase    =	block_size
							lowerCAmelCase    =	num_random_blocks
							lowerCAmelCase    =	use_bias

							super().__init__(
							    pad_token_id=A_	,       bos_token_id=A_	,       eos_token_id=A_	,       is_encoder_decoder=A_	,       decoder_start_token_id=A_	,       **A_	,       )







class __snake_case(      _lowerCAmelCase					):


						'''simple docstring'''



						@property
						def 				__snake_case    (					self      )	->	Mapping[str, Mapping[int, str]]:
							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_(A_	,       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(A_      ):
										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 				__snake_case    (					self      )	->	Mapping[str, Mapping[int, str]]:
							if self.task in ["default", "seq2seq-lm"]:
								lowerCAmelCase    =	super().outputs
							else:
								lowerCAmelCase    =	super(A_	,       self      ).outputs
								if self.use_past:
									lowerCAmelCase,   lowerCAmelCase    =	self.num_layers
									for i in range(A_      ):
										lowerCAmelCase    =	{0: """batch""", 2: """past_sequence + sequence"""}
										lowerCAmelCase    =	{0: """batch""", 2: """past_sequence + sequence"""}
							return common_outputs


						def 				__snake_case    (					self	,       A_	,       A_ = -1	,       A_ = -1	,       A_ = False	,       A_ = None	,       )	->	Mapping[str, Any]:
							lowerCAmelCase    =	self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
							    A_	,       A_	,       A_	,       A_	,       A_      )

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

							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(A_	,       A_      )]	,       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(A_	,       A_      )
								lowerCAmelCase    =	max(A_	,       A_      ) - min_num_layers
								lowerCAmelCase    =	"""encoder""" if num_encoder_layers > num_decoder_layers else """decoder"""

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


						def 				__snake_case    (					self	,       A_	,       A_ = -1	,       A_ = -1	,       A_ = False	,       A_ = None	,       )	->	Mapping[str, Any]:
							lowerCAmelCase    =	self._generate_dummy_inputs_for_sequence_classification_and_question_answering(
							    A_	,       A_	,       A_	,       A_	,       A_      )

							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(A_	,       A_	,       dtype=A_      )]	,       dim=1      )
								lowerCAmelCase    =	[
								    (torch.zeros(A_      ), torch.zeros(A_      )) for _ in range(A_      )
								]
							return common_inputs


						def 				__snake_case    (					self	,       A_	,       A_ = -1	,       A_ = -1	,       A_ = False	,       A_ = None	,       )	->	Mapping[str, Any]:
							# 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(
							    A_	,       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(A_      )
							lowerCAmelCase    =	compute_effective_axis_dimension(
							    A_	,       fixed_dimension=OnnxConfig.default_fixed_sequence	,       num_token_to_add=A_      )

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


						def 				__snake_case    (					self	,       A_	,       A_ = -1	,       A_ = -1	,       A_ = False	,       A_ = None	,       )	->	Mapping[str, Any]:
							if self.task in ["default", "seq2seq-lm"]:
								lowerCAmelCase    =	self._generate_dummy_inputs_for_default_and_seqaseq_lm(
								    A_	,       batch_size=A_	,       seq_length=A_	,       is_pair=A_	,       framework=A_      )

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

							return common_inputs




						def 				__snake_case    (					self	,       A_	,       A_	,       A_	,       A_      )	->	Tuple:
							if self.task in ["default", "seq2seq-lm"]:
								lowerCAmelCase    =	super()._flatten_past_key_values_(A_	,       A_	,       A_	,       A_      )
							else:
								lowerCAmelCase    =	super(A_	,       self      )._flatten_past_key_values_(
								    A_	,       A_	,       A_	,       A_      )