Guide to recursively iterating through an array of objects in TypeScript/Javascript

Question

Guide to recursively iterating through an array of objects in TypeScript/Javascript

In my current programming challenge, I am dealing with an array of objects that have two properties: target and source. Additionally, there is a designated starting source to begin with.

The goal is to start from the starting source and recursively find a target from the given array. Once a target is found, it becomes the new source and the process continues until the target value is undefined.

I am seeking an efficient way to achieve this task and would appreciate any concise code suggestions.

let result = new Array();
// input
    const a = [
      { source: '2', target: '3' },
      { source: '1', target: '2' },
      { source: '3', target: '4' },
      { source: '4', target: '5' }
    ];
    const startSource = '1';
    result.push(startSource);
   // recursive function
    this.findTarget(startSource, a);
    console.log(result);

Here is the recursive function I have implemented:

 public findTarget(s: string, a: Sequence[]): any {
    let obj = a.find(i => i.source === s);
    if (obj) {
      this.result.push(obj.target);
      return this.findTarget(obj.target, a);
    } else {
      return;
    }
  }

javascript arrays typescript ecmascript-6 ecmascript-5

Answer 1

Answer №1

To simplify the process, you can create a hashmap or plain object where the source is the key and the target is the value. This eliminates the need for recursion and allows for a straightforward chaining of values until completion.

By utilizing this map, you can gather all values until there are no more defined targets in the map[nextSource] sequence.

The following method accomplishes this efficiently by leveraging function generators to yield the discovered values.

This approach is considered the most efficient due to the O(1) complexity of creating the lookup table once compared to the higher complexity of applying find in every iteration (potentially O(n) or O(n^2)).

If preferred, the use of function generators can be replaced with collecting the results directly. Function generators were chosen for their simplicity and ease of maintenance.

SIDE NOTE: The provided sample code initially pushes a source followed by targets. If targeting specific data, modify yield startSourceValue; to

yield reverseMap[startSourceValue];

.

Below is the functional code snippet:

const a = [
  { source: '2', target: '3' },
  { source: '1', target: '2' },
  { source: '3', target: '4' },
  { source: '4', target: '5' }
];
const startSource = '1';

function* chainSources(array, targetKey, sourceKey, startSourceValue) {
  const reverseMap = array.reduce((acc, item) => {
    acc[item[sourceKey]] = item[targetKey];
    return acc;
  }, {});

  while (reverseMap[startSourceValue] !== undefined) {
    yield startSourceValue;
    startSourceValue = reverseMap[startSourceValue];
  }
  return;
}

for (let target of chainSources(a, 'target', 'source', '1')) {
  console.log(target);
}

const result = [...chainSources(a, 'target', 'source', '1')];

console.log(result);

Alternate solution without function generators:

const a = [
  { source: '2', target: '3' },
  { source: '1', target: '2' },
  { source: '3', target: '4' },
  { source: '4', target: '5' }
];
const startSource = '1';

function chainSources(array, targetKey, sourceKey, startSourceValue) {
  const res = [];
  const reverseMap = array.reduce((acc, item) => {
    acc[item[sourceKey]] = item[targetKey];
    return acc;
  }, {});

  while (reverseMap[startSourceValue] !== undefined) {
    res.push(startSourceValue);
    startSourceValue = reverseMap[startSourceValue];
  }
  return res;
}

const result = chainSources(a, 'target', 'source', '1');

console.log(result);

Answer 2

To simplify the process, you can create a hashmap or plain object where the source is the key and the target is the value. This eliminates the need for recursion and allows for a straightforward chaining of values until completion.

By utilizing this map, you can gather all values until there are no more defined targets in the map[nextSource] sequence.

The following method accomplishes this efficiently by leveraging function generators to yield the discovered values.

This approach is considered the most efficient due to the O(1) complexity of creating the lookup table once compared to the higher complexity of applying find in every iteration (potentially O(n) or O(n^2)).

If preferred, the use of function generators can be replaced with collecting the results directly. Function generators were chosen for their simplicity and ease of maintenance.

SIDE NOTE: The provided sample code initially pushes a source followed by targets. If targeting specific data, modify yield startSourceValue; to

yield reverseMap[startSourceValue];

.

Below is the functional code snippet:

const a = [
  { source: '2', target: '3' },
  { source: '1', target: '2' },
  { source: '3', target: '4' },
  { source: '4', target: '5' }
];
const startSource = '1';

function* chainSources(array, targetKey, sourceKey, startSourceValue) {
  const reverseMap = array.reduce((acc, item) => {
    acc[item[sourceKey]] = item[targetKey];
    return acc;
  }, {});

  while (reverseMap[startSourceValue] !== undefined) {
    yield startSourceValue;
    startSourceValue = reverseMap[startSourceValue];
  }
  return;
}

