Successor in a JavaScript array with multiple dimensions

Question

Successor in a JavaScript array with multiple dimensions

I am grappling with a complex nested multidimensional array that resembles the following structure in JSON format:

[
    {
        "Object": "Car",
        "Child": [
            {
                "Object": "Toyota",
                "Child": [
                    {
                        "Object": "Prius"
                    },
                    {
                        "Object": "Yaris"
                    }
                ]
            },
            {
                "Object": "Honda",
                "Child": [
                    {
                        "Object": "Accord"
                    },
                    {
                        "Object": "Civic",
                        "Child": [
                            {
                                "Object": "Sedan"
                            },
                            {
                                "Object": "Coupe"
                            }
                        ]
                    }
                ]
            }
        ]
    }
]

I'm seeking a way to determine if one object is a direct descendant of another within this hierarchy.

For instance, "Sedan" is a direct descendant of "Civic", "Honda", and "Car"; however, it is not a direct descendant of "Coupe", "Accord", "Toyota", "Prius", or "Yaris".

The goal is to develop a function similar to the following:

function Lineal_Descendant(A,B){
    /*perform logic here*/
}

Lineal_Descendant("Sedan","Civic") /*should return true*/
Lineal_Descendant("Sedan","Toyota") /*should return false*/
Lineal_Descendant("Prius","Honda") /*should return false*/
Lineal_Descendant("Yaris","Car") /*should return true*/

javascript arrays algorithm multidimensional-array

Answer 1

Answer №1

Alright, I'll take a crack at it: http://jsfiddle.net/nrabinowitz/UJrhK/

function Lineal_Descendant(child, parent) {
    // examining an array of objects
    function walk(array, search) {
        for (var x=0, found; x<array.length; x++) {
            found = visit(array[x], search);
            if (found) return found;
        }
        return false;
    }
    // searching an object and its children
    function visit(obj, search) {
        // identifying the search item
        return obj.Object === search ? obj :
            // not found, but has children
            obj.Child ? walk(obj.Child, search) :
            // no children
            false; 
    }
    // locating the parent
    parent = walk(data, parent);
    // finding child, converting to boolean
    if (parent) return !!walk(parent.Child || [], child);
}

There might be a more elegant solution to this problem, but this should suffice. Keep in mind that your data structure does not enforce unique names, so if you have two items at the same level with identical values for Object, the search results may be unexpected.

Answer 2

Alright, I'll take a crack at it: http://jsfiddle.net/nrabinowitz/UJrhK/

function Lineal_Descendant(child, parent) {
    // examining an array of objects
    function walk(array, search) {
        for (var x=0, found; x<array.length; x++) {
            found = visit(array[x], search);
            if (found) return found;
        }
        return false;
    }
    // searching an object and its children
    function visit(obj, search) {
        // identifying the search item
        return obj.Object === search ? obj :
            // not found, but has children
            obj.Child ? walk(obj.Child, search) :
            // no children
            false; 
    }
    // locating the parent
    parent = walk(data, parent);
    // finding child, converting to boolean
    if (parent) return !!walk(parent.Child || [], child);
}

There might be a more elegant solution to this problem, but this should suffice. Keep in mind that your data structure does not enforce unique names, so if you have two items at the same level with identical values for Object, the search results may be unexpected.

Answer 3

Answer №2

This technique may seem unconventional, but it involves utilizing the browser DOM model to achieve certain tasks. By preloading your data structure into the DOM and then using functions like querySelectorAll or similar (such as jQuery), you can manipulate the data effectively.

For a practical example, check out this jsFiddle demonstration - http://jsfiddle.net/SxCD6/2/

Answer 4

This technique may seem unconventional, but it involves utilizing the browser DOM model to achieve certain tasks. By preloading your data structure into the DOM and then using functions like querySelectorAll or similar (such as jQuery), you can manipulate the data effectively.

For a practical example, check out this jsFiddle demonstration - http://jsfiddle.net/SxCD6/2/

Answer 5

Answer №3

Presented below is a compact and recursive function that fulfills the desired requirements:

function linearDescendant(list, search, ancestor, _parent) {
  var i, item, found = false;

  for (i=0; i<list.length; i++) {
    item = list[i];
    item._parent = _parent;

    if (item.Object == search) {
      while (item._parent && item.Object != ancestor) {
        item = item._parent;
      }
      found = item.Object == ancestor;
    } else if (item.Child) { 
      found = linearDescendant(item.Child, search, ancestor, item);
    }
    if (found) break;
  }
  return found;
}

To utilize this function, use the following syntax:

linearDescendant(yourArray, "Sedan", "Civic")  // true
linearDescendant(yourArray, "Sedan", "Toyota") // false
linearDescendant(yourArray, "Prius", "Honda")  // false
linearDescendant(yourArray, "Yaris", "Car")    // true

It should be noted that the function assigns a _parent property to each nested object. This attribute is crucial for conducting the ancestor verification once the target object has been identified.

Answer 6

Presented below is a compact and recursive function that fulfills the desired requirements:

