// 导入，依赖就近风格
const a = require('a.js')
console.log(a)

// 导出
module.exports = {
  // ...
}

define(['jquery'], function ($) {
  // 此函数调用时， jquery 已经加载完成
})

define(function (require, exports, module) {
  const $ = require('jquery') // 依赖就近，延迟执行
})

define(['a', 'b'’], function (a, b) {
  a()
  if (false) {
    // AMD 规范中，即使 b 模块最终不会用到，但也会被执行
    b()
  }
})

define(function (require, exports, module) {
  const a = require('a')
  a()
  if (false) {
    // CMD 中， b 模块虽然也会下载，但需要在代码执行到 require 的时候才会执行
    const b = require('b')
    b()
  }
})

// Parse dependencies according to the module factory code
if (!isArray(deps) && isFunction(factory)) {
  deps = typeof parseDependencies === "undefined" ? [] : parseDependencies(factory.toString())
}

var funcs = [];
// let's create 3 functions
for (var i = 0; i < 3; i++) {
  // and store them in funcs
  funcs[i] = function() {
    // each should log its value.
    console.log("My value: " + i);
  };
}
for (var j = 0; j < 3; j++) {
  // and now let's run each one to see
  funcs[j]();
}

function run() {
  console.log(foo); // undefined
  var foo = "Foo";
  console.log(foo); // Foo
}

run();

function checkHoisting() {
  console.log(foo); // ReferenceError
  let foo = "Foo";
  console.log(foo); // Foo
}

checkHoisting();

var foo = "Foo";  // globally scoped
let bar = "Bar"; // globally scoped

console.log(window.foo); // Foo
console.log(window.bar); // undefined

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    const result = []

    const traverse = (node) => {
        if (!node) return
        result.push(node.val)
        if (node.left) traverse(node.left)
        if (node.right) traverse(node.right)
    }

    traverse(root)

    return result
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    const result = []
    const stack = []
    
    let node = root
    while (node || stack.length) {
        while (node) {
            result.push(node.val)
            stack.push(node)
            node = node.left
        }
        node = stack.pop().right
    }

    return result
};

const iterable = {
  [Symbol.iterator] () {
    let i = 0
    return {
      next () {
        return { value: i++, done: i > 5 }
      }
    }
  }
}

for (let i of iterable) {
  console.log(i)
}
// 0 1 2 3 4

const iter = iterable[Symbol.iterator]()

console.log(iter.next()) // { value: 0, done: false }
console.log(iter.next()) // { value: 1, done: false }
console.log(iter.next()) // { value: 2, done: false }
console.log(iter.next()) // { value: 3, done: false }
console.log(iter.next()) // { value: 4, done: false }
console.log(iter.next()) // { value: 5, done: true }

const arr = [1, 2, 3]
const it = arr[Symbol.iterator]()
it.next() // { value: 1, done: false }
it.next() // { value: 2, done: false }
it.next() // { value: 3, done: false }
it.next() // { value: undefined, done: true }

function readLinesSync (file) {
  return {
    [Symbol.iterator] () {
      return {
        next () {
          return { done: false }
        },
        return () {
          file.close()
          return { done: true }
        }
      }
    }
  }
}

for (let line of readLinesSync(fileName)) {
  console.log(line)
  break
}

// 或者

for (let line of readLinesSync(fileName)) {
  console.log(line)
  throw new Error()
}

for (let key in [1, 2, 3]) {
  console.log(typeof key) // string
}

