71292


**やりたいこと**  
・JS(TypeScript)の連想配列において、階層を取得し、特定階層以上はfalseにしたい。

[code]

    [
      {
        "id": 1,
        "name": "フォルダA",
        folder:[
        {
          "id":2,
          "name":"フォルダA-2"
        },
        {
          "id":3,
          "name":"フォルダA-3"
        }]
      },
      {
        "id": 4,
        "name": "フォルダB"
      },
      {
        "id": 5,
        "name": "フォルダC",
        folder:[
        {
          "id":6,
          "name":"フォルダC-1",
          folder:[
          {
            "id": 7,
            "name": "フォルダC-1-1"
          }]
        }]
      }
    ]
    
[/code]

上記のような入れ子構造のデータがあります。  
また、folderプロパティは必須ではない・idは一意です。

特定のidの階層を数え、特定の階層以上だった場合はfalseを返すメソッドを作成したいのですが、思い付かず悩んでいます。（再帰処理？）  
ご教授頂けないでしょうか。

例：id=6 の場合は、countNode=1としたい。id=7の場合は、countNode=2としたい。(dataは上記のデータ全ての想定)  
countNode>=10の場合はfalse

[code]

    const countNode(currentId:string,data:any):boolean => {
      const node = 0;
      const maxNode = 10;
      //以下処理悩み中。
    }
    
[/code]


CC BY-SA 4.0
2020-10-17T16:27:59.957
71287
2020-10-19T03:16:58.453
42358
question
javascript typescript
JS(TypeScript) 連想配列　検索処理について


参考: <https://repl.it/repls/CyanWiseQueries>

TSということなので、まずは対象となるデータ配列の要素をモデル化しておくと、次のように書けます:

[code]

    interface Data {
      id: number
      name: string
      folder?: Data[]
    }
    
[/code]

このような要素をもつデータ配列において、ある`id`をもつ要素の“深さ”は、ご指摘のとおり再帰処理で簡単に取得できます:

[code]

    const scanDepth = (data: Data[], id: number, depth: number = 0): number => {
      for (const d of data) {
        if (d.id === id) return depth
        if (d.folder) {
          const ret = scanDepth(d.folder, id, depth + 1)
          if (ret !== -1) return ret
        }
      }
      return -1
    }
    
    // for example
    console.assert(scanDepth(DATA, 1) === 0)
    console.assert(scanDepth(DATA, 6) === 1)
    console.assert(scanDepth(DATA, 7) === 2)
    
[/code]

あとは、`scanDepth`関数の返り値を判定すればよいでしょう（こまかい条件は必要に応じて直してください）:

[code]

    const verifyDepth = (data: Data[], id: number, maxdepth: number): boolean => scanDepth(data, id) < maxdepth
    
    // for example
    console.assert(verifyDepth(DATA, 1, 1))
    console.assert(verifyDepth(DATA, 6, 2))
    console.assert(verifyDepth(DATA, 7, 3))
    console.assert(!verifyDepth(DATA, 7, 2))
    console.assert(!verifyDepth(DATA, 7, 1))
    console.assert(!verifyDepth(DATA, 7, 0))
    
[/code]

ただし、`scanDepth`はナイーブな実装なので、必要以上に深く探索をするかもしれません。データ構造がかなり深くなることが事前に予測できるならば、探索を打ち切るなど改良の余地はあると思います。


CC BY-SA 4.0
2020-10-18T00:12:31.883
71292
2020-10-18T00:12:31.883
71287
answer


個人的な経験則ですが、ツリー状のデータ構造の場合、データを探索する関数に再帰処理が多く発生し、デバッグがしづらかったり、メンテナンスがしづらかったりします。

あくまでデータが数十万、数百万とない前提で処理を組むと一度データ構造をユニークキーでフラット化すると様々な処理が簡素に書くことが可能です。

もし、メモリーの消費を抑えて、高速な処理を求めるならば、この方法ではないもの探すと良いでしょう。