function linearDescendant(list, search, ancestor, _parent) {
  var i, item, found = false;

  for (i=0; i<list.length; i++) {
    item = list[i];
    item._parent = _parent;

    if (item.Object == search) {
      while (item._parent && item.Object != ancestor) {
        item = item._parent;
      }
      found = item.Object == ancestor;
    } else if (item.Child) { 
      found = linearDescendant(item.Child, search, ancestor, item);
    }
    if (found) break;
  }
  return found;
}

To utilize this function, use the following syntax:

linearDescendant(yourArray, "Sedan", "Civic")  // true
linearDescendant(yourArray, "Sedan", "Toyota") // false
linearDescendant(yourArray, "Prius", "Honda")  // false
linearDescendant(yourArray, "Yaris", "Car")    // true

It should be noted that the function assigns a _parent property to each nested object. This attribute is crucial for conducting the ancestor verification once the target object has been identified.

Answer 7

Answer №4

I implemented the approach of Modified Preorder Tree Traversal to solve this problem. Essentially, I iterated through the JSON object using a recursive function and assigned "left" and "right" values to each element. After updating the entire JSON object with these values, I compared the "left" and "right" values in Object A and B to determine if one is a lineal descendant of the other.

For instance, if Object A is a lineal descendant of Object B, then the "left" value in A will be greater than the "left" value in B, and the "right" value in A will be smaller than the "right" value in B.

Sample Code:

var data = [{"Object":"Car","Child":[{"Object":"Toyota","Child":[{"Object":"Prius"},{"Object":"Yaris"}]},{"Object":"Honda","Child":[{"Object":"Accord"},{"Object":"Civic","Child":[{"Object":"Sedan"},{"Object":"Coupe"}]}]}]}];

alert(Lineal_Descendant(data,'Sedan','Civic'));  //true
alert(Lineal_Descendant(data,'Sedan','Toyota')); //false
alert(Lineal_Descendant(data,'Prius','Honda'));  //false
alert(Lineal_Descendant(data,'Yaris','Car'));    //true

function Lineal_Descendant(data, A, B){
    var i=1,                  
        k=0,                  
        aIndex,               
        bIndex,               
        entry = new Array(),  
        mpttObj = mptt(data); 

    function mptt(obj) {
        for (var f=0, n=obj.length; f<n; f++) {
            if(obj[f].Object==A) aIndex=k; 
            if(obj[f].Object==B) bIndex=k; 

            obj[f].index=k;
            entry[obj[f].index] = {left:i, right:-1};
            obj[f].left=i;
            
            k++;
            i++;

            if (obj[f].Child) mptt(obj[f].Child);

            entry[obj[f].index].right = i;
            obj[f].right=i;
            i++;
        }
        return obj;
    }

    if(entry[aIndex].left>entry[bIndex].left  &&  entry[aIndex].right<entry[bIndex].right) return true;
    else return false;
}

See it in action: http://jsfiddle.net/bPu2V/

Answer 8

I implemented the approach of Modified Preorder Tree Traversal to solve this problem. Essentially, I iterated through the JSON object using a recursive function and assigned "left" and "right" values to each element. After updating the entire JSON object with these values, I compared the "left" and "right" values in Object A and B to determine if one is a lineal descendant of the other.

For instance, if Object A is a lineal descendant of Object B, then the "left" value in A will be greater than the "left" value in B, and the "right" value in A will be smaller than the "right" value in B.

Sample Code:

var data = [{"Object":"Car","Child":[{"Object":"Toyota","Child":[{"Object":"Prius"},{"Object":"Yaris"}]},{"Object":"Honda","Child":[{"Object":"Accord"},{"Object":"Civic","Child":[{"Object":"Sedan"},{"Object":"Coupe"}]}]}]}];

alert(Lineal_Descendant(data,'Sedan','Civic'));  //true
alert(Lineal_Descendant(data,'Sedan','Toyota')); //false
alert(Lineal_Descendant(data,'Prius','Honda'));  //false
alert(Lineal_Descendant(data,'Yaris','Car'));    //true

function Lineal_Descendant(data, A, B){
    var i=1,                  
        k=0,                  
        aIndex,               
        bIndex,               
        entry = new Array(),  
        mpttObj = mptt(data); 

    function mptt(obj) {
        for (var f=0, n=obj.length; f<n; f++) {
            if(obj[f].Object==A) aIndex=k; 
            if(obj[f].Object==B) bIndex=k; 

            obj[f].index=k;
            entry[obj[f].index] = {left:i, right:-1};
            obj[f].left=i;
            
            k++;
            i++;

            if (obj[f].Child) mptt(obj[f].Child);

            entry[obj[f].index].right = i;
            obj[f].right=i;
            i++;
        }
        return obj;
    }

    if(entry[aIndex].left>entry[bIndex].left  &&  entry[aIndex].right<entry[bIndex].right) return true;
    else return false;
}

See it in action: http://jsfiddle.net/bPu2V/

Answer 9

Answer №5

Before anything else,

Absolutely do not utilize `"Object"` as a key on an `Object`.

You are dangerously close to accidentally overwriting the native javascript Object which would result in the dreaded javascript apocalypse. I recommend using name instead.

