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/java/org/apache/commons/jrcs/diff/myers MyersDiff.java PathNode.java
Date Tue, 06 May 2003 18:07:51 GMT
juanco      2003/05/06 11:07:51

  Modified:    jrcs     jrcs.jpx
               jrcs/src/java/org/apache/commons/jrcs/diff
                        DiffAlgorithm.java Revision.java
               jrcs/src/java/org/apache/commons/jrcs/diff/myers
                        MyersDiff.java PathNode.java
  Log:
  minor optimizations, and code and comment cleanup
  
  Revision  Changes    Path
  1.6       +11 -2     jakarta-commons-sandbox/jrcs/jrcs.jpx
  
  Index: jrcs.jpx
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/jrcs.jpx,v
  retrieving revision 1.5
  retrieving revision 1.6
  diff -u -r1.5 -r1.6
  --- jrcs.jpx	6 May 2003 14:26:04 -0000	1.5
  +++ jrcs.jpx	6 May 2003 18:07:51 -0000	1.6
  @@ -3,16 +3,16 @@
   <project>
     <property category="generalFormatting" name="blockIndent" value="4"/>
     <property category="idl" name="ProcessIDL" value="false"/>
  +  <property category="javaFormatting" name="alignMultilineAssign" value="1"/>
     <property category="javaFormatting" name="arrayInitDataOnNewLine" value="0"/>
  -  <property category="javaFormatting" name="catchOnNewLine" value="1"/>
     <property category="javaFormatting" name="classBraceNextLine" value="1"/>
     <property category="javaFormatting" name="methodBraceNextLine" value="1"/>
     <property category="javaFormatting" name="otherBraceNextLine" value="1"/>
     <property category="javaFormatting" name="packageThreshold" value="4"/>
     <property category="javaFormatting" name="throwsOnNewLine" value="1"/>
  +  <property category="javaFormatting" name="wrapAtColumn" value="132"/>
     <property category="javadoc" name="custom.tags.1" value="todo;a;To Do:"/>
     <property category="runtime" name="ConfigurationCount" value="2"/>
  -  <property category="runtime" name="DefaultConfiguration" value="2"/>
     <property category="runtime.0" name="BuildTargetOnRun" value="com.borland.jbuilder.build.ProjectBuilder$ProjectBuildAction;make"/>
     <property category="runtime.0" name="ConfigurationName" value="AllTests"/>
     <property category="runtime.0" name="RunnableType" value="com.borland.jbuilder.runtime.TestRunner"/>
  @@ -59,5 +59,14 @@
     <property category="sys" name="Version" value="1.0"/>
     <property category="sys" name="VersionLabel" value="@version"/>
     <property category="sys" name="WorkingDirectory" value="."/>
  +  <node name="Javadocs" type="Javadoc">
  +    <property category="docletJavadoc" name="author" value="1"/>
  +    <property category="docletJavadoc" name="splitIndex" value="1"/>
  +    <property category="docletJavadoc" name="use" value="1"/>
  +    <property category="docletJavadoc" name="version" value="1"/>
  +    <property category="javadoc" name="scope" value="private"/>
  +    <property category="nodeJavadoc" name="directory" value="doc/api"/>
  +    <property category="nodeJavadoc" name="displayAllOutput" value="0"/>
  +  </node>
     <file path="src/test/org/apache/commons/jrcs/rcs/idchar.testfile"/>
   </project>
  
  
  
  1.4       +5 -3      jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/DiffAlgorithm.java
  
  Index: DiffAlgorithm.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/DiffAlgorithm.java,v
  retrieving revision 1.3
  retrieving revision 1.4
  diff -u -r1.3 -r1.4
  --- DiffAlgorithm.java	6 May 2003 14:59:12 -0000	1.3
  +++ DiffAlgorithm.java	6 May 2003 18:07:51 -0000	1.4
  @@ -67,8 +67,10 @@
   public interface DiffAlgorithm
   {
       /**
  -     * Compute a {@link org.apache.commons.jrcs.diff#Revision Revision}
  -     * between the original sequence and the revised sequence.
  +     * Computes the difference between the original
  +     * sequence and the revised sequence and returns it
  +     * as a {@link org.apache.commons.jrcs.diff.Revision Revision}
  +     * object.
        * <p>
        * The revision can be used to construct the revised sequence
        * from the original sequence.
  
  
  
  1.6       +2 -2      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.5
  retrieving revision 1.6
  diff -u -r1.5 -r1.6
  --- Revision.java	6 May 2003 14:59:12 -0000	1.5
  +++ Revision.java	6 May 2003 18:07:51 -0000	1.6
  @@ -69,7 +69,7 @@
   
   /**
    * A Revision holds the series of deltas that describe the differences
  - * between to revisions of a text.
  + * between two sequences.
    *
    * @version $Revision$ $Date$
    *
  
  
  
  1.4       +49 -26    jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/myers/MyersDiff.java
  
  Index: MyersDiff.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/myers/MyersDiff.java,v
  retrieving revision 1.3
  retrieving revision 1.4
  diff -u -r1.3 -r1.4
  --- MyersDiff.java	6 May 2003 14:59:13 -0000	1.3
  +++ MyersDiff.java	6 May 2003 18:07:51 -0000	1.4
  @@ -66,7 +66,7 @@
    * <p>
    * See the paper at
    * <a href="http://www.cs.arizona.edu/people/gene/PAPERS/diff.ps">
  - * Myers' site</a>
  + * http://www.cs.arizona.edu/people/gene/PAPERS/diff.ps</a>
    *
    * @version $Revision$ $Date$
    * @author <a href="mailto:juanco@suigeneris.org">Juanco Anez</a>
  @@ -77,10 +77,16 @@
   public class MyersDiff
       implements DiffAlgorithm
   {
  +    /**
  +     * Constructs an instance of the Myers differencing algorithm.
  +     */
       public MyersDiff()
       {
       }
   
  +    /**
  +     * {@inheritDoc}
  +     */
       public Revision diff(Object[] orig, Object[] rev)
           throws DifferentiationFailedException
       {
  @@ -98,28 +104,34 @@
        * @return A minimum {@link PathNode Path} accross the differences graph.
        * @throws DifferentiationFailedException if a diff path could not be found.
        */
  -    public PathNode buildPath(Object[] orig, Object[] rev)
  +    public static PathNode buildPath(Object[] orig, Object[] rev)
           throws DifferentiationFailedException
       {
  -        int n = orig.length;
  -        int m = rev.length;
  +        if (orig == null)
  +            throw new IllegalArgumentException("original sequence is null");
  +        if (rev == null)
  +            throw new IllegalArgumentException("revised sequence is null");
   
  -        int max = n + m + 1;
  -        PathNode diagonal[] = new PathNode[1 + 2 * max];
  -        int middle = (diagonal.length + 1) / 2;
  +        // these are local constants
  +        final int N = orig.length;
  +        final int M = rev.length;
  +
  +        final int MAX = N + M + 1;
  +        final int size = 1 + 2 * MAX;
  +        final int middle = (size + 1) / 2;
  +        final PathNode diagonal[] = new PathNode[size];
   
           PathNode path = null;
   
  -        int d = 0;
           diagonal[middle + 1] = new PathNode(0, -1);
  -        outer:for (d = 0; d < max; d++)
  +        for (int d = 0; d < MAX; d++)
           {
               for (int k = -d; k <= d; k += 2)
               {
  -                PathNode prev = null;
                   int kmiddle = middle + k;
                   int kplus = kmiddle + 1;
                   int kminus = kmiddle - 1;
  +                PathNode prev = null;
   
                   int i;
                   if ( (k == -d) ||
  @@ -133,22 +145,32 @@
                       i = diagonal[kminus].i + 1;
                       prev = diagonal[kminus];
                   }
  +
                   if (prev.i < 0 || prev.j < 0)
  -                    prev = null;
  +                {
  +                    prev = null; // discard artificial nodes used for bootstrapping
  +                }
   
                   int j = i - k;
  -                while (i < n && j < m && orig[i].equals(rev[j]))
  +
  +                // orig and rev are zero-based
  +                // but the algorithm is one-based
  +                // that's why there's no +1 when indexing the sequences
  +                while (i < N && j < M && orig[i].equals(rev[j]))
                   {
                       i++;
                       j++;
                   }
  +
                   diagonal[kmiddle] = new PathNode(i, j, prev);
  -                if (i >= n && j >= m)
  +
  +                if (i >= N && j >= M)
                   {
                       return diagonal[kmiddle];
                   }
               }
           }
  +        // According to Myers, this cannot happen
           throw new DifferentiationFailedException("could not find a diff path");
       }
   
  @@ -162,7 +184,7 @@
        * @throws DifferentiationFailedException if the {@link Revision} could
        *         not be built.
        */
  -    public Revision buildRevision(PathNode path, Object[] orig, Object[] rev)
  +    public static Revision buildRevision(PathNode path, Object[] orig, Object[] rev)
       {
           if (path == null)
               throw new IllegalArgumentException("path is null");
  @@ -177,27 +199,28 @@
               int i = path.i;
               int j = path.j;
               while (i > 0 && j > 0
  -                   && i > path.prev.i && j > path.prev.j
  -                   && orig[i - 1].equals(rev[j - 1]))
  -            { // reverse snake
  +                   && i > path.prev.i && j > path.prev.j // donnot
follow a snake past a previous node
  +                   && orig[i - 1].equals(rev[j - 1])) // check that it is indeed
a snake
  +            {
  +                // reverse snake
                   i--;
                   j--;
               }
   
  -            int ia;
  -            int ja;
  +            int ianchor;
  +            int janchor;
               do
               {
                   path = path.prev;
  -                ia = path.i;
  -                ja = path.j;
  +                ianchor = path.i;
  +                janchor = path.j;
               }
               while (path.prev != null
  -                   && (ia == path.prev.i || ja == path.prev.j)
  -                   ); // while no snake
  +                   && (ianchor == path.prev.i || janchor == path.prev.j) // while
no snake
  +                   );
   
  -            Delta delta = Delta.newDelta(new Chunk(orig, ia, i - ia),
  -                                         new Chunk(rev, ja, j - ja));
  +            Delta delta = Delta.newDelta(new Chunk(orig, ianchor, i - ianchor),
  +                                         new Chunk(rev, janchor, j - janchor));
               revision.insertDelta(delta);
           }
           return revision;
  
  
  
  1.3       +7 -1      jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/myers/PathNode.java
  
  Index: PathNode.java
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/myers/PathNode.java,v
  retrieving revision 1.2
  retrieving revision 1.3
  diff -u -r1.2 -r1.3
  --- PathNode.java	6 May 2003 14:59:13 -0000	1.2
  +++ PathNode.java	6 May 2003 18:07:51 -0000	1.3
  @@ -59,8 +59,11 @@
   
   public final class PathNode
   {
  +    /** Position in the original sequence. */
       public final int i;
  +    /** Position in the revised sequence. */
       public final int j;
  +    /** The previous node in the path. */
       public final PathNode prev;
   
       /**
  @@ -74,7 +77,7 @@
       }
   
       /**
  -     * Adds a node to an existing diffpath.
  +     * Concatenates a new path node with an existing diffpath.
        * @param i The position in the original sequence for the new node.
        * @param j The position in the revised sequence for the new node.
        * @param prev The previous node in the path.
  @@ -88,6 +91,9 @@
           this.prev = prev;
       }
   
  +    /**
  +     * {@inheritDoc}
  +     */
       public String toString()
       {
           StringBuffer buf = new StringBuffer("[");
  
  
  

---------------------------------------------------------------------
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