js-train

目录

• Color

• Debounce

• DeepClone

• DismantleArray

• DynamicPlanning

• Event

• Format

• Inherit

• JsBridge

• LuckyDraw

• Middleware

• New

• Num2ChineseNum

• Promise

  • promise

  • promiseAll

  • promiseRace

• ReadFiles

• Redux

  • redux

  • middleware

• Regex

• Request4Node

• Sort

  • bubbleSort

  • quickSort

• Stack

• Throttle

• Tree

  • expandTree

  • findPath

  • genTree

  • transform

• Websocket

Color

// #ffffff
function hex2Rgb(hex) {
  hex = hex.replace('#', '')

  return `rgb(${hex
    .split('')
    .reduce((result, item, i) => {
      if (i % 2 === 1) {
        result[result.length - 1] = result[result.length - 1] + item
        return result
      } else {
        return result.concat(item)
      }
    }, [])
    .map(o => parseInt(o, 16))
    .join()})`
}

// rgb(255,255,255)
function rgb2Hex(rgb) {
  const rgbArr = rgb.match(/\d+/g)
  return (
    '#' +
    rgbArr
      .map(color => {
        return Number(color).toString(16).padStart(2, '0')
      })
      .join('')
  )
}

// #ffffff or rgb(255,255,255)
function isHex(color) {
  return color.startsWith('#')
}

// rgb(255,255,255)
function getRgbArr(color) {
  return color.match(/\d+/g).map(o => Number(o))
}

function calcColor(start, end, ratios) {
  return Math.floor(start + (end - start) * ratios)
}

// Gradient = Start+ (End-Start) / Step * N
function gradientColor(sColor, eColor, min, max, value) {
  const formatStartColor = isHex(sColor) ? hex2Rgb(sColor) : sColor
  const formatEndColor = isHex(eColor) ? hex2Rgb(eColor) : eColor

  const [sR, sG, sB] = getRgbArr(formatStartColor)
  const [eR, eG, eB] = getRgbArr(formatEndColor)

  let ratios = value / (max - min)

  ratios = Math.min(ratios, 1)

  ratios = Math.max(ratios, 0)

  const result = [calcColor(sR, eR, ratios), calcColor(sG, eG, ratios), calcColor(sB, eB, ratios)]

  return rgb2Hex(`rgb(${result.join()})`)
}

console.log(gradientColor('#021137', '#315FAE', 1, 10, 2))

Debounce

const debounce = (fn, delay, maxTime) => {
  let timer = null
  let lastTime = 0
  maxTime = maxTime ?? delay

  return function () {
    const context = this

    if (lastTime) {
      const currentTime = +new Date()
      if (currentTime - lastTime > maxTime) {
        lastTime = +new Date()
        fn.apply(context, arguments)
      } else {
        clearTimeout(timer)
        timer = setTimeout(function () {
          lastTime = +new Date()
          fn.apply(context, arguments)
        }, delay)
      }
    } else {
      fn.apply(context, arguments)
      timer = true
      lastTime = +new Date()
    }
  }
}

const fn = debounce(() => {
  console.log('user click')
}, 500)

setInterval(fn, 100)

DeepClone

// 通过数组存储，查询访问对象
// 尾调用，提高递归效率
const deepCloneByArray = val => {
  const visitedObjs = []

  const clone = val => {
    if (val instanceof RegExp) return new RegExp(val)
    if (val instanceof Date) return new Date(val)
    if (val === null || typeof val !== 'object') return val // 简单类型

    let retVal
    let visitedObj = visitedObjs.find(({ obj }) => obj === val)
    if (!visitedObj) {
      retVal = Array.isArray(val) ? [] : {}
      visitedObjs.push({ obj: val, retVal })
      Object.keys(val).forEach(key => {
        retVal[key] = clone(val[key])
      })
      return retVal
    } else {
      return visitedObj.retVal
    }
  }

  return clone(val)
}

// 通过Map，提高搜索访问对象效率
const deepCloneByMap = val => {
  const visitedObjs = new Map()

  const clone = val => {
    if (val instanceof RegExp) return new RegExp(val)
    if (val instanceof Date) return new Date(val)
    if (val === null || typeof val !== 'object') return val // 简单类型

    let retVal
    if (!visitedObjs.has(val)) {
      retVal = Array.isArray(val) ? [] : {}
      visitedObjs.set(val, retVal)
      Object.keys(val).forEach(key => {
        retVal[key] = clone(val[key])
      })
      return retVal
    } else {
      return visitedObjs.get(val)
    }
  }

  return clone(val)
}

// WeakMap 比 Map更安全，防止Map的key不被垃圾回收
const deepCloneByWeakMap = (obj, hash = new WeakMap()) => {
  // 递归拷贝
  if (obj instanceof RegExp) return new RegExp(obj)
  if (obj instanceof Date) return new Date(obj)
  if (obj === null || typeof obj !== 'object') return obj // 简单类型

  if (hash.has(obj)) return hash.get(obj) // 循环引用

  const instance = new obj.constructor()
  hash.set(obj, instance)

  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      instance[key] = deepCloneByWeakMap(obj[key], hash)
    }
  }
  return instance
}

