from typing import List
from typing import Optional
from typing import Union


def convert_to_bio(
    labels: List[List[str]], constant_outside: str, flat: Optional[bool] = False
) -> Union[List[str], List[List[str]]]:
    """Transforms labels to BIO format (begin, in, out)

    Args:
        labels (List[List[str]]): Plain list of the labels.
        constant_outside (str): Placeholder value for predictions that are out-of-scope.
        flat (Optional[bool], optional): If set to True, the resulting list will be flattened. Defaults to False.

    Returns:
        Union[List[str], List[List[str]]]: List of BIO-labels, either 1d or 2d
    """
    labels_prefixed = []
    for label_list in labels:
        label_list_prefixed = []
        for idx, label in enumerate(label_list):
            if label == constant_outside:
                label_list_prefixed.append(label)
            else:
                if idx == 0:
                    label_list_prefixed.append(f"B-{label}")
                elif label_list[idx - 1] == label:
                    label_list_prefixed.append(f"I-{label}")
                else:
                    label_list_prefixed.append(f"B-{label}")
        if flat:
            labels_prefixed.extend(label_list_prefixed)
        else:
            labels_prefixed.append(label_list_prefixed)
    return labels_prefixed