






'''simple docstring'''
import inspect
import tempfile
from collections import OrderedDict, UserDict
from collections.abc import MutableMapping
from contextlib import ExitStack, contextmanager
from dataclasses import fields
from enum import Enum
from typing import Any, ContextManager, List, Tuple

import numpy as np

from .import_utils import is_flax_available, is_tf_available, is_torch_available, is_torch_fx_proxy


if is_flax_available():
						import jax.numpy as jnp


class  _snake_case (					snake_case       ):

					"""simple docstring"""





					def __get__(  self ,			UpperCAmelCase__ ,			UpperCAmelCase__=None  )   ->						Any:







										if obj is None:
															return self
										if self.fget is None:
															raise AttributeError('unreadable attribute'  )
										a_						= '__cached_' + self.fget.__name__
										a_						= getattr(UpperCAmelCase__ ,			UpperCAmelCase__ ,			UpperCAmelCase__  )
										if cached is None:
															a_						= self.fget(UpperCAmelCase__  )
															setattr(UpperCAmelCase__ ,			UpperCAmelCase__ ,			UpperCAmelCase__  )
										return cached



def 				a						( _UpperCAmelCase			)					->					Any:






					"""simple docstring"""







					a_						= val.lower()
					if val in {"y", "yes", "t", "true", "on", "1"}:
										return 1
					if val in {"n", "no", "f", "false", "off", "0"}:
										return 0
					raise ValueError(F'''invalid truth value {val!r}'''			)

def 				a						( _UpperCAmelCase			)					->					Any:






					"""simple docstring"""







					if is_torch_fx_proxy(__lowerCamelCase			):
										return True
					if is_torch_available():
										import torch

										if isinstance(__lowerCamelCase       ,	torch.Tensor			):
															return True
					if is_tf_available():
										import tensorflow as tf

										if isinstance(__lowerCamelCase       ,	tf.Tensor			):
															return True

					if is_flax_available():
										import jax.numpy as jnp
										from jax.core import Tracer

										if isinstance(__lowerCamelCase       ,	(jnp.ndarray, Tracer)			):
															return True

					return isinstance(__lowerCamelCase       ,	np.ndarray			)

def 				a						( _UpperCAmelCase			)					->					Dict:






					"""simple docstring"""







					return isinstance(__lowerCamelCase       ,	np.ndarray			)

def 				a						( _UpperCAmelCase			)					->					str:






					"""simple docstring"""







					return _is_numpy(__lowerCamelCase			)

def 				a						( _UpperCAmelCase			)					->					Tuple:






					"""simple docstring"""







					import torch

					return isinstance(__lowerCamelCase       ,	torch.Tensor			)

def 				a						( _UpperCAmelCase			)					->					List[Any]:






					"""simple docstring"""







					return False if not is_torch_available() else _is_torch(__lowerCamelCase			)

def 				a						( _UpperCAmelCase			)					->					int:






					"""simple docstring"""







					import torch

					return isinstance(__lowerCamelCase       ,	torch.device			)

def 				a						( _UpperCAmelCase			)					->					Tuple:






					"""simple docstring"""







					return False if not is_torch_available() else _is_torch_device(__lowerCamelCase			)

def 				a						( _UpperCAmelCase			)					->					Optional[int]:






					"""simple docstring"""







					import torch

					if isinstance(__lowerCamelCase       ,	__lowerCamelCase			):
										if hasattr(__lowerCamelCase       ,	__lowerCamelCase			):
															a_						= getattr(__lowerCamelCase       ,	__lowerCamelCase			)
										else:
															return False
					return isinstance(__lowerCamelCase       ,	torch.dtype			)

def 				a						( _UpperCAmelCase			)					->					int:






					"""simple docstring"""







					return False if not is_torch_available() else _is_torch_dtype(__lowerCamelCase			)

def 				a						( _UpperCAmelCase			)					->					int:






					"""simple docstring"""







					import tensorflow as tf

					return isinstance(__lowerCamelCase       ,	tf.Tensor			)

def 				a						( _UpperCAmelCase			)					->					Optional[int]:






					"""simple docstring"""







					return False if not is_tf_available() else _is_tensorflow(__lowerCamelCase			)

