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 private final Color color; 042 DiffItemType(Color color) { 043 this.color = color; 044 } 045 046 public Color getColor() { 047 return color; 048 } 049 } 050 051 Item(DiffItemType state, Object value) { 052 this.state = state; 053 this.value = state == DiffItemType.EMPTY ? null : value; 054 } 055 056 public final Object value; 057 public final DiffItemType state; 058 } 059 060 public List<Item> referenceDiff; 061 public List<Item> currentDiff; 062 private final Object[] reference; 063 private final Object[] current; 064 boolean referenceReversed; 065 066 TwoColumnDiff(Object[] reference, Object ... current) { 067 this.reference = Utils.copyArray(reference); 068 this.current = Utils.copyArray(current); 069 referenceDiff = new ArrayList<>(); 070 currentDiff = new ArrayList<>(); 071 diff(); 072 } 073 074 private void diff() { 075 Diff.Change script = new Diff(reference, current).diff2(false); 076 // attempt diff with reference reversed and test whether less deletions+inserts are required 077 Object[] referenceReversed = Utils.copyArray(reference); 078 Collections.reverse(Arrays.asList(referenceReversed)); 079 Diff.Change scriptReversed = new Diff(referenceReversed, current).diff2(false); 080 if (scriptReversed == null /* reference and current are identical */ 081 || (script != null && scriptReversed.getTotalNumberOfChanges() < script.getTotalNumberOfChanges())) { 082 this.referenceReversed = true; 083 twoColumnDiffFromScript(scriptReversed, referenceReversed, current, true); 084 } else { 085 this.referenceReversed = false; 086 twoColumnDiffFromScript(script, reference, current, false); 087 } 088 } 089 090 /** 091 * The result from the diff algorithm is a "script" (a compressed description of the changes) 092 * This method expands this script into a full two column description. 093 * @param script diff script 094 * @param a reference version 095 * @param b current version 096 * @param reversed if {@code true} use {@link DiffItemType#REVERSED} instead of {@link DiffItemType#SAME} 097 */ 098 private void twoColumnDiffFromScript(Diff.Change script, Object[] a, Object[] b, final boolean reversed) { 099 int ia = 0; 100 int ib = 0; 101 102 while (script != null) { 103 int deleted = script.deleted; 104 int inserted = script.inserted; 105 while (ia < script.line0 && ib < script.line1) { 106 referenceDiff.add(new Item(reversed ? DiffItemType.REVERSED : DiffItemType.SAME, a[ia++])); 107 currentDiff.add(new Item(DiffItemType.SAME, b[ib++])); 108 } 109 110 while (inserted > 0 || deleted > 0) { 111 if (inserted > 0 && deleted > 0) { 112 referenceDiff.add(new Item(DiffItemType.CHANGED, a[ia++])); 113 currentDiff.add(new Item(DiffItemType.CHANGED, b[ib++])); 114 } else if (inserted > 0) { 115 referenceDiff.add(new Item(DiffItemType.EMPTY, null)); 116 currentDiff.add(new Item(DiffItemType.INSERTED, b[ib++])); 117 } else { 118 referenceDiff.add(new Item(DiffItemType.DELETED, a[ia++])); 119 currentDiff.add(new Item(DiffItemType.EMPTY, null)); 120 } 121 inserted--; 122 deleted--; 123 } 124 script = script.link; 125 } 126 while (ia < a.length && ib < b.length) { 127 referenceDiff.add(new Item(reversed ? DiffItemType.REVERSED : DiffItemType.SAME, a[ia++])); 128 currentDiff.add(new Item(DiffItemType.SAME, b[ib++])); 129 } 130 } 131}