






from __future__ import annotations

from random import random
from typing import Generic, TypeVar

lowerCamelCase			:					Union[str, Any]         =	TypeVar('''KT''')
lowerCamelCase			:					int         =	TypeVar('''VT''')



class 							_UpperCamelCase			(Generic[KT, VT]			):


      def __init__(	self					,						__UpperCamelCase = "root"					,						__UpperCamelCase = None	)->	List[Any]:
           __lowerCAmelCase								=					key
           __lowerCAmelCase								=					value
           __lowerCAmelCase								=					[]


      def __repr__(	self	)->	str:
           return F"""Node({self.key}: {self.value})"""


      @property
      def  __UpperCAmelCase		(	self	)->	int:
           return len(self.forward	)



class 							_UpperCamelCase			(Generic[KT, VT]			):


      def __init__(	self					,						__UpperCamelCase = 0.5					,						__UpperCamelCase = 1_6	)->	Optional[Any]:
           __lowerCAmelCase								=					Node[KT, VT]()
           __lowerCAmelCase								=					0
           __lowerCAmelCase								=					p
           __lowerCAmelCase								=					max_level


      def __str__(	self	)->	str:
           __lowerCAmelCase								=					list(self	)

           if len(A_	) == 0:
                return F"""SkipList(level={self.level})"""

           __lowerCAmelCase								=					max((len(str(A_	)	) for item in items)					,						default=4	)
           __lowerCAmelCase								=					max(A_					,						4	) + 4

           __lowerCAmelCase								=					self.head
           __lowerCAmelCase								=					[]

           __lowerCAmelCase								=					node.forward.copy()
           lines.append(F"""[{node.key}]""".ljust(A_					,						"-"	) + "* " * len(A_	)	)
           lines.append(" " * label_size + "| " * len(A_	)	)

           while len(node.forward	) != 0:
                __lowerCAmelCase								=					node.forward[0]

                lines.append(
                    F"""[{node.key}]""".ljust(A_					,						"-"	)
                    + " ".join(str(n.key	) if n.key == node.key else "|" for n in forwards	)	)
                lines.append(" " * label_size + "| " * len(A_	)	)
                __lowerCAmelCase								=					node.forward

           lines.append("None".ljust(A_	) + "* " * len(A_	)	)
           return F"""SkipList(level={self.level})\n""" + "\n".join(A_	)


      def __iter__(	self	)->	Union[str, Any]:
           __lowerCAmelCase								=					self.head

           while len(node.forward	) != 0:
                yield node.forward[0].key
                __lowerCAmelCase								=					node.forward[0]


      def  __UpperCAmelCase		(	self	)->	int:
           __lowerCAmelCase								=					1
           while random() < self.p and level < self.max_level:
                level += 1

           return level


      def  __UpperCAmelCase		(	self					,						__UpperCamelCase	)->	tuple[Node[KT, VT] | None, list[Node[KT, VT]]]:
           __lowerCAmelCase								=					[]

           __lowerCAmelCase								=					self.head

           for i in reversed(range(self.level	)	):
                # i < node.level - When node level is lesser than `i` decrement `i`.
                # node.forward[i].key < key - Jumping to node with key value higher
                #                             or equal to searched key would result
                #                             in skipping searched key.
                while i < node.level and node.forward[i].key < key:
                     __lowerCAmelCase								=					node.forward[i]
                # Each leftmost node (relative to searched node) will potentially have to
                # be updated.
                update_vector.append(A_	)

           update_vector.reverse()  # Note that we were inserting values in reverse order.

           # len(node.forward) != 0 - If current node doesn't contain any further
           #                          references then searched key is not present.
           # node.forward[0].key == key - Next node key should be equal to search key
           #                              if key is present.
           if len(node.forward	) != 0 and node.forward[0].key == key:
                return node.forward[0], update_vector
           else:
                return None, update_vector


      def  __UpperCAmelCase		(	self					,						__UpperCamelCase	)->	Any:
           __lowerCAmelCase			, __lowerCAmelCase								=					self._locate_node(A_	)

           if node is not None:
                for i, update_node in enumerate(A_	):
                     # Remove or replace all references to removed node.
                     if update_node.level > i and update_node.forward[i].key == key:
                          if node.level > i:
                               __lowerCAmelCase								=					node.forward[i]
                          else:
                               __lowerCAmelCase								=					update_node.forward[:i]


      def  __UpperCAmelCase		(	self					,						__UpperCamelCase					,						__UpperCamelCase	)->	Union[str, Any]:
           __lowerCAmelCase			, __lowerCAmelCase								=					self._locate_node(A_	)
           if node is not None:
                __lowerCAmelCase								=					value
           else:
                __lowerCAmelCase								=					self.random_level()

                if level > self.level:
                     # After level increase we have to add additional nodes to head.
                     for _ in range(self.level - 1					,						A_	):
                          update_vector.append(self.head	)
                     __lowerCAmelCase								=					level

                __lowerCAmelCase								=					Node(A_					,						A_	)

                for i, update_node in enumerate(update_vector[:level]	):
                     # Change references to pass through new node.
                     if update_node.level > i:
                          new_node.forward.append(update_node.forward[i]	)

                     if update_node.level < i + 1:
                          update_node.forward.append(A_	)
                     else:
                          __lowerCAmelCase								=					new_node


      def  __UpperCAmelCase		(	self					,						__UpperCamelCase	)->	VT | None:
           __lowerCAmelCase			, __lowerCAmelCase								=					self._locate_node(A_	)

           if node is not None:
                return node.value

           return None





