CODEWITHSUNDEEP
javascriptarraysrecursion
AndyJamesN
AndyJamesN

Reputation: 498

Return all id's from a deeply nested Object of arrays and objects

Assuming I have this deeply nested object

let obj = {
  comp: "el",
  type: "ele",
  children: [
    {
      children: [
        {
          text: "text",
          children: [],
          uid: "-5zIANJjCz-qU0MNcf5E1",
        },
        {
          text:"text",
          children: [],
          uid: "bpeVj4NaD_Io3WP7V0v91"
        }
      ],
      uid: "ZygtUliVsFbFpbmHv5yp9"
    },
    {
      children: [
        {
          text: "text",
          children: [],
          uid: "qmw59v1BVRMEuM8r9VvQp",
        },
        {
          text: "text. ",
          children: [],
          uid: "q-QeWlEnKvVTjD0dPRXCu"
        }
      ],
      uid: "rp_gURLFIgd1n7bn-pRhn"
    },
    {
      children: [
        {
          text: "text",
          children: [],
          uid: "8gIytZ52tq0mqiVAhAJLN",
        },
        {
          text: "text",
          children: [],
          uid: "q-QeeWlEnKvVTjD0dPRXCu"
        }
      ],
      uid: "M3hqA-Rp1wQz60IVdIGUX"
    }
  ],
  uid: "M4JBL9SoOOLo5iQSb5M_P"
};

How would I go about getting an array of all uid values?

Currently I am using object scan

https://github.com/blackflux/object-scan

const find = (data, needle) => objectScan([needle], { rtn: "value" })(data);
const allIds = find(obj, "**.uid");

This works really well but I am curious how this could be achieved with recursion.

Upvotes: 1

Views: 877

Answers (3)

Ajax1234
Ajax1234

Reputation: 71451

You can use a recursive generator function:

function* get_uid(d){
   yield* ('uid' in d ? [d.uid] : [])
   for (var c of ('children' in d ? d.children : [])){
      yield* get_uid(c)
   }
}
let obj = {'comp': 'el', 'type': 'ele', 'children': [{'children': [{'text': 'text', 'children': [], 'uid': '-5zIANJjCz-qU0MNcf5E1'}, {'text': 'text', 'children': [], 'uid': 'bpeVj4NaD_Io3WP7V0v91'}], 'uid': 'ZygtUliVsFbFpbmHv5yp9'}, {'children': [{'text': 'text', 'children': [], 'uid': 'qmw59v1BVRMEuM8r9VvQp'}, {'text': 'text. ', 'children': [], 'uid': 'q-QeWlEnKvVTjD0dPRXCu'}], 'uid': 'rp_gURLFIgd1n7bn-pRhn'}, {'children': [{'text': 'text', 'children': [], 'uid': '8gIytZ52tq0mqiVAhAJLN'}, {'text': 'text', 'children': [], 'uid': 'q-QeeWlEnKvVTjD0dPRXCu'}], 'uid': 'M3hqA-Rp1wQz60IVdIGUX'}], 'uid': 'M4JBL9SoOOLo5iQSb5M_P'}
var result = [...get_uid(obj)]
console.log(result);

Upvotes: 0

Scott Sauyet
Scott Sauyet

Reputation: 50797

It's pretty easy with a simple helper function that gathers results paired with one that uses that to get the id of every node visited::

const gather = (fn) => (o) => 
  [fn (o), ... (o .children || []) .flatMap (gather (fn))]

const obj = {comp: "el", type: "ele", children: [{children: [{text: "text", children: [], uid: "-5zIANJjCz-qU0MNcf5E1"}, {text: "text", children: [], uid: "bpeVj4NaD_Io3WP7V0v91"}], uid: "ZygtUliVsFbFpbmHv5yp9"}, {children: [{text: "text", children: [], uid: "qmw59v1BVRMEuM8r9VvQp"}, {text: "text. ", children: [], uid: "q-QeWlEnKvVTjD0dPRXCu"}], uid: "rp_gURLFIgd1n7bn-pRhn"}, {children: [{text: "text", children: [], uid: "8gIytZ52tq0mqiVAhAJLN"}, {text: "text", children: [], uid: "q-QeeWlEnKvVTjD0dPRXCu"}], uid: "M3hqA-Rp1wQz60IVdIGUX"}], uid: "M4JBL9SoOOLo5iQSb5M_P"}

console .log (gather (x => x .uid) (obj))

//   or, storing the uid function in a helper: 
// const extractUids = gather (x => x .uid)
// console .log (extractUids (obj))

But if you have no other need for the generic solution, you can alternatively inline that helper directly into the function:

const extractUids = (o) => 
  [o .uid, ... (o .children || []) .flatMap (extractUids)]

Upvotes: 3

Alexander Alexandrov
Alexander Alexandrov

Reputation: 1372

For trees (and graphs without cycles) you can use simple recursion-based strategy as follows:

function reduceTree<Item, Acc>(
    next: (item: Item) => Item[],
    reducer: (acc: Acc, item: Item) => Acc
) {
    const step = (acc: Acc, item: Item): Acc => next(item)
        .reduce((_, child) => step(_, child), reducer(acc, item));
    return step;
}

// Test
const allIds = reduceTree(
    (item: TreeItem) => item.children,
    (allIds: string[], item) => [...allIds, item.uid]
)(
    [], obj
);

TS Playground

Upvotes: 0

Related Questions