// removeOnly is a special flag used only by <transition-group>
  // to ensure removed elements stay in correct relative positions
  // during leaving transitions
  const canMove = !removeOnly

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
   if (isUndef(oldStartVnode)) {
    oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left
   } else if (isUndef(oldEndVnode)) {
    oldEndVnode = oldCh[--oldEndIdx]
   } else if (sameVnode(oldStartVnode, newStartVnode)) {
    patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
    oldStartVnode = oldCh[++oldStartIdx]
    newStartVnode = newCh[++newStartIdx]
   } else if (sameVnode(oldEndVnode, newEndVnode)) {
    patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
    oldEndVnode = oldCh[--oldEndIdx]
    newEndVnode = newCh[--newEndIdx]
   } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
    patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
    canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm))
    oldStartVnode = oldCh[++oldStartIdx]
    newEndVnode = newCh[--newEndIdx]
   } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
    patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
    canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm)
    oldEndVnode = oldCh[--oldEndIdx]
    newStartVnode = newCh[++newStartIdx]
   } else {
    if (isUndef(oldKeyToIdx)) oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
    idxInOld = isDef(newStartVnode.key)
     ? oldKeyToIdx[newStartVnode.key]
     : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
    if (isUndef(idxInOld)) { // New element
     createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
    } else {
     vnodeToMove = oldCh[idxInOld]
     if (sameVnode(vnodeToMove, newStartVnode)) {
      patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
      oldCh[idxInOld] = undefined
      canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
     } else {
      // same key but different element. treat as new element
      createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
     }
    }
    newStartVnode = newCh[++newStartIdx]
   }
  }

function sameVnode (a, b) {
 return (
  a.key === b.key && (
   (
    a.tag === b.tag &&
    a.isComment === b.isComment &&
    isDef(a.data) === isDef(b.data) &&
    sameInputType(a, b)
   ) || (
    isTrue(a.isAsyncPlaceholder) &&
    a.asyncFactory === b.asyncFactory &&
    isUndef(b.asyncFactory.error)
   )
  )
 )
}

// Provides transition support for list items.
// supports move transitions using the FLIP technique.

// Because the vdom's children update algorithm is "unstable" - i.e.
// it doesn't guarantee the relative positioning of removed elements,
// we force transition-group to update its children into two passes:
// in the first pass, we remove all nodes that need to be removed,
// triggering their leaving transition; in the second pass, we insert/move
// into the final desired state. This way in the second pass removed
// nodes will remain where they should be.

const props = extend({
 tag: String,
 moveClass: String
}, transitionProps)

beforeMount () {
  const update = this._update
  this._update = (vnode, hydrating) => {
   const restoreActiveInstance = setActiveInstance(this)
   // force removing pass
   this.__patch__(
    this._vnode,
    this.kept,
    false, // hydrating
    true // removeOnly (!important, avoids unnecessary moves)
   )
   this._vnode = this.kept
   restoreActiveInstance()
   update.call(this, vnode, hydrating)
  }
 }

render (h: Function) {
  const tag: string = this.tag || this.$vnode.data.tag || 'span'
  const map: Object = Object.create(null)
  const prevChildren: Array<VNode> = this.prevChildren = this.children
  const rawChildren: Array<VNode> = this.$slots.default || []
  const children: Array<VNode> = this.children = []
  const transitionData: Object = extractTransitionData(this)

  for (let i = 0; i < rawChildren.length; i++) {
   const c: VNode = rawChildren[i]
   if (c.tag) {
    if (c.key != null && String(c.key).indexOf('__vlist') !== 0) {
     children.push(c)
     map[c.key] = c
     ;(c.data || (c.data = {})).transition = transitionData
    } else if (process.env.NODE_ENV !== 'production') {
     const opts: ?VNodeComponentOptions = c.componentOptions
     const name: string = opts ? (opts.Ctor.options.name || opts.tag || '') : c.tag
     warn(`<transition-group> children must be keyed: <${name}>`)
    }
   }
  }

  if (prevChildren) {
   const kept: Array<VNode> = []
   const removed: Array<VNode> = []
   for (let i = 0; i < prevChildren.length; i++) {
    const c: VNode = prevChildren[i]
    c.data.transition = transitionData
    c.data.pos = c.elm.getBoundingClientRect()
    if (map[c.key]) {
     kept.push(c)
    } else {
     removed.push(c)
    }
   }
   this.kept = h(tag, null, kept)
   this.removed = removed
  }

  return h(tag, null, children)
 },

updated () {
  const children: Array<VNode> = this.prevChildren
  const moveClass: string = this.moveClass || ((this.name || 'v') + '-move')
  if (!children.length || !this.hasMove(children[0].elm, moveClass)) {
   return
  }

  // we divide the work into three loops to avoid mixing DOM reads and writes
  // in each iteration - which helps prevent layout thrashing.
  children.forEach(callPendingCbs)
  children.forEach(recordPosition)
  children.forEach(applyTranslation)

  // force reflow to put everything in position
  // assign to this to avoid being removed in tree-shaking
  // $flow-disable-line
  this._reflow = document.body.offsetHeight

  children.forEach((c: VNode) => {
   if (c.data.moved) {
    const el: any = c.elm
    const s: any = el.style
    addTransitionClass(el, moveClass)
    s.transform = s.WebkitTransform = s.transitionDuration = ''
    el.addEventListener(transitionEndEvent, el._moveCb = function cb (e) {
     if (e && e.target !== el) {
      return
     }
     if (!e || /transform$/.test(e.propertyName)) {
      el.removeEventListener(transitionEndEvent, cb)
      el._moveCb = null
      removeTransitionClass(el, moveClass)
     }
    })
   }
  })
 },