Transform a one-dimensional array arranged in ASCII order into a hierarchical array structure using Javascript

Question

Transform a one-dimensional array arranged in ASCII order into a hierarchical array structure using Javascript

Consider the array of objects below, sorted by the code property in ascending ASCII order:

var codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

Is there a way to transform this into a nested array structure like so :

var nestedCodes = [
    {
        code: '01',
        children: [
            { code: '0101' },
            {
                code: '0102',
                children: [
                    { code: '010201' }
                ]
            },
            { code: '0103' }
        ]
    },
    {
        code: '02',
        children: [
            { code: '0201' },
            { code: '0202' }
        ]
    }
];

The organization of codes involves combining multiple 0N, where N could range from 1 to 9. It's worth noting that the codes are retrieved from a server and may have additional properties apart from code, such as title, which is irrelevant to this issue.

The primary objective here is to create a suitable format for use with jsTree.

javascript arrays jstree

Answer 1

Answer №1

To achieve this task, you can utilize a recursive approach. The strategy involves keeping track of the path (obtained as an array through String.prototype.match using a regex) and the parent where you intend to insert the code for each iteration of the recursive function.

The parent variable denotes the specific node to select in the current recursive call, while the path aids in constructing the hierarchy by delving deeper into the nested elements:

function insert(d, path, parent, arr) {
  if (path.length === 0) {
    arr.push(Object.assign({}, d));
    return;
  }
  var target = arr.find(e => e.code === parent);
  target.children = target.children || [];
  insert(d, path.slice(1), parent + path[0], target.children);
}

var codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

var res = codes.reduce((a, c) => {
  var p = c.code.match(/(0[1-9])/g);
  insert(c, p.slice(1), p[0], a);
  return a;
}, []);

console.log(res);

It is crucial to note that the implementation assumes that the parent of a particular code has already been inserted earlier in the process.

Answer 2

To achieve this task, you can utilize a recursive approach. The strategy involves keeping track of the path (obtained as an array through String.prototype.match using a regex) and the parent where you intend to insert the code for each iteration of the recursive function.

The parent variable denotes the specific node to select in the current recursive call, while the path aids in constructing the hierarchy by delving deeper into the nested elements:

function insert(d, path, parent, arr) {
  if (path.length === 0) {
    arr.push(Object.assign({}, d));
    return;
  }
  var target = arr.find(e => e.code === parent);
  target.children = target.children || [];
  insert(d, path.slice(1), parent + path[0], target.children);
}

var codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

var res = codes.reduce((a, c) => {
  var p = c.code.match(/(0[1-9])/g);
  insert(c, p.slice(1), p[0], a);
  return a;
}, []);

console.log(res);

It is crucial to note that the implementation assumes that the parent of a particular code has already been inserted earlier in the process.

Answer 3

Answer №2

It was a challenge for me to create the recursive function needed to construct the desired structure. I found the solution here

In order to achieve this, it's necessary to include a parent property in each element of the codes array. My approach involved assuming that each code has a parent which is essentially the same code, except for the last two characters.

var codes = [{code: '01'    },
             {code: '0101'  },
             {code: '0102'  },
             {code: '010201'},
             {code: '0103'  },
             {code: '02'    },
             {code: '0201'  },
             {code: '0202'  },
          ];

// adding parents to each code
codes.forEach(function(c) {
  if (c.code.length > 2) {
    c.parent = c.code.substr(0, c.code.length - 2);
  } else {
    c.parent = 'root';
  }
});



function find_children(arr, parent) {
  var output = [];
  for (var i in arr) {
    
    if (arr[i].parent == parent) {
      
      var children = find_children(arr, arr[i].code);

      if (children.length) {
        arr[i].children = children;
      }
      output.push(arr[i])
    }
  }
  return output;
}

var nested = find_children(codes,'root');
console.log(nested);

Answer 4

