SitePoint Sponsor

User Tag List

Results 1 to 9 of 9

Hybrid View

  1. #1
    SitePoint Addict jtrelfa's Avatar
    Join Date
    Oct 2004
    Location
    Troy, Mi
    Posts
    231
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Question Recursive function - finding depth

    I have an array of objects that contain arrays of objects:
    Code:
    var a = [
      {group:"abc",data:[
        {id:123,title:"Title of item"},
        {id:456,title:"Title of item"},
        {group:"def",data:[
          {id:789,title:"Title if item"},
          {id:101,title:"Title of item"}
        ]}
      ]}
    ];
    There's no limit to how deeply this could be nested. I use a recursive function to loop through the array. In each iteration, I check if there's a data array and initiate the loop on that specific data array:
    Code:
    function looper(sourcearray) {
      for(var i = 0, len = sourcearray.length; i < len; ++i) {
        //do stuff
        if(typeof sourcearray[i].data !== 'undefined' && sourcearray[i].data.length > 0) {
          looper(sourcearray[i].data);
        }
      }
    }
    Lets say that I'm 3 levels 'deep' in the array. Is there a way for me to determine the 'path' to where I am?

    For example, if the array 'path' is: a[1][3][1]

    Is there a way for me to obtain some sort of reference to that array path?

    I hope my question is clear - this is a bit of a tough one for me for some reason (could it be because it's Monday?)
    var me = null;

  2. #2
    SitePoint Wizard gRoberts's Avatar
    Join Date
    Oct 2004
    Location
    Birtley, UK
    Posts
    2,439
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    It all depends on what your doing with the data. In some way you'd need a unique way to indentify each object in each array etc. Or at least a way of documenting the way you reached that object to display it.


  3. #3
    SitePoint Addict jtrelfa's Avatar
    Join Date
    Oct 2004
    Location
    Troy, Mi
    Posts
    231
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by gRoberts View Post
    It all depends on what your doing with the data. In some way you'd need a unique way to indentify each object in each array etc. Or at least a way of documenting the way you reached that object to display it.
    Actually, I'm using the 'reference' to the depth in order to sort the information in a tree-like structure.

    Items within a group can only be sorted and rearranged within their group - so when I click an action to move that specific item within the group, I need to change what's displayed on the page; but at the same time I need to ensure that the correct array is sorted - because I'm using the 'final' version of the array to save the new tree structure into a database.
    var me = null;

  4. #4
    Caveat surfer Buddy Bradley's Avatar
    Join Date
    May 2003
    Location
    Cambridge, UK
    Posts
    2,366
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    You could set a counter to zero at the same scope as your function, and then increment it each time it is called (before the for loop), then read it when you need to find out what depth you're at. I think if you decrement it at the end of the function it should keep track of the level correctly.

  5. #5
    SitePoint Wizard gRoberts's Avatar
    Join Date
    Oct 2004
    Location
    Birtley, UK
    Posts
    2,439
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Are you using a Tree?

    Have a look at ExtJs.com, I am "sure" that you can use your array structure as a datasource. When you rearrange the tree using the GUI, your datasource will change, and IIRC you can then get the changed datasource from the tree.


  6. #6
    SitePoint Addict jtrelfa's Avatar
    Join Date
    Oct 2004
    Location
    Troy, Mi
    Posts
    231
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by gRoberts View Post
    Are you using a Tree?

    Have a look at ExtJs.com, I am "sure" that you can use your array structure as a datasource. When you rearrange the tree using the GUI, your datasource will change, and IIRC you can then get the changed datasource from the tree.
    Yes, I am using a tree

    I tried YUI and ext and ran into a small problem - the 'special' nature of my tree required significant hacks to the point where those trees fell short.

    I'll give the detail here - please pardon the verbosity:

    The trees offered by YUI and Ext assume a tree based on the structure of a recordset and/or array. In my application, the 'container' objects actually change how the branches in the tree are displayed based on certain values.

    Here's a sample bit of code (source tree):
    Code:
    [
      {
        "id":1,
        "siblings":0,
        "currlevel":0,
        "activityid":6214,
        "containertype":"O",
        "hidden":"N",
        "title":"Course Group 1",
        "code":"DEV20170d",
        "data":[
          {
            "id":4,
            "siblings":2,
            "activityid":6211,
            "hidden":"N",
            "title":"Course - Session 1",
            "code":"DEV20171d",
          },
          {
            "id":5,
            "siblings":1,
            "activityid":6212,
            "hidden":"N",
            "title":"Course - Session 2",
            "code":"DEV20172d",
          },
          {
            "id":6,
            "siblings":0,
            "activityid":6213,
            "hidden":"N",
            "title":"Course - Session 3",
            "code":"DEV20173d",
          }
        ]
      },
      {
        "id":12,
        "siblings":0,
        "activityid":null,
        "containertype":"R",
        "hidden":"N",
        "title":"Recommended",
        "code":null,
        "data":[
          {
            "id":16,
            "siblings":1,
            "activityid":4678,
            "hidden":"N",
            "title":"Recommended Course 1",
            "code":"GEN10800w",
          },
          {
            "id":17,
            "siblings":0,
            "activityid":1839,
            "hidden":"N",
            "title":"Recommended Course 2",
            "code":"gcp_csdbau",
          }
        ]
      }
    ]
    The first object has a container type of "O", so each item at the first level of the tree has to have an extra "node" in the tree with the word "OR" in it (meaning that course A or course B or Course C is required, etc).
    If the container type is "A", then all courses would be required, so there are no additional nodes would be necessary. For the container of type "R", all courses are optional, so that part of the tree is actually styled differently with CSS. In addition to the potential "OR" node, every node that has a container type also has an additional node appended that has a "completion requirements" node added with phrases like "Complete any n of the following" and "Complete all of the following".

    I'm currently designing the part of the system used to create the tree and one of the requirements is to allow the user to change the order that the courses appear - but only within their respective containers. An "action" column has been added as the first table cell in all tree node rows that enables the user to click an 'up' or 'down' arrow to move the node (only within it's container).

    On top of all this, the user still wants the ability to expand/collapse the different parts of the tree, so I had to maintain the 'children' container div to house everything that expands and collapses. Here's an image of what part of the interface looks like:

    var me = null;

  7. #7
    SitePoint Wizard gRoberts's Avatar
    Join Date
    Oct 2004
    Location
    Birtley, UK
    Posts
    2,439
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    so when would you want to find the path? Does the user have to click on something?


  8. #8
    SitePoint Addict jtrelfa's Avatar
    Join Date
    Oct 2004
    Location
    Troy, Mi
    Posts
    231
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by gRoberts View Post
    so when would you want to find the path? Does the user have to click on something?
    I want the path so that I can re-arrange the appropriate "data" array in the correct nesting level. This way, a click event on an "up" arrow for a course that's 4 levels deep would only rearrange that specific array within the tree/data structure.

    Here's what I have that's (sort of) working:
    1. Start the loop
    2. Pass the unique 'id' field value (from the database) to the onclick function of the up/down arrows
    3. recursively loop through the dataset until the correct id is found
    4. sort the array where that node was located
    5. redraw the tree


    What I'm trying to do is circumvent the additional loop from the onclick event so that I can just go directly to the correct array (regardless of depth) and re-arrange. I wasn't sure if there was a quick and dirty way to do something like:
    Code:
    moveData(dataStructure[0][1][1], 'up');
    Where the reference to the 'dataStructure[0][1][1]' text could be programmatically inserted into the onclick event. I think I'll try the 'stack' that stereofrog suggested and maybe do a string-concatenation hack:
    Code:
    <uglyhack>
    <script>
    var str = 'dataStructure';
    for (var i = 0, len = stack.length; i < len; ++i) {
      str += '[' + stack[i] + ']';
    }
    </script>
    <img onclick="moveData(" + str + ",'up');" src=...>
    </uglyhack>
    .. you get the idea
    var me = null;

  9. #9
    SitePoint Wizard stereofrog's Avatar
    Join Date
    Apr 2004
    Location
    germany
    Posts
    4,324
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    I don't know anything about yahoo UI, but to answer you original quiestion, you need a data structure that is called "stack".

    http://en.wikipedia.org/wiki/Stack_&#37;28data_structure%29

    Code:
    var stack = [];
    
    function walk(node) {
    	// at this point, "stack" contains the path to the node
    	if(node.data) {
    		for(var i = 0; i < node.data.length; i++) {
    			stack.push(i);
    			walk(node.data[i]);
    			stack.pop();
    		}
    	}
    }
    
    walk(tree);


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •