1 | // License: GPL. For details, see LICENSE file.
|
---|
2 | package org.openstreetmap.josm.gui.history;
|
---|
3 | /// Feel free to move me somewhere else. Maybe a bit specific for josm.tools?
|
---|
4 |
|
---|
5 | import java.util.ArrayList;
|
---|
6 |
|
---|
7 | import org.openstreetmap.josm.tools.Diff;
|
---|
8 |
|
---|
9 | /**
|
---|
10 | * Produces a "two column diff" of two lists. (same as diff -y)
|
---|
11 | *
|
---|
12 | * Each list is annotated with the changes relative to the other, and "empty" cells are inserted so the lists are comparable item by item.
|
---|
13 | *
|
---|
14 | * diff on [1 2 3 4] [1 a 4 5] yields:
|
---|
15 | *
|
---|
16 | * item(SAME, 1) item(SAME, 1)
|
---|
17 | * item(CHANGED, 2) item(CHANGED, 2)
|
---|
18 | * item(DELETED, 3) item(EMPTY)
|
---|
19 | * item(SAME, 4) item(SAME, 4)
|
---|
20 | * item(EMPTY) item(INSERTED, 5)
|
---|
21 | *
|
---|
22 | * @author olejorgenb
|
---|
23 | */
|
---|
24 | class TwoColumnDiff {
|
---|
25 | public static class Item {
|
---|
26 | public static final int INSERTED = 1;
|
---|
27 | public static final int DELETED = 2;
|
---|
28 | public static final int CHANGED = 3;
|
---|
29 | public static final int SAME = 4;
|
---|
30 | public static final int EMPTY = 5; // value should be null
|
---|
31 | public Item(int state, Object value) {
|
---|
32 | this.state = state;
|
---|
33 | this.value = state == EMPTY ? null : value;
|
---|
34 | }
|
---|
35 |
|
---|
36 | public final Object value;
|
---|
37 | public final int state;
|
---|
38 | }
|
---|
39 |
|
---|
40 | public ArrayList<Item> referenceDiff;
|
---|
41 | public ArrayList<Item> currentDiff;
|
---|
42 | Object[] reference;
|
---|
43 | Object[] current;
|
---|
44 |
|
---|
45 | /**
|
---|
46 | * The arguments will _not_ be modified
|
---|
47 | */
|
---|
48 | public TwoColumnDiff(Object[] reference, Object[] current) {
|
---|
49 | this.reference = reference;
|
---|
50 | this.current = current;
|
---|
51 | referenceDiff = new ArrayList<Item>();
|
---|
52 | currentDiff = new ArrayList<Item>();
|
---|
53 | diff();
|
---|
54 | }
|
---|
55 | private void diff() {
|
---|
56 | Diff diff = new Diff(reference, current);
|
---|
57 | Diff.change script = diff.diff_2(false);
|
---|
58 | twoColumnDiffFromScript(script, reference, current);
|
---|
59 | }
|
---|
60 |
|
---|
61 | /**
|
---|
62 | * The result from the diff algorithm is a "script" (a compressed description of the changes)
|
---|
63 | * This method expands this script into a full two column description.
|
---|
64 | */
|
---|
65 | private void twoColumnDiffFromScript(Diff.change script, Object[] a, Object[] b) {
|
---|
66 | int ia = 0;
|
---|
67 | int ib = 0;
|
---|
68 |
|
---|
69 | while(script != null) {
|
---|
70 | int deleted = script.deleted;
|
---|
71 | int inserted = script.inserted;
|
---|
72 | while(ia < script.line0 && ib < script.line1){
|
---|
73 | // System.out.println(" "+a[ia] + "\t "+b[ib]);
|
---|
74 | Item cell = new Item(Item.SAME, a[ia]);
|
---|
75 | referenceDiff.add(cell);
|
---|
76 | currentDiff.add(cell);
|
---|
77 | ia++;
|
---|
78 | ib++;
|
---|
79 | }
|
---|
80 |
|
---|
81 | while(inserted > 0 || deleted > 0) {
|
---|
82 | if(inserted > 0 && deleted > 0) {
|
---|
83 | // System.out.println("="+a[ia] + "\t="+b[ib]);
|
---|
84 | referenceDiff.add(new Item(Item.CHANGED, a[ia++]));
|
---|
85 | currentDiff.add(new Item(Item.CHANGED, b[ib++]));
|
---|
86 | } else if(inserted > 0) {
|
---|
87 | // System.out.println("\t+" + b[ib]);
|
---|
88 | referenceDiff.add(new Item(Item.EMPTY, null));
|
---|
89 | currentDiff.add(new Item(Item.INSERTED, b[ib++]));
|
---|
90 | } else if(deleted > 0) {
|
---|
91 | // System.out.println("-"+a[ia]);
|
---|
92 | referenceDiff.add(new Item(Item.DELETED, a[ia++]));
|
---|
93 | currentDiff.add(new Item(Item.EMPTY, null));
|
---|
94 | }
|
---|
95 | inserted--;
|
---|
96 | deleted--;
|
---|
97 | }
|
---|
98 | script = script.link;
|
---|
99 | }
|
---|
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 | }
|
---|