Furthermore, this issue can be resolved with a fairly straightforward recursive function:

var find = function(obj, search){
    // return this object if it matches
    if(obj.name === search)
      return obj;
    // false if it has no children
    if(!obj.hasOwnProperty('Child')) 
      return false;
    for(var i=0,u=obj.Child.length;i<u;i++){
        // recursively check each child
        var foundRecursively = find(obj.Child[i], search);
        if(foundRecursively) // match found! return up the chain
            return foundRecursively; 
    }
    // no match, return up the chain
    return false;
};

var Lineal_Descendant = function(A,B){
    // find the B (the parent) in data, then find A in B.  
    // Convert any object into a boolean and return.
    return !!find(find(data[0],B),A);
};

Lineal_Descendant("Sedan","Civic") // true
Lineal_Descendant("Sedan","Toyota") // false
Lineal_Descendant("Prius","Honda") // false
Lineal_Descendant("Yaris","Car") // true

This solution assumes that the data is an array with 1 root Object (as shown by OP in the sample data). Nonetheless, it can be easily modified to handle an array of roots at the outset.

Answer 10

Before anything else,

Absolutely do not utilize `"Object"` as a key on an `Object`.

You are dangerously close to accidentally overwriting the native javascript Object which would result in the dreaded javascript apocalypse. I recommend using name instead.

Furthermore, this issue can be resolved with a fairly straightforward recursive function:

var find = function(obj, search){
    // return this object if it matches
    if(obj.name === search)
      return obj;
    // false if it has no children
    if(!obj.hasOwnProperty('Child')) 
      return false;
    for(var i=0,u=obj.Child.length;i<u;i++){
        // recursively check each child
        var foundRecursively = find(obj.Child[i], search);
        if(foundRecursively) // match found! return up the chain
            return foundRecursively; 
    }
    // no match, return up the chain
    return false;
};

var Lineal_Descendant = function(A,B){
    // find the B (the parent) in data, then find A in B.  
    // Convert any object into a boolean and return.
    return !!find(find(data[0],B),A);
};

Lineal_Descendant("Sedan","Civic") // true
Lineal_Descendant("Sedan","Toyota") // false
Lineal_Descendant("Prius","Honda") // false
Lineal_Descendant("Yaris","Car") // true

This solution assumes that the data is an array with 1 root Object (as shown by OP in the sample data). Nonetheless, it can be easily modified to handle an array of roots at the outset.

Successor in a JavaScript array with multiple dimensions

Answer №1

Answer №2

Answer №3

Answer №4

Answer №5

Absolutely do not utilize `"Object"` as a key on an `Object`.

Similar questions

Server-side issue: Ajax POST request returns an empty POST array

In JavaScript, the function will return a different object if the string in an array matches the

What is the best way to use the $push operation to add an object to an array within a mongoDB database using Node.js

Error: The variable "weather" is not defined while using React with the weatherbit API

Issues with the proper functionality of the .ajax() method in Django

Updating information within AngularJS select boxes

Transforming a string representation of a nested array into an actual nested array with the help of JavaScript

Page redirects automatically after AJAX call

What is the best way to format table values as currency?

Retrieving values with Jquery on a function's onClick event

Receiving serialized post data in array on RESTful Server using CodeIgniter

Include a new class in the classList of an element at a specific index

Is it possible to preserve the <canvas> elements to use for future animation frames?

The fusion of Combining Forms, JSON, AJAX, PHP, and Google graphs

Explore by the anchor tag

What is the most effective method to extract an ID from a URL that is written in various formats?

typescript error is not defined

CSS - Achieving full width on hover even when the element has a specified width setting

Implementing setInterval in ReactJS to create a countdown timer

Identify the absence of search results in an Ajax request to the search page before rendering the HTML content

Successor in a JavaScript array with multiple dimensions

Answer №1

Answer №2

Answer №3

Answer №4

Answer №5

Absolutely do not utilize "Object" as a key on an Object.

Similar questions

Server-side issue: Ajax POST request returns an empty POST array

In JavaScript, the function will return a different object if the string in an array matches the

What is the best way to use the $push operation to add an object to an array within a mongoDB database using Node.js

Error: The variable "weather" is not defined while using React with the weatherbit API

Issues with the proper functionality of the .ajax() method in Django

Updating information within AngularJS select boxes

Transforming a string representation of a nested array into an actual nested array with the help of JavaScript

Page redirects automatically after AJAX call

What is the best way to format table values as currency?

Retrieving values with Jquery on a function's onClick event

Receiving serialized post data in array on RESTful Server using CodeIgniter

Include a new class in the classList of an element at a specific index

Is it possible to preserve the <canvas> elements to use for future animation frames?

The fusion of Combining Forms, JSON, AJAX, PHP, and Google graphs

Explore by the anchor tag

What is the most effective method to extract an ID from a URL that is written in various formats?

typescript error is not defined

CSS - Achieving full width on hover even when the element has a specified width setting

Implementing setInterval in ReactJS to create a countdown timer

Identify the absence of search results in an Ajax request to the search page before rendering the HTML content

Absolutely do not utilize `"Object"` as a key on an `Object`.