前言

最近做一個(gè)矩陣圖編輯器需求，其實(shí)就是一個(gè)表格編輯器。
主要要求

表頭支持多層級(jí)行列合并，抽象出來也就是多棵樹組成的表頭
表體行單元格隨表頭葉子節(jié)點(diǎn)的變化去做diff聯(lián)動(dòng)

其他業(yè)務(wù)就不細(xì)述了。

具體UI

先看UI圖效果

初始狀態(tài).png

增加、刪除單元格.png

最后樣子.png

從圖中可以看出單元格是通過 + - icon不斷去增加刪除的，有增加同級(jí)的、下級(jí)的，這樣就類似一棵樹了，而且樹可以有多棵。

下面的圖可能更加清晰，有1、2、3 三棵樹。

例子.png

那么第一個(gè)問題來了，在不斷增加單元格的過程中，怎么去保持每棵樹的行、列同步呢？，比如1單元格在不斷增加子單元格的時(shí)候，1這個(gè)單元格要實(shí)現(xiàn)列合并，同時(shí)2這個(gè)單元格也要不斷實(shí)現(xiàn)行合并。

要解決這個(gè)問題，需要分步驟：
第一步：按行去一行行渲染單元格
第二步：計(jì)算哪些單元格需要行合并、哪些單元格需要列合并

那么第一步，我們定義一個(gè)最簡單的樹的數(shù)據(jù)結(jié)構(gòu)為：

type IdType = string

interface TreeItem {
  id: IdType;
  name: string; // 名稱
  level: number; // 層級(jí)
  children: TreeItem[]
}

其中l(wèi)evel 層級(jí)用來記錄該節(jié)點(diǎn)處于樹的第幾層，而這也是用來確定該節(jié)點(diǎn)在第幾行渲染，level從0開始，根節(jié)點(diǎn)1是0。1-1、1-2的level是1；而1-1-1,1-1-2的level是2如此。我們需要寫一個(gè)方法把樹轉(zhuǎn)成二維數(shù)組，然后通過循環(huán)二維數(shù)組去渲染單元格:,期待的二維數(shù)組的結(jié)構(gòu)如下，注意這里用二維數(shù)組也有一個(gè)取巧的地方，那就是數(shù)組arr的index 與 level相對(duì)應(yīng)

arr = [
  [{id, name: 1, level: 0}, {id, name: 2: level: 0}],
  [{id, name: 1-1, level: 1}, {id, name: 1-2: level: 1}]
  [{id, name: 1-1-1, level: 2}, {id, name: 1-1-2, level: 2}]
]

寫一個(gè)轉(zhuǎn)換方法

// 樹轉(zhuǎn)換層級(jí)數(shù)組
  function generateLevelArray(treeData: TreeItem[]) {
    const arr = [];
    treeForEach(treeData, (item) => {
      if (!Array.isArray(arr[item.level])) {
        arr[item.level] = [];
      }
      arr[item.level].push(item);
    });
    return arr;
  }

這里的treeForEach是一個(gè)深度遍歷樹節(jié)點(diǎn)的方法。遍歷樹的方法有深度優(yōu)先遍歷與廣度優(yōu)先遍歷。這里用深度的原因是廣度優(yōu)先遍歷過程中無法傳遞當(dāng)前節(jié)點(diǎn)的parent；而深度優(yōu)先遍歷是通過遞歸方式，可以傳遞parent，省心省力完成后面的一些特色需求，所以一般沒啥特殊要求的話還是深度優(yōu)先遍歷比較好。

// 是否有子節(jié)點(diǎn)，一般用來判斷是否是葉子節(jié)點(diǎn)
export function hasChildren(item: TreeItem): boolean {
  return Array.isArray(item.children) && item.children.length > 0;
}

// 深度遍歷樹執(zhí)行回調(diào)函數(shù)
export function treeForEach(tree: TreeItem[], cb: Function, parent?: TreeItem): void {
  const isFunction = typeof cb === 'function';
  if (!isFunction) return;
  tree.forEach((item, index) => {
    const hasChild = hasChildren(item);
    cb(item, index, parent);
    if (hasChild) {
      treeForEach(item.children, cb, item);
    }
  });
}

