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 96
def initialize(a, b)
  @hunks = []
  diff(a, b)
end

Public Instance Methods

editScript() click to toggle source
# File lib/taskjuggler/AlgorithmDiff.rb, line 115
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 136
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 102
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 130
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 177
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 266
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 142
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 276
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 242
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 228
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