By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,493 Members | 1,296 Online
Bytes IT Community
+ Ask a Question
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<subconditions_tree.length; i++) {
if (subconditions_tree[i].condID == searchCondID){
return subconditions_tree[i];
}
arguments.callee(subconditions_tree[i],searchCondID);
}

}

I mean like function
scantree(criterions, 21);
that would tell me it is a 'Movie'.
The code of mine is too simplistic and doesnt work right.
I have probably wrong exit conditions.
It is available as a quick test& tryout at:

http://marekmand.kuubik.ee/test/recursion.htm
Jul 23 '05 #1
Share this Question
Share on Google+
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 <ca********@mail.ee> 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 <ca********@mail.ee> 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 <ca********@mail.ee> 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.