from typing import List
from typing import Dict


def data_splits_from_folds(folds: List[str]) -> List[Dict[str, List[str]]]:
    """
    Create data splits by using Leave One Out Cross Validation strategy.

    folds is a list of dataset partitions created during pre-processing. For example,
    for 5-fold cross val: ["fold00", "fold01", ..., "fold04"]. This function will create
    k test, validation, and train splits using these folds. Each fold is successively
    treated as test split, the next split as validation, and the remaining as train.
    Folds will be sorted before applying the above strategy.

    With 5-fold, for example, we would have:
    test=fold00, val=fold01, train=fold02..04,
    test=fold01, val=fold02, train=fold03,04,01
    ...
    test=fold04, val=fold00, train=01..03
    """
    sorted_folds = tuple(sorted(folds))
    assert len(sorted_folds) == len(set(sorted_folds)), "Folds are not unique"
    num_folds = len(sorted_folds)
    all_data_splits: List[Dict[str, List[str]]] = []
    for fold_idx in range(num_folds):
        test_fold = sorted_folds[fold_idx]
        valid_fold = sorted_folds[(fold_idx + 1) % num_folds]
        train_folds = [f for f in sorted_folds if f not in (test_fold, valid_fold)]
        all_data_splits.append(
            {
                "train": train_folds,
                "valid": [valid_fold],
                "test": [test_fold],
            }
        )
        assert not set(train_folds).intersection(
            {test_fold, valid_fold}
        ), "Train folds are not distinct from the dev and the test folds"

    return all_data_splits