Skip to content
blog.takenoko.dev
Blog

【TypeScript】フラットなデータ構造をdepthによってネストしたデータ構造にする

はじめに

ネストしたデータ構造をフラットなデータにする記事は検索すれば、たくさん出てきます。
しかし、フラットなデータをネストしたデータに変換するような記事はなかなか見当たりません。
今回はどのようにしてコードで実現するのかを、TypeScriptを使って考えてみようと思います。

成果物

https://github.com/kntks/blog-code/tree/main/2023/03/generate-nested-array

入力と求める出力

入力は深さと、名前を持ったオブジェクトの配列です。

入力データのルールは、

  • 親は子よりも配列のインデックスが小さい
  • 必ず木構造になる
[
  { "depth": 2, name: "A" },
  { "depth": 3, name: "AA" },
  { "depth": 2, name: "B" },
  { "depth": 3, name: "BB" },
  { "depth": 4, name: "BBB" },
  { "depth": 2, name: "C" }
]

イメージ図は以下の通りです。

graph TB
    A-->AA
    B-->BB
    BB-->BBB
    C

求める結果は以下の通りです。

[
  {
    {"depth": 2, name: "A" },
    [
       { "depth": 3, name: "AA" }
    ]
  },
  {
    { "depth": 2, name: "B" },
    [
      { "depth": 3, name: "BB" },
      [
        { "depth": 4, name: "BBB" },
      ]
    ]
  }
  { "depth": 2, name: "C" }
]

結論

type Depth = {
  depth: number;
};


type NestedDepth = Depth | NestedDepth[];


function generateNestedArray(arr: Depth[]): NestedDepth[] {
  type DepthWithVisited = Depth & { visited: boolean };


  const recursive = (arr: DepthWithVisited[], depth: number): NestedDepth[] => {
    const results: NestedDepth[] = [];
    for (let index = 0; index < arr.length; index++) {
      const current = arr[index];
      if (current.visited) continue;
      if (current.depth < depth) break;
      if (current.depth === depth) {
        const { depth } = current;
        results.push({ depth });
        current.visited = true;
      }
      if (current.depth > depth)
        results.push(recursive(arr.slice(index), depth + 1));
    }
    return results;
  };


  return recursive(
    arr.map((x) => ({ ...x, visited: false })),
    2
  );
}

playground

実装

はじめにtypeを定義します。

TypeScript 3.7以降からRecursive Typeが使えるので、これを利用します。

type Depth = {
  depth: number;
};


type NestedDepth = Depth | NestedDepth[];

参考：

generateNestedArrayの中を見てみる

実装のアイデアは深さ優先探索と同じです。
引数に渡された配列を上から順に見ていき、訪問済みかどうかを確認します。

function generateNestedArray(arr: Depth[]): NestedDepth[] {
  type DepthWithVisited = Depth & { visited: boolean };


  // 第2引数のdepthは、関数実行中の基準となる深さになります。
  const recursive = (arr: DepthWithVisited[], depth: number): NestedDepth[] => {
    const results: NestedDepth[] = [];
    for (let index = 0; index < arr.length; index++) {
      const current = arr[index];


      // すでに訪問済みであるならば、配列を次に進める。
      if (current.visited) continue;


      // currrentの深さが、基準となる深さよりも小さい場合
      // ループを終了して、結果を返す = 再帰関数を終了する = currentは兄弟でも、子でもない
      if (current.depth < depth) break;


      // currentの深さが、基準となる深さと同じである場合、配列にpush
      // 訪問済みにする
      if (current.depth === depth) {
        const { depth } = current;
        results.push({ depth });
        current.visited = true;
      }


      // currentの深さが、基準となる深さよりも大きい場合、基準となる深さよりもまだ、子供がいることがわかる。
      if (current.depth > depth)
        results.push(recursive(arr.slice(index), depth + 1));
    }
    return results;
  };


  return recursive(
    // 引数のデータに訪問フラグを追加して、再帰関数をスタートする
    arr.map((x) => ({ ...x, visited: false })),
    2
  );
}

テストを書いて動作確認してみる

実装が完了したので、実際にテストを書いて挙動が正しいか確認します。

main.test.ts
import { generateNestedArray } from "../main";
describe("", () => {
  test.each([
    {
      name: "子のデータが1つネストしている",
      headings: [{ depth: 2 }, { depth: 3 }],
      expected: [{ depth: 2 }, [{ depth: 3 }]],
    },
    {
      name: "孫に当たるデータは、子のデータにネストする",
      headings: [{ depth: 2 }, { depth: 3 }, { depth: 4 }],
      expected: [{ depth: 2 }, [{ depth: 3 }, [{ depth: 4 }]]],
    },
    {
      name: "depthがすべて同じである場合、データはネストしない",
      headings: [{ depth: 2 }, { depth: 2 }, { depth: 2 }],
      expected: [{ depth: 2 }, { depth: 2 }, { depth: 2 }],
    },
    {
      name: "子が2つある場合、ネストした配列に2つ入る",
      headings: [{ depth: 2 }, { depth: 3 }, { depth: 3 }],
      expected: [{ depth: 2 }, [{ depth: 3 }, { depth: 3 }]],
    },
  ])("$name", ({ headings, expected }) => {
    expect(generateNestedArray(headings)).toEqual(expected);
  });
});

どうやら意図した挙動になっていそうです！

Terminal window
$ npm test


> generate-nested-array@1.0.0 test
> jest --coverage --passWithNoTests


 PASS  src/__tests__/main.test.ts
    ✓ 子のデータが1つネストしている (1 ms)
    ✓ 孫に当たるデータは、子のデータにネストする
    ✓ depthがすべて同じである場合、データはネストしない (1 ms)
    ✓ 子が2つある場合、ネストした配列に2つ入る


----------|---------|----------|---------|---------|-------------------
File      | % Stmts | % Branch | % Funcs | % Lines | Uncovered Line #s
----------|---------|----------|---------|---------|-------------------
All files |     100 |      100 |     100 |     100 |
 main.ts  |     100 |      100 |     100 |     100 |
----------|---------|----------|---------|---------|-------------------
Test Suites: 1 passed, 1 total
Tests:       4 passed, 4 total
Snapshots:   0 total
Time:        0.26 s

最後に

再帰関数を使うことで、ネストしたデータを作成できることがわかりました。しかし、挙動を把握するためにはしっかりコードを読む必要があります。個人的な意見ですが、もしforで実現できるのならば、再帰関数よりもfor文を選択した方が良いです。

参考になれば幸いです。

Tags: