view lib/diff.rb @ 1082:997f6d7738f7 bug_531

In repo controller entry action, show the page for the file even if it's binary (so user still has access to history etc links). This makes it possible to use the entry action as the default when a file is clicked on

module RedmineDiff
  class Diff

    VERSION = 0.3

    def Diff.lcs(a, b)
      astart = 0
      bstart = 0
      afinish = a.length-1
      bfinish = b.length-1
      mvector = []

      # First we prune off any common elements at the beginning
      while (astart <= afinish && bstart <= afinish && a[astart] == b[bstart])
        mvector[astart] = bstart
        astart += 1
        bstart += 1
      end

      # now the end
      while (astart <= afinish && bstart <= bfinish && a[afinish] == b[bfinish])
        mvector[afinish] = bfinish
        afinish -= 1
        bfinish -= 1
      end

      bmatches = b.reverse_hash(bstart..bfinish)
      thresh = []
      links = []

      (astart..afinish).each { |aindex|
        aelem = a[aindex]
        next unless bmatches.has_key? aelem
        k = nil
        bmatches[aelem].reverse.each { |bindex|
    if k && (thresh[k] > bindex) && (thresh[k-1] < bindex)
      thresh[k] = bindex
    else
      k = thresh.replacenextlarger(bindex, k)
    end
    links[k] = [ (k==0) ? nil : links[k-1], aindex, bindex ] if k
        }
      }

      if !thresh.empty?
        link = links[thresh.length-1]
        while link
    mvector[link[1]] = link[2]
    link = link[0]
        end
      end

      return mvector
    end

    def makediff(a, b)
      mvector = Diff.lcs(a, b)
      ai = bi = 0
      while ai < mvector.length
        bline = mvector[ai]
        if bline
    while bi < bline
      discardb(bi, b[bi])
      bi += 1
    end
    match(ai, bi)
    bi += 1
        else
    discarda(ai, a[ai])
        end
        ai += 1
      end
      while ai < a.length
        discarda(ai, a[ai])
        ai += 1
      end
      while bi < b.length
        discardb(bi, b[bi])
        bi += 1
      end
      match(ai, bi)
      1
    end

    def compactdiffs
      diffs = []
      @diffs.each { |df|
        i = 0
        curdiff = []
        while i < df.length
    whot = df[i][0]
    s = @isstring ? df[i][2].chr : [df[i][2]]
    p = df[i][1]
    last = df[i][1]
    i += 1
    while df[i] && df[i][0] == whot && df[i][1] == last+1
      s << df[i][2]
      last  = df[i][1]
      i += 1
    end
    curdiff.push [whot, p, s]
        end
        diffs.push curdiff
      }
      return diffs
    end

    attr_reader :diffs, :difftype

    def initialize(diffs_or_a, b = nil, isstring = nil)
      if b.nil?
        @diffs = diffs_or_a
        @isstring = isstring
      else
        @diffs = []
        @curdiffs = []
        makediff(diffs_or_a, b)
        @difftype = diffs_or_a.class
      end
    end

    def match(ai, bi)
      @diffs.push @curdiffs unless @curdiffs.empty?
      @curdiffs = []
    end

    def discarda(i, elem)
      @curdiffs.push ['-', i, elem]
    end

    def discardb(i, elem)
      @curdiffs.push ['+', i, elem]
    end

    def compact
      return Diff.new(compactdiffs)
    end

    def compact!
      @diffs = compactdiffs
    end

    def inspect
      @diffs.inspect
    end

  end
end

module Diffable
  def diff(b)
    RedmineDiff::Diff.new(self, b)
  end

  # Create a hash that maps elements of the array to arrays of indices
  # where the elements are found.

  def reverse_hash(range = (0...self.length))
    revmap = {}
    range.each { |i|
      elem = self[i]
      if revmap.has_key? elem
  revmap[elem].push i
      else
  revmap[elem] = [i]
      end
    }
    return revmap
  end

  def replacenextlarger(value, high = nil)
    high ||= self.length
    if self.empty? || value > self[-1]
      push value
      return high
    end
    # binary search for replacement point
    low = 0
    while low < high
      index = (high+low)/2
      found = self[index]
      return nil if value == found
      if value > found
  low = index + 1
      else
  high = index
      end
    end

    self[low] = value
    # $stderr << "replace #{value} : 0/#{low}/#{init_high} (#{steps} steps) (#{init_high-low} off )\n"
    # $stderr.puts self.inspect
    #gets
    #p length - low
    return low
  end

  def patch(diff)
    newary = nil
    if diff.difftype == String
      newary = diff.difftype.new('')
    else
      newary = diff.difftype.new
    end
    ai = 0
    bi = 0
    diff.diffs.each { |d|
      d.each { |mod|
  case mod[0]
  when '-'
    while ai < mod[1]
      newary << self[ai]
      ai += 1
      bi += 1
    end
    ai += 1
  when '+'
    while bi < mod[1]
      newary << self[ai]
      ai += 1
      bi += 1
    end
    newary << mod[2]
    bi += 1
  else
    raise "Unknown diff action"
  end
      }
    }
    while ai < self.length
      newary << self[ai]
      ai += 1
      bi += 1
    end
    return newary
  end
end

class Array
  include Diffable
end

class String
  include Diffable
end

=begin
  = Diff
  (({diff.rb})) - computes the differences between two arrays or
  strings. Copyright (C) 2001 Lars Christensen

  == Synopsis

      diff = Diff.new(a, b)
      b = a.patch(diff)

  == Class Diff
  === Class Methods
  --- Diff.new(a, b)
  --- a.diff(b)
        Creates a Diff object which represent the differences between
        ((|a|)) and ((|b|)). ((|a|)) and ((|b|)) can be either be arrays
        of any objects, strings, or object of any class that include
        module ((|Diffable|))

  == Module Diffable
  The module ((|Diffable|)) is intended to be included in any class for
  which differences are to be computed. Diffable is included into String
  and Array when (({diff.rb})) is (({require}))'d.

  Classes including Diffable should implement (({[]})) to get element at
  integer indices, (({<<})) to append elements to the object and
  (({ClassName#new})) should accept 0 arguments to create a new empty
  object.

  === Instance Methods
  --- Diffable#patch(diff)
        Applies the differences from ((|diff|)) to the object ((|obj|))
        and return the result. ((|obj|)) is not changed. ((|obj|)) and
        can be either an array or a string, but must match the object
        from which the ((|diff|)) was created.
=end