

"""simple docstring"""




def 				snake_case_(_UpperCamelCase					)							->     bool:



  """simple docstring"""






  _snake_case						=							set()
  # To detect a back edge, keep track of vertices currently in the recursion stack
  _snake_case						=							set()
  return any(
      node not in visited and depth_first_search(_UpperCamelCase			,	_UpperCamelCase			,	_UpperCamelCase			,	_UpperCamelCase					)
      for node in graph					)



def 				snake_case_(_UpperCamelCase			,	_UpperCamelCase			,	_UpperCamelCase			,	_UpperCamelCase					)							->     bool:



  """simple docstring"""






  visited.add(_UpperCamelCase					)
  rec_stk.add(_UpperCamelCase					)

  for node in graph[vertex]:
    if node not in visited:
      if depth_first_search(_UpperCamelCase			,	_UpperCamelCase			,	_UpperCamelCase			,	_UpperCamelCase					):
        return True
    elif node in rec_stk:
      return True

    # The node needs to be removed from recursion stack before function ends
  rec_stk.remove(_UpperCamelCase					)
  return False


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

 testmod()




import json
import os
import unittest

from transformers import CLIPTokenizer, CLIPTokenizerFast
from transformers.models.clip.tokenization_clip import VOCAB_FILES_NAMES
from transformers.testing_utils import require_ftfy, require_tokenizers

from ...test_tokenization_common import TokenizerTesterMixin



