2

I have following JSON.

[{
    "ID": "Root_1",
    "Name": "Root_1",                   
    "ParentID": "",
    "Sequent": 1
},
{
    "ID": "Root_2",
    "Name": "Root_2",                   
    "ParentID": "",
    "Sequent": 2
},              
{
    "ID": "Root_1_Sub_1_Child_1",
    "Name": "Root_1_Sub_1_Child_1",                 
    "ParentID": "Root_1_Sub_1",
    "Sequent": 1
},
{
    "ID": "Root_1_Sub_1_Child_2",
    "Name": "Root_1_Sub_1_Child_2",                 
    "ParentID": "Root_1_Sub_1",
    "Sequent": 2
},
{
    "ID": "Root_1_Sub_1",
    "Name": "Root_1_Sub_1",                 
    "ParentID": "Root_1",
    "Sequent": 1
}]

I want to change my JSON to as following.

[{
    "ID": "Root_1",
    "Name": "Root_1",
    "ParentID": "",
    "Sequent": 1,
    "Sub": [{
        "ID": "Root_1_Sub_1",
        "Name": "Root_1_Sub_1",
        "ParentID": "Root_1",
        "Sequent": 1,
        "Sub": [{
            "ID": "Root_1_Sub_1_Child_1",
            "Name": "Root_1_Sub_1_Child_1",
            "ParentID": "Root_1_Sub_1",
            "Sequent": 1            
        },
        {
            "ID": "Root_1_Sub_1_Child_2",
            "Name": "Root_1_Sub_1_Child_2",
            "ParentID": "Root_1_Sub_1",
            "Sequent": 2            
        }]
    }]
},
{
    "ID": "Root_2",
    "Name": "Root_2",                   
    "ParentID": "",
    "Sequent": 2
}]

After I trying following way, the result is not what I want.

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    <script src="./bower_components/angular/angular.min.js"></script>       
    <script>
            angular.module('myApp', [])
            .controller('MyCtrl', function($scope, $http) {

                $scope.ProjectCategoryList_FlatStyle = [{
                    "ID": "Root_1",
                    "Name": "Root_1",                   
                    "ParentID": "",
                    "Sequent": 1
                },
                {
                    "ID": "Root_2",
                    "Name": "Root_2",                   
                    "ParentID": "",
                    "Sequent": 2
                },              
                {
                    "ID": "Root_1_Sub_1_Child_1",
                    "Name": "Root_1_Sub_1_Child_1",                 
                    "ParentID": "Root_1_Sub_1",
                    "Sequent": 1
                },
                {
                    "ID": "Root_1_Sub_1_Child_2",
                    "Name": "Root_1_Sub_1_Child_2",                 
                    "ParentID": "Root_1_Sub_1",
                    "Sequent": 2
                },
                {
                    "ID": "Root_1_Sub_1",
                    "Name": "Root_1_Sub_1",                 
                    "ParentID": "Root_1",
                    "Sequent": 1
                }];


                $scope.ProjectCategoryList_TreeStyle = [];
                $scope.ParentArray = [];
                $scope.ConvertFlatToTree = function(Value){ 
                    angular.forEach(Value, function(item){                      

                            // Create row.                                                  
                            var  _Object = new Object();
                            _Object.ID = item.ID;
                            _Object.Name = item.Name;                           
                            _Object.ParentID = item.ParentID;
                            _Object.Sequent = item.Sequent;
                            _Object.Sub = [];

                            // Checking if it is root element.
                            if(item.ParentID){
                                // It is for child node.
                                // Get Parent Element.
                                var ParentElement = $scope.ParentArray.filter(function (x) { return x.ID === item.ParentID; });
                                ParentElement[0].Sub.push(_Object);
                                $scope.ParentArray.push(_Object);                               
                            }else{
                                // It is for parent node.
                                // Get child elements.
                                var ChildElementArray = $scope.ProjectCategoryList_FlatStyle.filter(function (x) { return x.ParentID === item.ID; });
                                if(ChildElementArray.length != 0){                                  
                                    $scope.ParentArray.push(_Object);
                                    $scope.ProjectCategoryList_TreeStyle.push(_Object); 
                                    $scope.ConvertFlatToTree(ChildElementArray);
                                }
                            }
                   })
                   console.log("ProjectCategoryList_TreeStyle = ", JSON.stringify($scope.ProjectCategoryList_TreeStyle));
                }
                $scope.ConvertFlatToTree($scope.ProjectCategoryList_FlatStyle);
            });
    </script>   
