
"""simple docstring"""
import collections
from typing import List, Optional, Union

from ...tokenization_utils_base import BatchEncoding
from ...utils import TensorType, add_end_docstrings, add_start_docstrings, logging
from ..bert.tokenization_bert import BertTokenizer


lowercase_       :						int     					=	logging.get_logger(__name__)

lowercase_       :						str     					=	{'''vocab_file''': '''vocab.txt''', '''tokenizer_file''': '''tokenizer.json'''}

lowercase_       :						List[str]     					=	{
    '''vocab_file''': {
        '''facebook/dpr-ctx_encoder-single-nq-base''': (
            '''https://huggingface.co/facebook/dpr-ctx_encoder-single-nq-base/resolve/main/vocab.txt'''
        ),
        '''facebook/dpr-ctx_encoder-multiset-base''': (
            '''https://huggingface.co/facebook/dpr-ctx_encoder-multiset-base/resolve/main/vocab.txt'''
        ),
    },
    '''tokenizer_file''': {
        '''facebook/dpr-ctx_encoder-single-nq-base''': (
            '''https://huggingface.co/facebook/dpr-ctx_encoder-single-nq-base/resolve/main/tokenizer.json'''
        ),
        '''facebook/dpr-ctx_encoder-multiset-base''': (
            '''https://huggingface.co/facebook/dpr-ctx_encoder-multiset-base/resolve/main/tokenizer.json'''
        ),
    },
}
lowercase_       :						Any     					=	{
    '''vocab_file''': {
        '''facebook/dpr-question_encoder-single-nq-base''': (
            '''https://huggingface.co/facebook/dpr-question_encoder-single-nq-base/resolve/main/vocab.txt'''
        ),
        '''facebook/dpr-question_encoder-multiset-base''': (
            '''https://huggingface.co/facebook/dpr-question_encoder-multiset-base/resolve/main/vocab.txt'''
        ),
    },
    '''tokenizer_file''': {
        '''facebook/dpr-question_encoder-single-nq-base''': (
            '''https://huggingface.co/facebook/dpr-question_encoder-single-nq-base/resolve/main/tokenizer.json'''
        ),
        '''facebook/dpr-question_encoder-multiset-base''': (
            '''https://huggingface.co/facebook/dpr-question_encoder-multiset-base/resolve/main/tokenizer.json'''
        ),
    },
}
lowercase_       :						Dict     					=	{
    '''vocab_file''': {
        '''facebook/dpr-reader-single-nq-base''': (
            '''https://huggingface.co/facebook/dpr-reader-single-nq-base/resolve/main/vocab.txt'''
        ),
        '''facebook/dpr-reader-multiset-base''': (
            '''https://huggingface.co/facebook/dpr-reader-multiset-base/resolve/main/vocab.txt'''
        ),
    },
    '''tokenizer_file''': {
        '''facebook/dpr-reader-single-nq-base''': (
            '''https://huggingface.co/facebook/dpr-reader-single-nq-base/resolve/main/tokenizer.json'''
        ),
        '''facebook/dpr-reader-multiset-base''': (
            '''https://huggingface.co/facebook/dpr-reader-multiset-base/resolve/main/tokenizer.json'''
        ),
    },
}

lowercase_       :						Dict     					=	{
    '''facebook/dpr-ctx_encoder-single-nq-base''': 5_12,
    '''facebook/dpr-ctx_encoder-multiset-base''': 5_12,
}
lowercase_       :						Union[str, Any]     					=	{
    '''facebook/dpr-question_encoder-single-nq-base''': 5_12,
    '''facebook/dpr-question_encoder-multiset-base''': 5_12,
}
lowercase_       :						Any     					=	{
    '''facebook/dpr-reader-single-nq-base''': 5_12,
    '''facebook/dpr-reader-multiset-base''': 5_12,
}


