加载中…
个人资料
微博
  • 博客等级：
  • 博客积分：
  • 博客访问：
  • 关注人气：
  • 获赠金笔：0支
  • 赠出金笔：0支
  • 荣誉徽章：
正文 字体大小：大 中 小

Java Diff算法实现

(2013-12-17 21:13:41)
标签：

java

diff算法

it

 分类： 数据结构与算法
Diff算法涉及class：
FileDiff.java
Difference.java
Diff.java

FileDiff.java：
import java.io.*;
import java.util.*;

public class FileDiff
{
    public FileDiff(String fromFile, String toFile)
    {
        String[]         aLines = read(fromFile);
        String[]         bLines = read(toFile);
        List diffs  = (new Diff(aLines, bLines)).diff();
        
        for (Difference diff : diffs) {
            int        delStart = diff.getDeletedStart();
            int        delEnd   = diff.getDeletedEnd();
            int        addStart = diff.getAddedStart();
            int        addEnd   = diff.getAddedEnd();
            String     from     = toString(delStart, delEnd);
            String     to       = toString(addStart, addEnd);
            String     type     = delEnd != Difference.NONE && addEnd != Difference.NONE ? "c" : (delEnd == Difference.NONE ? "a" : "d");

            System.out.println(from + type + to);

            if (delEnd != Difference.NONE) {
                printLines(delStart, delEnd, "<", aLines);
                if (addEnd != Difference.NONE) {
                    System.out.println("---");
                }
            }
            if (addEnd != Difference.NONE) {
                printLines(addStart, addEnd, ">", bLines);
            }
        }
    }

    protected void printLines(int start, int end, String ind, String[] lines)
    {
        for (int lnum = start; lnum <= end; ++lnum) {
            System.out.println(ind + " " + lines[lnum]);
        }
    }

    protected String toString(int start, int end)
    {
        // adjusted, because file lines are one-indexed, not zero.
        StringBuffer buf = new StringBuffer();
        // match the line numbering from diff(1):
        buf.append(end == Difference.NONE ? start : (1 + start));
        if (end != Difference.NONE && start != end) {
            buf.append(",").append(1 + end);
        }
        return buf.toString();
    }

    protected String[] read(String fileName)
    {
        try {
            BufferedReader br       = new BufferedReader(new FileReader(fileName));
            List   contents = new ArrayList();
            
            String in;
            while ((in = br.readLine()) != null) {
                contents.add(in);
            }
            return (String[])contents.toArray(new String[] {});
        }
        catch (Exception e) {
            System.err.println("error reading " + fileName + ": " + e);
            System.exit(1);
            return null;
        }        
    }

    public static void main(String[] args)
    {
    new FileDiff("C:\\Documents and Settings\\Administrator\\桌面\\DesignPattern\\1.txt", "C:\\Documents and Settings\\Administrator\\桌面\\DesignPattern\\2.txt");
    }
}

Diff.java：
import java.util.*;
public class Diff
{
   
    protected List a;
   
    protected List b;
   
    protected List diffs = new ArrayList();
   
    private Difference pending;
   
    private Comparator comparator;
   
    private TreeMap thresh;
   
    public Diff(Type[] a, Type[] b, Comparator comp)
    {
        this(Arrays.asList(a), Arrays.asList(b), comp);
    }
   
