The Trunk: System-ul.224.mcz

Levente Uzonyi uploaded a new version of System to project The Trunk:
http://source.squeak.org/trunk/System-ul.224.mcz

==================== Summary ====================

Name: System-ul.224
Author: ul
Time: 6 January 2010, 7:35:29 am
UUID: 6073aec0-d4d8-cd43-a35b-0e0f8354f7ed
Ancestors: System-nice.223

- decrease space usage of TextDiffBuilder

=============== Diff against System-nice.223 ===============

Item was changed:
  ----- Method: TextDiffBuilder>>lcsFor:and: (in category 'private') -----
  lcsFor: xFilteredLines and: yFilteredLines
- "I find one of the longest common subsequences of my the arguments. I assume that none of my arguments are empty. I return an OrderedCollection with 2 * L elements where L is the length of the longest common subsequence. Every odd indexed element is from the first argument others are from the second. I'm a modified version of the greedy lcs algorithm from the 6th page of 'An O(ND) Difference Algorithm and Its Variations (1986)' by Eugene W. Myers"
 
+ "I find one of the longest common subsequences of my the arguments. I assume that none of my arguments are empty. I return nil or an Array which represents a list. The first two elements are the matching line numbers, the last is the next node in the list or nil if there are no more elements. The list containts the longest common subsequence. I'm a modified version of the greedy lcs algorithm from the 6th page of 'An O(ND) Difference Algorithm and Its Variations (1986)' by Eugene W. Myers"
+
+ | n m v lcss max |
- | n m v lcs lcss max x y |
  n := xFilteredLines size.
  m := yFilteredLines size.
  max := m + n.
  v := Array new: 2 * max + 1.
  v at: max + 2 put: 0.
  lcss := Array new: 2 * max + 1.
  0 to: max do: [ :d |
  d negated to: d by: 2 do: [ :k |
+ | index lcs x y |
- | index |
  (k + d = 0 or: [ k ~= d and: [ (v at: max + k ) < (v at: max + k + 2) ] ])
  ifTrue: [
  index := max + k + 2.
  x := v at: index ]
  ifFalse: [
  index := max + k.
  x := (v at: index) + 1 ].
- lcs := nil.
  y := x - k.
+ lcs := lcss at: index.
  [ x < n and: [ y < m and: [ (xFilteredLines at: x + 1) = (yFilteredLines at: y + 1) ] ] ]
  whileTrue: [
+ lcs := { x := x + 1. y := y + 1. lcs } ].
- (lcs ifNil: [
- lcs := (lcss at: index)
- ifNil: [ OrderedCollection new ]
- ifNotNil: [ :oc | oc copy ] ])
- add: (xFilteredLines at: x + 1);
- add: (yFilteredLines at: y + 1).
- x := x + 1.
- y := y + 1 ].
- v at: max + k + 1 put: x.
- lcss at: max + k + 1 put: (lcs ifNil: [
- lcs := (lcss at: index)
- ifNil: [ nil ]
- ifNotNil: [ :oc | oc copy ] ]).
  (x >= n and: [ y >= m ]) ifTrue: [
+ ^lcs ].
+ v at: max + k + 1 put: x.
+ lcss at: max + k + 1 put: lcs ] ].
- ^lcs ifNil: [ (lcss at: index) ifNil: [ #() ] ] ] ] ].
  self error!

Item was changed:
  ----- Method: TextDiffBuilder>>findMatches (in category 'private') -----
  findMatches
  "I find the matching pairs of xLines and yLines. First I filter out all lines that can't have a pair, then I find the longest common subsequence of the remaining elements. Finally I mark the matching pairs."
 
  | lineSet lcs xFilteredLines yFilteredLines |
  lineSet := yLines asSet.
  xFilteredLines := xLines select: [ :each |
  lineSet includes: each ].
  xFilteredLines size = 0 ifTrue: [ ^self ].
  lineSet := xLines asSet.
  yFilteredLines := yLines select: [ :each |
  (lineSet includes: each) ].
  yFilteredLines size = 0 ifTrue: [ ^self ].
  lcs := self
  lcsFor: xFilteredLines
  and: yFilteredLines.
+ [ lcs == nil ] whileFalse: [
+ (xFilteredLines at: (lcs at: 1)) matches: (yFilteredLines at: (lcs at: 2)).
+ lcs := lcs at: 3 ]!
- lcs pairsDo: [ :first :second | first matches: second ]!