
"""simple docstring"""






def 						_snake_case       (	)  ->				Optional[Any]:


			'''simple docstring'''





			return [list(range(1_0_0_0 - i      ,     -1_0_0_0 - i      ,     -1		)		) for i in range(1_0_0_0		)]


__UpperCAmelCase       =  generate_large_matrix()
__UpperCAmelCase       =  (
    [[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 						_snake_case       (	lowercase__		:  Tuple		)  ->				Any:


			'''simple docstring'''





			assert all(row == sorted(_lowercase      ,     reverse=_lowercase		) for row in grid		)
			assert all(list(_lowercase		) == sorted(_lowercase      ,     reverse=_lowercase		) for col in zip(*_lowercase		)		)






def 						_snake_case       (	lowercase__		:  Optional[Any]		)  ->				Tuple:


			'''simple docstring'''





			lowerCAmelCase_    :Dict			     =  0
			lowerCAmelCase_    :Optional[Any]			     =  len(_lowercase		) - 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:
						lowerCAmelCase_    :Any			     =  (left + right) // 2
						lowerCAmelCase_    :Dict			     =  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:
									lowerCAmelCase_    :List[str]			     =  mid + 1
						else:
									lowerCAmelCase_    :Tuple			     =  mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
			return len(_lowercase		)






def 						_snake_case       (	lowercase__		:  Union[str, Any]		)  ->				List[str]:


			'''simple docstring'''





			lowerCAmelCase_    :int			     =  0
			lowerCAmelCase_    :Dict			     =  len(grid[0]		)

			for i in range(len(_lowercase		)		):
						lowerCAmelCase_    :Optional[int]			     =  find_negative_index(grid[i][:bound]		)
						total += bound
			return (len(_lowercase		) * len(grid[0]		)) - total






def 						_snake_case       (	lowercase__		:  Dict		)  ->				List[str]:


			'''simple docstring'''





			return len([number for row in grid for number in row if number < 0]		)






def 						_snake_case       (	lowercase__		:  List[Any]		)  ->				Optional[int]:


			'''simple docstring'''





			lowerCAmelCase_    :Optional[Any]			     =  0
			for row in grid:
						for i, number in enumerate(_lowercase		):
									if number < 0:
												total += len(_lowercase		) - i
												break
			return total






def 						_snake_case       (	)  ->				List[str]:


			'''simple docstring'''





			from timeit import timeit

			print("""Running benchmarks"""		)
			lowerCAmelCase_    :Tuple			     =  (
			    '''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
			):
						lowerCAmelCase_    :int			     =  timeit(f"""{func}(grid=grid)"""      ,     setup=_lowercase      ,     number=5_0_0		)
						print(f"""{func}() took {time:0.4f} seconds"""		)


if __name__ == "__main__":
				import doctest

				doctest.testmod()
				benchmark()







import unittest

from transformers import MODEL_FOR_ZERO_SHOT_OBJECT_DETECTION_MAPPING, is_vision_available, pipeline
from transformers.testing_utils import (
    is_pipeline_test,
    nested_simplify,
    require_tf,
    require_torch,
    require_vision,
    slow,
)

from .test_pipelines_common import ANY


if is_vision_available():
					from PIL import Image
else:





					class 					lowercase__						:


											@staticmethod
											def        __A       (       *UpperCamelCase__	:				Union[str, Any]    ,		**UpperCamelCase__	:				Optional[Any]						):





																	'''simple docstring'''





																	pass





@is_pipeline_test
@require_vision
@require_torch
class 					lowercase__						(   unittest.TestCase):
						UpperCamelCase_     =		MODEL_FOR_ZERO_SHOT_OBJECT_DETECTION_MAPPING


						def        __A       (       self	:				Union[str, Any]    ,		UpperCamelCase__	:				Tuple    ,		UpperCamelCase__	:				List[Any]    ,		UpperCamelCase__	:				int						):





												'''simple docstring'''





												SCREAMING_SNAKE_CASE							:    List[Any]							=							pipeline(
												    '''zero-shot-object-detection'''    ,		model='''hf-internal-testing/tiny-random-owlvit-object-detection'''						)

												SCREAMING_SNAKE_CASE							:    List[str]							=							[
												    {
												        '''image''': '''./tests/fixtures/tests_samples/COCO/000000039769.png''',
												        '''candidate_labels''': ['''cat''', '''remote''', '''couch'''],
												    }
												]
												return object_detector, examples


						def        __A       (       self	:				Union[str, Any]    ,		UpperCamelCase__	:				Any    ,		UpperCamelCase__	:				Optional[Any]						):





												'''simple docstring'''





												SCREAMING_SNAKE_CASE							:    Optional[int]							=							object_detector(examples[0]    ,		threshold=0.0						)

												SCREAMING_SNAKE_CASE							:    Tuple							=							len(UpperCamelCase__						)
												self.assertGreater(UpperCamelCase__    ,		0						)
												self.assertEqual(
												    UpperCamelCase__    ,		[
												        {
												            '''score''': ANY(UpperCamelCase__						),
												            '''label''': ANY(UpperCamelCase__						),
												            '''box''': {'''xmin''': ANY(UpperCamelCase__						), '''ymin''': ANY(UpperCamelCase__						), '''xmax''': ANY(UpperCamelCase__						), '''ymax''': ANY(UpperCamelCase__						)},
												        }
												        for i in range(UpperCamelCase__						)
												    ]    ,		)


						@require_tf
						@unittest.skip('''Zero Shot Object Detection not implemented in TF'''						)
						def        __A       (       self	:				Optional[Any]						):





												'''simple docstring'''





												pass


						@require_torch
						def        __A       (       self	:				Dict						):





												'''simple docstring'''





												SCREAMING_SNAKE_CASE							:    Tuple							=							pipeline(
												    '''zero-shot-object-detection'''    ,		model='''hf-internal-testing/tiny-random-owlvit-object-detection'''						)

												SCREAMING_SNAKE_CASE							:    str							=							object_detector(
												    '''./tests/fixtures/tests_samples/COCO/000000039769.png'''    ,		candidate_labels=['''cat''', '''remote''', '''couch''']    ,		threshold=0.64    ,		)

												self.assertEqual(
												    nested_simplify(UpperCamelCase__    ,		decimals=4						)    ,		[
												        {'''score''': 0.7235, '''label''': '''cat''', '''box''': {'''xmin''': 204, '''ymin''': 167, '''xmax''': 232, '''ymax''': 190}},
												        {'''score''': 0.7218, '''label''': '''remote''', '''box''': {'''xmin''': 204, '''ymin''': 167, '''xmax''': 232, '''ymax''': 190}},
												        {'''score''': 0.7184, '''label''': '''couch''', '''box''': {'''xmin''': 204, '''ymin''': 167, '''xmax''': 232, '''ymax''': 190}},
												        {'''score''': 0.6748, '''label''': '''remote''', '''box''': {'''xmin''': 571, '''ymin''': 83, '''xmax''': 598, '''ymax''': 103}},
												        {'''score''': 0.6656, '''label''': '''cat''', '''box''': {'''xmin''': 571, '''ymin''': 83, '''xmax''': 598, '''ymax''': 103}},
												        {'''score''': 0.6614, '''label''': '''couch''', '''box''': {'''xmin''': 571, '''ymin''': 83, '''xmax''': 598, '''ymax''': 103}},
												        {'''score''': 0.6456, '''label''': '''remote''', '''box''': {'''xmin''': 494, '''ymin''': 105, '''xmax''': 521, '''ymax''': 127}},
												        {'''score''': 0.642, '''label''': '''remote''', '''box''': {'''xmin''': 67, '''ymin''': 274, '''xmax''': 93, '''ymax''': 297}},
												        {'''score''': 0.6419, '''label''': '''cat''', '''box''': {'''xmin''': 494, '''ymin''': 105, '''xmax''': 521, '''ymax''': 127}},
												    ]    ,		)

												SCREAMING_SNAKE_CASE							:    str							=							object_detector(
												    [
												        {
												            '''image''': '''./tests/fixtures/tests_samples/COCO/000000039769.png''',
												            '''candidate_labels''': ['''cat''', '''remote''', '''couch'''],
												        }
												    ]    ,		threshold=0.64    ,		)

												self.assertEqual(
												    nested_simplify(UpperCamelCase__    ,		decimals=4						)    ,		[
												        [
												            {'''score''': 0.7235, '''label''': '''cat''', '''box''': {'''xmin''': 204, '''ymin''': 167, '''xmax''': 232, '''ymax''': 190}},
												            {'''score''': 0.7218, '''label''': '''remote''', '''box''': {'''xmin''': 204, '''ymin''': 167, '''xmax''': 232, '''ymax''': 190}},
												            {'''score''': 0.7184, '''label''': '''couch''', '''box''': {'''xmin''': 204, '''ymin''': 167, '''xmax''': 232, '''ymax''': 190}},
												            {'''score''': 0.6748, '''label''': '''remote''', '''box''': {'''xmin''': 571, '''ymin''': 83, '''xmax''': 598, '''ymax''': 103}},
												            {'''score''': 0.6656, '''label''': '''cat''', '''box''': {'''xmin''': 571, '''ymin''': 83, '''xmax''': 598, '''ymax''': 103}},
												            {'''score''': 0.6614, '''label''': '''couch''', '''box''': {'''xmin''': 571, '''ymin''': 83, '''xmax''': 598, '''ymax''': 103}},
												            {'''score''': 0.6456, '''label''': '''remote''', '''box''': {'''xmin''': 494, '''ymin''': 105, '''xmax''': 521, '''ymax''': 127}},
												            {'''score''': 0.642, '''label''': '''remote''', '''box''': {'''xmin''': 67, '''ymin''': 274, '''xmax''': 93, '''ymax''': 297}},
												            {'''score''': 0.6419, '''label''': '''cat''', '''box''': {'''xmin''': 494, '''ymin''': 105, '''xmax''': 521, '''ymax''': 127}},
												        ]
												    ]    ,		)


						@require_torch
						@slow
						def        __A       (       self	:				Tuple						):





												'''simple docstring'''





												SCREAMING_SNAKE_CASE							:    int							=							pipeline('''zero-shot-object-detection'''						)

												SCREAMING_SNAKE_CASE							:    Optional[int]							=							object_detector(
												    '''http://images.cocodataset.org/val2017/000000039769.jpg'''    ,		candidate_labels=['''cat''', '''remote''', '''couch''']    ,		)
												self.assertEqual(
												    nested_simplify(UpperCamelCase__    ,		decimals=4						)    ,		[
												        {'''score''': 0.2868, '''label''': '''cat''', '''box''': {'''xmin''': 324, '''ymin''': 20, '''xmax''': 640, '''ymax''': 373}},
												        {'''score''': 0.277, '''label''': '''remote''', '''box''': {'''xmin''': 40, '''ymin''': 72, '''xmax''': 177, '''ymax''': 115}},
												        {'''score''': 0.2537, '''label''': '''cat''', '''box''': {'''xmin''': 1, '''ymin''': 55, '''xmax''': 315, '''ymax''': 472}},
												        {'''score''': 0.1474, '''label''': '''remote''', '''box''': {'''xmin''': 335, '''ymin''': 74, '''xmax''': 371, '''ymax''': 187}},
												        {'''score''': 0.1208, '''label''': '''couch''', '''box''': {'''xmin''': 4, '''ymin''': 0, '''xmax''': 642, '''ymax''': 476}},
												    ]    ,		)

												SCREAMING_SNAKE_CASE							:    int							=							object_detector(
												    [
												        {
												            '''image''': '''http://images.cocodataset.org/val2017/000000039769.jpg''',
												            '''candidate_labels''': ['''cat''', '''remote''', '''couch'''],
												        },
												        {
												            '''image''': '''http://images.cocodataset.org/val2017/000000039769.jpg''',
												            '''candidate_labels''': ['''cat''', '''remote''', '''couch'''],
												        },
												    ]    ,		)
												self.assertEqual(
												    nested_simplify(UpperCamelCase__    ,		decimals=4						)    ,		[
												        [
												            {'''score''': 0.2868, '''label''': '''cat''', '''box''': {'''xmin''': 324, '''ymin''': 20, '''xmax''': 640, '''ymax''': 373}},
												            {'''score''': 0.277, '''label''': '''remote''', '''box''': {'''xmin''': 40, '''ymin''': 72, '''xmax''': 177, '''ymax''': 115}},
												            {'''score''': 0.2537, '''label''': '''cat''', '''box''': {'''xmin''': 1, '''ymin''': 55, '''xmax''': 315, '''ymax''': 472}},
												            {'''score''': 0.1474, '''label''': '''remote''', '''box''': {'''xmin''': 335, '''ymin''': 74, '''xmax''': 371, '''ymax''': 187}},
												            {'''score''': 0.1208, '''label''': '''couch''', '''box''': {'''xmin''': 4, '''ymin''': 0, '''xmax''': 642, '''ymax''': 476}},
												        ],
												        [
												            {'''score''': 0.2868, '''label''': '''cat''', '''box''': {'''xmin''': 324, '''ymin''': 20, '''xmax''': 640, '''ymax''': 373}},
												            {'''score''': 0.277, '''label''': '''remote''', '''box''': {'''xmin''': 40, '''ymin''': 72, '''xmax''': 177, '''ymax''': 115}},
												            {'''score''': 0.2537, '''label''': '''cat''', '''box''': {'''xmin''': 1, '''ymin''': 55, '''xmax''': 315, '''ymax''': 472}},
												            {'''score''': 0.1474, '''label''': '''remote''', '''box''': {'''xmin''': 335, '''ymin''': 74, '''xmax''': 371, '''ymax''': 187}},
												            {'''score''': 0.1208, '''label''': '''couch''', '''box''': {'''xmin''': 4, '''ymin''': 0, '''xmax''': 642, '''ymax''': 476}},
												        ],
												    ]    ,		)


						@require_tf
						@unittest.skip('''Zero Shot Object Detection not implemented in TF'''						)
						def        __A       (       self	:				str						):





												'''simple docstring'''





												pass


						@require_torch
						@slow
						def        __A       (       self	:				List[str]						):





												'''simple docstring'''





												SCREAMING_SNAKE_CASE							:    Tuple							=							0.2
												SCREAMING_SNAKE_CASE							:    Optional[int]							=							pipeline('''zero-shot-object-detection'''						)

												SCREAMING_SNAKE_CASE							:    Dict							=							object_detector(
												    '''http://images.cocodataset.org/val2017/000000039769.jpg'''    ,		candidate_labels=['''cat''', '''remote''', '''couch''']    ,		threshold=UpperCamelCase__    ,		)
												self.assertEqual(
												    nested_simplify(UpperCamelCase__    ,		decimals=4						)    ,		[
												        {'''score''': 0.2868, '''label''': '''cat''', '''box''': {'''xmin''': 324, '''ymin''': 20, '''xmax''': 640, '''ymax''': 373}},
												        {'''score''': 0.277, '''label''': '''remote''', '''box''': {'''xmin''': 40, '''ymin''': 72, '''xmax''': 177, '''ymax''': 115}},
												        {'''score''': 0.2537, '''label''': '''cat''', '''box''': {'''xmin''': 1, '''ymin''': 55, '''xmax''': 315, '''ymax''': 472}},
												    ]    ,		)



						@require_torch
						@slow
						def        __A       (       self	:				List[Any]						):





												'''simple docstring'''





												SCREAMING_SNAKE_CASE							:    List[str]							=							2
												SCREAMING_SNAKE_CASE							:    Optional[Any]							=							pipeline('''zero-shot-object-detection'''						)

												SCREAMING_SNAKE_CASE							:    List[str]							=							object_detector(
												    '''http://images.cocodataset.org/val2017/000000039769.jpg'''    ,		candidate_labels=['''cat''', '''remote''', '''couch''']    ,		top_k=UpperCamelCase__    ,		)
												self.assertEqual(
												    nested_simplify(UpperCamelCase__    ,		decimals=4						)    ,		[
												        {'''score''': 0.2868, '''label''': '''cat''', '''box''': {'''xmin''': 324, '''ymin''': 20, '''xmax''': 640, '''ymax''': 373}},
												        {'''score''': 0.277, '''label''': '''remote''', '''box''': {'''xmin''': 40, '''ymin''': 72, '''xmax''': 177, '''ymax''': 115}},
												    ]    ,		)





