"""simple docstring"""





def 				a_     (      ):





       '''simple docstring'''

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


_UpperCamelCase   :						Optional[int]      =    generate_large_matrix()
_UpperCamelCase   :						int      =    (
    [[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  : list[list[int]]     ):





       '''simple docstring'''

       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  : list[int]     ):





       '''simple docstring'''

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





def 				a_     (      _lowerCAmelCase  : list[list[int]]     ):





       '''simple docstring'''

       lowercase__			:		Optional[int]       =	0
       lowercase__			:		Dict       =	len(grid[0]     )

       for i in range(len(_lowerCAmelCase     )     ):
              lowercase__			:		List[Any]       =	find_negative_index(grid[i][:bound]     )
              total += bound
       return (len(_lowerCAmelCase     ) * len(grid[0]     )) - total





def 				a_     (      _lowerCAmelCase  : list[list[int]]     ):





       '''simple docstring'''

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





def 				a_     (      _lowerCAmelCase  : list[list[int]]     ):





       '''simple docstring'''

       lowercase__			:		Tuple       =	0
       for row in grid:
              for i, number in enumerate(_lowerCAmelCase     ):
                     if number < 0:
                            total += len(_lowerCAmelCase     ) - i
                            break
       return total





def 				a_     (      ):





       '''simple docstring'''

       from timeit import timeit

       print('Running benchmarks'     )
       lowercase__			:		Union[str, 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
       ):
              lowercase__			:		Any       =	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()








import json
from typing import List, Optional, Tuple

from tokenizers import normalizers

from ...tokenization_utils_fast import PreTrainedTokenizerFast
from ...utils import logging
from .tokenization_funnel import FunnelTokenizer


UpperCAmelCase	:	int		     =       logging.get_logger(__name__)

UpperCAmelCase	:	Optional[Any]		     =       {"""vocab_file""": """vocab.txt""", """tokenizer_file""": """tokenizer.json"""}

UpperCAmelCase	:	List[Any]		     =       [
    """small""",
    """small-base""",
    """medium""",
    """medium-base""",
    """intermediate""",
    """intermediate-base""",
    """large""",
    """large-base""",
    """xlarge""",
    """xlarge-base""",
]

UpperCAmelCase	:	Optional[int]		     =       {
    """vocab_file""": {
        """funnel-transformer/small""": """https://huggingface.co/funnel-transformer/small/resolve/main/vocab.txt""",
        """funnel-transformer/small-base""": """https://huggingface.co/funnel-transformer/small-base/resolve/main/vocab.txt""",
        """funnel-transformer/medium""": """https://huggingface.co/funnel-transformer/medium/resolve/main/vocab.txt""",
        """funnel-transformer/medium-base""": (
            """https://huggingface.co/funnel-transformer/medium-base/resolve/main/vocab.txt"""
        ),
        """funnel-transformer/intermediate""": (
            """https://huggingface.co/funnel-transformer/intermediate/resolve/main/vocab.txt"""
        ),
        """funnel-transformer/intermediate-base""": (
            """https://huggingface.co/funnel-transformer/intermediate-base/resolve/main/vocab.txt"""
        ),
        """funnel-transformer/large""": """https://huggingface.co/funnel-transformer/large/resolve/main/vocab.txt""",
        """funnel-transformer/large-base""": """https://huggingface.co/funnel-transformer/large-base/resolve/main/vocab.txt""",
        """funnel-transformer/xlarge""": """https://huggingface.co/funnel-transformer/xlarge/resolve/main/vocab.txt""",
        """funnel-transformer/xlarge-base""": (
            """https://huggingface.co/funnel-transformer/xlarge-base/resolve/main/vocab.txt"""
        ),
    },
    """tokenizer_file""": {
        """funnel-transformer/small""": """https://huggingface.co/funnel-transformer/small/resolve/main/tokenizer.json""",
        """funnel-transformer/small-base""": (
            """https://huggingface.co/funnel-transformer/small-base/resolve/main/tokenizer.json"""
        ),
        """funnel-transformer/medium""": """https://huggingface.co/funnel-transformer/medium/resolve/main/tokenizer.json""",
        """funnel-transformer/medium-base""": (
            """https://huggingface.co/funnel-transformer/medium-base/resolve/main/tokenizer.json"""
        ),
        """funnel-transformer/intermediate""": (
            """https://huggingface.co/funnel-transformer/intermediate/resolve/main/tokenizer.json"""
        ),
        """funnel-transformer/intermediate-base""": (
            """https://huggingface.co/funnel-transformer/intermediate-base/resolve/main/tokenizer.json"""
        ),
        """funnel-transformer/large""": """https://huggingface.co/funnel-transformer/large/resolve/main/tokenizer.json""",
        """funnel-transformer/large-base""": (
            """https://huggingface.co/funnel-transformer/large-base/resolve/main/tokenizer.json"""
        ),
        """funnel-transformer/xlarge""": """https://huggingface.co/funnel-transformer/xlarge/resolve/main/tokenizer.json""",
        """funnel-transformer/xlarge-base""": (
            """https://huggingface.co/funnel-transformer/xlarge-base/resolve/main/tokenizer.json"""
        ),
    },
}
UpperCAmelCase	:	Optional[int]		     =       {F"""funnel-transformer/{name}""": 512 for name in _model_names}
UpperCAmelCase	:	Optional[int]		     =       {F"""funnel-transformer/{name}""": {"""do_lower_case""": True} for name in _model_names}







class 				__lowerCAmelCase       (    UpperCamelCase__):
      _lowercase				:					str						=			VOCAB_FILES_NAMES
      _lowercase				:					List[Any]						=			PRETRAINED_VOCAB_FILES_MAP
      _lowercase				:					Dict						=			PRETRAINED_INIT_CONFIGURATION
      _lowercase				:					Union[str, Any]						=			FunnelTokenizer
      _lowercase				:					Any						=			PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
      _lowercase				:					int						=			2







      def __init__(    self		,      lowerCAmelCase__=None		,      lowerCAmelCase__=None		,      lowerCAmelCase__=True		,      lowerCAmelCase__="<unk>"		,      lowerCAmelCase__="<sep>"		,      lowerCAmelCase__="<pad>"		,      lowerCAmelCase__="<cls>"		,      lowerCAmelCase__="<mask>"		,      lowerCAmelCase__="<s>"		,      lowerCAmelCase__="</s>"		,      lowerCAmelCase__=True		,      lowerCAmelCase__=True		,      lowerCAmelCase__=None		,      lowerCAmelCase__="##"		,      **lowerCAmelCase__		,      )   ->						Optional[int]:



        '''simple docstring'''




        super().__init__(
            lowerCAmelCase__		,      tokenizer_file=lowerCAmelCase__		,      do_lower_case=lowerCAmelCase__		,      unk_token=lowerCAmelCase__		,      sep_token=lowerCAmelCase__		,      pad_token=lowerCAmelCase__		,      cls_token=lowerCAmelCase__		,      mask_token=lowerCAmelCase__		,      bos_token=lowerCAmelCase__		,      eos_token=lowerCAmelCase__		,      clean_text=lowerCAmelCase__		,      tokenize_chinese_chars=lowerCAmelCase__		,      strip_accents=lowerCAmelCase__		,      wordpieces_prefix=lowerCAmelCase__		,      **lowerCAmelCase__		,      )

        a__	:					Optional[Any]										=json.loads(self.backend_tokenizer.normalizer.__getstate__()							)
        if (
            normalizer_state.get("lowercase"		,      lowerCAmelCase__							) != do_lower_case
            or normalizer_state.get("strip_accents"		,      lowerCAmelCase__							) != strip_accents
            or normalizer_state.get("handle_chinese_chars"		,      lowerCAmelCase__							) != tokenize_chinese_chars
        ):
          a__	:					List[str]										=getattr(lowerCAmelCase__		,      normalizer_state.pop("type"							)							)
          a__	:					Union[str, Any]										=do_lower_case
          a__	:					Any										=strip_accents
          a__	:					Optional[Any]										=tokenize_chinese_chars
          a__	:					Dict										=normalizer_class(**lowerCAmelCase__							)

        a__	:					Any										=do_lower_case







      def    _lowercase  (    self		,      lowerCAmelCase__		,      lowerCAmelCase__=None							)   ->						str:



        '''simple docstring'''




        a__	:					Dict										=[self.cls_token_id] + token_ids_a + [self.sep_token_id]

        if token_ids_a:
          output += token_ids_a + [self.sep_token_id]

        return output







      def    _lowercase  (    self		,      lowerCAmelCase__		,      lowerCAmelCase__ = None							)   ->						List[int]:



        '''simple docstring'''




        a__	:					Optional[int]										=[self.sep_token_id]
        a__	:					Union[str, Any]										=[self.cls_token_id]
        if token_ids_a is None:
          return len(cls							) * [self.cls_token_type_id] + len(token_ids_a + sep							) * [0]
        return len(cls							) * [self.cls_token_type_id] + len(token_ids_a + sep							) * [0] + len(token_ids_a + sep							) * [1]







      def    _lowercase  (    self		,      lowerCAmelCase__		,      lowerCAmelCase__ = None							)   ->						Tuple[str]:



        '''simple docstring'''




        a__	:					Tuple										=self._tokenizer.model.save(lowerCAmelCase__		,      name=lowerCAmelCase__							)
        return tuple(lowerCAmelCase__							)






