// 没有 Diff：直接替换整个 DOM
oldDOM.parentNode.replaceChild(newDOM, oldDOM)
// 问题：性能极差，会丢失状态（输入框内容、滚动位置等）

// 有 Diff：精确找出差异，最小化 DOM 操作
patch(oldVNode, newVNode)
// 优势：性能好，保留状态，用户体验好

// 只比较同一层级的节点，不跨层级比较
// 旧树              新树
  div                div
  / \                / \
 p   span    →      p   div
                         |
                        span

// Vue 的处理：
// 1. 比较根节点 div（相同，复用）
// 2. 比较第二层：p 和 span → p 和 div
//    - p 相同，复用
//    - span ≠ div，删除 span，创建 div
// 3. 比较第三层：无 → span
//    - 创建 span

// 不会识别出 span 只是移动了位置
// 但这种情况在实际开发中极少出现

function sameVnode(a, b) {
  return (
    a.key === b.key &&  // key 相同
    a.tag === b.tag &&  // 标签名相同
    a.isComment === b.isComment &&  // 都是注释节点
    isDef(a.data) === isDef(b.data) &&  // 都有 data
    sameInputType(a, b)  // input 类型相同
  )
}

// 示例
// 相同节点（可复用）
<div key="1">A</div>  →  <div key="1">B</div>  // ✓ 复用

// 不同节点（不可复用）
<div key="1">A</div>  →  <div key="2">A</div>  // ✗ key 不同
<div>A</div>          →  <span>A</span>        // ✗ tag 不同

// 没有 key（使用 index）
<div v-for="(item, index) in list" :key="index">
  {{ item.name }}
</div>

// 问题：插入/删除元素时，后面所有元素的 key 都会变化
// 旧：[A(0), B(1), C(2)]
// 新：[X(0), A(1), B(2), C(3)]  // 在开头插入 X
// Diff 认为：0、1、2 位置的节点都变了，全部更新

// 有唯一 key
<div v-for="item in list" :key="item.id">
  {{ item.name }}
</div>

// 旧：[A(id:1), B(id:2), C(id:3)]
// 新：[X(id:4), A(id:1), B(id:2), C(id:3)]
// Diff 认为：只是在开头插入了一个新节点，其他节点复用

// 旧子节点：[A, B, C, D]
// 新子节点：[B, C, D, E]

oldStartIdx = 0  // 指向 A
oldEndIdx = 3    // 指向 D
newStartIdx = 0  // 指向 B
newEndIdx = 3    // 指向 E

function updateChildren(parentElm, oldCh, newCh) {
  let oldStartIdx = 0
  let oldEndIdx = oldCh.length - 1
  let oldStartVnode = oldCh[0]
  let oldEndVnode = oldCh[oldEndIdx]
  
  let newStartIdx = 0
  let newEndIdx = newCh.length - 1
  let newStartVnode = newCh[0]
  let newEndVnode = newCh[newEndIdx]
  
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (isUndef(oldStartVnode)) {
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (isUndef(oldEndVnode)) {
      oldEndVnode = oldCh[--oldEndIdx]
    }
    // 1. 头头比较
    else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    }
    // 2. 尾尾比较
    else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    }
    // 3. 头尾比较
    else if (sameVnode(oldStartVnode, newEndVnode)) {
      patchVnode(oldStartVnode, newEndVnode)
      nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    }
    // 4. 尾头比较
    else if (sameVnode(oldEndVnode, newStartVnode)) {
      patchVnode(oldEndVnode, newStartVnode)
      nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    }
    // 5. 都没匹配，查找 key
    else {
      // 创建旧节点 key -> index 的映射
      if (isUndef(oldKeyToIdx)) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
      }
      // 在旧节点中查找新节点
      idxInOld = isDef(newStartVnode.key)
        ? oldKeyToIdx[newStartVnode.key]
        : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
      
      if (isUndef(idxInOld)) {
        // 没找到，创建新节点
        createElm(newStartVnode, parentElm, oldStartVnode.elm)
      } else {
        // 找到了，移动节点
        vnodeToMove = oldCh[idxInOld]
        if (sameVnode(vnodeToMove, newStartVnode)) {
          patchVnode(vnodeToMove, newStartVnode)
          oldCh[idxInOld] = undefined
          nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
        } else {
          // key 相同但节点不同，创建新节点
          createElm(newStartVnode, parentElm, oldStartVnode.elm)
        }
      }
      newStartVnode = newCh[++newStartIdx]
    }
  }
  
  // 处理剩余节点
  if (oldStartIdx > oldEndIdx) {
    // 旧节点遍历完，新节点还有剩余，批量添加
    addVnodes(parentElm, newCh, newStartIdx, newEndIdx)
  } else if (newStartIdx > newEndIdx) {
    // 新节点遍历完，旧节点还有剩余，批量删除
    removeVnodes(oldCh, oldStartIdx, oldEndIdx)
  }
}

