class DocDiff::Diff

Public Class Methods

algorithm(algorithm) click to toggle source
# File lib/docdiff/diff.rb, line 144
def Diff.algorithm(algorithm)
  case algorithm
  when :shortestpath
    return ShortestPath
  when :contours
    return Contours
  when :speculative
    return Speculative
  else
    raise ArgumentError.new("unknown diff algorithm: #{algorithm}")
  end
end
new(a, b) click to toggle source
# File lib/docdiff/diff.rb, line 55
def initialize(a, b)
  @original_a = a
  @original_b = b

  count_a = {}
  count_a.default = 0
  a.each {|e| count_a[e] += 1}

  count_b = {}
  count_b.default = 0
  b.each {|e| count_b[e] += 1}

  beg_a = 0
  end_a = a.length

  beg_b = 0
  end_b = b.length

  @prefix_lcs = []
  @suffix_lcs = []

  flag = true
  while flag
    flag = false

    while beg_a < end_a && beg_b < end_b && a[beg_a].eql?(b[beg_b])
      @prefix_lcs << [beg_a, beg_b]
      count_a[a[beg_a]] -= 1
      count_b[b[beg_b]] -= 1
      beg_a += 1
      beg_b += 1
      flag = true
    end

    while beg_a < end_a && beg_b < end_b && a[end_a - 1].eql?(b[end_b - 1])
      @suffix_lcs << [end_a - 1, end_b - 1]
      count_a[a[end_a - 1]] -= 1
      count_b[b[end_b - 1]] -= 1
      end_a -= 1
      end_b -= 1
      flag = true
    end

    while beg_a < end_a && count_b[a[beg_a]] == 0
      count_a[a[beg_a]] -= 1
      beg_a += 1
      flag = true
    end

    while beg_b < end_b && count_a[b[beg_b]] == 0
      count_b[b[beg_b]] -= 1
      beg_b += 1
      flag = true
    end

    while beg_a < end_a && count_b[a[end_a - 1]] == 0
      count_a[a[end_a - 1]] -= 1
      end_a -= 1
      flag = true
    end

    while beg_b < end_b && count_a[b[end_b - 1]] == 0
      count_b[b[end_b - 1]] -= 1
      end_b -= 1
      flag = true
    end
  end

  @alphabet = Alphabet.new

  @a = []
  @revert_index_a = []
  (beg_a...end_a).each {|i|
    if count_b[a[i]] != 0
      @a << @alphabet.add(a[i])
      @revert_index_a << i
    end
  }

  @b = []
  @revert_index_b = []
  (beg_b...end_b).each {|i|
    if count_a[b[i]] != 0
      @b << @alphabet.add(b[i])
      @revert_index_b << i
    end
  }
end
rcsdiff(a, b) click to toggle source
# File lib/docdiff/diff/rcsdiff.rb, line 3
def Diff.rcsdiff(a, b)
  al = []
  a.each_line {|l| al << l}
  bl = []
  b.each_line {|l| bl << l}
  return Diff.new(al, bl).ses.rcsdiff
end
unidiff(a, b, algorithm=nil) click to toggle source
# File lib/docdiff/diff/unidiff.rb, line 3
def Diff.unidiff(a, b, algorithm=nil)
  al = []
  a.each_line {|l| al << l}
  bl = []
  b.each_line {|l| bl << l}
  return Diff.new(al, bl).ses(algorithm).unidiff
end

Public Instance Methods

lcs(algorithm=:speculative) click to toggle source
# File lib/docdiff/diff.rb, line 157
def lcs(algorithm=:speculative) # longest common subsequence
  klass = Diff.algorithm(algorithm)
  reduced_lcs = klass.new(@a, @b).lcs

  lcs = Subsequence.new
  @prefix_lcs.each {|i, j| lcs.add i, j}
  reduced_lcs.each {|i, j, l|
    l.times {|k|
      lcs.add @revert_index_a[i+k], @revert_index_b[j+k]
    }
  }
  @suffix_lcs.reverse_each {|i, j| lcs.add i, j}

  return lcs
end
ses(algorithm=nil) click to toggle source
# File lib/docdiff/diff.rb, line 173
def ses(algorithm=nil) # shortest edit script
  algorithm ||= :speculative
  lcs = lcs(algorithm)
  ses = EditScript.new
  i0 = j0 = 0
  lcs.each {|i, j, l|
    ses.del @original_a[i0, i - i0] if i0 < i
    ses.add @original_b[j0, j - j0] if j0 < j
    ses.common @original_a[i, l], @original_b[j, l]

    i0 = i + l
    j0 = j + l
  }

  i = @original_a.length
  j = @original_b.length
  ses.del @original_a[i0, i - i0] if i0 < i
  ses.add @original_b[j0, j - j0] if j0 < j

  return ses
end