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)),
|
---|
35 | DELETED(new Color(255, 197, 197)),
|
---|
36 | CHANGED(new Color(255, 234, 213)),
|
---|
37 | REVERSED(new Color(255, 255, 204)),
|
---|
38 | SAME(new Color(234, 234, 234)),
|
---|
39 | EMPTY(new Color(234, 234, 234));
|
---|
40 |
|
---|
41 | @SuppressWarnings("ImmutableEnumChecker") // see https://github.com/google/error-prone/pull/1682
|
---|
42 | private final Color color;
|
---|
43 | DiffItemType(Color color) {
|
---|
44 | this.color = color;
|
---|
45 | }
|
---|
46 |
|
---|
47 | public Color getColor() {
|
---|
48 | return color;
|
---|
49 | }
|
---|
50 |
|
---|
51 | public Color getColor(boolean isSelected, boolean hasFocus) {
|
---|
52 | if (isSelected && hasFocus) {
|
---|
53 | return TagTableCellRenderer.BGCOLOR_SELECTED_FOCUS;
|
---|
54 | } else if (isSelected) {
|
---|
55 | return TagTableCellRenderer.BGCOLOR_SELECTED;
|
---|
56 | } else {
|
---|
57 | return getColor();
|
---|
58 | }
|
---|
59 | }
|
---|
60 | }
|
---|
61 |
|
---|
62 | Item(DiffItemType state, Object value) {
|
---|
63 | this.state = state;
|
---|
64 | this.value = state == DiffItemType.EMPTY ? null : value;
|
---|
65 | }
|
---|
66 |
|
---|
67 | public final Object value;
|
---|
68 | public final DiffItemType state;
|
---|
69 | }
|
---|
70 |
|
---|
71 | public List<Item> referenceDiff;
|
---|
72 | public List<Item> currentDiff;
|
---|
73 | private final Object[] reference;
|
---|
74 | private final Object[] current;
|
---|
75 | boolean referenceReversed;
|
---|
76 |
|
---|
77 | TwoColumnDiff(Object[] reference, Object... current) {
|
---|
78 | this.reference = Utils.copyArray(reference);
|
---|
79 | this.current = Utils.copyArray(current);
|
---|
80 | referenceDiff = new ArrayList<>();
|
---|
81 | currentDiff = new ArrayList<>();
|
---|
82 | diff();
|
---|
83 | }
|
---|
84 |
|
---|
85 | private void diff() {
|
---|
86 | Diff.Change script = new Diff(reference, current).diff2(false);
|
---|
87 | // attempt diff with reference reversed and test whether less deletions+inserts are required
|
---|
88 | Object[] referenceReversed = Utils.copyArray(reference);
|
---|
89 | Collections.reverse(Arrays.asList(referenceReversed));
|
---|
90 | Diff.Change scriptReversed = new Diff(referenceReversed, current).diff2(false);
|
---|
91 | if (scriptReversed == null /* reference and current are identical */
|
---|
92 | || (script != null && scriptReversed.getTotalNumberOfChanges() < script.getTotalNumberOfChanges())) {
|
---|
93 | this.referenceReversed = true;
|
---|
94 | twoColumnDiffFromScript(scriptReversed, referenceReversed, current, true);
|
---|
95 | } else {
|
---|
96 | this.referenceReversed = false;
|
---|
97 | twoColumnDiffFromScript(script, reference, current, false);
|
---|
98 | }
|
---|
99 | }
|
---|
100 |
|
---|
101 | /**
|
---|
102 | * The result from the diff algorithm is a "script" (a compressed description of the changes)
|
---|
103 | * This method expands this script into a full two column description.
|
---|
104 | * @param script diff script
|
---|
105 | * @param a reference version
|
---|
106 | * @param b current version
|
---|
107 | * @param reversed if {@code true} use {@link DiffItemType#REVERSED} instead of {@link DiffItemType#SAME}
|
---|
108 | */
|
---|
109 | private void twoColumnDiffFromScript(Diff.Change script, Object[] a, Object[] b, final boolean reversed) {
|
---|
110 | int ia = 0;
|
---|
111 | int ib = 0;
|
---|
112 |
|
---|
113 | while (script != null) {
|
---|
114 | int deleted = script.deleted;
|
---|
115 | int inserted = script.inserted;
|
---|
116 | while (ia < script.line0 && ib < script.line1) {
|
---|
117 | referenceDiff.add(new Item(reversed ? DiffItemType.REVERSED : DiffItemType.SAME, a[ia++]));
|
---|
118 | currentDiff.add(new Item(DiffItemType.SAME, b[ib++]));
|
---|
119 | }
|
---|
120 |
|
---|
121 | while (inserted > 0 || deleted > 0) {
|
---|
122 | if (inserted > 0 && deleted > 0) {
|
---|
123 | referenceDiff.add(new Item(DiffItemType.CHANGED, a[ia++]));
|
---|
124 | currentDiff.add(new Item(DiffItemType.CHANGED, b[ib++]));
|
---|
125 | } else if (inserted > 0) {
|
---|
126 | referenceDiff.add(new Item(DiffItemType.EMPTY, null));
|
---|
127 | currentDiff.add(new Item(DiffItemType.INSERTED, b[ib++]));
|
---|
128 | } else {
|
---|
129 | referenceDiff.add(new Item(DiffItemType.DELETED, a[ia++]));
|
---|
130 | currentDiff.add(new Item(DiffItemType.EMPTY, null));
|
---|
131 | }
|
---|
132 | inserted--;
|
---|
133 | deleted--;
|
---|
134 | }
|
---|
135 | script = script.link;
|
---|
136 | }
|
---|
137 | while (ia < a.length && ib < b.length) {
|
---|
138 | referenceDiff.add(new Item(reversed ? DiffItemType.REVERSED : DiffItemType.SAME, a[ia++]));
|
---|
139 | currentDiff.add(new Item(DiffItemType.SAME, b[ib++]));
|
---|
140 | }
|
---|
141 | }
|
---|
142 | }
|
---|