class Diff
This class is an implementation of the classic UNIX diff functionality. It’s based on an original implementation by Lars Christensen, which based his version on the Perl Algorithm::Diff implementation. This is largely a from-scratch implementation that tries to have a less intrusive and more user-friendly interface. But some code fragments are very similar to the original and are copyright © 2001 Lars Christensen.
Public Class Methods
new(a, b)
click to toggle source
Create a new Diff
between the a list and b list.
# File lib/taskjuggler/AlgorithmDiff.rb, line 97 def initialize(a, b) @hunks = [] diff(a, b) end
Public Instance Methods
editScript()
click to toggle source
# File lib/taskjuggler/AlgorithmDiff.rb, line 116 def editScript script = [] @hunks.each do |hunk| if hunk.delete? script << "#{hunk.aIdx + 1}d#{hunk.deleteValues.length}" end if hunk.insert? script << "#{hunk.bIdx + 1}i#{hunk.insertValues.join(',')}" end end script end
inspect()
click to toggle source
# File lib/taskjuggler/AlgorithmDiff.rb, line 137 def inspect puts to_s end
patch(values)
click to toggle source
Modify the values list according to the stored diff information.
# File lib/taskjuggler/AlgorithmDiff.rb, line 103 def patch(values) res = values.dup @hunks.each do |hunk| if hunk.delete? res.slice!(hunk.bIdx, hunk.deleteValues.length) end if hunk.insert? res.insert(hunk.bIdx, *hunk.insertValues) end end res end
to_s()
click to toggle source
Return the diff list as standard UNIX diff output.
# File lib/taskjuggler/AlgorithmDiff.rb, line 131 def to_s str = +'' @hunks.each { |hunk| str << hunk.to_s } str end
Private Instance Methods
computeIndexTranslations(a, b)
click to toggle source
# File lib/taskjuggler/AlgorithmDiff.rb, line 178 def computeIndexTranslations(a, b) aEndIdx = a.length - 1 bEndIdx = b.length - 1 startIdx = 0 indexTranslationTable = [] while (startIdx < aEndIdx && startIdx < bEndIdx && a[startIdx] == b[startIdx]) indexTranslationTable[startIdx] = startIdx startIdx += 1 end while (aEndIdx >= startIdx && bEndIdx >= startIdx && a[aEndIdx] == b[bEndIdx]) indexTranslationTable[aEndIdx] = bEndIdx aEndIdx -= 1 bEndIdx -= 1 end return indexTranslationTable if startIdx >= aEndIdx && startIdx >= bEndIdx links = [] thresholds = [] bHashesToIndicies = reverseHash(b, startIdx, bEndIdx) startIdx.upto(aEndIdx) do |ai| aValue = a[ai] next unless bHashesToIndicies.has_key? aValue k = nil bHashesToIndicies[aValue].each do |bi| if k && (thresholds[k] > bi) && (thresholds[k - 1] < bi) thresholds[k] = bi else k = replaceNextLarger(thresholds, bi, k) end links[k] = [ k == 0 ? nil : links[k - 1], ai, bi ] if k end end if !thresholds.empty? link = links[thresholds.length - 1] while link indexTranslationTable[link[1]] = link[2] link = link[0] end end return indexTranslationTable end
deleteElement(aIdx, bIdx, value)
click to toggle source
# File lib/taskjuggler/AlgorithmDiff.rb, line 267 def deleteElement(aIdx, bIdx, value) if @hunks.empty? || @hunks.last.aIdx + @hunks.last.deleteValues.length != aIdx @hunks << (hunk = Hunk.new(aIdx, bIdx)) else hunk = @hunks.last end hunk.deleteValues << value end
diff(a, b)
click to toggle source
# File lib/taskjuggler/AlgorithmDiff.rb, line 143 def diff(a, b) indexTranslationTable = computeIndexTranslations(a, b) ai = bi = 0 tableLength = indexTranslationTable.length while ai < tableLength do # Check if value from index ai should be included in B. destIndex = indexTranslationTable[ai] if destIndex # Yes, it needs to go to position destIndex. All values from bi to # newIndex - 1 are new values in B, not in A. while bi < destIndex insertElement(ai, bi, b[bi]) bi += 1 end bi += 1 else # No, it's not in B. Put it onto the deletion list. deleteElement(ai, bi, a[ai]) end ai += 1 end # The remainder of the A list has to be deleted. while ai < a.length deleteElement(ai, bi, a[ai]) ai += 1 end # The remainder of the B list are new values. while bi < b.length insertElement(ai, bi, b[bi]) bi += 1 end end
insertElement(aIdx, bIdx, value)
click to toggle source
# File lib/taskjuggler/AlgorithmDiff.rb, line 277 def insertElement(aIdx, bIdx, value) if @hunks.empty? || @hunks.last.bIdx + @hunks.last.insertValues.length != bIdx @hunks << (hunk = Hunk.new(aIdx, bIdx)) else hunk = @hunks.last end hunk.insertValues << value end
replaceNextLarger(ary, value, high = nil)
click to toggle source
# File lib/taskjuggler/AlgorithmDiff.rb, line 243 def replaceNextLarger(ary, value, high = nil) high ||= ary.length if ary.empty? || value > ary[-1] ary.push value return high end low = 0 while low < high index = (high + low) / 2 found = ary[index] return nil if value == found if value > found low = index + 1 else high = index end end ary[low] = value low end
reverseHash(values, startIdx, endIdx)
click to toggle source
# File lib/taskjuggler/AlgorithmDiff.rb, line 229 def reverseHash(values, startIdx, endIdx) hash = {} startIdx.upto(endIdx) do |i| element = values[i] if hash.has_key?(element) hash[element].insert(0, i) else hash[element] = [ i ] end end hash end