448,493 Members | 1,296 Online
Need help? Post your question and get tips & solutions from a community of 448,493 IT Pros & Developers. It's quick & easy.

# recursion, data structure

 P: n/a var criterions = { subconds:{ tree:[ // LAST HEARED {condID:1, strrep:'Last heared' subconds:{ tree:[ {condID:5,strrep:'yesterday'} ,{condID:6,strrep:'last week'} ,{condID:7,strrep:'last month'} ,{condID:8,strrep:'last year'} ] } } // MUSIC , {condID:17, strrep:'Music', subconds:{ tree:[ {condID:18,strrep:'Type', subconds:{ tree:[ {condID:19, strrep:'All'} ,{condID:20, strrep:'Image'} ,{condID:21, strrep:'Movie'} ] } } ] } } ] } } Ich have this kind of data structure. I'd need a method that would give me the specific node and subtree by which the nodes property condID equals to argument searchCondID. function scantree(searchTree,searchCondID){ var subconditions = searchTree.subconds; if (subconditions == null){ return; } var subconditions_tree = searchTree.subconds.tree; if (subconditions_tree == null){ return; } var i=0; for (i=0; i
4 Replies

 P: n/a Marek Mänd wrote on 27 okt 2004 in comp.lang.javascript: var criterions = { subconds:{ tree:[ // LAST HEARED Please do not multipost !!! -- Evertjan. The Netherlands. (Please change the x'es to dots in my emailaddress, but let us keep the discussions in the newsgroup) Jul 23 '05 #2

 P: n/a On Wed, 27 Oct 2004 22:37:17 +0300, Marek Mänd wrote: var criterions = { subconds:{ tree:[ // LAST HEARED {condID:1, strrep:'Last heared' An inconsequential correction: heard is the past participle of hear. You also missed the comma at the end of the line above. :) [snip] To boil that structure down: cond { condID, strrep, subconds? } subconds { tree[ cond+ ] } A condition (cond) contains an identifier (condID), a string (strrep) and, optionally, a set of sub-conditions (subconds). A sub-condition contains an array (tree) of one or more conditions (cond). This isn't the cleanest solution, but that structure doesn't really seem amenable to clean solutions. /* Assumes that the object, o, always contains a sub-condition. */ function scanTree(o, i) { /* Get the sub-condition array, tree. */ var t = o.subconds.tree; /* Loop through each sub-condition. */ for(var c, j = 0, n = t.length; j < n; ++j) { /* Save a reference to the current sub-condition. */ c = t[j]; /* If the current sub-condition matches the id * we're looking for, return its value. */ if(c.condID == i) {return c.strrep;} /* If a match wasn't found and this sub-condition * contains more conditions, begin searching them. */ if(c.subconds) { var r = scanTree(c, i); /* If that search found a match, return it... */ if(r) {return r;} } /* ...otherwise keep searching until we're out of * conditions. */ } } Untested. [snip] Hope that helps, Mike -- Michael Winter Replace ".invalid" with ".uk" to reply by e-mail. Jul 23 '05 #3

 P: n/a Michael Winter wrote: On Wed, 27 Oct 2004 22:37:17 +0300, Marek Mänd wrote: // LAST HEARED {condID:1, strrep:'Last heared' An inconsequential correction: heard is the past participle of hear. You also missed the comma at the end of the line above. :) I had it correct before I posted here, there stood "Last Tested" which I found a bit lame, so in a hurry... But thanks for pointing out. Besides javascript I use usenet also too keep level up with my crappy language skills in german and english ;D To boil that structure down: cond { condID, strrep, subconds? } subconds { tree[ cond+ ] } A condition (cond) contains an identifier (condID), a string (strrep) and, optionally, a set of sub-conditions (subconds). A sub-condition contains an array (tree) of one or more conditions (cond). This isn't the cleanest solution, but that structure doesn't really seem amenable to clean solutions. the data structure is IMHO quite flexible for emulating XML file. The general theory why I dont hang directly the "tree" to the "cond", but have a "proxy-object" "subconds" between them is, that so I can possibly putin the future more attributes in, if I need to. I rather do it in more complex way, enforce the format on the serverside programmer (that will do one other guy) oso when later I want to introduce some my compelc attributes, I shall to hear from him, that he has treouble rewritiung his PHP outputs ;D var r = scanTree(c, i); /* If that search found a match, return it... */ if(r) {return r;} The code I posted here was very of the modifications of my own. When I looked the code I initially produced on my HDD I noticed, that the idea I had was ok, except it was lacking the if(r) {return r;} part, the key part... Hope that helps, Mike You managed to do it great. And if the project I am now on for weeks without sleeping properly (thatswhy such problems with concentration) will be lucky, this will develop into huge system in Estonia here. Well see. Other people do the selling part ;D Jul 23 '05 #4

 P: n/a On Thu, 28 Oct 2004 02:52:37 +0300, Marek Mänd wrote: [snip] This isn't the cleanest solution, but that structure doesn't really seem amenable to clean solutions. the data structure is IMHO quite flexible for emulating XML file. Oh, I'm sure it is. What I was mainly commenting on is that structure, as it stands, could be represented in a much simpler fashion, but... The general theory why I dont hang directly the "tree" to the "cond", but have a "proxy-object" "subconds" between them is, that so I can possibly putin the future more attributes in, if I need to. ....I assumed this was the case (it was quite obvious, really), which was why I made no attempt to suggest something different. Just to clear up any confusion, the "cleanest solution" remark was directed at my solution, not yours. [snip] Hope that helps, Mike You managed to do it great. Thank you. Glad to have helped. By the way, based on the sample data, the search algorithm could be optimised. Consider the following structure: 1 2 3 4 5 6 7 8 9 10 11 12 and this pseudo(-ish) code: function find(nodes, id) { var cN, n; if(!nodes) {return;} if(id == (cN = nodes[0]).id) {return cN;} if((n = nodes.length) == 1) {return find(cN.nodes, id);} for(var i = 1; i < n; ++i) { if((cN = nodes[i]).id > id) {return find(nodes[i - 1].nodes, id);} if(id == cN.id) {return cN;} } } where nodes, the argument, and nodes, the property, are analogous to the tree array in your structure. At a glance, this version should perform, at worst case, like the original. However, at best case, it should be substantially quicker. It works on the premise that nodes are assigned ids depth-first. That is, the children of a node are assigned ids before that node's siblings. This guarantees that if the search value is less than the current node id, the target must occur earlier in the tree. If you consider trying to find node 12 (an extreme example) in the tree above, the original algorithm will search every subtree on its way down. The (pseudo-)code above will remain at the first level, so it will find the node very quickly. If your application will have a large data structure or will search it frequently, you might want to consider an optimisation such as this. This particular one may not actually be optimal (and it's only had a walkthrough, not a rigorous test), but then I'm not too familiar with the various types of search patterns. [snip] Good luck with the project, Mike -- Michael Winter Replace ".invalid" with ".uk" to reply by e-mail. Jul 23 '05 #5

### This discussion thread is closed

Replies have been disabled for this discussion.