class DocDiff::Diff::Contours

Public Class Methods

new(a, b) click to toggle source
# File lib/docdiff/diff/contours.rb, line 52
def initialize(a, b)
  @a = a
  @b = b
  @closest_a = Closest.new(@a)
  @closest_b = Closest.new(@b)
end

Public Instance Methods

contourCrossed(fc, bc) click to toggle source
# File lib/docdiff/diff/contours.rb, line 269
def contourCrossed(fc, bc)
  #p [:contourCrossed1Beg, fc, bc]
  new_fc, new_bc = contourCrossed1(fc, bc)
  #p [:contourCrossed1End, new_fc, new_bc]
  if new_fc.empty? && new_bc.empty?
    return true
  end

  fc.replace new_fc
  bc.replace new_bc

  return false
end
contourCrossed1(fc, bc) click to toggle source
# File lib/docdiff/diff/contours.rb, line 283
def contourCrossed1(fc, bc)
  new_fc = []
  new_bc = []
  fc_k = 0
  bc_k = 0
  bc_j = bc[0][1]
  fc_j = fc[0][1]
  fc_j = bc_j if fc_j < bc_j
  fc_j += 1
  while fc_k < fc.length || bc_k < bc.length
    if bc_k < bc.length && (!(fc_k < fc.length) || bc[bc_k][0] <= fc[fc_k][0])
      if fc_j < bc[bc_k][1]
        new_bc << bc[bc_k]
      end
      bc_k += 1
      bc_j = bc_k < bc.length ? bc[bc_k][1] : 0
    end

    if fc_k < fc.length && (!(bc_k < bc.length) || fc[fc_k][0] < bc[bc_k][0])
      if fc[fc_k][1] < bc_j
        new_fc << fc[fc_k]
      end
      fc_j = fc[fc_k][1]
      fc_k += 1
    end
  end
  return new_fc, new_bc
end
lcs(lcs=Subsequence.new, beg_a=0, beg_b=0, end_a=@a.length, end_b=@b.length, len=nil) click to toggle source
# File lib/docdiff/diff/contours.rb, line 59
def lcs(lcs=Subsequence.new, beg_a=0, beg_b=0, end_a=@a.length, end_b=@b.length, len=nil)
  #p [:lcs, beg_a, beg_b, end_a, end_b]
  found, len, mid_a, mid_b = midpoint(beg_a, beg_b, end_a, end_b, len)

  return lcs unless found

  len1 = len2 = len / 2
  if len & 1 == 0
    len2 -= 1
  end

  l = 1

  while beg_a < mid_a && beg_b < mid_b && @a[mid_a-1] == @b[mid_b-1]
    len1 -= 1
    mid_a -= 1
    mid_b -= 1
    l += 1
  end

  while mid_a+l < end_a && mid_b+l < end_b && @a[mid_a+l] == @b[mid_b+l]
    len2 -= 1
    l += 1
  end

  lcs(lcs, beg_a, beg_b, mid_a, mid_b, len1)
  lcs.add(mid_a, mid_b, l)
  lcs(lcs, mid_a + l, mid_b + l, end_a, end_b, len2)

  return lcs
end
midpoint(beg_a, beg_b, end_a, end_b, len) click to toggle source
# File lib/docdiff/diff/contours.rb, line 91
def midpoint(beg_a, beg_b, end_a, end_b, len)
  return false, 0, nil, nil if len == 0

  fc = newForwardContour(beg_a, beg_b, end_a, end_b)
  return false, 0, nil, nil if fc.empty?

  bc = newBackwardContour(beg_a, beg_b, end_a, end_b)

  midpoints = nil

  l = 1

  while true
    crossed = contourCrossed(fc, bc)
    if crossed
      midpoints = fc
      break
    end
    l += 1
    fc = nextForwardContour(fc, end_a, end_b)
    crossed = contourCrossed(fc, bc)
    if crossed
      midpoints = bc
      break
    end
    l += 1
    bc = nextBackwardContour(bc, beg_a, beg_b)
  end

  # select a dominant match which is closest to diagonal.
  m = midpoints[0]
  (1...midpoints.length).each {|m1| m = m1 if m[0] < m1[0] && m[1] < m1[1] }

  return [true, l, *m]
end
newBackwardContour(beg_a, beg_b, end_a, end_b) click to toggle source
# File lib/docdiff/diff/contours.rb, line 198
def newBackwardContour(beg_a, beg_b, end_a, end_b)
  return nextBackwardContour([[end_a,end_b]], beg_a, beg_b)
end
newForwardContour(beg_a, beg_b, end_a, end_b) click to toggle source
# File lib/docdiff/diff/contours.rb, line 127
def newForwardContour(beg_a, beg_b, end_a, end_b)
  return nextForwardContour([[beg_a-1,beg_b-1]], end_a, end_b)
end
nextBackwardContour(bc0, beg_a, beg_b) click to toggle source
# File lib/docdiff/diff/contours.rb, line 202
def nextBackwardContour(bc0, beg_a, beg_b)
  next_dominants = []
  topright_dominant = 0
  bottomleft_dominant = bc0.length - 1

  bc0.each_index {|k|
    i, j = bc0[k]
    if beg_a <= i-1 && beg_b <= j-1 && @a[i-1] == @b[j-1]
      if topright_dominant <= k - 1
        nextBackwardContour1(bc0, topright_dominant, k - 1, beg_a, j, next_dominants)
      end
      next_dominants << [i-1, j-1]
      beg_a = i
      topright_dominant = k + 1
    end
  }

  if topright_dominant <= bottomleft_dominant
    nextBackwardContour1(bc0, topright_dominant, bottomleft_dominant, beg_a, beg_b, next_dominants)
  end
  return next_dominants
