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.List; 008 009import org.openstreetmap.josm.gui.history.TwoColumnDiff.Item.DiffItemType; 010import org.openstreetmap.josm.tools.Diff; 011import org.openstreetmap.josm.tools.Utils; 012 013/** 014 * Produces a "two column diff" of two lists. (same as diff -y) 015 * 016 * Each list is annotated with the changes relative to the other, and "empty" cells are inserted so the lists are comparable item by item. 017 * 018 * diff on [1 2 3 4] [1 a 4 5] yields: 019 * 020 * item(SAME, 1) item(SAME, 1) 021 * item(CHANGED, 2) item(CHANGED, 2) 022 * item(DELETED, 3) item(EMPTY) 023 * item(SAME, 4) item(SAME, 4) 024 * item(EMPTY) item(INSERTED, 5) 025 * 026 * @author olejorgenb 027 */ 028class TwoColumnDiff { 029 public static class Item { 030 031 public enum DiffItemType { 032 INSERTED(new Color(0xDD, 0xFF, 0xDD)), DELETED(new Color(255,197,197)), CHANGED(new Color(255,234,213)), 033 SAME(new Color(234,234,234)), EMPTY(new Color(234,234,234)); 034 035 private final Color color; 036 private DiffItemType(Color color) { 037 this.color = color; 038 } 039 public Color getColor() { 040 return color; 041 } 042 } 043 044 public Item(DiffItemType state, Object value) { 045 this.state = state; 046 this.value = state == DiffItemType.EMPTY ? null : value; 047 } 048 049 public final Object value; 050 public final DiffItemType state; 051 } 052 053 public List<Item> referenceDiff; 054 public List<Item> currentDiff; 055 Object[] reference; 056 Object[] current; 057 058 public TwoColumnDiff(Object[] reference, Object[] current) { 059 this.reference = Utils.copyArray(reference); 060 this.current = Utils.copyArray(current); 061 referenceDiff = new ArrayList<Item>(); 062 currentDiff = new ArrayList<Item>(); 063 diff(); 064 } 065 066 private void diff() { 067 Diff diff = new Diff(reference, current); 068 Diff.Change script = diff.diff_2(false); 069 twoColumnDiffFromScript(script, reference, current); 070 } 071 072 /** 073 * The result from the diff algorithm is a "script" (a compressed description of the changes) 074 * This method expands this script into a full two column description. 075 */ 076 private void twoColumnDiffFromScript(Diff.Change script, Object[] a, Object[] b) { 077 int ia = 0; 078 int ib = 0; 079 080 while(script != null) { 081 int deleted = script.deleted; 082 int inserted = script.inserted; 083 while(ia < script.line0 && ib < script.line1){ 084 Item cell = new Item(DiffItemType.SAME, a[ia]); 085 referenceDiff.add(cell); 086 currentDiff.add(cell); 087 ia++; 088 ib++; 089 } 090 091 while(inserted > 0 || deleted > 0) { 092 if(inserted > 0 && deleted > 0) { 093 referenceDiff.add(new Item(DiffItemType.CHANGED, a[ia++])); 094 currentDiff.add(new Item(DiffItemType.CHANGED, b[ib++])); 095 } else if(inserted > 0) { 096 referenceDiff.add(new Item(DiffItemType.EMPTY, null)); 097 currentDiff.add(new Item(DiffItemType.INSERTED, b[ib++])); 098 } else if(deleted > 0) { 099 referenceDiff.add(new Item(DiffItemType.DELETED, a[ia++])); 100 currentDiff.add(new Item(DiffItemType.EMPTY, null)); 101 } 102 inserted--; 103 deleted--; 104 } 105 script = script.link; 106 } 107 while(ia < a.length && ib < b.length) { 108 referenceDiff.add(new Item(DiffItemType.SAME, a[ia++])); 109 currentDiff.add(new Item(DiffItemType.SAME, b[ib++])); 110 } 111 } 112}