// 实现 call
Function.prototype.myCall = function (context, ...args) {
  // 1. 处理 context 为 null/undefined 的情况
  context = context || globalThis

  // 2. 创建唯一属性名，避免覆盖原有属性
  const fnSymbol = Symbol("fn")

  // 3. 将函数挂载到 context 上
  context[fnSymbol] = this

  // 4. 执行函数
  const result = context[fnSymbol](...args)

  // 5. 删除临时属性
  delete context[fnSymbol]

  return result
}

// 实现 apply
Function.prototype.myApply = function (context, args = []) {
  context = context || globalThis
  const fnSymbol = Symbol("fn")
  context[fnSymbol] = this
  const result = context[fnSymbol](...args)
  delete context[fnSymbol]
  return result
}

// 实现 bind
Function.prototype.myBind = function (context, ...bindArgs) {
  const fn = this

  return function (...args) {
    // 合并 bind 时和调用时的参数
    return fn.apply(context, [...bindArgs, ...args])
  }
}

// 测试
function greet(greeting, punctuation) {
  return `${greeting}, ${this.name}${punctuation}`
}

const person = { name: "Alice" }
console.log(greet.myCall(person, "Hello", "!")) // Hello, Alice!
console.log(greet.myApply(person, ["Hi", "?"])) // Hi, Alice?
const boundGreet = greet.myBind(person, "Hey")
console.log(boundGreet("!!!")) // Hey, Alice!!!

function myNew(constructor, ...args) {
  // 1. 创建空对象，继承构造函数的 prototype
  const obj = Object.create(constructor.prototype)

  // 2. 执行构造函数，绑定 this 为新对象
  const result = constructor.apply(obj, args)

  // 3. 如果构造函数返回对象，则返回该对象；否则返回新对象
  return result !== null &&
    (typeof result === "object" || typeof result === "function")
    ? result
    : obj
}

// 测试
function Person(name, age) {
  this.name = name
  this.age = age
}

Person.prototype.sayHello = function () {
  return `Hello, I'm ${this.name}`
}

const person = myNew(Person, "Alice", 25)
console.log(person.name) // Alice
console.log(person.sayHello()) // Hello, I'm Alice

function myInstanceof(obj, constructor) {
  // 基本类型直接返回 false
  if (obj === null || typeof obj !== "object") {
    return false
  }

  // 获取对象的原型
  let proto = Object.getPrototypeOf(obj)

  // 沿原型链查找
  while (proto !== null) {
    if (proto === constructor.prototype) {
      return true
    }
    proto = Object.getPrototypeOf(proto)
  }

  return false
}

// 测试
console.log(myInstanceof([], Array)) // true
console.log(myInstanceof([], Object)) // true
console.log(myInstanceof({}, Array)) // false
console.log(myInstanceof(function () {}, Function)) // true

function deepClone(obj, map = new WeakMap()) {
  // 处理 null 或基本类型
  if (obj === null || typeof obj !== "object") {
    return obj
  }

  // 处理日期
  if (obj instanceof Date) {
    return new Date(obj.getTime())
  }

  // 处理正则
  if (obj instanceof RegExp) {
    return new RegExp(obj.source, obj.flags)
  }

  // 处理 Map
  if (obj instanceof Map) {
    const cloneMap = new Map()
    obj.forEach((value, key) => {
      cloneMap.set(key, deepClone(value, map))
    })
    return cloneMap
  }

  // 处理 Set
  if (obj instanceof Set) {
    const cloneSet = new Set()
    obj.forEach((value) => {
      cloneSet.add(deepClone(value, map))
    })
    return cloneSet
  }

  // 处理循环引用
  if (map.has(obj)) {
    return map.get(obj)
  }

  // 创建新对象/数组
  const clone = Array.isArray(obj) ? [] : {}

  // 缓存，处理循环引用
  map.set(obj, clone)

  // 递归拷贝
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      clone[key] = deepClone(obj[key], map)
    }
  }

  return clone
}

// 测试
const obj = {
  a: 1,
  b: { c: 2, d: [3, 4] },
  e: new Date(),
  f: /abc/g,
  g: new Map([["key", "value"]]),
}
obj.circular = obj // 循环引用

const cloned = deepClone(obj)
console.log(cloned)
console.log(cloned.b === obj.b) // false
console.log(cloned.circular === cloned) // true