</head>
<body ng-app="myApp" ng-controller="MyCtrl">    
</body>
</html>

Below is my final result.

[{
    "ID": "Root_1",
    "Name": "Root_1",
    "ParentID": "",
    "Sequent": 1,
    "Sub": [{
        "ID": "Root_1_Sub_1",
        "Name": "Root_1_Sub_1",
        "ParentID": "Root_1",
        "Sequent": 1,
        "Sub": [{
            "ID": "Root_1_Sub_1_Child_1",
            "Name": "Root_1_Sub_1_Child_1",
            "ParentID": "Root_1_Sub_1",
            "Sequent": 1,
            "Sub": []
        },
        {
            "ID": "Root_1_Sub_1_Child_2",
            "Name": "Root_1_Sub_1_Child_2",
            "ParentID": "Root_1_Sub_1",
            "Sequent": 2,
            "Sub": []
        }]
    },
    {
        "ID": "Root_1_Sub_1",
        "Name": "Root_1_Sub_1",
        "ParentID": "Root_1",
        "Sequent": 1,
        "Sub": []
    }]
}]

Plunker

Improve this question
1
  • You can try implementing a previous answer of mine to a very similar question. stackoverflow.com/a/36942348/4543207 Later i will try to answer this one as well. Commented May 13, 2016 at 6:22

1 Answer 1

Reset to default
7

Here is your solution. However it could have been much better if you had your ID and parentID naming conventions better. Instead of doing tons of recursive runs i just sorted the input data first then did the job sequentially.

var flat = [{
    "ID": "Root_1",
    "Name": "Root_1",                   
    "ParentID": "",
    "Sequent": 1
},
{
    "ID": "Root_2",
    "Name": "Root_2",                   
    "ParentID": "",
    "Sequent": 2
},              
{
    "ID": "Root_1_Sub_1_Child_1",
    "Name": "Root_1_Sub_1_Child_1",                 
    "ParentID": "Root_1_Sub_1",
    "Sequent": 1
},
{
    "ID": "Root_1_Sub_1_Child_2",
    "Name": "Root_1_Sub_1_Child_2",                 
    "ParentID": "Root_1_Sub_1",
    "Sequent": 2
},
{
    "ID": "Root_1_Sub_1",
    "Name": "Root_1_Sub_1",                 
    "ParentID": "Root_1",
    "Sequent": 1
}];
function nested(f){
  return f.sort((a,b) => a.ID.length < b.ID.length ? 1 : a.ID.length == b.ID.length ? a.ID < b.ID ? -1 : 1 :-1)
          .reduce((p,c,i,a) => {var parent = !!c.ParentID && a.find(e => e.ID === c.ParentID);
                                !!parent ? !!parent.Sub && parent.Sub.push(c) || (parent.Sub=[c]) : p.push(c);
                                return p;},[]);
};
document.write("<pre>" +  JSON.stringify(nested(flat),null,2) + "</pre>");

OK as per your comment i decided to find a solution to nest a flat array when there is absolutely no information other than parental relationship. I mean the array item properties can be of two type. 