const arr = [1, 2, 3]
Object.setPrototypeOf(arr, { protoProperty: 666 })
for (let key in arr) {
  console.log(key)
}
// 0 1 2 protoProperty

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    const result = []
    const traverse = (node) => {
        if (node) {
            if (node.left) traverse(node.left)
            if (node.right) traverse(node.right)
            result.push(node.val)
        }
    }
    traverse(root)
    return result
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    const result = []
    const stack = []
    let seen = null
    let node = root
    while (node || stack.length) {
        while (node) {
            stack.push(node)
            node = node.left
        }
        // 此处因为中间节点可能还不能 push 到 result 中，因此不用 pop
        const last = stack[stack.length - 1]
        if (!last.right || last.right === seen) {
            // 如果没有右子节点或者右子节点已经遍历过了
            result.push(last.val)
            seen = last
            stack.pop()
        } else {
            node = last.right
        }
    }
    return result
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    const result = []
    if (!root) return result
    const stack = [root]
    while (stack.length) {
        const node = stack.pop()
        if (node.left) stack.push(node.left)
        if (node.right) stack.push(node.right)
        result.unshift(node.val)
    }
    return result
};

/** 观察者集合 */
const observerSet = new Set()

// 观察者模式方法
const observe = (fn) => observerSet.add(fn)
const observable = (obj) => new Proxy(obj, { set })
const set = (target, key, value, receiver) => {
  // 先完成默认行为
  const result = Reflect.set(target, key, value, receiver)
  // 通知观察者变化
  observerSet.forEach((observer) => observer())
  return result
}

/** 观察目标 */
const person = observable({
  name: 'a',
  age: 18,
})

/** 观察者 */
const print = () => {
  console.log(`${person.name}, ${person.age}`)
}

observe(print)

person.name = 'b' // b 18

function* gen () {}

function* gen () {
  yield 1
  yield 1 + 1
  return 3
}

// Iterator
const it = gen()
it.next() // { value: 1, done: false }
it.next() // { value: 2, done: false }
it.next() // { value: 3, done: true }

function* gen () {
  console.log('executed')
}

const it = gen()
it.next()
// executed

function* demo() {
  console.log('Hello' + yield); // SyntaxError
  console.log('Hello' + yield 123); // SyntaxError

  console.log('Hello' + (yield)); // OK
  console.log('Hello' + (yield 123)); // OK
}

function* gen () {
  yield 1
  yield 2
  yield 3
  return 4
}

for (let value of gen()) {
  console.log(value)
}
//  1 2 3
// 注意， `for...of` 循环不会输出结果为 `done: true` 的值

function* gen () {
  const i = yield 1
  console.log(i)
  yield i + 1
}

const it = gen()
const y1 = it.next() // { value: 1, done: false }
it.next(y1.value + 1)
// 函数内部输出 2
// next 返回值： { value: 3, done: false }
it.next() // { value: undefined, done: true }

function* gen () {
  try {
    yield
  } catch (e) {
    console.log('Generator 函数内部捕获', e)
  }
}

const it = gen()
it.next() // 先执行到第一个 yield 处
it.throw('手动抛出一个错误')
// Generator 函数内部捕获 手动抛出一个错误

function* gen () {
  yield 1
  yield 2
  yield 3
  return 4
}

const it = gen()
it.next() // { value: 1, done: false }
it.return() // { value: undefined, done: true }
it.next() // { value: undefined, done: true }

function* gen () {
  yield 1
  yield 2
  yield 3
  return 4
}

const it = gen()
it.next() // { value: 1, done: false }
it.return('foo') // { value: 'foo', done: true }
it.next() // { value: undefined, done: true }

function* gen () {
  const r = yield 1
}

const it = gen()
it.next() // 执行到第一个 yield

it.next()
// 相当于把 `const r = yield 1` 替换成 `const r = undefined`

// it.throw(new Error('error'))
// 相当于把 `const r = yield 1` 替换成 `const r = throw new Error('error')`

// it.return(6)
// 相当于把 `const r = yield 1` 替换成 `const r = return 6`

function* bar () {
  yield 1
  yield 2
}

function* foo () {
  yield 3
  // 这边如果没有手动去遍历 `bar()` 返回的迭代器， `foo` 的下一个 `next` 函数就会执行到 `yield 4` 了
  bar()
  yield 4
}

const it = foo()
for (let value of it) {
  console.log(value)
}
// 3 4

function* bar () {
  yield 1
  yield 2
}

function* foo () {
  yield 3
  for (let value of bar()) {
    yield value
  }
  yield 4
}

