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 Mon, 05 May 2003 23:02:16 GMT
juanco      2003/05/05 16:02:16

  Added:       jrcs/src/java/org/apache/commons/jrcs/diff/myers
                        MyersDiff.java PathNode.java
  Log:
  A clean-room implementation of Eugene Myers differencing algorithm.
  
  see:
  
    http://www.cs.arizona.edu/people/gene/
  
  The paper is at;
  
    http://www.cs.arizona.edu/people/gene/PAPERS/diff.ps
  
  Revision  Changes    Path
  1.1                  jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/myers/MyersDiff.java
  
  Index: MyersDiff.java
  ===================================================================
  /* ====================================================================
   * 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/>.
   */
  
  package org.apache.commons.jrcs.diff.myers;
  
  import org.apache.commons.jrcs.diff.*;
  
  /**
   * A clean-room implementation of
   * <a href="http://www.cs.arizona.edu/people/gene/">
   * Eugene Myers</a> differencing algorithm.
   * <p>
   * See the paper at
   * <a href="http://www.cs.arizona.edu/people/gene/PAPERS/diff.ps">
   * Myers' site</a>
   *
   * @version $Revision: 1.1 $ $Date: 2003/05/05 23:02:16 $
   * @author <a href="mailto:juanco@suigeneris.org">Juanco Anez</a>
   * @see Delta
   * @see Revision
   * @see Diff
   */
  public class MyersDiff
      implements DiffAlgorithm
  {
      public MyersDiff()
      {
      }
  
      public Revision diff(Object[] orig, Object[] rev)
          throws DifferentiationFailedException
      {
          PathNode path = buildPath(orig, rev);
          return buildRevision(path, orig, rev);
      }
  
      /**
       * Computes the minimum diffpath that expresses de differences
       * between the original and revised sequences, according
       * to Gene Myers differencing algorithm.
       *
       * @param orig The original sequence.
       * @param rev The revised sequence.
       * @return A minimum {@link PathNode Path} accross the differences graph.
       */
      public PathNode buildPath(Object[] orig, Object[] rev)
      {
          int n = orig.length;
          int m = rev.length;
  
          int max = n + m + 1;
          PathNode diagonal[] = new PathNode[1 + 2 * max];
          int middle = (diagonal.length + 1) / 2;
  
          PathNode node = null;
  
          int d = 0;
          diagonal[middle + 1] = new PathNode(0, -1);
          outer:for (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;
  
                  int i;
                  if ( (k == -d) ||
                      (k != d && diagonal[kminus].i < diagonal[kplus].i))
                  {
                      i = diagonal[kplus].i;
                      prev = diagonal[kplus];
                  }
                  else
                  {
                      i = diagonal[kminus].i + 1;
                      prev = diagonal[kminus];
                  }
                  if (prev.i < 0 || prev.j < 0)
                      prev = null;
  
                  int j = i - k;
                  while (i < n && j < m && orig[i].equals(rev[j]))
                  {
                      i++;
                      j++;
                  }
                  diagonal[kmiddle] = new PathNode(i, j, prev);
                  if (i >= n && j >= m)
                  {
                      node = diagonal[kmiddle];
                      break outer;
                  }
              }
          }
          return node;
      }
  
      /**
       * Constructs a {@link Revision} from a difference path.
       *
       * @param path The path.
       * @param orig The original sequence.
       * @param rev The revised sequence.
       * @return A {@link Revision} script corresponding to the path.
       * @throws DifferentiationFailedException
       */
      public Revision buildRevision(PathNode path, Object[] orig, Object[] rev)
      {
          if (path == null)
              throw new IllegalArgumentException("path is null");
          if (orig == null)
              throw new IllegalArgumentException("original sequence is null");
          if (path == null)
              throw new IllegalArgumentException("revised sequence is null");
  
          Revision revision = new Revision();
          while (path != null && path.prev != null)
          {
              int i = path.i;
              int j = path.j;
              while (i > 0 && j > 0 && orig[i - 1].equals(rev[j - 1]))
              { // reverse snake
                  i--;
                  j--;
              }
              if (i < 0 && j < 0)
                  break;
  
              int ia;
              int ja;
              do
              {
                  path = path.prev;
                  ia = path.i;
                  ja = path.j;
              }
              while (path.prev != null
                     && (ia == 0 || ja == 0
                         || !orig[ia - 1].equals(rev[ja - 1]))
                     ); // while no snake
  
              Delta delta = Delta.newDelta(new Chunk(orig, ia, i - ia),
                                           new Chunk(rev, ja, j - ja));
              revision.insertDelta(delta);
          }
          return revision;
      }
  
  }
  
  
  1.1                  jakarta-commons-sandbox/jrcs/src/java/org/apache/commons/jrcs/diff/myers/PathNode.java
  
  Index: PathNode.java
  ===================================================================
  package org.apache.commons.jrcs.diff.myers;
  
  /* ====================================================================
   * 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/>.
   */
  
  /**
   * A node in a difference path.
   *
   * @version $Revision: 1.1 $ $Date: 2003/05/05 23:02:16 $
   * @author <a href="mailto:juanco@suigeneris.org">Juanco Anez</a>
   */
  
  public final class PathNode
  {
      public final int i;
      public final int j;
      public final PathNode prev;
  
      /**
       * Creates a diffpath of a single node.
       * @param i The position in the original sequence.
       * @param j The position in the revised sequence.
       */
      public PathNode(int i, int j)
      {
          this(i, j, null);
      }
  
      /**
       * Adds a node to 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.
       */
      public PathNode(int i, int j, PathNode prev)
      {
          if (prev != null && (i - prev.i) == (j - prev.j))
              throw new IllegalArgumentException("node points to a diagonal");
          this.i = i;
          this.j = j;
          this.prev = prev;
      }
  
      public String toString()
      {
          StringBuffer buf = new StringBuffer("[");
          PathNode node = this;
          while (node != null)
          {
              buf.append("(");
              buf.append(Integer.toString(node.i));
              buf.append(",");
              buf.append(Integer.toString(node.j));
              buf.append(")");
              node = node.prev;
          }
          buf.append("]");
          return buf.toString();
      }
  }
  
  

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