Šestý domácí úkol

Kvůli přílišné prodlevě ve spuštění testu byl tento domácí úkol zrušen. Pokud jste i bez testu vypracovali jeho správné řešení, pošlete ho přednášejícímu a ten vám navrhne úlevu z budoucích úkolů.

Tento úkol volně navazuje na kód ze cvičení v osmém týdnu.

Aktuální (nekomitnutý) stav adresáře je reprezentován mapou files, ve které jsou jména všech existujících souborů uložena jako klíče a obsahy těchto souborů jako příslušné hodnoty. Vaším úkolem je napsat metodu ChangeSet RepositoryView.createChangeSet(ImmutableMap<String, String> files), která vrátí ChangeSet reprezentující rozdíl mezi this a files. Pokud mezi this a files žádný rozdíl není, vrátí prázdný ChangeSet. Formálně vzato má pro všechny instance Repository r, RepositoryView rv, ImmutableMap<String, String> f a String n platit

r.addChangeSet(rv.createChangeSet(f)).getFileContents(n).equals(f.get(n)).

Navíc musí být vaše ChangeSety co nejmenší, proto musíte využít (již naprogramovanou) metodu List<Integer> DifferenceUtils.longestCommonSubsequence(String, String), která ke dvěma řetezcům vrátí seznam všech indexů shodných řádků (indexy jsou vztaženy k prvnímu z řetězců). Např. k řetězcům

avokádo
brambora
citrón
dýně
jablko
pomeranč

a

avokádo
citrón
granátové jablko
jablko
meloun
pomeranč

vrátí seznam 0, 2, 4, 5.

Odevzdávaný kód (tzn. třídu RepositoryView) uložte do svého repozitáře do adresáře hw/Assignment6.java. Termín odevzdání je 23. 4. ve 24:00.

import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Arrays;
import java.util.LinkedList;
 
/**
 * Trida Repository reprezentuje repozitar.
 */
class Repository {
    final List<ChangeSet> changeSets = new ArrayList<>();
 
    /**
     * Vytvori prazdny repozitar.
     */
    public Repository() {
        changeSets.add(new ChangeSet(null, ImmutableMap.<String, Change>of()));
    }
 
    /**
     * Prida zadany changeset do tohoto repozitare a vrati novou revizi.
     */
    RepositoryView addChangeSet(ChangeSet changeSet) {
        changeSets.add(changeSet);
        return new RepositoryView(this, changeSets.size() - 1);
    }
 
    /**
     * Vrati revizi s danym cislem.
     */
    RepositoryView getRevision(int number) {
        return new RepositoryView(this, number);
    }
 
    /**
     * Vrati pocatecni revizi.
     */
    RepositoryView getInitialRevision() {
        return getRevision(0);
    }
    /**
     * Vrati posledni revizi.
     */    
    RepositoryView getLastRevision() {
        return getRevision(changeSets.size() - 1);
    }
}
 
class RepositoryView {
    final Repository repository;
    final int revision;
 
    /**
     * Vytvori revizi od daneho repozitare s danym cislem.
     */
    public RepositoryView(Repository repository, int revision) {
        this.repository = repository;
        this.revision = revision;
    }
 
    /**
     * Vrati obsah souboru se jmenem name v teto revizi. Pokud soubor s danym
     * jmenem neexistuje, vrati null.
     */
    String getFileContents(String name) {
        return repository.changeSets.get(revision).getFileContents(name);
    }
 
    ChangeSet createChangeSet(ImmutableMap<String, String> files) {
        // sem dopiste svuj kod
    }
}
 
class ChangeSet {
    /**
     * Ukazatel na predchozi changeset.
     */
    final ChangeSet previous;
    /**
     * Mapa, ktera ke jmenu souboru vrati prislusnou zmenu. Pokud nejaky soubor
     * neni v teto mape obsazen, znamena to, ze zustava nezmenen.
     */
    final ImmutableMap<String, Change> changes;
 
    public ChangeSet(ChangeSet previous, ImmutableMap<String, Change> changes) {
        this.previous = previous;
        this.changes = changes;
    }
 
