




def 					SCREAMING_SNAKE_CASE    (			):
	return [list(range(1000 - i					,  -1000 - i					,  -1       )       ) for i in range(1000       )]


__lowerCamelCase :      Dict										=				generate_large_matrix()
__lowerCamelCase :      str										=				(
    [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]],
    [[3, 2], [1, 0]],
    [[7, 7, 6]],
    [[7, 7, 6], [-1, -2, -3]],
    grid,
)







def 					SCREAMING_SNAKE_CASE    (			snake_case_ :							Optional[int]       ):
	assert all(row == sorted(SCREAMING_SNAKE_CASE_					,  reverse=SCREAMING_SNAKE_CASE_       ) for row in grid       )
	assert all(list(SCREAMING_SNAKE_CASE_       ) == sorted(SCREAMING_SNAKE_CASE_					,  reverse=SCREAMING_SNAKE_CASE_       ) for col in zip(*SCREAMING_SNAKE_CASE_       )       )







def 					SCREAMING_SNAKE_CASE    (			snake_case_ :							Tuple       ):
	snake_case__			:				str       =  0
	snake_case__			:				Dict       =  len(SCREAMING_SNAKE_CASE_       ) - 1

	# Edge cases such as no values or all numbers are negative.
	if not array or array[0] < 0:
		return 0

	while right + 1 > left:
		snake_case__			:				Tuple       =  (left + right) // 2
		snake_case__			:				Optional[Any]       =  array[mid]

		# Num must be negative and the index must be greater than or equal to 0.
		if num < 0 and array[mid - 1] >= 0:
			return mid

		if num >= 0:
			snake_case__			:				Optional[Any]       =  mid + 1
		else:
			snake_case__			:				List[Any]       =  mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
	return len(SCREAMING_SNAKE_CASE_       )







def 					SCREAMING_SNAKE_CASE    (			snake_case_ :							List[Any]       ):
	snake_case__			:				Optional[Any]       =  0
	snake_case__			:				Optional[int]       =  len(grid[0]       )

	for i in range(len(SCREAMING_SNAKE_CASE_       )       ):
		snake_case__			:				Tuple       =  find_negative_index(grid[i][:bound]       )
		total += bound
	return (len(SCREAMING_SNAKE_CASE_       ) * len(grid[0]       )) - total







def 					SCREAMING_SNAKE_CASE    (			snake_case_ :							List[str]       ):
	return len([number for row in grid for number in row if number < 0]       )







def 					SCREAMING_SNAKE_CASE    (			snake_case_ :							List[str]       ):
	snake_case__			:				Tuple       =  0
	for row in grid:
		for i, number in enumerate(SCREAMING_SNAKE_CASE_       ):
			if number < 0:
				total += len(SCREAMING_SNAKE_CASE_       ) - i
				break
	return total







def 					SCREAMING_SNAKE_CASE    (			):
	from timeit import timeit

	print("Running benchmarks"       )
	snake_case__			:				List[Any]       =  (
	    "from __main__ import count_negatives_binary_search, "
	    "count_negatives_brute_force, count_negatives_brute_force_with_break, grid"
	)
	for func in (
	    "count_negatives_binary_search",  # took 0.7727 seconds
	    "count_negatives_brute_force_with_break",  # took 4.6505 seconds
	    "count_negatives_brute_force",  # took 12.8160 seconds
	):
		snake_case__			:				str       =  timeit(F'''{func}(grid=grid)'''					,  setup=SCREAMING_SNAKE_CASE_					,  number=500       )
		print(F'''{func}() took {time:0.4f} seconds'''       )


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	benchmark()











from __future__ import annotations

import os
import tempfile
import unittest

from transformers import ConvBertConfig, is_tf_available
from transformers.testing_utils import require_tf, slow

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
	import tensorflow as tf

	from transformers import (
	    TFConvBertForMaskedLM,
	    TFConvBertForMultipleChoice,
	    TFConvBertForQuestionAnswering,
	    TFConvBertForSequenceClassification,
	    TFConvBertForTokenClassification,
	    TFConvBertModel,
	)