def 				a						( _UpperCAmelCase			)					->					Optional[Any]:






					"""simple docstring"""







					import tensorflow as tf

					# the `is_symbolic_tensor` predicate is only available starting with TF 2.14
					if hasattr(__lowerCamelCase       ,	'is_symbolic_tensor'			):
										return tf.is_symbolic_tensor(__lowerCamelCase			)
					return type(__lowerCamelCase			) == tf.Tensor

def 				a						( _UpperCAmelCase			)					->					Union[str, Any]:






					"""simple docstring"""







					return False if not is_tf_available() else _is_tf_symbolic_tensor(__lowerCamelCase			)

def 				a						( _UpperCAmelCase			)					->					Union[str, Any]:






					"""simple docstring"""







					import jax.numpy as jnp  # noqa: F811

					return isinstance(__lowerCamelCase       ,	jnp.ndarray			)

def 				a						( _UpperCAmelCase			)					->					List[str]:






					"""simple docstring"""







					return False if not is_flax_available() else _is_jax(__lowerCamelCase			)

def 				a						( _UpperCAmelCase			)					->					Any:






					"""simple docstring"""







					if isinstance(__lowerCamelCase       ,	(dict, UserDict)			):
										return {k: to_py_obj(__lowerCamelCase			) for k, v in obj.items()}
					elif isinstance(__lowerCamelCase       ,	(list, tuple)			):
										return [to_py_obj(__lowerCamelCase			) for o in obj]
					elif is_tf_tensor(__lowerCamelCase			):
										return obj.numpy().tolist()
					elif is_torch_tensor(__lowerCamelCase			):
										return obj.detach().cpu().tolist()
					elif is_jax_tensor(__lowerCamelCase			):
										return np.asarray(__lowerCamelCase			).tolist()
					elif isinstance(__lowerCamelCase       ,	(np.ndarray, np.number)			):  # tolist also works on 0d np arrays
										return obj.tolist()
					else:
										return obj

def 				a						( _UpperCAmelCase			)					->					int:






					"""simple docstring"""







					if isinstance(__lowerCamelCase       ,	(dict, UserDict)			):
										return {k: to_numpy(__lowerCamelCase			) for k, v in obj.items()}
					elif isinstance(__lowerCamelCase       ,	(list, tuple)			):
										return np.array(__lowerCamelCase			)
					elif is_tf_tensor(__lowerCamelCase			):
										return obj.numpy()
					elif is_torch_tensor(__lowerCamelCase			):
										return obj.detach().cpu().numpy()
					elif is_jax_tensor(__lowerCamelCase			):
										return np.asarray(__lowerCamelCase			)
					else:
										return obj