    String getFileContents(String name) {
        if (changes.containsKey(name))
            return changes.get(name).getChangedFileContents(name, previous);
        else return previous == null ? null : previous.getFileContents(name);
    }
 
    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        final ChangeSet other = (ChangeSet) obj;
        if (!Objects.equals(this.previous, other.previous)) return false;
        if (!Objects.equals(this.changes, other.changes)) return false;
        return true;
    }
 
    @Override
    public int hashCode() {
        int hash = 7;
        hash = 31 * hash + Objects.hashCode(this.previous);
        hash = 31 * hash + Objects.hashCode(this.changes);
        return hash;
    }
}
 
interface Change {
    String getChangedFileContents(String name, ChangeSet previous);
}
 
/**
 * Tato zmena indikuje, ze prislusny soubor byl smazan.
 */
class Removal implements Change {
    @Override
    public String getChangedFileContents(String name, ChangeSet previous) {
        return null;
    }
 
    @Override
    public boolean equals(Object obj) {
        return obj instanceof Removal;
    }
 
    @Override
    public int hashCode() {
        return 1;
    }
}
 
/**
 * Tato zmena indikuje, ze prislusny soubor byl vytvoren (pokud je seznam
 * differences prazdny) nebo zmenen (pokud je seznam differences neprazdny).
 *
 */
class Modification implements Change {
    /**
     * Seznam zmen. Zmeny v nem musi byt serazeny vzestupne podle cisel radku.
     */
    final ImmutableList<Difference> differences;
 
    public Modification(ImmutableList<Difference> differences) {
        this.differences = differences;
    }
 
    @Override
    public String getChangedFileContents(String name, ChangeSet previous) {
        String result;
        if (previous == null) result = "";
        else {
            String previousContents = previous.getFileContents(name);
            result = previousContents == null ? "" : previousContents;
        }
        int delta = 0;
        for (Difference diff : differences) {
            result = diff.getChangedFileContents(result, delta);
            delta += diff.getDelta();
        }
        return result;
    }
 
    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        final Modification other = (Modification) obj;
        if (!Objects.equals(this.differences, other.differences)) return false;
        return true;
    }
 
    @Override
    public int hashCode() {
        int hash = 5;
        hash = 29 * hash + Objects.hashCode(this.differences);
        return hash;
    }
}
 
interface Difference {
    String getChangedFileContents(String previous, int delta);
 
    int getDelta();
}
 
abstract class DifferenceUtils {
    /**
     * Prevede seznam retezcu na jeden dlouhy retezec oddeleny novymi radky.
     */
    static String convertToString(List<String> lines) {
        StringBuilder result = new StringBuilder();
        boolean first = true;
        for (String line : lines) {
            if (!first) result.append("\n");
            else first = false;
            result.append(line);
        }
        return result.toString();
    }
 
    /**
     * Vrati vzestupne serazene indexy spolecnych radku.
     */
    static List<Integer> longestCommonSubsequence(String a, String b) {
        String[] x = a.split("\n", -1);
        String[] y = b.split("\n", -1);
        int[][] c = new int[x.length + 1][y.length + 1];
        for (int i = 1; i <= x.length; i++)
            for (int j = 1; j <= y.length; j++)
                if (x[i - 1].equals(y[j - 1]))
                    c[i][j] = c[i - 1][j - 1] + 1;
                else
                    c[i][j] = c[i][j - 1] < c[i - 1][j] ? c[i - 1][j] : c[i][j - 1];
        List<Integer> list = new LinkedList<>();
        longestCommonSubsequenceBacktrack(list, c, x, y, x.length, y.length);
        return list;
    }
 
    //pomocna metoda pro longestCommonSubsequence()
    static void longestCommonSubsequenceBacktrack(List<Integer> list, int[][] c, String[] x, String[] y, int i, int j) {
        if (i == 0 || j == 0) {
        } else if (x[i - 1].equals(y[j - 1])) {
            longestCommonSubsequenceBacktrack(list, c, x, y, i - 1, j - 1);
            list.add(i - 1);
        } else if (c[i][j - 1] > c[i - 1][j])
            longestCommonSubsequenceBacktrack(list, c, x, y, i, j - 1);
        else
            longestCommonSubsequenceBacktrack(list, c, x, y, i - 1, j);
    }
}
 
/**
 * Pridani jednoho nebo vice radku.
 */