end
nextBackwardContour1(bc0, topright_dominant, bottomleft_dominant, beg_a, beg_b, next_dominants_topright) click to toggle source
# File lib/docdiff/diff/contours.rb, line 225
def nextBackwardContour1(bc0, topright_dominant, bottomleft_dominant, beg_a, beg_b, next_dominants_topright)
  end_a = bc0[bottomleft_dominant][0]
  end_b = bc0[topright_dominant][1]

  next_dominants_bottomleft = []

  while beg_a < end_a && beg_b < end_b
    if end_a - beg_a < end_b - beg_b
      # search bottom row: [end_a-1, end_b-1] from [end_a-1, beg_b]
      if 0 <= bottomleft_dominant - 1 && end_a - 1 < bc0[bottomleft_dominant - 1][0]
        bottomleft_dominant -= 1
      end
      search_end_b = bc0[bottomleft_dominant][1]
      # search bottom row: [end_a-1, search_end_b-1] from [end_a-1, beg_b]
      j = @closest_b.prev(@a[end_a-1], search_end_b)
      if beg_b <= j
        # new dominant found.
        # it means that the rectangle [beg_a, beg_b] to [end_a-1, j] is not required to search any more.
        next_dominants_bottomleft << [end_a-1, j]
        beg_b = j + 1
      end
      end_a -= 1
    else
      # search right column: [end_a-1, end_b-1] to [beg_a, end_b-1]
      if topright_dominant + 1 < bc0.length && end_b - 1 < bc0[topright_dominant + 1][1]
        topright_dominant += 1
      end
      search_end_a = bc0[topright_dominant][0]
      # search right column: [search_end_a-1, end_b-1] to [beg_a, end_b-1]
      i = @closest_a.prev(@b[end_b-1], search_end_a)
      if beg_a <= i
        # new dominant found.
        # if means that the rectangle [beg_a, beg_b] to [i, end_b-1] is not required to search any more.
        next_dominants_topright << [i, end_b-1]
        beg_a = i + 1
      end
      end_b -= 1
    end
  end

  next_dominants_bottomleft.reverse!
  next_dominants_topright.concat next_dominants_bottomleft
end
nextForwardContour(fc0, end_a, end_b) click to toggle source
# File lib/docdiff/diff/contours.rb, line 131
def nextForwardContour(fc0, end_a, end_b)
  next_dominants = []
  topright_dominant = 0
  bottomleft_dominant = fc0.length - 1

  fc0.each_index {|k|
    i, j = fc0[k]
    if i+1 < end_a && j+1 < end_b && @a[i+1] == @b[j+1]
      if topright_dominant <= k - 1
        nextForwardContour1(fc0, topright_dominant, k - 1, i+1, end_b, next_dominants)
      end
      next_dominants << [i+1, j+1]
      end_b = j+1
      topright_dominant = k + 1
    end
  }

  if topright_dominant <= bottomleft_dominant
    nextForwardContour1(fc0, topright_dominant, bottomleft_dominant, end_a, end_b, next_dominants)
  end
  return next_dominants
end
nextForwardContour1(fc0, topright_dominant, bottomleft_dominant, end_a, end_b, next_dominants_topright) click to toggle source
# File lib/docdiff/diff/contours.rb, line 154
def nextForwardContour1(fc0, topright_dominant, bottomleft_dominant, end_a, end_b, next_dominants_topright)
  beg_a = fc0[topright_dominant][0] + 1
  beg_b = fc0[bottomleft_dominant][1] + 1

  next_dominants_bottomleft = []

  while beg_a < end_a && beg_b < end_b
    if end_a - beg_a < end_b - beg_b
      # search top row: [beg_a, beg_b] to [beg_a, end_b-1] inclusive
      if topright_dominant + 1 < fc0.length && fc0[topright_dominant + 1][0] < beg_a
        topright_dominant += 1
      end
      search_start_b = fc0[topright_dominant][1]
      # search top row: [beg_a, search_start_b+1] to [beg_a, end_b-1] inclusive
      j = @closest_b.next(@a[beg_a], search_start_b)
      if j < end_b
        # new dominant found.
        # it means that the rectangle [beg_a, j] to [end_a-1, end_b-1] is not required to search any more.
        next_dominants_topright << [beg_a, j]
        end_b = j
      end
      beg_a += 1
    else
      # search left column: [beg_a, beg_b] to [end_a-1, beg_b]
      if 0 <= bottomleft_dominant - 1 && fc0[bottomleft_dominant - 1][1] < beg_b
        bottomleft_dominant -= 1
      end
      search_start_a = fc0[bottomleft_dominant][0]
      # search left column: [search_start_a, beg_b] to [end_a-1, beg_b]
      i = @closest_a.next(@b[beg_b], search_start_a)
      if i < end_a
        # new dominant found.
        # if means that the rectangle [i, beg_b] to [end_a-1, end_b-1] is not required to search any more.
        next_dominants_bottomleft << [i, beg_b]
        end_a = i
      end
      beg_b += 1
    end
  end

  next_dominants_bottomleft.reverse!
  next_dominants_topright.concat next_dominants_bottomleft
end