// 旧：[A, B, C, D]
// 新：[D, A, B, C]

// 第 1 轮：
// 头头：A ≠ D  ✗
// 尾尾：D = D  ✓  → patch D，双方尾指针前移
// 旧：[A, B, C, D]  oldEnd--
//      ↑     ↑
// 新：[D, A, B, C]  newEnd--
//      ↑     ↑

// 第 2 轮：
// 头头：A ≠ C  ✗
// 尾尾：C = C  ✓  → patch C，双方尾指针前移
// 旧：[A, B, C]  oldEnd--
//      ↑  ↑
// 新：[D, A, B]  newEnd--
//      ↑  ↑

// 第 3 轮：
// 头头：A ≠ B  ✗
// 尾尾：B = B  ✓  → patch B，双方尾指针前移
// 旧：[A, B]  oldEnd--
//      ↑↑
// 新：[D, A]  newEnd--
//      ↑↑

// 第 4 轮：
// 头头：A = A  ✓  → patch A，双方头指针后移
// 旧：[A]  oldStart++
//      ↑
// 新：[D]  newStart++
//      ↑

// 结束：oldStartIdx > oldEndIdx
// 新节点还有剩余：D
// 在开头插入 D

// 旧：[A, B, C, D, E]
// 新：[A, B, F, G, E]

let i = 0
const l2 = newChildren.length
let e1 = oldChildren.length - 1  // 旧节点的结束索引
let e2 = l2 - 1                   // 新节点的结束索引

// 从前往后比较
while (i <= e1 && i <= e2) {
  const n1 = oldChildren[i]
  const n2 = newChildren[i]
  if (sameVnode(n1, n2)) {
    patch(n1, n2)
    i++
  } else {
    break
  }
}

// 结果：
// i = 2（A、B 已处理）
// 旧：[A, B, C, D, E]
//          ↑
// 新：[A, B, F, G, E]
//          ↑

// 从后往前比较
while (i <= e1 && i <= e2) {
  const n1 = oldChildren[e1]
  const n2 = newChildren[e2]
  if (sameVnode(n1, n2)) {
    patch(n1, n2)
    e1--
    e2--
  } else {
    break
  }
}

// 结果：
// e1 = 3, e2 = 3（E 已处理）
// 旧：[A, B, C, D, E]
//          ↑  ↑
// 新：[A, B, F, G, E]
//          ↑  ↑

if (i > e1) {
  if (i <= e2) {
    // 批量新增
    while (i <= e2) {
      patch(null, newChildren[i], container, anchor)
      i++
    }
  }
}

// 示例：
// 旧：[A, B, C]
// 新：[A, B, D, E, C]
// 处理前后置后：i=2, e1=1, e2=3
// i > e1，新增 D、E

else if (i > e2) {
  while (i <= e1) {
    unmount(oldChildren[i])
    i++
  }
}

// 示例：
// 旧：[A, B, C, D, E]
// 新：[A, B, E]
// 处理前后置后：i=2, e1=3, e2=1
// i > e2，删除 C、D

// 旧：[A, B, C, D, E, F, G]
// 新：[A, B, E, C, D, H, F, G]
// 处理前后置后：
// i = 2, e1 = 4, e2 = 5
// 中间部分：
// 旧：[C, D, E]
// 新：[E, C, D, H]

// 步骤 1：建立新节点的 key -> index 映射
const keyToNewIndexMap = new Map()
for (let i = s2; i <= e2; i++) {
  keyToNewIndexMap.set(newChildren[i].key, i)
}
// { E: 2, C: 3, D: 4, H: 5 }

