





import os
import pickle
import tempfile
import unittest
from typing import Callable, Optional

import numpy as np

from transformers import (
    BatchEncoding,
    BertTokenizer,
    BertTokenizerFast,
    PreTrainedTokenizer,
    PreTrainedTokenizerFast,
    TensorType,
    TokenSpan,
    is_tokenizers_available,
)
from transformers.models.gpta.tokenization_gpta import GPTaTokenizer
from transformers.testing_utils import CaptureStderr, require_flax, require_tf, require_tokenizers, require_torch, slow


if is_tokenizers_available():
    from tokenizers import Tokenizer
    from tokenizers.models import WordPiece







class 						_lowerCAmelCase(						unittest.TestCase):

  """simple docstring"""







  def 		SCREAMING_SNAKE_CASE__	( self  ,    UpperCAmelCase     )-> List[Any]:
     __A				 =       list(tokenizer_class.max_model_input_sizes.keys()     )
     for model_name in sa_models[:1]:
        __A				 =       tokenizer_class.from_pretrained(snake_case_     )
        self.assertIsNotNone(snake_case_     )
        self.assertIsInstance(snake_case_  ,    snake_case_     )
        self.assertIsInstance(snake_case_  ,    snake_case_     )

        for special_tok in tokenizer.all_special_tokens:
           self.assertIsInstance(snake_case_  ,    snake_case_     )
           __A				 =       tokenizer.convert_tokens_to_ids(snake_case_     )
           self.assertIsInstance(snake_case_  ,    snake_case_     )

  def 		SCREAMING_SNAKE_CASE__	( self  ,    UpperCAmelCase  ,    UpperCAmelCase = None     )-> Optional[Any]:
     __A				 =       pickle.dumps(snake_case_     )
     self.assertIsNotNone(snake_case_     )

     __A				 =       pickle.loads(snake_case_     )

     # Ensure is_fast is correctly restored
     self.assertEqual(be_restored.is_fast  ,    be_original.is_fast     )

     # Ensure encodings are potentially correctly restored
     if be_original.is_fast:
        self.assertIsNotNone(be_restored.encodings     )
     else:
        self.assertIsNone(be_restored.encodings     )

     # Ensure the keys are the same
     for original_v, restored_v in zip(be_original.values()  ,    be_restored.values()     ):
        if equal_op:
           self.assertTrue(equal_op(snake_case_  ,    snake_case_     )     )
        else:
           self.assertEqual(snake_case_  ,    snake_case_     )

  @slow
  def 		SCREAMING_SNAKE_CASE__	( self     )-> Tuple:
     self.check_tokenizer_from_pretrained(snake_case_     )

  def 		SCREAMING_SNAKE_CASE__	( self     )-> Tuple:
     self.assertEqual(TensorType('''tf'''     )  ,    TensorType.TENSORFLOW     )
     self.assertEqual(TensorType('''pt'''     )  ,    TensorType.PYTORCH     )
     self.assertEqual(TensorType('''np'''     )  ,    TensorType.NUMPY     )

  @require_tokenizers
  def 		SCREAMING_SNAKE_CASE__	( self     )-> str:
     import numpy as np

     __A				 =       BertTokenizer.from_pretrained('''bert-base-cased'''     )
     __A				 =       BertTokenizerFast.from_pretrained('''bert-base-cased'''     )

     # Python no tensor
     with self.subTest('''BatchEncoding (Python, return_tensors=None)'''     ):
        self.assert_dump_and_restore(tokenizer_p('''Small example to encode'''     )     )

     with self.subTest('''BatchEncoding (Python, return_tensors=NUMPY)'''     ):
        self.assert_dump_and_restore(
            tokenizer_p('''Small example to encode'''  ,    return_tensors=TensorType.NUMPY     )  ,    np.array_equal     )

     with self.subTest('''BatchEncoding (Rust, return_tensors=None)'''     ):
        self.assert_dump_and_restore(tokenizer_r('''Small example to encode'''     )     )

     with self.subTest('''BatchEncoding (Rust, return_tensors=NUMPY)'''     ):
        self.assert_dump_and_restore(
            tokenizer_r('''Small example to encode'''  ,    return_tensors=TensorType.NUMPY     )  ,    np.array_equal     )

  @require_tf
  @require_tokenizers
  def 		SCREAMING_SNAKE_CASE__	( self     )-> Optional[Any]:
     import tensorflow as tf

     def tf_array_equals(UpperCAmelCase  ,    UpperCAmelCase     ):
        return tf.reduce_all(tf.equal(snake_case_  ,    snake_case_     )     )

     __A				 =       BertTokenizer.from_pretrained('''bert-base-cased'''     )
     __A				 =       BertTokenizerFast.from_pretrained('''bert-base-cased'''     )

     with self.subTest('''BatchEncoding (Python, return_tensors=TENSORFLOW)'''     ):
        self.assert_dump_and_restore(
            tokenizer_p('''Small example to encode'''  ,    return_tensors=TensorType.TENSORFLOW     )  ,    snake_case_     )

     with self.subTest('''BatchEncoding (Rust, return_tensors=TENSORFLOW)'''     ):
        self.assert_dump_and_restore(
            tokenizer_r('''Small example to encode'''  ,    return_tensors=TensorType.TENSORFLOW     )  ,    snake_case_     )

  @require_torch
  @require_tokenizers
  def 		SCREAMING_SNAKE_CASE__	( self     )-> Optional[int]:
     import torch

     __A				 =       BertTokenizer.from_pretrained('''bert-base-cased'''     )
     __A				 =       BertTokenizerFast.from_pretrained('''bert-base-cased'''     )

     with self.subTest('''BatchEncoding (Python, return_tensors=PYTORCH)'''     ):
        self.assert_dump_and_restore(
            tokenizer_p('''Small example to encode'''  ,    return_tensors=TensorType.PYTORCH     )  ,    torch.equal     )

     with self.subTest('''BatchEncoding (Rust, return_tensors=PYTORCH)'''     ):
        self.assert_dump_and_restore(
            tokenizer_r('''Small example to encode'''  ,    return_tensors=TensorType.PYTORCH     )  ,    torch.equal     )

  @require_tokenizers
  def 		SCREAMING_SNAKE_CASE__	( self     )-> int:
     __A				 =       BertTokenizer.from_pretrained('''bert-base-cased'''     )
     __A				 =       BertTokenizerFast.from_pretrained('''bert-base-cased'''     )

     with self.subTest('''Python Tokenizer'''     ):
        self.assertFalse(tokenizer_p('''Small example to_encode'''     ).is_fast     )

     with self.subTest('''Rust Tokenizer'''     ):
        self.assertTrue(tokenizer_r('''Small example to_encode'''     ).is_fast     )

  @require_tokenizers
  def 		SCREAMING_SNAKE_CASE__	( self     )-> int:
     __A				 =       BertTokenizerFast.from_pretrained('''bert-base-cased'''     )
     __A				 =       tokenizer_r(['''Test''', '''\xad''', '''test''']  ,    is_split_into_words=snake_case_     )

     self.assertEqual(encoded.word_to_tokens(0     )  ,    TokenSpan(start=1  ,    end=2     )     )
     self.assertEqual(encoded.word_to_tokens(1     )  ,    snake_case_     )
     self.assertEqual(encoded.word_to_tokens(2     )  ,    TokenSpan(start=2  ,    end=3     )     )

  def 		SCREAMING_SNAKE_CASE__	( self     )-> List[str]:
     __A				 =       BatchEncoding({'''inputs''': [[1, 2, 3], [4, 5, 6]], '''labels''': [0, 1]}     )
     __A				 =       batch.convert_to_tensors(tensor_type='''np'''     )
     self.assertEqual(tensor_batch['''inputs'''].shape  ,    (2, 3)     )
     self.assertEqual(tensor_batch['''labels'''].shape  ,    (2,)     )
     # test converting the converted
     with CaptureStderr() as cs:
        __A				 =       batch.convert_to_tensors(tensor_type='''np'''     )
     self.assertFalse(len(cs.err     )  ,    msg=f"should have no warning, but got {cs.err}"     )

     __A				 =       BatchEncoding({'''inputs''': [1, 2, 3], '''labels''': 0}     )
     __A				 =       batch.convert_to_tensors(tensor_type='''np'''  ,    prepend_batch_axis=snake_case_     )
     self.assertEqual(tensor_batch['''inputs'''].shape  ,    (1, 3)     )
     self.assertEqual(tensor_batch['''labels'''].shape  ,    (1,)     )

  @require_torch
  def 		SCREAMING_SNAKE_CASE__	( self     )-> int:
     __A				 =       BatchEncoding({'''inputs''': [[1, 2, 3], [4, 5, 6]], '''labels''': [0, 1]}     )
     __A				 =       batch.convert_to_tensors(tensor_type='''pt'''     )
     self.assertEqual(tensor_batch['''inputs'''].shape  ,    (2, 3)     )
     self.assertEqual(tensor_batch['''labels'''].shape  ,    (2,)     )
     # test converting the converted
     with CaptureStderr() as cs:
        __A				 =       batch.convert_to_tensors(tensor_type='''pt'''     )
     self.assertFalse(len(cs.err     )  ,    msg=f"should have no warning, but got {cs.err}"     )

     __A				 =       BatchEncoding({'''inputs''': [1, 2, 3], '''labels''': 0}     )
     __A				 =       batch.convert_to_tensors(tensor_type='''pt'''  ,    prepend_batch_axis=snake_case_     )
     self.assertEqual(tensor_batch['''inputs'''].shape  ,    (1, 3)     )
     self.assertEqual(tensor_batch['''labels'''].shape  ,    (1,)     )

  @require_tf
  def 		SCREAMING_SNAKE_CASE__	( self     )-> Any:
     __A				 =       BatchEncoding({'''inputs''': [[1, 2, 3], [4, 5, 6]], '''labels''': [0, 1]}     )
     __A				 =       batch.convert_to_tensors(tensor_type='''tf'''     )
     self.assertEqual(tensor_batch['''inputs'''].shape  ,    (2, 3)     )
     self.assertEqual(tensor_batch['''labels'''].shape  ,    (2,)     )
     # test converting the converted
     with CaptureStderr() as cs:
        __A				 =       batch.convert_to_tensors(tensor_type='''tf'''     )
     self.assertFalse(len(cs.err     )  ,    msg=f"should have no warning, but got {cs.err}"     )

     __A				 =       BatchEncoding({'''inputs''': [1, 2, 3], '''labels''': 0}     )
     __A				 =       batch.convert_to_tensors(tensor_type='''tf'''  ,    prepend_batch_axis=snake_case_     )
     self.assertEqual(tensor_batch['''inputs'''].shape  ,    (1, 3)     )
     self.assertEqual(tensor_batch['''labels'''].shape  ,    (1,)     )

  @require_flax
  def 		SCREAMING_SNAKE_CASE__	( self     )-> Union[str, Any]:
     __A				 =       BatchEncoding({'''inputs''': [[1, 2, 3], [4, 5, 6]], '''labels''': [0, 1]}     )
     __A				 =       batch.convert_to_tensors(tensor_type='''jax'''     )
     self.assertEqual(tensor_batch['''inputs'''].shape  ,    (2, 3)     )
     self.assertEqual(tensor_batch['''labels'''].shape  ,    (2,)     )
     # test converting the converted
     with CaptureStderr() as cs:
        __A				 =       batch.convert_to_tensors(tensor_type='''jax'''     )
     self.assertFalse(len(cs.err     )  ,    msg=f"should have no warning, but got {cs.err}"     )

     __A				 =       BatchEncoding({'''inputs''': [1, 2, 3], '''labels''': 0}     )
     __A				 =       batch.convert_to_tensors(tensor_type='''jax'''  ,    prepend_batch_axis=snake_case_     )
     self.assertEqual(tensor_batch['''inputs'''].shape  ,    (1, 3)     )
     self.assertEqual(tensor_batch['''labels'''].shape  ,    (1,)     )

  def 		SCREAMING_SNAKE_CASE__	( self     )-> Dict:
     __A				 =       [{'''input_ids''': np.array([0, 1, 2]     )}, {'''input_ids''': np.array([0, 1, 2, 3]     )}]
     __A				 =       BertTokenizer.from_pretrained('''bert-base-cased'''     )

     __A				 =       tokenizer.pad(snake_case_  ,    padding=snake_case_     )
     self.assertTrue(isinstance(batch['''input_ids''']  ,    np.ndarray     )     )
     self.assertEqual(batch['''input_ids'''].tolist()  ,    [[0, 1, 2, tokenizer.pad_token_id], [0, 1, 2, 3]]     )
     __A				 =       tokenizer.pad(snake_case_  ,    padding=snake_case_  ,    return_tensors='''np'''     )
     self.assertTrue(isinstance(batch['''input_ids''']  ,    np.ndarray     )     )
     self.assertEqual(batch['''input_ids'''].tolist()  ,    [[0, 1, 2, tokenizer.pad_token_id], [0, 1, 2, 3]]     )

  @require_torch
  def 		SCREAMING_SNAKE_CASE__	( self     )-> Optional[int]:
     import torch

     __A				 =       [{'''input_ids''': torch.tensor([0, 1, 2]     )}, {'''input_ids''': torch.tensor([0, 1, 2, 3]     )}]
     __A				 =       BertTokenizer.from_pretrained('''bert-base-cased'''     )

     __A				 =       tokenizer.pad(snake_case_  ,    padding=snake_case_     )
     self.assertTrue(isinstance(batch['''input_ids''']  ,    torch.Tensor     )     )
     self.assertEqual(batch['''input_ids'''].tolist()  ,    [[0, 1, 2, tokenizer.pad_token_id], [0, 1, 2, 3]]     )
     __A				 =       tokenizer.pad(snake_case_  ,    padding=snake_case_  ,    return_tensors='''pt'''     )
     self.assertTrue(isinstance(batch['''input_ids''']  ,    torch.Tensor     )     )
     self.assertEqual(batch['''input_ids'''].tolist()  ,    [[0, 1, 2, tokenizer.pad_token_id], [0, 1, 2, 3]]     )

  @require_tf
  def 		SCREAMING_SNAKE_CASE__	( self     )-> Dict:
     import tensorflow as tf

     __A				 =       [{'''input_ids''': tf.constant([0, 1, 2]     )}, {'''input_ids''': tf.constant([0, 1, 2, 3]     )}]
     __A				 =       BertTokenizer.from_pretrained('''bert-base-cased'''     )

     __A				 =       tokenizer.pad(snake_case_  ,    padding=snake_case_     )
     self.assertTrue(isinstance(batch['''input_ids''']  ,    tf.Tensor     )     )
     self.assertEqual(batch['''input_ids'''].numpy().tolist()  ,    [[0, 1, 2, tokenizer.pad_token_id], [0, 1, 2, 3]]     )
     __A				 =       tokenizer.pad(snake_case_  ,    padding=snake_case_  ,    return_tensors='''tf'''     )
     self.assertTrue(isinstance(batch['''input_ids''']  ,    tf.Tensor     )     )
     self.assertEqual(batch['''input_ids'''].numpy().tolist()  ,    [[0, 1, 2, tokenizer.pad_token_id], [0, 1, 2, 3]]     )

  @require_tokenizers
  def 		SCREAMING_SNAKE_CASE__	( self     )-> str:
     __A				 =       Tokenizer(WordPiece(unk_token='''[UNK]'''     )     )
     PreTrainedTokenizerFast(tokenizer_object=snake_case_     )





  @require_tokenizers
  def 		SCREAMING_SNAKE_CASE__	( self     )-> List[str]:
     __A				 =       Tokenizer(WordPiece(unk_token='''[UNK]'''     )     )
     with tempfile.TemporaryDirectory() as tmpdirname:
        bert_tokenizer.save(os.path.join(snake_case_  ,    '''tokenizer.json'''     )     )
        PreTrainedTokenizerFast(tokenizer_file=os.path.join(snake_case_  ,    '''tokenizer.json'''     )     )








