TS/JSでレベルを持つオブジェクトの一次元配列をネストされた配列に変換する

連休中のヤクの毛刈りを共有したいと思います。

要件

TypeScriptで、一次元配列をネストされた配列に変換するというのをやってました。
level要素を持つオブジェクトの配列を、そのレベルに従って入れ子式にした状態にする処理です。

日本語だとちょっと何言ってるかわからないですね。
以下のfromをtoに変換するということです。

const from = [
  { level: 0, name: "a" },
  { level: 1, name: "b" },
  { level: 1, name: "c" },
  { level: 0, name: "d" },
  { level: 1, name: "e" },
  { level: 0, name: "f" },
  { level: 1, name: "g" },
  { level: 2, name: "h" },
  { level: 2, name: "i" },
  { level: 0, name: "j" },
];
const target = [
  {
    level: 0,
    name: "a",
    children: [
      { level: 1, name: "b", children: [] },
      { level: 1, name: "c", children: [] },
    ],
  },
  {
    level: 0,
    name: "d",
    children: [
      { level: 1, name: "e", children: [] },
    ],
  },
  {
    level: 0,
    name: "f",
    children: [
      {
        level: 1,
        name: "g",
        children: [
          { level: 2, name: "h", children: [] },
          { level: 2, name: "i", children: [] },
        ],
      },
    ],
  },
  { level: 0, name: "j", children: [] },
];

レベルが上がると、直前の要素のchildrenに入ります。
「親は直前のもの」みたいな制約を考えてしまったので、一旦レベルごとに分割するというのもうまくできず…。

"javascript flat array to nested array" "javascript make array nested"とかでググってもそれっぽい記事が出てこなかったため難儀しました。

以下に自分なりの実装を載せますが、配列処理に自信のある方は、いったんここで記事を閉じて自分でコードを書き、比較してみると面白いかもしれません。

↓

↓

↓

↓

↓

↓

実装

こちらはDeno環境でのTypeScriptによる実装です。型関連の記述を外せばJavaScriptでも動くはずです^[1]。

import { assertEquals } from "https://deno.land/std@0.102.0/testing/asserts.ts";

const from = [ /* 省略 */ ];
const target = [ /* 省略 */ ];

interface Item {
  level: number;
  // deno-lint-ignore no-explicit-any
  [key: string]: any;
  children?: Item[];
}

const levelArray = (arr: Item[]): Item[] => {
  const out = [];
  for (let i = 0; i < arr.length; i++) {
    const { level } = arr[i];

    const rest = arr.slice(i + 1);
    const end = rest.findIndex((item) => item.level <= level);
    const extracted = end < 0 ? rest : rest.slice(0, end);

    const children = levelArray(extracted);
    out.push({ ...arr[i], children });

    i += extracted.length;
  }
  return out;
};

const flatLevelArray = (arr: Item[]): Item[] => {
  const out: Item[] = [];
  arr.forEach((item) => {
    const extractedChildren = flatLevelArray(item.children || []);
    delete item.children;
    out.push(item);
    extractedChildren.forEach((child) => out.push(child));
  });
  return out;
};

assertEquals(levelArray(from), to);
assertEquals(flatLevelArray(levelArray(from)), from);

console.log("works fine!");

前述の処理を行う関数levelArrayと、その逆関数flatLevelArrayです。
お察しの通り、再帰関数となります。

levelArray

ループ中でインデックスを多くすすめる必要があるため単純なforループを使用しています。

各行に解説をつけるとこのようになります。

const levelArray = (arr: Item[]): Item[] => {
  const out = [];
  for (let i = 0; i < arr.length; i++) {
    const { level } = arr[i];

    // 自分より後のすべての要素
    const rest = arr.slice(i + 1);

    // 自分より後で、自分と同世代か先祖側（levelの値が同じか小さい）の要素のインデックス
    // 見つからない（配列の残りがすべて子孫）なら-1
    const end = rest.findIndex((item) => item.level <= level);

    // 自分の子孫となる部分配列
    // 上のendが負なら残りがすべて子孫ということなのでrestをそのまま返す
    // そうでなければsliceして部分配列を返す
    const extracted = end < 0 ? rest : rest.slice(0, end);

    // 部分配列を再帰的に階層化
    const children = levelArray(extracted);

    // 階層化されたすべての子孫を自分の子として登録
    out.push({ ...arr[i], children });

    // 子孫の数だけインデックスをすすめる
    i += extracted.length;
  }
  return out;
};

配列fromの構造を見ながら各行の解説を読めば意味がわかると思います。
日本語の表現力が足りない…コードのほうがわかりやすいかもしれません。

flatLevelArray

levelArrayとは違い、インデックスをいじくる必要がないのでforEachで回しています。

こちらも解説をつけました。

const flatLevelArray = (arr: Item[]): Item[] => {
  const out: Item[] = [];
  arr.forEach((item) => {
    // 自分の子孫を再帰的に平坦化して抽出
    const extractedChildren = flatLevelArray(item.children || []);

    // プロパティ削除
    delete item.children;

    // 自身を出力結果の配列に追加
    out.push(item);

    // 子孫を出力結果の配列に追加
    extractedChildren.forEach((child) => out.push(child));
  });
  return out;
};

途中でプロパティをdelete削除しているのは、確認にassertEqualsを使っているためで、別にitem.children = []などで消去しても本質的な違いはありません。

おわりに

「yamlとかmarkdownとかの文字列に変換してパースするのはどうか？」とか「木構造の処理に近いか？」とかいろいろ考えました。
実装できた後で、自分の目的にはこの処理自体を使う必要がないことが判明したため、なかなか贅沢な時間の使い方をできたと思います。
他の解法を見つけた方や、もっと楽なやり方をご存知という方はコメントいただけると嬉しいです。

完全に余談なのですが、この問題をやりながら、こういうのがプログラミング学習というかアルゴリズム学習だな、と考えていました。
いまの小中学生は学校でこんな感じの問題をやるんでしょうかね。お子さんをお持ちの方は夏休みのコミュニケーションにお使いください。

脚注

1. めちゃくちゃ悩んだ割に無駄のないきれいなコードになっていて嬉しい…自分のコードずっと見ていられる