ListDiff is useful for situations where some structure (such as a user interface) is shadowing a changing list, and you don't want to rebuild the structure from scratch every time the list changes -- perhaps beacuse the cost of recreating the structure is high, or because you don't want to lose state information about existing elements whose position has changed in the list.
The algorithm ListDiff uses for generating the steps is quite simple. It does
not guarantee the shortest possible sequence of steps, but usually comes quite
close.
@author Paul Cantrell
@version [Development version]
*/
public class ListDiff
extends CollectionDiff
{
/** For testing */
public static void main(String[] args)
throws Exception
{
while(true)
{
System.out.println();
System.out.println();
java.io.BufferedReader in = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
List a = new LinkedList(), b = new LinkedList();
System.out.print("Old: ");
StringTokenizer st = new StringTokenizer(in.readLine());
while(st.hasMoreTokens())
a.add(st.nextToken());
System.out.print("New: ");
st = new StringTokenizer(in.readLine());
while(st.hasMoreTokens())
b.add(st.nextToken());
for(Iterator i = (new ListDiff(a, b)).getSteps(); i.hasNext(); )
System.out.println(i.next());
}
}
/** Prepares a comparison of two lists. */
public ListDiff(List oldStuff, List newStuff)
{
super(oldStuff, newStuff, true);
this.oldStuff = oldStuff;
this.newStuff = newStuff;
calculateSteps();
}
/** Returns a sequence of steps which transform the old list into the new.
* The Iterator returns {@link ListDiff.Step} objects. */
public Iterator/*index is now at index+1. */
public class Insert extends Step
{
public Insert(Object object, int index)
{ super(object, index); }
public String toString()
{ return "Insert " + getObject() + " at position " + getIndex(); }
}
/** A list transformation step: remove an object at a given position.
* After the step, the length of the list has decreased by one. */
public class Remove extends Step
{
public Remove(Object object,int index)
{ super(object, index); }
public String toString()
{ return "Remove " + getObject() + " at position " + getIndex(); }
}
/** A list transformation step: move an object from one position to another.
* Before the move, object is at index;
* after the move, object is at toIndex.
* Items in the list between index and toIndex shift
* over one position to accomodate the move. */
public class Move extends Step
{
public Move(Object object, int index, int toIndex)
{
super(object, index);
this.toIndex = toIndex;
}
public int getToIndex()
{ return toIndex; }
public String toString()
{ return "Insert " + getObject() + " from position " + getIndex() + " to " + getToIndex(); }
private int toIndex;
}
private void calculateSteps()
{
// We transform oldWork to look like newWork one step at a time.
// At step i, the first i positions of the two lists match.
// We could generate a shorter transformation list by being
// cleverer, but we're not, and so we don't.
steps = new LinkedList();
List
oldWork = new ArrayList(oldStuff),
newWork = new ArrayList(newStuff);
int curPos;
for(curPos = 0; curPos < oldWork.size() && curPos < newWork.size(); curPos++)
{
// Look for next object from new list in old list
Object nextObject = newWork.get(curPos);
int oldPos = -1;
for(int j = curPos; j < oldWork.size(); j++)
if(oldWork.get(j).equals(nextObject))
{
oldPos = j;
break;
}
if(oldPos == -1)
{
// Didn't find new object, so insert it
steps.add(new Insert(nextObject, curPos));
oldWork.add(curPos, nextObject);
}
else if(curPos != oldPos)
{
// Found new object in old list, so move it
steps.add(new Move(nextObject, oldPos, curPos));
oldWork.remove(oldPos);
oldWork.add(curPos, nextObject);
}
}
// If objects remain only in new, insert them
for(; curPos < newWork.size(); curPos++)
steps.add(new Insert(newWork.get(curPos), curPos));
// If objects remain only in old, remove them
for(int j = curPos; j < oldWork.size(); j++)
steps.add(new Remove(oldWork.get(curPos), curPos));
}
private List oldStuff, newStuff, steps;
}