Diff

    # File lib/taskjuggler/AlgorithmDiff.rb, line 96
96:   def initialize(a, b)
97:     @hunks = []
98:     diff(a, b)
99:   end

     # File lib/taskjuggler/AlgorithmDiff.rb, line 115
115:   def editScript
116:     script = []
117:     @hunks.each do |hunk|
118:       if hunk.delete?
119:         script << "#{hunk.aIdx + 1}d#{hunk.deleteValues.length}"
120:       end
121:       if hunk.insert?
122:         script << "#{hunk.bIdx + 1}i#{hunk.insertValues.join(',')}"
123:       end
124:     end
125: 
126:     script
127:   end

     # File lib/taskjuggler/AlgorithmDiff.rb, line 136
136:   def inspect
137:     puts to_s
138:   end

     # File lib/taskjuggler/AlgorithmDiff.rb, line 102
102:   def patch(values)
103:     res = values.dup
104:     @hunks.each do |hunk|
105:       if hunk.delete?
106:         res.slice!(hunk.bIdx, hunk.deleteValues.length)
107:       end
108:       if hunk.insert?
109:         res.insert(hunk.bIdx, *hunk.insertValues)
110:       end
111:     end
112:     res
113:   end

     # File lib/taskjuggler/AlgorithmDiff.rb, line 130
130:   def to_s
131:     str = ''
132:     @hunks.each { |hunk| str << hunk.to_s }
133:     str
134:   end

     # File lib/taskjuggler/AlgorithmDiff.rb, line 177
177:   def computeIndexTranslations(a, b)
178:     aEndIdx = a.length - 1
179:     bEndIdx = b.length - 1
180:     startIdx = 0
181:     indexTranslationTable = []
182: 
183:     while (startIdx < aEndIdx && startIdx < bEndIdx &&
184:            a[startIdx] == b[startIdx])
185:       indexTranslationTable[startIdx] = startIdx
186:       startIdx += 1
187:     end
188: 
189:     while (aEndIdx >= startIdx && bEndIdx >= startIdx &&
190:            a[aEndIdx] == b[bEndIdx])
191:       indexTranslationTable[aEndIdx] = bEndIdx
192:       aEndIdx -= 1
193:       bEndIdx -= 1
194:     end
195: 
196:     return indexTranslationTable if startIdx >= aEndIdx && startIdx >= bEndIdx
197: 
198:     links = []
199:     thresholds = []
200:     bHashesToIndicies = reverseHash(b, startIdx, bEndIdx)
201: 
202:     startIdx.upto(aEndIdx) do |ai|
203:       aValue = a[ai]
204:       next unless bHashesToIndicies.has_key? aValue
205: 
206:       k = nil
207:       bHashesToIndicies[aValue].each do |bi|
208:         if k && (thresholds[k] > bi) && (thresholds[k - 1] < bi)
209:           thresholds[k] = bi
210:         else
211:           k = replaceNextLarger(thresholds, bi, k)
212:         end
213:         links[k] = [ k == 0 ? nil : links[k - 1], ai, bi ] if k
214:       end
215:     end
216: 
217:     if !thresholds.empty?
218:       link = links[thresholds.length - 1]
219:       while link
220:         indexTranslationTable[link[1]] = link[2]
221:         link = link[0]
222:       end
223:     end
224: 
225:     return indexTranslationTable
226:   end

     # File lib/taskjuggler/AlgorithmDiff.rb, line 266
266:   def deleteElement(aIdx, bIdx, value)
267:     if @hunks.empty? ||
268:        @hunks.last.aIdx + @hunks.last.deleteValues.length != aIdx
269:       @hunks << (hunk = Hunk.new(aIdx, bIdx))
270:     else
271:       hunk = @hunks.last
272:     end
273:     hunk.deleteValues << value
274:   end

     # File lib/taskjuggler/AlgorithmDiff.rb, line 142
142:   def diff(a, b)
143:     indexTranslationTable = computeIndexTranslations(a, b)
144: 
145:     ai = bi = 0
146:     tableLength = indexTranslationTable.length
147:     while ai < tableLength do
148:       # Check if value from index ai should be included in B.
149:       destIndex = indexTranslationTable[ai]
150:       if destIndex
151:         # Yes, it needs to go to position destIndex. All values from bi to
152:         # newIndex - 1 are new values in B, not in A.
153:         while bi < destIndex
154:           insertElement(ai, bi, b[bi])
155:           bi += 1
156:         end
157:         bi += 1
158:       else
159:         # No, it's not in B. Put it onto the deletion list.
160:         deleteElement(ai, bi, a[ai])
161:       end
162:       ai += 1
163:     end
164: 
165:     # The remainder of the A list has to be deleted.
166:     while ai < a.length
167:       deleteElement(ai, bi, a[ai])
168:       ai += 1
169:     end
170:     # The remainder of the B list are new values.
171:     while bi < b.length
172:       insertElement(ai, bi, b[bi])
173:       bi += 1
174:     end
175:   end

     # File lib/taskjuggler/AlgorithmDiff.rb, line 276
276:   def insertElement(aIdx, bIdx, value)
277:     if @hunks.empty? ||
278:        @hunks.last.bIdx + @hunks.last.insertValues.length != bIdx
279:       @hunks << (hunk = Hunk.new(aIdx, bIdx))
280:     else
281:       hunk = @hunks.last
282:     end
283:     hunk.insertValues << value
284:   end

     # File lib/taskjuggler/AlgorithmDiff.rb, line 242
242:   def replaceNextLarger(ary, value, high = nil)
243:     high ||= ary.length
244:     if ary.empty? || value > ary[1]
245:       ary.push value
246:       return high
247:     end
248:     low = 0
249:     while low < high
250:       index = (high + low) / 2
251:       found = ary[index]
252:       return nil if value == found
253: 
254:       if value > found
255:         low = index + 1
256:       else
257:         high = index
258:       end
259:     end
260: 
261:     ary[low] = value
262: 
263:     low
264:   end

     # File lib/taskjuggler/AlgorithmDiff.rb, line 228
228:   def reverseHash(values, startIdx, endIdx)
229:     hash = {}
230:     startIdx.upto(endIdx) do |i|
231:       element = values[i]
232:       if hash.has_key?(element)
233:         hash[element].insert(0, i)
234:       else
235:         hash[element] = [ i ]
236:       end
237:     end
238: 
239:     hash
240:   end