// 步骤 2：遍历旧节点，标记可复用的节点
const newIndexToOldIndexMap = new Array(e2 - s2 + 1).fill(0)
// [0, 0, 0, 0]  // 0 表示新节点，非 0 表示可复用

let moved = false
let maxNewIndexSoFar = 0

for (let i = s1; i <= e1; i++) {
  const prevChild = oldChildren[i]
  const newIndex = keyToNewIndexMap.get(prevChild.key)
  
  if (newIndex === undefined) {
    // 旧节点在新节点中不存在，删除
    unmount(prevChild)
  } else {
    // 记录旧节点在新节点中的位置
    newIndexToOldIndexMap[newIndex - s2] = i + 1
    
    // 判断是否需要移动
    if (newIndex >= maxNewIndexSoFar) {
      maxNewIndexSoFar = newIndex
    } else {
      moved = true
    }
    
    patch(prevChild, newChildren[newIndex])
  }
}

// newIndexToOldIndexMap = [5, 3, 4, 0]
// 含义：
// - 新节点 E（索引 2）对应旧节点索引 4（5-1）
// - 新节点 C（索引 3）对应旧节点索引 2（3-1）
// - 新节点 D（索引 4）对应旧节点索引 3（4-1）
// - 新节点 H（索引 5）是新增的（0）

// 步骤 3：计算最长递增子序列
const increasingNewIndexSequence = moved
  ? getSequence(newIndexToOldIndexMap)
  : []
// [1, 2]  // 表示索引 1 和 2 的节点不需要移动
// 对应新节点 C 和 D

// 步骤 4：移动和挂载节点
let j = increasingNewIndexSequence.length - 1

for (let i = e2 - s2; i >= 0; i--) {
  const nextIndex = s2 + i
  const nextChild = newChildren[nextIndex]
  const anchor = nextIndex + 1 < l2 ? newChildren[nextIndex + 1].el : null
  
  if (newIndexToOldIndexMap[i] === 0) {
    // 新节点，挂载
    patch(null, nextChild, container, anchor)
  } else if (moved) {
    if (j < 0 || i !== increasingNewIndexSequence[j]) {
      // 需要移动
      move(nextChild, container, anchor)
    } else {
      // 不需要移动
      j--
    }
  }
}

function getSequence(arr) {
  const p = arr.slice()  // 用于记录前驱节点
  const result = [0]     // 存储最长递增子序列的索引
  let i, j, u, v, c
  const len = arr.length
  
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    if (arrI !== 0) {
      j = result[result.length - 1]
      if (arr[j] < arrI) {
        p[i] = j
        result.push(i)
        continue
      }
      
      // 二分查找
      u = 0
      v = result.length - 1
      while (u < v) {
        c = (u + v) >> 1
        if (arr[result[c]] < arrI) {
          u = c + 1
        } else {
          v = c
        }
      }
      
      if (arrI < arr[result[u]]) {
        if (u > 0) {
          p[i] = result[u - 1]
        }
        result[u] = i
      }
    }
  }
  
  u = result.length
  v = result[u - 1]
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  
  return result
}

// 示例：
getSequence([5, 3, 4, 0])  // [1, 2]
// 含义：索引 1 和 2 的元素（3 和 4）构成最长递增子序列

// 场景：列表反转
// 旧：[A, B, C, D, E]
// 新：[E, D, C, B, A]

// Vue 2（双端比较）：
// - 需要多次比较和移动
// - 时间复杂度：O(n)
// - 移动次数：较多

// Vue 3（快速 Diff + LIS）：
// - 计算出最长递增子序列
// - 只移动不在序列中的节点
// - 时间复杂度：O(n log n)（LIS 算法）
// - 移动次数：最少

// 没有 key（使用 index）
// 旧：[A(0), B(1), C(2)]
// 新：[D(0), A(1), B(2), C(3)]  // 在开头插入 D

// Diff 认为：
// - 0 位置：A → D（更新）
// - 1 位置：B → A（更新）
// - 2 位置：C → B（更新）
// - 3 位置：无 → C（新增）
// 结果：4 次操作

