commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jua...@apache.org
Subject cvs commit: jakarta-commons-sandbox/jrcs/src/test/org/apache/commons/jrcs/diff DiffTest.java
Date Mon, 05 May 2003 21:49:29 GMT
juanco      2003/05/05 14:49:29

  Modified:    jrcs     build.xml jrcs.jpx
               jrcs/src/java/org/apache/commons/jrcs overview.html
               jrcs/src/java/org/apache/commons/jrcs/diff Chunk.java
                        DeleteDelta.java Delta.java Diff.java Revision.java
               jrcs/src/test/org/apache/commons/jrcs/diff DiffTest.java
  Added:       jrcs/src/java/org/apache/commons/jrcs/diff
                        DiffAlgorithm.java DiffAlgorithmBound.java
                        SimpleDiff.java SimpleDiffBound.java
  Log:
  Contributions by Brian McBride <bwm@hplb.hpl.hp.com>
  
  Implemented the Algorithm pattern to make the Diff class independent of the
  particular implementation.
  
  Implemented the visitor pattern over Revisions and Deltas to allow for
  different functionality in traversals of a revision.
  
  Revision  Changes    Path
  1.9       +1 -2      jakarta-commons-sandbox/jrcs/build.xml
  
  Index: build.xml
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/build.xml,v
  retrieving revision 1.8
  retrieving revision 1.9
  diff -u -r1.8 -r1.9
  --- build.xml	23 Apr 2003 23:32:09 -0000	1.8
  +++ build.xml	5 May 2003 21:49:28 -0000	1.9
  @@ -179,7 +179,6 @@
              debug="on" optimize="on" deprecation="on" >
              <include name="**/jrcs/diff/**/*.java" />
              <include name="**/jrcs/util/**/*.java" />
  -           <include name="**/jrcs/tools/**/*.java" />
         <exclude name="**/*Test*.class" />
       </javac>
   
  @@ -266,7 +265,7 @@
   				 author="true"
                version="true" 
                private="yes"
  -             overview="java/org/apache/commons/jrcs/overview.html"
  +             overview="${java.dir}/org/apache/commons/jrcs/overview.html"
   				 windowtitle="${app.name} API"
       		    doctitle="${app.name}"
                bottom="Copyright 2002 the Apache Software Foundation&lt;br&gt;
  
  
  
  1.4       +2 -8      jakarta-commons-sandbox/jrcs/jrcs.jpx
  
  Index: jrcs.jpx
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/jrcs.jpx,v
  retrieving revision 1.3
  retrieving revision 1.4
  diff -u -r1.3 -r1.4
  --- jrcs.jpx	28 Apr 2003 22:00:38 -0000	1.3
  +++ jrcs.jpx	5 May 2003 21:49:28 -0000	1.4
  @@ -10,17 +10,11 @@
     <property category="javaFormatting" name="packageThreshold" value="4"/>
     <property category="javaFormatting" name="throwsOnNewLine" value="1"/>
     <property category="javadoc" name="custom.tags.1" value="todo;a;To Do:"/>
  -  <property category="runtime" name="ConfigurationCount" value="1"/>
  -  <property category="runtime" name="DefaultConfiguration" value="1"/>
  +  <property category="runtime" name="DefaultConfiguration" value="-1"/>
     <property category="runtime.0" name="ConfigurationName" value="AllTests"/>
     <property category="runtime.0" name="RunnableType" value="com.borland.jbuilder.runtime.TestRunner"/>
     <property category="runtime.0" name="test.class" value="org.apache.commons.jrcs.AllTests"/>
     <property category="runtime.0" name="test.harness" value="com.borland.jbuilder.unittest.JBTestRunner"/>
  -  <property category="runtime.1" name="BuildTargetOnRun" value="com.borland.jbuilder.build.ProjectBuilder$ProjectBuildAction;make"/>
  -  <property category="runtime.1" name="ConfigurationName" value="JDiff"/>
  -  <property category="runtime.1" name="RunnableType" value="com.borland.jbuilder.runtime.ApplicationRunner"/>
  -  <property category="runtime.1" name="application.class" value="org.apache.commons.jrcs.tools.JDiff"/>
  -  <property category="runtime.1" name="application.parameters" value="\tmp\jdifftest\CommandCentral1.java \tmp\jdifftest\CommandCentral2.java"/>
     <property category="serverservices" name="disabled.services" value="connector;jdatastore"/>
     <property category="serverservices" name="single.server.name" value="Tomcat 4.0"/>
     <property category="sys" name="AuthorLabel" value="@author"/>
  @@ -39,7 +33,7 @@
     <property category="sys" name="InstanceVisibility" value="2"/>
     <property category="sys" name="JDK" value="java version 1.4.1_02-b06"/>
     <property category="sys" name="LastTag" value="0"/>
  -  <property category="sys" name="Libraries" value="JUnit;Jakarta ORO"/>
  +  <property category="sys" name="Libraries" value="JUnit;Jakarta ORO Regexp"/>
     <property category="sys" name="MakeStable" value="0"/>
     <property category="sys" name="OutPath" value="classes"/>
     <property category="sys" name="SourcePath" value="src/java;src/test"/>
  
  
  
  1.2       +4 -4      jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/overview.html
  
  Index: overview.html
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/overview.html,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- overview.html	28 May 2002 16:45:43 -0000	1.1
  +++ overview.html	5 May 2003 21:49:28 -0000	1.2
  @@ -75,17 +75,17 @@
         tests.
       </p>
       <p>
  -      The {@link org.apache.maven.jrcs.diff diff} package implements
  +      The {@link org.apache.commons.jrcs.diff diff} package implements
         the differencing engine that JRCS uses. The engine has the power
         of Unix diff, is simple to understand, and can be used
         independently of the archive handling functionality. The entry
         point to the differencing engine is class {@link
  -      org.apache.maven.jrcs.diff.Diff Diff}.
  +      org.apache.commons.jrcs.diff.Diff Diff}.
       </p>
       <p>
  -      The {@link org.apache.maven.jrcs.rcs rcs} package implements th8e
  +      The {@link org.apache.commons.jrcs.rcs rcs} package implements th8e
         archive handling functionality. The entry point to the library is
  -      class {@link org.apache.maven.jrcs.rcs.Archive Archive}.
  +      class {@link org.apache.commons.jrcs.rcs.Archive Archive}.
       </p>
       <p>
         <b>CAVEAT UTILITOR:</b> Do not make modifications to your
  
  
  
  1.2       +5 -11     jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/Chunk.java
  
  Index: Chunk.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/Chunk.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- Chunk.java	28 May 2002 16:45:44 -0000	1.1
  +++ Chunk.java	5 May 2003 21:49:28 -0000	1.2
  @@ -54,14 +54,13 @@
    * <http://www.apache.org/>.
    */
   
  -
   import java.util.ArrayList;
   import java.util.Arrays;
   import java.util.Iterator;
   import java.util.List;
   
   /**
  - * Holds a information about a parrt of the text involved in 
  + * Holds a information about a parrt of the text involved in
    * a differencing or patching operation.
    *
    * @version $Id$
  @@ -70,7 +69,7 @@
    * @see Delta
    */
   public class Chunk
  -        extends org.apache.commons.jrcs.util.ToString
  +    extends org.apache.commons.jrcs.util.ToString
   {
   
       protected int anchor;
  @@ -238,7 +237,7 @@
               target.remove(i);
           }
       }
  -    
  +
       /**
        * Add the text of this chunk to the target at the given position.
        * @param start where to add the text.
  @@ -262,7 +261,6 @@
           toString(s, "", "");
       }
   
  -
       /**
        * Provide a string image of the chunk using the given prefix and
        * postfix.
  @@ -316,7 +314,6 @@
           return slice(Arrays.asList(seq), pos, count);
       }
   
  -
       /**
        * Provide a string representation of the numeric range of this chunk.
        */
  @@ -354,7 +351,4 @@
               s.append(Integer.toString(rcsto()));
           }
       }
  -
  -    
  -}
  -
  +}
  \ No newline at end of file
  
  
  
  1.2       +6 -9      jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/DeleteDelta.java
  
  Index: DeleteDelta.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/DeleteDelta.java,v
  retrieving revision 1.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- DeleteDelta.java	28 May 2002 16:45:44 -0000	1.1
  +++ DeleteDelta.java	5 May 2003 21:49:28 -0000	1.2
  @@ -54,10 +54,8 @@
    * <http://www.apache.org/>.
    */
   
  -
   import java.util.List;
   
  -
   /**
    * Holds a delete-delta between to revisions of a text.
    *
  @@ -67,7 +65,8 @@
    * @see Diff
    * @see Chunk
    */
  -public class DeleteDelta extends Delta
  +public class DeleteDelta
  +    extends Delta
   {
   
       DeleteDelta()
  @@ -80,7 +79,8 @@
           init(orig, null);
       }
   
  -    public void verify(List target) throws PatchFailedException
  +    public void verify(List target)
  +        throws PatchFailedException
       {
           if (!original.verify(target))
           {
  @@ -110,7 +110,4 @@
           s.append(original.size());
           s.append(EOL);
       }
  -}
  -
  -
  -
  +}
  \ No newline at end of file
  
  
  
  1.3       +49 -14    jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/Delta.java
  
  Index: Delta.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/Delta.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- Delta.java	9 Oct 2002 13:43:35 -0000	1.2
  +++ Delta.java	5 May 2003 21:49:28 -0000	1.3
  @@ -59,24 +59,32 @@
   /**
    * Holds a "delta" difference between to revisions of a text.
    *
  - * @version $Id$
  + * @version $Revision$ $Date$
  + *
    * @author <a href="mailto:juanco@suigeneris.org">Juanco Anez</a>
  + * @author <a href="mailto:bwm@hplb.hpl.hp.com">Brian McBride</a>
    * @see Diff
    * @see Chunk
  + * @see Revision
  + *
  + * modifications
  + *
  + * 27 Apr 2003 bwm
  + *
  + * Added getOriginal() and getRevised() accessor methods
  + * Added visitor pattern accept() method
    */
   
   public abstract class Delta
  -        extends org.apache.commons.jrcs.util.ToString
  +    extends org.apache.commons.jrcs.util.ToString
   {
   
       protected Chunk original;
   
       protected Chunk revised;
   
  -
       static Class[][] DeltaClass;
   
  -
       static
       {
           DeltaClass = new Class[2][2];
  @@ -93,9 +101,8 @@
           }
       }
   
  -
       /**
  -     * Returns a Delta that corresponds to the given chunks in the 
  +     * Returns a Delta that corresponds to the given chunks in the
        * original and revised text respectively.
        * @param orig the chunk in the original text.
        * @param rev  the chunk in the revised text.
  @@ -103,7 +110,7 @@
       public static Delta newDelta(Chunk orig, Chunk rev)
       {
           Class c = DeltaClass[orig.size() > 0 ? 1 : 0]
  -                [rev.size() > 0  ? 1 : 0];
  +            [rev.size() > 0 ? 1 : 0];
           Delta result;
           try
           {
  @@ -124,7 +131,6 @@
       {
       }
   
  -
       /**
        * Creates a delta object with the given chunks from the original
        * and revised texts.
  @@ -134,7 +140,6 @@
           init(orig, rev);
       }
   
  -
       /**
        * Initializaes the delta with the given chunks from the original
        * and revised texts.
  @@ -145,20 +150,21 @@
           revised = rev;
       }
   
  -
       /**
        * Verifies that this delta can be used to patch the given text.
        * @param target the text to patch.
        * @throws PatchFailedException if the patch cannot be applied.
        */
  -    public abstract void verify(List target) throws PatchFailedException;
  +    public abstract void verify(List target)
  +        throws PatchFailedException;
   
       /**
        * Applies this delta as a patch to the given text.
        * @param target the text to patch.
        * @throws PatchFailedException if the patch cannot be applied.
        */
  -    public final void patch(List target) throws PatchFailedException
  +    public final void patch(List target)
  +        throws PatchFailedException
       {
           verify(target);
           try
  @@ -178,7 +184,6 @@
        */
       public abstract void applyTo(List target);
   
  -
       /**
        * Converts this delta into its Unix diff style string representation.
        * @param s a {@link StringBuffer StringBuffer} to which the string
  @@ -214,7 +219,37 @@
           toRCSString(s, EOL);
           return s.toString();
       }
  -}
   
  +    /**
  +     * Accessor method to return the chunk representing the original
  +     * sequence of items
  +     *
  +     * @return the original sequence
  +     */
  +    public Chunk getOriginal()
  +    {
  +        return original;
  +    }
   
  +    /**
  +     * Accessor method to return the chunk representing the updated
  +     * sequence of items.
  +     *
  +     * @return the updated sequence
  +     */
  +    public Chunk getRevised()
  +    {
  +        return revised;
  +    }
   
  +    /**
  +     * Accepts a visitor.
  +     * <p>
  +     * See the Visitor pattern in "Design Patterns" by the GOF4.
  +     * @param visitor The visitor.
  +     */
  +    public void accept(Revision.Visitor visitor)
  +    {
  +        visitor.visit(this);
  +    }
  +}
  
  
  
  1.7       +76 -263   jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/Diff.java
  
  Index: Diff.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/Diff.java,v
  retrieving revision 1.6
  retrieving revision 1.7
  diff -u -r1.6 -r1.7
  --- Diff.java	28 Apr 2003 22:03:59 -0000	1.6
  +++ Diff.java	5 May 2003 21:49:28 -0000	1.7
  @@ -66,312 +66,154 @@
   import java.util.Set;
   
   import org.apache.commons.jrcs.util.ToString;
  -import java.util.Iterator;
  -
   
   /**
    * Implements a differencing engine that works on arrays of {@link Object Object}.
    *
    * <p>Within this library, the word <i>text</i> means a unit of information
  - * subject to differencing.
  + * subject to version control.
    *
    * <p>Text is represented as <code>Object[]</code> because
  - * the diff engine is capable of handling more than plain ASCII. In fact,
  + * the diff engine is capable of handling more than plain ascci. In fact,
    * arrays of any type that implements
    * {@link java.lang.Object#hashCode hashCode()} and
    * {@link java.lang.Object#equals equals()}
    * correctly can be subject to differencing using this
    * library.</p>
    *
  + * <p>This library provides a framework in which different differencing
  + * algorithms may be used.  If no algorithm is specififed, a default
  + * algorithm is used.</p>
  + *
    * @version $Revision$ $Date$
    * @author <a href="mailto:juanco@suigeneris.org">Juanco Anez</a>
    * @see     Delta
  + * @see     DiffAlgorithm
  + *
  + * modifications:
  + *
  + * 27 Apr 2003 bwm
  + *
  + * Added some comments whilst trying to figure out the algorithm
  + *
  + * 03 May 2003 bwm
  + *
  + * Factored out the algorithm implementation into a separate difference
  + * algorithm class to allow pluggable algorithms.
    */
   
   public class Diff
  -        extends ToString
  +    extends ToString
   {
   
  -    /**
  -     * The system line separator is used for standard kinds of output
  -     */
       public static final String NL = System.getProperty("line.separator");
  -
  -    /**
  -     * For RCS kind of output a plain newline is required.
  -     */
       public static final String RCS_EOL = "\n";
  +    static DiffAlgorithm algorithm = SimpleDiff.getInstance();
   
  +    private Object[] orig;
  +    private DiffAlgorithmBound algorithmImpl;
   
       /**
  -     * Mark for non-matching items in source sequences.
  -     */
  -    static final int NOT_FOUND_i = -2;
  -
  -    /**
  -     * Mark for non-matching items in target sequences. They have to
  -     * be different in source and target because they would match
  -     * otherwise.
  -     */
  -    static final int NOT_FOUND_j = -1;
  -
  -    /**
  -     * Marker for End-Of-Sequence. It must be the same for both sequences.
  -     */
  -    static final int EOS = Integer.MAX_VALUE;
  -
  -
  -    /**
  -     * The source (original) sequence is stored here.
  +     * create a differencing object using the given algorithm
  +     *
  +     * @param o the original text which will be compared against
  +     * @param algorithm the difference algorithm to use.
        */
  -    protected Object[] orig;
  +    public Diff(Object[] o, DiffAlgorithm algorithm)
  +    {
  +        init(o, algorithm);
  +    }
   
       /**
  -     * Constructs a differencer based on an original/source sequence.
  -     * @param o the original sequences.
  +     * create a differencing object using the default algorithm
  +     *
  +     * @param the original text that will be compared
        */
       public Diff(Object[] o)
       {
  -        if (o == null)
  +        init(o, algorithm);
  +    }
  +
  +    protected void init(Object[] o, DiffAlgorithm algorithm)
  +    {
  +        if (o == null || algorithm == null)
           {
               throw new IllegalArgumentException();
           }
  +
           orig = o;
  +        algorithmImpl = algorithm.createBoundInstance(o);
       }
   
       /**
  -     * Calculates the differences between two input sequences.
  -     * @param orig The original/source sequence.
  -     * @param rev The target/revised sequence.
  -     * @return The differences as a {@link Revision Revision} object.
  -     * @throws DifferentiationFailedException if the algorithm cannot
  -     * construct the revised sequence out of the original one using the generated
  -     * edit script.
  +     * compute the difference between an original and a revision.
  +     *
  +     * @param orig the original
  +     * @param rev the revision to compare with the original.
  +     * @return a Revision describing the differences
        */
       public static Revision diff(Object[] orig, Object[] rev)
  -            throws DifferentiationFailedException
  +        throws DifferentiationFailedException
       {
           if (orig == null || rev == null)
           {
               throw new IllegalArgumentException();
           }
   
  -        return new Diff(orig).diff(rev);
  +        return diff(orig, rev, algorithm);
       }
   
       /**
  -     * Compares two sequences.
  -     * @param orig The original sequence.
  -     * @param rev Revised sequences.
  -     * @return true if the sequences are identical, false otherwise.
  +     * compute the difference between an original and a revision.
  +     *
  +     * @param orig the original
  +     * @param rev the revision to compare with the original.
  +     * @param algorithm the difference algorithm to use
  +     * @return a Revision describing the differences
        */
  -    public static boolean compare(Object[] orig, Object[] rev)
  +    public static Revision diff(Object[] orig, Object[] rev,
  +                                DiffAlgorithm algorithm)
  +        throws DifferentiationFailedException
       {
  -        if (orig.length != rev.length)
  -        {
  -            return false;
  -        }
  -        else
  +        if (orig == null || rev == null || algorithm == null)
           {
  -            for (int i = 0; i < orig.length; i++)
  -            {
  -                if (!orig[i].equals(rev[i]))
  -                {
  -                    return false;
  -                }
  -            }
  -            return true;
  +            throw new IllegalArgumentException();
           }
  -    }
   
  -    /**
  -     * Scans a sequence of indexes for a value.
  -     * @param ndx The sequence to scan.
  -     * @param i The starting index.
  -     * @param target The value to scan for.
  -     * @return The index in the sequence of a value less-than or equal to
  -     * the target value.
  -     */
  -    protected int scan(int[] ndx, int i, int target)
  -    {
  -        while (ndx[i] < target)
  -        {
  -            i++;
  -        }
  -        return i;
  +        return new Diff(orig, algorithm).diff(rev);
       }
   
       /**
  -     * Calculates the differences between the sequence given as original/source
  -     * and the given target/revised sequence.
  -     * <p>
  -     * This algorithm was designed by
  -     * <a href="juanca@suigeneris.org">Juancarlo Aņez</a> way back when
  -     * there weren't any good implementations of diff in Java.
  +     * compute the difference between the original and a revision.
        *
  -     * @param rev The target/revised sequence.
  -     * @return The differences as a {@link Revision Revision} object.
  -     * @throws DifferentiationFailedException if the algorithm cannot
  -     * construct the revised sequence out of the original one using the generated
  -     * edit script.
  +     * @param rev the revision to compare with the original.
  +     * @return a Revision describing the differences
        */
       public Revision diff(Object[] rev)
           throws DifferentiationFailedException
       {
  -        Map eqs = buildEqSet(orig, rev);
  -        int[] indx = buildIndex(eqs, orig, NOT_FOUND_i);
  -        int[] jndx = buildIndex(eqs, rev, NOT_FOUND_j);
  -        eqs = null; // let gc know we're done with this
  -
  -        Revision deltas = new Revision();
  -        int i = 0;
  -        int j = 0;
  -
  -        // skip matching
  -        for (; indx[i] != EOS && indx[i] == jndx[j]; i++, j++)
  -        {
  -            /* void */
  -        }
  -
  -        while (indx[i] != jndx[j]) // only equal if both == EOS
  -        {
  -            // indexed items in each sequence are different
  -            int ia = i;
  -            int ja = j;
  -
  -            // find the delta
  -            do
  -            {
  -                while (jndx[j] < 0 || jndx[j] < indx[i])
  -                {
  -                    j++;
  -                }
  -                while (indx[i] < 0 || indx[i] < jndx[j])
  -                {
  -                    i++;
  -                }
  -            }
  -            while (indx[i] != jndx[j]);
  -
  -            // they are equal, reverse any exedent matches
  -            while (i > ia && j > ja && indx[i - 1] == jndx[j - 1])
  -            {
  -                --i;
  -                --j;
  -            }
  -
  -            deltas.addDelta(Delta.newDelta(new Chunk(orig, ia, i - ia),
  -                    new Chunk(rev, ja, j - ja)));
  -
  -            // skip matching
  -            for (; indx[i] != EOS && indx[i] == jndx[j]; i++, j++)
  -            {
  -                /* void */
  -            }
  -        }
  -        try
  -        {
  -            /** @todo This should be removed at some point as it is
  -             * just a verification and it has considerable impact
  -             * on algorithm execution time
  -             */
  -            if (!compare(deltas.patch(orig), rev))
  -            {
  -                throw new DifferentiationFailedException();
  -            }
  -        }
  -        catch(PatchFailedException e)
  -        {
  -          throw new DifferentiationFailedException(e.getMessage());
  -        }
  -        return deltas;
  +        return algorithmImpl.diff(rev);
       }
   
  -    /**
  -     * Builds the "equivalence set" for two input sequences.
  -     * <p>
  -     * The equivalence set is a map that contains sequence items
  -     * as keys, and a list of source-sequence indexes as values.
  -     * <p>
  -     * Only items that appear in both input sequences are mapped, and
  -     * the indexes in the map values correspond to the positions in the
  -     * original/source sequence where the items were found.
  -     *
  -     * @param orig The original/source sequence.
  -     * @param rev The target/revised sequence.
  -     * @return The equivalence set.
  -     */
  -    protected Map buildEqSet(Object[] orig, Object[] rev)
  +    public static boolean compare(Object[] orig, Object[] rev)
       {
  -        Set items = new HashSet(Arrays.asList(orig));
  -        items.retainAll(Arrays.asList(rev));
  -
  -        Map eqs = new HashMap();
  -        for (int i = 0; i < orig.length; i++)
  +        if (orig.length != rev.length)
           {
  -            if (items.contains(orig[i]))
  -            {
  -                List matches = (List) eqs.get(orig[i]);
  -                if (matches == null)
  -                {
  -                    matches = new LinkedList();
  -                    eqs.put(orig[i], matches);
  -                }
  -                matches.add(new Integer(i));
  -            }
  +            return false;
           }
  -        return eqs;
  -    }
  -
  -    /**
  -     * Indexes a sequence according to a given equivalence set.
  -     * <p>
  -     * Items in the input sequene are searched for in the equivalence set.
  -     * For each item, the index with the less absolute distance to the item
  -     * number is chosen from the list in the eauivalence set.
  -     * <p>
  -     * Items which do not appear in the equivalence set get an index of
  -     * NF (not found).
  -     *
  -     * @param eqs The equivalence set.
  -     * @param seq The sequence to index.
  -     * @param NF The value to use for sequence items which do not appear
  -     * on the equivalence set.
  -     * @return The index.
  -     */
  -    protected int[] buildIndex(Map eqs, Object[] seq, int NF)
  -    {
  -        int[] result = new int[seq.length + 1];
  -        for (int i = 0; i < seq.length; i++)
  +        else
           {
  -            List matches = (List) eqs.get(seq[i]);
  -            if (matches == null)
  -            {
  -                result[i] = NF;
  -            }
  -            else
  +            for (int i = 0; i < orig.length; i++)
               {
  -                Iterator match = matches.iterator();
  -                int j = ((Integer) match.next()).intValue();
  -                int distance = Math.abs(i - j);
  -                result[i] = j;
  -                while (match.hasNext())
  +                if (!orig[i].equals(rev[i]))
                   {
  -                    j = ((Integer) match.next()).intValue();;
  -                    int d = Math.abs(i - j);
  -                    if (d < distance)
  -                    {
  -                        distance = d;
  -                        result[i] = j;
  -                    }
  +                    return false;
                   }
               }
  +            return true;
           }
  -        result[seq.length] = EOS;
  -        return result;
       }
   
  -
       /**
        * Converts an array of {@link Object Object} to a string
        * using {@link Diff#NL Diff.NL}
  @@ -383,25 +225,11 @@
           return arrayToString(o, Diff.NL);
       }
   
  -
  -
  -    /**
  -     * Performs random edits on the input sequence. Useful for testing.
  -     * @param text The input sequence.
  -     * @return The sequence with random edits performed.
  -     */
       public static Object[] randomEdit(Object[] text)
       {
           return randomEdit(text, text.length);
       }
   
  -
  -    /**
  -     * Performs random edits on the input sequence. Useful for testing.
  -     * @param text The input sequence.
  -     * @param seed A seed value for the randomizer.
  -     * @return The sequence with random edits performed.
  -     */
       public static Object[] randomEdit(Object[] text, long seed)
       {
           List result = new ArrayList(Arrays.asList(text));
  @@ -420,38 +248,23 @@
               {
                   for (int k = 0; k < len; k++, pos++)
                   {
  -                    result.add(pos, "[" + i + "] random edit[" + i + "][" + i + "]");
  +                    result.add(pos,
  +                               "[" + i + "] random edit[" + i + "][" + i + "]");
                   }
               }
           }
           return result.toArray();
       }
   
  -
  -    /**
  -     * Shuffles around the items in the input sequence.
  -     * @param text The input sequence.
  -     * @return The shuffled sequence.
  -     */
       public static Object[] shuffle(Object[] text)
       {
           return shuffle(text, text.length);
       }
   
  -
  -    /**
  -     * Shuffles around the items in the input sequence.
  -     * @param text The input sequence.
  -     * @param seed A seed value for randomizing the suffle.
  -     * @return The shuffled sequence.
  -     */
       public static Object[] shuffle(Object[] text, long seed)
       {
           List result = new ArrayList(Arrays.asList(text));
           Collections.shuffle(result);
           return result.toArray();
       }
  -}
  -
  -
  -
  +}
  \ No newline at end of file
  
  
  
  1.3       +31 -1     jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/Revision.java
  
  Index: Revision.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/Revision.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- Revision.java	28 Sep 2002 15:57:10 -0000	1.2
  +++ Revision.java	5 May 2003 21:49:28 -0000	1.3
  @@ -70,10 +70,19 @@
    *
    * @version $Id$
    * @author <a href="mailto:juanco@suigeneris.org">Juanco Anez</a>
  + * @author <a href="mailto:bwm@hplb.hpl.hp.com">Brian McBride</a>
  + *
    * @see Delta
    * @see Diff
    * @see Chunk
  + * @see Revision
  + *
  + * modifications
  + * 27 Apr 2003 bwm
  + *
  + * Added visitor pattern Visitor interface and accept() method.
    */
  +
   public class Revision
           extends ToString
   {
  @@ -221,6 +230,27 @@
       public String toRCSString()
       {
           return toRCSString(Diff.NL);
  +    }
  +
  +    /**
  +     * Definition of a visitor interface for revisions.
  +     * See "Design Patterns" by the Gang of Four
  +     */
  +    public interface Visitor {
  +        public void visit(Revision revision);
  +        public void visit(Delta delta);
  +    }
  +
  +    /**
  +     * Accepts a visitor.
  +     * @param visitor the {@link Visitor} visiting this instance
  +     */
  +    public void accept(Visitor visitor) {
  +        visitor.visit(this);
  +        Iterator iter = deltas_.iterator();
  +        while (iter.hasNext()) {
  +            ((Delta) iter.next()).accept(visitor);
  +        }
       }
   
   }
  
  
  
  1.1                  jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/DiffAlgorithm.java
  
  Index: DiffAlgorithm.java
  ===================================================================
  package org.apache.commons.jrcs.diff;
  
  /* ====================================================================
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 2002 The Apache Software Foundation.  All rights
   * reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   *
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   *
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in
   *    the documentation and/or other materials provided with the
   *    distribution.
   *
   * 3. The end-user documentation included with the redistribution,
   *    if any, must include the following acknowledgment:
   *       "This product includes software developed by the
   *        Apache Software Foundation (http://www.apache.org/)."
   *    Alternately, this acknowledgment may appear in the software itself,
   *    if and wherever such third-party acknowledgments normally appear.
   *
   * 4. The names "Apache" and "Apache Software Foundation" and
   *    "Apache Maven" must not be used to endorse or promote products
   *    derived from this software without prior written permission. For
   *    written permission, please contact apache@apache.org.
   *
   * 5. Products derived from this software may not be called "Apache",
   *    "Apache Maven", nor may "Apache" appear in their name, without
   *    prior written permission of the Apache Software Foundation.
   *
   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   * SUCH DAMAGE.
   * ====================================================================
   *
   * This software consists of voluntary contributions made by many
   * individuals on behalf of the Apache Software Foundation.  For more
   * information on the Apache Software Foundation, please see
   * <http://www.apache.org/>.
   */
  /**
   * The interface to a difference algorithm.
   *
   * @version $Revision: 1.1 $ $Date: 2003/05/05 21:49:28 $
   *
   * <p>An algorithm is essentially a factory that creates instances of
   * the algorithm that are bound to original text.</p>
   * @author bwm
   *
   */
  public interface DiffAlgorithm
  {
      /**
       * return a new instance of an algorithm bound to some original text
       */
      public DiffAlgorithmBound createBoundInstance(Object[] orig);
  }
  
  
  1.1                  jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/DiffAlgorithmBound.java
  
  Index: DiffAlgorithmBound.java
  ===================================================================
  package org.apache.commons.jrcs.diff;
  
  /* ====================================================================
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 2002 The Apache Software Foundation.  All rights
   * reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   *
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   *
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in
   *    the documentation and/or other materials provided with the
   *    distribution.
   *
   * 3. The end-user documentation included with the redistribution,
   *    if any, must include the following acknowledgment:
   *       "This product includes software developed by the
   *        Apache Software Foundation (http://www.apache.org/)."
   *    Alternately, this acknowledgment may appear in the software itself,
   *    if and wherever such third-party acknowledgments normally appear.
   *
   * 4. The names "Apache" and "Apache Software Foundation" and
   *    "Apache Maven" must not be used to endorse or promote products
   *    derived from this software without prior written permission. For
   *    written permission, please contact apache@apache.org.
   *
   * 5. Products derived from this software may not be called "Apache",
   *    "Apache Maven", nor may "Apache" appear in their name, without
   *    prior written permission of the Apache Software Foundation.
   *
   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   * SUCH DAMAGE.
   * ====================================================================
   *
   * This software consists of voluntary contributions made by many
   * individuals on behalf of the Apache Software Foundation.  For more
   * information on the Apache Software Foundation, please see
   * <http://www.apache.org/>.
   */
  
  /**
   * The interface to an implementation of a difference algorithm
   *
   * @version $Revision: 1.1 $ $Date: 2003/05/05 21:49:28 $
   *
   * <p>The algorithm is bound to some original text.</p>
   * @author bwm
   *
   */
  public interface DiffAlgorithmBound
  {
      /**
       * Compute a {@link org.apache.commons.jrcs.diff#Revision Revision}
       * between the original text and the revised text.
       *
       * @param rev the revised text
       */
      Revision diff(Object[] rev)
          throws DifferentiationFailedException;
  }
  
  
  1.1                  jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/SimpleDiff.java
  
  Index: SimpleDiff.java
  ===================================================================
  package org.apache.commons.jrcs.diff;
  
  /* ====================================================================
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 2002 The Apache Software Foundation.  All rights
   * reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   *
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   *
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in
   *    the documentation and/or other materials provided with the
   *    distribution.
   *
   * 3. The end-user documentation included with the redistribution,
   *    if any, must include the following acknowledgment:
   *       "This product includes software developed by the
   *        Apache Software Foundation (http://www.apache.org/)."
   *    Alternately, this acknowledgment may appear in the software itself,
   *    if and wherever such third-party acknowledgments normally appear.
   *
   * 4. The names "Apache" and "Apache Software Foundation" and
   *    "Apache Maven" must not be used to endorse or promote products
   *    derived from this software without prior written permission. For
   *    written permission, please contact apache@apache.org.
   *
   * 5. Products derived from this software may not be called "Apache",
   *    "Apache Maven", nor may "Apache" appear in their name, without
   *    prior written permission of the Apache Software Foundation.
   *
   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   * SUCH DAMAGE.
   * ====================================================================
   *
   * This software consists of voluntary contributions made by many
   * individuals on behalf of the Apache Software Foundation.  For more
   * information on the Apache Software Foundation, please see
   * <http://www.apache.org/>.
   */
  
  /**
   * The interface to a difference algorithm.
   *
   * @version $Revision: 1.1 $ $Date: 2003/05/05 21:49:28 $
   *
   * <p>An algorithm is essentially a factory that creates instances of
   * the algorithm.  This algorithm uses the singleton pattern to create
   * the factory.</p>
   *
   * @author bwm
   */
  public class SimpleDiff
      implements DiffAlgorithm
  {
  
      private static SimpleDiff instance = new SimpleDiff();
  
      private SimpleDiff()
      {}
  
      /**
       * return the factory for this algorithm
       *
       * @return the factory for this algorithm
       */
      public static SimpleDiff getInstance()
      {
          return instance;
      }
  
      /**
       * return an instance of the algorithm bound to some original text
       *
       * @return an instance of the algorithm
       */
      public DiffAlgorithmBound createBoundInstance(Object[] orig)
      {
          return new SimpleDiffBound(orig);
      }
  }
  
  
  1.1                  jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/SimpleDiffBound.java
  
  Index: SimpleDiffBound.java
  ===================================================================
  package org.apache.commons.jrcs.diff;
  
  /* ====================================================================
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 2002 The Apache Software Foundation.  All rights
   * reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   *
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   *
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in
   *    the documentation and/or other materials provided with the
   *    distribution.
   *
   * 3. The end-user documentation included with the redistribution,
   *    if any, must include the following acknowledgment:
   *       "This product includes software developed by the
   *        Apache Software Foundation (http://www.apache.org/)."
   *    Alternately, this acknowledgment may appear in the software itself,
   *    if and wherever such third-party acknowledgments normally appear.
   *
   * 4. The names "Apache" and "Apache Software Foundation" and
   *    "Apache Maven" must not be used to endorse or promote products
   *    derived from this software without prior written permission. For
   *    written permission, please contact apache@apache.org.
   *
   * 5. Products derived from this software may not be called "Apache",
   *    "Apache Maven", nor may "Apache" appear in their name, without
   *    prior written permission of the Apache Software Foundation.
   *
   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   * SUCH DAMAGE.
   * ====================================================================
   *
   * This software consists of voluntary contributions made by many
   * individuals on behalf of the Apache Software Foundation.  For more
   * information on the Apache Software Foundation, please see
   * <http://www.apache.org/>.
   */
  
  import java.util.Collections;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Map;
  import java.util.Random;
  import java.util.Set;
  
  import org.apache.commons.jrcs.util.ToString;
  
  /**
   * Implements a simple difference algortithm
   *
   * @version $Revision: 1.1 $ $Date: 2003/05/05 21:49:28 $
   * @author <a href="mailto:juanco@suigeneris.org">Juanco Anez</a>
   * @see Delta
   * @see Revision
   *
   * <p><b>Overview of Algorithm</b></p>
   *
   * <p><i>this description was written by <a
   * href='http://www.topmeadow.net/bwm'> bwm</a> whilst trying to understand
   * the algorithm - Juancarlos - feel free to remove  this attribution if
   * you agree with the content below - its just to absolve you of
   * responsibility.</i></p>
   *
   * <p>The algorithm is optimised for situations where the input sequences
   * have few repeated objects.  If it is given input with many repeated
   * objects it may report sub-optimal changes.  However, given appropriate
   * input, it is fast.</p>
   *
   * <p>The algorithm consists of the following steps:</p>
   * <ul>
   *   <li>compute a perfect hash function for the input data</li>
   *   <li>compute the hash function for each element of the orginal
   *       and revised input sequences</li>
   *   <li>match the the input sequences to determine the deltas, i.e.
   *       the differences between the original and revised sequences.</li>
   * </ul>
   *
   * <p>The first step is to compute a perfect hash for the input data.  The
   * hash function is defined only for objects that are in the original
   * input sequence and in the revised input sequences:</p>
   * <pre>
   *   eq(x) = the index of the first occurence of x in the orig sequence.
   * </pre>
   *
   * <p>With this hash function, the algorithm can compare integers rather
   * than strings, which is considerably more efficient.</p>
   *
   * <p>The second step is to compute the datastructure on which the
   * algorithm will operate.  Having computed the perfect hash function
   * in the previous step, we can compute two arrays where
   * indx[i] = eqs(orig[i]) and jndx[i] = eqs(rev[i]).  The algorithm can
   * now operate on indx and jndx instead of orig and rev.</p>
   *
   * <p>The algorithm now matches indx and jndx.  Whilst indx[i] == jndx[i]
   * it skips matching objects in the sequence.  In seeking to match objects
   * in the input sequence it assumes that each object is likely to be unique.
   * It uses the known characteristics of the unique hash function.  It can
   * tell from the hash value if this object appeared in the other sequence
   * at all.  If it did not, there is point in searching for a match.</p>
   *
   * <p>Recall that hash function value is the index earliest occurrence in
   *  the orig sequence.  This information is used to search efficiently for
   * the next match.  The algorithm is perfect when all input objects are
   *  unique, but degrades when input objects are not unique.  When input
   *  objects are not unique an optimal match may not be found, but a
   * correct match will be.</p>
   *
   * <p>Having identified common matching objects in the orig and revised
   * sequences, the differences between them are easily computed.</p>
   *
   * Modifications:
   *
   * 27/Apr/2003 bwm
   * Added some comments whilst trying to figure out the algorithm
   *
   * 03 May 2003 bwm
   * Created this implementation class by refactoring it out of the Diff
   * class to enable plug in difference algorithms
   *
   */
  
  public class SimpleDiffBound
      extends ToString
      implements DiffAlgorithmBound
  {
  
      public static final String NL = System.getProperty("line.separator");
      public static final String RCS_EOL = "\n";
  
      static final int NOT_FOUND_i = -2;
  
      static final int NOT_FOUND_j = -1;
  
      static final int EOS = Integer.MAX_VALUE;
  
      Object[] orig;
  
      public SimpleDiffBound(Object[] o)
      {
          if (o == null)
          {
              throw new IllegalArgumentException();
          }
          orig = o;
      }
  
      protected int scan(int[] ndx, int i, int target)
      {
          while (ndx[i] < target)
          {
              i++;
          }
          return i;
      }
  
      /**
       * compute the difference between an original and a revision.
       *
       * @param rev the revision to compare with the original.
       * @return a Revision describing the differences
       */
      public Revision diff(Object[] rev)
          throws DifferentiationFailedException
      {
          // create map eqs, such that for each item in both orig and rev
          // eqs(item) = firstOccurrence(item, orig);
          Map eqs = buildEqSet(orig, rev);
  
          // create an array such that
          //   indx[i] = NOT_FOUND_i if orig[i] is not in rev
          //   indx[i] = firstOccurrence(orig[i], orig)
          int[] indx = buildIndex(eqs, orig, NOT_FOUND_i);
  
          // create an array such that
          //   jndx[j] = NOT_FOUND_j if orig[j] is not in rev
          //   jndx[j] = firstOccurrence(rev[j], orig)
          int[] jndx = buildIndex(eqs, rev, NOT_FOUND_j);
  
          // what in effect has been done is to build a unique hash
          // for each item that is in both orig and rev
          // and to label each item in orig and new with that hash value
          // or a marker that the item is not common to both.
  
          eqs = null; // let gc know we're done with this
  
          Revision deltas = new Revision(); //!!! new Revision()
          int i = 0;
          int j = 0;
  
          // skip matching
          // skip leading items that are equal
          // could be written
          // for (i=0; indx[i] != EOS && indx[i] == jndx[i]; i++);
          // j = i;
          for (; indx[i] != EOS && indx[i] == jndx[j]; i++, j++)
          {
              /* void */
          }
  
          while (indx[i] != jndx[j])
          { // only equal if both == EOS
              // they are different
              int ia = i;
              int ja = j;
  
              // size of this delta
              do
              {
                  // look down rev for a match
                  // stop at a match
                  // or if the FO(rev[j]) > FO(orig[i])
                  // or at the end
                  while (jndx[j] < 0 || jndx[j] < indx[i])
                  {
                      j++;
                  }
                  // look down orig for a match
                  // stop at a match
                  // or if the FO(orig[i]) > FO(rev[j])
                  // or at the end
                  while (indx[i] < 0 || indx[i] < jndx[j])
                  {
                      i++;
                  }
  
                  // this doesn't do a compare each line with each other line
                  // so it won't find all matching lines
              }
              while (indx[i] != jndx[j]);
  
              // on exit we have a match
  
              // they are equal, reverse any exedent matches
              // it is possible to overshoot, so count back matching items
              while (i > ia && j > ja && indx[i - 1] == jndx[j - 1])
              {
                  --i;
                  --j;
              }
  
              deltas.addDelta(Delta.newDelta(new Chunk(orig, ia, i - ia),
                                             new Chunk(rev, ja, j - ja)));
              // skip matching
              for (; indx[i] != EOS && indx[i] == jndx[j]; i++, j++)
              {
                  /* void */
              }
          }
          return deltas;
      }
  
      /**
       * create a <code>Map</code> from each common item in orig and rev
       * to the index of its first occurrence in orig
       *
       * @param orig the original sequence of items
       * @param rev  the revised sequence of items
       */
      protected Map buildEqSet(Object[] orig, Object[] rev)
      {
          // construct a set of the objects that orig and rev have in common
  
          // first construct a set containing all the elements in orig
          Set items = new HashSet(Arrays.asList(orig));
  
          // then remove all those not in rev
          items.retainAll(Arrays.asList(rev));
  
          Map eqs = new HashMap();
          for (int i = 0; i < orig.length; i++)
          {
              // if its a common item and hasn't been found before
              if (items.contains(orig[i]))
              {
                  // add it to the map
                  eqs.put(orig[i], new Integer(i));
                  // and make sure its not considered again
                  items.remove(orig[i]);
              }
          }
          return eqs;
      }
  
      /**
       * build a an array such each a[i] = eqs([i]) or NF if eqs([i]) undefined
       *
       * @param eqs a mapping from Object to Integer
       * @param seq a sequence of objects
       * @param NF  the not found marker
       */
      protected int[] buildIndex(Map eqs, Object[] seq, int NF)
      {
          int[] result = new int[seq.length + 1];
          for (int i = 0; i < seq.length; i++)
          {
              Integer value = (Integer) eqs.get(seq[i]);
              if (value == null || value.intValue() < 0)
              {
                  result[i] = NF;
              }
              else
              {
                  result[i] = value.intValue();
              }
          }
          result[seq.length] = EOS;
          return result;
      }
  
  }
  
  
  
  1.4       +62 -0     jakarta-commons-sandbox/jrcs/src/test/org/apache/commons/jrcs/diff/DiffTest.java
  
  Index: DiffTest.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/src/test/org/apache/commons/jrcs/diff/DiffTest.java,v
  retrieving revision 1.3
  retrieving revision 1.4
  diff -u -r1.3 -r1.4
  --- DiffTest.java	1 Nov 2002 18:19:12 -0000	1.3
  +++ DiffTest.java	5 May 2003 21:49:29 -0000	1.4
  @@ -247,6 +247,68 @@
           orig = random;
       }
     }
  +  
  +  public void testVisitor()
  +  {    
  +      Object[] orig = new String[] {
  +                   "[1] one",
  +                   "[2] two",
  +                   "[3] three",
  +                   "[4] four",
  +                   "[5] five",
  +                   "[6] six"
  +                   };
  +      Object[] rev = new String[] {
  +                   "[1] one",
  +                   "[2] two revised",
  +                   "[3] three",
  +                   "[4] four revised",
  +                   "[5] five",
  +                   "[6] six"
  +                   };
  +        
  +      class Visitor implements Revision.Visitor {
  +        
  +        StringBuffer sb = new StringBuffer();
  +        
  +        public void visit(Revision revision) {
  +            sb.append("visited Revision\n");
  +        }
  +        
  +        public void visit(Delta delta) {
  +            sb.append(delta.getRevised());
  +            sb.append("\n");
  +        }
  +        
  +        public String toString() {
  +            return sb.toString();
  +        }
  +      }
  +        
  +      Visitor visitor = new Visitor();
  +      try {           
  +          Diff.diff(orig, rev).accept(visitor);
  +          assertEquals(visitor.toString(),
  +            "visited Revision\n" +
  +            "[2] two revised\n" +
  +            "[4] four revised\n");
  +      } catch (Exception e) {
  +        fail(e.toString());
  +      }
  +  }
   
   
  +  public void testAlternativeAlgorithm()
  +  throws DifferentiationFailedException, PatchFailedException
  +  {
  +    Revision revision = Diff.diff(original, rev2, SimpleDiff.getInstance());
  +    assertEquals(1, revision.size());
  +    assertEquals(ChangeDelta.class, revision.getDelta(0).getClass());
  +    assertTrue(Diff.compare(revision.patch(original), rev2));
  +    assertEquals("d7 3" + Diff.NL +
  +                 "a9 2" + Diff.NL +
  +                 "[7] seven revised" + Diff.NL +
  +                 "[8] eight revised" + Diff.NL,
  +                 revision.toRCSString());
  +  }
   }
  
  
  

---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message