
import unittest

from transformers import FunnelConfig, FunnelTokenizer, is_torch_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_sentencepiece, require_tokenizers, require_torch, slow, torch_device

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
							import torch

							from transformers import (
							    MODEL_FOR_PRETRAINING_MAPPING,
							    FunnelBaseModel,
							    FunnelForMaskedLM,
							    FunnelForMultipleChoice,
							    FunnelForPreTraining,
							    FunnelForQuestionAnswering,
							    FunnelForSequenceClassification,
							    FunnelForTokenClassification,
							    FunnelModel,
							)







class 	A_       :




	'''simple docstring'''


	def __init__(	self		,   snake_case		,   snake_case=13		,   snake_case=7		,   snake_case=True		,   snake_case=True		,   snake_case=True		,   snake_case=True		,   snake_case=99		,   snake_case=[1, 1, 2]		,   snake_case=1		,   snake_case=32		,   snake_case=4		,   snake_case=8		,   snake_case=37		,   snake_case="gelu_new"		,   snake_case=0.1		,   snake_case=0.1		,   snake_case=0.0		,   snake_case=512		,   snake_case=3		,   snake_case=0.02		,   snake_case=3		,   snake_case=4		,   snake_case=None		,   snake_case=False		,   ):
		lowercase					  =   parent
		lowercase					  =   batch_size
		lowercase					  =   seq_length
		lowercase					  =   is_training
		lowercase					  =   use_input_mask
		lowercase					  =   use_token_type_ids
		lowercase					  =   use_labels
		lowercase					  =   vocab_size
		lowercase					  =   block_sizes
		lowercase					  =   num_decoder_layers
		lowercase					  =   d_model
		lowercase					  =   n_head
		lowercase					  =   d_head
		lowercase					  =   d_inner
		lowercase					  =   hidden_act
		lowercase					  =   hidden_dropout
		lowercase					  =   attention_dropout
		lowercase					  =   activation_dropout
		lowercase					  =   max_position_embeddings
		lowercase					  =   type_vocab_size
		lowercase					  =   2
		lowercase					  =   num_labels
		lowercase					  =   num_choices
		lowercase					  =   scope
		lowercase					  =   initializer_std

		# Used in the tests to check the size of the first attention layer
		lowercase					  =   n_head
		# Used in the tests to check the size of the first hidden state
		lowercase					  =   self.d_model
		# Used in the tests to check the number of output hidden states/attentions
		lowercase					  =   sum(self.block_sizes	) + (0 if base else self.num_decoder_layers)
		# FunnelModel adds two hidden layers: input embeddings and the sum of the upsampled encoder hidden state with
		# the last hidden state of the first block (which is the first hidden state of the decoder).
		if not base:
			lowercase					  =   self.num_hidden_layers + 2





	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   ids_tensor([self.batch_size, self.seq_length]		,   self.vocab_size	)

		lowercase					  =   None
		if self.use_input_mask:
			lowercase					  =   ids_tensor([self.batch_size, self.seq_length]		,   vocab_size=2	)

		lowercase					  =   None
		if self.use_token_type_ids:
			lowercase					  =   ids_tensor([self.batch_size, self.seq_length]		,   self.type_vocab_size	)

		lowercase					  =   None
		lowercase					  =   None
		lowercase					  =   None
		if self.use_labels:
			lowercase					  =   ids_tensor([self.batch_size]		,   self.type_sequence_label_size	)
			lowercase					  =   ids_tensor([self.batch_size, self.seq_length]		,   self.num_labels	)
			lowercase					  =   ids_tensor([self.batch_size]		,   self.num_choices	)
			lowercase					  =   ids_tensor([self.batch_size, self.seq_length]		,   1	)

		lowercase					  =   self.get_config()

		return (
		    config,
		    input_ids,
		    token_type_ids,
		    input_mask,
		    sequence_labels,
		    token_labels,
		    choice_labels,
		    fake_token_labels,
		)





	def      SCREAMING_SNAKE_CASE__						(	self	):
		return FunnelConfig(
		    vocab_size=self.vocab_size		,   block_sizes=self.block_sizes		,   num_decoder_layers=self.num_decoder_layers		,   d_model=self.d_model		,   n_head=self.n_head		,   d_head=self.d_head		,   d_inner=self.d_inner		,   hidden_act=self.hidden_act		,   hidden_dropout=self.hidden_dropout		,   attention_dropout=self.attention_dropout		,   activation_dropout=self.activation_dropout		,   max_position_embeddings=self.max_position_embeddings		,   type_vocab_size=self.type_vocab_size		,   initializer_std=self.initializer_std		,   )





	def      SCREAMING_SNAKE_CASE__						(	self		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   ):
		lowercase					  =   FunnelModel(config=snake_case	)
		model.to(snake_case	)
		model.eval()
		lowercase					  =   model(snake_case		,   attention_mask=snake_case		,   token_type_ids=snake_case	)
		lowercase					  =   model(snake_case		,   token_type_ids=snake_case	)
		lowercase					  =   model(snake_case	)
		self.parent.assertEqual(result.last_hidden_state.shape		,   (self.batch_size, self.seq_length, self.d_model)	)

		lowercase					  =   False
		lowercase					  =   model(snake_case	)
		self.parent.assertEqual(result.last_hidden_state.shape		,   (self.batch_size, self.seq_length, self.d_model)	)

		lowercase					  =   False
		lowercase					  =   model(snake_case	)
		self.parent.assertEqual(result.last_hidden_state.shape		,   (self.batch_size, self.seq_length, self.d_model)	)





	def      SCREAMING_SNAKE_CASE__						(	self		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   ):
		lowercase					  =   FunnelBaseModel(config=snake_case	)
		model.to(snake_case	)
		model.eval()
		lowercase					  =   model(snake_case		,   attention_mask=snake_case		,   token_type_ids=snake_case	)
		lowercase					  =   model(snake_case		,   token_type_ids=snake_case	)
		lowercase					  =   model(snake_case	)
		self.parent.assertEqual(result.last_hidden_state.shape		,   (self.batch_size, 2, self.d_model)	)

		lowercase					  =   False
		lowercase					  =   model(snake_case	)
		self.parent.assertEqual(result.last_hidden_state.shape		,   (self.batch_size, 3, self.d_model)	)

		lowercase					  =   False
		lowercase					  =   model(snake_case	)
		self.parent.assertEqual(result.last_hidden_state.shape		,   (self.batch_size, 2, self.d_model)	)





	def      SCREAMING_SNAKE_CASE__						(	self		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   ):
		lowercase					  =   self.num_labels
		lowercase					  =   FunnelForPreTraining(config=snake_case	)
		model.to(snake_case	)
		model.eval()
		lowercase					  =   model(snake_case		,   attention_mask=snake_case		,   token_type_ids=snake_case		,   labels=snake_case	)
		self.parent.assertEqual(result.logits.shape		,   (self.batch_size, self.seq_length)	)





	def      SCREAMING_SNAKE_CASE__						(	self		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   ):
		lowercase					  =   FunnelForMaskedLM(config=snake_case	)
		model.to(snake_case	)
		model.eval()
		lowercase					  =   model(snake_case		,   attention_mask=snake_case		,   token_type_ids=snake_case		,   labels=snake_case	)
		self.parent.assertEqual(result.logits.shape		,   (self.batch_size, self.seq_length, self.vocab_size)	)





	def      SCREAMING_SNAKE_CASE__						(	self		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   ):
		lowercase					  =   self.num_labels
		lowercase					  =   FunnelForSequenceClassification(snake_case	)
		model.to(snake_case	)
		model.eval()
		lowercase					  =   model(snake_case		,   attention_mask=snake_case		,   token_type_ids=snake_case		,   labels=snake_case	)
		self.parent.assertEqual(result.logits.shape		,   (self.batch_size, self.num_labels)	)





	def      SCREAMING_SNAKE_CASE__						(	self		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   ):
		lowercase					  =   self.num_choices
		lowercase					  =   FunnelForMultipleChoice(config=snake_case	)
		model.to(snake_case	)
		model.eval()
		lowercase					  =   input_ids.unsqueeze(1	).expand(-1		,   self.num_choices		,   -1	).contiguous()
		lowercase					  =   token_type_ids.unsqueeze(1	).expand(-1		,   self.num_choices		,   -1	).contiguous()
		lowercase					  =   input_mask.unsqueeze(1	).expand(-1		,   self.num_choices		,   -1	).contiguous()
		lowercase					  =   model(
		    snake_case		,   attention_mask=snake_case		,   token_type_ids=snake_case		,   labels=snake_case		,   )
		self.parent.assertEqual(result.logits.shape		,   (self.batch_size, self.num_choices)	)





	def      SCREAMING_SNAKE_CASE__						(	self		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   ):
		lowercase					  =   self.num_labels
		lowercase					  =   FunnelForTokenClassification(config=snake_case	)
		model.to(snake_case	)
		model.eval()
		lowercase					  =   model(snake_case		,   attention_mask=snake_case		,   token_type_ids=snake_case		,   labels=snake_case	)
		self.parent.assertEqual(result.logits.shape		,   (self.batch_size, self.seq_length, self.num_labels)	)





	def      SCREAMING_SNAKE_CASE__						(	self		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   snake_case		,   ):
		lowercase					  =   FunnelForQuestionAnswering(config=snake_case	)
		model.to(snake_case	)
		model.eval()
		lowercase					  =   model(
		    snake_case		,   attention_mask=snake_case		,   token_type_ids=snake_case		,   start_positions=snake_case		,   end_positions=snake_case		,   )
		self.parent.assertEqual(result.start_logits.shape		,   (self.batch_size, self.seq_length)	)
		self.parent.assertEqual(result.end_logits.shape		,   (self.batch_size, self.seq_length)	)





	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   self.prepare_config_and_inputs()
		(
		    (
		    lowercase 
		)  , (
		    lowercase 
		)  , (
		    lowercase 
		)  , (
		    lowercase 
		)  , (
		    lowercase 
		)  , (
		    lowercase 
		)  , (
		    lowercase 
		)  , (
		    lowercase 
		)  ,  
		)					  =   config_and_inputs
		lowercase					  =   {'input_ids': input_ids, 'token_type_ids': token_type_ids, 'attention_mask': input_mask}
		return config, inputs_dict