const obj = { a: 2 }
obj.b = { d: 1, c: obj, e: [1, 2, 3, obj] }
obj.b.f = obj.b.c
obj.f = obj.b.e

let start = +new Date()
console.log(deepCloneByArray(obj))
console.log(+new Date() - start, 'Array')

let start1 = +new Date()
console.log(deepCloneByMap(obj))
console.log(+new Date() - start1, 'Map')

let start2 = +new Date()
console.log(deepCloneByWeakMap(obj))
console.log(+new Date() - start2, 'WeakMap')

DismantleArray

/**
 *  输入：[1, [2, 3, [4]], 5]  '[a, [b, [c], e], d, f]'
 * 输出：{ a: 1, b: 2, c: 4, e: undefined, d: 5, f: undefined }
 * 注意：e和f没有匹配到任何值
 * @param a
 * @param b
 * @returns {{}}
 */

function dismantleArray(a, b) {
  try {
    b = JSON.parse(b.replace(/(\w+)/g, '"$1"'))
  } catch (e) {
    console.log('输入字符串有误')
  }

  function parse(initArr, matchArr, initRet = {}) {
    for (let i = 0, j = 0; i < matchArr.length; i++, j++) {
      let key = matchArr[i]
      if (Array.isArray(key) && Array.isArray(initArr[j])) {
        parse(initArr[j], matchArr[i], initRet)
      } else if (!Array.isArray(key) && Array.isArray(initArr[j])) {
        if (!initRet[key]) {
          initRet[key] = undefined
        }
        j = j - 1
      } else if (Array.isArray(key) && !Array.isArray(initArr[j])) {
        if (j < initArr.length) {
          i = i - 1
        } else {
          parse([], matchArr[i], initRet)
        }
      } else {
        if (!initRet[key]) {
          initRet[key] = initArr[j]
        }
      }
    }
    return initRet
  }

  return parse(a, b)
}

let arr = [1, 2, [2, 3, [4]], 5, [7, 8, [10]], [null, 'o']]

let arrStr = '[a,h,[w,y],[b,z, g, y, [c], e], d, f,[t], [k,p,[o,[u]]]]'

console.log(dismantleArray(arr, arrStr))

DynamicPlanning

/**
 * 假设你是一个专业的劫匪，你计划去打劫一条街上的家舍，每家有一定数量的钱财，
 * 但相邻两家有一个彼此连接的安全系统，一旦相邻两家在同一晚被打劫，那么这个安全系统就会自动报警。
 *
 * 给你一个由非负整数组成的数组，用来代表每家的钱财，在不让安全系统自动报警的前提下，
 * 求你能打劫到的钱财的最大数量。
 *
 * 比如 [2, 0, 0, 4, 5]，能打劫到的最大钱财是7
 */
function getMax(nums) {
  if (nums.length === 0) {
    return 0
  }
  let maxMoney = nums[0]
  for (let i = 0; i < nums.length; i++) {
    nums[i] = Math.max(nums[i - 2] || 0, nums[i - 3] || 0) + nums[i]
    if (nums[i] > maxMoney) {
      maxMoney = nums[i]
    }
  }

  return maxMoney
}

function getMax1(arr) {
  let max = 0
  const length = arr.length
  for (let i = length - 1; i >= 0; i--) {
    const nextIndex = i + 2
    if (nextIndex > length - 1) continue
    if (nextIndex + 1 <= length - 1) {
      arr[i] =
        arr[i] + arr[nextIndex + 1] > arr[i] + arr[nextIndex] ? arr[i] + arr[nextIndex + 1] : arr[i] + arr[nextIndex]
    } else {
      arr[i] = arr[i] + arr[nextIndex]
    }
    if (arr[i] > max) {
      max = arr[i]
    }
  }
  return max
}

const arr1 = [2, 0, 0, 4, 5, 10, 12, 19]
console.log(getMax(arr1))
const arr2 = [2, 0, 0, 4, 5, 10, 12, 19]
console.log(getMax1(arr2))

Event

class Event {
  events = {}
  constructor(initEvents = {}) {
    this.events = initEvents
  }

  on(event, fn) {
    if (Array.isArray(event)) {
      for (let i = 0, l = event.length; i < l; i++) {
        this.on(event[i], fn)
      }
    } else {
      this.events[event] = (this.events[event] || []).concat(fn)
    }
    return this
  }

  emit(event) {
    let cbs = this.events[event]
    const args = Array.from(arguments).slice(1)
    if (cbs) {
      cbs.forEach(function (cb) {
        cb.apply(this, args)
      })
    }

    return this
  }

  off(event, fn) {
    if (Array.isArray(event)) {
      for (let i = 0, l = event.length; i < l; i++) {
        this.off(event[i], fn)
      }
    } else {
      let cbs = this.events[event]
      if (!fn) {
        this.events[event] = null
        return this
      }

      if (cbs) {
        this.events[event] = cbs.filter(cb => cb !== fn)
      }
    }

    return this
  }