const it = foo()
for (let value of it) {
  console.log(value)
}
// 3 1 2 4

function* bar () {
  yield 1
  yield 2
}

function* foo () {
  yield 3
  yield* bar()
  yield 4
}

const it = foo()
for (let value of it) {
  console.log(value)
}
// 3 1 2 4

const obj = {
  * generatorProperty () {
    yield 1
  }
}

function* gen () {
  this.a = 1
}

const it = gen()
console.log(it instanceof gen) // true , 这是 ES6 规定的，返回的迭代器是 Generator 函数的实例
console.log(it.a) // undefined

function* gen () {
  this.a = 1
}

const it = new gen() // TypeError: gen is not a constructor

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
  this.capacity = capacity
  this.map = new Map()
  // 指向排名开头的指针
  this.pStart = null
  // 指向排名结尾的指针
  this.pEnd = null
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  const result = this.map.get(key)
  // 找不到则返回 -1
  if (!result) return -1
  // 如果 get 的是末尾，则不操作
  if (this.pEnd !== result) {
    if (result.prev) {
      // 如果 get 的不是开头
      // 上一个链表元素的 next 指向 get 的 next
      result.prev.next = result.next
      // 下一个链表元素的 prev 指向 get 的 prev
      result.next.prev = result.prev
    } else {
      // 如果 get 的是开头，则重新赋值 pStart
      this.pStart = result.next
      this.pStart.prev = null
    }
    // get 的元素放到链表末尾
    result.next = null
    this.pEnd.next = result
    result.prev = this.pEnd
    this.pEnd = result
  }
  return result.value
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  if (!this.map.has(key)) {
    if (this.map.size === this.capacity) {
      // 容量达到上限，先删除最近最少使用的缓存，直接把 pStart 指向的链表元素删除
      this.map.delete(this.pStart.key)
      this.pStart = this.pStart.next
      if (this.pStart) {
        this.pStart.prev = null
      }
    }
    // put 操作插入的 rank 一定是最高的，因此 next 指向空
    const element = {
      key,
      value,
      prev: this.pEnd,
      next: null,
    }
    if (this.map.size === 0) {
      this.pStart = element
    } else {
      this.pEnd.next = element
    }
    this.pEnd = element
    this.map.set(key, element)
  } else {
    this.map.get(key).value = value
    this.get(key)
  }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
  this.capacity = capacity
  this.map = new Map()
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  const result = this.map.get(key)
  // 找不到则返回 -1
  if (!result) return -1
  this.map.delete(key)
  this.map.set(key, result)
  return result
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  if (!this.map.has(key)) {
    if (this.map.size === this.capacity) {
      this.map.delete(this.map.keys().next().value)
    }
    this.map.set(key, value)
  } else {
    this.map.delete(key)
    this.map.set(key, value)
  }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

const proxyObject = new Proxy({}, {
  get (target, key, receiver) {
    // target: 目标对象
    // key: 当前获取的键
    // receiver: 当前 Proxy 对象
    console.log('getting ', key)
    return Reflect.get(target, key, receiver)
  },
  set (target, key, value, receiver) {
    // value 当前设置的值
    console.log('setting ', key)
    return Reflect.set(target, key, value, receiver)
  },
})

proxyObject.a = 1 // setting a

proxyObject.a++
// getting a
// setting a
// 1

const { proxy, revoke } = Proxy.revocable({}, {})

proxy.a = 1
proxy.a // 1

revoke()

proxy.a // TypeError: Cannot perform 'get' on a proxy that has been revoked

const target = {
  f () {
    return this
  }
}

const proxy = new Proxy(target, {})

target.f() === target // true
proxy.f() === target // false
proxy.f() === proxy // true

const target = new Date()
const proxy = new Proxy(target, {})

proxy.getDate() // TypeError: this is not a Date object

const target = new Date()
const proxy = new Proxy(target, {
  get (target, key) {
    if (key === 'getDate') {
      // 判断是否调用的 getDate 方法
      return target.getDate.bind(target)
    }
    return Reflect.get(target, key)
  }
})