function debounce(fn, delay, immediate = false) {
  let timer = null

  return function (...args) {
    const context = this

    // 清除之前的定时器
    if (timer) clearTimeout(timer)

    if (immediate) {
      // 立即执行版本
      const callNow = !timer
      timer = setTimeout(() => {
        timer = null
      }, delay)
      if (callNow) fn.apply(context, args)
    } else {
      // 延迟执行版本
      timer = setTimeout(() => {
        fn.apply(context, args)
      }, delay)
    }
  }
}

// 测试
const handleSearch = debounce((query) => {
  console.log("搜索:", query)
}, 300)

// 频繁调用，只会在停止输入 300ms 后执行一次
input.addEventListener("input", (e) => {
  handleSearch(e.target.value)
})

// 时间戳版本（立即执行）
function throttle(fn, limit) {
  let lastTime = 0

  return function (...args) {
    const now = Date.now()

    if (now - lastTime >= limit) {
      lastTime = now
      fn.apply(this, args)
    }
  }
}

// 定时器版本（延迟执行）
function throttleTimer(fn, limit) {
  let timer = null

  return function (...args) {
    if (!timer) {
      timer = setTimeout(() => {
        timer = null
        fn.apply(this, args)
      }, limit)
    }
  }
}

// 测试
const handleScroll = throttle(() => {
  console.log("滚动位置:", window.scrollY)
}, 200)

window.addEventListener("scroll", handleScroll)

function curry(fn) {
  return function curried(...args) {
    // 如果参数足够，直接执行
    if (args.length >= fn.length) {
      return fn.apply(this, args)
    } else {
      // 参数不够，返回新函数继续收集参数
      return function (...nextArgs) {
        return curried.apply(this, [...args, ...nextArgs])
      }
    }
  }
}

// 测试
function add(a, b, c) {
  return a + b + c
}

const curriedAdd = curry(add)
console.log(curriedAdd(1)(2)(3)) // 6
console.log(curriedAdd(1, 2)(3)) // 6
console.log(curriedAdd(1)(2, 3)) // 6
console.log(curriedAdd(1, 2, 3)) // 6

class EventEmitter {
  constructor() {
    this.events = {}
  }

  // 订阅事件
  on(event, listener) {
    if (!this.events[event]) {
      this.events[event] = []
    }
    this.events[event].push(listener)

    // 返回取消订阅函数
    return () => this.off(event, listener)
  }

  // 订阅一次
  once(event, listener) {
    const onceWrapper = (...args) => {
      listener(...args)
      this.off(event, onceWrapper)
    }
    return this.on(event, onceWrapper)
  }

  // 取消订阅
  off(event, listener) {
    if (!this.events[event]) return

    this.events[event] = this.events[event].filter((l) => l !== listener)

    // 清理空数组
    if (this.events[event].length === 0) {
      delete this.events[event]
    }
  }

  // 发布事件
  emit(event, ...args) {
    if (!this.events[event]) return

    this.events[event].forEach((listener) => {
      listener(...args)
    })
  }

  // 移除所有监听
  removeAllListeners(event) {
    if (event) {
      delete this.events[event]
    } else {
      this.events = {}
    }
  }
}

// 测试
const emitter = new EventEmitter()

const unsubscribe = emitter.on("message", (data) => {
  console.log("收到消息:", data)
})

emitter.emit("message", "Hello") // 收到消息: Hello
unsubscribe()
emitter.emit("message", "World") // 无输出

function promiseAll(promises) {
  return new Promise((resolve, reject) => {
    // 处理非数组输入
    if (!Array.isArray(promises)) {
      return reject(new TypeError("Argument must be an array"))
    }

    const results = []
    let completedCount = 0
    const total = promises.length

    // 处理空数组
    if (total === 0) {
      return resolve([])
    }

    promises.forEach((promise, index) => {
      // 将非 Promise 值包装为 Promise
      Promise.resolve(promise)
        .then((result) => {
          results[index] = result
          completedCount++

          // 所有 Promise 完成
          if (completedCount === total) {
            resolve(results)
          }
        })
        .catch(reject) // 任一 Promise 失败，立即 reject
    })
  })
}

// 测试
const p1 = Promise.resolve(1)
const p2 = new Promise((resolve) => setTimeout(() => resolve(2), 100))
const p3 = 3 // 非 Promise 值

promiseAll([p1, p2, p3]).then((results) => {
  console.log(results) // [1, 2, 3]
})