class 							SCREAMING_SNAKE_CASE__						:





					"""simple docstring"""






					def __init__( self					:  Union[str, Any]							,		__A					:  str							,		__A					:  Optional[Any]=1_3							,		__A					:  Dict=7							,		__A					:  List[str]=True							,		__A					:  Any=True							,		__A					:  str=True							,		__A					:  Optional[Any]=True							,		__A					:  List[str]=9_9							,		__A					:  Dict=3_2							,		__A					:  Tuple=2							,		__A					:  Tuple=4							,		__A					:  Dict=3_7							,		__A					:  Tuple="gelu"							,		__A					:  Any=0.1							,		__A					:  str=0.1							,		__A					:  int=5_1_2							,		__A					:  Union[str, Any]=1_6							,		__A					:  Optional[int]=2							,		__A					:  Union[str, Any]=0.0_2							,		__A					:  Tuple=3							,		__A					:  Union[str, Any]=4							,		__A					:  Optional[int]=None							,		):
						snake_case__			:				Optional[int]       =  parent
						snake_case__			:				Optional[Any]       =  1_3
						snake_case__			:				int       =  7
						snake_case__			:				Optional[int]       =  True
						snake_case__			:				Optional[Any]       =  True
						snake_case__			:				List[str]       =  True
						snake_case__			:				int       =  True
						snake_case__			:				Optional[int]       =  9_9
						snake_case__			:				Union[str, Any]       =  3_8_4
						snake_case__			:				Optional[Any]       =  2
						snake_case__			:				Union[str, Any]       =  4
						snake_case__			:				Any       =  3_7
						snake_case__			:				Any       =  "gelu"
						snake_case__			:				str       =  0.1
						snake_case__			:				Optional[Any]       =  0.1
						snake_case__			:				Union[str, Any]       =  5_1_2
						snake_case__			:				Optional[Any]       =  1_6
						snake_case__			:				List[Any]       =  2
						snake_case__			:				Optional[int]       =  0.0_2
						snake_case__			:				Dict       =  3
						snake_case__			:				Any       =  4
						snake_case__			:				int       =  1_2_8
						snake_case__			:				Dict       =  2
						snake_case__			:				Any       =  9
						snake_case__			:				List[str]       =  1
						snake_case__			:				List[Any]       =  None



					def 	_lowercase					( self					:  List[str]	):
						snake_case__			:				Optional[int]       =  ids_tensor([self.batch_size, self.seq_length]							,		self.vocab_size	)

						snake_case__			:				str       =  None
						if self.use_input_mask:
							snake_case__			:				str       =  random_attention_mask([self.batch_size, self.seq_length]	)

						snake_case__			:				Union[str, Any]       =  None
						if self.use_token_type_ids:
							snake_case__			:				Tuple       =  ids_tensor([self.batch_size, self.seq_length]							,		self.type_vocab_size	)

						snake_case__			:				Optional[Any]       =  None
						snake_case__			:				Any       =  None
						snake_case__			:				Tuple       =  None
						if self.use_labels:
							snake_case__			:				List[str]       =  ids_tensor([self.batch_size]							,		self.type_sequence_label_size	)
							snake_case__			:				str       =  ids_tensor([self.batch_size, self.seq_length]							,		self.num_labels	)
							snake_case__			:				int       =  ids_tensor([self.batch_size]							,		self.num_choices	)

						snake_case__			:				int       =  ConvBertConfig(
						    vocab_size=self.vocab_size							,		hidden_size=self.hidden_size							,		num_hidden_layers=self.num_hidden_layers							,		num_attention_heads=self.num_attention_heads							,		intermediate_size=self.intermediate_size							,		hidden_act=self.hidden_act							,		hidden_dropout_prob=self.hidden_dropout_prob							,		attention_probs_dropout_prob=self.attention_probs_dropout_prob							,		max_position_embeddings=self.max_position_embeddings							,		type_vocab_size=self.type_vocab_size							,		initializer_range=self.initializer_range							,		return_dict=__A							,		)

						return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels



					def 	_lowercase					( self					:  Dict							,		__A					:  Dict							,		__A					:  Dict							,		__A					:  Union[str, Any]							,		__A					:  Optional[int]							,		__A					:  Any							,		__A					:  Union[str, Any]							,		__A					:  Tuple	):
						snake_case__			:				Optional[int]       =  TFConvBertModel(config=__A	)
						snake_case__			:				Optional[int]       =  {"input_ids": input_ids, "attention_mask": input_mask, "token_type_ids": token_type_ids}

						snake_case__			:				List[str]       =  [input_ids, input_mask]
						snake_case__			:				Union[str, Any]       =  model(__A	)

						snake_case__			:				str       =  model(__A	)

						self.parent.assertEqual(result.last_hidden_state.shape							,		(self.batch_size, self.seq_length, self.hidden_size)	)



					def 	_lowercase					( self					:  Union[str, Any]							,		__A					:  List[Any]							,		__A					:  Any							,		__A					:  Union[str, Any]							,		__A					:  int							,		__A					:  Optional[Any]							,		__A					:  Dict							,		__A					:  Optional[int]	):
						snake_case__			:				List[str]       =  TFConvBertForMaskedLM(config=__A	)
						snake_case__			:				Any       =  {
						    "input_ids": input_ids,
						    "attention_mask": input_mask,
						    "token_type_ids": token_type_ids,
						}
						snake_case__			:				int       =  model(__A	)
						self.parent.assertEqual(result.logits.shape							,		(self.batch_size, self.seq_length, self.vocab_size)	)



					def 	_lowercase					( self					:  Tuple							,		__A					:  Union[str, Any]							,		__A					:  List[Any]							,		__A					:  Any							,		__A					:  List[Any]							,		__A					:  List[Any]							,		__A					:  Optional[int]							,		__A					:  List[str]	):
						snake_case__			:				Any       =  self.num_labels
						snake_case__			:				List[Any]       =  TFConvBertForSequenceClassification(config=__A	)
						snake_case__			:				Any       =  {
						    "input_ids": input_ids,
						    "attention_mask": input_mask,
						    "token_type_ids": token_type_ids,
						}

						snake_case__			:				Optional[int]       =  model(__A	)
						self.parent.assertEqual(result.logits.shape							,		(self.batch_size, self.num_labels)	)



					def 	_lowercase					( self					:  int							,		__A					:  List[Any]							,		__A					:  Union[str, Any]							,		__A					:  Optional[Any]							,		__A					:  List[Any]							,		__A					:  Union[str, Any]							,		__A					:  Union[str, Any]							,		__A					:  Optional[int]	):
						snake_case__			:				Optional[Any]       =  self.num_choices
						snake_case__			:				Any       =  TFConvBertForMultipleChoice(config=__A	)
						snake_case__			:				Optional[int]       =  tf.tile(tf.expand_dims(__A							,		1	)							,		(1, self.num_choices, 1)	)
						snake_case__			:				Optional[Any]       =  tf.tile(tf.expand_dims(__A							,		1	)							,		(1, self.num_choices, 1)	)
						snake_case__			:				Optional[int]       =  tf.tile(tf.expand_dims(__A							,		1	)							,		(1, self.num_choices, 1)	)
						snake_case__			:				int       =  {
						    "input_ids": multiple_choice_inputs_ids,
						    "attention_mask": multiple_choice_input_mask,
						    "token_type_ids": multiple_choice_token_type_ids,
						}
						snake_case__			:				Optional[Any]       =  model(__A	)
						self.parent.assertEqual(result.logits.shape							,		(self.batch_size, self.num_choices)	)



					def 	_lowercase					( self					:  List[str]							,		__A					:  Tuple							,		__A					:  str							,		__A					:  Union[str, Any]							,		__A					:  Union[str, Any]							,		__A					:  Any							,		__A					:  int							,		__A					:  Tuple	):
						snake_case__			:				Dict       =  self.num_labels
						snake_case__			:				str       =  TFConvBertForTokenClassification(config=__A	)
						snake_case__			:				Optional[Any]       =  {
						    "input_ids": input_ids,
						    "attention_mask": input_mask,
						    "token_type_ids": token_type_ids,
						}
						snake_case__			:				List[str]       =  model(__A	)
						self.parent.assertEqual(result.logits.shape							,		(self.batch_size, self.seq_length, self.num_labels)	)



					def 	_lowercase					( self					:  Optional[int]							,		__A					:  Union[str, Any]							,		__A					:  List[Any]							,		__A					:  List[str]							,		__A					:  Any							,		__A					:  Any							,		__A					:  Optional[int]							,		__A					:  Optional[Any]	):
						snake_case__			:				Any       =  TFConvBertForQuestionAnswering(config=__A	)
						snake_case__			:				List[str]       =  {
						    "input_ids": input_ids,
						    "attention_mask": input_mask,
						    "token_type_ids": token_type_ids,
						}

						snake_case__			:				int       =  model(__A	)
						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 	_lowercase					( self					:  Any	):
						snake_case__			:				List[Any]       =  self.prepare_config_and_inputs()
						(
						    (
						    snake_case__
						),						(
						    snake_case__
						),						(
						    snake_case__
						),						(
						    snake_case__
						),						(
						    snake_case__
						),						(
						    snake_case__
						),						(
						    snake_case__
						),						
						)			:				List[str]       =  config_and_inputs
						snake_case__			:				Tuple       =  {"input_ids": input_ids, "token_type_ids": token_type_ids, "attention_mask": input_mask}
						return config, inputs_dict



