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 Tue, 06 May 2003 14:26:05 GMT
juanco      2003/05/06 07:26:05

  Modified:    jrcs     jrcs.jpx
               jrcs/src/java/org/apache/commons/jrcs/diff Diff.java
               jrcs/src/java/org/apache/commons/jrcs/diff/myers
                        MyersDiff.java
               jrcs/src/test/org/apache/commons/jrcs/diff DiffTest.java
  Log:
  Finished implementing Myer's differencing algorithm. All unit tests
  now run 100%.
  
  Myer's differencing algorithm produces optimum diffs fast and using
  memory proportional to the sum of the lengths of the input sequences.
  
  Revision  Changes    Path
  1.5       +18 -2     jakarta-commons-sandbox/jrcs/jrcs.jpx
  
  Index: jrcs.jpx
  ===================================================================
  RCS file: /home/cvs/jakarta-commons-sandbox/jrcs/jrcs.jpx,v
  retrieving revision 1.4
  retrieving revision 1.5
  diff -u -r1.4 -r1.5
  --- jrcs.jpx	5 May 2003 21:49:28 -0000	1.4
  +++ jrcs.jpx	6 May 2003 14:26:04 -0000	1.5
  @@ -2,6 +2,7 @@
   <!--JBuilder XML Project-->
   <project>
     <property category="generalFormatting" name="blockIndent" value="4"/>
  +  <property category="idl" name="ProcessIDL" value="false"/>
     <property category="javaFormatting" name="arrayInitDataOnNewLine" value="0"/>
     <property category="javaFormatting" name="catchOnNewLine" value="1"/>
     <property category="javaFormatting" name="classBraceNextLine" value="1"/>
  @@ -10,11 +11,24 @@
     <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="DefaultConfiguration" value="-1"/>
  +  <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"/>
     <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="Large Diff"/>
  +  <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="runtime.1" name="application.vmparameters" value="-Xmx128m"/>
  +  <property category="runtime.2" name="BuildTargetOnRun" value="com.borland.jbuilder.build.ProjectBuilder$ProjectBuildAction;make"/>
  +  <property category="runtime.2" name="ConfigurationName" value="Short Diff"/>
  +  <property category="runtime.2" name="RunnableType" value="com.borland.jbuilder.runtime.ApplicationRunner"/>
  +  <property category="runtime.2" name="application.class" value="org.apache.commons.jrcs.tools.JDiff"/>
  +  <property category="runtime.2" name="application.parameters" value="\tmp\difftest\test1.txt