It was a challenge for me to create the recursive function needed to construct the desired structure. I found the solution here

In order to achieve this, it's necessary to include a parent property in each element of the codes array. My approach involved assuming that each code has a parent which is essentially the same code, except for the last two characters.

var codes = [{code: '01'    },
             {code: '0101'  },
             {code: '0102'  },
             {code: '010201'},
             {code: '0103'  },
             {code: '02'    },
             {code: '0201'  },
             {code: '0202'  },
          ];

// adding parents to each code
codes.forEach(function(c) {
  if (c.code.length > 2) {
    c.parent = c.code.substr(0, c.code.length - 2);
  } else {
    c.parent = 'root';
  }
});



function find_children(arr, parent) {
  var output = [];
  for (var i in arr) {
    
    if (arr[i].parent == parent) {
      
      var children = find_children(arr, arr[i].code);

      if (children.length) {
        arr[i].children = children;
      }
      output.push(arr[i])
    }
  }
  return output;
}

var nested = find_children(codes,'root');
console.log(nested);

Answer 5

Answer №3

The code provided may seem a bit lengthy at first glance, but it is actually quite easy to comprehend. It boasts high robustness by not requiring the array to be sorted and can process strings like "0102" without needing "01" to exist beforehand. While the code could be shorter if these cases were not handled, I included them for your convenience.

To begin, an object-based tree data structure is generated from the input data. This tree is efficient due to its O(1) index access. Subsequently, the object-based tree is converted into the final array-based tree by traversing each layer of the object-based tree and transforming them into arrays.

Recursion plays a significant role in this implementation as it proves to be ideal for both creating and navigating through trees efficiently.

In comparison to other solutions, my algorithm exhibits superior time complexity thanks to the creation of a dictionary/object that allows for O(1) access during tree generation. On the contrary, alternative algorithms perform searches within each layer, resulting in inefficiency. My approach operates in O(N) time complexity, whereas others found here are shorter yet run in O(N^2).

You can simply copy the format function into your project and utilize it seamlessly.

const codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

function format(codes) {
  // Splits the string into an array of 2-character strings.
  const SPLIT_REGEX = /.{2}(?=(.{2})+(?!.))|.{2}$/g;
  const codeFragments = codes.map(obj => obj.code.match(SPLIT_REGEX));

  // 1. Represent the data as a tree which is more efficient to build.
  const tree = {};
  function createTree(tree, fragments) {
    let node = tree;
    fragments.forEach(fragment => {
      if (!node[fragment]) {
        node[fragment] = {};
      }
      node = node[fragment];
    });
  }
  codeFragments.forEach(fragments => createTree(tree, fragments));
  
  // 2. Convert the tree structure into the desired format.
  function generateCodesFromTree(tree, previous) {
    const nestedCodes = [];
    Object.keys(tree).forEach(treeNode => {
      const code = previous + treeNode;
      const children = generateCodesFromTree(tree[treeNode], code);
      const nestedCode = { code };
      if (children.length > 0) {
        nestedCode.children = children;
      }
      nestedCodes.push(nestedCode);
    });
    return nestedCodes;
  }

  return generateCodesFromTree(tree, '');
}

console.log(format(codes));

Answer 6

The code provided may seem a bit lengthy at first glance, but it is actually quite easy to comprehend. It boasts high robustness by not requiring the array to be sorted and can process strings like "0102" without needing "01" to exist beforehand. While the code could be shorter if these cases were not handled, I included them for your convenience.

To begin, an object-based tree data structure is generated from the input data. This tree is efficient due to its O(1) index access. Subsequently, the object-based tree is converted into the final array-based tree by traversing each layer of the object-based tree and transforming them into arrays.

Recursion plays a significant role in this implementation as it proves to be ideal for both creating and navigating through trees efficiently.

