This is one of the implementations of DiffAlgorithm interface. More...

Inheritance diagram for org.openoffice.xmerge.merger.diff.IteratorLCSAlgorithm:

Collaboration diagram for org.openoffice.xmerge.merger.diff.IteratorLCSAlgorithm:

Public Member Functions
Difference[]	computeDiffs (Iterator orgSeq, Iterator modSeq)
	Returns a `Difference` array. More...

Difference[]	computeDiffs (Iterator orgSeq, Iterator modSeq)
	Returns a `Difference` array. More...

Private Member Functions
void	printDiffTable (int[][] diffTable)
	Debug function used to print out the nicely formatted difference table. More...

int[][]	createDiffTable (Iterator orgSeq, Iterator modSeq)
	Create the difference table. More...

void	generateResult (int[][] diffTable, int i, int j, ArrayList< Difference > diffVector)
	Generate the `Difference` object result vector. More...

Detailed Description

This is one of the implementations of DiffAlgorithm interface.

Using Longest Common Subsequence (LCS). The algorithm here is based on the book "Introduction to Algorithms" by Thomas H.Cormen, Charles E.Leiserson and Ronald L.Riverst (MIT Press 1990) page 314.

Definition at line 34 of file IteratorLCSAlgorithm.java.

Member Function Documentation

◆ computeDiffs()

Difference[] org.openoffice.xmerge.merger.diff.IteratorLCSAlgorithm.computeDiffs	(	Iterator	orgSeq,
		Iterator	modSeq
	)

inline

Returns a Difference array.

This method finds out the difference between two sequences.

Parameters

orgSeq	The original sequence of object.
modSeq	The modified (or changed) sequence to compare against with the original.

Returns: A Difference array.

Implements org.openoffice.xmerge.merger.DiffAlgorithm.

Definition at line 36 of file IteratorLCSAlgorithm.java.

References org.openoffice.xmerge.merger.diff.IteratorLCSAlgorithm.createDiffTable(), org.openoffice.xmerge.merger.Iterator.elementCount(), org.openoffice.xmerge.merger.diff.IteratorLCSAlgorithm.generateResult(), org.openoffice.xmerge.util.Debug.INFO, org.openoffice.xmerge.util.Debug.isFlagSet(), and org.openoffice.xmerge.merger.diff.IteratorLCSAlgorithm.printDiffTable().

◆ createDiffTable()

int[][] org.openoffice.xmerge.merger.diff.IteratorLCSAlgorithm.createDiffTable	(	Iterator	orgSeq,
		Iterator	modSeq
	)

inlineprivate

Create the difference table.

The difference table is used internal to keep track what elements are common or different in the two sequences.

Parameters

orgSeq	The original sequence to be used as a base.
modSeq	The modified sequence to compare.

Returns: A difference table as a two-dimensional array of integers.

Definition at line 89 of file IteratorLCSAlgorithm.java.

References org.openoffice.xmerge.merger.Iterator.elementCount(), org.openoffice.xmerge.merger.Iterator.equivalent(), i, org.openoffice.xmerge.merger.Iterator.next(), Object, and org.openoffice.xmerge.merger.Iterator.start().

Referenced by org.openoffice.xmerge.merger.diff.IteratorLCSAlgorithm.computeDiffs().

◆ generateResult()

void org.openoffice.xmerge.merger.diff.IteratorLCSAlgorithm.generateResult	(	int	diffTable[][],
		int	i,
		int	j,
		ArrayList< Difference >	diffVector
	)

inlineprivate

Generate the Difference object result vector.

This method will be called recursively to backtrack the difference table to get the difference result (and also the LCS).

Parameters

diffTable	The difference table containing the `Difference` result.
i	The nth element in original sequence to compare. This method is called recursively with `i` and `j` decreased until `0`.
j	The nth element in modified sequence to compare.
diffVector	A vector to output the `Difference` result. Can not use a return variable as it is a recursive method. The vector will contain `Difference` objects with operation and positions fill in.