






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


a_     :   Any							=    logging.get_logger(__name__)

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

a_     :   Any							=    {
    "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"
        ),
    },
}
a_     :   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"
        ),
    },
}
a_     :   Optional[int]							=    {
    "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"
        ),
    },
}

a_     :   List[str]							=    {
    "facebook/dpr-ctx_encoder-single-nq-base": 512,
    "facebook/dpr-ctx_encoder-multiset-base": 512,
}
a_     :   List[Any]							=    {
    "facebook/dpr-question_encoder-single-nq-base": 512,
    "facebook/dpr-question_encoder-multiset-base": 512,
}
a_     :   Tuple							=    {
    "facebook/dpr-reader-single-nq-base": 512,
    "facebook/dpr-reader-multiset-base": 512,
}


a_     :   int							=    {
    "facebook/dpr-ctx_encoder-single-nq-base": {"do_lower_case": True},
    "facebook/dpr-ctx_encoder-multiset-base": {"do_lower_case": True},
}
a_     :   Union[str, Any]							=    {
    "facebook/dpr-question_encoder-single-nq-base": {"do_lower_case": True},
    "facebook/dpr-question_encoder-multiset-base": {"do_lower_case": True},
}
a_     :   List[str]							=    {
    "facebook/dpr-reader-single-nq-base": {"do_lower_case": True},
    "facebook/dpr-reader-multiset-base": {"do_lower_case": True},
}


class      lowercase__     (			__UpperCAmelCase	):
	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      lowercase__     (			__UpperCAmelCase	):
	a_         =VOCAB_FILES_NAMES
	a_         =QUESTION_ENCODER_PRETRAINED_VOCAB_FILES_MAP
	a_         =QUESTION_ENCODER_PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
	a_         =QUESTION_ENCODER_PRETRAINED_INIT_CONFIGURATION





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

a_     :   Optional[int]							=    collections.namedtuple('''DPRReaderOutput''', ['''start_logits''', '''end_logits''', '''relevance_logits'''])


a_     :   Any							=    r"\n    Return a dictionary with the token ids of the input strings and other information to give to `.decode_best_spans`.\n    It converts the strings of a question and different passages (title and text) in a sequence of IDs (integers),\n    using the tokenizer and vocabulary. The resulting `input_ids` is a matrix of size `(n_passages, sequence_length)`\n    with the format:\n\n    ```\n    [CLS] <question token ids> [SEP] <titles ids> [SEP] <texts ids>\n    ```\n\n    Args:\n        questions (`str` or `List[str]`):\n            The questions to be encoded. You can specify one question for many passages. In this case, the question\n            will be duplicated like `[questions] * n_passages`. Otherwise you have to specify as many questions as in\n            `titles` or `texts`.\n        titles (`str` or `List[str]`):\n            The passages titles to be encoded. This can be a string or a list of strings if there are several passages.\n        texts (`str` or `List[str]`):\n            The passages texts to be encoded. This can be a string or a list of strings if there are several passages.\n        padding (`bool`, `str` or [`~utils.PaddingStrategy`], *optional*, defaults to `False`):\n            Activates and controls padding. Accepts the following values:\n\n            - `True` or `'longest'`: Pad to the longest sequence in the batch (or no padding if only a single sequence\n              if provided).\n            - `'max_length'`: Pad to a maximum length specified with the argument `max_length` or to the maximum\n              acceptable input length for the model if that argument is not provided.\n            - `False` or `'do_not_pad'` (default): No padding (i.e., can output a batch with sequences of different\n              lengths).\n        truncation (`bool`, `str` or [`~tokenization_utils_base.TruncationStrategy`], *optional*, defaults to `False`):\n            Activates and controls truncation. Accepts the following values:\n\n            - `True` or `'longest_first'`: Truncate to a maximum length specified with the argument `max_length` or to\n              the maximum acceptable input length for the model if that argument is not provided. This will truncate\n              token by token, removing a token from the longest sequence in the pair if a pair of sequences (or a batch\n              of pairs) is provided.\n            - `'only_first'`: Truncate to a maximum length specified with the argument `max_length` or to the maximum\n              acceptable input length for the model if that argument is not provided. This will only truncate the first\n              sequence of a pair if a pair of sequences (or a batch of pairs) is provided.\n            - `'only_second'`: Truncate to a maximum length specified with the argument `max_length` or to the maximum\n              acceptable input length for the model if that argument is not provided. This will only truncate the\n              second sequence of a pair if a pair of sequences (or a batch of pairs) is provided.\n            - `False` or `'do_not_truncate'` (default): No truncation (i.e., can output batch with sequence lengths\n              greater than the model maximum admissible input size).\n        max_length (`int`, *optional*):\n                Controls the maximum length to use by one of the truncation/padding parameters.\n\n                If left unset or set to `None`, this will use the predefined model maximum length if a maximum length\n                is required by one of the truncation/padding parameters. If the model has no specific maximum input\n                length (like XLNet) truncation/padding to a maximum length will be deactivated.\n        return_tensors (`str` or [`~utils.TensorType`], *optional*):\n                If set, will return tensors instead of list of python integers. Acceptable values are:\n\n                - `'tf'`: Return TensorFlow `tf.constant` objects.\n                - `'pt'`: Return PyTorch `torch.Tensor` objects.\n                - `'np'`: Return Numpy `np.ndarray` objects.\n        return_attention_mask (`bool`, *optional*):\n            Whether or not to return the attention mask. If not set, will return the attention mask according to the\n            specific tokenizer's default, defined by the `return_outputs` attribute.\n\n            [What are attention masks?](../glossary#attention-mask)\n\n    Returns:\n        `Dict[str, List[List[int]]]`: A dictionary with the following keys:\n\n        - `input_ids`: List of token ids to be fed to a model.\n        - `attention_mask`: List of indices specifying which tokens should be attended to by the model.\n    "