// 有唯一 key
// 旧：[A(a), B(b), C(c)]
// 新：[D(d), A(a), B(b), C(c)]

// Diff 认为：
// - D 是新节点（新增）
// - A、B、C 都可以复用（移动）
// 结果：1 次操作

// 为什么要加 key：
1. 提高 Diff 效率：精确找到可复用的节点
2. 避免就地更新：防止状态错乱（input 输入值）
3. 减少 DOM 操作：最大化节点复用

// 场景：列表中有输入框
<div v-for="(item, index) in list" :key="index">
  <input v-model="item.value">
  {{ item.name }}
</div>

// 初始状态：
// [{ name: 'A', value: '1' }, { name: 'B', value: '2' }]
// 用户在 A 的输入框输入了 'test'

// 在开头插入新元素：
// [{ name: 'C', value: '' }, { name: 'A', value: '1' }, { name: 'B', value: '2' }]

// 使用 index 作为 key：
// 旧：A(0), B(1)
// 新：C(0), A(1), B(2)

// Diff 认为：
// - 0 位置：A → C（复用 DOM，但内容变了）
// - 1 位置：B → A（复用 DOM，但内容变了）
// - 2 位置：新增 B

// 问题：
// - C 的输入框会显示 'test'（原本是 A 的输入值）
// - 状态错乱

// 使用唯一 id 作为 key：
// 旧：A(id:1), B(id:2)
// 新：C(id:3), A(id:1), B(id:2)

// Diff 认为：
// - C 是新节点（创建新 DOM）
// - A、B 可以复用（保持原有状态）

// 结果：状态正确

// 不可以！

// 使用随机数
<div v-for="item in list" :key="Math.random()">
  {{ item.name }}
</div>

// 问题：
// 1. 每次渲染 key 都会变化
// 2. Diff 认为所有节点都是新节点
// 3. 无法复用任何 DOM
// 4. 性能极差，相当于没有 Diff

// 正确做法：
// 使用稳定且唯一的标识符
<div v-for="item in list" :key="item.id">
  {{ item.name }}
</div>

// 1. 静态列表（不会增删改）
<div v-for="item in staticList">
  {{ item.name }}
</div>

// 2. 列表项没有状态（纯展示）
<div v-for="item in list">
  <span>{{ item.name }}</span>
</div>

// 3. 列表项不会重排序
<div v-for="item in list">
  {{ item.name }}
</div>

// 但是：
// 为了代码的可维护性和避免潜在问题
// 建议始终使用唯一的 key

// ✓ 推荐：使用唯一 id
<div v-for="item in list" :key="item.id">
  {{ item.name }}
</div>

// ✗ 不推荐：使用 index
<div v-for="(item, index) in list" :key="index">
  {{ item.name }}
</div>

// ✗ 不推荐：使用随机数
<div v-for="item in list" :key="Math.random()">
  {{ item.name }}
</div>

// ✗ 不推荐：使用对象（会转为字符串 [object Object]）
<div v-for="item in list" :key="item">
  {{ item.name }}
</div>

// 1. 使用 v-show 代替 v-if（频繁切换）
<div v-for="item in list" :key="item.id" v-show="item.visible">
  {{ item.name }}
</div>

// 2. 使用计算属性过滤列表
computed: {
  filteredList() {
    return this.list.filter(item => item.visible)
  }
}
<div v-for="item in filteredList" :key="item.id">
  {{ item.name }}
</div>

// 3. 使用虚拟滚动（长列表）
<virtual-list :items="list" :item-height="50">
  <template #default="{ item }">
    <div>{{ item.name }}</div>
  </template>
</virtual-list>

// 1. 使用 v-once（只渲染一次）
<div v-once>
  <h1>{{ title }}</h1>
  <p>这些内容不会更新</p>
</div>

// 2. 使用 v-memo（Vue 3.2+）
<div v-memo="[value1, value2]">
  <!-- 只有 value1 或 value2 变化时才重新渲染 -->
</div>

// 3. 使用 Object.freeze（冻结数据）
data() {
  return {
    list: Object.freeze([
      { id: 1, name: 'A' },
      { id: 2, name: 'B' }
    ])
  }
}