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 | private final Color color;
|
---|
42 | DiffItemType(Color color) {
|
---|
43 | this.color = color;
|
---|
44 | }
|
---|
45 |
|
---|
46 | public Color getColor() {
|
---|
47 | return color;
|
---|
48 | }
|
---|
49 | }
|
---|
50 |
|
---|
51 | public Item(DiffItemType state, Object value) {
|
---|
52 | this.state = state;
|
---|
53 | this.value = state == DiffItemType.EMPTY ? null : value;
|
---|
54 | }
|
---|
55 |
|
---|
56 | public final Object value;
|
---|
57 | public final DiffItemType state;
|
---|
58 | }
|
---|
59 |
|
---|
60 | public List<Item> referenceDiff;
|
---|
61 | public List<Item> currentDiff;
|
---|
62 | private Object[] reference;
|
---|
63 | private Object[] current;
|
---|
64 | boolean referenceReversed = false;
|
---|
65 |
|
---|
66 | public TwoColumnDiff(Object[] reference, Object[] current) {
|
---|
67 | this.reference = Utils.copyArray(reference);
|
---|
68 | this.current = Utils.copyArray(current);
|
---|
69 | referenceDiff = new ArrayList<>();
|
---|
70 | currentDiff = new ArrayList<>();
|
---|
71 | diff();
|
---|
72 | }
|
---|
73 |
|
---|
74 | private void diff() {
|
---|
75 | Diff.Change script = new Diff(reference, current).diff_2(false);
|
---|
76 | // attempt diff with reference reversed and test whether less deletions+inserts are required
|
---|
77 | Object[] referenceReversed = Utils.copyArray(reference);
|
---|
78 | Collections.reverse(Arrays.asList(referenceReversed));
|
---|
79 | Diff.Change scriptReversed = new Diff(referenceReversed, current).diff_2(false);
|
---|
80 | if (scriptReversed == null /* reference and current are identical */
|
---|
81 | || script != null && scriptReversed.deleted + scriptReversed.inserted < script.deleted + script.inserted) {
|
---|
82 | this.referenceReversed = true;
|
---|
83 | twoColumnDiffFromScript(scriptReversed, referenceReversed, current, true);
|
---|
84 | } else {
|
---|
85 | this.referenceReversed = false;
|
---|
86 | twoColumnDiffFromScript(script, reference, current, false);
|
---|
87 | }
|
---|
88 | }
|
---|
89 |
|
---|
90 | /**
|
---|
91 | * The result from the diff algorithm is a "script" (a compressed description of the changes)
|
---|
92 | * This method expands this script into a full two column description.
|
---|
93 | */
|
---|
94 | private void twoColumnDiffFromScript(Diff.Change script, Object[] a, Object[] b, final boolean reversed) {
|
---|
95 | int ia = 0;
|
---|
96 | int ib = 0;
|
---|
97 |
|
---|
98 | while (script != null) {
|
---|
99 | int deleted = script.deleted;
|
---|
100 | int inserted = script.inserted;
|
---|
101 | while (ia < script.line0 && ib < script.line1) {
|
---|
102 | referenceDiff.add(new Item(reversed ? DiffItemType.REVERSED : DiffItemType.SAME, a[ia++]));
|
---|
103 | currentDiff.add(new Item(DiffItemType.SAME, b[ib++]));
|
---|
104 | }
|
---|
105 |
|
---|
106 | while (inserted > 0 || deleted > 0) {
|
---|
107 | if (inserted > 0 && deleted > 0) {
|
---|
108 | referenceDiff.add(new Item(DiffItemType.CHANGED, a[ia++]));
|
---|
109 | currentDiff.add(new Item(DiffItemType.CHANGED, b[ib++]));
|
---|
110 | } else if (inserted > 0) {
|
---|
111 | referenceDiff.add(new Item(DiffItemType.EMPTY, null));
|
---|
112 | currentDiff.add(new Item(DiffItemType.INSERTED, b[ib++]));
|
---|
113 | } else {
|
---|
114 | referenceDiff.add(new Item(DiffItemType.DELETED, a[ia++]));
|
---|
115 | currentDiff.add(new Item(DiffItemType.EMPTY, null));
|
---|
116 | }
|
---|
117 | inserted--;
|
---|
118 | deleted--;
|
---|
119 | }
|
---|
120 | script = script.link;
|
---|
121 | }
|
---|
122 | while (ia < a.length && ib < b.length) {
|
---|
123 | referenceDiff.add(new Item(reversed ? DiffItemType.REVERSED : DiffItemType.SAME, a[ia++]));
|
---|
124 | currentDiff.add(new Item(DiffItemType.SAME, b[ib++]));
|
---|
125 | }
|
---|
126 | }
|
---|
127 | }
|
---|