  once(event, fn) {
    const on = () => {
      this.off(event, on)
      fn.apply(this, arguments)
    }

    this.on(event, on)

    return this
  }
}

const event = new Event()

const fn = () => {
  console.log('I click')
}

event.on('click', fn)

event.once('touch', function () {
  console.log('I touch')
})

event.emit('click')

event.off('click', fn)
event.emit('click')
event.emit('touch')
event.emit('touch')

export default Event

Format

//千分位格式化
const roundByFour = (num, digits) => {
  return parseFloat(num.toFixed(digits))
}

console.log(roundByFour(1000.12345678, 4))

Inherit

JsBridge

;(function () {
  const callbacks = {}

  // 如果使用iframe传值
  function renderIframe(url) {
    try {
      let iframeElem = document.createElement('iframe')
      iframeElem.setAttribute('src', url)
      iframeElem.setAttribute('style', 'display:none;')
      iframeElem.setAttribute('height', '0px')
      iframeElem.setAttribute('width', '0px')
      iframeElem.setAttribute('frameborder', '0')
      document.body.appendChild(iframeElem)
      setTimeout(() => {
        document.body.removeChild(iframeElem)
        iframeElem = null
      }, 300)
    } catch (e) {}
  }

  window.JSBridge = {
    dispatch(name, data) {
      const event = document.createEvent('Events')
      event.initEvent(name, false, true)
      event.data = data
      document.dispatchEvent(event)
    },

    invoke(bridgeName, data, callback) {
      const callbackId = `${name}_${Math.floor(Math.random() * new Date().getTime())}`
      callbacks[callbackId] = callback
      window.postBridgeMessage({
        bridgeName,
        data,
        callbackId
      })
    },

    receiveMessage(msg) {
      const { data, callbackId } = msg
      if (callbacks[callbackId]) {
        callbacks[callbackId](data)
        delete callbacks.callbackId
      }
    }
  }

  document.addEventListener('DOMContentLoaded', () => {
    window.JSBridge.dispatch('myJSBridgeReady')
  })
})()

LuckyDraw

/*
请实现抽奖函数rand，保证随机性
输入为表示对象数组，对象有属性n表示人名，w表示权重
随机返回一个中奖人名，中奖概率和w成正比
*/
const genPeoples = count => {
  let arr = []
  for (let i = 0; i < count; i++) {
    arr.push({ n: `p${i + 1}`, w: Math.floor(Math.random() * 5000000) })
  }

  return arr
}

const peoples = genPeoples(200)

// 方法1
const rand = function (p) {
  const ret = p.map(o => ({ ...o, score: o.w * Math.random() }))

  const max = Math.max(...ret.map(o => o.score))

  return ret.find(o => o.score === max).n
}

let startTime = +new Date()
console.log(rand(peoples))
console.log(+new Date() - startTime, 'rand1')

// 方法2
const rand2 = function (p) {
  const ret = p.reduce((arr, o) => {
    const multiple = Math.floor(o.w / 100)
    for (let i = 0; i < multiple; i++) {
      arr.push(o)
    }
    return arr
  }, [])

  const randomIdx = Math.floor(ret.length * Math.random())
  return ret[randomIdx]
}

let startTime1 = +new Date()
console.log(rand2(peoples).n)
console.log(+new Date() - startTime1, 'rand2')

Middleware

const ctx = {}

const next = async () => {}

const middleware = [
  async function A(ctx, next) {
    console.log(1)
    await next()
    console.log(6)
  },
  async function B(ctx, next) {
    console.log(2)
    await next()
    console.log(5)
  },
  async function C(ctx, next) {
    console.log(3)
    await next()
    console.log(4)
  }
]

// 推倒过程
// middleware.reduceRight((exec, fn, i) => {
//   if (i === 0) return fn(ctx, exec)
//   return () => fn(ctx, exec)
// }, next)

const compose = middleware => next => middleware.reduceRight((exec, fn) => ctx => fn(ctx, exec), next)

compose(middleware)(next)(ctx)

New

Num2ChineseNum

