Android学习笔记07-Android列表中的DiffUtils

function myers(stra, strb) {
  let n = stra.length
  let m = strb.length

  //记录的是在k线上 能够走动的最优最表的X值，也能通过该集合推导出，每个最有坐标的x,y,k的值
  let v = {
    '1': 0
  }
  //记录的是每走一步，走过的（x,y)坐标的集合
  let vs = {
    '0': { '1': 0 }
  }
  let d

  loop:
  for (d = 0; d <= n + m; d++) {
    let tmp = {}

    for (let k = -d; k <= d; k += 2) {
      //判断是向右走 还是向下走
      let down = k == -d || k != d && v[k + 1] > v[k - 1]
      //取出上一步对应的k线
      let kPrev = down ? k + 1 : k - 1

      //取出上一步对应的k线走到的最大值X值
      let xStart = v[kPrev]
      //取出上一步对应的k线走到的最大值Y值
      let yStart = xStart - kPrev

      //计算出当前k线的x,y的值
      let xMid = down ? xStart : xStart + 1
      let yMid = xMid - k

      let xEnd = xMid
      let yEnd = yMid

      //如果当前步数对应的k线下有坐标(xEnd,yEnd)使得两个集合的值相等，说明可以向对角线，那么x,y各加1.
      while(xEnd < n && yEnd < m && stra[xEnd] === strb[yEnd]) {
        xEnd++
        yEnd++
      }
      //把当前步数线当前k线的最大值更新
      v[k] = xEnd
      tmp[k] = xEnd

      if (xEnd == n && yEnd == m) {
        vs[d] = tmp
        let snakes = solution(vs, n, m, d)
        printRes(snakes, stra, strb)

        break loop
      }
    }

    vs[d] = tmp
  }
}

function solution(vs, n, m, d) {
  let snakes = []
  let p = { x: n, y: m }
  
  //倒推开始
  for (; d > 0; d--) {
    //取出步数为d时所走过的x,y的坐标集合
    let v = vs[d]
    //取出步数为d-1时所走过的x,y的坐标集合
    let vPrev = vs[d-1]
    //计算出当前k线值
    let k = p.x - p.y

    //取出当前步数下 斜线为k时 x的最大坐标
    let xEnd = v[k]
    //计算出取出当前步数下 斜线为k时 y的值
    let yEnd = xEnd - k
    //计算当前步，当前k线下 它是从上一步 向右还是向下过来的
    let down = k == -d || k != d && vPrev[k + 1] > vPrev[k - 1]
    //那么就知道了上一步的k线值
    let kPrev = down ? k + 1 : k - 1
    
    //取出当前步数下开始x值
    let xStart = vPrev[kPrev]
    let yStart = xStart - kPrev
    
    //计算出当前步数下的中间x值
    let xMid = down ? xStart : xStart + 1
    let yMid = xMid - k
    
    //收集每一步走的线的 开始，中间，终点的X值
    snakes.unshift([xStart, xMid, xEnd])

    p.x = xStart
    p.y = yStart
  }

  return snakes
}

function printRes(snakes, stra, strb) {
  let grayColor = 'color: gray'
  let redColor = 'color: red'
  let greenColor = 'color: green'
  let consoleStr = ''
  let args = []
  let yOffset = 0
  
  snakes.forEach((snake, index) => {
    let s = snake[0]
    let m = snake[1]
    let e = snake[2]
    let large = s
    
    if (index === 0 && s !== 0) {
      for (let j = 0; j < s; j++) {
        consoleStr += `%c${stra[j]}`
        args.push(grayColor)
        yOffset++
      }
    }
    
    // 删除
    if (m - s == 1) {
      consoleStr += `%c${stra[s]}`
      args.push(redColor)
      large = m
    // 添加
    } else {
      consoleStr += `%c${strb[yOffset]}`
      args.push(greenColor)
      yOffset++
    }
    
    // 不变
    for (let i = 0; i < e - large; i++) {
      consoleStr += `%c${stra[large+i]}`
      args.push(grayColor)
      yOffset++
    }
  })

  console.log(consoleStr, ...args)
}

let s1 = 'ABCABBA'
let s2 = 'CBABAC'
myers(s1, s2)