def       __lowerCAmelCase      (						):
     __lowerCAmelCase								=					SkipList()
     skip_list.insert("Key1"					, 3       )
     skip_list.insert("Key2"					, 12       )
     skip_list.insert("Key3"					, 41       )
     skip_list.insert("Key4"					, -19       )

     __lowerCAmelCase								=					skip_list.head
     __lowerCAmelCase								=					{}
     while node.level != 0:
          __lowerCAmelCase								=					node.forward[0]
          __lowerCAmelCase								=					node.value

     assert len(__snake_case       ) == 4
     assert all_values["Key1"] == 3
     assert all_values["Key2"] == 12
     assert all_values["Key3"] == 41
     assert all_values["Key4"] == -19





def       __lowerCAmelCase      (						):
     __lowerCAmelCase								=					SkipList()
     skip_list.insert("Key1"					, 10       )
     skip_list.insert("Key1"					, 12       )

     skip_list.insert("Key5"					, 7       )
     skip_list.insert("Key7"					, 10       )
     skip_list.insert("Key10"					, 5       )

     skip_list.insert("Key7"					, 7       )
     skip_list.insert("Key5"					, 5       )
     skip_list.insert("Key10"					, 10       )

     __lowerCAmelCase								=					skip_list.head
     __lowerCAmelCase								=					{}
     while node.level != 0:
          __lowerCAmelCase								=					node.forward[0]
          __lowerCAmelCase								=					node.value

     if len(__snake_case       ) != 4:
          print()
     assert len(__snake_case       ) == 4
     assert all_values["Key1"] == 12
     assert all_values["Key7"] == 7
     assert all_values["Key5"] == 5
     assert all_values["Key10"] == 10





def       __lowerCAmelCase      (						):
     __lowerCAmelCase								=					SkipList()
     assert skip_list.find("Some key"       ) is None





def       __lowerCAmelCase      (						):
     __lowerCAmelCase								=					SkipList()

     skip_list.insert("Key2"					, 20       )
     assert skip_list.find("Key2"       ) == 20

     skip_list.insert("Some Key"					, 10       )
     skip_list.insert("Key2"					, 8       )
     skip_list.insert("V"					, 13       )

     assert skip_list.find("Y"       ) is None
     assert skip_list.find("Key2"       ) == 8
     assert skip_list.find("Some Key"       ) == 10
     assert skip_list.find("V"       ) == 13





def       __lowerCAmelCase      (						):
     __lowerCAmelCase								=					SkipList()
     skip_list.delete("Some key"       )

     assert len(skip_list.head.forward       ) == 0





def       __lowerCAmelCase      (						):
     __lowerCAmelCase								=					SkipList()

     skip_list.insert("Key1"					, 12       )
     skip_list.insert("V"					, 13       )
     skip_list.insert("X"					, 14       )
     skip_list.insert("Key2"					, 15       )

     skip_list.delete("V"       )
     skip_list.delete("Key2"       )

     assert skip_list.find("V"       ) is None
     assert skip_list.find("Key2"       ) is None