function num2ChineseNum(num, isAmount = false) {
  const strNum = num.toString()

  let integerPart
  let decimalPart

  let hasDecimal = strNum.indexOf('.') > -1

  if (hasDecimal) {
    integerPart = strNum.split('.')[0]
    decimalPart = strNum.split('.')[1]
  } else {
    integerPart = strNum
  }

  const length = integerPart.length

  const chineseNum = isAmount
    ? {
        0: '零',
        1: '壹',
        2: '贰',
        3: '叁',
        4: '肆',
        5: '伍',
        6: '陆',
        7: '柒',
        8: '捌',
        9: '玖'
      }
    : {
        0: '零',
        1: '一',
        2: '二',
        3: '三',
        4: '四',
        5: '五',
        6: '六',
        7: '七',
        8: '八',
        9: '九'
      }

  const chineseUnit = isAmount
    ? {
        0: isAmount ? '元' : '',
        1: '拾',
        2: '佰',
        3: '仟',
        4: '万',
        5: '十万',
        6: '佰万',
        7: '仟万',
        8: '亿',
        9: '拾亿',
        10: '佰亿',
        11: '仟亿',
        12: '兆',
        13: '拾兆',
        14: '佰兆',
        15: '仟兆',
        16: '京'
      }
    : {
        0: isAmount ? '元' : '',
        1: '拾',
        2: '佰',
        3: '仟',
        4: '万',
        5: '十万',
        6: '佰万',
        7: '仟万',
        8: '亿',
        9: '拾亿',
        10: '佰亿',
        11: '仟亿',
        12: '兆',
        13: '拾兆',
        14: '佰兆',
        15: '仟兆',
        16: '京'
      }

  const decimalChineseUnit = { 0: '角', 1: '分' }

  let returnValue = ''
  let decimalReturnValue = ''

  for (let i = 1; i <= length; i++) {
    let exponent = length - i

    const divisor = Math.pow(10, exponent)

    const result = Math.floor(num / divisor)

    const remainder = num % divisor

    if (result === 0) {
      if (!returnValue.endsWith('零')) {
        returnValue = returnValue + chineseNum[result]
      }
    } else {
      if (remainder > Math.pow(10, 12)) {
        returnValue = returnValue + chineseNum[result] + chineseUnit[exponent].replace(/兆/, '')
      } else if (remainder > Math.pow(10, 8)) {
        returnValue = returnValue + chineseNum[result] + chineseUnit[exponent].replace(/亿/, '')
      } else if (remainder > Math.pow(10, 4)) {
        returnValue = returnValue + chineseNum[result] + chineseUnit[exponent].replace(/万/, '')
      } else {
        returnValue = returnValue + chineseNum[result] + chineseUnit[exponent]
      }
    }

    num = remainder
  }

  if (hasDecimal) {
    for (let i = 0; i < decimalPart.length; i++) {
      decimalReturnValue += chineseNum[decimalPart[i]] + decimalChineseUnit[i]
    }
  }

  returnValue = returnValue.replace(/零$/, '元')

  if (isAmount) {
    if (hasDecimal) {
      return returnValue + decimalReturnValue
    } else {
      return returnValue + '整'
    }
  } else {
    if (hasDecimal) {
      return returnValue + '点' + decimalReturnValue
    } else {
      return returnValue + '整'
    }
  }
}

console.log(num2ChineseNum(5))
console.log(num2ChineseNum(5000))
console.log(num2ChineseNum(5001))
console.log(num2ChineseNum(5010))
console.log(num2ChineseNum(5100))
console.log(num2ChineseNum(12102))
console.log(num2ChineseNum(512102))
console.log(num2ChineseNum(3512102))
console.log(num2ChineseNum(63512102))
console.log(num2ChineseNum(21987963512102))

Promise

promise

class MyPromise {
  status = 'pending'
  result = undefined

  constructor(fn) {
    let callbacks = []
    const resolve = resolveVal => {
      try {
        if (this.status !== 'pending') return
        this.status = 'fulfilled'
        this.result = resolveVal
        if (callbacks.length > 0) {
          if (this.status !== 'pending') {
            const { resolveFn } = callbacks.splice(0, 1)[0]
            this.status = 'pending'
            resolveVal = resolveFn(resolveVal)
            this.status = 'fulfilled'
            this.result = resolveVal
            queueMicrotask(() => {
              this.status = 'pending'
              if (resolveVal instanceof MyPromise) {
                if (resolveVal.status === 'fulfilled') {
                  resolveVal.then(function (data) {
                    resolve(data)
                  })
                } else {
                  resolveVal.then(
                    data => {},
                    err => {
                      reject(err)
                    }
                  )
                }
              } else {
                resolve(resolveVal)
              }
            })
          }
        }
      } catch (err) {
        reject(err)
      }
    }

    const reject = rejectVal => {
      if (this.status !== 'pending') return
      this.status = 'rejected'
      this.result = rejectVal
      if (callbacks.length > 0) {
        if (this.status !== 'pending') {
          const { rejectFn } = callbacks.splice(0, 1)[0]
          this.status = 'pending'
          rejectVal = rejectFn(rejectVal)
          this.status = 'rejected'
          this.result = rejectVal
          queueMicrotask(() => {
            this.status = 'pending'
            if (rejectVal instanceof MyPromise) {
              if (rejectVal.status === 'rejected') {
                rejectVal.then(
                  data => {},
                  err => {
                    reject(err)
                  }
                )
              } else {
                rejectVal.then(
                  data => {
                    resolve(data)
                  },
                  err => {}
                )
              }
            } else {
              reject(rejectVal)
            }
          })
        }
      }
    }

    try {
      fn(resolve, reject)
    } catch (err) {
      reject(err)
    }

    this.then = (resolveFn, rejectFn) => {
      callbacks.push({ resolveFn, rejectFn })

      if (this.status !== 'pending') {
        queueMicrotask(() => {
          if (this.status === 'fulfilled') {
            this.status = 'pending'
            resolve(this.result)
          } else {
            this.status = 'pending'
            reject(this.result)
          }
        })
      }

      return this
    }

    this.catch = errFn => this.then(undefined, errFn)

    this.finally = finallyFn => {
      this.then(finallyFn, finallyFn)
    }
  }
}