function promiseRace(promises) {
  return new Promise((resolve, reject) => {
    if (!Array.isArray(promises)) {
      return reject(new TypeError("Argument must be an array"))
    }

    promises.forEach((promise) => {
      Promise.resolve(promise).then(resolve, reject)
    })
  })
}

// 测试
const p1 = new Promise((resolve) => setTimeout(() => resolve("p1"), 500))
const p2 = new Promise((resolve) => setTimeout(() => resolve("p2"), 300))

promiseRace([p1, p2]).then((result) => {
  console.log(result) // p2（先完成）
})

function promiseAllSettled(promises) {
  return new Promise((resolve) => {
    if (!Array.isArray(promises)) {
      return resolve([])
    }

    const results = []
    let completedCount = 0
    const total = promises.length

    if (total === 0) {
      return resolve([])
    }

    promises.forEach((promise, index) => {
      Promise.resolve(promise)
        .then((value) => {
          results[index] = { status: "fulfilled", value }
        })
        .catch((reason) => {
          results[index] = { status: "rejected", reason }
        })
        .finally(() => {
          completedCount++
          if (completedCount === total) {
            resolve(results)
          }
        })
    })
  })
}

// 测试
const promises = [
  Promise.resolve("success"),
  Promise.reject("error"),
  Promise.resolve("another success"),
]

promiseAllSettled(promises).then((results) => {
  console.log(results)
  // [
  //   { status: 'fulfilled', value: 'success' },
  //   { status: 'rejected', reason: 'error' },
  //   { status: 'fulfilled', value: 'another success' }
  // ]
})

class MyPromise {
  constructor(executor) {
    this.state = "pending" // pending, fulfilled, rejected
    this.value = undefined
    this.reason = undefined
    this.onFulfilledCallbacks = []
    this.onRejectedCallbacks = []

    const resolve = (value) => {
      if (this.state === "pending") {
        this.state = "fulfilled"
        this.value = value
        this.onFulfilledCallbacks.forEach((fn) => fn())
      }
    }

    const reject = (reason) => {
      if (this.state === "pending") {
        this.state = "rejected"
        this.reason = reason
        this.onRejectedCallbacks.forEach((fn) => fn())
      }
    }

    try {
      executor(resolve, reject)
    } catch (error) {
      reject(error)
    }
  }

  then(onFulfilled, onRejected) {
    onFulfilled =
      typeof onFulfilled === "function" ? onFulfilled : (value) => value
    onRejected =
      typeof onRejected === "function"
        ? onRejected
        : (reason) => {
            throw reason
          }

    const promise2 = new MyPromise((resolve, reject) => {
      if (this.state === "fulfilled") {
        setTimeout(() => {
          try {
            const x = onFulfilled(this.value)
            resolvePromise(promise2, x, resolve, reject)
          } catch (error) {
            reject(error)
          }
        }, 0)
      }

      if (this.state === "rejected") {
        setTimeout(() => {
          try {
            const x = onRejected(this.reason)
            resolvePromise(promise2, x, resolve, reject)
          } catch (error) {
            reject(error)
          }
        }, 0)
      }

      if (this.state === "pending") {
        this.onFulfilledCallbacks.push(() => {
          setTimeout(() => {
            try {
              const x = onFulfilled(this.value)
              resolvePromise(promise2, x, resolve, reject)
            } catch (error) {
              reject(error)
            }
          }, 0)
        })

        this.onRejectedCallbacks.push(() => {
          setTimeout(() => {
            try {
              const x = onRejected(this.reason)
              resolvePromise(promise2, x, resolve, reject)
            } catch (error) {
              reject(error)
            }
          }, 0)
        })
      }
    })

    return promise2
  }
}

// 处理 then 返回值
function resolvePromise(promise2, x, resolve, reject) {
  if (promise2 === x) {
    return reject(new TypeError("Chaining cycle detected"))
  }

  if (x !== null && (typeof x === "object" || typeof x === "function")) {
    try {
      const then = x.then
      if (typeof then === "function") {
        then.call(
          x,
          (y) => resolvePromise(promise2, y, resolve, reject),
          reject
        )
      } else {
        resolve(x)
      }
    } catch (error) {
      reject(error)
    }
  } else {
    resolve(x)
  }
}

function sleep(ms) {
  return new Promise((resolve) => setTimeout(resolve, ms))
}

// 使用
async function demo() {
  console.log("开始")
  await sleep(1000)
  console.log("1秒后")
}