proxy.getDate() // 正常显示日期

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    const result = []
    if (!root) return result
    const stack = [[root, 0]]
    while (stack.length) {
        const info = stack.pop()
        const node = info[0]
        const level = info[1]
        if (node) {
            if (result.length <= level) result.unshift([])
            result[result.length - 1 - level].push(node.val)
            stack.push([node.right, level + 1])
            stack.push([node.left, level + 1])
        }
    }
    return result
};

// 同步引入
import syncHello from './sync-hello'

document.querySelector('#text').innerText += `${syncHello}\n`

// 异步引入
import(/* webpackChunkName: "async" */ './async-hello').then(({ default: asyncHello }) => {
  document.querySelector('#text').innerText += `${asyncHello}\n`
})

import generateHello from './sync-util'

export default generateHello('sync code')

const generateHello = (source) => {
  return `Hello from ${source}`
}

export default generateHello

import generateHello from './sync-util'

export default generateHello('async code')

module.exports = {
  devtool: 'inline-source-map'
}

(function (modules) {
  // webpack bootstrap
})({
  // modules
})

{
  "./src/index.js": (function (module, __webpack_exports__, __webpack_require__) {
    // 模块内容
  })
  "./src/sync-hello.js": (function (module, __webpack_exports__, __webpack_require__) {
    // 模块内容
  })
  "./src/sync-util.js": (function (module, __webpack_exports__, __webpack_require__) {
    // 模块内容
  })
}

{
  "./src/sync-hello.js": (function(module, __webpack_exports__, __webpack_require__) {
    // 模块默认是严格模式
    "use strict";
    // 在 exports 中加上 __esModule 属性，表示是 ES 模块
    __webpack_require__.r(__webpack_exports__);
    // 导入 sync-util 模块
    var _sync_util__WEBPACK_IMPORTED_MODULE_0__ = __webpack_require__("./src/sync-util.js");
    // 导出此模块
    __webpack_exports__["default"] = (Object(_sync_util__WEBPACK_IMPORTED_MODULE_0__["default"])('sync code'));
  })
}

(function (modules) {
  // 模块缓存
  var installedModules = {}
  // The require function
  function __webpack_require__(moduleId) {

    // 检查是否在缓存中，如果是，则表示模块执行过了，直接返回缓存的结果
    if(installedModules[moduleId]) {
      return installedModules[moduleId].exports;
    }
    // 创建新模块并缓存
    var module = installedModules[moduleId] = {
      i: moduleId,
      l: false,
      exports: {}
    };

    // 执行模块函数
    modules[moduleId].call(module.exports, module, module.exports, __webpack_require__);

    // 标识模块已经加载过了
    module.l = true;

    // 返回模块的导出（exports）
    return module.exports;
  }
  // ...定义了一堆东西
  // Load entry module and return exports
  return __webpack_require__(__webpack_require__.s = "./src/index.js");
})({
  // modules
})

import(/* webpackChunkName: "async" */ './async-hello').then(({ default: asyncHello }) => {
  document.querySelector('#text').innerText += `${asyncHello}\n`
})

__webpack_require__.e(/*! import() | async */ "async").then(__webpack_require__.bind(null, /*! ./async-hello */ "./src/async-hello.js")).then(({ default: asyncHello }) => {
  document.querySelector('#text').innerText += `${asyncHello}\n`
})

__webpack_require__.e(chunkId).then(__webpack_require__.bind(null, moduleId))

// 加载代码块的 jsonp 回调
function webpackJsonpCallback (data) {
  var chunkIds = data[0];
  var moreModules = data[1];

  // 把 data 参数数组的第二个元素添加到 modules 对象中（也就是引导函数的 modules 参数）
  // 把 chunkIds 里的元素都标记为已加载（即在 installedChunks 中置为 0 ）
  var moduleId, chunkId, i = 0, resolves = [];
  for (; i < chunkIds.length; i++) {
    chunkId = chunkIds[i];
    if (Object.prototype.hasOwnProperty.call(installedChunks, chunkId) && installedChunks[chunkId]) {
      resolves.push(installedChunks[chunkId][0]);
    }
    installedChunks[chunkId] = 0;
  }
  for (moduleId in moreModules) {
    if (Object.prototype.hasOwnProperty.call(moreModules, moduleId)) {
      modules[moduleId] = moreModules[moduleId];
    }
  }
  if (parentJsonpFunction) parentJsonpFunction(data);

  while (resolves.length) {
    resolves.shift()();
  }
};

