001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.gui.history; 003/// Feel free to move me somewhere else. Maybe a bit specific for josm.tools? 004 005import java.awt.Color; 006import java.util.ArrayList; 007import java.util.Arrays; 008import java.util.Collections; 009import java.util.List; 010 011import org.openstreetmap.josm.gui.history.TwoColumnDiff.Item.DiffItemType; 012import org.openstreetmap.josm.tools.Diff; 013import org.openstreetmap.josm.tools.Utils; 014 015/** 016 * Produces a "two column diff" of two lists. (same as diff -y) 017 * 018 * Each list is annotated with the changes relative to the other, and "empty" cells are inserted so the lists are comparable item by item. 019 * 020 * diff on [1 2 3 4] [1 a 4 5] yields: 021 * 022 * item(SAME, 1) item(SAME, 1) 023 * item(CHANGED, 2) item(CHANGED, 2) 024 * item(DELETED, 3) item(EMPTY) 025 * item(SAME, 4) item(SAME, 4) 026 * item(EMPTY) item(INSERTED, 5) 027 * 028 * @author olejorgenb 029 */ 030class TwoColumnDiff { 031 public static class Item { 032 033 public enum DiffItemType { 034 INSERTED(new Color(0xDD, 0xFF, 0xDD)), 035 DELETED(new Color(255, 197, 197)), 036 CHANGED(new Color(255, 234, 213)), 037 REVERSED(new Color(255, 255, 204)), 038 SAME(new Color(234, 234, 234)), 039 EMPTY(new Color(234, 234, 234)); 040 041 @SuppressWarnings("ImmutableEnumChecker") // see https://github.com/google/error-prone/pull/1682 042 private final Color color; 043 DiffItemType(Color color) { 044 this.color = color; 045 } 046 047 public Color getColor() { 048 return color; 049 } 050 051 public Color getColor(boolean isSelected, boolean hasFocus) { 052 if (isSelected && hasFocus) { 053 return TagTableCellRenderer.BGCOLOR_SELECTED_FOCUS; 054 } else if (isSelected) { 055 return TagTableCellRenderer.BGCOLOR_SELECTED; 056 } else { 057 return getColor(); 058 } 059 } 060 } 061 062 Item(DiffItemType state, Object value) { 063 this.state = state; 064 this.value = state == DiffItemType.EMPTY ? null : value; 065 } 066 067 public final Object value; 068 public final DiffItemType state; 069 } 070 071 public List<Item> referenceDiff; 072 public List<Item> currentDiff; 073 private final Object[] reference; 074 private final Object[] current; 075 boolean referenceReversed; 076 077 TwoColumnDiff(Object[] reference, Object... current) { 078 this.reference = Utils.copyArray(reference); 079 this.current = Utils.copyArray(current); 080 referenceDiff = new ArrayList<>(); 081 currentDiff = new ArrayList<>(); 082 diff(); 083 } 084 085 private void diff() { 086 Diff.Change script = new Diff(reference, current).diff2(false); 087 // attempt diff with reference reversed and test whether less deletions+inserts are required 088 Object[] referenceReversed = Utils.copyArray(reference); 089 Collections.reverse(Arrays.asList(referenceReversed)); 090 Diff.Change scriptReversed = new Diff(referenceReversed, current).diff2(false); 091 if (scriptReversed == null /* reference and current are identical */ 092 || (script != null && scriptReversed.getTotalNumberOfChanges() < script.getTotalNumberOfChanges())) { 093 this.referenceReversed = true; 094 twoColumnDiffFromScript(scriptReversed, referenceReversed, current, true); 095 } else { 096 this.referenceReversed = false; 097 twoColumnDiffFromScript(script, reference, current, false); 098 } 099 } 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}