class  _snake_case (					snake_case       ):

					"""simple docstring"""





					def 			__SCREAMING_SNAKE_CASE			(  self  )   ->						int:
										a_						= fields(self  )

										# Safety and consistency checks
										if not len(UpperCAmelCase__  ):
															raise ValueError(F'''{self.__class__.__name__} has no fields.'''  )
										if not all(field.default is None for field in class_fields[1:]  ):
															raise ValueError(F'''{self.__class__.__name__} should not have more than one required field.'''  )

										a_						= getattr(self ,			class_fields[0].name  )
										a_						= all(getattr(self ,			field.name  ) is None for field in class_fields[1:]  )

										if other_fields_are_none and not is_tensor(UpperCAmelCase__  ):
															if isinstance(UpperCAmelCase__ ,			UpperCAmelCase__  ):
																				a_						= first_field.items()
																				a_						= True
															else:
																				try:
																									a_						= iter(UpperCAmelCase__  )
																									a_						= True
																				except TypeError:
																									a_						= False

            # if we provided an iterator as first field and the iterator is a (key, value) iterator
            # set the associated fields
															if first_field_iterator:
																				for idx, element in enumerate(UpperCAmelCase__  ):
																									if (
																									    not isinstance(UpperCAmelCase__ ,			(list, tuple)  )
																									    or not len(UpperCAmelCase__  ) == 2
																									    or not isinstance(element[0] ,			UpperCAmelCase__  )
																									):
																														if idx == 0:
																																			# If we do not have an iterator of key/values, set it as attribute
																																			a_						= first_field
																														else:
																																			# If we have a mixed iterator, raise an error
																																			raise ValueError(
																																			    F'''Cannot set key/value for {element}. It needs to be a tuple (key, value).'''  )
																														break
																									setattr(self ,			element[0] ,			element[1]  )
																									if element[1] is not None:
																														a_						= element[1]
															elif first_field is not None:
																				a_						= first_field
										else:
															for field in class_fields:
																				a_						= getattr(self ,			field.name  )
																				if v is not None:
																									a_						= v




					def __delitem__(  self ,			*UpperCAmelCase__ ,			**UpperCAmelCase__  )   ->						str:
										raise Exception(F'''You cannot use ``__delitem__`` on a {self.__class__.__name__} instance.'''  )




					def 			__SCREAMING_SNAKE_CASE			(  self ,			*UpperCAmelCase__ ,			**UpperCAmelCase__  )   ->						str:
										raise Exception(F'''You cannot use ``setdefault`` on a {self.__class__.__name__} instance.'''  )




					def 			__SCREAMING_SNAKE_CASE			(  self ,			*UpperCAmelCase__ ,			**UpperCAmelCase__  )   ->						str:
										raise Exception(F'''You cannot use ``pop`` on a {self.__class__.__name__} instance.'''  )




					def 			__SCREAMING_SNAKE_CASE			(  self ,			*UpperCAmelCase__ ,			**UpperCAmelCase__  )   ->						int:
										raise Exception(F'''You cannot use ``update`` on a {self.__class__.__name__} instance.'''  )




					def __getitem__(  self ,			UpperCAmelCase__  )   ->						Tuple:







										if isinstance(UpperCAmelCase__ ,			UpperCAmelCase__  ):
															a_						= dict(self.items()  )
															return inner_dict[k]
										else:
															return self.to_tuple()[k]




					def __setattr__(  self ,			UpperCAmelCase__ ,			UpperCAmelCase__  )   ->						int:







										if name in self.keys() and value is not None:
															# Don't call self.__setitem__ to avoid recursion errors
															super().__setitem__(UpperCAmelCase__ ,			UpperCAmelCase__  )
										super().__setattr__(UpperCAmelCase__ ,			UpperCAmelCase__  )




					def __setitem__(  self ,			UpperCAmelCase__ ,			UpperCAmelCase__  )   ->						Dict:
										super().__setitem__(UpperCAmelCase__ ,			UpperCAmelCase__  )
										# Don't call self.__setattr__ to avoid recursion errors
										super().__setattr__(UpperCAmelCase__ ,			UpperCAmelCase__  )




					def 			__SCREAMING_SNAKE_CASE			(  self  )   ->						Tuple:
										return tuple(self[k] for k in self.keys()  )



class  _snake_case (					snake_case  ,       snake_case       ):

					"""simple docstring"""





					@classmethod
					def 			__SCREAMING_SNAKE_CASE			(  cls ,			UpperCAmelCase__  )   ->						List[str]:
										raise ValueError(
										    F'''{value} is not a valid {cls.__name__}, please select one of {list(cls._valueamember_map_.keys()  )}'''  )



class  _snake_case (					snake_case       ):

					"""simple docstring"""





					_UpperCamelCase					=   "longest"
					_UpperCamelCase					=   "max_length"
					_UpperCamelCase					=   "do_not_pad"



class  _snake_case (					snake_case       ):

					"""simple docstring"""





					_UpperCamelCase					=   "pt"
					_UpperCamelCase					=   "tf"
					_UpperCamelCase					=   "np"
					_UpperCamelCase					=   "jax"



class  _snake_case :

					"""simple docstring"""





					def __init__(  self ,			UpperCAmelCase__  )   ->						Optional[int]:
										a_						= context_managers
										a_						= ExitStack()




					def __enter__(  self  )   ->						str:







										for context_manager in self.context_managers:
															self.stack.enter_context(UpperCAmelCase__  )




					def __exit__(  self ,			*UpperCAmelCase__ ,			**UpperCAmelCase__  )   ->						Any:
										self.stack.__exit__(*UpperCAmelCase__ ,			**UpperCAmelCase__  )



def 				a						( _UpperCAmelCase			)					->					List[str]:






					"""simple docstring"""







					a_						= infer_framework(__lowerCamelCase			)
					if framework == "tf":
										a_						= inspect.signature(model_class.call			)  # TensorFlow models
					elif framework == "pt":
										a_						= inspect.signature(model_class.forward			)  # PyTorch models
					else:
										a_						= inspect.signature(model_class.__call__			)  # Flax models

					for p in signature.parameters:
										if p == "return_loss" and signature.parameters[p].default is True:
															return True

					return False

