Iterating over array of objects with references to each other and resolve these from string to object

Question

I'm creating a preset system, where presets can "include" other presets.

Preset A includes Preset B and C, while Preset B includes D and E.

They all have this structure: - id - name (string, used as reference in include) - content (array of strings) - include (array of name, corresponding to the name prop)

The content is what gets included.

I tried coming up with a solution for the last 2 days, trying to wrap my head around recursion. I looked at the recursion related posts on here, but nothing really fits my scenario.

function getIncludes (original) {
    let output = [];

    function recursion (package) {
        if (package.content) output.push(package.content.join(' '));
        if (package.include) {
            return package.include.forEach(str => {
                let c = presets.find(obj => obj.name === str);
                if (c.content) output.push(c.content.join(' '));
                    recursion(c)
            });
        }
    }

    recursion(original);
    return output.join(' ');
}

example presets obj

[
  {
    "id": 0,
    "name": "videoFormats",
    "content": ["(avi|mkv|mov|mp4|mpg|wmv)"],
    "hidden": true,
    "include": ["imageFormats"]
  },
  {
    "name": "audioFormats",
    "id": 1,
    "content": ["(ac3|flac|m4a|mp3|ogg|wav|wma)"],
    "hidden": true,
    "include": ["imageFormats"]
  },
  {
    "id": 2,
    "name": "imageFormats",
    "content": ["(bmp|gif|jpg|jpeg|png|psd|tif|tiff)"],
    "hidden": true
  },
  {
    "id": 3,
    "name": "media",
    "title": "Media",
    "include": ["videoFormats", "audioFormats"],
    "hidden": false
  }
]

I need a function that gives me a list of presets, the selected preset depends on.

A function like this would work.

getIncludes("media") returning ["videoFormats", "audioFormats", "imageFormats"]

Answer 1

First we need to think of some type T which allows for efficient lookup of a particular preset by name. Arrays provide no such facility and so we will convert from Array to our desired type, T. In this case, we will use Map -

// type preset =
//   { id: number
//   , name: string
//   , content: string array
//   , hidden: bool
//   , include: string array
//   }

// type t =
//   (string, preset) map

Above we see t as a map which has string keys that each point to a preset value. Now we can write fromArray -

// fromArray : preset array -> t
const fromArray = (a = []) =>
  a.reduce((r,x) => r.set(x.name, x), new Map)

Now that we can easily find a preset by name, we write a generic traverse procedure. This allows us to separate 1) the traversal of our tree from 2) the intended operation we want to perform on each tree element -

// traverse : (t, string) -> preset generator
const traverse = function* (t = new Map, name = "") {
  if (!t.has(name)) return
  yield* traverse1(t, t.get(name))
}

// traverse1 : (t, preset) -> preset generator
const traverse1 = function* (t = new Map, preset = {}) {
  yield preset
  for (const i of preset.include || [])
    yield* traverse(t, i)
}

Now our getIncludes function can be a simple program. It no longer has to concern itself with tree traversal, and instead can focus on converting a linear sequence of preset elements into the desired Set of strings -

const getIncludes = (t = new Map, name = "") =>
{ const r = new Set
  for (const p of traverse(t, name))
    if (r.has(p.name) || p.name === name)
      continue
    else
      r.add(p.name)
  return Array.from(r)
}

As you can see, removing the traversal logic from each function that depends on our tree can be a huge help. Let's test it here -

const tree =
  fromArray(presets)

getIncludes(tree, "media")
// [ "videoFormats", "imageFormats", "audioFormats" ]

getIncludes(tree, "audioFormats")
// [ "imageFormats" ]

getIncludes(tree, "imageFormats")
// []

Expand the snippet below to verify the results in your own browser -

