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.awt.Color;
|
---|
6 | import java.util.ArrayList;
|
---|
7 | import java.util.Arrays;
|
---|
8 | import java.util.Collections;
|
---|
9 | import java.util.List;
|
---|
10 |
|
---|
11 | import org.openstreetmap.josm.gui.history.TwoColumnDiff.Item.DiffItemType;
|
---|
12 | import org.openstreetmap.josm.tools.Diff;
|
---|
13 | import org.openstreetmap.josm.tools.Utils;
|
---|
14 |
|
---|
15 | /**
|
---|
16 | * Produces a "two column diff" of two lists. (same as diff -y)
|
---|
17 | *
|
---|
18 | * Each list is annotated with the changes relative to the other, and "empty" cells are inserted so the lists are comparable item by item.
|
---|
19 | *
|
---|
20 | * diff on [1 2 3 4] [1 a 4 5] yields:
|
---|
21 | *
|
---|
22 | * item(SAME, 1) item(SAME, 1)
|
---|
23 | * item(CHANGED, 2) item(CHANGED, 2)
|
---|
24 | * item(DELETED, 3) item(EMPTY)
|
---|
25 | * item(SAME, 4) item(SAME, 4)
|
---|
26 | * item(EMPTY) item(INSERTED, 5)
|
---|
27 | *
|
---|
28 | * @author olejorgenb
|
---|
29 | */
|
---|
30 | class TwoColumnDiff {
|
---|
31 | public static class Item {
|
---|
32 |
|
---|
33 | public enum DiffItemType {
|
---|
34 | INSERTED(new Color(0xDD, 0xFF, 0xDD)), DELETED(new Color(255,197,197)), CHANGED(new Color(255,234,213)),
|
---|
35 | SAME(new Color(234,234,234)), EMPTY(new Color(234,234,234));
|
---|
36 |
|
---|
37 | private final Color color;
|
---|
38 | private DiffItemType(Color color) {
|
---|
39 | this.color = color;
|
---|
40 | }
|
---|
41 | public Color getColor() {
|
---|
42 | return color;
|
---|
43 | }
|
---|
44 | }
|
---|
45 |
|
---|
46 | public Item(DiffItemType state, Object value) {
|
---|
47 | this.state = state;
|
---|
48 | this.value = state == DiffItemType.EMPTY ? null : value;
|
---|
49 | }
|
---|
50 |
|
---|
51 | public final Object value;
|
---|
52 | public final DiffItemType state;
|
---|
53 | }
|
---|
54 |
|
---|
55 | public List<Item> referenceDiff;
|
---|
56 | public List<Item> currentDiff;
|
---|
57 | private Object[] reference;
|
---|
58 | private Object[] current;
|
---|
59 | boolean referenceReversed = false;
|
---|
60 |
|
---|
61 | public TwoColumnDiff(Object[] reference, Object[] current) {
|
---|
62 | this.reference = Utils.copyArray(reference);
|
---|
63 | this.current = Utils.copyArray(current);
|
---|
64 | referenceDiff = new ArrayList<>();
|
---|
65 | currentDiff = new ArrayList<>();
|
---|
66 | diff();
|
---|
67 | }
|
---|
68 |
|
---|
69 | private void diff() {
|
---|
70 | Diff.Change script = new Diff(reference, current).diff_2(false);
|
---|
71 | // attempt diff with reference reversed and test whether less deletions+inserts are required
|
---|
72 | Object[] referenceReversed = Utils.copyArray(reference);
|
---|
73 | Collections.reverse(Arrays.asList(referenceReversed));
|
---|
74 | Diff.Change scriptReversed = new Diff(referenceReversed, current).diff_2(false);
|
---|
75 | if (scriptReversed == null /* reference and current are identical */
|
---|
76 | || script != null && scriptReversed.deleted + scriptReversed.inserted < script.deleted + script.inserted) {
|
---|
77 | this.referenceReversed = true;
|
---|
78 | twoColumnDiffFromScript(scriptReversed, referenceReversed, current);
|
---|
79 | } else {
|
---|
80 | this.referenceReversed = false;
|
---|
81 | twoColumnDiffFromScript(script, reference, current);
|
---|
82 | }
|
---|
83 | }
|
---|
84 |
|
---|
85 | /**
|
---|
86 | * The result from the diff algorithm is a "script" (a compressed description of the changes)
|
---|
87 | * This method expands this script into a full two column description.
|
---|
88 | */
|
---|
89 | private void twoColumnDiffFromScript(Diff.Change script, Object[] a, Object[] b) {
|
---|
90 | int ia = 0;
|
---|
91 | int ib = 0;
|
---|
92 |
|
---|
93 | while(script != null) {
|
---|
94 | int deleted = script.deleted;
|
---|
95 | int inserted = script.inserted;
|
---|
96 | while(ia < script.line0 && ib < script.line1){
|
---|
97 | Item cell = new Item(DiffItemType.SAME, a[ia]);
|
---|
98 | referenceDiff.add(cell);
|
---|
99 | currentDiff.add(cell);
|
---|
100 | ia++;
|
---|
101 | ib++;
|
---|
102 | }
|
---|
103 |
|
---|
104 | while(inserted > 0 || deleted > 0) {
|
---|
105 | if(inserted > 0 && deleted > 0) {
|
---|
106 | referenceDiff.add(new Item(DiffItemType.CHANGED, a[ia++]));
|
---|
107 | currentDiff.add(new Item(DiffItemType.CHANGED, b[ib++]));
|
---|
108 | } else if(inserted > 0) {
|
---|
109 | referenceDiff.add(new Item(DiffItemType.EMPTY, null));
|
---|
110 | currentDiff.add(new Item(DiffItemType.INSERTED, b[ib++]));
|
---|
111 | } else {
|
---|
112 | referenceDiff.add(new Item(DiffItemType.DELETED, a[ia++]));
|
---|
113 | currentDiff.add(new Item(DiffItemType.EMPTY, null));
|
---|
114 | }
|
---|
115 | inserted--;
|
---|
116 | deleted--;
|
---|
117 | }
|
---|
118 | script = script.link;
|
---|
119 | }
|
---|
120 | while(ia < a.length && ib < b.length) {
|
---|
121 | referenceDiff.add(new Item(DiffItemType.SAME, a[ia++]));
|
---|
122 | currentDiff.add(new Item(DiffItemType.SAME, b[ib++]));
|
---|
123 | }
|
---|
124 | }
|
---|
125 | }
|
---|