--- /dev/null
+module HTMLDiff
+
+ Match = Struct.new(:start_in_old, :start_in_new, :size)
+ class Match
+ def end_in_old
+ self.start_in_old + self.size
+ end
+
+ def end_in_new
+ self.start_in_new + self.size
+ end
+ end
+
+ Operation = Struct.new(:action, :start_in_old, :end_in_old, :start_in_new, :end_in_new)
+
+ class DiffBuilder
+
+ def initialize(old_version, new_version)
+ @old_version, @new_version = old_version, new_version
+ split_inputs_to_words
+ index_new_words
+ end
+
+ def split_inputs_to_words
+ @old_words = explode(@old_version)
+ @new_words = explode(@new_version)
+ end
+
+ def index_new_words
+ @word_indices = Hash.new { |h, word| h[word] = [] }
+ @new_words.each_with_index { |word, i| @word_indices[word] << i }
+ end
+
+ def operations
+ position_in_old = position_in_new = 0
+ operations = []
+
+ matches = matching_blocks
+ # an empty match at the end forces the loop below to handle the unmatched tails
+ # I'm sure it can be done more gracefully, but not at 23:52
+ matches << Match.new(@old_words.length, @new_words.length, 0)
+
+ matches.each_with_index do |match, i|
+ match_starts_at_current_position_in_old = (position_in_old == match.start_in_old)
+ match_starts_at_current_position_in_new = (position_in_new == match.start_in_new)
+
+ action_upto_match_positions =
+ case [match_starts_at_current_position_in_old, match_starts_at_current_position_in_new]
+ when [false, false]
+ :replace
+ when [true, false]
+ :insert
+ when [false, true]
+ :delete
+ else
+ # this happens if the first few words are same in both versions
+ :none
+ end
+
+ if action_upto_match_positions != :none
+ operation_upto_match_positions =
+ Operation.new(action_upto_match_positions,
+ position_in_old, match.start_in_old,
+ position_in_new, match.start_in_new)
+ operations << operation_upto_match_positions
+ end
+ if match.size != 0
+ match_operation = Operation.new(:equal,
+ match.start_in_old, match.end_in_old,
+ match.start_in_new, match.end_in_new)
+ operations << match_operation
+ end
+
+ position_in_old = match.end_in_old
+ position_in_new = match.end_in_new
+ end
+
+ operations
+ end
+
+ def matching_blocks
+ matching_blocks = []
+ recursively_find_matching_blocks(0, @old_words.size, 0, @new_words.size, matching_blocks)
+ matching_blocks
+ end
+
+ def recursively_find_matching_blocks(start_in_old, end_in_old, start_in_new, end_in_new, matching_blocks)
+ match = find_match(start_in_old, end_in_old, start_in_new, end_in_new)
+ if match
+ if start_in_old < match.start_in_old and start_in_new < match.start_in_new
+ recursively_find_matching_blocks(
+ start_in_old, match.start_in_old, start_in_new, match.start_in_new, matching_blocks)
+ end
+ matching_blocks << match
+ if match.end_in_old < end_in_old and match.end_in_new < end_in_new
+ recursively_find_matching_blocks(
+ match.end_in_old, end_in_old, match.end_in_new, end_in_new, matching_blocks)
+ end
+ end
+ end
+
+ def find_match(start_in_old, end_in_old, start_in_new, end_in_new)
+
+ best_match_in_old = start_in_old
+ best_match_in_new = start_in_new
+ best_match_size = 0
+
+ match_length_at = Hash.new { |h, index| h[index] = 0 }
+
+ start_in_old.upto(end_in_old - 1) do |index_in_old|
+
+ new_match_length_at = Hash.new { |h, index| h[index] = 0 }
+
+ @word_indices[@old_words[index_in_old]].each do |index_in_new|
+ next if index_in_new < start_in_new
+ break if index_in_new >= end_in_new
+
+ new_match_length = match_length_at[index_in_new - 1] + 1
+ new_match_length_at[index_in_new] = new_match_length
+
+ if new_match_length > best_match_size
+ best_match_in_old = index_in_old - new_match_length + 1
+ best_match_in_new = index_in_new - new_match_length + 1
+ best_match_size = new_match_length
+ end
+ end
+ match_length_at = new_match_length_at
+ end
+
+# best_match_in_old, best_match_in_new, best_match_size = add_matching_words_left(
+# best_match_in_old, best_match_in_new, best_match_size, start_in_old, start_in_new)
+# best_match_in_old, best_match_in_new, match_size = add_matching_words_right(
+# best_match_in_old, best_match_in_new, best_match_size, end_in_old, end_in_new)
+
+ return (best_match_size != 0 ? Match.new(best_match_in_old, best_match_in_new, best_match_size) : nil)
+ end
+
+ def add_matching_words_left(match_in_old, match_in_new, match_size, start_in_old, start_in_new)
+ while match_in_old > start_in_old and
+ match_in_new > start_in_new and
+ @old_words[match_in_old - 1] == @new_words[match_in_new - 1]
+ match_in_old -= 1
+ match_in_new -= 1
+ match_size += 1
+ end
+ [match_in_old, match_in_new, match_size]
+ end
+
+ def add_matching_words_right(match_in_old, match_in_new, match_size, end_in_old, end_in_new)
+ while match_in_old + match_size < end_in_old and
+ match_in_new + match_size < end_in_new and
+ @old_words[match_in_old + match_size] == @new_words[match_in_new + match_size]
+ match_size += 1
+ end
+ [match_in_old, match_in_new, match_size]
+ end
+
+ def explode(sequence)
+ sequence.is_a?(String) ? sequence.split(//) : sequence
+ end
+
+ end # of class Diff Builder
+
+end
projects / vuplus_webkit / blobdiff