class 						_lowerCAmelCase:

  """simple docstring"""







  def __init__( self  ,    UpperCAmelCase     )-> List[Any]:
     __A				 =       val
     # Number of nodes in left subtree
     __A				 =       0
     __A				 =       None
     __A				 =       None
     __A				 =       None





  def 		SCREAMING_SNAKE_CASE__	( self  ,    UpperCAmelCase     )-> List[Any]:
     assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks"

     if self.val < other.val:
        __A				 =       self.right
        __A				 =       None
        if self.right:
           __A				 =       other
        __A				 =       other
        __A				 =       self.left_tree_size * 2 + 1
        return self
     else:
        __A				 =       other.right
        __A				 =       None
        if other.right:
           __A				 =       self
        __A				 =       self
        __A				 =       other.left_tree_size * 2 + 1
        return other







class 						_lowerCAmelCase:

  """simple docstring"""







  def __init__( self  ,    UpperCAmelCase=None  ,    UpperCAmelCase=None  ,    UpperCAmelCase=0     )-> List[Any]:
     __A				 =       heap_size
     __A				 =       bottom_root
     __A				 =       min_node

  def 		SCREAMING_SNAKE_CASE__	( self  ,    UpperCAmelCase     )-> Optional[int]:

     # Empty heaps corner cases
     if other.size == 0:
        return None
     if self.size == 0:
        __A				 =       other.size
        __A				 =       other.bottom_root
        __A				 =       other.min_node
        return None
     # Update size
     __A				 =       self.size + other.size

     # Update min.node
     if self.min_node.val > other.min_node.val:
        __A				 =       other.min_node
     # Merge

     # Order roots by left_subtree_size
     __A				 =       []
     __A ,						__A				 =       self.bottom_root, other.bottom_root
     while i or j:
        if i and ((not j) or i.left_tree_size < j.left_tree_size):
           combined_roots_list.append((i, True)     )
           __A				 =       i.parent
        else:
           combined_roots_list.append((j, False)     )
           __A				 =       j.parent
        # Insert links between them
     for i in range(len(UpperCAmelCase     ) - 1     ):
        if combined_roots_list[i][1] != combined_roots_list[i + 1][1]:
           __A				 =       combined_roots_list[i + 1][0]
           __A				 =       combined_roots_list[i][0]
        # Consecutively merge roots with same left_tree_size
     __A				 =       combined_roots_list[0][0]
     while i.parent:
        if (
            (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent)
        ) or (
            i.left_tree_size == i.parent.left_tree_size
            and i.left_tree_size != i.parent.parent.left_tree_size
        ):
           # Neighbouring Nodes
           __A				 =       i.left
           __A				 =       i.parent.parent

           # Merging trees
           __A				 =       i.merge_trees(i.parent     )

           # Updating links
           __A				 =       previous_node
           __A				 =       next_node
           if previous_node:
              __A				 =       i
           if next_node:
              __A				 =       i
        else:
           __A				 =       i.parent
        # Updating self.bottom_root
     while i.left:
        __A				 =       i.left
     __A				 =       i

     # Update other
     __A				 =       self.size
     __A				 =       self.bottom_root
     __A				 =       self.min_node

     # Return the merged heap
     return self

  def 		SCREAMING_SNAKE_CASE__	( self  ,    UpperCAmelCase     )-> Optional[Any]:
     if self.size == 0:
        __A				 =       Node(UpperCAmelCase     )
        __A				 =       1
        __A				 =       self.bottom_root
     else:
        # Create new node
        __A				 =       Node(UpperCAmelCase     )

        # Update size
        self.size += 1

        # update min_node
        if val < self.min_node.val:
           __A				 =       new_node
        # Put new_node as a bottom_root in heap
        __A				 =       new_node
        __A				 =       self.bottom_root
        __A				 =       new_node

        # Consecutively merge roots with same left_tree_size
        while (
            self.bottom_root.parent
            and self.bottom_root.left_tree_size
            == self.bottom_root.parent.left_tree_size
        ):
           # Next node
           __A				 =       self.bottom_root.parent.parent

           # Merge
           __A				 =       self.bottom_root.merge_trees(self.bottom_root.parent     )

           # Update Links
           __A				 =       next_node
           __A				 =       None
           if next_node:
              __A				 =       self.bottom_root

  def 		SCREAMING_SNAKE_CASE__	( self     )-> int:
     return self.min_node.val

  def 		SCREAMING_SNAKE_CASE__	( self     )-> Tuple:
     return self.size == 0

  def 		SCREAMING_SNAKE_CASE__	( self     )-> List[Any]:
     __A				 =       self.min_node.val

     # Last element in heap corner case
     if self.size == 1:
        # Update size
        __A				 =       0

        # Update bottom root
        __A				 =       None

        # Update min_node
        __A				 =       None

        return min_value
     # No right subtree corner case
     # The structure of the tree implies that this should be the bottom root
     # and there is at least one other root
     if self.min_node.right is None:
        # Update size
        self.size -= 1

        # Update bottom root
        __A				 =       self.bottom_root.parent
        __A				 =       None

        # Update min_node
        __A				 =       self.bottom_root
        __A				 =       self.bottom_root.parent
        while i:
           if i.val < self.min_node.val:
              __A				 =       i
           __A				 =       i.parent
        return min_value
     # General case
     # Find the BinomialHeap of the right subtree of min_node
     __A				 =       self.min_node.right
     __A				 =       None
     __A				 =       bottom_of_new
     __A				 =       1

     # Size, min_node and bottom_root
     while bottom_of_new.left:
        __A				 =       size_of_new * 2 + 1
        __A				 =       bottom_of_new.left
        if bottom_of_new.val < min_of_new.val:
           __A				 =       bottom_of_new
        # Corner case of single root on top left path
     if (not self.min_node.left) and (not self.min_node.parent):
        __A				 =       size_of_new
        __A				 =       bottom_of_new
        __A				 =       min_of_new
        # print("Single root, multiple nodes case")
        return min_value
     # Remaining cases
     # Construct heap of right subtree
     __A				 =       BinomialHeap(
         bottom_root=UpperCAmelCase  ,    min_node=UpperCAmelCase  ,    heap_size=UpperCAmelCase     )

     # Update size
     __A				 =       self.size - 1 - size_of_new

     # Neighbour nodes
     __A				 =       self.min_node.left
     __A				 =       self.min_node.parent

     # Initialize new bottom_root and min_node
     __A				 =       previous_node or next_node
     __A				 =       next_node

     # Update links of previous_node and search below for new min_node and
     # bottom_root
     if previous_node:
        __A				 =       next_node

        # Update bottom_root and search for min_node below
        __A				 =       previous_node
        __A				 =       previous_node
        while self.bottom_root.left:
           __A				 =       self.bottom_root.left
           if self.bottom_root.val < self.min_node.val:
              __A				 =       self.bottom_root
     if next_node:
        __A				 =       previous_node

        # Search for new min_node above min_node
        __A				 =       next_node
        while i:
           if i.val < self.min_node.val:
              __A				 =       i
           __A				 =       i.parent
        # Merge heaps
     self.merge_heaps(UpperCAmelCase     )

     return min_value

  def 		SCREAMING_SNAKE_CASE__	( self     )-> List[str]:
     __A				 =       self.bottom_root
     while top_root.parent:
        __A				 =       top_root.parent
     # preorder
     __A				 =       []
     self.__traversal(UpperCAmelCase  ,    UpperCAmelCase     )
     return heap_pre_order

  def 		SCREAMING_SNAKE_CASE__	( self  ,    UpperCAmelCase  ,    UpperCAmelCase  ,    UpperCAmelCase=0     )-> Optional[Any]:
     if curr_node:
        preorder.append((curr_node.val, level)     )
        self.__traversal(curr_node.left  ,    UpperCAmelCase  ,    level + 1     )
        self.__traversal(curr_node.right  ,    UpperCAmelCase  ,    level + 1     )
     else:
        preorder.append(('''#''', level)     )





  def __str__( self     )-> str:
     if self.is_empty():
        return ""
     __A				 =       self.pre_order()

     return "\n".join(('''-''' * level + str(UpperCAmelCase     )) for value, level in preorder_heap     )


# Unit Tests
if __name__ == "__main__":
    import doctest

    doctest.testmod()