In comparison to other solutions, my algorithm exhibits superior time complexity thanks to the creation of a dictionary/object that allows for O(1) access during tree generation. On the contrary, alternative algorithms perform searches within each layer, resulting in inefficiency. My approach operates in O(N) time complexity, whereas others found here are shorter yet run in O(N^2).

You can simply copy the format function into your project and utilize it seamlessly.

const codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

function format(codes) {
  // Splits the string into an array of 2-character strings.
  const SPLIT_REGEX = /.{2}(?=(.{2})+(?!.))|.{2}$/g;
  const codeFragments = codes.map(obj => obj.code.match(SPLIT_REGEX));

  // 1. Represent the data as a tree which is more efficient to build.
  const tree = {};
  function createTree(tree, fragments) {
    let node = tree;
    fragments.forEach(fragment => {
      if (!node[fragment]) {
        node[fragment] = {};
      }
      node = node[fragment];
    });
  }
  codeFragments.forEach(fragments => createTree(tree, fragments));
  
  // 2. Convert the tree structure into the desired format.
  function generateCodesFromTree(tree, previous) {
    const nestedCodes = [];
    Object.keys(tree).forEach(treeNode => {
      const code = previous + treeNode;
      const children = generateCodesFromTree(tree[treeNode], code);
      const nestedCode = { code };
      if (children.length > 0) {
        nestedCode.children = children;
      }
      nestedCodes.push(nestedCode);
    });
    return nestedCodes;
  }

  return generateCodesFromTree(tree, '');
}

console.log(format(codes));

Answer 7

Answer №4

To solve this problem, one must take a recursive approach. Give the following solution a try:

let codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

roots = codes.filter(c => c.code.length === 2);

roots.forEach(c => assign(c));

console.log(roots);

function assign(code) {
  codes.forEach(c => {
    if (c !== code) {
      if (code.code === c.code.slice(0, code.code.length)) {
        code.children = !code.children ? [c] : [...code.children, c];
        assign(code.children[code.children.length - 1]);
      }
    }
  });
}

Answer 8

To solve this problem, one must take a recursive approach. Give the following solution a try:

let codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

roots = codes.filter(c => c.code.length === 2);

roots.forEach(c => assign(c));

console.log(roots);

function assign(code) {
  codes.forEach(c => {
    if (c !== code) {
      if (code.code === c.code.slice(0, code.code.length)) {
        code.children = !code.children ? [c] : [...code.children, c];
        assign(code.children[code.children.length - 1]);
      }
    }
  });
}

Transform a one-dimensional array arranged in ASCII order into a hierarchical array structure using Javascript

Answer №1

Answer №2

Answer №3

Answer №4

Similar questions

Utilizing Selenium and Python to extract data from JavaScript tables via web scraping

What is the best way to place a div within another div?

Ways to append multiple values to an object ID in mongoDB at a later time

What is the best way to keep an image centered in the nav-bar as it decreases in size?

Unexpected outcome when utilizing localeCompare options in Node.js

Integrate Tailwind CSS into the bundled JavaScript file

Discover the simple steps to generating dynamic variables with jQuery!

Summing values in es6 (TypeScript) without explicitly knowing their corresponding keys

Handling dynamic routes with React Router 4 and the 404 path

Use Jquery to insert HTML content after every third iteration of a for loop

I'm struggling to activate the eventListener on several elements with the same className or ID. Unfortunately, only the initial child is being triggered in my current code implementation

Retrieve a string value in Next.JS without using quotation marks

Is there a way for me to generate a custom subtype of Error that can be thrown?

Determine all checkboxes in a table that are selected if the rows contain a display style tag using Javascript

What is the best way to access data stored in the state of the store.js within a Vue application?

Guide to enabling cross-domain uploads of files

Creating an array object in JavaScript using an integer variable involves utilizing the integer as the

Adjust the CSS for the "a" tag's "title" attribute

Sorting nested JSON by property with NodeJS

Managing Time Before Browser Refresh in AngularLearn how to monitor and examine the time remaining before