MyPromise.resolve = function (val) {
  return new MyPromise(resolve => {
    resolve(val)
  })
}

MyPromise.reject = function (val) {
  return new MyPromise((resolve, reject) => {
    reject(val)
  })
}

new MyPromise((resolve, reject) => {
  setTimeout(() => {
    resolve(1)
    reject(2)
  }, 500)
})
  .then(
    data => {
      console.log(data, 'resolve')
      return new MyPromise((resolve, reject) => {
        reject(2)
      })
    },
    err => {
      console.log(err, 'reject')
      return 3
    }
  )
  .then(
    data => {
      console.log(data, 'resolve')
    },
    err => {
      console.log(err, 'reject')
    }
  )
  .catch(() => {
    console.log('err')
  })
  .finally(() => {
    console.log('finally')
  })

promiseAll

function promiseAll(arr) {
  let retVal = []
  if (arr && !arr.length) {
    console.warn('参数有问题')
  } else {
    return new Promise(resolve => {
      arr.forEach(promise => {
        if (!(promise instanceof Promise)) {
          promise = Promise.resolve(promise)
        }

        promise.then(data => {
          retVal.push(data)
          if (retVal.length === arr.length) {
            resolve(retVal)
          }
        })
      })
    })
  }
}

const promise1 = () => Promise.resolve(1)
const promise2 = () => Promise.resolve(2)
const promise3 = () => Promise.resolve(3)
const promise4 = () => Promise.resolve(4)
const promise5 = () => Promise.resolve(5)

Promise.all([promise1(), promise2(), promise3(), promise4(), promise5()]).then(data => {
  console.log(data)
})

promiseAll([promise1(), promise2(), promise3(), promise4(), promise5()]).then(data => {
  console.log(data)
})

promiseRace

function promiseRace(arr) {
  if (arr && !arr.length) {
    console.warn('参数有问题')
  } else {
    return new Promise(resolve => {
      arr.forEach(promise => {
        if (!(promise instanceof Promise)) {
          promise = Promise.resolve(promise)
        }

        promise.then(data => {
          resolve(data)
        })
      })
    })
  }
}

const promise1 = () =>
  new Promise(resolve => {
    setTimeout(resolve.bind(this, 1), 1000)
  })
const promise2 = () =>
  new Promise(resolve => {
    setTimeout(resolve.bind(this, 2), 3000)
  })
const promise3 = () =>
  new Promise(resolve => {
    setTimeout(resolve.bind(this, 3), 2000)
  })
const promise4 = () =>
  new Promise(resolve => {
    setTimeout(resolve.bind(this, 4), 5000)
  })
const promise5 = () =>
  new Promise(resolve => {
    setTimeout(resolve.bind(this, 5), 6000)
  })

Promise.race([promise1(), promise2(), promise3(), promise4(), promise5()]).then(data => {
  console.log(data)
})

promiseRace([promise1(), promise2(), promise3(), promise4(), promise5()]).then(data => {
  console.log(data)
})

ReadFiles

const path = require('path')
const glob = require('glob')
const fs = require('fs')

const readCss = function (pattern) {
  return new Promise(resolve => {
    glob(pattern, function (err, files) {
      const str = files.reduce((cssStr, file) => {
        return cssStr.concat(fs.readFileSync(path.resolve(file), 'utf8'))
      }, '')
      resolve(str)
    })
  })
}

readCss('less/**/*.{css,less,scss,sass}').then(cssStr => {
  console.log(cssStr)
})

Redux

redux

const createStore = (config = {}) => {
  let state = config.initialState || {}
  const reducers = config.reducers
  const listens = []

  return {
    dispatch(name, data) {
      if (reducers[name]) {
        state = reducers[name](state, data)
        listens.forEach(fn => {
          fn(state)
        })
      }
    },
    getState() {
      return state
    },
    subscribe(fn) {
      listens.push(fn)
    }
  }
}

const store = createStore({
  initialState: {
    a: 1
  },
  reducers: {
    change(state, data) {
      return { ...state, a: data }
    }
  }
})

store.subscribe(() => console.log(store.getState()))
store.dispatch('change', 2)

middleware

Regex

Request4Node

const https = require('https')

const hostname = ''

const request = (options, postData, headers = {}) =>
  new Promise(resolve => {
    if (options.method === 'get') {
      options.path = options.path + '?' + new URLSearchParams(postData).toString()
      postData = null
    } else {
      postData = JSON.stringify(postData)
      headers['Content-Type'] = 'application/json'
      headers['Content-Length'] = Buffer.byteLength(postData)
    }

    const req = https.request(
      {
        hostname,
        port: 443,
        ...options,
        headers: {
          ...headers
        }
      },
      res => {
        let result = ''

        res.setEncoding('utf8')

        res.on('data', chunk => {
          result += chunk
        })

        res.on('error', error => {
          console.error('res=', error)
        })

        res.on('end', () => {
          resolve(result)
        })
      }
    )

    req.on('error', error => {
      console.error('req=', error)
    })

    postData && req.write(postData)
    req.end()
  })

