I have some data that looks like this:

const data = {
  "type": "A",
  "items": [
    {
      "type": "B",
      "tokens": [
        {
          "type": "C"
        }
      ]
    },
    {
      "type": "B",
      "tokens": {
        "type": "A",
        "items": [
          {
            "type": "B",
            "tokens": [
              {
                "type": "D"
              },
              {
                "type": "A",
                "items": [
                  "..."
                ]
              }
            ]
          },
          {
            "type": "B",
            "tokens": []
          }
        ]
      }
    }
  ]
}

The logic of the data is as follows

• Objects of type A contains the field items, that contains only objects of type B and must contain at least 1 of them.
• Objects of type B contain the tokens field, that contains all types except B, and must contain at least one of them, for example: D, C or A.
• The B.tokens could also contain object A which contains another items and so on. This could be repeated more than 10 levels deep.
• Both A.items and B.tokens are of the type Token[].

type Token =
    | Tokens.A
    | Tokens.B
    | Tokens.C

namespace Tokens {
  export interface A {
    type: "A";
    items: Token.B[];
  }
  export interface B {
    type:"B"
    tokens: Token[];
  }
  export interface C {
    type: "C";
    content: string;
  }
}

I am trying to obtain an array of all entries inside type B that are not type A. The type A inside B.tokens should be recursive checked to find entries inside of B that aren't A and include an index of the depth.

It would be of great help if someone could help me by indicating an approach to the problem or pseudocode.

Thanks in advance.

Update on @Mulan request What does the final output look like for the example provided?

Something like this

{
  "id": 0,
  "collection": [
    {
      "type": "C",
      "content": "BLA",
      "depth": 1
    },
    {
      "type": "D",
      "content": "BLO",
      "depth": 2
    }
  ]
}

Although Mulan's answer is much more detailed and accurate than mine, I leave what I had tried at the request of Dima

const filterTokens = (tokens: Token[], filtered: Token[] = []): Token[] => {
    for (const token of tokens) {
        if (token.type === "A") {
            filterTokens(token.items, filtered);
        } else if (token.type === "B") {
            filterTokens(token.tokens, filtered);
        } else {
            filtered.push(token);
        }
    }
    return filtered;
}
console.log(filterTokens(data.items));

CodePudding user response：

Mutual recursion is an effective way to process trees. I'll start with some function f that accepts an input t and an initial depth of 0. We perform a simple type analysis on t and declare how each type of t should flatten to an array. In this particular case, Array is the only one given special consideration, all other items can be treated as a single item -

const f = (t, depth = 0) => {
  switch (t?.constructor) {
    case Array: return t.flatMap(v => f(v, depth))
    default: return f1(t, depth)
  }
}

When we encounter a single item, we pass it to some function f1 that processes just one item. Here we do a type analysis on the nodes type property and declare how each type, A, B, etc, should flatten -

const f1 = (t, depth = 0) => {
  switch (t?.type) {
    case "A": return f(t.items, depth   1)
    case "B": return f(t.tokens, depth   1)
    default: return [{...t, depth}]
  }
}

In your mock data I made a change to keep it consistent with the tree shape -

// ellipses
"..."

// replaced with
{type:"Z",content:"..."}

console.log(f(data))

[
  {
    "type": "C",
    "depth": 2
  },
  {
    "type": "D",
    "depth": 4
  },
  {
    "type": "Z",
    "content": "...",
    "depth": 5
  }
]

Here's a full working demo -

const f = (t, depth = 0) => {
  switch (t?.constructor) {
    case Array: return t.flatMap(v => f(v, depth))
    default: return f1(t, depth)
  }
}

const f1 = (t, depth) => {
  switch (t?.type) {
    case "A": return f(t.items, depth   1)
    case "B": return f(t.tokens, depth   1)
    default: return [{...t, depth}]
  }
}

const data =
  {type:"A",items:[{type:"B",tokens:[{type:"C"}]},{type:"B",tokens:{type:"A",items:[{type:"B",tokens:[{type:"D"},{type:"A",items:[{type:"Z",content:"..."}]}]},{type:"B",tokens:[]}]}}]}

console.log(f(data))