001 // License: GPL. For details, see LICENSE file. 002 package org.openstreetmap.josm.gui.history; 003 /// Feel free to move me somewhere else. Maybe a bit specific for josm.tools? 004 005 import java.util.ArrayList; 006 007 import org.openstreetmap.josm.tools.Diff; 008 009 /** 010 * Produces a "two column diff" of two lists. (same as diff -y) 011 * 012 * Each list is annotated with the changes relative to the other, and "empty" cells are inserted so the lists are comparable item by item. 013 * 014 * diff on [1 2 3 4] [1 a 4 5] yields: 015 * 016 * item(SAME, 1) item(SAME, 1) 017 * item(CHANGED, 2) item(CHANGED, 2) 018 * item(DELETED, 3) item(EMPTY) 019 * item(SAME, 4) item(SAME, 4) 020 * item(EMPTY) item(INSERTED, 5) 021 * 022 * @author olejorgenb 023 */ 024 class TwoColumnDiff { 025 public static class Item { 026 public static final int INSERTED = 1; 027 public static final int DELETED = 2; 028 public static final int CHANGED = 3; 029 public static final int SAME = 4; 030 public static final int EMPTY = 5; // value should be null 031 public Item(int state, Object value) { 032 this.state = state; 033 this.value = state == EMPTY ? null : value; 034 } 035 036 public final Object value; 037 public final int state; 038 } 039 040 public ArrayList<Item> referenceDiff; 041 public ArrayList<Item> currentDiff; 042 Object[] reference; 043 Object[] current; 044 045 /** 046 * The arguments will _not_ be modified 047 */ 048 public TwoColumnDiff(Object[] reference, Object[] current) { 049 this.reference = reference; 050 this.current = current; 051 referenceDiff = new ArrayList<Item>(); 052 currentDiff = new ArrayList<Item>(); 053 diff(); 054 } 055 private void diff() { 056 Diff diff = new Diff(reference, current); 057 Diff.change script = diff.diff_2(false); 058 twoColumnDiffFromScript(script, reference, current); 059 } 060 061 /** 062 * The result from the diff algorithm is a "script" (a compressed description of the changes) 063 * This method expands this script into a full two column description. 064 */ 065 private void twoColumnDiffFromScript(Diff.change script, Object[] a, Object[] b) { 066 int ia = 0; 067 int ib = 0; 068 069 while(script != null) { 070 int deleted = script.deleted; 071 int inserted = script.inserted; 072 while(ia < script.line0 && ib < script.line1){ 073 // System.out.println(" "+a[ia] + "\t "+b[ib]); 074 Item cell = new Item(Item.SAME, a[ia]); 075 referenceDiff.add(cell); 076 currentDiff.add(cell); 077 ia++; 078 ib++; 079 } 080 081 while(inserted > 0 || deleted > 0) { 082 if(inserted > 0 && deleted > 0) { 083 // System.out.println("="+a[ia] + "\t="+b[ib]); 084 referenceDiff.add(new Item(Item.CHANGED, a[ia++])); 085 currentDiff.add(new Item(Item.CHANGED, b[ib++])); 086 } else if(inserted > 0) { 087 // System.out.println("\t+" + b[ib]); 088 referenceDiff.add(new Item(Item.EMPTY, null)); 089 currentDiff.add(new Item(Item.INSERTED, b[ib++])); 090 } else if(deleted > 0) { 091 // System.out.println("-"+a[ia]); 092 referenceDiff.add(new Item(Item.DELETED, a[ia++])); 093 currentDiff.add(new Item(Item.EMPTY, null)); 094 } 095 inserted--; 096 deleted--; 097 } 098 script = script.link; 099 } 100 while(ia < a.length && ib < b.length) { 101 // System.out.println((ia < a.length ? " "+a[ia]+"\t" : "\t") + (ib < b.length ? " "+b[ib] : "")); 102 referenceDiff.add(new Item(Item.SAME, a[ia++])); 103 currentDiff.add(new Item(Item.SAME, b[ib++])); 104 } 105 } 106 }