通過樹轉(zhuǎn)換成數(shù)組方法，我們遍歷二維數(shù)組就能生成下面的表格,（先忽略“工作內(nèi)容”這個(gè)單元格）

樹轉(zhuǎn)換成數(shù)組.png

這與我們的實(shí)際需求相差甚遠(yuǎn)：

例子.png

所以我們上面說的第二個(gè)步驟要實(shí)現(xiàn)。

再次通過觀察實(shí)際效果，我們可以發(fā)現(xiàn)1單元格的列合并數(shù)量，其實(shí)等于它下面的葉子節(jié)點(diǎn)數(shù)量（沒有后代的節(jié)點(diǎn)是葉子節(jié)點(diǎn)），注意這里說的是葉子節(jié)點(diǎn)，不是兒子節(jié)點(diǎn)。1單元格下面的葉子節(jié)點(diǎn)是1-1-1、1-1-2、1-2 。由此得出列合并的規(guī)律就是：

單元格不是葉子節(jié)點(diǎn)，因?yàn)槿~子節(jié)點(diǎn)不需要合并
找出該單元格下面的葉子節(jié)點(diǎn)數(shù)量

那么行合并怎么算呢？比如2單元格是要三行合并成一行。通過觀察1-2、2這兩個(gè)單元格，我們也可以得到行合并數(shù)量的規(guī)律：

單元格必須為葉子節(jié)點(diǎn)，且它所在的level不是最大的層級(jí)level
找到該單元格的層級(jí)level與最大level的差距，即等于二維數(shù)組的長度減去當(dāng)前的層級(jí)： arr.length - currentLevel

由此我們可以得到一個(gè)表頭二維數(shù)組的computed

const columnTree: Ref<TreeItem[]> = ref([]);

const tableHeadData = computed(() => {
    const levelArray = generateLevelArray(columnTree.value);
    const tableHeadData: Array<Array<TableHeadCell>> = [];
    const maxLevel = levelArray.length - 1; // 最大層級(jí)

    levelArray.forEach((level) => {
      const row: Array<TableHeadCell> = [];
      level.forEach((treeItem: TreeItem) => {
        if (hasChildren(treeItem)) {
          // 非葉子節(jié)點(diǎn)列合并
          const item: TableHeadCell = {
            id: treeItem.id,
            name: treeItem.name,
            level: treeItem.level,
            colspan: getLeafNumber([treeItem]),
          }
          row.push(item);
        } else if (treeItem.level !== maxLevel) {
          // 非末端葉子節(jié)點(diǎn)需要行合并
          const rowspan = maxLevel - treeItem.level + 1;
          const item: TableHeadCell = {
            id: treeItem.id,
            name: treeItem.name,
            level: treeItem.level,
            rowspan,
          }
          row.push(item);
        } else {
          // 末端葉子節(jié)點(diǎn) 啥也不干
          const item: TableHeadCell = {
            id: treeItem.id,
            name: treeItem.name,
            level: treeItem.level,
          }
          row.push(item);
        }
      });
      tableHeadData.push(row);
    });
    const firstCell: TableHeadCell = { id: FIRST_CELL_ID, name: '工作內(nèi)容', rowspan: maxLevel + 1, level: 0 };
    if (tableHeadData[0]) {
      tableHeadData[0].unshift(firstCell);
    } else {
      tableHeadData[0] = [firstCell]
    }
    return tableHeadData;
  })

// 獲取葉子節(jié)點(diǎn)數(shù)量來實(shí)現(xiàn)列合并
export function getLeafNumber(tree: TreeItem[]): number {
  let num = 0;
  treeForEach(tree, (item: TreeItem) => {
    if (!hasChildren(item)) {
      num++;
    }
  });
  return num;
}

這樣子就實(shí)現(xiàn)我們的行合并、列合并的效果。

例子.png

咋一看好像沒啥問題，但是實(shí)際上卻有嚴(yán)重的性能問題！問題就出在getLeafNumber這里，這個(gè)方法是獲取節(jié)點(diǎn)下面有幾個(gè)葉子節(jié)點(diǎn)的。單獨(dú)算一個(gè)節(jié)點(diǎn)的下面的葉子節(jié)點(diǎn)數(shù)量是完全沒有問題的，但是如果你遍歷一棵樹的過程中，每個(gè)節(jié)點(diǎn)都去算其下有幾個(gè)葉子節(jié)點(diǎn)，這實(shí)際上是存在巨大的重復(fù)工作的，比如1節(jié)點(diǎn)的葉子數(shù)量應(yīng)該等于1-1、1-2兩者的葉子節(jié)點(diǎn)之和，而不是1節(jié)點(diǎn)算一遍、1-1、1-2自己又算一遍。

