Creating Hierarchy Using Id And Parentid

Possible duplicate, but this one unlike other questions does not wish to hook objects to another. I would want to create a new objects/array containing the hierarchy data So I have

Solution 1:

Your problem requires traversing your dependency tree while keeping track of the depth. You can solve the problem using a depth-first-traversal implemented using recursion and incrementing the depth.

Update: Alright, you wanted some more explanation, some more explanation you'll get.

Also, can you provide some links to where I can study these kinds of concepts? Your approach is very new to me

This problem cam be solved using recursion. I'll explain the code and drop in some links to the concepts.

---

Transform sets to hashMap

The first thing I'm doing is transforming your sets object to another object which I'm calling hashMap. I'm transforming it to this form because it will make "look-ups" faster when we're creating the tier object.

Here is the sets object for reference:

const sets = {
  'dataSet1': {
    'ID': '1',
    'ParentID': '0'
  },

  'dataSet2': {
    'ID': '2',
    'ParentID': '1'
  },

  'dataSet3': {
    'ID': '3',
    'ParentID': '1'
  },

  'dataSet4': {
    'ID': '4',
    'ParentID': '3'
  }
};

And I perform this transformation:

const hashMap = (Object// 1
  .keys(sets)
  // 2
  .map(datasetKey => ({
    originalKey: datasetKey,
    id: sets[datasetKey].ID,
    parentId: sets[datasetKey].ParentID
  }))
  // 3
  .reduce((hashMap, value) => {
    // 4const hashMapKey = 'hasParentId' + value.parentId;
    // 5if (!hashMap[hashMapKey]) {
      hashMap[hashMapKey] = [];
    }
    // 6
    hashMap[hashMapKey].push(value);
    // 7return hashMap;
  }, {})
);

which results in this object:

{"hasParentId0":[{"originalKey":"dataSet1","id":"1","parentId":"0"}],"hasParentId1":[{"originalKey":"dataSet2","id":"2","parentId":"1"},{"originalKey":"dataSet3","id":"3","parentId":"1"}],"hasParentId3":[{"originalKey":"dataSet4","id":"4","parentId":"3"}]}

So step by step:

1. Use Object.keys to get an array of keys from the object sets
2. Use Array.prototype.map to map each key of the array create from calling Object.keys to a new object. This object has 3 properties: originalKey, id, parentId
3. Use Array.prototype.reduce to reduce the array of mapped objects (created in the last step) into a single object. The first parameter of Array.prototype.reduce is a "reducer" function that takes two arguments. The first argument of the "reducer" function is an "accumulator" and the second argument is an item from your array. The reducer will be called multiple times, one call for each item in the array. The reducer function returns an accumulator and that accumulator will be used in the next call of this inner function (so all the items of the array reduce into the accumulator). The second argument of Array.prototype.reduce is the initial accumulator. In this case, the initial accumulator is an empty object {}.
4. Inside the reducer function, we create a string hashMapKey. This string will be used as the key to the accumulator.
5. This transformation expects every hashMap[hashMapKey] to be an array. Here we check to see if the value at hashMap[hashMapKey] is an array and if it isn't we make it one.
6. Now that we know there is an array at hashMap[hashMapKey], we can push the value on that array. Remember that the value is an object we mapped from step 2.
7. Return the modified hashMap to be used as the "accumulator" of the next "reducer" call.

When the reduction is finished, the hashMap contains the correct transformation. The transformation to sets to hashMap is required for fast lookups in the next step.

Transform hashMap to tier

The above structure has an implied graph where each node (aka point) is an object from sets and each edge is a directed relationship via the property ParentID.

In order to create the structure you want, you need to perform a depth-first-traversal traversing this graph while keeping track of the depth.

Here is the code:

// 1const tier = {};
let maxDepth = 0;

// 2functiontraverse(currentParentId, depth) {
  // 3if (depth > maxDepth) {
    maxDepth = depth;
  }
  // 4const childrenOfCurrentParent = hashMap['hasParentId' + currentParentId]

  // 5if (!childrenOfCurrentParent) {
    return;
  }

  // 6
  childrenOfCurrentParent.forEach(value => {
    // 7const tierKey = 'tier' + depth;
    if (!tier[tierKey]) {
      tier[tierKey] = [];
    }
    // 8
    tier[tierKey].push(value);
    // 9traverse(value.id, depth + 1);
  });
}