def       __lowerCAmelCase      (						):
     __lowerCAmelCase								=					SkipList()

     skip_list.insert("Key1"					, 12       )
     skip_list.insert("V"					, 13       )
     skip_list.insert("X"					, 14       )
     skip_list.insert("Key2"					, 15       )

     skip_list.delete("V"       )
     assert skip_list.find("V"       ) is None
     assert skip_list.find("X"       ) == 14
     assert skip_list.find("Key1"       ) == 12
     assert skip_list.find("Key2"       ) == 15

     skip_list.delete("X"       )
     assert skip_list.find("V"       ) is None
     assert skip_list.find("X"       ) is None
     assert skip_list.find("Key1"       ) == 12
     assert skip_list.find("Key2"       ) == 15

     skip_list.delete("Key1"       )
     assert skip_list.find("V"       ) is None
     assert skip_list.find("X"       ) is None
     assert skip_list.find("Key1"       ) is None
     assert skip_list.find("Key2"       ) == 15

     skip_list.delete("Key2"       )
     assert skip_list.find("V"       ) is None
     assert skip_list.find("X"       ) is None
     assert skip_list.find("Key1"       ) is None
     assert skip_list.find("Key2"       ) is None





def       __lowerCAmelCase      (						):
     __lowerCAmelCase								=					SkipList()

     skip_list.insert("Key1"					, 12       )
     skip_list.insert("V"					, 13       )
     skip_list.insert("X"					, 142       )
     skip_list.insert("Key2"					, 15       )

     skip_list.delete("X"       )

     def traverse_keys(__snake_case       ):
          yield node.key
          for forward_node in node.forward:
               yield from traverse_keys(__snake_case       )

     assert len(set(traverse_keys(skip_list.head       )       )       ) == 4





def       __lowerCAmelCase      (						):
     def is_sorted(__snake_case       ):
          return all(next_item >= item for item, next_item in zip(__snake_case					, lst[1:]       )       )

     __lowerCAmelCase								=					SkipList()
     for i in range(10       ):
          skip_list.insert(__snake_case					, __snake_case       )
     assert is_sorted(list(__snake_case       )       )
     skip_list.delete(5       )
     skip_list.delete(8       )
     skip_list.delete(2       )
     assert is_sorted(list(__snake_case       )       )
     skip_list.insert(-12					, -12       )
     skip_list.insert(77					, 77       )
     assert is_sorted(list(__snake_case       )       )





def       __lowerCAmelCase      (						):
     for _ in range(100       ):
          # Repeat test 100 times due to the probabilistic nature of skip list
          # random values == random bugs
          test_insert()
          test_insert_overrides_existing_value()

          test_searching_empty_list_returns_none()
          test_search()

          test_deleting_item_from_empty_list_do_nothing()
          test_deleted_items_are_not_founded_by_find_method()
          test_delete_removes_only_given_key()
          test_delete_doesnt_leave_dead_nodes()

          test_iter_always_yields_sorted_values()





def       __lowerCAmelCase      (						):
     __lowerCAmelCase								=					SkipList()
     skip_list.insert(2					, "2"       )
     skip_list.insert(4					, "4"       )
     skip_list.insert(6					, "4"       )
     skip_list.insert(4					, "5"       )
     skip_list.insert(8					, "4"       )
     skip_list.insert(9					, "4"       )

     skip_list.delete(4       )

     print(__snake_case       )


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 main()







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_fast import BertTokenizerFast
from .tokenization_dpr import DPRContextEncoderTokenizer, DPRQuestionEncoderTokenizer, DPRReaderTokenizer


lowerCamelCase			:					Any         =	logging.get_logger(__name__)

lowerCamelCase			:					Tuple         =	{'''vocab_file''': '''vocab.txt''', '''tokenizer_file''': '''tokenizer.json'''}

lowerCamelCase			:					Optional[int]         =	{
    '''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'''
        ),
    },
}
lowerCamelCase			:					List[str]         =	{
    '''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'''
        ),
    },
}
lowerCamelCase			:					Any         =	{
    '''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'''
        ),
    },
}

