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