org.wings.util
Class EditTranscriptGenerator

java.lang.Object
  org.wings.util.EditTranscriptGenerator

public final class EditTranscriptGenerator
extends Object

This class takes two Strings an generates the shortes list of necessarry change operations to transform the source string into the target string.

For more information about the used algorithm refer to:

• http://www.merriampark.com/ld.htm
• http://www.msci.memphis.edu/~giri/compbio/f99/ningxu/NOTE10.html
• http://www.itu.dk/courses/AVA/E2005/StringEditDistance.pdf

Original source extracted from Glazed Lists (http://publicobject.com/glazedlists/) Implementation of Eugene W. Myer's paper, "An O(ND) Difference Algorithm and Its Variations", the same algorithm found in GNU diff.

Note that this is a cleanroom implementation of this popular algorithm that is particularly suited for the Java programmer. The variable names are descriptive and the approach is more object-oriented than Myer's sample algorithm.

Author:

Jesse Wilson

Constructor Summary

EditTranscriptGenerator()

Method Summary

static List

generateEvents(String source, String target) Generates the shorted edit transcript needed to transform the source String into the target String.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

EditTranscriptGenerator

public EditTranscriptGenerator()

Method Detail

generateEvents

public static List generateEvents(String source,
                                  String target)

Generates the shorted edit transcript needed to transform the source String into the target String. The needed changes are noted down as DocumentEvents.

Returns:

A list of DocumentEvents either of type DocumentEvent.EventType.INSERT or DocumentEvent.EventType.REMOVE with correct sourceIndexes and lengths.