    public Diff(Type[] a, Type[] b)
    {
        this(a, b, null);
    }

   
    public Diff(List a, List b, Comparator comp)
    {
        this.a = a;
        this.b = b;
        this.comparator = comp;
        this.thresh = null;
    }

   
    public Diff(List a, List b)
    {
        this(a, b, null);
    }

   
    public List diff()
    {
        traverseSequences();

        // add the last difference, if pending:
        if (pending != null) {
            diffs.add(pending);
        }

        return diffs;
    }

   
    protected void traverseSequences()
    {
        Integer[] matches = getLongestCommonSubsequences();

        int lastA = a.size() - 1;
        int lastB = b.size() - 1;
        int bi = 0;
        int ai;

        int lastMatch = matches.length - 1;
        
        for (ai = 0; ai <= lastMatch; ++ai) {
            Integer bLine = matches[ai];

            if (bLine == null) {
                onANotB(ai, bi);
            }
            else {
                while (bi < bLine) {
                    onBNotA(ai, bi++);
                }

                onMatch(ai, bi++);
            }
        }

        boolean calledFinishA = false;
        boolean calledFinishB = false;

        while (ai <= lastA || bi <= lastB) {

            // last A?
            if (ai == lastA + 1 && bi <= lastB) {
                if (!calledFinishA && callFinishedA()) {
                    finishedA(lastA);
                    calledFinishA = true;
                }
                else {
                    while (bi <= lastB) {
                        onBNotA(ai, bi++);
                    }
                }
            }

            // last B?
            if (bi == lastB + 1 && ai <= lastA) {
                if (!calledFinishB && callFinishedB()) {
                    finishedB(lastB);
                    calledFinishB = true;
                }
                else {
                    while (ai <= lastA) {
                        onANotB(ai++, bi);
                    }
                }
            }

            if (ai <= lastA) {
                onANotB(ai++, bi);
            }

            if (bi <= lastB) {
                onBNotA(ai, bi++);
            }
        }
    }

   
    protected boolean callFinishedA()
    {
        return false;
    }

   
    protected boolean callFinishedB()
    {
        return false;
    }

   
    protected void finishedA(int lastA)
    {
    }

   
    protected void finishedB(int lastB)
    {
    }

   
    protected void onANotB(int ai, int bi)
    {
        if (pending == null) {
            pending = new Difference(ai, ai, bi, -1);
        }
        else {
            pending.setDeleted(ai);
        }
    }

   
    protected void onBNotA(int ai, int bi)
    {
        if (pending == null) {
            pending = new Difference(ai, -1, bi, bi);
        }
        else {
            pending.setAdded(bi);
        }
    }

   
    protected void onMatch(int ai, int bi)
    {
        if (pending == null) {
            // no current pending
        }
        else {
            diffs.add(pending);
            pending = null;
        }
    }

   
    protected boolean equals(Type x, Type y)
    {
        return comparator == null ? x.equals(y) : comparator.compare(x, y) == 0;
    }
    
   
    public Integer[] getLongestCommonSubsequences()
    {
        int aStart = 0;
        int aEnd = a.size() - 1;

        int bStart = 0;
        int bEnd = b.size() - 1;

        TreeMap matches = new TreeMap();

        while (aStart <= aEnd && bStart <= bEnd && equals(a.get(aStart), b.get(bStart))) {
            matches.put(aStart++, bStart++);
        }

        while (aStart <= aEnd && bStart <= bEnd && equals(a.get(aEnd), b.get(bEnd))) {
            matches.put(aEnd--, bEnd--);
        }

        Map> bMatches = null;
        if (comparator == null) {
            if (a.size() > 0 && a.get(0) instanceof Comparable) {
                // this uses the Comparable interface
                bMatches = new TreeMap>();
            }
            else {
                // this just uses hashCode()
                bMatches = new HashMap>();
            }
        }
        else {
            // we don't really want them sorted, but this is the only Map
            // implementation (as of JDK 1.4) that takes a comparator.
            bMatches = new TreeMap>(comparator);
        }

        for (int bi = bStart; bi <= bEnd; ++bi) {
            Type         element    = b.get(bi);
            Type          key       = element;
            List positions = bMatches.get(key);
            
            if (positions == null) {
                positions = new ArrayList();
                bMatches.put(key, positions);
            }
            
            positions.add(bi);
        }

        thresh = new TreeMap();
        Map links = new HashMap();

        for (int i = aStart; i <= aEnd; ++i) {
            Type aElement  = a.get(i);
            List positions = bMatches.get(aElement);

            if (positions != null) {
                Integer  k   = 0;
                ListIterator pit = positions.listIterator(positions.size());
                while (pit.hasPrevious()) {
                    Integer j = pit.previous();

                    k = insert(j, k);

                    if (k == null) {
                        // nothing
                    }
                    else {
                        Object value = k > 0 ? links.get(k - 1) : null;
                        links.put(k, new Object[] { value, i, j });
                    }   
                }
            }
        }

        if (thresh.size() > 0) {
            Integer  ti   = thresh.lastKey();
            Object[] link = (Object[])links.get(ti);
            while (link != null) {
                Integer x = (Integer)link[1];
                Integer y = (Integer)link[2];
                matches.put(x, y);
                link = (Object[])link[0];
            }
        }

        int       size = matches.size() == 0 ? 0 : 1 + matches.lastKey();
        Integer[] ary  = new Integer[size];
        for (Integer idx : matches.keySet()) {
            Integer val = matches.get(idx);
            ary[idx] = val;
        }
        return ary;
    }

   
    protected static boolean isNonzero(Integer i)
    {
        return i != null && i != 0;
    }

   
    protected boolean isGreaterThan(Integer index, Integer val)
    {
        Integer lhs = thresh.get(index);
        return lhs != null && val != null && lhs.compareTo(val) > 0;
    }

   
    protected boolean isLessThan(Integer index, Integer val)
    {
        Integer lhs = thresh.get(index);
        return lhs != null && (val == null || lhs.compareTo(val) < 0);
    }

   
    protected Integer getLastValue()
    {
        return thresh.get(thresh.lastKey());
    }

   
    protected void append(Integer value)
    {
        Integer addIdx = null;
        if (thresh.size() == 0) {
            addIdx = 0;
        }
        else {
            Integer lastKey = thresh.lastKey();
            addIdx = lastKey + 1;
        }
        thresh.put(addIdx, value);
    }

   
    protected Integer insert(Integer j, Integer k)
    {
        if (isNonzero(k) && isGreaterThan(k, j) && isLessThan(k - 1, j)) {
            thresh.put(k, j);
        }
        else {
            int high = -1;
            
            if (isNonzero(k)) {
                high = k;
            }
            else if (thresh.size() > 0) {
                high = thresh.lastKey();
            }

            // off the end?
            if (high == -1 || j.compareTo(getLastValue()) > 0) {
                append(j);
                k = high + 1;
            }
            else {
                // binary search for insertion point:
                int low = 0;
        
                while (low <= high) {
                    int     index = (high + low) / 2;
                    Integer val   = thresh.get(index);
                    int     cmp   = j.compareTo(val);

                    if (cmp == 0) {
                        return null;
                    }
                    else if (cmp > 0) {
                        low = index + 1;
                    }
                    else {
                        high = index - 1;
                    }
                }
        
                thresh.put(low, j);
                k = low;
            }
        }

        return k;
    }
}

