const newVnode = {
  type: 'div',
  children: [
    { type: 'p', children: '1' },
    { type: 'p', children: '2' },
    { type: 'p', children: '3' },
  ]
}

const oldVnode = {
  type: 'div',
  children: [
    { type: 'p', children: '4' },
    { type: 'p', children: '5' },
    { type: 'p', children: '6' }
  ]
}

const newVnode = {
  type: 'div',
  children: [
    { type: 'p', children: '1' },
    { type: 'p', children: '2' },
    { type: 'p', children: '3' },
  ]
}

const oldVnode = {
  type: 'div',
  children: [
    { type: 'p', children: '3' },
    { type: 'p', children: '2' },
    { type: 'p', children: '1' }
  ]
}

const newVnode = {
  type: 'div',
  children: [
    { type: 'p', children: '1', key:1 },
    { type: 'p', children: '2', key:2  },
    { type: 'p', children: '3', key:3  },
  ]
}

const oldVnode = {
  type: 'div',
  children: [
    { type: 'p', children: '3', key:3 },
    { type: 'p', children: '2', key:2  },
    { type: 'p', children: '1', key:1  },
  ]
}

function patchChildren(n1, n2, container) {
    if (typeof n2.children === 'string') {
     //省略代碼
    } else if (Array.isArray(n2.children)) {
      //新子節(jié)點(diǎn)是一組節(jié)點(diǎn)
      if (Array.isArray(n1.children)) {
        //舊子節(jié)點(diǎn)也是一組節(jié)點(diǎn)，應(yīng)用diff算法處理
        //省略diff算法代碼
        //diff中會(huì)使用patch去更新可復(fù)用元素
      } else if (typeof n1.children === 'string') {
       //省略代碼
      }
    }
  }

  function patchKeyedChildren(n1, n2, container) {
    const oldChildren = n1.children
    const newChildren = n2.children
    
    //處理前置節(jié)點(diǎn)
    let j = 0
    let oldVNode = oldChildren[j]
    let newVNode = newChildren[j]
    
    while (oldVNode.key === newVNode.key) {
        patch(oldVNode, newVNode, container) 
        j++ 
        oldVNode = oldChildren[j] 
        newVNode = newChildren[j]
    }
    
    //處理后置節(jié)點(diǎn)
    //將新舊節(jié)點(diǎn)的索引指向最后一個(gè)子節(jié)點(diǎn)
    let oldEnd = oldChildren.length - 1 
    let newEnd = newChildren.length - 1
    
    oldVNode = oldChildren[oldEnd] 
    newVNode = newChildren[newEnd]
    
    while (oldVNode.key === newVNode.key) {
        patch(oldVNode, newVNode, container) 
        oldEnd-- 
        newEnd--
        oldVNode = oldChildren[oldEnd] 
        newVNode = newChildren[newEnd]
    }
       
  }

