##// END OF EJS Templates
jro_apps » redmine
RSS
Fixed: https urls in the wiki are not displayed as external (closes #943)....
Fixed: https urls in the wiki are not displayed as external (closes #943). git-svn-id: http://redmine.rubyforge.org/svn/trunk@1301 e93f8b46-1217-0410-a6f0-8f06a7374b81
Jean-Philippe Lang - - Load All Authors

File last commit:

r580:5e20417e6d52
r1286:85858cebe64a
Show More
diff.rb
280 lines | 5.5 KiB | text/x-ruby | RubyLexer
/ lib / diff.rb
History | Source | Raw |Copy content |Copy permalink
Jean-Philippe Lang
Added wiki diff....
 r580 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
module Diffable
def diff(b)
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