// 存储已加载或正在加载的块（chunk）
// undefined = chunk 未加载, null = chunk preloaded/prefetched
// Promise = chunk 正在加载, 0 = chunk 已加载
var installedChunks = {
  "main": 0
};

// script path function
function jsonpScriptSrc(chunkId) {
  return __webpack_require__.p + "" + ({"async":"async"}[chunkId]||chunkId) + ".js"
}

// 由于 main.js 只包含入口的块（chunk），因此提供以下函数
// 加载额外（异步）块的函数
__webpack_require__.e = function requireEnsure (chunkId) {
  var promises = [];


  // JSONP chunk loading for javascript

  var installedChunkData = installedChunks[chunkId];
  if (installedChunkData !== 0) { // 0 表示 "已安装".

    // 一个 Promise 表示 "正在加载".
    if (installedChunkData) {
      promises.push(installedChunkData[2]);
    } else {
      // installedChunks[chunkId] === undefined , 表示此 chunk 未加载
      // 因此将 installedChunks[chunkId] 赋值为 Promise 表示正在加载这个 chunk
      var promise = new Promise(function (resolve, reject) {
        installedChunkData = installedChunks[chunkId] = [resolve, reject];
      });
      promises.push(installedChunkData[2] = promise);

      // start chunk loading
      var script = document.createElement('script');
      var onScriptComplete;

      script.charset = 'utf-8';
      script.timeout = 120;
      if (__webpack_require__.nc) {
        script.setAttribute("nonce", __webpack_require__.nc);
      }
      script.src = jsonpScriptSrc(chunkId);

      // create error before stack unwound to get useful stacktrace later
      var error = new Error();
      // script 标签下载、执行完成后的回调
      onScriptComplete = function (event) {
        // avoid mem leaks in IE.
        script.onerror = script.onload = null;
        clearTimeout(timeout);
        var chunk = installedChunks[chunkId];
        if (chunk !== 0) {
          if (chunk) {
            var errorType = event && (event.type === 'load' ? 'missing' : event.type);
            var realSrc = event && event.target && event.target.src;
            error.message = 'Loading chunk ' + chunkId + ' failed.\n(' + errorType + ': ' + realSrc + ')';
            error.name = 'ChunkLoadError';
            error.type = errorType;
            error.request = realSrc;
            chunk[1](error);
          }
          installedChunks[chunkId] = undefined;
        }
      };
      // 2 分钟超时
      var timeout = setTimeout(function () {
        onScriptComplete({ type: 'timeout', target: script });
      }, 120000);
      script.onerror = script.onload = onScriptComplete;
      // 把 script 标签插入 html ，开始下载异步模块
      document.head.appendChild(script);
    }
  }
  return Promise.all(promises);
};

var jsonpArray = window["webpackJsonp"] = window["webpackJsonp"] || [];
var oldJsonpFunction = jsonpArray.push.bind(jsonpArray);
// 重写 push 方法，因此 script 标签下载完成时执行的 jsonp 回调就是 webpackJsonpCallback
jsonpArray.push = webpackJsonpCallback;
jsonpArray = jsonpArray.slice();
for(var i = 0; i < jsonpArray.length; i++) webpackJsonpCallback(jsonpArray[i]);
// parentJsonpFunction 就是数组原来的 push 方法
var parentJsonpFunction = oldJsonpFunction;