lowerCamelCase			:					str         =	{
    '''facebook/dpr-ctx_encoder-single-nq-base''': 512,
    '''facebook/dpr-ctx_encoder-multiset-base''': 512,
}
lowerCamelCase			:					Any         =	{
    '''facebook/dpr-question_encoder-single-nq-base''': 512,
    '''facebook/dpr-question_encoder-multiset-base''': 512,
}
lowerCamelCase			:					Tuple         =	{
    '''facebook/dpr-reader-single-nq-base''': 512,
    '''facebook/dpr-reader-multiset-base''': 512,
}


lowerCamelCase			:					Tuple         =	{
    '''facebook/dpr-ctx_encoder-single-nq-base''': {'''do_lower_case''': True},
    '''facebook/dpr-ctx_encoder-multiset-base''': {'''do_lower_case''': True},
}
lowerCamelCase			:					int         =	{
    '''facebook/dpr-question_encoder-single-nq-base''': {'''do_lower_case''': True},
    '''facebook/dpr-question_encoder-multiset-base''': {'''do_lower_case''': True},
}
lowerCamelCase			:					List[Any]         =	{
    '''facebook/dpr-reader-single-nq-base''': {'''do_lower_case''': True},
    '''facebook/dpr-reader-multiset-base''': {'''do_lower_case''': True},
}



class 							_UpperCamelCase			(a_			):
      snake_case_  =							VOCAB_FILES_NAMES
      snake_case_  =							CONTEXT_ENCODER_PRETRAINED_VOCAB_FILES_MAP
      snake_case_  =							CONTEXT_ENCODER_PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
      snake_case_  =							CONTEXT_ENCODER_PRETRAINED_INIT_CONFIGURATION
      snake_case_  =							DPRContextEncoderTokenizer



class 							_UpperCamelCase			(a_			):
      snake_case_  =							VOCAB_FILES_NAMES
      snake_case_  =							QUESTION_ENCODER_PRETRAINED_VOCAB_FILES_MAP
      snake_case_  =							QUESTION_ENCODER_PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
      snake_case_  =							QUESTION_ENCODER_PRETRAINED_INIT_CONFIGURATION
      snake_case_  =							DPRQuestionEncoderTokenizer

lowerCamelCase			:					Union[str, Any]         =	collections.namedtuple(
    '''DPRSpanPrediction''', ['''span_score''', '''relevance_score''', '''doc_id''', '''start_index''', '''end_index''', '''text''']
)

lowerCamelCase			:					List[str]         =	collections.namedtuple('''DPRReaderOutput''', ['''start_logits''', '''end_logits''', '''relevance_logits'''])