request({ method: 'get', path: '' }).then(data => {})

Sort

bubbleSort

function bubbleSort(arr) {
  let count = arr.length - 1
  while (count > 0) {
    for (let i = 0; i < count; i++) {
      if (arr[i] > arr[i + 1]) {
        let temp
        temp = arr[i]
        arr[i] = arr[i + 1]
        arr[i + 1] = temp
      }
    }
    count -= 1
  }
}

function bubbleSort2(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp
        temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
}

let arr = [2, 1, 3, 4, 5]

bubbleSort(arr)
console.log(arr)

quickSort

function quickSort(arr) {
  const count = arr.length
  const halfIdx = Math.floor(count / 2)
  let halfNo = arr[halfIdx]

  if (halfIdx < 1) {
    return arr
  } else {
    let temp1 = []
    let temp2 = []
    arr.splice(halfIdx, 1)
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] < halfNo) {
        temp1.push(arr[i])
      } else {
        temp2.push(arr[i])
      }
    }
    return [...quickSort(temp1), halfNo, ...quickSort(temp2)]
  }
}

let arr = [2, 1, 9, 10, 12, 11]
console.log(quickSort(arr))

Stack

// 栈：先进后出，后进先出
class Stack {
  items = []

  // 压栈
  push(item) {
    this.items.push(item)
  }

  // 出栈
  pop() {
    return this.items.pop()
  }

  // 查看栈顶元素
  peek() {
    return this.items[this.items.length - 1]
  }

  // 判断栈是否为空
  isEmpty() {
    return this.items.length === 0
  }

  // 获取栈中元素的个数
  size() {
    return this.items.length
  }

  // 以字符串形式输出栈内元素
  toString() {
    return this.items.reduce((str, item) => {
      return str.concat(item.toString())
    }, '')
  }
}

const stack = new Stack()

stack.push({ name: 'allen' })
console.log(stack.peek())
console.log(stack.size())
console.log(stack.isEmpty())
console.log(stack.toString())

Throttle

const throttle = (fn, delay) => {
  let startTime = 0
  return function () {
    const context = this

    const currentTime = +new Date()
    if (startTime === 0) {
      startTime = +new Date()
      fn.apply(context, arguments)
    } else {
      if (currentTime - startTime > delay) {
        startTime = +new Date()
        fn.apply(context, arguments)
      }
    }
  }
}

const fn = throttle(() => {
  console.log('show', +new Date() - startTime)
  return 1
}, 1000)

let startTime = +new Date()
setInterval(() => {
  console.log(fn())
}, 100)

Tree

expandTree

// 把一个树平铺
let tree = {
  id: 1001,
  parentId: 0,
  name: 'AA',
  children: [
    {
      id: 1002,
      parentId: 1001,
      name: 'BB',
      children: [
        { id: 1006, parentId: 1002, name: 'FF' },
        { id: 1007, parentId: 1002, name: 'GG' }
      ]
    },
    {
      id: 1003,
      parentId: 1001,
      name: 'CC',
      children: [
        {
          id: 1004,
          parentId: 1003,
          name: 'DD',
          children: [{ id: 1008, parentId: 1004, name: 'HH' }]
        },
        {
          id: 1005,
          parentId: 1003,
          name: 'EE',
          children: [{ id: 1009, parentId: 1005, name: 'II' }]
        }
      ]
    }
  ]
}

const expandTree = tree => {
  let result = []

  const expand = tree => {
    tree.forEach(({ children, ...rest }) => {
      result.push(rest)
      if (children) expand(children)
    })

    return result
  }

  return expand(tree)
}

console.log(JSON.stringify(expandTree([tree])))

findPath

// 已知数组list，写一个函数，要求输入eg，输出ac->ce->eg.
const list = [
  {
    id: 'ab',
    children: [
      {
        id: 'cd',
        children: [
          {
            id: 'ef',
            children: []
          }
        ]
      },
      {
        id: 'fg',
        children: []
      }
    ]
  },
  {
    id: 'ac',
    children: [
      {
        id: 'ce',
        children: [
          {
            id: 'eg',
            children: []
          }
        ]
      }
    ]
  }
]

const findPath = (list, key) => {
  let result = []

  const getPath = (list, pId = '') => {
    list.forEach(node => {
      let key = `${pId ? `${pId}->` : pId}${node.id}`
      result.push(key)
      getPath(node.children, key)
    })
  }

  getPath(list)

  console.log(result)

  return result.find(str => str.indexOf(key) > -1)
}

console.log(JSON.stringify(findPath(list, 'eg')))

genTree