@require_torch
class 	A_       (      __lowerCamelCase				,     __lowerCamelCase				,     unittest.TestCase       ):




	'''simple docstring'''


	_UpperCamelCase					:					Optional[int]										=	False
	_UpperCamelCase					:					int										=	False
	_UpperCamelCase					:					Optional[int]										=	(
	    (
	        FunnelModel,
	        FunnelForMaskedLM,
	        FunnelForPreTraining,
	        FunnelForQuestionAnswering,
	        FunnelForTokenClassification,
	    )
	    if is_torch_available()
	    else ()
	)
	_UpperCamelCase					:					List[Any]										=	(
	    {
	        """feature-extraction""": (FunnelBaseModel, FunnelModel),
	        """fill-mask""": FunnelForMaskedLM,
	        """question-answering""": FunnelForQuestionAnswering,
	        """text-classification""": FunnelForSequenceClassification,
	        """token-classification""": FunnelForTokenClassification,
	        """zero-shot""": FunnelForSequenceClassification,
	    }
	    if is_torch_available()
	    else {}
	)





	def      SCREAMING_SNAKE_CASE__						(	self		,   snake_case		,   snake_case		,   snake_case=False	):
		lowercase					  =   super()._prepare_for_class(snake_case		,   snake_case		,   return_labels=snake_case	)

		if return_labels:
			if model_class in get_values(snake_case	):
				lowercase					  =   torch.zeros(
				    (self.model_tester.batch_size, self.model_tester.seq_length)		,   dtype=torch.long		,   device=snake_case	)
		return inputs_dict





	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   FunnelModelTester(self	)
		lowercase					  =   ConfigTester(self		,   config_class=snake_case	)





	def      SCREAMING_SNAKE_CASE__						(	self	):
		self.config_tester.run_common_tests()





	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_model(*snake_case	)





	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_for_pretraining(*snake_case	)





	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_for_masked_lm(*snake_case	)





	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_for_token_classification(*snake_case	)





	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_for_question_answering(*snake_case	)





	def      SCREAMING_SNAKE_CASE__						(	self		,   snake_case	):
		if hasattr(snake_case		,   'weight'	) and module.weight is not None:
			module.weight.data.fill_(3	)
		if hasattr(snake_case		,   'bias'	) and module.bias is not None:
			module.bias.data.fill_(3	)

		for param in ["r_w_bias", "r_r_bias", "r_kernel", "r_s_bias", "seg_embed"]:
			if hasattr(snake_case		,   snake_case	) and getattr(snake_case		,   snake_case	) is not None:
				lowercase					  =   getattr(snake_case		,   snake_case	)
				weight.data.fill_(3	)