for (let target of chainSources(a, 'target', 'source', '1')) {
  console.log(target);
}

const result = [...chainSources(a, 'target', 'source', '1')];

console.log(result);

Alternate solution without function generators:

const a = [
  { source: '2', target: '3' },
  { source: '1', target: '2' },
  { source: '3', target: '4' },
  { source: '4', target: '5' }
];
const startSource = '1';

function chainSources(array, targetKey, sourceKey, startSourceValue) {
  const res = [];
  const reverseMap = array.reduce((acc, item) => {
    acc[item[sourceKey]] = item[targetKey];
    return acc;
  }, {});

  while (reverseMap[startSourceValue] !== undefined) {
    res.push(startSourceValue);
    startSourceValue = reverseMap[startSourceValue];
  }
  return res;
}

const result = chainSources(a, 'target', 'source', '1');

console.log(result);

Answer 3

Answer №2

Within my code snippet, I am utilizing the .findIndex() array method to locate the index of an element in the array based on certain conditions. If the index returned is -1, it indicates that there is no data in the array that meets our specified condition.

const findElement = (value, array = [], tempArray = []) => {
  const index = array.findIndex((item) => { return item.name === value; });
  if (index > -1) {
    const element = array[index];
    tempArray.push(element.type);
    return findElement(element.type, array, tempArray);
  }
  return tempArray;
};

const data = [
  { name: 'apple', type: 'fruit' },
  { name: 'carrot', type: 'vegetable' },
  { name: 'banana', type: 'fruit' },
  { name: 'lettuce', type: 'vegetable' },
];
const startingValue = 'carrot';
const result = findElement(startingValue, data);
console.log(result);

Answer 4

Within my code snippet, I am utilizing the .findIndex() array method to locate the index of an element in the array based on certain conditions. If the index returned is -1, it indicates that there is no data in the array that meets our specified condition.

const findElement = (value, array = [], tempArray = []) => {
  const index = array.findIndex((item) => { return item.name === value; });
  if (index > -1) {
    const element = array[index];
    tempArray.push(element.type);
    return findElement(element.type, array, tempArray);
  }
  return tempArray;
};

const data = [
  { name: 'apple', type: 'fruit' },
  { name: 'carrot', type: 'vegetable' },
  { name: 'banana', type: 'fruit' },
  { name: 'lettuce', type: 'vegetable' },
];
const startingValue = 'carrot';
const result = findElement(startingValue, data);
console.log(result);

Answer 5

Answer №3

If you convert your current data structure into an object with the format {source: target}, you can then iterate through it until you reach a null node:

map = {};

for (let {source, target} of b) {
    map[source] = target;
}

while (current) {
    output.push(current);
    current = map[current];
}

This method relies on the assumption that your graph functions as a linear chain, where each source only has one target.

Answer 6

If you convert your current data structure into an object with the format {source: target}, you can then iterate through it until you reach a null node:

map = {};

for (let {source, target} of b) {
    map[source] = target;
}

while (current) {
    output.push(current);
    current = map[current];
}

This method relies on the assumption that your graph functions as a linear chain, where each source only has one target.

Guide to recursively iterating through an array of objects in TypeScript/Javascript

Answer №1

Answer №2

Answer №3

Similar questions

What is preventing my function from retrieving data from the JSON File?

Locate the word or phrase without a comma

Having difficulty choosing a default value from the Angular dropdown menu

The syntax in JavaScript of (0, fn)(args) is used to call

Is there a way for Ionic to remember the last page for a few seconds before session expiry?

Having trouble correctly parsing XML data using JavaScript

Angular: Unable to retrieve defined data when loading a component

Issue: Undefined onClick function for HTML when using Node.js, NPM, and Parcel

How can I achieve the functionality of an image changing when clicked and going back to its original state upon release with the help of HTML

ajax - unable to fetch information from the same domain

Error: The function is not defined on this.props during the handleCHange event

Changing URI to File Object using JavaScript

Mapped Generics in Typescript allows you to manipulate and

Encountering an issue of THREE.EventDispatcher being undefined while trying to create a THREE.OrbitControls instance using THREE.js, THREE.OrbitControls, and TypeScript

Exploring the functionality of surveyjs in conjunction with react and typescript

What can be done to ensure that two separate react-native Picker components do not interfere with each other's

Angular: The Process of Completely Updating a Model Object

Is there a method to compress all of my JS/CSS files before displaying them in the browser without doing so while editing them in the IDE?

Show a directional indicator on hover in the date selection tool

Mapping DOM elements to VueJS components for hydration is a key process in facilitating