function patch(n1, n2, container, anchor) {
   //...省略代碼
  if (typeof type === 'string') {
    if (!n1) {
        //在此處傳入錨點(diǎn)以支持新節(jié)點(diǎn)按位置插入
      mountElement(n2, container, anchor)
    } else {
      patchElement(n1, n2)
    }
  } else if (type === Text) {
    //...省略代碼
}

function mountElement(vnode, container, anchor) {
    //省略代碼
    //給insert方法傳遞錨點(diǎn)元素
    insert(el, container, anchor)
}

const renderer = createRenderer({
    //...省略代碼
    insert(el, parent, anchor = null) {
        //根據(jù)錨點(diǎn)元素插入節(jié)點(diǎn)
        parent.insertBefore(el, anchor)
    }
})

function patchKeyedChildren(n1, n2, container) {
    const oldChildren = n1.children
    const newChildren = n2.children
    
    //需要插入新節(jié)點(diǎn)
    if (j > oldEnd && j <= newEnd){
         //取得錨點(diǎn)索引
         const anchorIndex = newEnd + 1
         //取得錨點(diǎn)元素
         const anchor = anchorIndex < newChildren.length ? newChildren[anchorIndex].el : null
         //調(diào)用patch掛載新節(jié)點(diǎn)
         while (j <= newEnd) { 
             patch(null, newChildren[j++], container, anchor) 
         }
    }
       
  }

function patchKeyedChildren(n1, n2, container) {
    const oldChildren = n1.children
    const newChildren = n2.children
    
    //需要插入新節(jié)點(diǎn)
    if (j > oldEnd && j <= newEnd){
        //...省略新增節(jié)點(diǎn)邏輯
         
    }else if (j > newEnd && j <= oldEnd) { 
       //卸載節(jié)點(diǎn)
        while (j <= oldEnd) { 
            unmount(oldChildren[j++]) 
        } 
    }
       
  }

function patchKeyedChildren(n1, n2, container) {
    const oldChildren = n1.children
    const newChildren = n2.children
    
    //需要插入新節(jié)點(diǎn)
    if (j > oldEnd && j <= newEnd){
        //...省略新增節(jié)點(diǎn)邏輯
         
    }else if (j > newEnd && j <= oldEnd) { 
       //卸載節(jié)點(diǎn)
        while (j <= oldEnd) { 
            unmount(oldChildren[j++]) 
        } 
        //預(yù)處理完畢后
    } else{
        //初始化source數(shù)組
        const count = newEnd - j + 1
        const source = new Array(count)
        source.fill(-1)
    }
       
  }

for (let i = oldStart; i <= oldEnd; i++) { 
    const oldVNode = oldChildren[i] 
    // 遍歷新的一組子節(jié)點(diǎn) 
    for (let k = newStart; k <= newEnd; k++) { 
        const newVNode = newChildren[k] 
        // 找到擁有相同 key 值的可復(fù)用節(jié)點(diǎn) 
        if (oldVNode.key === newVNode.key) { 
            // 調(diào)用 patch 進(jìn)行更新 
            patch(oldVNode, newVNode, container) 
            // 最后填充 source 數(shù)組 
            source[k - newStart] = i 
        } 
    } 
}

const oldStart = j
const newStart = j
const keyIndex = {}
for(let i = newStart; i <= newEnd; i++) {
    keyIndex[newChildren[i].key] = i
}
for(let i = oldStart; i <= oldEnd; i++) {
  oldVNode = oldChildren[i]
  const k = keyIndex[oldVNode.key]
  if (typeof k !== 'undefined') {
    newVNode = newChildren[k]
    patch(oldVNode, newVNode, container)
    source[k - newStart] = i
  } else {
    unmount(oldVNode)
  }
}

const count = newEnd - j + 1  // 新的一組子節(jié)點(diǎn)中剩余未處理節(jié)點(diǎn)的數(shù)量
const source = new Array(count)
source.fill(-1)

const oldStart = j
const newStart = j
let moved = false
let pos = 0
const keyIndex = {}
for(let i = newStart; i <= newEnd; i++) {
    keyIndex[newChildren[i].key] = i
}
let patched = 0
for(let i = oldStart; i <= oldEnd; i++) {
    oldVNode = oldChildren[i]
    if (patched < count) {
      const k = keyIndex[oldVNode.key]
      if (typeof k !== 'undefined') {
        newVNode = newChildren[k]
        patch(oldVNode, newVNode, container)
        patched++
        source[k - newStart] = i
        // 判斷是否需要移動(dòng)
        if (k < pos) {
          moved = true
        } else {
          pos = k
        }
      } else {
        // 沒找到
        unmount(oldVNode)
      }
    } else {
      unmount(oldVNode)
    }
}

const seq = lis(source)

function patchKeyedChildren(n1, n2, container) {
  //省略預(yù)處理和構(gòu)造source數(shù)組代碼
  if (moved) {
    const seq = lis(source)
    // s 指向最長(zhǎng)遞增子序列的最后一個(gè)值
    let s = seq.length - 1
    let i = count - 1
    for (i; i >= 0; i--) {
      if (source[i] === -1) {
        // 說(shuō)明索引為 i 的節(jié)點(diǎn)是全新的節(jié)點(diǎn)，應(yīng)該將其掛載
       
      } else if (i !== seq[j]) {
      
        // 說(shuō)明該節(jié)點(diǎn)需要移動(dòng)
      } else {
        // 當(dāng) i === seq[j] 時(shí)，說(shuō)明該位置的節(jié)點(diǎn)不需要移動(dòng)
        // 并讓 s 指向下一個(gè)位置
        s--
      }
    }
  }
}
}

if (source[i] === -1) {
    // 該節(jié)點(diǎn)在新的一組子節(jié)點(diǎn)中的真實(shí)位置索引
    const pos = i + newStart
    const newVNode = newChildren[pos]
    // 該節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)的位置索引
    const nextPos = pos + 1
    // 錨點(diǎn)
    const anchor = nextPos < newChildren.length
      ? newChildren[nextPos].el
      : null
    patch(null, newVNode, container, anchor)
}

if (i !== seq[s]) {
    // 該節(jié)點(diǎn)在新的一組子節(jié)點(diǎn)中的真實(shí)位置索引
    const pos = i + newStart
    const newVNode = newChildren[pos]
    // 該節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)的位置索引
    const nextPos = pos + 1
    // 錨點(diǎn)
    const anchor = nextPos < newChildren.length
      ? newChildren[nextPos].el
      : null
    patch(null, newVNode, container, anchor)
}

  s--

  if (moved) {
    const seq = lis(source)
    // s 指向最長(zhǎng)遞增子序列的最后一個(gè)值
    let s = seq.length - 1
    let i = count - 1
    for (i; i >= 0; i--) {
      if (source[i] === -1) {
        // 說(shuō)明索引為 i 的節(jié)點(diǎn)是全新的節(jié)點(diǎn)，應(yīng)該將其掛載
        // 該節(jié)點(diǎn)在新 children 中的真實(shí)位置索引
        const pos = i + newStart
        const newVNode = newChildren[pos]
        // 該節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)的位置索引
        const nextPos = pos + 1
        // 錨點(diǎn)
        const anchor = nextPos < newChildren.length
          ? newChildren[nextPos].el
          : null
        // 掛載
        patch(null, newVNode, container, anchor)
      } else if (i !== seq[j]) {
        // 說(shuō)明該節(jié)點(diǎn)需要移動(dòng)
        // 該節(jié)點(diǎn)在新的一組子節(jié)點(diǎn)中的真實(shí)位置索引
        const pos = i + newStart
        const newVNode = newChildren[pos]
        // 該節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)的位置索引
        const nextPos = pos + 1
        // 錨點(diǎn)
        const anchor = nextPos < newChildren.length
          ? newChildren[nextPos].el
          : null
        // 移動(dòng)
        insert(newVNode.el, container, anchor)
      } else {
        // 當(dāng) i === seq[j] 時(shí)，說(shuō)明該位置的節(jié)點(diǎn)不需要移動(dòng)
        // 并讓 s 指向下一個(gè)位置
        s--
      }
    }
  }
}