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            @SuppressWarnings("ImmutableEnumChecker") // see https://github.com/google/error-prone/pull/1682
042            private final Color color;
043            DiffItemType(Color color) {
044                this.color = color;
045            }
046
047            public Color getColor() {
048                return color;
049            }
050
051            public Color getColor(boolean isSelected, boolean hasFocus) {
052                if (isSelected && hasFocus) {
053                    return TagTableCellRenderer.BGCOLOR_SELECTED_FOCUS;
054                } else if (isSelected) {
055                    return TagTableCellRenderer.BGCOLOR_SELECTED;
056                } else {
057                    return getColor();
058                }
059            }
060        }
061
062        Item(DiffItemType state, Object value) {
063            this.state = state;
064            this.value = state == DiffItemType.EMPTY ? null : value;
065        }
066
067        public final Object value;
068        public final DiffItemType state;
069    }
070
071    public List<Item> referenceDiff;
072    public List<Item> currentDiff;
073    private final Object[] reference;
074    private final Object[] current;
075    boolean referenceReversed;
076
077    TwoColumnDiff(Object[] reference, Object... current) {
078        this.reference = Utils.copyArray(reference);
079        this.current = Utils.copyArray(current);
080        referenceDiff = new ArrayList<>();
081        currentDiff = new ArrayList<>();
082        diff();
083    }
084
085    private void diff() {
086        Diff.Change script = new Diff(reference, current).diff2(false);
087        // attempt diff with reference reversed and test whether less deletions+inserts are required
088        Object[] referenceReversed = Utils.copyArray(reference);
089        Collections.reverse(Arrays.asList(referenceReversed));
090        Diff.Change scriptReversed = new Diff(referenceReversed, current).diff2(false);
091        if (scriptReversed == null /* reference and current are identical */
092                || (script != null && scriptReversed.getTotalNumberOfChanges() < script.getTotalNumberOfChanges())) {
093            this.referenceReversed = true;
094            twoColumnDiffFromScript(scriptReversed, referenceReversed, current, true);
095        } else {
096            this.referenceReversed = false;
097            twoColumnDiffFromScript(script, reference, current, false);
098        }
099    }
100
101    /**
102     * The result from the diff algorithm is a "script" (a compressed description of the changes)
103     * This method expands this script into a full two column description.
104     * @param script diff script
105     * @param a reference version
106     * @param b current version
107     * @param reversed if {@code true} use {@link DiffItemType#REVERSED} instead of {@link DiffItemType#SAME}
108     */
109    private void twoColumnDiffFromScript(Diff.Change script, Object[] a, Object[] b, final boolean reversed) {
110        int ia = 0;
111        int ib = 0;
112
113        while (script != null) {
114            int deleted = script.deleted;
115            int inserted = script.inserted;
116            while (ia < script.line0 && ib < script.line1) {
117                referenceDiff.add(new Item(reversed ? DiffItemType.REVERSED : DiffItemType.SAME, a[ia++]));
118                currentDiff.add(new Item(DiffItemType.SAME, b[ib++]));
119            }
120
121            while (inserted > 0 || deleted > 0) {
122                if (inserted > 0 && deleted > 0) {
123                    referenceDiff.add(new Item(DiffItemType.CHANGED, a[ia++]));
124                    currentDiff.add(new Item(DiffItemType.CHANGED, b[ib++]));
125                } else if (inserted > 0) {
126                    referenceDiff.add(new Item(DiffItemType.EMPTY, null));
127                    currentDiff.add(new Item(DiffItemType.INSERTED, b[ib++]));
128                } else {
129                    referenceDiff.add(new Item(DiffItemType.DELETED, a[ia++]));
130                    currentDiff.add(new Item(DiffItemType.EMPTY, null));
131                }
132                inserted--;
133                deleted--;
134            }
135            script = script.link;
136        }
137        while (ia < a.length && ib < b.length) {
138            referenceDiff.add(new Item(reversed ? DiffItemType.REVERSED : DiffItemType.SAME, a[ia++]));
139            currentDiff.add(new Item(DiffItemType.SAME, b[ib++]));
140        }
141    }
142}