(window["webpackJsonp"] = window["webpackJsonp"] || []).push([["async"], {
  "./src/async-hello.js": (function (module, __webpack_exports__, __webpack_require__) {
    "use strict";
    __webpack_require__.r(__webpack_exports__);
    var _sync_util__WEBPACK_IMPORTED_MODULE_0__ = __webpack_require__("./src/sync-util.js");

    __webpack_exports__["default"] = (Object(_sync_util__WEBPACK_IMPORTED_MODULE_0__["default"])('async code'));
  })
}]);

__webpack_require__.e(chunkId).then(__webpack_require__.bind(null, moduleId))

__webpack_require__.e(chunkId).then(() => {
  return __webpack_require__(moduleId)
})

window.jsonpCallback = (responseData) => {
  // 处理跨域请求返回的数据
}

// 也就是执行了：
window.jsonpCallback({ data: 666 })

otherWindow.postMessage(message, targetOrigin, [transfer])

const passTest = (
  // 判断 x 轴
  Math.max(x1, x2) >= Math.min(x3, x4) &&
  Math.max(x3, x4) >= Math.min(x1, x2) &&
  // 判断 y 轴
  Math.max(y1, y2) >= Math.min(y3, y4) &&
  Math.max(y3, y4) >= Math.min(y1, y2)
)

function getAsyncValue () {
  return new Promise((resolve, reject) => {
    setTimeout(resolve, 10, 123)
  })
}

async function asyncFunction (p) {
  console.log('param: ', p)
  const value = await getAsyncValue()
  return value
}

asyncFunction(666).then((result) => {
  console.log(result)
})

// param: 666
// 123

const _async = (generator) => {
  return function (...args) {
    // async 函数返回一个 Promise
    return new Promise((resolve, reject) => {
      // Promise 内部会自动将 Generator 函数返回的迭代器执行到最后
      const it = generator(...args)
      const step = (nextFunction) => {
        let next
        try {
          next = nextFunction()
        } catch (e) {
          reject(e)
        }
        if (next.done) {
          return resolve(next.value)
        }
        // 其中， next 的执行时机就是 yield 后面的 Promise 状态改变的时候
        // next 的参数就是上一个 yield 的值
        Promise.resolve(next.value).then((value) => {
          return step(() => it.next(value))
        }, (reason) => {
          return step(() => it.throw(reason))
        })
      }
      step(() => it.next())
    })
  }
}

function getAsyncValue () {
  return new Promise((resolve, reject) => {
    setTimeout(resolve, 10, 123)
  })
}

const asyncFunction = _async(function* (p) {
  console.log('param: ', p)
  const value = yield getAsyncValue()
  return value
})

asyncFunction(666).then((result) => {
  console.log(result)
})

// param: 666
// 123

function func () {
  var obj1 = {}
  var obj2 = {}
  obj1.a = obj2
  obj2.a = obj1
}

func()

function func () {
  property = 1
}

function func () {
  this.property = 1
}

// 直接在全局作用域调用
func()

let a = 1
setInterval(function () {
  let b = a
}, 1000)

var $button = document.getElementById('button')

// ...do something

$button.remove()

// 记得清除引用
$button = null

var theThing = null;
var replaceThing = function () {
  var originalThing = theThing;
  var unused = function () {
    if (originalThing)
      console.log('hi');
  };
  theThing = {
    longStr: new Array(1000000).join('*'),
    someMethod: function () {
      console.log('someMessage');
    }
  };
};
setInterval(replaceThing, 1000);

function bubbleSort (array) {
  const length = array.length
  for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      if (array[j] < array[j - 1]) {
        [array[j], array[j - 1]] = [array[j - 1], array[j]]
      }
    }
  }
}

function selectionSort (array) {
  const length = array.length
  for (let i = 0; i < length; i++) {
    let minIndex = i
    for (let j = i + 1; j < length; j++) {
      if (array[j] < array[minIndex]) minIndex = j
    }
    [array[i], array[minIndex]] = [array[minIndex], array[i]]
  }
}

function insertionSort (array) {
  const length = array.length
  for (let i = 1; i < length; i++) {
    const insertValue = array[i]
    // 注：此处可用二分查找
    let j = i - 1
    for (; j >=0; j--) {
      if (array[j] > insertValue) {
        array[j + 1] = array[j]
      } else break
    }
    array[j + 1] = insertValue
  }
}

