How to create such a kind of data structure?

[CoolCaptain]

First of all:
1. This isn't any homework, merely my own thought and my own work.
2. I've the detail analysis of my work "what to do?" in diagrammatic representation.
3. I've less coding skills, moreover this idea of mine made me LOST where to start to implement.
4. Moreover, I felt this seems to fun for guys who seeks coding is a challenge.
5. I'm no good in JavaScript and Logic writing, but able to design complex data structures like above.

I'm looking for a data structure, may be a linked list or Java script object or a JSON object, whatever, could be able to store such kind of relationships in the above diagram.

Some real-time implementations:

for ex: If I say generateData(100, 4); The last layer of the data structure should contain 100 objects and its parents (should be created 4 layers where Layer 0 is a parent and layer 4 is foremost child and this layer will be having 100 objects) in previous layer should adjust themselves and in first layer should have objects less than 100 (A Must).
and data structure becomes lc_data = {obj1, obj2,......obj100)

If I say generateData(100,7): The last layer of the data structure should contain 100 objects and its parents (should be created 7 layers where Layer 0 is a parent and layer 7 is foremost child and this layer will be having 100 objects) in previous layer should adjust themselves and in first layer should have objects less than 100 (A Must).
and data structure becomes lc_data = {obj1, obj2,......obj100)

I know this is a task which will challenge coders abilities and most importantly they love this kind of tasks which improves their coding abilities more and more.

Looking forward for replies with required code , seriously I'm thumping myself to see my idea to be in a code.

[Old Pedant]

I give up. What's the point of this.

So *EXACTLY* how many objects *AT EACH LEVEL* do you want that to generate?

And in any case, what will each object at each level *CONTAIN*? I mean, I guess it's okay for a parent to contain only its children. But at the lowest level, surely those final children should contain *something* useful.

Let's take a smaller example:
generateData( 6, 4 )

Is that supposed to generate:

var something = [
    child1 : {
        child2 : {
            child3 : {
                obj1 : "nothing?",
                obj2 : "nothing?",
                obj3 : "nothing?",
                obj4 : "nothing?",
                obj5 : "nothing?",
                obj6 : "nothing?"
            }
        }
    };

Or what?



las

[CoolCaptain]

Originally Posted by Old Pedant

I give up. What's the point of this.

So *EXACTLY* how many objects *AT EACH LEVEL* do you want that to generate?

And in any case, what will each object at each level *CONTAIN*? I mean, I guess it's okay for a parent to contain only its children. But at the lowest level, surely those final children should contain *something* useful.

Let's take a smaller example:
generateData( 6, 4 )

Is that supposed to generate:

var something = [
    child1 : {
        child2 : {
            child3 : {
                obj1 : "nothing?",
                obj2 : "nothing?",
                obj3 : "nothing?",
                obj4 : "nothing?",
                obj5 : "nothing?",
                obj6 : "nothing?"
            }
        }
    };

Or what?



las

First of all thanks for the reply,

as you said, generateData(6,3); should create lc_data = { obj1, obj2, obj3, obj4, obj5, obj6}; where as this whole set should be divided into random clusters like, {obj1,obj2} has one parent (p1obj) in lower level, and {obj3, obj4, obj5, obj6} has one parent (p3obj) with array structure like : {p1obj, p2obj, p3obj} and its lower most level contain superior parent {pp1obj} for {p1obj} and {pp2obj} for (p2obj, p3obj}

you see the following diagram for clear representation:




Hope you got your answers

[Old Pedant]

I hate random answers.

How is the code supposed to determine whether it should produce

var foo = [
    pp1obj : {
        p1obj : {
            obj1 : "what?",
            obj2 : "what?"
        }
   },
   pp2obj : {
        p2obj : null,
        p3obj : {
            obj3 : "what?",
            obj4 : "what?",
            obj5 : "what?",
            obj6 : "what?"
        }
    }
};

(As you diagrammed in just above post)

Or, instead,

var foo = [
    pp1obj : null,
    pp2obj : null,
    pp3obj : null,
    pp4obj : null,
    pp5obj : {
        p1obj : null,
        p2obj : {
            obj1 : "what?",
            obj2 : "what?",
            obj3 : "what?",
            obj4 : "what?",
            obj5 : "what?",
            obj6 : "what?"
        },
        p3obj : null,
        p4obj : null,
        p5obj : null,
        p6obj : null,
        p7obj : null
    }
};

I mean, yes, we could assign a random number of dummy objects at each level. But what is the range of the random numbers? 1 through 10? 1 through 100? What?

It would be much better if you had some deterministic rule to make the decision instead of just random numbers.

[Old Pedant]

And unless you care a bunch, I might implement it as obj3.parent() using a method instead of a property for parent.

[xelawho]

It seems to me that there is one variable too many in the equation. If you were to supply the number of parents you ended up with it would be simpler, but from the two diagrams you have posted, it looks like this is undetermined.

Which to me looks like an impossible calculation. Or put another way: you give it a starting (or end) point - how many children in the lc_data layer. You give how many steps to take. But you don't provide an end point. Butt that end point is going to have to be decided at some stage.

Which I guess is what Old Pedant is saying. Based on what you are providing, any code produced will either be random and meaningless or determined by some arbitrary decision that comes from outside of the scope of the original idea.

[Old Pedant]

Ehhh...he *does* say how many LEVELS to create. And how many kids at the lowest level.

So it's not *TERRIBLE*. But with no indication of how many children get attached to how many parents, the whole thing seems like just a toy for playing around with. I can't imagine any practical use for it, as specified so far.

I mean, given the parameters so far, a reasonable answer to generateDate( 6, 3 ) would be:

var foo = [
    pp1obj : {
        p1obj : {
            obj1 : "what?",
            obj2 : "what?",
            obj3 : "what?",
            obj4 : "what?",
            obj5 : "what?",
            obj6 : "what?"
        }
    };

With only one parent at each level. And if he doesn't give us better parameters/rules than he has given us so far. that's exactly what I would generate. It is the simplest structure that meets the specifications.

[xelawho]

Originally Posted by Old Pedant

With only one parent at each level.

this is my point exactly - yes, we have the number of kids and yes, we have the number of "generations" but to make the picture complete we need (I think) the number of "primary ancestors", which is not being given (or it is, but that number is radically different between the first diagram - a busload - and the second - two).

So with that factor undefined the whole thing is meaningless, because whoever designs it will end up having to pick a number, just like you did - one in this case. But you could have easily picked 12 or 78, still fit the requisites and produced radically different outcomes.

I think. I was never much of a mathematician, anyway.

[007julien]

Are you talking about neural networks ? Then this page may shed some light?

[niralsoni]

Hi,

I really found your requirement a kind of challenge. It took me around 3 hours to implement the required functionality.

Below is the random data generator which takes the child object count and layer count as input. And then randomly generates parent objects and assigns them to random number of child objects. This process is repeated upto nth layer.

And yes, it does not have the capabilities of traversing to and fro (like next, first, prev, last etc). But will try to implement them in future if this is the right solution.

function generateData(objectCount, layerCount) {
  var r = d = i = j = k = c = s = n = 0, pre = '', data = [[]];
  c = objectCount;

  for(i = 0; i < c; i++) {
    data[n][i] = {};
    data[n][i].cid = 'Obj' + (layerCount-n) + '' + (i+1);
    data[n][i].pid = 'root';
  }

  for(n = 1; n < layerCount; n++) {
    j = s = 0;
    r = c;
    c = Math.floor(Math.random()*c);
    if(c == 0) c = 1;
    data[n] = [];
    for(d = n-1; d < n; d++) {
      pre += 'P';
    }

    for(i = 0; i < c; i++) {
      data[n][i] = {};
      data[n][i].cid = pre + 'Obj' + (layerCount-n) + '' + (i+1);
      data[n][i].pid = 'root';
      
      if(j == r) continue;

      s = Math.floor(Math.random()*(r-j));
      if(s == 0) s = 1;
      k = (j + s) >= r ? r : (j + s);

      for(; j < k; j++) {
        data[n-1][j].pid = data[n][i].cid;
      }
    }
    if(j < r) {
      data[n][c] = {};
      data[n][c].cid = pre + 'Obj' + (layerCount-n) + '' + (i+1);
      data[n][c].pid = 'root';

      for(; j < r; j++) {
        data[n-1][j].pid = data[n][c].cid;
      }
      c++;
    }
  }
  return data;
}

function renderData(data) {
  document.write('Output format is - Child Object : Parent Object <br><br>');
  for(i = 0; i < data.length; i++) { // bottom-to-top print
//for(i = data.length-1; i >= 0; i--) { // top-to-bottom print
    document.write('{')
    for(j = 0; j < data[i].length; j++) {
      if(data[i][j])
        document.write(data[i][j].cid + ': ' + data[i][j].pid);
      if(j+1 < data[i].length) {
        document.write(', ');
      }
    }
    document.write('}<br><br>');
  }
}

renderData( generateData(10,3) );

Check it out and tell me whether it suffice your requirement (partly) or not?

And for viewing it in action (using some sort of tree), I have attached a sample (randomTreeGenerator.htm). Check that also. (please note that this sample does not support Chrome. You might have to open it in IE or FF... Strange but true.)


Regards,
Niral Soni

[CoolCaptain]

Originally Posted by niralsoni

Hi,

I really found your requirement a kind of challenge. It took me around 3 hours to implement the required functionality.

Below is the random data generator which takes the child object count and layer count as input. And then randomly generates parent objects and assigns them to random number of child objects. This process is repeated upto nth layer.

And yes, it does not have the capabilities of traversing to and fro (like next, first, prev, last etc). But will try to implement them in future if this is the right solution.

function generateData(objectCount, layerCount) {
  var r = d = i = j = k = c = s = n = 0, pre = '', data = [[]];
  c = objectCount;

  for(i = 0; i < c; i++) {
    data[n][i] = {};
    data[n][i].cid = 'Obj' + (layerCount-n) + '' + (i+1);
    data[n][i].pid = 'root';
  }

  for(n = 1; n < layerCount; n++) {
    j = s = 0;
    r = c;
    c = Math.floor(Math.random()*c);
    if(c == 0) c = 1;
    data[n] = [];
    for(d = n-1; d < n; d++) {
      pre += 'P';
    }

    for(i = 0; i < c; i++) {
      data[n][i] = {};
      data[n][i].cid = pre + 'Obj' + (layerCount-n) + '' + (i+1);
      data[n][i].pid = 'root';
      
      if(j == r) continue;

      s = Math.floor(Math.random()*(r-j));
      if(s == 0) s = 1;
      k = (j + s) >= r ? r : (j + s);

      for(; j < k; j++) {
        data[n-1][j].pid = data[n][i].cid;
      }
    }
    if(j < r) {
      data[n][c] = {};
      data[n][c].cid = pre + 'Obj' + (layerCount-n) + '' + (i+1);
      data[n][c].pid = 'root';

      for(; j < r; j++) {
        data[n-1][j].pid = data[n][c].cid;
      }
      c++;
    }
  }
  return data;
}

function renderData(data) {
  document.write('Output format is - Child Object : Parent Object <br><br>');
  for(i = 0; i < data.length; i++) { // bottom-to-top print
//for(i = data.length-1; i >= 0; i--) { // top-to-bottom print
    document.write('{')
    for(j = 0; j < data[i].length; j++) {
      if(data[i][j])
        document.write(data[i][j].cid + ': ' + data[i][j].pid);
      if(j+1 < data[i].length) {
        document.write(', ');
      }
    }
    document.write('}<br><br>');
  }
}

renderData( generateData(10,3) );

Check it out and tell me whether it suffice your requirement (partly) or not?

And for viewing it in action (using some sort of tree), I have attached a sample (randomTreeGenerator.htm). Check that also. (please note that this sample does not support Chrome. You might have to open it in IE or FF... Strange but true.)


Regards,
Niral Soni

Thanks for your reply with code.
You could use B+ tree architecture.

Basic data structure needed only 1 level of layer and it must be child layer, more over for now, just 1-1 relationship between parent nodes and child nodes are enough.

Data structure should have the functionalities to do in future:

1. Insert new parent layers
2. Insert nodes to parent layers
3. should be able walk through the tree.

[CoolCaptain]

right now, there isn't availability of parents information, only children is available and also there will be n number of parents to parents in this scenario, but only final children are available now. So to create a data structure which can hold children values now, as the parents are derived in the future, data structure should posses the functionality to add those parents and its relationship in future. So please suggest me, what approach I can follow, if my current way of thinking is wrong

[CoolCaptain]

1. Right now only one layer of information I've ie, children. In future, I'll get parents, parents to parents info.

2. So my data structure, should posses the functionality, like adding parents in future,
have space (shouldn't force altering the current implementation) in the raw code so that 1 - many relationship can be structured between children and parents in future.
if possible, incoporate b+ tree kind of architecture, to Insert data.

3. forget about my diagram if that provide insufficient information.

[Old Pedant]

Well, I'm still not sure I have the idea of what you want or not, but here goes...

<!DOCTYPTE html>
<html>
<head>
<title>Object Networks</title>
<style type="text/css">
div#showme {
    position: relative;
    border: solid brown 3px;
    background-color: yellow;
}
div.demo {
    position: relative;
    height: 100px; width: 200px;
    border: solid blue 1px;
    background-color: lightblue;
}
</style>
</head>
<body>
<div>
    <form id="theForm">
        How many child nodes? <input name="kids"/>
        <input type="button" name="gen" value="Generate" />
    </form>
    <div id="showme"></div>

</div>

<script type="text/javascript">
(
  function()
  {
      var form = document.getElementById("theForm");
      var show = document.getElementById("showme");

      function showName( ofWhat )
      {
          return ofWhat == null ? "[none]" : ofWhat.myName;
      }

      function DemoObject( owner, name )
      {
          this.myName = name;
          this.myParent = owner;
          this.myChildren = [ ];
          this.rightSibling = null;
          this.leftSibling = null;
          
          this.display = function( )
          {
              var d = document.createElement("div");
              d.className = "demo";
              d.innerHTML = "Name: " + showName(this)
                          + "<br/>Parent: " + showName(this.myParent)
                          + "<br/>Left: " + showName(this.leftSibling)
                          + "<br/>Right: " + showName(this.rightSibling)
                          + "<br/># of children: " + this.myChildren.length;
              return d;
          }
          
      }

      form.gen.onclick = function()
      {
          var howMany = Number(form.kids.value);
          var top = new DemoObject( null, "Daddy" );

          for ( var n = 1; n <= howMany; ++n )
          {
              top.myChildren.push( new DemoObject( top, "Child" + n ) );
          }
          for ( var c = 0; c < howMany; ++c )
          {
              var kid = top.myChildren[c];
              kid.leftSibling = top.myChildren[ ( c + howMany - 1 ) % howMany ];
              kid.rightSibling = top.myChildren[ ( c + 1 ) % howMany ];
          }
          // for demo purposes, show what we just created:
          show.appendChild( top.display( ) );
          show.appendChild( document.createElement("hr") );
          for ( var k = 0; k < howMany; ++k )
          {
              show.appendChild( top.myChildren[k].display( ) );
          }
      }
  }
)();
</script>
</body>
</html>