lowercase_       :						Dict     					=	{
    '''facebook/dpr-ctx_encoder-single-nq-base''': {'''do_lower_case''': True},
    '''facebook/dpr-ctx_encoder-multiset-base''': {'''do_lower_case''': True},
}
lowercase_       :						Optional[Any]     					=	{
    '''facebook/dpr-question_encoder-single-nq-base''': {'''do_lower_case''': True},
    '''facebook/dpr-question_encoder-multiset-base''': {'''do_lower_case''': True},
}
lowercase_       :						Tuple     					=	{
    '''facebook/dpr-reader-single-nq-base''': {'''do_lower_case''': True},
    '''facebook/dpr-reader-multiset-base''': {'''do_lower_case''': True},
}
class 			UpperCamelCase      (							__SCREAMING_SNAKE_CASE  ):
					A__      =			VOCAB_FILES_NAMES
					A__      =			CONTEXT_ENCODER_PRETRAINED_VOCAB_FILES_MAP
					A__      =			CONTEXT_ENCODER_PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
					A__      =			CONTEXT_ENCODER_PRETRAINED_INIT_CONFIGURATION
class 			UpperCamelCase      (							__SCREAMING_SNAKE_CASE  ):
					A__      =			VOCAB_FILES_NAMES
					A__      =			QUESTION_ENCODER_PRETRAINED_VOCAB_FILES_MAP
					A__      =			QUESTION_ENCODER_PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
					A__      =			QUESTION_ENCODER_PRETRAINED_INIT_CONFIGURATION
lowercase_       :						Optional[Any]     					=	collections.namedtuple(
    '''DPRSpanPrediction''', ['''span_score''', '''relevance_score''', '''doc_id''', '''start_index''', '''end_index''', '''text''']
)

lowercase_       :						Dict     					=	collections.namedtuple('''DPRReaderOutput''', ['''start_logits''', '''end_logits''', '''relevance_logits'''])


lowercase_       :						int     					=	R'''
    Return a dictionary with the token ids of the input strings and other information to give to `.decode_best_spans`.
    It converts the strings of a question and different passages (title and text) in a sequence of IDs (integers),
    using the tokenizer and vocabulary. The resulting `input_ids` is a matrix of size `(n_passages, sequence_length)`
    with the format:

    ```
    [CLS] <question token ids> [SEP] <titles ids> [SEP] <texts ids>
    ```

    Args:
        questions (`str` or `List[str]`):
            The questions to be encoded. You can specify one question for many passages. In this case, the question
            will be duplicated like `[questions] * n_passages`. Otherwise you have to specify as many questions as in
            `titles` or `texts`.
        titles (`str` or `List[str]`):
            The passages titles to be encoded. This can be a string or a list of strings if there are several passages.
        texts (`str` or `List[str]`):
            The passages texts to be encoded. This can be a string or a list of strings if there are several passages.
        padding (`bool`, `str` or [`~utils.PaddingStrategy`], *optional*, defaults to `False`):
            Activates and controls padding. Accepts the following values:

            - `True` or `\'longest\'`: Pad to the longest sequence in the batch (or no padding if only a single sequence
              if provided).
            - `\'max_length\'`: Pad to a maximum length specified with the argument `max_length` or to the maximum
              acceptable input length for the model if that argument is not provided.
            - `False` or `\'do_not_pad\'` (default): No padding (i.e., can output a batch with sequences of different
              lengths).
        truncation (`bool`, `str` or [`~tokenization_utils_base.TruncationStrategy`], *optional*, defaults to `False`):
            Activates and controls truncation. Accepts the following values:

            - `True` or `\'longest_first\'`: Truncate to a maximum length specified with the argument `max_length` or to
              the maximum acceptable input length for the model if that argument is not provided. This will truncate
              token by token, removing a token from the longest sequence in the pair if a pair of sequences (or a batch
              of pairs) is provided.
            - `\'only_first\'`: Truncate to a maximum length specified with the argument `max_length` or to the maximum
              acceptable input length for the model if that argument is not provided. This will only truncate the first
              sequence of a pair if a pair of sequences (or a batch of pairs) is provided.
            - `\'only_second\'`: Truncate to a maximum length specified with the argument `max_length` or to the maximum
              acceptable input length for the model if that argument is not provided. This will only truncate the
              second sequence of a pair if a pair of sequences (or a batch of pairs) is provided.
            - `False` or `\'do_not_truncate\'` (default): No truncation (i.e., can output batch with sequence lengths
              greater than the model maximum admissible input size).
        max_length (`int`, *optional*):
                Controls the maximum length to use by one of the truncation/padding parameters.

                If left unset or set to `None`, this will use the predefined model maximum length if a maximum length
                is required by one of the truncation/padding parameters. If the model has no specific maximum input
                length (like XLNet) truncation/padding to a maximum length will be deactivated.
        return_tensors (`str` or [`~utils.TensorType`], *optional*):
                If set, will return tensors instead of list of python integers. Acceptable values are:

                - `\'tf\'`: Return TensorFlow `tf.constant` objects.
                - `\'pt\'`: Return PyTorch `torch.Tensor` objects.
                - `\'np\'`: Return Numpy `np.ndarray` objects.
        return_attention_mask (`bool`, *optional*):
            Whether or not to return the attention mask. If not set, will return the attention mask according to the
            specific tokenizer\'s default, defined by the `return_outputs` attribute.

            [What are attention masks?](../glossary#attention-mask)

    Returns:
        `Dict[str, List[List[int]]]`: A dictionary with the following keys:

        - `input_ids`: List of token ids to be fed to a model.
        - `attention_mask`: List of indices specifying which tokens should be attended to by the model.
    '''