function sort (array, startIndex = 0, endIndex = array.length - 1) {
  if (startIndex >= endIndex) return
  const pivot = array[startIndex]
  let left = startIndex
  let right = endIndex
  while (left < right) {
    while (left < right && array[right] > pivot) right--
    while (left < right && array[left] <= pivot) left++
    if (left < right) {
      [array[left], array[right]] = [array[right], array[left]]
    }
  }
  [array[startIndex], array[left]] = [array[left], array[startIndex]]
  sort(array, startIndex, left - 1)
  sort(array, left + 1, endIndex)
}

function quickSort (array) {
  sort(array)
}

function partition(array, startIndex = 0, endIndex = array.length - 1) {
  if (startIndex >= endIndex) return -1
  const pivot = array[startIndex]
  let left = startIndex
  let right = endIndex
  while (left < right) {
    while (left < right && array[right] > pivot) right--
    while (left < right && array[left] <= pivot) left++
    if (left < right) {
      [array[left], array[right]] = [array[right], array[left]]
    }
  }
  [array[startIndex], array[left]] = [array[left], array[startIndex]]
  return left
}

function quickSort (array) {
  const stack = [[0, array.length - 1]]
  while (stack.length) {
    const pair = stack.pop()
    const pivot = partition(array, pair[0], pair[1])
    if (pivot !== -1) {
      stack.push([pivot + 1, pair[1]])
      stack.push([pair[0], pivot - 1])
    }
  }
}

// 最小堆下沉操作
function down (array, position, length) {
  const target = array[position]
  let parentIndex = position
  let leftChildIndex = 2 * parentIndex + 1
  while (leftChildIndex < length) {
    const rightChildIndex = leftChildIndex + 1
    if (rightChildIndex < length && array[rightChildIndex] < array[leftChildIndex]) leftChildIndex = rightChildIndex
    if (array[leftChildIndex] >= target) break
    array[parentIndex] = array[leftChildIndex]
    parentIndex = leftChildIndex
    leftChildIndex = 2 * parentIndex + 1
  }
  array[parentIndex] = target
}

function heapSort (array) {
  const length = array.length
  // 构建二叉堆
  for (let i = Math.floor((length - 2) / 2); i >= 0; i--) {
    down(array, i, length)
  }
  // 将二叉堆逐个输出，把删除的元素移动到堆末尾
  for (let i = length - 1; i >= 0; i--) {
    const first = array[0]
    array.push(first)
    if (i !== 0) {
      array[0] = array.splice(i, 1)[0]
      down(array, 0, i)
    } else {
      array.splice(i, 1)
    }
  }
}

function merge (array, start, mid, end) {
  const mergedArray = []
  let p1 = start
  let p2 = mid + 1
  let p = 0
  while (p1 <= mid && p2 <= end) {
    if (array[p1] <= array[p2]) {
      mergedArray[p++] = array[p1++]
    } else {
      mergedArray[p++] = array[p2++]
    }
  }
  while (p1 <= mid) mergedArray[p++] = array[p1++]
  while (p2 <= end) mergedArray[p++] = array[p2++]
  const length = mergedArray.length
  for (let i = 0; i < length; i++) {
    array[i + start] = mergedArray[i]
  }
}

function mergeSort (array, start = 0, end = array.length - 1) {
  if (end > start) {
    const mid = start + Math.floor((end - start) / 2)
    mergeSort(array, start, mid)
    mergeSort(array, mid + 1, end)
    merge(array, start, mid, end)
  }
}

function shellSort (array) {
  const length = array.length
  let d = length
  while (d > 1) {
    d = Math.floor(d / 2)
    for (let i = d; i < length; i += d) {
      const insertValue = array[i]
      let j = i - d
      for (; j >= 0; j -= d) {
        if (array[j] > insertValue) {
          array[j + d] = array[j]
        } else break
      }
      array[j + d] = insertValue
    }
  }
}