Method: JsonDiff.array_changes

Defined in:
lib/json-diff/diff.rb

.array_changes(pairing) ⇒ Object

Input: [[before index, after index, similarity]],

removed: [before index],
added: [after index]

Output: {removed: [before index],

pairs: [[before index, after index,
  original before index, original after index]],
added: [after index]}



253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
 
# File 'lib/json-diff/diff.rb', line 253

def self.array_changes(pairing)
  # We perform removals starting from the highest index.
  # That way, they don't offset their own.
  pairing[:removed].sort!.reverse!
  pairing[:added].sort!

  # First, map indices from before to after removals.
  removal_map = IndexMaps.new
  pairing[:removed].each { |rm| removal_map.removal(rm) }
  # And map indices from after to before additions
  # (removals, since it is reversed).
  addition_map = IndexMaps.new
  pairing[:added].reverse.each { |ad| addition_map.removal(ad) }

  moves = {}
  orig_before = {}
  orig_after = {}
  pairing[:pairs].each do |before, after|
    mapped_before = removal_map.map(before)
    mapped_after = addition_map.map(after)
    orig_before[mapped_before] = before
    orig_after[mapped_after] = after
    moves[mapped_before] = mapped_after
  end

  # Now, detect rings within the pairs.
  # The proof is, if whatever was at position i was sent to position j,
  # whatever was at position j cannot have stayed at j.
  # By induction, there is a ring.
  # Oh, and a piece of the proof is that the arrays have the same length.
  # Trivially. Right. Hey, this is not an interview!
  rings = []
  while moves.size > 0
    # i goes to j. j goes to (…). k goes to i.
    ring = []
    pair = moves.shift
    origin, target = pair
    first_origin = origin
    while target != first_origin
      ring << origin
      origin = target
      target = moves[target]
      moves.delete(origin)
    end
    ring << origin
    rings << ring
  end
  # rings is of the form [[i,j,k], …]

  # Finally, we can register the moves.
  # The idea is, if the whole ring moves instantaneously,
  # no element outside of the ring changed position.
  pairs = []
  rings.each do |ring|
    orig_ring = ring.map { |i| [orig_before[i], orig_after[i]] }
    ring_map = IndexMaps.new
    len = ring.size
    i = 0
    while i < len
      ni = (i + 1) % len  # next i
      if ring[i] != ring[ni]
        pairs << [ring_map.map(ring[i]), ring[ni], orig_ring[i][0], orig_ring[ni][1]]
      end
      ring_map.removal(ring[i])
      ring_map.addition(ring[ni])
      i += 1
    end
  end

  pairing[:pairs] = pairs

  pairing
end