class AddedText implements Difference {
    /**
     * Index radku, nula znamena zacatek souboru.
     */
    final int lineNo;
    /**
     * Pridavany text.
     */
    final String addedText;
 
    public AddedText(int lineNo, String addedText) {
        this.lineNo = lineNo;
        this.addedText = addedText;
    }
 
    @Override
    public String getChangedFileContents(String previous, int delta) {
        List<String> lines = new LinkedList<>();
        lines.addAll(Arrays.asList(previous.split("\n", -1)));
        lines.add(lineNo + delta, addedText);
        return DifferenceUtils.convertToString(lines);
    }
 
    @Override
    public int getDelta() {
        return addedText.split("\n", -1).length;
    }
 
    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        final AddedText other = (AddedText) obj;
        if (this.lineNo != other.lineNo) return false;
        if (!Objects.equals(this.addedText, other.addedText)) return false;
        return true;
    }
 
    @Override
    public int hashCode() {
        int hash = 7;
        hash = 37 * hash + this.lineNo;
        hash = 37 * hash + Objects.hashCode(this.addedText);
        return hash;
    }
}
 
/**
 * Odebrani jednoho nebo vice radku.
 */
class DeletedText implements Difference {
    /**
     * Prvni z odebiranych radku.
     */
    final int startLineNo;
    /**
     * Posledni z odebiranych radku. Dvojice (0, 0) znamena odebrani prvniho
     * radku.
     */
    final int endLineNo;
 
    public DeletedText(int startLineNo, int endLineNo) {
        this.startLineNo = startLineNo;
        this.endLineNo = endLineNo;
    }
 
    @Override
    public String getChangedFileContents(String previous, int delta) {
        List<String> lines = new LinkedList<>();
        lines.addAll(Arrays.asList(previous.split("\n", -1)));
        for (int i = startLineNo + delta; i <= endLineNo + delta; i++)
            lines.remove(startLineNo + delta);
        return DifferenceUtils.convertToString(lines);
    }
 
    @Override
    public int getDelta() {
        return startLineNo - endLineNo - 1;
    }
 
    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        final DeletedText other = (DeletedText) obj;
        if (this.startLineNo != other.startLineNo) return false;
        if (this.endLineNo != other.endLineNo) return false;
        return true;
    }
 
    @Override
    public int hashCode() {
        int hash = 7;
        hash = 67 * hash + this.startLineNo;
        hash = 67 * hash + this.endLineNo;
        return hash;
    }
}
 
/**
 * Zamena jednoho nebo vice radku.
 */
class ChangedText implements Difference {
    /**
     * Prvni ze zamenovanych radku.
     */
    final int startLineNo;
    /**
     * Posledni ze zamenovanych radku.
     */
    final int endLineNo;
    /**
     * Zamenovany text.
     */
    final String replacementText;
 
    public ChangedText(int startLineNo, int endLineNo, String replacementText) {
        this.startLineNo = startLineNo;
        this.endLineNo = endLineNo;
        this.replacementText = replacementText;
    }
 
    @Override
    public String getChangedFileContents(String previous, int delta) {
        List<String> lines = new LinkedList<>();
        lines.addAll(Arrays.asList(previous.split("\n", -1)));
        for (int i = startLineNo + delta; i <= endLineNo + delta; i++)
            lines.remove(startLineNo + delta);
        lines.add(startLineNo + delta, replacementText);
        return DifferenceUtils.convertToString(lines);
    }
 
    @Override
    public int getDelta() {
        return replacementText.split("\n", -1).length + startLineNo - endLineNo - 1;
    }
 
    @Override
    public boolean equals(Object obj) {
        if (obj == null) return false;
        if (getClass() != obj.getClass()) return false;
        final ChangedText other = (ChangedText) obj;
        if (this.startLineNo != other.startLineNo) return false;
        if (this.endLineNo != other.endLineNo) return false;
        if (!Objects.equals(this.replacementText, other.replacementText))
            return false;
        return true;
    }
 
    @Override
    public int hashCode() {
        int hash = 5;
        hash = 41 * hash + this.startLineNo;
        hash = 41 * hash + this.endLineNo;
        hash = 41 * hash + Objects.hashCode(this.replacementText);
        return hash;
    }
}

~~DISCUSSION:closed~~