const presets = 
[ { id: 0
  , name: "videoFormats"
  , content: ["(avi|mkv|mov|mp4|mpg|wmv)"]
  , hidden: true
  , include: ["imageFormats"]
  }
, { id: 1
  , name: "audioFormats"
  , content: ["(ac3|flac|m4a|mp3|ogg|wav|wma)"]
  , hidden: true
  , include: ["imageFormats"]
  }
, { id: 2
  , name: "imageFormats"
  , content: ["(bmp|gif|jpg|jpeg|png|psd|tif|tiff)"]
  , hidden: true
  }
, { id: 3
  , name: "media"
  , title: "Media"
  , include: ["videoFormats", "audioFormats"]
  , hidden: false
  }
]

const fromArray = (a = []) =>
  a.reduce((r,x) => r.set(x.name, x), new Map)

const traverse = function* (t = new Map, name = "") {
  if (!t.has(name)) return
  yield* traverse1(t, t.get(name))
}

const traverse1 = function* (t = new Map, preset = {}) {
  yield preset
  for (const i of preset.include || [])
    yield* traverse(t, i)
}

const getIncludes = (t = new Map, name = "") =>
{ const r = new Set
  for (const p of traverse(t, name))
    if (r.has(p.name) || p.name === name)
      continue
    else
      r.add(p.name)
  return Array.from(r)
}

const tree =
  fromArray(presets)

console.log(getIncludes(tree, "media"))
// [ "videoFormats", "imageFormats", "audioFormats" ]

console.log(getIncludes(tree, "audioFormats"))
// [ "imageFormats" ]

console.log(getIncludes(tree, "imageFormats"))
// []

Answer 2

You could take an object for all presets for an access by name an then get the includes values. To get unique items, you could get a Set and omit double items.

function getIncludes(original) {
    if (!presets[original]) return [];
    return [].concat(presets[original].include || []).reduce(
        (r, name) => [...r, ...getIncludes(name)],
        [original]
    );
}

var data = [{ id: 0, name: "videoFormats", content: ["(avi|mkv|mov|mp4|mpg|wmv)"], hidden: true, include: "imageFormats" }, { id: 1, name: "audioFormats", content: ["(ac3|flac|m4a|mp3|ogg|wav|wma)"], hidden: true, include: "imageFormats" }, { id: 2, name: "imageFormats", content: ["(bmp|gif|jpg|jpeg|png|psd|tif|tiff)"], hidden: true }, { id: 3, name: "media", title: "Media", include: ["videoFormats", "audioFormats"], hidden: false }],
    presets = data.reduce((r, o) => (r[o.name] = o, r), {});

console.log(getIncludes('videoFormats'));
console.log(getIncludes('audioFormats'));
console.log(getIncludes('imageFormats'));
console.log(getIncludes('media'));

.as-console-wrapper { max-height: 100% !important; top: 0; }

A different approach by using a stack and taking the presets of the same level first and prevent to add already inserted items. This approach works without recursion.

function getIncludes(original) {
    var stack = [original],
        name,
        result = [];

    while (stack.length) {
        name = stack.shift();
        if (result.includes(name) || !presets[name]) continue;
        result.push(name);
        stack.push(...[].concat(presets[name].include || []));
    }
    return result;
}

var data = [{ id: 0, name: "videoFormats", content: ["(avi|mkv|mov|mp4|mpg|wmv)"], hidden: true, include: "imageFormats" }, { id: 1, name: "audioFormats", content: ["(ac3|flac|m4a|mp3|ogg|wav|wma)"], hidden: true, include: "imageFormats" }, { id: 2, name: "imageFormats", content: ["(bmp|gif|jpg|jpeg|png|psd|tif|tiff)"], hidden: true }, { id: 3, name: "media", title: "Media", include: ["videoFormats", "audioFormats"], hidden: false }],
    presets = data.reduce((r, o) => (r[o.name] = o, r), {});

console.log(getIncludes('videoFormats'));
console.log(getIncludes('audioFormats'));
console.log(getIncludes('imageFormats'));
console.log(getIncludes('media'));

.as-console-wrapper { max-height: 100% !important; top: 0; }