class AsyncPool {
  constructor(concurrency) {
    this.concurrency = concurrency
    this.running = 0
    this.queue = []
  }

  add(fn) {
    return new Promise((resolve, reject) => {
      this.queue.push({ fn, resolve, reject })
      this.run()
    })
  }

  run() {
    while (this.running < this.concurrency && this.queue.length) {
      const { fn, resolve, reject } = this.queue.shift()
      this.running++

      fn()
        .then(resolve, reject)
        .finally(() => {
          this.running--
          this.run()
        })
    }
  }
}

// 使用
const pool = new AsyncPool(3) // 最多3个并发

const urls = ["url1", "url2", "url3", "url4", "url5"]

urls.forEach((url) => {
  pool.add(() => fetch(url))
})

// 递归版本
function flat(arr, depth = 1) {
  if (depth === 0) return arr

  return arr.reduce((result, item) => {
    if (Array.isArray(item)) {
      return result.concat(flat(item, depth - 1))
    }
    return result.concat(item)
  }, [])
}

// 迭代版本（栈）
function flatIterative(arr, depth = 1) {
  const stack = arr.map((item) => ({ item, depth }))
  const result = []

  while (stack.length) {
    const { item, depth } = stack.pop()

    if (Array.isArray(item) && depth > 0) {
      stack.push(...item.map((i) => ({ item: i, depth: depth - 1 })))
    } else {
      result.push(item)
    }
  }

  return result.reverse()
}

// 测试
const arr = [1, [2, [3, [4]]]]
console.log(flat(arr, 2)) // [1, 2, 3, [4]]
console.log(flatIterative(arr, Infinity)) // [1, 2, 3, 4]

// Set 版本（最简单）
function unique(arr) {
  return [...new Set(arr)]
}

// filter 版本
function uniqueFilter(arr) {
  return arr.filter((item, index) => arr.indexOf(item) === index)
}

// reduce 版本
function uniqueReduce(arr) {
  return arr.reduce((result, item) => {
    if (!result.includes(item)) {
      result.push(item)
    }
    return result
  }, [])
}

// 对象去重（根据某个 key）
function uniqueBy(arr, key) {
  const seen = new Set()
  return arr.filter((item) => {
    const val = item[key]
    if (seen.has(val)) return false
    seen.add(val)
    return true
  })
}

// 测试
console.log(unique([1, 2, 2, 3, 3, 3])) // [1, 2, 3]

// 实现 map
Array.prototype.myMap = function (callback, thisArg) {
  if (typeof callback !== "function") {
    throw new TypeError(callback + " is not a function")
  }

  const result = []
  for (let i = 0; i < this.length; i++) {
    if (i in this) {
      result[i] = callback.call(thisArg, this[i], i, this)
    }
  }
  return result
}

// 实现 filter
Array.prototype.myFilter = function (callback, thisArg) {
  if (typeof callback !== "function") {
    throw new TypeError(callback + " is not a function")
  }

  const result = []
  for (let i = 0; i < this.length; i++) {
    if (i in this && callback.call(thisArg, this[i], i, this)) {
      result.push(this[i])
    }
  }
  return result
}

// 实现 reduce
Array.prototype.myReduce = function (callback, initialValue) {
  if (typeof callback !== "function") {
    throw new TypeError(callback + " is not a function")
  }

  let accumulator = initialValue
  let startIndex = 0

  // 如果没有初始值，使用数组第一个元素
  if (arguments.length < 2) {
    if (this.length === 0) {
      throw new TypeError("Reduce of empty array with no initial value")
    }
    accumulator = this[0]
    startIndex = 1
  }

  for (let i = startIndex; i < this.length; i++) {
    if (i in this) {
      accumulator = callback(accumulator, this[i], i, this)
    }
  }

  return accumulator
}

// 测试
const arr = [1, 2, 3, 4]
console.log(arr.myMap((x) => x * 2)) // [2, 4, 6, 8]
console.log(arr.myFilter((x) => x > 2)) // [3, 4]
console.log(arr.myReduce((sum, x) => sum + x, 0)) // 10

function myCreate(proto, propertiesObject) {
  if (typeof proto !== "object" && typeof proto !== "function") {
    throw new TypeError("Object prototype may only be an Object or null")
  }

  // 创建空函数
  function F() {}
  F.prototype = proto

  // 创建新对象
  const obj = new F()

  // 定义额外属性
  if (propertiesObject !== undefined) {
    Object.defineProperties(obj, propertiesObject)
  }

  return obj
}