/**
 * 把 var list = [
 { id: 1001, parentId: 0, name: "AA" },
 { id: 1002, parentId: 1001, name: "BB" },
 { id: 1003, parentId: 1001, name: "CC" },
 { id: 1004, parentId: 1003, name: "DD" },
 { id: 1005, parentId: 1003, name: "EE" },
 { id: 1006, parentId: 1002, name: "FF" },
 { id: 1007, parentId: 1002, name: "GG" },
 { id: 1008, parentId: 1004, name: "HH" },
 { id: 1009, parentId: 1005, name: "II" }
 ]
 转化为
 {
  id: 1001,
  parentId: 0,
  name: "AA",
  children: [
    {
      id: 1002,
      parentId: 1001,
      name: "BB",
      children: [
        { id: 1006, parentId: 1002, name: "FF" },
        { id: 1007, parentId: 1002, name: "GG" }
      ]
    },
    {
      id: 1003,
      parentId: 1001,
      name: "CC",
      children: [
        {
          id: 1004,
          parentId: 1003,
          name: "DD",
          children: [{ id: 1008, parentId: 1004, name: "HH" }]
        },
        {
          id: 1005,
          parentId: 1003,
          name: "EE",
          children: [{ id: 1009, parentId: 1005, name: "II" }]
        }
      ]
    }
  ]
}
 */

const list = [
  { id: 1001, parentId: 0, name: 'AA' },
  { id: 1002, parentId: 1001, name: 'BB' },
  { id: 1003, parentId: 1001, name: 'CC' },
  { id: 1004, parentId: 1003, name: 'DD' },
  { id: 1005, parentId: 1003, name: 'EE' },
  { id: 1006, parentId: 1002, name: 'FF' },
  { id: 1007, parentId: 1002, name: 'GG' },
  { id: 1008, parentId: 1004, name: 'HH' },
  { id: 1009, parentId: 1005, name: 'II' }
]

const genTree = (arr, parentId) => {
  return arr.reduce((tree, node) => {
    if (node.parentId === parentId) {
      if (parentId === 0) {
        return { ...node, children: genTree(arr, node.id) }
      }
      return tree.concat({ ...node, children: genTree(arr, node.id) })
    }
    return tree
  }, [])
}

console.log(JSON.stringify(genTree(list, 0)))

transform

// transform({
//   0: {
//     username: '0',
//     department: 'A-B-C', {path:'A'} {path:'A-B'} {path:'A-B-C'}
//   },
//   1: {
//     username: '1',
//     department: 'A-B-D', {path:'A'} {path:'A-B'} {path:'A-B-D'}
//   },
//   2: {
//     username: '2',
//     department: 'A-X-Y',
//   },
// })
// // 打印结果：
//   [
//   {
//     name: 'A',
//     path: 'A',
//     children: [
//       {
//         name: '0',
//         path: 'A-B',
//         children: [
//           { name: '0', path: 'A-B-C', children: [] },
//           { name: '1', path: 'A-B-D', children: [] },
//         ],
//       },
//       { name: '2', path: 'A-X', children: [{ name: '2', path: 'A-X-Y', children: [] }] },
//     ],
//   }
//   ]

const transform = data => {
  const expand = originData => {
    const expandData = []
    Object.values(originData).forEach(value => {
      const departmentList = value.department.split('-')

      departmentList.forEach((d, i) => {
        expandData.push({
          path: departmentList.slice(0, i + 1).join('-'),
          parentId: i > 0 ? departmentList.slice(0, i).join('-') : '',
          username: i
        })
      })
    })

    return expandData
  }

  const removeDuplicate = originData => {
    const retObj = originData.reduce((obj, item) => {
      return {
        ...obj,
        [item.path]: item
      }
    }, {})

    return Object.values(retObj)
  }

  const genTree = (originData, parentId = '') => {
    return originData.reduce((tree, node) => {
      if (node.parentId === parentId) {
        return tree.concat({ ...node, children: genTree(originData, node.path) })
      }
      return tree
    }, [])
  }

  return genTree(removeDuplicate(expand(data)))
}

const data = {
  0: {
    username: '0',
    department: 'A-B-C'
  },
  1: {
    username: '1',
    department: 'A-B-D'
  },
  2: {
    username: '2',
    department: 'A-X-Y'
  }
}

console.log(transform(data))

Websocket

import Events from '../event/index.mjs'

const md5 = str => {
  // todo
  return encodeURIComponent(str)
}

export const MSG_TYPE = {
  /*
   * 心跳
   * */
  HEARTBEAT_CHECK: 0,
  /*
   *  文本
   * */
  TEXT: 1,
  /*
   * 图片
   * */
  IMAGE: 2
}

export const SEND_MSG_TYPE = {
  /*
   * 心跳
   * */
  HEARTBEAT_CHECK: 1,
  /*
   * 回执
   * */
  ACK: 2
}

const HEARTBEAT_TIME = 30 * 1000