@add_start_docstrings(__SCREAMING_SNAKE_CASE  )
class 			UpperCamelCase      :
					def __call__(     self  ,     snake_case__  ,     snake_case__ = None  ,     snake_case__ = None  ,     snake_case__ = False  ,     snake_case__ = False  ,     snake_case__ = None  ,     snake_case__ = None  ,     snake_case__ = None  ,     **snake_case__  ,     ):




							"""simple docstring"""


							if titles is None and texts is None:
									return super().__call__(
									    snake_case__  ,     padding=snake_case__  ,     truncation=snake_case__  ,     max_length=snake_case__  ,     return_tensors=snake_case__  ,     return_attention_mask=snake_case__  ,     **snake_case__  ,     )
							elif titles is None or texts is None:
									_SCREAMING_SNAKE_CASE   :				str							    = titles if texts is None else texts
									return super().__call__(
									    snake_case__  ,     snake_case__  ,     padding=snake_case__  ,     truncation=snake_case__  ,     max_length=snake_case__  ,     return_tensors=snake_case__  ,     return_attention_mask=snake_case__  ,     **snake_case__  ,     )
							_SCREAMING_SNAKE_CASE   :				Optional[int]							    = titles if not isinstance(snake_case__  ,     snake_case__				) else [titles]
							_SCREAMING_SNAKE_CASE   :				Dict							    = texts if not isinstance(snake_case__  ,     snake_case__				) else [texts]
							_SCREAMING_SNAKE_CASE   :				Optional[int]							    = len(snake_case__				)
							_SCREAMING_SNAKE_CASE   :				List[str]							    = questions if not isinstance(snake_case__  ,     snake_case__				) else [questions] * n_passages
							if len(snake_case__				) != len(snake_case__				):
									raise ValueError(
									    F'''There should be as many titles than texts but got {len(snake_case__				)} titles and {len(snake_case__				)} texts.'''				)
							_SCREAMING_SNAKE_CASE   :				Optional[int]							    = super().__call__(snake_case__  ,     snake_case__  ,     padding=snake_case__  ,     truncation=snake_case__				)["input_ids"]
							_SCREAMING_SNAKE_CASE   :				List[str]							    = super().__call__(snake_case__  ,     add_special_tokens=snake_case__  ,     padding=snake_case__  ,     truncation=snake_case__				)["input_ids"]
							_SCREAMING_SNAKE_CASE   :				Any							    = {
							    "input_ids": [
							        (encoded_question_and_title + encoded_text)[:max_length]
							        if max_length is not None and truncation
							        else encoded_question_and_title + encoded_text
							        for encoded_question_and_title, encoded_text in zip(snake_case__  ,     snake_case__				)
							    ]
							}
							if return_attention_mask is not False:
									_SCREAMING_SNAKE_CASE   :				Optional[int]							    = []
									for input_ids in encoded_inputs["input_ids"]:
											attention_mask.append([int(input_id != self.pad_token_id				) for input_id in input_ids]				)
									_SCREAMING_SNAKE_CASE   :				Tuple							    = attention_mask
							return self.pad(snake_case__  ,     padding=snake_case__  ,     max_length=snake_case__  ,     return_tensors=snake_case__				)
					def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__  ,     snake_case__ = 16  ,     snake_case__ = 64  ,     snake_case__ = 4  ,     ):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				List[str]							    = reader_input["input_ids"]
							_SCREAMING_SNAKE_CASE   :				Optional[Any]							    = reader_output[:3]
							_SCREAMING_SNAKE_CASE   :				Optional[Any]							    = len(snake_case__				)
							_SCREAMING_SNAKE_CASE   :				List[Any]							    = sorted(range(snake_case__				)  ,     reverse=snake_case__  ,     key=relevance_logits.__getitem__				)
							_SCREAMING_SNAKE_CASE   :				List[DPRReaderOutput]							    = []
							for doc_id in sorted_docs:
									_SCREAMING_SNAKE_CASE   :				Any							    = list(input_ids[doc_id]				)
									# assuming question & title information is at the beginning of the sequence
									_SCREAMING_SNAKE_CASE   :				List[str]							    = sequence_ids.index(self.sep_token_id  ,     2				) + 1  # second sep id
									if sequence_ids[-1] == self.pad_token_id:
											_SCREAMING_SNAKE_CASE   :				int							    = sequence_ids.index(self.pad_token_id				)
									else:
											_SCREAMING_SNAKE_CASE   :				Optional[int]							    = len(snake_case__				)

									_SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = self._get_best_spans(
									    start_logits=start_logits[doc_id][passage_offset:sequence_len]  ,     end_logits=end_logits[doc_id][passage_offset:sequence_len]  ,     max_answer_length=snake_case__  ,     top_spans=snake_case__  ,     )
									for start_index, end_index in best_spans:
											start_index += passage_offset
											end_index += passage_offset
											nbest_spans_predictions.append(
											    DPRSpanPrediction(
											        span_score=start_logits[doc_id][start_index] + end_logits[doc_id][end_index]  ,     relevance_score=relevance_logits[doc_id]  ,     doc_id=snake_case__  ,     start_index=snake_case__  ,     end_index=snake_case__  ,     text=self.decode(sequence_ids[start_index : end_index + 1]				)  ,     )				)
									if len(snake_case__				) >= num_spans:
											break
							return nbest_spans_predictions[:num_spans]




					def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     snake_case__  ,     ):




							"""simple docstring"""


							_SCREAMING_SNAKE_CASE   :				Any							    = []
							for start_index, start_score in enumerate(snake_case__				):
									for answer_length, end_score in enumerate(end_logits[start_index : start_index + max_answer_length]				):
											scores.append(((start_index, start_index + answer_length), start_score + end_score)				)
							_SCREAMING_SNAKE_CASE   :				Any							    = sorted(snake_case__  ,     key=lambda snake_case__				: x[1]  ,     reverse=snake_case__				)
							_SCREAMING_SNAKE_CASE   :				Optional[int]							    = []
							for (start_index, end_index), score in scores:
									if start_index > end_index:
											raise ValueError(F'''Wrong span indices: [{start_index}:{end_index}]'''				)
									_SCREAMING_SNAKE_CASE   :				str							    = end_index - start_index + 1
									if length > max_answer_length:
											raise ValueError(F'''Span is too long: {length} > {max_answer_length}'''				)
									if any(
									    start_index <= prev_start_index <= prev_end_index <= end_index
									    or prev_start_index <= start_index <= end_index <= prev_end_index
									    for (prev_start_index, prev_end_index) in chosen_span_intervals				):
											continue
									chosen_span_intervals.append((start_index, end_index)				)

									if len(snake_case__				) == top_spans:
											break
							return chosen_span_intervals