@add_start_docstrings(__UpperCAmelCase	)
class      lowercase__     :

	def __call__(							self		,    __UpperCAmelCase		,    __UpperCAmelCase = None		,    __UpperCAmelCase = None		,    __UpperCAmelCase = False		,    __UpperCAmelCase = False		,    __UpperCAmelCase = None		,    __UpperCAmelCase = None		,    __UpperCAmelCase = None		,    **__UpperCAmelCase		,    )->					List[Any]:







							'''simple docstring'''





							if titles is None and texts is None:
													return super().__call__(
													    lowerCAmelCase_		,    padding=lowerCAmelCase_		,    truncation=lowerCAmelCase_		,    max_length=lowerCAmelCase_		,    return_tensors=lowerCAmelCase_		,    return_attention_mask=lowerCAmelCase_		,    **lowerCAmelCase_		,    )
							elif titles is None or texts is None:
													lowerCAmelCase__       =						titles if texts is None else texts
													return super().__call__(
													    lowerCAmelCase_		,    lowerCAmelCase_		,    padding=lowerCAmelCase_		,    truncation=lowerCAmelCase_		,    max_length=lowerCAmelCase_		,    return_tensors=lowerCAmelCase_		,    return_attention_mask=lowerCAmelCase_		,    **lowerCAmelCase_		,    )
							lowerCAmelCase__       =						titles if not isinstance(lowerCAmelCase_		,    lowerCAmelCase_       ) else [titles]
							lowerCAmelCase__       =						texts if not isinstance(lowerCAmelCase_		,    lowerCAmelCase_       ) else [texts]
							lowerCAmelCase__       =						len(lowerCAmelCase_       )
							lowerCAmelCase__       =						questions if not isinstance(lowerCAmelCase_		,    lowerCAmelCase_       ) else [questions] * n_passages
							if len(lowerCAmelCase_       ) != len(lowerCAmelCase_       ):
													raise ValueError(
													    F"There should be as many titles than texts but got {len(lowerCAmelCase_       )} titles and {len(lowerCAmelCase_       )} texts."       )
							lowerCAmelCase__       =						super().__call__(lowerCAmelCase_		,    lowerCAmelCase_		,    padding=lowerCAmelCase_		,    truncation=lowerCAmelCase_       )["input_ids"]
							lowerCAmelCase__       =						super().__call__(lowerCAmelCase_		,    add_special_tokens=lowerCAmelCase_		,    padding=lowerCAmelCase_		,    truncation=lowerCAmelCase_       )["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(lowerCAmelCase_		,    lowerCAmelCase_       )
							    ]
							}
							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(lowerCAmelCase_		,    padding=lowerCAmelCase_		,    max_length=lowerCAmelCase_		,    return_tensors=lowerCAmelCase_       )

	def 		UpperCAmelCase  (							self		,    __UpperCAmelCase		,    __UpperCAmelCase		,    __UpperCAmelCase = 16		,    __UpperCAmelCase = 64		,    __UpperCAmelCase = 4		,    )->					Dict:







							'''simple docstring'''





							lowerCAmelCase__       =						reader_input["input_ids"]
							lowerCAmelCase__      ,							lowerCAmelCase__      ,							lowerCAmelCase__       =						reader_output[:3]
							lowerCAmelCase__       =						len(lowerCAmelCase_       )
							lowerCAmelCase__       =						sorted(range(lowerCAmelCase_       )		,    reverse=lowerCAmelCase_		,    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(lowerCAmelCase_       )

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


	def 		UpperCAmelCase  (							self		,    __UpperCAmelCase		,    __UpperCAmelCase		,    __UpperCAmelCase		,    __UpperCAmelCase		,    )->					Any:







							'''simple docstring'''





							lowerCAmelCase__       =						[]
							for start_index, start_score in enumerate(lowerCAmelCase_       ):
													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(lowerCAmelCase_		,    key=lambda __UpperCAmelCase       : x[1]		,    reverse=lowerCAmelCase_       )
							lowerCAmelCase__       =						[]
							for (start_index, end_index), score in scores:
													if start_index > end_index:
																			raise ValueError(F"Wrong span indices: [{start_index}:{end_index}]"       )
													lowerCAmelCase__       =						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(lowerCAmelCase_       ) == top_spans:
																			break
							return chosen_span_intervals





@add_end_docstrings(__UpperCAmelCase	)
class      lowercase__     (			__UpperCAmelCase,					__UpperCAmelCase	):
	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"""]














def        _a  (     UpperCamelCase_					:				Any    ,   UpperCamelCase_					:				List[str]   ) ->   List[Any]:
						"""simple docstring"""







						lowerCAmelCase__       =						0
						lowerCAmelCase__       =						len(UpperCamelCase_   ) - 1

						while left <= right:
												# avoid divided by 0 during interpolation
												if sorted_collection[left] == sorted_collection[right]:
																		if sorted_collection[left] == item:
																								return left
																		else:
																								return None

												lowerCAmelCase__       =						left + ((item - sorted_collection[left]) * (right - left)) // (
												    sorted_collection[right] - sorted_collection[left]
												)

												# out of range check
												if point < 0 or point >= len(UpperCamelCase_   ):
																		return None

												lowerCAmelCase__       =						sorted_collection[point]
												if current_item == item:
																		return point
												else:
																		if point < left:
																								lowerCAmelCase__       =						left
																								lowerCAmelCase__       =						point
																		elif point > right:
																								lowerCAmelCase__       =						right
																								lowerCAmelCase__       =						point
																		else:
																								if item < current_item:
																														lowerCAmelCase__       =						point - 1
																								else:
																														lowerCAmelCase__       =						point + 1
						return None


def        _a  (     UpperCamelCase_					:				List[str]    ,   UpperCamelCase_					:				Optional[Any]    ,   UpperCamelCase_					:				int    ,   UpperCamelCase_					:				int   ) ->   List[Any]:
						"""simple docstring"""







						if sorted_collection[left] == sorted_collection[right]:
												if sorted_collection[left] == item:
																		return left
												else:
																		return None

						lowerCAmelCase__       =						left + ((item - sorted_collection[left]) * (right - left)) // (
						    sorted_collection[right] - sorted_collection[left]
						)

						# out of range check
						if point < 0 or point >= len(UpperCamelCase_   ):
												return None

						if sorted_collection[point] == item:
												return point
						elif point < left:
												return interpolation_search_by_recursion(UpperCamelCase_    ,   UpperCamelCase_    ,   UpperCamelCase_    ,   UpperCamelCase_   )
						elif point > right:
												return interpolation_search_by_recursion(UpperCamelCase_    ,   UpperCamelCase_    ,   UpperCamelCase_    ,   UpperCamelCase_   )
						else:
												if sorted_collection[point] > item:
																		return interpolation_search_by_recursion(
																		    UpperCamelCase_    ,   UpperCamelCase_    ,   UpperCamelCase_    ,   point - 1   )
												else:
																		return interpolation_search_by_recursion(
																		    UpperCamelCase_    ,   UpperCamelCase_    ,   point + 1    ,   UpperCamelCase_   )


def        _a  (     UpperCamelCase_					:				Optional[Any]   ) ->   Tuple:
						"""simple docstring"""







						if collection != sorted(UpperCamelCase_   ):
												raise ValueError("Collection must be ascending sorted"   )
						return True


if __name__ == "__main__":
	import sys
	a_							=    0
	if debug == 1:
		a_							=    [10, 30, 40, 45, 50, 66, 77, 93]
		try:
			__assert_sorted(collection)
		except ValueError:
			sys.exit('''Sequence must be ascending sorted to apply interpolation search''')
		a_							=    67

	a_							=    interpolation_search(collection, target)
	if result is not None:
		print(F"{target} found at positions: {result}")
	else:
		print('''Not found''')