def 				a						( _UpperCAmelCase			)					->					Union[str, Any]:






					"""simple docstring"""







					a_						= model_class.__name__
					a_						= infer_framework(__lowerCamelCase			)
					if framework == "tf":
										a_						= inspect.signature(model_class.call			)  # TensorFlow models
					elif framework == "pt":
										a_						= inspect.signature(model_class.forward			)  # PyTorch models
					else:
										a_						= inspect.signature(model_class.__call__			)  # Flax models

					if "QuestionAnswering" in model_name:
										return [p for p in signature.parameters if "label" in p or p in ("start_positions", "end_positions")]
					else:
										return [p for p in signature.parameters if "label" in p]

def 				a						( _UpperCAmelCase       ,	_UpperCAmelCase = ""       ,	_UpperCAmelCase = "."			)					->					List[Any]:






					"""simple docstring"""







					def _flatten_dict(_UpperCAmelCase       ,	_UpperCAmelCase=""       ,	_UpperCAmelCase="."			):
										for k, v in d.items():
															a_						= str(__lowerCamelCase			) + delimiter + str(__lowerCamelCase			) if parent_key else k
															if v and isinstance(__lowerCamelCase       ,	__lowerCamelCase			):
																				yield from flatten_dict(__lowerCamelCase       ,	__lowerCamelCase       ,	delimiter=__lowerCamelCase			).items()
															else:
																				yield key, v

					return dict(_flatten_dict(__lowerCamelCase       ,	__lowerCamelCase       ,	__lowerCamelCase			)			)

@contextmanager
def 				a						( _UpperCAmelCase       ,	_UpperCAmelCase = False			)					->					int:






					"""simple docstring"""







					if use_temp_dir:
										with tempfile.TemporaryDirectory() as tmp_dir:
															yield tmp_dir
					else:
										yield working_dir

def 				a						( _UpperCAmelCase       ,	_UpperCAmelCase=None			)					->					List[str]:






					"""simple docstring"""







					if is_numpy_array(__lowerCamelCase			):
										return np.transpose(__lowerCamelCase       ,	axes=__lowerCamelCase			)
					elif is_torch_tensor(__lowerCamelCase			):
										return array.T if axes is None else array.permute(*__lowerCamelCase			)
					elif is_tf_tensor(__lowerCamelCase			):
										import tensorflow as tf

										return tf.transpose(__lowerCamelCase       ,	perm=__lowerCamelCase			)
					elif is_jax_tensor(__lowerCamelCase			):
										return jnp.transpose(__lowerCamelCase       ,	axes=__lowerCamelCase			)
					else:
										raise ValueError(F'''Type not supported for transpose: {type(__lowerCamelCase			)}.'''			)

def 				a						( _UpperCAmelCase       ,	_UpperCAmelCase			)					->					List[str]:






					"""simple docstring"""







					if is_numpy_array(__lowerCamelCase			):
										return np.reshape(__lowerCamelCase       ,	__lowerCamelCase			)
					elif is_torch_tensor(__lowerCamelCase			):
										return array.reshape(*__lowerCamelCase			)
					elif is_tf_tensor(__lowerCamelCase			):
										import tensorflow as tf

										return tf.reshape(__lowerCamelCase       ,	__lowerCamelCase			)
					elif is_jax_tensor(__lowerCamelCase			):
										return jnp.reshape(__lowerCamelCase       ,	__lowerCamelCase			)
					else:
										raise ValueError(F'''Type not supported for reshape: {type(__lowerCamelCase			)}.'''			)

def 				a						( _UpperCAmelCase       ,	_UpperCAmelCase=None			)					->					str:






					"""simple docstring"""







					if is_numpy_array(__lowerCamelCase			):
										return np.squeeze(__lowerCamelCase       ,	axis=__lowerCamelCase			)
					elif is_torch_tensor(__lowerCamelCase			):
										return array.squeeze() if axis is None else array.squeeze(dim=__lowerCamelCase			)
					elif is_tf_tensor(__lowerCamelCase			):
										import tensorflow as tf

										return tf.squeeze(__lowerCamelCase       ,	axis=__lowerCamelCase			)
					elif is_jax_tensor(__lowerCamelCase			):
										return jnp.squeeze(__lowerCamelCase       ,	axis=__lowerCamelCase			)
					else:
										raise ValueError(F'''Type not supported for squeeze: {type(__lowerCamelCase			)}.'''			)