// 测试
const person = {
  greet() {
    return "Hello!"
  },
}

const student = myCreate(person, {
  name: {
    value: "Alice",
    writable: true,
    enumerable: true,
    configurable: true,
  },
})

console.log(student.name) // Alice
console.log(student.greet()) // Hello!
console.log(Object.getPrototypeOf(student) === person) // true

function myAssign(target, ...sources) {
  if (target === null || target === undefined) {
    throw new TypeError("Cannot convert undefined or null to object")
  }

  const result = Object(target)

  sources.forEach((source) => {
    if (source !== null && source !== undefined) {
      for (const key in source) {
        if (source.hasOwnProperty(key)) {
          result[key] = source[key]
        }
      }
    }
  })

  return result
}

// 测试
const target = { a: 1 }
const source1 = { b: 2 }
const source2 = { c: 3, a: 4 }

console.log(myAssign(target, source1, source2)) // { a: 4, b: 2, c: 3 }

// 从右到左执行
function compose(...fns) {
  return function (value) {
    return fns.reduceRight((acc, fn) => fn(acc), value)
  }
}

// 从左到右执行（pipe）
function pipe(...fns) {
  return function (value) {
    return fns.reduce((acc, fn) => fn(acc), value)
  }
}

// 测试
const add5 = (x) => x + 5
const multiply2 = (x) => x * 2
const toString = (x) => String(x)

const composed = compose(toString, multiply2, add5)
console.log(composed(3)) // "16" (3 + 5 = 8, 8 * 2 = 16, "16")

const piped = pipe(add5, multiply2, toString)
console.log(piped(3)) // "16"

function memoize(fn, resolver) {
  const cache = new Map()

  return function (...args) {
    // 使用自定义 key 生成器或 JSON.stringify
    const key = resolver ? resolver(...args) : JSON.stringify(args)

    if (cache.has(key)) {
      return cache.get(key)
    }

    const result = fn.apply(this, args)
    cache.set(key, result)

    return result
  }
}

// 测试
const fibonacci = memoize(function (n) {
  if (n < 2) return n
  return fibonacci(n - 1) + fibonacci(n - 2)
})

console.log(fibonacci(40)) // 快速计算，无重复计算

function $(selector) {
  return document.querySelectorAll(selector)
}

// 链式操作版本
class DOMWrapper {
  constructor(elements) {
    this.elements = Array.isArray(elements) ? elements : [elements]
  }

  // 添加类名
  addClass(className) {
    this.elements.forEach((el) => el.classList.add(className))
    return this
  }

  // 移除类名
  removeClass(className) {
    this.elements.forEach((el) => el.classList.remove(className))
    return this
  }

  // 设置文本
  text(content) {
    if (content === undefined) {
      return this.elements[0]?.textContent
    }
    this.elements.forEach((el) => (el.textContent = content))
    return this
  }

  // 设置 HTML
  html(content) {
    if (content === undefined) {
      return this.elements[0]?.innerHTML
    }
    this.elements.forEach((el) => (el.innerHTML = content))
    return this
  }

  // 绑定事件
  on(event, handler) {
    this.elements.forEach((el) => el.addEventListener(event, handler))
    return this
  }

  // 设置样式
  css(property, value) {
    if (typeof property === "object") {
      Object.assign(this.elements[0].style, property)
    } else {
      this.elements[0].style[property] = value
    }
    return this
  }
}

function $(selector) {
  const elements = document.querySelectorAll(selector)
  return new DOMWrapper(Array.from(elements))
}

// 使用
$(".box")
  .addClass("active")
  .text("Hello")
  .css("color", "red")
  .on("click", () => console.log("clicked"))

function delegate(parent, eventType, selector, handler) {
  parent.addEventListener(eventType, function (event) {
    // 获取实际触发事件的元素
    const target = event.target

    // 查找匹配的委托元素
    const delegateTarget = target.closest(selector)

    // 如果找到且是父元素的子元素，执行处理器
    if (delegateTarget && parent.contains(delegateTarget)) {
      handler.call(delegateTarget, event, delegateTarget)
    }
  })
}

// 使用
delegate(
  document.querySelector(".list"),
  "click",
  ".item",
  function (event, el) {
    console.log("点击了:", el.textContent)
  }
)

// HTML 结构
// <ul class="list">
//   <li class="item">Item 1</li>
//   <li class="item">Item 2</li>
// </ul>

