export const arr = [
  {
    id: 2,
    name: '部门B',
    parentId: 0
  },
  {
    id: 3,
    name: '部门C',
    parentId: 1
  },
  {
    id: 1,
    name: '部门A',
    parentId: 2
  },
  {
    id: 4,
    name: '部门D',
    parentId: 1
  },
  {
    id: 5,
    name: '部门E',
    parentId: 2
  },
  {
    id: 6,
    name: '部门F',
    parentId: 3
  },
  {
    id: 7,
    name: '部门G',
    parentId: 2
  },
  {
    id: 8,
    name: '部门H',
    parentId: 4
  }
]

type Item = typeof arr[number]
type ItemTree = Item & { children: ItemTree[] }

const normalItem = (item: Item | ItemTree): ItemTree => {
  if ('children' in item && Array.isArray(item.children)) {
    return item
  } else {
    return { ...item, children: [] }
  }
}

const toTrees = (items: Item[]) => {
  const map = new Map<number, ItemTree>()
  for (const item of items) {
    map.set(item.id, normalItem(item))
  }

  const roots: ItemTree[] = []
  const rootTreeAddNode = (itemTree: ItemTree) => {
    const parent = map.get(itemTree.parentId)
    if (parent) {
      parent.children.push(itemTree)
    } else {
      roots.push(itemTree)
    }
    return !parent
  }
  for (const itemTree of map.values()) {
    rootTreeAddNode(itemTree)
  }

  return {
    roots,
    addItem(item: Item) {
      if (map.has(item.id)) {
        return
      }
      const itemTree = normalItem(item)
      map.set(item.id, itemTree)
      if (rootTreeAddNode(itemTree)) {
        const oldRoots = roots.slice()
        roots.length = 0
        oldRoots.forEach(rootTreeAddNode)
      }
    },
    delItem(item: Item) {
      const itemTree = map.get(item.id)
      if (!itemTree) {
        return
      }
      const sameTrees = map.get(itemTree.parentId)?.children || roots
      const index = sameTrees.indexOf(itemTree)
      if (index !== -1) {
        sameTrees.splice(index, 1)
      }
    }
  }
}