Differnece.java:
public class Difference
{
    public static final int NONE = -1;
   
    private int delStart = NONE;
   
    private int delEnd = NONE;
   
    private int addStart = NONE;
   
    private int addEnd = NONE;
   
    public Difference(int delStart, int delEnd, int addStart, int addEnd)
    {
        this.delStart = delStart;
        this.delEnd   = delEnd;
        this.addStart = addStart;
        this.addEnd   = addEnd;
    }
   
    public int getDeletedStart()
    {
        return delStart;
    }
   
    public int getDeletedEnd()
    {
        return delEnd;
    }
   
    public int getAddedStart()
    {
        return addStart;
    }

   
    public int getAddedEnd()
    {
        return addEnd;
    }
   
    public void setDeleted(int line)
    {
        delStart = Math.min(line, delStart);
        delEnd   = Math.max(line, delEnd);
    }
   
    public void setAdded(int line)
    {
        addStart = Math.min(line, addStart);
        addEnd   = Math.max(line, addEnd);
    }
   
    public boolean equals(Object obj)
    {
        if (obj instanceof Difference) {
            Difference other = (Difference)obj;
            return (delStart == other.delStart && 
                    delEnd   == other.delEnd && 
                    addStart == other.addStart && 
                    addEnd   == other.addEnd);
        }
        else {
            return false;
        }
    }
   
    public String toString()
    {
        StringBuffer buf = new StringBuffer();
        buf.append("del: [" + delStart + ", " + delEnd + "]");
        buf.append(" ");
        buf.append("add: [" + addStart + ", " + addEnd + "]");
        return buf.toString();
    }

}

结果：
1.txt
模块原则：使用简单的接口拼合简单的部件。
清晰原则：清晰胜于技巧。
组合原则：设计时考虑拼接组合。
分离原则：策略同机制分离，接口同引擎分离。
简洁原则：设计要简洁，复杂度能低则低。
透明性原则：设计要可见，以便审查和调试。
健壮原则：健壮源于透明和简洁。
清晰原则：清晰胜于技巧。
优化原则：雕琢之前先要有原型，跑之前先学会走，不要过早优化。

2.txt
二、1.OOA是确定需求或者业务的角度，按照面向对象的思想来分析业务；OOA基本任务是在系统调查资料的基础上，针对OO方法所需要的素材进行的归类分析和整理，而不是对管理业务现状和方法的分析。
2.能否解决传统结构化开发方法中客观世界描述工具与软件结构的不一致性问题，缩短开发周期，解决从分析和设计到软件模块结构之间多次转换映射的繁杂过程。
3.面向对象设计过程： 是设计、编制、调试程序的方法和过程。它遵循以下设计原则：
模块原则：使用简单的接口拼合简单的部件。
清晰原则：清晰胜于技巧。
组合原则：设计时考虑拼接组合。
分离原则：策略同机制分离，接口同引擎分离。
简洁原则：设计要简洁，复杂度能低则低。
透明性原则：设计要可见，以便审查和调试。
健壮原则：健壮源于透明和简洁。
优化原则：雕琢之前先要有原型，跑之前先学会走，不要过早优化。
扩展原则：设计着眼于未来，未来总比预想快。
4.类是对同类事物的抽象，对象是类的具体表现。
5.单向关联，双向关联，多维关联，自身关联。1-1多维关联，1-2单向关联。

Result:

0a1,3
> 二、1.OOA是确定需求或者业务的角度，按照面向对象的思想来分析业务；OOA基本任务是在系统调查资料的基础上，针对OO方法所需要的素材进行的归类分析和整理，而不是对管理业务现状和方法的分析。
> 2.能否解决传统结构化开发方法中客观世界描述工具与软件结构的不一致性问题，缩短开发周期，解决从分析和设计到软件模块结构之间多次转换映射的繁杂过程。
> 3.面向对象设计过程： 是设计、编制、调试程序的方法和过程。它遵循以下设计原则：
8d10
< 清晰原则：清晰胜于技巧。
10c12,14
< 
---
> 扩展原则：设计着眼于未来，未来总比预想快。
> 4.类是对同类事物的抽象，对象是类的具体表现。
> 5.单向关联，双向关联，多维关联，自身关联。1-1多维关联，1-2单向关联。


喜欢

0

阅读┊ 收藏 ┊ 喜欢▼ ┊打印┊举报/Report
  

新浪BLOG意见反馈留言板　欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

Copyright © 1996 - 2022 SINA Corporation, All Rights Reserved

新浪公司 版权所有