@require_torch
class 	A_       (      __lowerCamelCase				,     unittest.TestCase       ):




	'''simple docstring'''


	_UpperCamelCase					:					Tuple										=	False
	_UpperCamelCase					:					Optional[int]										=	False
	_UpperCamelCase					:					Union[str, Any]										=	(
	    (FunnelBaseModel, FunnelForMultipleChoice, FunnelForSequenceClassification) if is_torch_available() else ()
	)





	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   FunnelModelTester(self		,   base=snake_case	)
		lowercase					  =   ConfigTester(self		,   config_class=snake_case	)





	def      SCREAMING_SNAKE_CASE__						(	self	):
		self.config_tester.run_common_tests()





	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_base_model(*snake_case	)





	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_for_sequence_classification(*snake_case	)





	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   self.model_tester.prepare_config_and_inputs()
		self.model_tester.create_and_check_for_multiple_choice(*snake_case	)





	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase  , lowercase					  =   self.model_tester.prepare_config_and_inputs_for_common()
		lowercase					  =   True

		for model_class in self.all_model_classes:
			if model_class.__name__ == "FunnelBaseModel":
				continue
			lowercase					  =   model_class(snake_case	)
			model.to(snake_case	)
			model.train()
			lowercase					  =   self._prepare_for_class(snake_case		,   snake_case		,   return_labels=snake_case	)
			lowercase					  =   model(**snake_case	).loss
			loss.backward()





	def      SCREAMING_SNAKE_CASE__						(	self		,   snake_case	):
		if hasattr(snake_case		,   'weight'	) and module.weight is not None:
			module.weight.data.fill_(3	)
		if hasattr(snake_case		,   'bias'	) and module.bias is not None:
			module.bias.data.fill_(3	)

		for param in ["r_w_bias", "r_r_bias", "r_kernel", "r_s_bias", "seg_embed"]:
			if hasattr(snake_case		,   snake_case	) and getattr(snake_case		,   snake_case	) is not None:
				lowercase					  =   getattr(snake_case		,   snake_case	)
				weight.data.fill_(3	)







