001    // License: GPL. For details, see LICENSE file.
002    package org.openstreetmap.josm.gui.history;
003    /// Feel free to move me somewhere else. Maybe a bit specific for josm.tools?
004    
005    import java.util.ArrayList;
006    
007    import org.openstreetmap.josm.tools.Diff;
008    
009    /**
010     * Produces a "two column diff" of two lists. (same as diff -y)
011     *
012     * Each list is annotated with the changes relative to the other, and "empty" cells are inserted so the lists are comparable item by item.
013     *
014     * diff on [1 2 3 4] [1 a 4 5] yields:
015     *
016     * item(SAME, 1)    item(SAME, 1)
017     * item(CHANGED, 2) item(CHANGED, 2)
018     * item(DELETED, 3) item(EMPTY)
019     * item(SAME, 4)    item(SAME, 4)
020     * item(EMPTY)      item(INSERTED, 5)
021     *
022     * @author olejorgenb
023     */
024    class TwoColumnDiff {
025        public static class Item {
026            public static final int INSERTED = 1;
027            public static final int DELETED = 2;
028            public static final int CHANGED = 3;
029            public static final int SAME = 4;
030            public static final int EMPTY = 5; // value should be null
031            public Item(int state, Object value) {
032                this.state = state;
033                this.value = state == EMPTY ? null : value;
034            }
035    
036            public final Object value;
037            public final int state;
038        }
039    
040        public ArrayList<Item> referenceDiff;
041        public ArrayList<Item> currentDiff;
042        Object[] reference;
043        Object[] current;
044    
045        /**
046         * The arguments will _not_ be modified
047         */
048        public TwoColumnDiff(Object[] reference, Object[] current) {
049            this.reference = reference;
050            this.current = current;
051            referenceDiff = new ArrayList<Item>();
052            currentDiff = new ArrayList<Item>();
053            diff();
054        }
055        private void diff() {
056            Diff diff = new Diff(reference, current);
057            Diff.change script = diff.diff_2(false);
058            twoColumnDiffFromScript(script, reference, current);
059        }
060    
061        /**
062         * The result from the diff algorithm is a "script" (a compressed description of the changes)
063         * This method expands this script into a full two column description.
064         */
065        private void twoColumnDiffFromScript(Diff.change script, Object[] a, Object[] b) {
066            int ia = 0;
067            int ib = 0;
068    
069            while(script != null) {
070                int deleted = script.deleted;
071                int inserted = script.inserted;
072                while(ia < script.line0 && ib < script.line1){
073                    // System.out.println(" "+a[ia] + "\t "+b[ib]);
074                    Item cell = new Item(Item.SAME, a[ia]);
075                    referenceDiff.add(cell);
076                    currentDiff.add(cell);
077                    ia++;
078                    ib++;
079                }
080    
081                while(inserted > 0 || deleted > 0) {
082                    if(inserted > 0 && deleted > 0) {
083                        // System.out.println("="+a[ia] + "\t="+b[ib]);
084                        referenceDiff.add(new Item(Item.CHANGED, a[ia++]));
085                        currentDiff.add(new Item(Item.CHANGED, b[ib++]));
086                    } else if(inserted > 0) {
087                        // System.out.println("\t+" + b[ib]);
088                        referenceDiff.add(new Item(Item.EMPTY, null));
089                        currentDiff.add(new Item(Item.INSERTED, b[ib++]));
090                    } else if(deleted > 0) {
091                        // System.out.println("-"+a[ia]);
092                        referenceDiff.add(new Item(Item.DELETED, a[ia++]));
093                        currentDiff.add(new Item(Item.EMPTY, null));
094                    }
095                    inserted--;
096                    deleted--;
097                }
098                script = script.link;
099            }
100            while(ia < a.length && ib < b.length) {
101                // System.out.println((ia < a.length ? " "+a[ia]+"\t" : "\t") + (ib < b.length ? " "+b[ib] : ""));
102                referenceDiff.add(new Item(Item.SAME, a[ia++]));
103                currentDiff.add(new Item(Item.SAME, b[ib++]));
104            }
105        }
106    }