from typing import Tuple
from typing import List


def clamp_global_span_to_tokenized_spans(global_span: Tuple[int, int], tokenized_spans: List[Tuple[int, int]]) -> Tuple[
    int, Tuple[int, int]]:
    """
    Assume the following scenario: You are given a paragraph of text and a character span (start, end) inside this
    paragraph. You sentence-tokenize the paragraph. Now, to which sentence does the character span belong and what
    are its character offsets inside the sentence? This method gives you the answer.
    In case the character span covers multiple sentence spans, this method will assign the character span to the
    first affected sentence, with the end of the span coinciding with the end of that sentence.
    Note: This method bears similarity to `allennlp.data.dataset_readers.reading_comprehension.util.char_span_to_token_span`.
    :param global_span: the start and end offsets of the span, with global offsets w.r.t. its surrounding paragraph (end
                        is exclusive!)
    :param tokenized_spans: the start and end offsets of the sentences (end offsets are exclusive!)
    :return: `(i, (start, end))` where `i` is the index of the sentence in which the start of the character span is
             located and `start`, `end` are the offsets of the span inside the sentence; clamped to the sentence
             boundary if necessary
    """

    start_global, end_global = global_span

    # i_sent is the sentence containing the start of the character span which we want to find
    i_sent = 1
    # Proceed as long as the currently examined sentence ends before the character span begins, or until there are
    # no more sentences to examine.
    while i_sent < len(tokenized_spans) and start_global >= tokenized_spans[i_sent - 1][1]:
        i_sent += 1

    # this happens if the span is somewhere inside the previous sentence
    if i_sent == len(tokenized_spans) or start_global < tokenized_spans[i_sent][0]:
        i_sent -= 1

    start_sentence, end_sentence = tokenized_spans[i_sent]

    # There is a special case where the start of global_span points to (typically whitespace) characters which lie
    # in between the end and start of the following tokenized span. In this case, we want to clamp the start of the
    # sentence to the beginning of the tokenized span which follows the in-between characters, i.e. 0.
    start_in_span = 0 if start_global < start_sentence else start_global - start_sentence

    # clamp the end of the span to the end of the sentence we assigned the global span to
    end_global_clamped = min(end_global, end_sentence)
    end_in_span = end_global_clamped - start_sentence

    return i_sent, (start_in_span, end_in_span)