@require_torch
@require_sentencepiece
@require_tokenizers
class 	A_       (      unittest.TestCase       ):




	'''simple docstring'''


	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   13
		lowercase					  =   7
		lowercase					  =   torch.arange(0		,   batch_size * sequence_length	).long().reshape(snake_case		,   snake_case	)
		lowercase					  =   [0, 1, 2, 3, 4, 5, 6, 4, 1, 3, 5, 0, 1]
		lowercase					  =   torch.tensor([[2] + [0] * a + [1] * (sequence_length - a - 1) for a in lengths]	)

		lowercase					  =   FunnelModel.from_pretrained('sgugger/funnel-random-tiny'	)
		lowercase					  =   model(snake_case		,   token_type_ids=snake_case	)[0].abs()

		lowercase					  =   torch.tensor(2344.8352	)
		lowercase					  =   torch.tensor(0.8_052	)
		self.assertTrue(torch.allclose(output.sum()		,   snake_case		,   atol=1E-4	)	)
		self.assertTrue(torch.allclose(output.mean()		,   snake_case		,   atol=1E-4	)	)

		lowercase					  =   torch.tensor([[1] * 7, [1] * 4 + [0] * 3] * 6 + [[0, 1, 1, 0, 0, 1, 1]]	)
		lowercase					  =   model(snake_case		,   attention_mask=snake_case		,   token_type_ids=snake_case	)[0].abs()

		lowercase					  =   torch.tensor(2343.8425	)
		lowercase					  =   torch.tensor(0.8_049	)
		self.assertTrue(torch.allclose(output.sum()		,   snake_case		,   atol=1E-4	)	)
		self.assertTrue(torch.allclose(output.mean()		,   snake_case		,   atol=1E-4	)	)





	@slow
	def      SCREAMING_SNAKE_CASE__						(	self	):
		lowercase					  =   FunnelTokenizer.from_pretrained('huggingface/funnel-small'	)
		lowercase					  =   FunnelModel.from_pretrained('huggingface/funnel-small'	)
		lowercase					  =   tokenizer('Hello! I am the Funnel Transformer model.'		,   return_tensors='pt'	)
		lowercase					  =   model(**snake_case	)[0]

		lowercase					  =   torch.tensor(235.7_246	)
		lowercase					  =   torch.tensor(0.0_256	)
		self.assertTrue(torch.allclose(output.sum()		,   snake_case		,   atol=1E-4	)	)
		self.assertTrue(torch.allclose(output.mean()		,   snake_case		,   atol=1E-4	)	)



def 							UpperCAmelCase_		(							__SCREAMING_SNAKE_CASE							):
	lowercase					  =   [701, 301, 132, 57, 23, 10, 4, 1]
	for gap in gaps:
		for i in range(__SCREAMING_SNAKE_CASE			,							len(__SCREAMING_SNAKE_CASE							)							):
			lowercase					  =   collection[i]
			lowercase					  =   i
			while j >= gap and collection[j - gap] > insert_value:
				lowercase					  =   collection[j - gap]
				j -= gap
			if j != i:
				lowercase					  =   insert_value
	return collection


if __name__ == "__main__":
	from doctest import testmod

	testmod()
	UpperCAmelCase     				=			input('''Enter numbers separated by a comma:\n''').strip()
	UpperCAmelCase     				=			[int(item) for item in user_input.split(''',''')]
	print(shell_sort(unsorted))

