import { createStore, applyMiddleware } from 'redux'
  import thunk from 'redux-thunk'

  const middleware = [ thunk ];
  const store = createStore(
    reducer,
    applyMiddleware(...middleware)
  )

  const state = store.getState();

  store.dispatch({
    type: 'ADD_TODO',
    payload: 'Learn Redux'
  })

// src/index.js
export default {
  Store,
  install,
  version: '__VERSION__',
  mapState,
  mapMutations,
  mapGetters,
  mapActions,
  createNamespacedHelpers
}

// src/mixin.js 导出作为install方法
export default function (Vue) {
  const version = Number(Vue.version.split('.')[0])

  if (version >= 2) {
    Vue.mixin({ beforeCreate: vuexInit })
  } else {
    // override init and inject vuex init procedure
    // for 1.x backwards compatibility.
    const _init = Vue.prototype._init
    Vue.prototype._init = function (options = {}) {
      options.init = options.init
        ? [vuexInit].concat(options.init)
        : vuexInit
      _init.call(this, options)
    }
  }

  /**
   * Vuex init hook, injected into each instances init hooks list.
   */

  function vuexInit () {
    const options = this.$options
    // store injection
    if (options.store) {
     // 根组件挂载$store
      this.$store = typeof options.store === 'function'
        ? options.store()
        : options.store
    } else if (options.parent && options.parent.$store) {
     // 从父组件获取$store
      this.$store = options.parent.$store
    }
  }
}

export default Store {
  constructor (options = {}) {
    // Auto install if it is not done yet and `window` has `Vue`.
    // To allow users to avoid auto-installation in some cases,
    // this code should be placed here. See #731
    if (!Vue && typeof window !== 'undefined' && window.Vue) {
      install(window.Vue)
    }
   // ....
    const {
      plugins = [],
      strict = false
    } = options

    // store internal state
    this._committing = false
    this._actions = Object.create(null) // 用于存储配置的actions
    this._actionSubscribers = []
    this._mutations = Object.create(null) // 用于存储配置的mutations
    this._wrappedGetters = Object.create(null) // 用于存储配置的getters
    this._modules = new ModuleCollection(options)  // 实例化后会将我们在store初始化配置的mudule构建成属性，eg:{root: {_children: {a: module,  b: module}, module}}
    this._modulesNamespaceMap = Object.create(null) // 用去存储每个命令空间的模块。eg: {'a/': module, 'b/': module}
    this._subscribers = []
    this._watcherVM = new Vue()

    // bind commit and dispatch to self
    const store = this
    const { dispatch, commit } = this
   // 重新绑定dipatch和commit方法，强行将其执行上下文this指向store，避免用户使用时，改写this指向，导致出错
    this.dispatch = function boundDispatch (type, payload) {
      return dispatch.call(store, type, payload)
    }
    this.commit = function boundCommit (type, payload, options) {
      return commit.call(store, type, payload, options)
    }

    // strict mode
    this.strict = strict

    const state = this._modules.root.state

    //  根据命令空间与否注册所有模块的state,mutation,getter和action（重点）
    // init root module.
    // this also recursively registers all sub-modules
    // and collects all module getters inside this._wrappedGetters
    installModule(this, state, [], this._modules.root)

   // 将state和getters变成响应式（重点）
    // initialize the store vm, which is responsible for the reactivity
    // (also registers _wrappedGetters as computed properties)
    resetStoreVM(this, state)

    // apply plugins
    plugins.forEach(plugin => plugin(this))

    if (Vue.config.devtools) {
      devtoolPlugin(this)
    }
  }

 function installModule (store, rootState, path, module, hot) {
   const isRoot = !path.length
   const namespace = store._modules.getNamespace(path)

   // register in namespace map
   if (module.namespaced) {
     store._modulesNamespaceMap[namespace] = module
   }

   // set state
   if (!isRoot && !hot) {
     const parentState = getNestedState(rootState, path.slice(0, -1))
     const moduleName = path[path.length - 1]
     store._withCommit(() => {
       Vue.set(parentState, moduleName, module.state)
     })
   }

   const local = module.context = makeLocalContext(store, namespace, path)

   module.forEachMutation((mutation, key) => {
     const namespacedType = namespace + key
     registerMutation(store, namespacedType, mutation, local)
   })

   module.forEachAction((action, key) => {
     const type = action.root ? key : namespace + key
     const handler = action.handler || action
     registerAction(store, type, handler, local)
   })

   module.forEachGetter((getter, key) => {
     const namespacedType = namespace + key
     registerGetter(store, namespacedType, getter, local)
   })

   module.forEachChild((child, key) => {
    installModule(store, rootState, path.concat(key), child, hot)
   })
 }
   /**
   * make localized dispatch, commit, getters and state
   * if there is no namespace, just use root ones
   */
  function makeLocalContext (store, namespace, path) {
    const noNamespace = namespace === ''

    const local = {
      dispatch: noNamespace ? store.dispatch : (_type, _payload, _options) => {
        const args = unifyObjectStyle(_type, _payload, _options)
        const { payload, options } = args
        let { type } = args

        if (!options || !options.root) {
          type = namespace + type
          if (process.env.NODE_ENV !== 'production' && !store._actions[type]) {
            console.error(`[vuex] unknown local action type: ${args.type}, global type: ${type}`)
            return
          }
        }

        return store.dispatch(type, payload)
      },

      commit: noNamespace ? store.commit : (_type, _payload, _options) => {
        const args = unifyObjectStyle(_type, _payload, _options)
        const { payload, options } = args
        let { type } = args

        if (!options || !options.root) {
          type = namespace + type
          if (process.env.NODE_ENV !== 'production' && !store._mutations[type]) {
            console.error(`[vuex] unknown local mutation type: ${args.type}, global type: ${type}`)
            return
          }
        }

        store.commit(type, payload, options)
      }
    }

    // getters and state object must be gotten lazily
    // because they will be changed by vm update
    Object.defineProperties(local, {
      getters: {
        get: noNamespace
          ? () => store.getters
          : () => makeLocalGetters(store, namespace)
      },
      state: {
        get: () => getNestedState(store.state, path)
      }
    })

    return local
  }

  function resetStoreVM (store, state, hot) {
    const oldVm = store._vm

    // bind store public getters
    store.getters = {}
    const wrappedGetters = store._wrappedGetters
    const computed = {}
    forEachValue(wrappedGetters, (fn, key) => {
      // use computed to leverage its lazy-caching mechanism
      computed[key] = () => fn(store)
      Object.defineProperty(store.getters, key, {
        get: () => store._vm[key],
        enumerable: true // for local getters
      })
    })

    // use a Vue instance to store the state tree
    // suppress warnings just in case the user has added
    // some funky global mixins
    const silent = Vue.config.silent
    Vue.config.silent = true
    store._vm = new Vue({
      data: {
        $$state: state
      },
      computed
    })
    Vue.config.silent = silent

    // enable strict mode for new vm
    if (store.strict) {
      enableStrictMode(store)
    }

    if (oldVm) {
      if (hot) {
        // dispatch changes in all subscribed watchers
        // to force getter re-evaluation for hot reloading.
        store._withCommit(() => {
          oldVm._data.$$state = null
        })
      }
      Vue.nextTick(() => oldVm.$destroy())
    }
  }
}