遍歷一顆樹，分別計(jì)算每個(gè)節(jié)點(diǎn)下面有幾個(gè)葉子節(jié)點(diǎn)，最好的時(shí)間復(fù)雜度應(yīng)該是O(n),怎么實(shí)現(xiàn)呢？
這里還是用到了遞歸方式，上面也說了每個(gè)節(jié)點(diǎn)的葉子節(jié)點(diǎn)數(shù)量等于它下面的兒子的葉子節(jié)點(diǎn)數(shù)量之和，直到該節(jié)點(diǎn)是葉子節(jié)點(diǎn)才退出遞歸。

// 記錄每個(gè)節(jié)點(diǎn)下面有幾個(gè)葉子節(jié)點(diǎn)
export function getLeafNumber(tree: TreeItem) {
  function deep(node: TreeItem) {
    if (!hasChildren(node)) {
      return 1 // 葉子節(jié)點(diǎn)直接返回本身1個(gè)數(shù)量
    }
    // 否則有children 去計(jì)算其下的children的葉子數(shù)量之和
    let num = 0;
    node.children.forEach(item => {
      num += deep(item);
    })
    return num;
  }
  return deep(tree);
}

參照基本邏輯實(shí)現(xiàn)了一版，仔細(xì)看這里還是有重復(fù)計(jì)算的問題，缺失了計(jì)算結(jié)果緩存，所以我們需要一個(gè)map來緩存計(jì)算過的節(jié)點(diǎn)結(jié)果，優(yōu)化版：

// 記錄每個(gè)節(jié)點(diǎn)下面有幾個(gè)葉子節(jié)點(diǎn)
export function getLeafNumberMap(tree: TreeItem): NodeLeafNumberMap {
  const nodeLeafNumberMap: NodeLeafNumberMap = Object.create(null);

  function deep(node: TreeItem) {
    if (!hasChildren(node)) {
      nodeLeafNumberMap[node.id] = 1;
      return nodeLeafNumberMap[node.id];
    }
    // 有children 有l(wèi)eaf
    if (Object.hasOwn(nodeLeafNumberMap, node.id)) return nodeLeafNumberMap[node.id];
    // 有children 沒leaf
    let num = 0;
    node.children.forEach(item => {
      num += deep(item);
    })
    nodeLeafNumberMap[node.id] = num;
    return num;
  }
  deep(tree);
  return nodeLeafNumberMap;
}

有了nodeLeafNumberMap知道每個(gè)節(jié)點(diǎn)的葉子數(shù)量那就好辦了，上面的表頭二維數(shù)組的computed可以改成下面優(yōu)化版，去掉getLeafNumber方法，改成 leafNumberMap[treeItem.id]

  const tableHeadData = computed(() => {
    const leafNumberMapList = columnTree.value.map(tree => getLeafNumberMap(tree));
    const leafNumberMap = leafNumberMapList.reduce((prevMap, currentMap) => ({ ...prevMap, ...currentMap }), Object.create(null))

    const levelArray = generateLevelArray(columnTree.value);
    const tableHeadData: Array<Array<TableHeadCell>> = [];
    const maxLevel = levelArray.length - 1; // 最大層級(jí)

    levelArray.forEach((level) => {
      const row: Array<TableHeadCell> = [];
      level.forEach((treeItem: TreeItem) => {
        if (hasChildren(treeItem)) {
          // 非葉子節(jié)點(diǎn)列合并
          const item: TableHeadCell = {
            id: treeItem.id,
            name: treeItem.name,
            level: treeItem.level,
            colspan: leafNumberMap[treeItem.id],
          }
          row.push(item);
        } else if (treeItem.level !== maxLevel) {
          // 非末端葉子節(jié)點(diǎn)需要行合并
          const rowspan = maxLevel - treeItem.level + 1;
          const item: TableHeadCell = {
            id: treeItem.id,
            name: treeItem.name,
            level: treeItem.level,
            rowspan,
          }
          row.push(item);
        } else {
          // 末端葉子節(jié)點(diǎn) 啥也不干
          const item: TableHeadCell = {
            id: treeItem.id,
            name: treeItem.name,
            level: treeItem.level,
          }
          row.push(item);
        }
      });
      tableHeadData.push(row);
    });
    const firstCell: TableHeadCell = { id: FIRST_CELL_ID, name: '工作內(nèi)容', rowspan: maxLevel + 1, level: 0 };
    if (tableHeadData[0]) {
      tableHeadData[0].unshift(firstCell);
    } else {
      tableHeadData[0] = [firstCell]
    }
    return tableHeadData;
  })