[{id: AY998, pid: FT497}, {id: SS113, pid: MN857}, {id: MN857, pid: "root"}, {id: FT497...

where id is the id of the element, pid is the parents id and some objects are root and there is no other information like level etc.

So the idea is to sort the array on parental seniority which means no parent will be listed after it's children. Accordingly once the sort is done a nesting can easily be done by a reverse iteration.

Ok lets create an shuffled array of 100 items of such a nature. (I actually had to create such a code to generate a data array of items with unique id's and proper parental relationship. Lets see the code

var flat = [
      { id: 'KR807', pid: 'UT731' },
      { id: 'DW402', pid: 'root' },
      { id: 'ID042', pid: 'RR203' },
      { id: 'ZT645', pid: 'CP292' },
      { id: 'LD796', pid: 'WI018' },
      { id: 'KH280', pid: 'JO343' },
      { id: 'EC894', pid: 'DX943' },
      { id: 'CR293', pid: 'VT921' },
      { id: 'XI611', pid: 'RQ903' },
      { id: 'YG388', pid: 'VN945' },
      { id: 'ZL243', pid: 'AA689' },
      { id: 'VK295', pid: 'CM110' },
      { id: 'CD374', pid: 'VK295' },
      { id: 'XO588', pid: 'ZL243' },
      { id: 'OM916', pid: 'WI018' },
      { id: 'JQ797', pid: 'CM110' },
      { id: 'BF782', pid: 'root' },
      { id: 'EK012', pid: 'VK295' },
      { id: 'AD556', pid: 'PK567' },
      { id: 'LA463', pid: 'KJ237' },
      { id: 'EL156', pid: 'MT394' },
      { id: 'VE720', pid: 'YG388' },
      { id: 'MT364', pid: 'CD374' },
      { id: 'JO343', pid: 'RJ027' },
      { id: 'QQ957', pid: 'PY806' },
      { id: 'UT731', pid: 'MT394' },
      { id: 'NA571', pid: 'OM916' },
      { id: 'NK641', pid: 'VT921' },
      { id: 'YX336', pid: 'FN157' },
      { id: 'RO244', pid: 'VT921' },
      { id: 'BJ784', pid: 'NA571' },
      { id: 'RJ027', pid: 'NH992' },
      { id: 'ZZ311', pid: 'EE630' },
      { id: 'CK935', pid: 'DX943' },
      { id: 'GF710', pid: 'PY806' },
      { id: 'WZ371', pid: 'MU258' },
      { id: 'IM089', pid: 'GL915' },
      { id: 'GN046', pid: 'NH992' },
      { id: 'MT394', pid: 'root' },
      { id: 'OC487', pid: 'WI018' },
      { id: 'KQ384', pid: 'AD556' },
      { id: 'VZ391', pid: 'ZS119' },
      { id: 'VT921', pid: 'MT394' },
      { id: 'OP416', pid: 'HT085' },
      { id: 'QU319', pid: 'ID042' },
      { id: 'SG270', pid: 'CP292' },
      { id: 'BG562', pid: 'WJ207' },
      { id: 'DX943', pid: 'NK641' },
      { id: 'II920', pid: 'UT731' },
      { id: 'AX150', pid: 'JO343' },
      { id: 'TO181', pid: 'YG388' },
      { id: 'WI985', pid: 'VK295' },
      { id: 'DU020', pid: 'VK225' },
      { id: 'RQ903', pid: 'EL156' },
      { id: 'EP215', pid: 'PK567' },
      { id: 'CZ627', pid: 'PY783' },
      { id: 'MU258', pid: 'GL915' },
      { id: 'MC556', pid: 'XI611' },
      { id: 'XX495', pid: 'II920' },
      { id: 'KJ237', pid: 'YG388' },
      { id: 'CP292', pid: 'UT731' },
      { id: 'MH665', pid: 'EL156' },
      { id: 'VK225', pid: 'FN157' },
      { id: 'FU290', pid: 'AX150' },
      { id: 'EE630', pid: 'GL915' },
      { id: 'VN945', pid: 'root' },
      { id: 'PK567', pid: 'VT921' },
      { id: 'PY806', pid: 'NH992' },
      { id: 'FN157', pid: 'GL915' },
      { id: 'DB935', pid: 'root' },
      { id: 'WK936', pid: 'ZL243' },
      { id: 'PY783', pid: 'WJ207' },
      { id: 'WJ207', pid: 'RO244' },
      { id: 'UR082', pid: 'VT921' },
      { id: 'AR742', pid: 'CD374' },
      { id: 'LS455', pid: 'IM089' },
      { id: 'GH814', pid: 'EL156' },
      { id: 'DX929', pid: 'II920' },
      { id: 'YR376', pid: 'CD374' },
      { id: 'EJ895', pid: 'XO588' },
      { id: 'ND802', pid: 'FU290' },
      { id: 'ZS119', pid: 'GD350' },
      { id: 'GD350', pid: 'YG388' },
      { id: 'HT085', pid: 'GL915' },
      { id: 'RR203', pid: 'AA689' },
      { id: 'IC103', pid: 'KR807' },
      { id: 'XT553', pid: 'WZ371' },
      { id: 'JZ880', pid: 'EL156' },
      { id: 'AA689', pid: 'EP215' },
      { id: 'TJ550', pid: 'RJ027' },
      { id: 'GL915', pid: 'root' },
      { id: 'BI123', pid: 'GD350' },
      { id: 'LD710', pid: 'JZ880' },
      { id: 'MQ351', pid: 'AD556' },
      { id: 'WI018', pid: 'NH992' },
      { id: 'KC160', pid: 'AD556' },
      { id: 'CM110', pid: 'root' },
      { id: 'OK014', pid: 'GH814' },
      { id: 'FD929', pid: 'VK225' },
      { id: 'NH992', pid: 'PK567' }
];

function construct(ar){
  var lut = {},
   sorted = [];
  function sort(a){
  	var len = a.length,
  	    fix = -1;
  	for (var i = 0; i < len; i++ ){
  	  while (!!~(fix = a.findIndex(e => a[i].pid == e.id)) && fix > i)
            [a[i],a[fix]] = [a[fix],a[i]]; // ES6 swap
  	  lut[a[i].id]=i;
  	}console.log(lut); //check LUT on the console.
  	return a;
  }
  sorted = sort(ar.slice(0)); // don't modify things that don't belong to you :)
  for (var i = sorted.length-1; i >= 0; i--){
  	if (sorted[i].pid != "root") {
  	  !!sorted[lut[sorted[i].pid]].children && sorted[lut[sorted[i].pid]].children.push(sorted.splice(i,1)[0])
  	                                        || (sorted[lut[sorted[i].pid]].children = [sorted.splice(i,1)[0]]);
  	}
  }
  return sorted;
}
document.write("<pre>" + JSON.stringify(construct(flat),null,2) + "</pre>");

So it works nice and fast. The key is the sort algorithm. As mentioned before it sorts the array according to the parental seniority and no child can come before it's parent. This is the only condition. But at the same time it prepares a LUT (hash list) of the parent id's indexes so that once we start reverse iterating the array (from last item to first) it avoids us from doing expensive searches for the parent. Instead we will look it's index up from the LUT (look up table) object and inserts it's children if any. Very fast..!

So here is the repl.it for you to play.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

I up voted for your helpful suggestion. I do appreciated that. But I am sorry to say that ID and ParentID are GUID 36 Digit. I don't want anyone to be confused seeing GUIDs. So I modified it as user readable format. Sorry about that.
@Frank Myat Thu : No worries that's very fine. When constructing the nested structure from a flat structure, being able to have the items sorted according to their ancestor seniority (or depth level) is enormously helpful. Then as you see it's just a simple Array.prototype.reduce() job. Otherwise... a recursive job might be needed but something cleverer than a tree walk since in big structures simple tree walks might yield long coffee breaks. I will think about it.
@Frank Myat Thu: OK i have modified the code to handle an emulation of your data structure. Please see the edit of my answer for details. I hope it helps you.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.