\tmp\difftest\test2.txt "/>
     <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"/>
  @@ -32,11 +46,13 @@
     <property category="sys" name="IncludeTestPath" value="1"/>
     <property category="sys" name="InstanceVisibility" value="2"/>
     <property category="sys" name="JDK" value="java version 1.4.1_02-b06"/>
  +  <property category="sys" name="JvmVersion" value="1.4"/>
     <property category="sys" name="LastTag" value="0"/>
  -  <property category="sys" name="Libraries" value="JUnit;Jakarta ORO Regexp"/>
  +  <property category="sys" name="Libraries" value="JUnit;Jakarta ORO;JakartaCommonsCollections"/>
     <property category="sys" name="MakeStable" value="0"/>
     <property category="sys" name="OutPath" value="classes"/>
     <property category="sys" name="SourcePath" value="src/java;src/test"/>
  +  <property category="sys" name="SourceVersion" value="1.4"/>
     <property category="sys" name="TestPath" value="src/test"/>
     <property category="sys" name="Title" value=""/>
     <property category="sys" name="TitleLabel" value="Title:"/>
  
  
  
  1.9       +26 -4     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.8
  retrieving revision 1.9
  diff -u -r1.8 -r1.9
  --- Diff.java	5 May 2003 22:43:24 -0000	1.8
  +++ Diff.java	6 May 2003 14:26:04 -0000	1.9
  @@ -66,7 +66,7 @@
   import java.util.Set;
   
   import org.apache.commons.jrcs.util.ToString;
  -
  +import org.apache.commons.jrcs.diff.myers.MyersDiff;
   /**
    * Implements a differencing engine that works on arrays of {@link Object Object}.
    *
  @@ -144,7 +144,7 @@
   
       protected DiffAlgorithm defaultAlgorithm()
       {
  -        return new SimpleDiff();
  +        return new MyersDiff();
       }
   
       /**
  @@ -227,11 +227,22 @@
           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));
  @@ -258,12 +269,23 @@
           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);
       }
   
  -    public static Object[] shuffle(Object[] text, long seed)
  +    /**
  +    * 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);
  
  
  
  1.2       +13 -12    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.1
  retrieving revision 1.2
  diff -u -r1.1 -r1.2
  --- MyersDiff.java	5 May 2003 23:02:16 -0000	1.1
  +++ MyersDiff.java	6 May 2003 14:26:05 -0000	1.2
  @@ -93,8 +93,10 @@
        * @param orig The original sequence.
        * @param rev The revised sequence.
        * @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)
  +        throws DifferentiationFailedException
       {
           int n = orig.length;
           int m = rev.length;
  @@ -103,7 +105,7 @@
           PathNode diagonal[] = new PathNode[1 + 2 * max];
           int middle = (diagonal.length + 1) / 2;
   
  -        PathNode node = null;
  +        PathNode path = null;
   
           int d = 0;
           diagonal[middle + 1] = new PathNode(0, -1);
  @@ -140,12 +142,11 @@
                   diagonal[kmiddle] = new PathNode(i, j, prev);
                   if (i >= n && j >= m)
                   {
  -                    node = diagonal[kmiddle];
  -                    break outer;
  +                    return diagonal[kmiddle];
                   }
               }
           }
  -        return node;
  +        throw new DifferentiationFailedException("could not find a diff path");
       }
   
       /**
  @@ -155,7 +156,8 @@
        * @param orig The original sequence.
        * @param rev The revised sequence.
        * @return A {@link Revision} script corresponding to the path.
  -     * @throws DifferentiationFailedException
  +     * @throws DifferentiationFailedException if the {@link Revision} could
  +     *         not be built.
        */
       public Revision buildRevision(PathNode path, Object[] orig, Object[] rev)
       {
  @@ -163,7 +165,7 @@
               throw new IllegalArgumentException("path is null");
           if (orig == null)
               throw new IllegalArgumentException("original sequence is null");
  -        if (path == null)
  +        if (rev == null)
               throw new IllegalArgumentException("revised sequence is null");
   
           Revision revision = new Revision();
  @@ -171,13 +173,13 @@
           {
               int i = path.i;
               int j = path.j;
  -            while (i > 0 && j > 0 && orig[i - 1].equals(rev[j - 1]))
  +            while (i > 0 && j > 0
  +                   && i > path.prev.i && j > path.prev.j
  +                   && orig[i - 1].equals(rev[j - 1]))
               { // reverse snake
                   i--;
                   j--;
               }
  -            if (i < 0 && j < 0)
  -                break;
   
               int ia;
               int ja;
  @@ -188,8 +190,7 @@
                   ja = path.j;
               }
               while (path.prev != null
  -                   && (ia == 0 || ja == 0
  -                       || !orig[ia - 1].equals(rev[ja - 1]))
  +                   && (ia == path.prev.i || ja == path.prev.j)
                      ); // while no snake
   
               Delta delta = Delta.newDelta(new Chunk(orig, ia, i - ia),
  
  
  
  1.5       +10 -10    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.4
  retrieving revision 1.5
  diff -u -r1.4 -r1.5
  --- DiffTest.java	5 May 2003 21:49:29 -0000	1.4
  +++ DiffTest.java	6 May 2003 14:26:05 -0000	1.5
  @@ -247,9 +247,9 @@
           orig = random;
       }
     }
  -  
  +
     public void testVisitor()
  -  {    
  +  {
         Object[] orig = new String[] {
                      "[1] one",
                      "[2] two",
  @@ -266,27 +266,27 @@
                      "[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 {           
  +      try {
             Diff.diff(orig, rev).accept(visitor);
             assertEquals(visitor.toString(),
               "visited Revision\n" +
  @@ -301,7 +301,7 @@
     public void testAlternativeAlgorithm()
     throws DifferentiationFailedException, PatchFailedException
     {
  -    Revision revision = Diff.diff(original, rev2, SimpleDiff.getInstance());
  +    Revision revision = Diff.diff(original, rev2, new SimpleDiff());
       assertEquals(1, revision.size());
       assertEquals(ChangeDelta.class, revision.getDelta(0).getClass());
       assertTrue(Diff.compare(revision.patch(original), rev2));
  
  
  

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