表格導(dǎo)出到excel

另外一個(gè)需求就是支持導(dǎo)出到excel, 我采用 exceljs 這個(gè)庫來導(dǎo)出。我覺得這是整個(gè)表格編輯器最難的地方，難點(diǎn)就是要拿到表頭的單元格行列位置信息與合并信息。其中導(dǎo)出的單元格位置信息數(shù)據(jù)結(jié)構(gòu)為

// sheet表格中單元格位置信息
export type SheetCellPosition = {
  c: number; // 列位置
  r: number // 行位置
  cs: number // 列合并數(shù)
  rs: number // 行合并數(shù)
}

其中每個(gè)單元格的 r \ rs \ cs 信息都可以輕松拿到，r = node.level; rs = node.rowspan; cs = node.colspan, 上面的二維數(shù)組都有，唯獨(dú)這個(gè)列信息c 沒有；這個(gè)列位置信息不是二維數(shù)組的每個(gè)單元格的index坐標(biāo)信息，而是要包含列合并后的位置信息，總結(jié)就是
當(dāng)前單元格的c = 同行的前一個(gè)單元格的c + cs

看到這里有人可能會(huì)想：既然這樣子那還不簡單？對(duì)二維數(shù)組的每一行進(jìn)行遍歷，根據(jù)上面的公式不就能知道每個(gè)單元格的c信息了嗎？

確實(shí)我一開始也是這么做的，導(dǎo)出后發(fā)現(xiàn)有些單元格就不符合預(yù)期了，原因是第一行的單元格可以這么做得到單元格的對(duì)應(yīng)信息沒問題，回到上面的例子中

例子.png

二維數(shù)組簡略后應(yīng)該是這樣子：

[
  [{name: '1'}, {name: '2'}, {name: 3}],
  [{name: '1-1'}, {name: '1-2'},{name: '3-1'}, {name: '3-2'}],
  [{name: '1-1-1'}, {name: '1-1-2'}],
]

從第二行開始，仔細(xì)觀察，你會(huì)發(fā)現(xiàn) ‘3-1’ 的c信息并不能依靠同行前面的'1-2'的c信息和cs得到，因?yàn)閺膱D中可以看到它們之間還隔著一個(gè)“2”單元格的距離，所以不能簡單遍歷二維數(shù)組就能得到每個(gè)單元格的列位置信息也就是c信息。

那要怎么才能得到呢？

能不能記錄不同行的信息也就是上面的“2”單元格的信息，用到的時(shí)候再加上？可以這么想，但是中間可能不僅僅是“2”一個(gè)單元格，實(shí)際導(dǎo)出過程中存在可能隔著好幾個(gè)單元格都有的情況，而且隔著的這些單元格可能分別分布在不同的行里面！這么一想就感覺太復(fù)雜了，難度系數(shù)劇增!

現(xiàn)在我們整理一下思路，要知道當(dāng)前單元格的列位置信息c，需要知道：

同行的前面的位置信息c + cs
類似“2”單元格這種不同行的一個(gè)或者多個(gè)單元格信息

而第2點(diǎn)很難計(jì)算出來，那么有沒有代替方法呢？

終于經(jīng)過一段時(shí)間的摸索之后我發(fā)現(xiàn)其實(shí)要知道“3-1”的位置不用第2點(diǎn)也行，我們只要知道“3”單元格這個(gè)位置信息就行了！因?yàn)榈?點(diǎn)的信息太難計(jì)算，無論它隔著幾個(gè)單元格，“3”單元格這個(gè)信息我們是可以輕易得到的，因?yàn)椤?”，“3-1”在同一顆樹上且是父子節(jié)點(diǎn)！