function makeDraggable(element) {
  let isDragging = false
  let startX, startY, initialLeft, initialTop

  element.addEventListener("mousedown", function (e) {
    isDragging = true
    startX = e.clientX
    startY = e.clientY
    initialLeft = element.offsetLeft
    initialTop = element.offsetTop
    element.style.cursor = "grabbing"
  })

  document.addEventListener("mousemove", function (e) {
    if (!isDragging) return

    const dx = e.clientX - startX
    const dy = e.clientY - startY

    element.style.left = `${initialLeft + dx}px`
    element.style.top = `${initialTop + dy}px`
  })

  document.addEventListener("mouseup", function () {
    isDragging = false
    element.style.cursor = "grab"
  })
}

// 使用
const box = document.querySelector(".draggable")
box.style.position = "absolute"
box.style.cursor = "grab"
makeDraggable(box)

// 递归版本
function quickSort(arr) {
  if (arr.length <= 1) return arr

  const pivot = arr[Math.floor(arr.length / 2)]
  const left = arr.filter((x) => x < pivot)
  const middle = arr.filter((x) => x === pivot)
  const right = arr.filter((x) => x > pivot)

  return [...quickSort(left), ...middle, ...quickSort(right)]
}

// 原地排序版本（节省空间）
function quickSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return

  const pivotIndex = partition(arr, left, right)
  quickSortInPlace(arr, left, pivotIndex - 1)
  quickSortInPlace(arr, pivotIndex + 1, right)

  return arr
}

function partition(arr, left, right) {
  const pivot = arr[right]
  let i = left

  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      ;[arr[i], arr[j]] = [arr[j], arr[i]]
      i++
    }
  }

  ;[arr[i], arr[right]] = [arr[right], arr[i]]
  return i
}

// 测试
console.log(quickSort([3, 6, 8, 10, 1, 2, 1])) // [1, 1, 2, 3, 6, 8, 10]

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.cache = new Map() // Map 保持插入顺序
  }

  get(key) {
    if (!this.cache.has(key)) return -1

    // 获取值，并移到最新位置
    const value = this.cache.get(key)
    this.cache.delete(key)
    this.cache.set(key, value)

    return value
  }

  put(key, value) {
    // 如果已存在，先删除
    if (this.cache.has(key)) {
      this.cache.delete(key)
    }

    // 如果超出容量，删除最旧的
    if (this.cache.size >= this.capacity) {
      const oldestKey = this.cache.keys().next().value
      this.cache.delete(oldestKey)
    }

    this.cache.set(key, value)
  }
}

// 测试
const cache = new LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
console.log(cache.get(1)) // 1
cache.put(3, 3) // 移除 key 2
console.log(cache.get(2)) // -1

// 二叉树节点
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

// 前序遍历（根-左-右）
function preorder(root) {
  if (!root) return []
  return [root.val, ...preorder(root.left), ...preorder(root.right)]
}

// 中序遍历（左-根-右）
function inorder(root) {
  if (!root) return []
  return [...inorder(root.left), root.val, ...inorder(root.right)]
}

// 后序遍历（左-右-根）
function postorder(root) {
  if (!root) return []
  return [...postorder(root.left), ...postorder(root.right), root.val]
}

// 层序遍历（BFS）
function levelOrder(root) {
  if (!root) return []

  const result = []
  const queue = [root]

  while (queue.length) {
    const levelSize = queue.length
    const currentLevel = []

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()
      currentLevel.push(node.val)

      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }

    result.push(currentLevel)
  }

  return result
}

// 测试
const tree = new TreeNode(
  1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3, new TreeNode(6), new TreeNode(7))
)

console.log("前序:", preorder(tree)) // [1, 2, 4, 5, 3, 6, 7]
console.log("中序:", inorder(tree)) // [4, 2, 5, 1, 6, 3, 7]
console.log("后序:", postorder(tree)) // [4, 5, 2, 6, 7, 3, 1]
console.log("层序:", levelOrder(tree)) // [[1], [2, 3], [4, 5, 6, 7]]

// 依赖收集器
class Dep {
  constructor() {
    this.subscribers = new Set()
  }

  depend() {
    if (activeEffect) {
      this.subscribers.add(activeEffect)
    }
  }

  notify() {
    this.subscribers.forEach((effect) => effect())
  }
}

let activeEffect = null