lowerCamelCase			:					List[Any]         =	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)

    Return:
        `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(a_			)
class 							_UpperCamelCase			:


      def __call__(	self					,						__UpperCamelCase					,						__UpperCamelCase = None					,						__UpperCamelCase = None					,						__UpperCamelCase = False					,						__UpperCamelCase = False					,						__UpperCamelCase = None					,						__UpperCamelCase = None					,						__UpperCamelCase = None					,						**__UpperCamelCase					,						)->	BatchEncoding:
           if titles is None and texts is None:
                return super().__call__(
                    __UpperCamelCase					,						padding=__UpperCamelCase					,						truncation=__UpperCamelCase					,						max_length=__UpperCamelCase					,						return_tensors=__UpperCamelCase					,						return_attention_mask=__UpperCamelCase					,						**__UpperCamelCase					,						)
           elif titles is None or texts is None:
                __lowerCAmelCase								=					titles if texts is None else texts
                return super().__call__(
                    __UpperCamelCase					,						__UpperCamelCase					,						padding=__UpperCamelCase					,						truncation=__UpperCamelCase					,						max_length=__UpperCamelCase					,						return_tensors=__UpperCamelCase					,						return_attention_mask=__UpperCamelCase					,						**__UpperCamelCase					,						)
           __lowerCAmelCase								=					titles if not isinstance(__UpperCamelCase					,						__UpperCamelCase	) else [titles]
           __lowerCAmelCase								=					texts if not isinstance(__UpperCamelCase					,						__UpperCamelCase	) else [texts]
           __lowerCAmelCase								=					len(__UpperCamelCase	)
           __lowerCAmelCase								=					questions if not isinstance(__UpperCamelCase					,						__UpperCamelCase	) else [questions] * n_passages
           assert len(__UpperCamelCase	) == len(
               __UpperCamelCase	), F"""There should be as many titles than texts but got {len(__UpperCamelCase	)} titles and {len(__UpperCamelCase	)} texts."""
           __lowerCAmelCase								=					super().__call__(__UpperCamelCase					,						__UpperCamelCase					,						padding=__UpperCamelCase					,						truncation=__UpperCamelCase	)["input_ids"]
           __lowerCAmelCase								=					super().__call__(__UpperCamelCase					,						add_special_tokens=__UpperCamelCase					,						padding=__UpperCamelCase					,						truncation=__UpperCamelCase	)["input_ids"]
           __lowerCAmelCase								=					{
               "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(__UpperCamelCase					,						__UpperCamelCase	)
               ]
           }
           if return_attention_mask is not False:
                __lowerCAmelCase								=					[]
                for input_ids in encoded_inputs["input_ids"]:
                     attention_mask.append([int(input_id != self.pad_token_id	) for input_id in input_ids]	)
                __lowerCAmelCase								=					attention_mask
           return self.pad(__UpperCamelCase					,						padding=__UpperCamelCase					,						max_length=__UpperCamelCase					,						return_tensors=__UpperCamelCase	)


      def  __UpperCAmelCase		(	self					,						__UpperCamelCase					,						__UpperCamelCase					,						__UpperCamelCase = 1_6					,						__UpperCamelCase = 6_4					,						__UpperCamelCase = 4					,						)->	List[DPRSpanPrediction]:
           __lowerCAmelCase								=					reader_input["input_ids"]
           __lowerCAmelCase			, __lowerCAmelCase			, __lowerCAmelCase								=					reader_output[:3]
           __lowerCAmelCase								=					len(__UpperCamelCase	)
           __lowerCAmelCase								=					sorted(range(__UpperCamelCase	)					,						reverse=__UpperCamelCase					,						key=relevance_logits.__getitem__	)
           __lowerCAmelCase								=					[]
           for doc_id in sorted_docs:
                __lowerCAmelCase								=					list(input_ids[doc_id]	)
                # assuming question & title information is at the beginning of the sequence
                __lowerCAmelCase								=					sequence_ids.index(self.sep_token_id					,						2	) + 1  # second sep id
                if sequence_ids[-1] == self.pad_token_id:
                     __lowerCAmelCase								=					sequence_ids.index(self.pad_token_id	)
                else:
                     __lowerCAmelCase								=					len(__UpperCamelCase	)

                __lowerCAmelCase								=					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=__UpperCamelCase					,						top_spans=__UpperCamelCase					,						)
                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=__UpperCamelCase					,						start_index=__UpperCamelCase					,						end_index=__UpperCamelCase					,						text=self.decode(sequence_ids[start_index : end_index + 1]	)					,						)	)
                if len(__UpperCamelCase	) >= num_spans:
                     break
           return nbest_spans_predictions[:num_spans]


      def  __UpperCAmelCase		(	self					,						__UpperCamelCase					,						__UpperCamelCase					,						__UpperCamelCase					,						__UpperCamelCase					,						)->	List[DPRSpanPrediction]:
           __lowerCAmelCase								=					[]
           for start_index, start_score in enumerate(__UpperCamelCase	):
                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)	)
           __lowerCAmelCase								=					sorted(__UpperCamelCase					,						key=lambda __UpperCamelCase	: x[1]					,						reverse=__UpperCamelCase	)
           __lowerCAmelCase								=					[]
           for (start_index, end_index), score in scores:
                assert start_index <= end_index, F"""Wrong span indices: [{start_index}:{end_index}]"""
                __lowerCAmelCase								=					end_index - start_index + 1
                assert length <= max_answer_length, 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(__UpperCamelCase	) == top_spans:
                     break
           return chosen_span_intervals



@add_end_docstrings(a_			)
class 							_UpperCamelCase			(a_							,		a_			):
      snake_case_  =							VOCAB_FILES_NAMES
      snake_case_  =							READER_PRETRAINED_VOCAB_FILES_MAP
      snake_case_  =							READER_PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
      snake_case_  =							READER_PRETRAINED_INIT_CONFIGURATION
      snake_case_  =							["""input_ids""", """attention_mask"""]
      snake_case_  =							DPRReaderTokenizer