那么我們就可以通過遍歷樹的方式，而且計(jì)算公式還是：
當(dāng)前單元格的c = 同層的前一個(gè)單元格的c + cs
不過要注意，當(dāng) “當(dāng)前單元格” 是同層的第一個(gè)節(jié)點(diǎn)的時(shí)候，它的列位置信息其實(shí) === 父節(jié)點(diǎn)的列位置信息！

這樣子就能通過深度遍歷樹得到所有單元格的正確的列位置信息了！

而且恰好第一個(gè)子節(jié)點(diǎn)的信息依賴父節(jié)點(diǎn)的信息，一次遍歷即可計(jì)算出所有的節(jié)點(diǎn)信息，這就是我前面說的深度優(yōu)先遍歷算法省心省力完成的特色需求！

想通了就好辦了，代碼如下：

// 設(shè)置每個(gè)單元格的colIndex
function setCellColIndex(treeData: TreeItem[], positionMap: SheetCellPositionMap): SheetCellPositionMap {

  // 獲取單元格的列位置
  function getCellColIndex(list: TreeItem[], itemIndex: number, parentColIndex: number = 0): number {
    let currentIndex = itemIndex - 1
    let currentItem: TreeItem
    let currentItemPosition: SheetCellPosition
    let c = parentColIndex;
    while (currentIndex >= 0) {
      currentItem = list[currentIndex];
      currentItemPosition = positionMap[currentItem.id]
      if (currentItemPosition.c !== 0) {
        return currentItemPosition.c + currentItemPosition.cs
      } else {
        c = c + currentItemPosition.cs
      }
      currentIndex--;
    }
    return c;
  }

  treeForEach(treeData, (item, index, parent) => {
    if (!parent) {
      // 沒有parent就是根節(jié)點(diǎn)
      positionMap[item.id].c = getCellColIndex(treeData, index)
    } else {
      // 非第一行數(shù)據(jù)，先找parent.c再找自身的index和累計(jì)的cs
      const parentColIndex = positionMap[parent.id].c;
      // 第一個(gè)子節(jié)點(diǎn)就要基于父節(jié)點(diǎn)的colIndex來加，后面的子節(jié)點(diǎn)就直接拿前面兄弟節(jié)點(diǎn)的colIndex + cs
      positionMap[item.id].c =  getCellColIndex(parent.children, index, parentColIndex);
    }
  })

  return positionMap;
}

其中的positionMap 是一個(gè)記錄了每個(gè)節(jié)點(diǎn)的 c 、r、 rs、 cs信息的map如：

positionMap = {
 'id1': {
    c: 0,
    cs: 2,
    r: 2,
    rs: 3
  },
'id2': {
    c: 0,
    cs: 3,
    r: 1,
    rs: 2
  }
}

通過上面的setCellColIndex方法就能補(bǔ)全positionMap 的每個(gè)節(jié)點(diǎn)的c信息。同時(shí)我們注意到同層節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)的結(jié)果依賴前一個(gè)節(jié)點(diǎn)的結(jié)果，這其實(shí)有點(diǎn)類似我另外一篇文章斐波那契數(shù)列解法有感: 遞歸+緩存 or 動(dòng)態(tài)規(guī)劃里面提到的場景。而在這里我其實(shí)用到的是“遞歸+緩存”的思想，而不是動(dòng)態(tài)規(guī)劃，因?yàn)檫@里是要計(jì)算所有節(jié)點(diǎn)的信息，動(dòng)態(tài)規(guī)劃只適于求某個(gè)節(jié)點(diǎn)的信息，動(dòng)態(tài)規(guī)劃在這里就不是最優(yōu)解了。

最后

感謝你仔細(xì)的閱讀，希望你可以從中獲得一些感悟與共鳴，以上如有不對(duì)，不煩指出，不勝感激。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

聊一聊多層級(jí)樹形表頭用到的那些算法思想

聊一聊多層級(jí)樹形表頭用到的那些算法思想

前言

具體UI

表格導(dǎo)出到excel

最后

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

聊一聊多層級(jí)樹形表頭用到的那些算法思想

前言

具體UI

表格導(dǎo)出到excel

最后

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av