Algoritm de compactare a unor intervale

Salutare tuturor. Astăzi vom prezenta și vom rezolva împreună o problemă cât se poate de simplă și anumea aceea de compactare a unor intervale de timp, în funcție de anumite informații.

Să presupunem că avem o aplicație de shopping, ce lucrează cu o tabelă de produse și una de prețuri. Fiecare produs va avea un anumit preț în fiecare moment de timp. Informația legată de preț poate fi modificată de mai multe ori pe zi și să spunem că în spatele fiecărei modificări stă o altă aplicație, care va monitoriza cu atenție ceea ce se întâmplă pe piață.

Haideți să luăm și un exemplu pentru a înțelege problema și mai bine. Să presupunem că tabela de produse arată astfel:

Fiecare produs are asociat un anumit preț la fiecare moment de timp. Acest lucru se poate evidenția cu ușurință dacă analizăm structura tabelei de prețuri:

Pentru simplitate, să presupunem că moneda este întotdeauna RON. Pentru determinarea prețului aferent unui produs, va trebui să selectăm linia din tabela de prețuri care corespunde ID-ului respectiv de produs și care corespunde intervalului aferent de timp - [Dată de start, Dată de sfârșit). Intervalul de timp este închis la stânga și deschis la dreapta. Se garantează faptul că prețul de start al unui interval coincide cu prețul de sfârșit al celui precedent. De exemplu, dacă astăzi este 2021-01-22 ora 10:00, produsul cu id-ul 1 nu are niciun preț atașat. Dacă la acest interval mai adăugat fix o zi, prețul produsului 1 va deveni 10. Dar ce se întâmplă dacă acum este 2021-01-24 ora 10:00? Acel null pe coloana de Dată de sfârșit se traduce ca fiind present. Cu alte cuvinte, prețul produsului 1 va fi 11. Clar?

Acum, dacă ne uităm mai cu atenție, observăm că produsul 1 are două prețuri posibile: 10 sau 11, chiar dacă în tabelă sunt 4 intervale reprezentate pentru acesta. Primul și al doilea interval se pot compacta. La fel și al 3-lea și al 4-lea.

Problema pe care dorim să o rezolvăm este cea de a scrie algoritmul aferent compactării prețurilor unui anumit produs.
Să presupunem că avem un Map în care cheia este id-ul produsului și valoarea este o listă de versiuni de prețuri: Map<Integer, List<PriceVersion>>unde definiția unui PriceVersion este:

public class PriceVersion {
    public LocalDateTime startDate;
    public LocalDateTime endDate;
    public int price;
}

Să se scrie o funcție care să realizeze compactarea versiunilor unui anumit produs, respectând toate constrângerile impuse mai jos:

Ne dorim ca metoda de compactare să fie cât mai generică. Din acest motiv, semnătura ei va fi:

public static <T> List<T> compact(List<T> versions,
 BiPredicate<T, T> mergePredicate,
 BiFunction<T, T, T> mergeFunction)

Complexitatea legată de timp trebuie să fie O(n), iar cea de spațiu maxim tot O(n).

• List<T> este lista de versiuni de prețuri primită ca și input.
• BiPredicate<T, T> reprezintă un predicat prin care se poate decide dacă operația de compacting va avea loc sau nu. Predicatul va returna true dacă compactarea va avea loc, altfel false.
• BiFunction<T, T, T> reprezintă o funcție prin care se va realiza compactarea a două versiuni consecutive.

O posibilă implementare în Java este descrisă mai jos:

public static <T> List<T> compact(final List<T> versions,
                                  final BiPredicate<T, T> mergePredicate,
                                  final BiFunction<T, T, T> mergeFunction) {
    final int size = versions.size();
    if (size <= 1) {
        return versions;
    }

    final List<T> results = new ArrayList<>();
    T lastCompactedVersion = versions.get(0);
    for (int i = 1; i < size; i++) {
        final T currentVersion = versions.get(i);
        if (mergePredicate.test(lastCompactedVersion, currentVersion)) {
            lastCompactedVersion = mergeFunction.apply(lastCompactedVersion, currentVersion);
        } else {
            results.add(lastCompactedVersion);
            lastCompactedVersion = currentVersion;
        }
    }
    results.add(lastCompactedVersion);

    return results;
}

Temă de casă: Câte teste unitare sunteți dispuși să scrieți pentru a testa algoritmul?