@add_end_docstrings(__SCREAMING_SNAKE_CASE  )
class 			UpperCamelCase      (							__SCREAMING_SNAKE_CASE      ,       __SCREAMING_SNAKE_CASE  ):
					A__      =			VOCAB_FILES_NAMES
					A__      =			READER_PRETRAINED_VOCAB_FILES_MAP
					A__      =			READER_PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
					A__      =			READER_PRETRAINED_INIT_CONFIGURATION
					A__      =			["""input_ids""", """attention_mask"""]





"""simple docstring"""
from collections.abc import Iterable
from typing import Any
class 			UpperCamelCase      :
     def __init__(     self  ,     snake_case__ = None				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				List[str]							    = value
       _SCREAMING_SNAKE_CASE   :				Node | None							    = None  # Added in order to delete a node easier
       _SCREAMING_SNAKE_CASE   :				Node | None							    = None
       _SCREAMING_SNAKE_CASE   :				Node | None							    = None




     def __repr__(     self				):




       """simple docstring"""


       from pprint import pformat

       if self.left is None and self.right is None:
         return str(self.value				)
       return pformat({F'''{self.value}''': (self.left, self.right)}  ,     indent=1				)
class 			UpperCamelCase      :
     def __init__(     self  ,     snake_case__ = None				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				List[str]							    = root
     def __str__(     self				):




       """simple docstring"""


       return str(self.root				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       if new_children is not None:  # reset its kids
         _SCREAMING_SNAKE_CASE   :				Dict							    = node.parent
       if node.parent is not None:  # reset its parent
         if self.is_right(snake_case__				):  # If it is the right children
           _SCREAMING_SNAKE_CASE   :				Any							    = new_children
         else:
           _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = new_children
       else:
         _SCREAMING_SNAKE_CASE   :				Any							    = new_children
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       if node.parent and node.parent.right:
         return node == node.parent.right
       return False
     def 				__SCREAMING_SNAKE_CASE							(     self				):




       """simple docstring"""


       return self.root is None
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				Optional[int]							    = Node(snake_case__				)  # create a new Node
       if self.empty():  # if Tree is empty
         _SCREAMING_SNAKE_CASE   :				str							    = new_node  # set its root
       else:  # Tree is not empty
         _SCREAMING_SNAKE_CASE   :				Dict							    = self.root  # from root
         if parent_node is None:
           return
         while True:  # While we don't get to a leaf
           if value < parent_node.value:  # We go left
             if parent_node.left is None:
               _SCREAMING_SNAKE_CASE   :				Union[str, Any]							    = new_node  # We insert the new node in a leaf
               break
             else:
               _SCREAMING_SNAKE_CASE   :				int							    = parent_node.left
           else:
             if parent_node.right is None:
               _SCREAMING_SNAKE_CASE   :				str							    = new_node
               break
             else:
               _SCREAMING_SNAKE_CASE   :				Optional[int]							    = parent_node.right
         _SCREAMING_SNAKE_CASE   :				Any							    = parent_node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     *snake_case__				):




       """simple docstring"""


       for value in values:
         self.__insert(snake_case__				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       if self.empty():
         raise IndexError("Warning: Tree is empty! please use another."				)
       else:
         _SCREAMING_SNAKE_CASE   :				Optional[int]							    = self.root
         # use lazy evaluation here to avoid NoneType Attribute error
         while node is not None and node.value is not value:
           _SCREAMING_SNAKE_CASE   :				List[Any]							    = node.left if value < node.value else node.right
         return node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__ = None				):




       """simple docstring"""


       if node is None:
         if self.root is None:
           return None
         _SCREAMING_SNAKE_CASE   :				Optional[Any]							    = self.root

       if not self.empty():
         while node.right is not None:
           _SCREAMING_SNAKE_CASE   :				Dict							    = node.right
       return node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__ = None				):




       """simple docstring"""


       if node is None:
         _SCREAMING_SNAKE_CASE   :				List[Any]							    = self.root
       if self.root is None:
         return None
       if not self.empty():
         _SCREAMING_SNAKE_CASE   :				Any							    = self.root
         while node.left is not None:
           _SCREAMING_SNAKE_CASE   :				Optional[int]							    = node.left
       return node
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				Dict							    = self.search(snake_case__				)  # Look for the node with that label
       if node is not None:
         if node.left is None and node.right is None:  # If it has no children
           self.__reassign_nodes(snake_case__  ,     snake_case__				)
         elif node.left is None:  # Has only right children
           self.__reassign_nodes(snake_case__  ,     node.right				)
         elif node.right is None:  # Has only left children
           self.__reassign_nodes(snake_case__  ,     node.left				)
         else:
           _SCREAMING_SNAKE_CASE   :				Dict							    = self.get_max(
               node.left				)  # Gets the max value of the left branch
           self.remove(tmp_node.value				)  # type: ignore
           _SCREAMING_SNAKE_CASE   :				List[Any]							    = (
               tmp_node.value  # type: ignore
           )  # Assigns the value to the node to delete and keep tree structure
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__				):




       """simple docstring"""


       if node is not None:
         yield node  # Preorder Traversal
         yield from self.preorder_traverse(node.left				)
         yield from self.preorder_traverse(node.right				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__=None				):




       """simple docstring"""


       if traversal_function is None:
         return self.preorder_traverse(self.root				)
       else:
         return traversal_function(self.root				)
     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       if node:
         self.inorder(snake_case__  ,     node.left				)
         arr.append(node.value				)
         self.inorder(snake_case__  ,     node.right				)




     def 				__SCREAMING_SNAKE_CASE							(     self  ,     snake_case__  ,     snake_case__				):




       """simple docstring"""


       _SCREAMING_SNAKE_CASE   :				list[int]							    = []
       self.inorder(snake_case__  ,     snake_case__				)  # append all values to list using inorder traversal
       return arr[k - 1]





