2009-05-06T03:04:34Z
1545
Home
12
5777
= List Diffs =
This is a simple library which has been used in <a href="http://netbeans.org">NetBeans</a> for years. It does one thing: Generate Diffs between two <code>java.util.List</code> instances.
Why is that useful? There are many APIs that take <code>List</code>s and it is not uncommon to write code that wants to respond to updates to a list. Typically this ends up being handled by creating wrapper lists, or observable list subclasses. But sometimes you are being given a list by a library you are calling - you cannot change the type of it, or wrap it in a List implementation that will tell you about mutations to the list.
That's where this library comes in.
== Usage ==
There are two classes and one enum to be concerned with:
* Diff - a diff encapsulates a set of changes. It has three methods
** <code>getOld()</code> gets the original ist
** <code>getNew()</code> gets the new list
** <code>getChanges()</code> gets a list of <code>Change</code> objects representing insertions, deletions and replacements indexed by start and end position
* Change - A change is an insertion, deletion or replacement. It has a start and end index. (Note that not all algorithms even have a concept of a replacement - any replacement can be accurately described as a deletion and an insertion - but the concept is more human-friendly).
* Algorithm - an enum of algorithms that the diff library can use to construct your diff
You get a Diff instance by calling one of the static methods of the Diff class, i.e.
<pre>
List<T> old, nue;
...
Diff diff = Diff.create (old, nue, Algorithm.ITERATIVE);
</pre>
== Swing JLists and the Diff Library ==
This library also includes a subproject, Swing List Diffs, which provides a <code>javax.swing.ListModel</code> that is driven by <code>java.util.List</code>s and internally uses the Diff library to generate <code>ListModelEvent</code>. Creating a JList that shows the contents of a <code>List</code> is as simple as
<pre>JDiffList theJList = new JDiffList (someList);</pre>
and updating it is as simple as
<pre>theJList.setModel (someOtherList);</pre>
Rather than tracking changes in one list, you simply pass in a new list when you want to change the contents of the JList's model. The model will preserve selection and fire appropriate events based on what changes have occurred.
Note there is no requirement to use <code>JDiffList</code> - you can use any <code>JList</code> and a <code>ListListModel</code> as its model. <code>JDiffList</code> simply contains some convenience methods, uses a generic type parameter so you can get the selection without having to cast, and has some protections against accidentally being passed a standard Swing <code>ListModel</code> or the wrong object type.
== Limitations of Diffs ==
This library is not a solution for all problems. Creating a diff between two lists means iterating every element of both lists at least once, usually more times. If you are dealing with lists of thousands of elements, probably you need a solution where whatever is creating the lists tells you about the changes made, rather than using a diff to figure out what happened ex-post-facto. Diffing is a problem that by definition, does not scale well. Used judiciously, however, it can save programming time and solve a certain subset of problems where you simply cannot find out what happened to one list without comparing it with another one.
Diffs are by definition fuzzy. Say that you have the sequence ''A,B,C,D,E''. You are given a new sequence, ''A,X,D,E''. The changes can be described in a number of ways, each accurate - and different diff algorithms will produce different results:
* B and C were deleted at index 1. X was inserted at index 1.
* B was replaced with X at index 1. C was deleted.
* C was replaced with X at index 2. B was deleted.
* A,B,C,D,E was replaced with A,X,D,E
Which one is the truth? What '''really''' happened?
A computer will never tell you.
The definition of an accurate diff is that it can be reversed and produce the original sequence. There is no ''what really happened'' in the world of diffs, only accuracy, which in practice means that the diff can be reversed. Different algorithms have different trade-offs of performance versus how minimal a diff they generate, and what patterns of mutations they work best with, either in terms of performance or resulting diff complexity.
If you find this topic interesting, a much more thorough discussion can be found [http://en.wikipedia.org/wiki/Longest_common_subsequence_problem in Wikipedia].
== Algorithms ==
There are currently two algroithms implemented:
* ''Iterative'' - This is a relatively fast diff algorithm for cases where there are typically a few insertions or deletions, not wholesale reordering of the list contents. It has the drawback that it does not tolerate duplicate elements in the lists it is diffing. It essentially just runs two iterators in parallel, continuing with one when a difference is encountered until it encounters the same element the other is on. Performance will fall off with the complexity of the diff. This algorithm will not be found in any academic paper, but was the result of the [http://weblogs.java.net/blog/timboudreau/ original project author] thinking way too hard about the problem for far too long.
* ''Longest Common Subsequence'' - Martin Matula, Tomas Hurka and Pavel Flaska's implementation from the NetBeans Java module, adapted to the Diff API. Origin of the specific algorithm used is unknown. Tolerates duplicates and performs reasonably.
Contributions of other diff algorithms (with tests!) are welcome.
== Proving Accuracy ==
The following code should work with any implementation of Diff to prove that it is accurate. What it does is simply make a copy of the original list, perform all of the changes the diff describes to that original list, and compare the result with the new list the diff describes.
<pre>
List <T> list = new ArrayList<T> (diff.getOld());
List <T> target = diff.getNew();
List <Change> changes = diff.getChanges();
for (Change change : changes) {
int start = change.getStart();
int end = change.getEnd();
switch (change.getType()) {
case Change.CHANGE :
for (int i=start; i <= end; i++) {
list.set (i, target.get(i));
}
break;
case Change.INSERT :
int ct = 0;
for (int i=end; i >= start; i--) {
Object o = target.get(i);
list.add(start, o);
}
break;
case Change.DELETE :
for (int i=end; i >= start; i--) {
list.remove(i);
}
break;
}
}
assert list.equals(target);
</pre>
The minimal requirement for any new algorithm implementations is that they come with a test that shows that the above code works for lists of reasonable complexity.
== History ==
This library was originally created by Tim Boudreau as part of the Navigator component in NetBeans 4.0 - as the user edits a file, the list of class members changes. The Java parser hands out a new list of class members (fields, methods, etc.); the only way to determine what changed is to compare it with the previous list. It is also used in the <a href="http://nbwicketsupport.dev.java.net">NetBeans Wicket Support</a> plugin, to compare trees of wicket IDs in HTML markup with trees of wicket IDs in Java source code, to determine if the Java component hierarchy matches the HTML tag hierarchy; it is also used in miscellaneous other projects.
<h1><a name='List_Diffs'></a> List Diffs </h1>
<p>
This is a simple library which has been used in <a href="http://netbeans.org">NetBeans</a> for years. It does one thing: Generate Diffs between two <code>java.util.List</code> instances.
</p><p>Why is that useful? There are many APIs that take <code>List</code>s and it is not uncommon to write code that wants to respond to updates to a list. Typically this ends up being handled by creating wrapper lists, or observable list subclasses. But sometimes you are being given a list by a library you are calling - you cannot change the type of it, or wrap it in a List implementation that will tell you about mutations to the list.
</p><p>That's where this library comes in.
</p><h2><a name='Usage'></a> Usage </h2>
<p>There are two classes and one enum to be concerned with:
</p><ul><li> Diff - a diff encapsulates a set of changes. It has three methods
<ul><li> <code>getOld()</code> gets the original ist
</li><li> <code>getNew()</code> gets the new list
</li><li> <code>getChanges()</code> gets a list of <code>Change</code> objects representing insertions, deletions and replacements indexed by start and end position
</li></ul></li><li> Change - A change is an insertion, deletion or replacement. It has a start and end index. (Note that not all algorithms even have a concept of a replacement - any replacement can be accurately described as a deletion and an insertion - but the concept is more human-friendly).
</li><li> Algorithm - an enum of algorithms that the diff library can use to construct your diff
</li></ul><p>
You get a Diff instance by calling one of the static methods of the Diff class, i.e.
<pre>
List<T> old, nue;
...
Diff diff = Diff.create (old, nue, Algorithm.ITERATIVE);
</pre>
</p><h2><a name='Swing_JLists_and_the_Diff_Library'></a> Swing JLists and the Diff Library </h2>
<p>This library also includes a subproject, Swing List Diffs, which provides a <code>javax.swing.ListModel</code> that is driven by <code>java.util.List</code>s and internally uses the Diff library to generate <code>ListModelEvent</code>. Creating a JList that shows the contents of a <code>List</code> is as simple as
<pre>JDiffList theJList = new JDiffList (someList);</pre>
and updating it is as simple as
<pre>theJList.setModel (someOtherList);</pre>
</p><p>Rather than tracking changes in one list, you simply pass in a new list when you want to change the contents of the JList's model. The model will preserve selection and fire appropriate events based on what changes have occurred.
</p><p>Note there is no requirement to use <code>JDiffList</code> - you can use any <code>JList</code> and a <code>ListListModel</code> as its model. <code>JDiffList</code> simply contains some convenience methods, uses a generic type parameter so you can get the selection without having to cast, and has some protections against accidentally being passed a standard Swing <code>ListModel</code> or the wrong object type.
</p><h2><a name='Limitations_of_Diffs'></a> Limitations of Diffs </h2>
<p>
This library is not a solution for all problems. Creating a diff between two lists means iterating every element of both lists at least once, usually more times. If you are dealing with lists of thousands of elements, probably you need a solution where whatever is creating the lists tells you about the changes made, rather than using a diff to figure out what happened ex-post-facto. Diffing is a problem that by definition, does not scale well. Used judiciously, however, it can save programming time and solve a certain subset of problems where you simply cannot find out what happened to one list without comparing it with another one.
</p><p>Diffs are by definition fuzzy. Say that you have the sequence <i>A,B,C,D,E</i>. You are given a new sequence, <i>A,X,D,E</i>. The changes can be described in a number of ways, each accurate - and different diff algorithms will produce different results:
</p><ul><li> B and C were deleted at index 1. X was inserted at index 1.
</li><li> B was replaced with X at index 1. C was deleted.
</li><li> C was replaced with X at index 2. B was deleted.
</li><li> A,B,C,D,E was replaced with A,X,D,E
</li></ul><p>Which one is the truth? What <b>really</b> happened?
</p><p>A computer will never tell you.
</p><p>The definition of an accurate diff is that it can be reversed and produce the original sequence. There is no <i>what really happened</i> in the world of diffs, only accuracy, which in practice means that the diff can be reversed. Different algorithms have different trade-offs of performance versus how minimal a diff they generate, and what patterns of mutations they work best with, either in terms of performance or resulting diff complexity.
</p><p>If you find this topic interesting, a much more thorough discussion can be found <a class='external' href="http://en.wikipedia.org/wiki/Longest_common_subsequence_problem">in Wikipedia</a>.
</p><h2><a name='Algorithms'></a> Algorithms </h2>
<p>
There are currently two algroithms implemented:
</p><ul><li> <i>Iterative</i> - This is a relatively fast diff algorithm for cases where there are typically a few insertions or deletions, not wholesale reordering of the list contents. It has the drawback that it does not tolerate duplicate elements in the lists it is diffing. It essentially just runs two iterators in parallel, continuing with one when a difference is encountered until it encounters the same element the other is on. Performance will fall off with the complexity of the diff. This algorithm will not be found in any academic paper, but was the result of the <a class='external' href="http://weblogs.java.net/blog/timboudreau/">original project author</a> thinking way too hard about the problem for far too long.
</li><li> <i>Longest Common Subsequence</i> - Martin Matula, Tomas Hurka and Pavel Flaska's implementation from the NetBeans Java module, adapted to the Diff API. Origin of the specific algorithm used is unknown. Tolerates duplicates and performs reasonably.
</li></ul><p>
Contributions of other diff algorithms (with tests!) are welcome.
</p><h2><a name='Proving_Accuracy'></a> Proving Accuracy </h2>
<p>
The following code should work with any implementation of Diff to prove that it is accurate. What it does is simply make a copy of the original list, perform all of the changes the diff describes to that original list, and compare the result with the new list the diff describes.
<pre>
List &lt;T&gt; list = new ArrayList&lt;T&gt; (diff.getOld());
List &lt;T&gt; target = diff.getNew();
List &lt;Change&gt; changes = diff.getChanges();
for (Change change : changes) {
int start = change.getStart();
int end = change.getEnd();
switch (change.getType()) {
case Change.CHANGE :
for (int i=start; i <= end; i++) {
list.set (i, target.get(i));
}
break;
case Change.INSERT :
int ct = 0;
for (int i=end; i >= start; i--) {
Object o = target.get(i);
list.add(start, o);
}
break;
case Change.DELETE :
for (int i=end; i >= start; i--) {
list.remove(i);
}
break;
}
}
assert list.equals(target);
</pre>
The minimal requirement for any new algorithm implementations is that they come with a test that shows that the above code works for lists of reasonable complexity.
</p><h2><a name='History'></a> History </h2>
<p>This library was originally created by Tim Boudreau as part of the Navigator component in NetBeans 4.0 - as the user edits a file, the list of class members changes. The Java parser hands out a new list of class members (fields, methods, etc.); the only way to determine what changed is to compare it with the previous list. It is also used in the <a href="http://nbwicketsupport.dev.java.net">NetBeans Wicket Support</a> plugin, to compare trees of wicket IDs in HTML markup with trees of wicket IDs in Java source code, to determine if the Java component hierarchy matches the HTML tag hierarchy; it is also used in miscellaneous other projects.</p>
2009-05-06T04:27:27Z
6333