/*
 * 消息通道类
 * 接收报文
 * {
 *  "id":"消息id",
 *  "msgType": 1, 0--心跳  1--文本  2--图片url
 *  "content": "http://www.baidu.com" 内容 { "bizType":"","content":""}
 * }
 *
 * 发送报文
 * {
 *  "type":1   1-心跳 2-ack
 * }
 * 对外暴露 init reconnection sendMessage destroy方法
 * 对外暴露 open message error close 事件
 * e.g let instance =  MessageChannel.init({url:''}); instance.on('message',data=>{console.log(data)})
 * */

class MessageChannel extends Events {
  timer
  timer2
  count
  __ws__
  url
  static instanceMap = {}

  constructor(url, initEvents = {}) {
    super(initEvents)
    this.timer = null
    this.timer2 = null
    this.count = 0
    this.__ws__ = {}
    this.url = url
    this.connect()
    this.handleMessage()
    this.handleClose()
    this.handleError()
    this.handleBrowserEvent()
  }

  /*
   * 初始化消息通道，同一个websocket只创建一次实例
   * */
  static init({ url }) {
    const instanceId = md5(url)
    if (!MessageChannel.instanceMap[instanceId]) {
      MessageChannel.instanceMap[instanceId] = new MessageChannel(url)
    }
    return MessageChannel.instanceMap[instanceId]
  }

  /*
   * 重新连接
   * */
  reconnection() {
    let initEvents = {}
    const instanceId = md5(this.url)
    if (this.__ws__.readyState !== WebSocket.CONNECTING && this.__ws__.readyState !== WebSocket.OPEN) {
      this.closeWebSocket()
      if (MessageChannel.instanceMap[instanceId]) {
        initEvents = MessageChannel.instanceMap[instanceId].events
      }
      Object.assign(MessageChannel.instanceMap[instanceId], new MessageChannel(this.url, initEvents))
    }
  }

  /*
   * 发送消息
   * */
  sendMessage(message) {
    this.__ws__.send(JSON.stringify(message))
  }

  /*
   * 销毁消息通道
   * */
  destroy() {
    this.closeWebSocket()
    const instanceId = md5(this.url)
    delete MessageChannel.instanceMap[instanceId]
  }

  /*
   * 连接websocket
   * */
  connect() {
    if (window.WebSocket) {
      if (this.__ws__.readyState !== WebSocket.CONNECTING && this.__ws__.readyState !== WebSocket.OPEN) {
        this.__ws__ = new WebSocket(this.url)
        this.__ws__.addEventListener('open', e => {
          console.log('连接成功，ws=', e.target)
          this.emit('open', e)
          this.heartbeatStart()
        })
      }
    } else {
      console.log('浏览器不支持WebSocket')
      this.emit('error', new Error('浏览器不支持WebSocket'))
    }
  }

  /*
   * 接收websocket消息
   * */
  handleMessage() {
    this.__ws__.addEventListener('message', e => {
      const receiveMsg = JSON.parse(e.data)

      // 不是心跳才回执
      if (receiveMsg?.msgType !== MSG_TYPE.HEARTBEAT_CHECK) {
        this.emit('message', receiveMsg)

        // 发送回执报文
        const message = JSON.stringify({
          id: receiveMsg.id,
          type: SEND_MSG_TYPE.ACK
        })
        if (this.__ws__) {
          this.__ws__.send(message)
        }
      } else {
        this.heartbeatReset()
        this.heartbeatStart()
      }
    })
  }

  /*
   * 连接断开
   * */
  handleClose() {
    this.__ws__.addEventListener('close', e => {
      console.log('连接断开，ws=', e.target)
      this.emit('close', e)
    })
  }

  /*
   * 连接错误
   * */
  handleError() {
    this.__ws__.addEventListener('error', e => {
      console.log('连接错误，ws=', e)
      this.closeWebSocket()
      this.emit('error', e)
    })
  }

  /*
   * 监听浏览器事件
   * */
  handleBrowserEvent() {
    window.addEventListener('online', this.reconnection.bind(this))
  }

  /*
   * 心跳开始
   * */
  heartbeatStart() {
    this.timer = window.setTimeout(() => {
      if (this.__ws__.readyState === WebSocket.OPEN) {
        // 连接还在发心跳报文
        const msg = JSON.stringify({
          type: SEND_MSG_TYPE.HEARTBEAT_CHECK
        })
        this.__ws__.send(msg)

        // 心跳补偿，重试三次心跳未应答关闭连接
        this.timer2 = window.setInterval(() => {
          if (this.count < 3) {
            this.count = this.count + 1
            this.__ws__.send(msg)
          } else {
            this.timer2 && clearInterval(this.timer2)
            this.closeWebSocket()
          }
        }, HEARTBEAT_TIME)
      } else {
        // 连接失败时 关闭websocket
        this.closeWebSocket()
      }
    }, HEARTBEAT_TIME)
  }

  /*
   * 心跳重置
   * */
  heartbeatReset() {
    this.count = 0
    this.timer2 && clearInterval(this.timer2)
  }

  /*
   * 关闭webSocket
   * */
  closeWebSocket() {
    this.__ws__.close()
    this.timer && clearTimeout(this.timer)
  }
}

export default MessageChannel