def    _lowerCAmelCase    (     lowerCamelCase__							:							Node | None				)  ->    list[Node]:
  _SCREAMING_SNAKE_CASE   :				Optional[int]							    = []
  if curr_node is not None:
    _SCREAMING_SNAKE_CASE   :				int							    = postorder(curr_node.left				) + postorder(curr_node.right				) + [curr_node]
  return node_list





def    _lowerCAmelCase    (     )  ->    None:
  _SCREAMING_SNAKE_CASE   :				Any							    = (8, 3, 6, 1, 1_0, 1_4, 1_3, 4, 7)
  _SCREAMING_SNAKE_CASE   :				List[Any]							    = BinarySearchTree()
  for i in testlist:
    t.insert(lowerCamelCase__				)

  # Prints all the elements of the list in order traversal
  print(lowerCamelCase__				)

  if t.search(6				) is not None:
    print("The value 6 exists"				)
  else:
    print("The value 6 doesn't exist"				)

  if t.search(-1				) is not None:
    print("The value -1 exists"				)
  else:
    print("The value -1 doesn't exist"				)

  if not t.empty():
    print("Max Value: ",						t.get_max().value				)  # type: ignore
    print("Min Value: ",						t.get_min().value				)  # type: ignore

  for i in testlist:
    t.remove(lowerCamelCase__				)
    print(lowerCamelCase__				)


if __name__ == "__main__":
      import doctest

      doctest.testmod(verbose=True)