1. create an empty object to store the tiers. Optionally create a variable for the hold the max depth. This is useful if you want to convert the tiers object into a tiers array.
2. define a function traverse that takes two arguments: currentParentId and depth. The currentParentId is the key used to identify the id of the current parent. This function is initially called with a currentParentId of 0 and a depth of 0. This will make more sense once we look at the implementation of the code.
3. Reassign maxDepth
4. Grab the childrenOfCurrentParent from the lookup table. See why we made it? Looking up values in this table is very fast :)
5. If there isn't any childrenOfCurrentParent, don't do anything.
6. Use Array.prototype.forEach to iterate through the childrenOfCurrentParent. The value again is the value of the mapped objects from the transformation.
7. create a tierKey to store the value in. If the array isn't initialized, initialize it.
8. push the value
9. Use recursion, call the traverse function again from within itself changing the currentParrentId and incrementing the depth. Repeat from step 3 until there are no more items to be placed. This is depth-first-traversal.

---

Transforming tier to tierArray

I think this one is self-explanatory. Since the tiers are a set of ordered items, it might be better to store it in an array. This is why we kept track of the maxDepth.

---

Working snippet

const sets = {
  'dataSet1': {
    'ID': '1',
    'ParentID': '0'
  },

  'dataSet2': {
    'ID': '2',
    'ParentID': '1'
  },

  'dataSet3': {
    'ID': '3',
    'ParentID': '1'
  },

  'dataSet4': {
    'ID': '4',
    'ParentID': '3'
  }
};

// `hashMap` is a data transform// see the `console.log` of this transformconst hashMap = (Object// grab the keys of the object `sets`
  .keys(sets)
  // then map every key to a new object
  .map(datasetKey => ({
    originalKey: datasetKey,
    id: sets[datasetKey].ID,
    parentId: sets[datasetKey].ParentID
  }))
  // reduce the new objects into a single object
  .reduce((hashMap, value) => {
    // create a key to store the `value`const hashMapKey = 'hasParentId' + value.parentId;
    // if `hashMap[hashMapKey]` isn't initialized yet,// initialize it to an arrayif (!hashMap[hashMapKey]) {
      hashMap[hashMapKey] = [];
    }
    // then push the value (the objects created above)
    hashMap[hashMapKey].push(value);
    // return the hashMapreturn hashMap;
  }, {})
);

console.log('hashMap', hashMap);

// create an object to store the `tier`s in.const tier = {};
// keep track of the `maxDepth` in case you want to transform `tier` to an arraylet maxDepth = 0;

// this is a recursive function to traverse your graph// this implements a depth-first-traversal keeping track of the `depth`functiontraverse(currentParentId, depth) {
  if (depth > maxDepth) {
    maxDepth = depth;
  }
  const childrenOfCurrentParent = hashMap['hasParentId' + currentParentId]

  // if there are no children of the currentParentif (!childrenOfCurrentParent) {
    return;
  }

  childrenOfCurrentParent.forEach(value => {
    const tierKey = 'tier' + depth;
    if (!tier[tierKey]) {
      tier[tierKey] = [];
    }
    tier[tierKey].push(value);
    traverse(value.id, depth + 1);
  });
}

// call the function to start the traversal// using 0 as the first `currentParentId` and// using 0 as the first `depth` valuetraverse(0, 0);


// the tier object is now createdconsole.log('tier', tier);

// but it might be more natural to have `tier` as an arrayconst tierArray = [];
for (let i = 0; i < maxDepth; i += 1) {
  tierArray[i] = tier['tier' + i];
}

console.log('tierArray', tierArray);

Phew, what an answer. Hope this helps!

Solution 2:

The problem with your if condition in your for loop. It only proccess the top level element if (datasetobj[x]['ParentID'] == 0) only processes parent id 0.

To get what you're after dynamically create hierarchy arrays and remove the if condition. Do something like:

var tiers = {};
      var sets = {
        'dataSet1': {
            'ID': '1',
            'ParentID': '0'
        },
    
        'dataSet2': {
            'ID': '2',
            'ParentID': '1'
        },
    
        'dataSet3': {
            'ID': '3',
            'ParentID': '1'
        },
    
         'dataSet4': {
             'ID': '4',
             'ParentID': '3'
        }
    };
    var datasetobj = sets;
    var hierarchy = tiers;
    for (x in datasetobj) {
            if (datasetobj[x]['ParentID']) { 
                var idx = 'tier'+datasetobj[x]['ParentID'];
                if(!hierarchy[idx])
                    hierarchy[idx]=[];
                hierarchy[idx].push({
                    'parentid': datasetobj[x]['ParentID'],
                    'id': datasetobj[x]['ID']
                });
            }
        };
    console.log(tiers);