@require_tf
class 							SCREAMING_SNAKE_CASE__						(    UpperCamelCase_			,       UpperCamelCase_			,       unittest.TestCase						):





					"""simple docstring"""






					a_     =		(
					    (
					        TFConvBertModel,
					        TFConvBertForMaskedLM,
					        TFConvBertForQuestionAnswering,
					        TFConvBertForSequenceClassification,
					        TFConvBertForTokenClassification,
					        TFConvBertForMultipleChoice,
					    )
					    if is_tf_available()
					    else ()
					)
					a_     =		(
					    {
					        "feature-extraction": TFConvBertModel,
					        "fill-mask": TFConvBertForMaskedLM,
					        "question-answering": TFConvBertForQuestionAnswering,
					        "text-classification": TFConvBertForSequenceClassification,
					        "token-classification": TFConvBertForTokenClassification,
					        "zero-shot": TFConvBertForSequenceClassification,
					    }
					    if is_tf_available()
					    else {}
					)
					a_     =		False
					a_     =		False
					a_     =		False



					def 	_lowercase					( self					:  int	):
						snake_case__			:				Optional[Any]       =  TFConvBertModelTester(self	)
						snake_case__			:				List[str]       =  ConfigTester(self							,		config_class=__A							,		hidden_size=3_7	)



					def 	_lowercase					( self					:  List[Any]	):
						self.config_tester.run_common_tests()



					def 	_lowercase					( self					:  Any	):
						snake_case__			:				List[str]       =  self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_model(*__A	)



					def 	_lowercase					( self					:  Union[str, Any]	):
						snake_case__			:				Any       =  self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_for_masked_lm(*__A	)



					def 	_lowercase					( self					:  Dict	):
						snake_case__			:				str       =  self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_for_multiple_choice(*__A	)



					def 	_lowercase					( self					:  Optional[Any]	):
						snake_case__			:				List[str]       =  self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_for_question_answering(*__A	)



					def 	_lowercase					( self					:  Optional[int]	):
						snake_case__			:				int       =  self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_for_sequence_classification(*__A	)



					def 	_lowercase					( self					:  Dict	):
						snake_case__			:				Any       =  self.model_tester.prepare_config_and_inputs()
						self.model_tester.create_and_check_for_token_classification(*__A	)



					@slow
					def 	_lowercase					( self					:  Dict	):
						snake_case__,						snake_case__			:				Tuple       =  self.model_tester.prepare_config_and_inputs_for_common()
						snake_case__			:				int       =  True
						snake_case__			:				int       =  True

						if hasattr(__A							,		"use_cache"	):
							snake_case__			:				Optional[Any]       =  True

						snake_case__			:				Dict       =  getattr(self.model_tester							,		"encoder_seq_length"							,		self.model_tester.seq_length	)
						snake_case__			:				List[str]       =  getattr(self.model_tester							,		"key_length"							,		__A	)

						for model_class in self.all_model_classes:
							snake_case__			:				Tuple       =  self._prepare_for_class(__A							,		__A	)
							snake_case__			:				List[str]       =  model_class(__A	)
							snake_case__			:				List[Any]       =  len(model(__A	)	)

							with tempfile.TemporaryDirectory() as tmpdirname:
								model.save_pretrained(__A							,		saved_model=__A	)
								snake_case__			:				str       =  os.path.join(__A							,		"saved_model"							,		"1"	)
								snake_case__			:				str       =  tf.keras.models.load_model(__A	)
								snake_case__			:				Optional[Any]       =  model(__A	)

								if self.is_encoder_decoder:
									snake_case__			:				Tuple       =  outputs["encoder_hidden_states"]
									snake_case__			:				str       =  outputs["encoder_attentions"]
								else:
									snake_case__			:				Dict       =  outputs["hidden_states"]
									snake_case__			:				Tuple       =  outputs["attentions"]

								self.assertEqual(len(__A	)							,		__A	)

								snake_case__			:				int       =  getattr(
								    self.model_tester							,		"expected_num_hidden_layers"							,		self.model_tester.num_hidden_layers + 1	)

								self.assertEqual(len(__A	)							,		__A	)
								self.assertListEqual(
								    list(output_hidden_states[0].shape[-2:]	)							,		[self.model_tester.seq_length, self.model_tester.hidden_size]							,		)

								self.assertEqual(len(__A	)							,		self.model_tester.num_hidden_layers	)
								self.assertListEqual(
								    list(output_attentions[0].shape[-3:]	)							,		[self.model_tester.num_attention_heads / 2, encoder_seq_length, encoder_key_length]							,		)



					@slow
					def 	_lowercase					( self					:  Tuple	):
						snake_case__			:				Optional[Any]       =  TFConvBertModel.from_pretrained("YituTech/conv-bert-base"	)
						self.assertIsNotNone(__A	)






					def 	_lowercase					( self					:  List[str]	):
						snake_case__,						snake_case__			:				Optional[Any]       =  self.model_tester.prepare_config_and_inputs_for_common()
						snake_case__			:				Optional[Any]       =  True
						snake_case__			:				List[Any]       =  getattr(self.model_tester							,		"decoder_seq_length"							,		self.model_tester.seq_length	)
						snake_case__			:				int       =  getattr(self.model_tester							,		"encoder_seq_length"							,		self.model_tester.seq_length	)
						snake_case__			:				Any       =  getattr(self.model_tester							,		"key_length"							,		__A	)
						snake_case__			:				List[Any]       =  getattr(self.model_tester							,		"key_length"							,		__A	)

						def check_decoder_attentions_output(__A					:  Optional[int]	):
							snake_case__			:				Optional[Any]       =  len(__A	)
							self.assertEqual(out_len % 2							,		0	)
							snake_case__			:				Optional[int]       =  outputs.decoder_attentions
							self.assertEqual(len(__A	)							,		self.model_tester.num_hidden_layers	)
							self.assertListEqual(
							    list(decoder_attentions[0].shape[-3:]	)							,		[self.model_tester.num_attention_heads / 2, decoder_seq_length, decoder_key_length]							,		)

						def check_encoder_attentions_output(__A					:  Any	):
							snake_case__			:				List[Any]       =  [
							    t.numpy() for t in (outputs.encoder_attentions if config.is_encoder_decoder else outputs.attentions)
							]
							self.assertEqual(len(__A	)							,		self.model_tester.num_hidden_layers	)
							self.assertListEqual(
							    list(attentions[0].shape[-3:]	)							,		[self.model_tester.num_attention_heads / 2, encoder_seq_length, encoder_key_length]							,		)

						for model_class in self.all_model_classes:
							snake_case__			:				Optional[int]       =  True
							snake_case__			:				Any       =  False
							snake_case__			:				Dict       =  model_class(__A	)
							snake_case__			:				List[Any]       =  model(self._prepare_for_class(__A							,		__A	)	)
							snake_case__			:				Dict       =  len(__A	)
							self.assertEqual(config.output_hidden_states							,		__A	)
							check_encoder_attentions_output(__A	)

							if self.is_encoder_decoder:
								snake_case__			:				str       =  model_class(__A	)
								snake_case__			:				List[Any]       =  model(self._prepare_for_class(__A							,		__A	)	)
								self.assertEqual(config.output_hidden_states							,		__A	)
								check_decoder_attentions_output(__A	)

							# Check that output attentions can also be changed via the config
							del inputs_dict["output_attentions"]
							snake_case__			:				Optional[int]       =  True
							snake_case__			:				Optional[Any]       =  model_class(__A	)
							snake_case__			:				Union[str, Any]       =  model(self._prepare_for_class(__A							,		__A	)	)
							self.assertEqual(config.output_hidden_states							,		__A	)
							check_encoder_attentions_output(__A	)

							# Check attention is always last and order is fine
							snake_case__			:				Optional[int]       =  True
							snake_case__			:				List[Any]       =  True
							snake_case__			:				Any       =  model_class(__A	)
							snake_case__			:				str       =  model(self._prepare_for_class(__A							,		__A	)	)

							self.assertEqual(out_len + (2 if self.is_encoder_decoder else 1)							,		len(__A	)	)
							self.assertEqual(model.config.output_hidden_states							,		__A	)
							check_encoder_attentions_output(__A	)



@require_tf
class 							SCREAMING_SNAKE_CASE__						(    unittest.TestCase						):





					"""simple docstring"""






					@slow
					def 	_lowercase					( self					:  int	):
						snake_case__			:				int       =  TFConvBertModel.from_pretrained("YituTech/conv-bert-base"	)
						snake_case__			:				int       =  tf.constant([[0, 1, 2, 3, 4, 5]]	)
						snake_case__			:				str       =  model(__A	)[0]

						snake_case__			:				int       =  [1, 6, 7_6_8]
						self.assertEqual(output.shape							,		__A	)

						snake_case__			:				List[Any]       =  tf.constant(
						    [
						        [
						            [-0.0_3_4_7_5_4_9_3, -0.4_6_8_6_0_3_4, -0.3_0_6_3_8_8_3_2],
						            [0.2_2_6_3_7_2_4_8, -0.2_6_9_8_8_6_4_6, -0.7_4_2_3_4_2_4],
						            [0.1_0_3_2_4_8_6_8, -0.4_5_0_1_3_5_0_8, -0.5_8_2_8_0_7_8_4],
						        ]
						    ]	)
						tf.debugging.assert_near(output[:, :3, :3]							,		__A							,		atol=1e-4	)



