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 }