function watchEffect(effect) {
  activeEffect = effect
  effect()
  activeEffect = null
}

// 响应式对象
function reactive(obj) {
  const deps = new Map()

  return new Proxy(obj, {
    get(target, key) {
      if (!deps.has(key)) {
        deps.set(key, new Dep())
      }
      deps.get(key).depend()
      return target[key]
    },
    set(target, key, value) {
      target[key] = value
      if (deps.has(key)) {
        deps.get(key).notify()
      }
      return true
    },
  })
}

// 测试
const state = reactive({ count: 0 })

watchEffect(() => {
  console.log("count:", state.count)
})

state.count++ // 自动触发更新

function createStore(reducer, initialState) {
  let state = initialState
  const listeners = []

  function getState() {
    return state
  }

  function dispatch(action) {
    state = reducer(state, action)
    listeners.forEach((listener) => listener())
    return action
  }

  function subscribe(listener) {
    listeners.push(listener)
    return function unsubscribe() {
      const index = listeners.indexOf(listener)
      listeners.splice(index, 1)
    }
  }

  // 初始化 state
  dispatch({ type: "@@redux/INIT" })

  return { getState, dispatch, subscribe }
}

// 测试
function counterReducer(state = 0, action) {
  switch (action.type) {
    case "INCREMENT":
      return state + 1
    case "DECREMENT":
      return state - 1
    default:
      return state
  }
}

const store = createStore(counterReducer)

store.subscribe(() => {
  console.log("当前状态:", store.getState())
})

store.dispatch({ type: "INCREMENT" }) // 当前状态: 1
store.dispatch({ type: "INCREMENT" }) // 当前状态: 2

// 创建虚拟节点
function h(tag, props = {}, children = []) {
  return { tag, props, children }
}

// 渲染虚拟 DOM 为真实 DOM
function render(vnode) {
  if (typeof vnode === "string") {
    return document.createTextNode(vnode)
  }

  const el = document.createElement(vnode.tag)

  // 设置属性
  for (const [key, value] of Object.entries(vnode.props)) {
    el.setAttribute(key, value)
  }

  // 递归渲染子节点
  vnode.children.forEach((child) => {
    el.appendChild(render(child))
  })

  return el
}

// Diff 算法（简化版）
function diff(oldVNode, newVNode) {
  // 1. 新节点不存在，删除
  if (!newVNode) {
    return { type: "REMOVE" }
  }

  // 2. 旧节点不存在，新增
  if (!oldVNode) {
    return { type: "CREATE", newVNode }
  }

  // 3. 文本节点变化
  if (typeof oldVNode === "string" || typeof newVNode === "string") {
    if (oldVNode !== newVNode) {
      return { type: "REPLACE", newVNode }
    }
    return { type: "NONE" }
  }

  // 4. 标签不同，替换
  if (oldVNode.tag !== newVNode.tag) {
    return { type: "REPLACE", newVNode }
  }

  // 5. 同标签，比较属性和子节点
  const patches = []

  // 比较属性
  const propsDiff = diffProps(oldVNode.props, newVNode.props)
  if (propsDiff.length > 0) {
    patches.push({ type: "PROPS", props: propsDiff })
  }

  // 比较子节点
  const childrenDiff = diffChildren(oldVNode.children, newVNode.children)
  if (childrenDiff.length > 0) {
    patches.push({ type: "CHILDREN", children: childrenDiff })
  }

  return patches
}

function diffProps(oldProps, newProps) {
  const patches = []

  // 新增或修改的属性
  for (const [key, value] of Object.entries(newProps)) {
    if (oldProps[key] !== value) {
      patches.push({ type: "SET_PROP", key, value })
    }
  }

  // 删除的属性
  for (const key of Object.keys(oldProps)) {
    if (!(key in newProps)) {
      patches.push({ type: "REMOVE_PROP", key })
    }
  }

  return patches
}

function diffChildren(oldChildren, newChildren) {
  const patches = []
  const maxLength = Math.max(oldChildren.length, newChildren.length)

  for (let i = 0; i < maxLength; i++) {
    patches.push(diff(oldChildren[i], newChildren[i]))
  }

  return patches
}

// 测试
const oldTree = h("div", { id: "app" }, [h("p", {}, ["Hello"])])

const newTree = h("div", { id: "app", class: "container" }, [
  h("p", {}, ["World"]),
  h("span", {}, ["New"]),
])

console.log(diff(oldTree, newTree))