[TypeScript
Playground](https://www.typescriptlang.org/play?target=7#code/JYOwLgpgTgZghgYwgAgGIHsA2ATayDeAsAFDLLDYBcyIArgLYBG0A3CWSHPRNQM5hRQAczalkMLLigB+ahhzQA2gF1RAXxIkA9ACod7HeWyAZBkAAcoHhDQFYMgFg1AECqBABgDyjAFYQEYQHYMAaQgBPQAsGQHUGQDMGQGc9QDN1QDRlQE0GQGiGAy0SUEhYRBRUTDgweSkCdmRFCmo6JmhlaiIxMgAHOCgIcABJbFkaBmYoUTJa7IALADkuCF4+AWEVbuQ1dU1iBHQQfmR6OABrCEzs3LwAXmQACgKJBShRtEklZQAaY6ycy6g5e52oZH38NVuxOobm1pKHWgJAAlM9to93gA+fJiE5SXgAOgkUAAoog+gcDvDoCDobCesgFkswMhfo0Hqd3mT6hSWsgAGQM8QvR6Kcn-
VQFMgwVmnRQ4qCIijKalVQm9P5gFrfCU0sCDYbnDmUqTciXSQqI7Uq16IuoKobcXjXcSPRGcbjKdWE6gC82WiA3dUzdXAGCHQXIx548US1YbLaq6DY82C028iGnCPmiggqZkDRiNTxgoNMC0KAgFlRqTqUQkYnLBa0cADdC4amh04tQFlKARvlScHBqBg5CMdBYCBwbO7GF+92HACEkdb9pr2GUvvVCqg6AA7jQIEvUVB51ADgADIOvQDWDIAnKMAyvqeQW15AAIgAJPgz9g1BfjIANbUAFOpBQB+DIBtBkAyQxb1PJgoi1JXAagVakx1eCcpBaZR9X6I0RkRTBGiEMCAFpkAARimICVjgAAPctK32TCAAYpnTTNsxAsCAB48MIisIHzOZcNWUAqzxfsCSJRZlnndBWzkNlRX2RR1T9Qliiw2UJUdagL0AVYZAEqGQBrhkAAYYAEEL1kwlBTtG0ekkuUjGoAAmXSTPky8VI0zS0LMnTDMTSzCWMuVpIAZlcuThgU2ytLQzynOqCUvkM51QvC0L3NM5AABYfOspS1PUgAhELCWitzDOkgBWJK-
Js1KAGFMolfTCmcniTLigA2HzCWSgKSrQzDytqyrxNC2rYtq6SAHZGqsoqUo01rMLajraumYayEi2rsolBaeiWrliEAvjSQgyF9gDTYmxDATW3-Mgi27JD0CEbFDrbHC+IuzAroOEsyyYg4GpzE7-1dDbiHYkADn-
IA)

[code]

    interface Folder {
      id: number;
      name: string;
      folder?: Folder[];
    }
    
    /**
     * idが一意な場合、ObjectのKeyとして平坦化する
     */
    interface FlatFolder {
      [id: number]: {
        parentId?: number;
        pathNames: string[];
      };
    }
    
    const makeFlatFolder = (
      folders: Folder[],
      flatFolder: FlatFolder = {},
      parentId?: number
    ): FlatFolder => {
      folders.forEach((folder) => {
        const parentFolder = parentId && flatFolder[parentId];
        flatFolder[folder.id] = {
          parentId,
          pathNames: parentFolder
            ? [...parentFolder.pathNames, folder.name]
            : [folder.name],
        };
        if (folder.folder) {
          makeFlatFolder(folder.folder, flatFolder, folder.id);
        }
      });
      return flatFolder;
    };
    
    const countNode = (folderId: number, flatFolder: FlatFolder): boolean => {
      if (!flatFolder[folderId]) {
        throw new Error(`FlatFolderに該当のfolderId: "${folderId}"が存在しません`);
      }
      const depth = flatFolder[folderId].pathNames.length - 1;
      const maxNode = 10;
      return depth < maxNode;
    };
    
    const main = () => {
      const rootFolder: Folder[] = [
        {
          id: 1,
          name: "フォルダA",
          folder: [
            {
              id: 2,
              name: "フォルダA-2",
            },
            {
              id: 3,
              name: "フォルダA-3",
            },
          ],
        },
        {
          id: 4,
          name: "フォルダB",
        },
        {
          id: 5,
          name: "フォルダC",
          folder: [
            {
              id: 6,
              name: "フォルダC-1",
              folder: [
                {
                  id: 7,
                  name: "フォルダC-1-1",
                },
              ],
            },
          ],
        },
      ];
    
      const flatFolder = makeFlatFolder(rootFolder);
      console.log(flatFolder);
      console.log(countNode(6, flatFolder));
    };
    
    main();
    
[/code]


CC BY-SA 4.0
2020-10-19T03:16:58.453
71318
2020-10-19T03:16:58.453
7997
71287
answer