def 				a						( _UpperCAmelCase       ,	_UpperCAmelCase			)					->					str:






					"""simple docstring"""







					if is_numpy_array(__lowerCamelCase			):
										return np.expand_dims(__lowerCamelCase       ,	__lowerCamelCase			)
					elif is_torch_tensor(__lowerCamelCase			):
										return array.unsqueeze(dim=__lowerCamelCase			)
					elif is_tf_tensor(__lowerCamelCase			):
										import tensorflow as tf

										return tf.expand_dims(__lowerCamelCase       ,	axis=__lowerCamelCase			)
					elif is_jax_tensor(__lowerCamelCase			):
										return jnp.expand_dims(__lowerCamelCase       ,	axis=__lowerCamelCase			)
					else:
										raise ValueError(F'''Type not supported for expand_dims: {type(__lowerCamelCase			)}.'''			)

def 				a						( _UpperCAmelCase			)					->					int:






					"""simple docstring"""







					if is_numpy_array(__lowerCamelCase			):
										return np.size(__lowerCamelCase			)
					elif is_torch_tensor(__lowerCamelCase			):
										return array.numel()
					elif is_tf_tensor(__lowerCamelCase			):
										import tensorflow as tf

										return tf.size(__lowerCamelCase			)
					elif is_jax_tensor(__lowerCamelCase			):
										return array.size
					else:
										raise ValueError(F'''Type not supported for expand_dims: {type(__lowerCamelCase			)}.'''			)

def 				a						( _UpperCAmelCase       ,	_UpperCAmelCase			)					->					Optional[Any]:






					"""simple docstring"""







					for key, value in auto_map.items():
										if isinstance(__lowerCamelCase       ,	(tuple, list)			):
															a_						= [F'''{repo_id}--{v}''' if (v is not None and '--' not in v) else v for v in value]
										elif value is not None and "--" not in value:
															a_						= F'''{repo_id}--{value}'''

					return auto_map





def 				a						( _UpperCAmelCase			)					->					Optional[Any]:






					"""simple docstring"""







					for base_class in inspect.getmro(__lowerCamelCase			):
										a_						= base_class.__module__
										a_						= base_class.__name__
										if module.startswith('tensorflow'			) or module.startswith('keras'			) or name == "TFPreTrainedModel":
															return "tf"
										elif module.startswith('torch'			) or name == "PreTrainedModel":
															return "pt"
										elif module.startswith('flax'			) or module.startswith('jax'			) or name == "FlaxPreTrainedModel":
															return "flax"
					else:
										raise TypeError(F'''Could not infer framework from class {model_class}.'''			)







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


__UpperCamelCase   :			str          = generate_large_matrix()
__UpperCamelCase   :			Tuple          = (
    [[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 						__A						(      __lowerCamelCase       ) ->			None:
	assert all(row == sorted(__lowerCamelCase				,     reverse=__lowerCamelCase       ) for row in grid       )
	assert all(list(__lowerCamelCase       ) == sorted(__lowerCamelCase				,     reverse=__lowerCamelCase       ) for col in zip(*__lowerCamelCase       )       )





def 						__A						(      __lowerCamelCase       ) ->			int:
	a									=				0
	a									=				len(__lowerCamelCase       ) - 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:
		a									=				(left + right) // 2
		a									=				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:
			a									=				mid + 1
		else:
			a									=				mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
	return len(__lowerCamelCase       )





def 						__A						(      __lowerCamelCase       ) ->			int:
	a									=				0
	a									=				len(grid[0]       )

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





def 						__A						(      __lowerCamelCase       ) ->			int:
	return len([number for row in grid for number in row if number < 0]       )





def 						__A						(      __lowerCamelCase       ) ->			int:
	a									=				0
	for row in grid:
		for i, number in enumerate(__lowerCamelCase       ):
			if number < 0:
				total += len(__lowerCamelCase       ) - i
				break
	return total





def 						__A						(      ) ->			None:
	from timeit import timeit

	print("""Running benchmarks"""       )
	a									=				(
	    """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
	):
		a									=				timeit(f'{func}(grid=grid)'				,     setup=__lowerCamelCase				,     number=500       )
		print(f'{func}() took {time:0.4f} seconds'       )


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		benchmark()