@require_tokenizers
class   lowercase_   (  __lowercase       ,							unittest.TestCase					):
      UpperCamelCase_      :		Union[str, Any]										=    CLIPTokenizer
      UpperCamelCase_      :		Optional[int]										=    CLIPTokenizerFast
      UpperCamelCase_      :		Dict										=    True
      UpperCamelCase_      :		Union[str, Any]										=    {}
      UpperCamelCase_      :		Optional[Any]										=    False



      def 						UpperCamelCase_		(      self				:    Union[str, Any]		)   ->					Dict:
        super().setUp()

        # fmt: off
        _snake_case						=							['''l''', '''o''', '''w''', '''e''', '''r''', '''s''', '''t''', '''i''', '''d''', '''n''', '''lo''', '''l</w>''', '''w</w>''', '''r</w>''', '''t</w>''', '''low</w>''', '''er</w>''', '''lowest</w>''', '''newer</w>''', '''wider''', '''<unk>''', '''<|startoftext|>''', '''<|endoftext|>''']
        # fmt: on
        _snake_case						=							dict(zip(A__      , range(len(A__		)		)		)		)
        _snake_case						=							['''#version: 0.2''', '''l o''', '''lo w</w>''', '''e r</w>''']
        _snake_case						=							{'''unk_token''': '''<unk>'''}

        _snake_case						=							os.path.join(self.tmpdirname      , VOCAB_FILES_NAMES['''vocab_file''']		)
        _snake_case						=							os.path.join(self.tmpdirname      , VOCAB_FILES_NAMES['''merges_file''']		)
        with open(self.vocab_file      , '''w'''      , encoding='''utf-8'''		) as fp:
          fp.write(json.dumps(A__		) + '''\n'''		)
        with open(self.merges_file      , '''w'''      , encoding='''utf-8'''		) as fp:
          fp.write('''\n'''.join(A__		)		)



      def 						UpperCamelCase_		(      self				:    List[Any]      , **A__				:    int		)   ->					Union[str, Any]:
        kwargs.update(self.special_tokens_map		)
        return CLIPTokenizer.from_pretrained(self.tmpdirname      , **A__		)



      def 						UpperCamelCase_		(      self				:    Any      , **A__				:    Tuple		)   ->					Optional[Any]:
        kwargs.update(self.special_tokens_map		)
        return CLIPTokenizerFast.from_pretrained(self.tmpdirname      , **A__		)



      def 						UpperCamelCase_		(      self				:    Optional[Any]      , A__				:    str		)   ->					str:
        _snake_case						=							'''lower newer'''
        _snake_case						=							'''lower newer'''
        return input_text, output_text



      def 						UpperCamelCase_		(      self				:    Union[str, Any]		)   ->					Optional[int]:
        _snake_case						=							CLIPTokenizer(self.vocab_file      , self.merges_file      , **self.special_tokens_map		)
        _snake_case						=							'''lower newer'''
        _snake_case						=							['''lo''', '''w''', '''er</w>''', '''n''', '''e''', '''w''', '''er</w>''']
        _snake_case						=							tokenizer.tokenize(A__		)
        self.assertListEqual(A__      , A__		)

        _snake_case						=							tokens + [tokenizer.unk_token]
        _snake_case						=							[10, 2, 16, 9, 3, 2, 16, 20]
        self.assertListEqual(tokenizer.convert_tokens_to_ids(A__		)      , A__		)



      @require_ftfy
      def 						UpperCamelCase_		(      self				:    Any		)   ->					Optional[int]:
        for tokenizer, pretrained_name, kwargs in self.tokenizers_list:
          with self.subTest(f"""{tokenizer.__class__.__name__} ({pretrained_name})"""		):
            _snake_case						=							self.tokenizer_class.from_pretrained(A__      , **A__		)
            _snake_case						=							self.rust_tokenizer_class.from_pretrained(A__      , **A__		)

            _snake_case						=							'''A\n\'ll 11p223RF☆ho!!to?\'d\'d\'\'d of a cat to-$\'\'d.'''
            _snake_case						=							tokenizer_s.tokenize(A__		)
            _snake_case						=							tokenizer_r.tokenize(A__		)

            self.assertListEqual(A__      , A__		)

            # Test that the tokenization is identical on an example containing a character (Latin Small Letter A
            # with Tilde) encoded in 2 different ways
            _snake_case						=							'''xa\u0303y''' + ''' ''' + '''x\xe3y'''
            _snake_case						=							tokenizer_s.tokenize(A__		)
            _snake_case						=							tokenizer_r.tokenize(A__		)

            self.assertListEqual(A__      , A__		)

            # Test that the tokenization is identical on unicode of space type
            _snake_case						=							[
                '''\u0009''',  # (horizontal tab, '\t')
                '''\u000B''',  # (vertical tab)
                '''\u000C''',  # (form feed)
                '''\u0020''',  # (space, ' ')
                '''\u200E''',  # (left-to-right mark):w
                '''\u200F''',  # (right-to-left mark)
            ]
            for unicode_seq in spaces_unicodes:
              _snake_case						=							tokenizer_s.tokenize(A__		)
              _snake_case						=							tokenizer_r.tokenize(A__		)

              self.assertListEqual(A__      , A__		)

            # Test that the tokenization is identical on unicode of line break type
            _snake_case						=							[
                '''\u000A''',  # (line feed, '\n')
                '''\r\n''',  # (carriage return and line feed, '\r\n')
                '''\u000D''',  # (carriage return, '\r')
                '''\r''',  # (carriage return, '\r')
                '''\u000D''',  # (carriage return, '\r')
                '''\u2028''',  # (line separator)
                '''\u2029''',  # (paragraph separator)
                # "\u0085", # (next line)
            ]

            # The tokenization is not identical for the character "\u0085" (next line). The slow version using ftfy transforms
            # it into the Horizontal Ellipsis character "…" ("\u2026") while the fast version transforms it into a
            # space (and thus into an empty list).

            for unicode_seq in line_break_unicodes:
              _snake_case						=							tokenizer_s.tokenize(A__		)
              _snake_case						=							tokenizer_r.tokenize(A__		)

              self.assertListEqual(A__      , A__		)



      def 						UpperCamelCase_		(      self				:    List[Any]		)   ->					Optional[Any]:
        # Test which aims to verify that the offsets are well adapted to the argument `add_prefix_space`
        for tokenizer, pretrained_name, kwargs in self.tokenizers_list:
          with self.subTest(f"""{tokenizer.__class__.__name__} ({pretrained_name})"""		):
            _snake_case						=							'''hello'''  # `hello` is a token in the vocabulary of `pretrained_name`
            _snake_case						=							f"""{text_of_1_token} {text_of_1_token}"""

            _snake_case						=							self.rust_tokenizer_class.from_pretrained(
                A__      , use_fast=A__      , )
            _snake_case						=							tokenizer_r(A__      , return_offsets_mapping=A__      , add_special_tokens=A__		)
            self.assertEqual(encoding.offset_mapping[0]      , (0, len(A__		))		)
            self.assertEqual(
                encoding.offset_mapping[1]      , (len(A__		) + 1, len(A__		) + 1 + len(A__		))      , )

            _snake_case						=							f""" {text}"""

            _snake_case						=							self.rust_tokenizer_class.from_pretrained(
                A__      , use_fast=A__      , )
            _snake_case						=							tokenizer_r(A__      , return_offsets_mapping=A__      , add_special_tokens=A__		)
            self.assertEqual(encoding.offset_mapping[0]      , (1, 1 + len(A__		))		)
            self.assertEqual(
                encoding.offset_mapping[1]      , (1 + len(A__		) + 1, 1 + len(A__		) + 1 + len(A__		))      , )



      def 						UpperCamelCase_		(      self				:    Union[str, Any]		)   ->					Optional[Any]:
        # Test related to the breaking change introduced in transformers v4.17.0
        # We need to check that an error in raised when the user try to load a previous version of the tokenizer.
        with self.assertRaises(A__		) as context:
          self.rust_tokenizer_class.from_pretrained('''robot-test/old-clip-tokenizer'''		)

        self.assertTrue(
            context.exception.args[0].startswith(
                '''The `backend_tokenizer` provided does not match the expected format.'''		)		)



      @require_ftfy
      def 						UpperCamelCase_		(      self				:    Dict		)   ->					Union[str, Any]:
        super().test_tokenization_python_rust_equals()







      def 						UpperCamelCase_		(      self				:    str		)   ->					Optional[int]:
        # CLIP always lower cases letters
        pass

