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 Diff.java
Date Mon, 28 Apr 2003 17:22:49 GMT
juanco      2003/04/28 10:22:49

  Modified:    jrcs/src/java/org/apache/commons/jrcs/diff Diff.java
  Log:
  Improved the diff algorithm using insights from:
  
    http://apinkin.net/space/DifferenceEngine
  
  and specially Eugene Myers' paper about his excellent diff algorithm:
  
    http://www.cs.arizona.edu/people/gene/PAPERS/diff.ps
  
  the JRCS diff algorithm is still the same, simple one, but it now performs
  adequately with sequences containing repeated elements.
  
  Credits for pinpointing the problem, getting involved, and pointing to a
  solution go to:
  
    Robert MacGrogan <robertmacgrogan@yahoo.com>
    Brian McBride <bwm@hplb.hpl.hp.com>
  
  Revision  Changes    Path
  1.4       +26 -6     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.3
  retrieving revision 1.4
  diff -u -r1.3 -r1.4
  --- Diff.java	28 Sep 2002 15:57:10 -0000	1.3
  +++ Diff.java	28 Apr 2003 17:22:49 -0000	1.4
  @@ -66,6 +66,7 @@
   import java.util.Set;
   
   import org.apache.commons.jrcs.util.ToString;
  +import java.util.Iterator;
   
   
   /**
  @@ -228,8 +229,13 @@
           {
               if (items.contains(orig[i]))
               {
  -                eqs.put(orig[i], new Integer(i));
  -                items.remove(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 eqs;
  @@ -240,14 +246,28 @@
           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)
  +            List matches = (List) eqs.get(seq[i]);
  +            if (matches == null)
               {
                   result[i] = NF;
               }
               else
               {
  -                result[i] = value.intValue();
  +                Iterator match = matches.iterator();
  +                Integer value = (Integer) match.next();
  +                int j = value.intValue();
  +                int distance = Math.abs(i - j);
  +                while (match.hasNext())
  +                {
  +                    value = (Integer) match.next();
  +                    j = value.intValue();
  +                    int d = Math.abs(i - j);
  +                    if (d < distance)
  +                    {
  +                        distance = d;
  +                        result[i] = j;
  +                    }
  +                }
               }
           }
           result[seq.length] = EOS;
  
  
  

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