// 二叉搜索树
function BinaryTree() {
  const Node = function(key) {
    //节点函数
    this.key = key;
    this.left = null;
    this.right = null;
  };

  let root = null;

  // 插入
  this.insert = function(key) {
    // 插入节点
    let insertNode = function(node, newNode) {
      if (node.key > newNode.key) {
        if (node.left == null) {
          node.left = newNode;
        } else {
          insertNode(node.left, newNode);
        }
      } else {
        if (node.right == null) {
          node.right = newNode;
        } else {
          insertNode(node.right, newNode);
        }
      }
    };
    const newNode = new Node(key);
    if (root == null) {
      root = newNode;
    } else {
      insertNode(root, newNode);
    }
  };

  // 获取二叉树
  this.getTree = function() {
    return root;
  }

  // 递归中序遍历 排序
  this.inOrderTraverse = function(callback) {
    const inOrderTraverseNode = function(node, callback) {
      if (node != null) {
        inOrderTraverseNode(node.left, callback);
        callback(node.key);
        inOrderTraverseNode(node.right, callback);
      }
    };
    inOrderTraverseNode(root, callback);
  };

  // 非递归中序遍历(利用栈实现)
  this.nonRecursiveInOrderTraverse = function(callback) {
    const stack = [{status: 'next', node: root}];
    while(stack && stack.length !== 0) {
      const cur = stack.pop();
      if(cur.status === 'print') {
        callback(cur.node.key);
      } else {
        cur.node.right && stack.push({status: 'next', node: cur.node.right});
        stack.push({status: 'print', node: cur.node });
        cur.node.left && stack.push({status: 'next', node: cur.node.left});
      }
    }
  }

  //递归前序遍历  复制二叉树  效率高得多
  this.proOrderTraverse = function(callback) {
    const proOrderTraverseNode = function(node, callback) {
      if (node != null) {
        callback(node.key);
        proOrderTraverseNode(node.left, callback);
        proOrderTraverseNode(node.right, callback);
      }
    };
    proOrderTraverseNode(root, callback);
  };

  // 非递归前序遍历(利用栈实现)
  this.nonRecursiveProOrderTraverse = function(callback) {
    const stack = [{status: 'next', node: root}];
    while(stack && stack.length !== 0) {
      const cur = stack.pop();
      if(cur.status === 'print') {
        callback(cur.node.key);
      } else {
        cur.node.right && stack.push({status: 'next', node: cur.node.right});
        cur.node.left && stack.push({status: 'next', node: cur.node.left});
        stack.push({status: 'print', node: cur.node });
      }
    }
  }

  //后续遍历  文件系统遍历
  this.postOrderTraverse = function(callback) {
    const postOrderTraverseNode = function(node, callback) {
      if (node != null) {
        postOrderTraverseNode(node.left, callback);
        postOrderTraverseNode(node.right, callback);
        callback(node.key);
      }
    };
    postOrderTraverseNode(root, callback);
  };

  // 非递归前序遍历(利用栈实现)
  this.nonRecursivePostOrderTraverse = function(callback) {
    const stack = [{status: 'next', node: root}];
    while(stack && stack.length !== 0) {
      const cur = stack.pop();
      if(cur.status === 'print') {
        callback(cur.node.key);
      } else {
        stack.push({status: 'print', node: cur.node });
        cur.node.right && stack.push({status: 'next', node: cur.node.right});
        cur.node.left && stack.push({status: 'next', node: cur.node.left});
      }
    }
  }

  // 查找最大值
  this.max = function() {
    let node = root;
    if (node) {
      while (node && node.right != null) {
        node = node.right;
      }
    }
    return node.key;
  };

  // 查找最小值
  this.min = function() {
    let node = root;
    if (node) {
      while (node && node.left != null) {
        node = node.left;
      }
    }
    return node.key;
  };

  // 查找指定值
  this.search = function(key) {
    const searchNode = function(node, key) {
      if (node == null) {
        return false;
      }

      if (node.key > key) {
        searchNode(node.left, key);
      } else if (node.key < key) {
        searchNode(node.right, key);
      } else {
        return true;
      }
    };
    return searchNode(root, key);
  };

  /**
   * 二叉树的删除
   * 二叉树删除分三种情况
   * 删除左叶子节点
   * 删除右叶子节点
   * 以及拥有左右两个节点的主节点删除
   * 拥有左右两个节点的主节点删除要考虑到数据的可排序行需要将删掉的节点重新赋值
   */
  // 移除节点
  this.remove = function(key) {
    const findMinNode = function(node) {
      //如果存在左右两个节点的话查找右节点的最小节点
      if (node) {
        while (node && node.left != null) {
          node = node.left;
        }
        return node;
      }
      return null;
    };
    const removeNode = function(node, key) {
      if (node == null) {
        return null;
      }
  
      if (node.key > key) {
        // 递归查找左叶子节点，直接等于返回的null值
        node.left = removeNode(node.left, key);
        return node;
      } else if (node.key < key) {
        node.right = removeNode(node.right, key);
        return node;
      } else {
        if (node.left == null && node.right == null) {
          // 当只有一个节点，而且被选中
          node = null;
          return node;
        }
        if (node.left == null) {
          //左节点为空
          node = node.right;
          return node;
        } else if (node.right == null) {
          //右节点为空
          node = node.left;
          return node;
        }
  
        // ?????
        let aux = findMinNode(node.right); //查找到右节点最小节点赋值
        node.key = aux.key;
        node.right = removeNode(node.right, aux.key);
        return node;
      }
    };
    return removeNode(root, key);
  };
}

// test
const nodes = [8, 3, 10, 2, 9, 14, 4, 7, 13];
const binaryTree = new BinaryTree();
nodes.forEach(function(key) {
  binaryTree.insert(key);
});

const callback = function(key) {
  console.log(key);
};
binaryTree.nonRecursivePostOrderTraverse(callback);