001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.gui.history;
003/// Feel free to move me somewhere else. Maybe a bit specific for josm.tools?
004
005import java.awt.Color;
006import java.util.ArrayList;
007import java.util.Arrays;
008import java.util.Collections;
009import java.util.List;
010
011import org.openstreetmap.josm.gui.history.TwoColumnDiff.Item.DiffItemType;
012import org.openstreetmap.josm.tools.Diff;
013import org.openstreetmap.josm.tools.Utils;
014
015/**
016 * Produces a "two column diff" of two lists. (same as diff -y)
017 *
018 * Each list is annotated with the changes relative to the other, and "empty" cells are inserted so the lists are comparable item by item.
019 *
020 * diff on [1 2 3 4] [1 a 4 5] yields:
021 *
022 * item(SAME, 1)    item(SAME, 1)
023 * item(CHANGED, 2) item(CHANGED, 2)
024 * item(DELETED, 3) item(EMPTY)
025 * item(SAME, 4)    item(SAME, 4)
026 * item(EMPTY)      item(INSERTED, 5)
027 *
028 * @author olejorgenb
029 */
030class TwoColumnDiff {
031    public static class Item {
032
033        public enum DiffItemType {
034            INSERTED(new Color(0xDD, 0xFF, 0xDD)),
035            DELETED(new Color(255, 197, 197)),
036            CHANGED(new Color(255, 234, 213)),
037            REVERSED(new Color(255, 255, 204)),
038            SAME(new Color(234, 234, 234)),
039            EMPTY(new Color(234, 234, 234));
040
041            private final Color color;
042            DiffItemType(Color color) {
043                this.color = color;
044            }
045
046            public Color getColor() {
047                return color;
048            }
049        }
050
051        Item(DiffItemType state, Object value) {
052            this.state = state;
053            this.value = state == DiffItemType.EMPTY ? null : value;
054        }
055
056        public final Object value;
057        public final DiffItemType state;
058    }
059
060    public List<Item> referenceDiff;
061    public List<Item> currentDiff;
062    private final Object[] reference;
063    private final Object[] current;
064    boolean referenceReversed;
065
066    TwoColumnDiff(Object[] reference, Object ... current) {
067        this.reference = Utils.copyArray(reference);
068        this.current = Utils.copyArray(current);
069        referenceDiff = new ArrayList<>();
070        currentDiff = new ArrayList<>();
071        diff();
072    }
073
074    private void diff() {
075        Diff.Change script = new Diff(reference, current).diff2(false);
076        // attempt diff with reference reversed and test whether less deletions+inserts are required
077        Object[] referenceReversed = Utils.copyArray(reference);
078        Collections.reverse(Arrays.asList(referenceReversed));
079        Diff.Change scriptReversed = new Diff(referenceReversed, current).diff2(false);
080        if (scriptReversed == null /* reference and current are identical */
081                || (script != null && scriptReversed.getTotalNumberOfChanges() < script.getTotalNumberOfChanges())) {
082            this.referenceReversed = true;
083            twoColumnDiffFromScript(scriptReversed, referenceReversed, current, true);
084        } else {
085            this.referenceReversed = false;
086            twoColumnDiffFromScript(script, reference, current, false);
087        }
088    }
089
090    /**
091     * The result from the diff algorithm is a "script" (a compressed description of the changes)
092     * This method expands this script into a full two column description.
093     * @param script diff script
094     * @param a reference version
095     * @param b current version
096     * @param reversed if {@code true} use {@link DiffItemType#REVERSED} instead of {@link DiffItemType#SAME}
097     */
098    private void twoColumnDiffFromScript(Diff.Change script, Object[] a, Object[] b, final boolean reversed) {
099        int ia = 0;
100        int ib = 0;
101
102        while (script != null) {
103            int deleted = script.deleted;
104            int inserted = script.inserted;
105            while (ia < script.line0 && ib < script.line1) {
106                referenceDiff.add(new Item(reversed ? DiffItemType.REVERSED : DiffItemType.SAME, a[ia++]));
107                currentDiff.add(new Item(DiffItemType.SAME, b[ib++]));
108            }
109
110            while (inserted > 0 || deleted > 0) {
111                if (inserted > 0 && deleted > 0) {
112                    referenceDiff.add(new Item(DiffItemType.CHANGED, a[ia++]));
113                    currentDiff.add(new Item(DiffItemType.CHANGED, b[ib++]));
114                } else if (inserted > 0) {
115                    referenceDiff.add(new Item(DiffItemType.EMPTY, null));
116                    currentDiff.add(new Item(DiffItemType.INSERTED, b[ib++]));
117                } else {
118                    referenceDiff.add(new Item(DiffItemType.DELETED, a[ia++]));
119                    currentDiff.add(new Item(DiffItemType.EMPTY, null));
120                }
121                inserted--;
122                deleted--;
123            }
124            script = script.link;
125        }
126        while (ia < a.length && ib < b.length) {
127            referenceDiff.add(new Item(reversed ? DiffItemType.REVERSED : DiffItemType.SAME, a[ia++]));
128            currentDiff.add(new Item(DiffItemType.SAME, b[ib++]));
129        }
130    }
131}