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.List;
008
009import org.openstreetmap.josm.gui.history.TwoColumnDiff.Item.DiffItemType;
010import org.openstreetmap.josm.tools.Diff;
011import org.openstreetmap.josm.tools.Utils;
012
013/**
014 * Produces a "two column diff" of two lists. (same as diff -y)
015 *
016 * Each list is annotated with the changes relative to the other, and "empty" cells are inserted so the lists are comparable item by item.
017 *
018 * diff on [1 2 3 4] [1 a 4 5] yields:
019 *
020 * item(SAME, 1)    item(SAME, 1)
021 * item(CHANGED, 2) item(CHANGED, 2)
022 * item(DELETED, 3) item(EMPTY)
023 * item(SAME, 4)    item(SAME, 4)
024 * item(EMPTY)      item(INSERTED, 5)
025 *
026 * @author olejorgenb
027 */
028class TwoColumnDiff {
029    public static class Item {
030
031        public enum DiffItemType {
032            INSERTED(new Color(0xDD, 0xFF, 0xDD)), DELETED(new Color(255,197,197)), CHANGED(new Color(255,234,213)),
033            SAME(new Color(234,234,234)), EMPTY(new Color(234,234,234));
034
035            private final Color color;
036            private DiffItemType(Color color) {
037                this.color = color;
038            }
039            public Color getColor() {
040                return color;
041            }
042        }
043
044        public Item(DiffItemType state, Object value) {
045            this.state = state;
046            this.value = state == DiffItemType.EMPTY ? null : value;
047        }
048
049        public final Object value;
050        public final DiffItemType state;
051    }
052
053    public List<Item> referenceDiff;
054    public List<Item> currentDiff;
055    Object[] reference;
056    Object[] current;
057
058    public TwoColumnDiff(Object[] reference, Object[] current) {
059        this.reference = Utils.copyArray(reference);
060        this.current = Utils.copyArray(current);
061        referenceDiff = new ArrayList<>();
062        currentDiff = new ArrayList<>();
063        diff();
064    }
065    
066    private void diff() {
067        Diff diff = new Diff(reference, current);
068        Diff.Change script = diff.diff_2(false);
069        twoColumnDiffFromScript(script, reference, current);
070    }
071
072    /**
073     * The result from the diff algorithm is a "script" (a compressed description of the changes)
074     * This method expands this script into a full two column description.
075     */
076    private void twoColumnDiffFromScript(Diff.Change script, Object[] a, Object[] b) {
077        int ia = 0;
078        int ib = 0;
079
080        while(script != null) {
081            int deleted = script.deleted;
082            int inserted = script.inserted;
083            while(ia < script.line0 && ib < script.line1){
084                Item cell = new Item(DiffItemType.SAME, a[ia]);
085                referenceDiff.add(cell);
086                currentDiff.add(cell);
087                ia++;
088                ib++;
089            }
090
091            while(inserted > 0 || deleted > 0) {
092                if(inserted > 0 && deleted > 0) {
093                    referenceDiff.add(new Item(DiffItemType.CHANGED, a[ia++]));
094                    currentDiff.add(new Item(DiffItemType.CHANGED, b[ib++]));
095                } else if(inserted > 0) {
096                    referenceDiff.add(new Item(DiffItemType.EMPTY, null));
097                    currentDiff.add(new Item(DiffItemType.INSERTED, b[ib++]));
098                } else if(deleted > 0) {
099                    referenceDiff.add(new Item(DiffItemType.DELETED, a[ia++]));
100                    currentDiff.add(new Item(DiffItemType.EMPTY, null));
101                }
102                inserted--;
103                deleted--;
104            }
105            script = script.link;
106        }
107        while(ia < a.length && ib < b.length) {
108            referenceDiff.add(new Item(DiffItemType.SAME, a[ia++]));
109            currentDiff.add(new Item(DiffItemType.SAME, b[ib++]));
110        }
111    }
112}