recursion, data structure

[Marek Mänd]

var criterions = {
subconds:{
tree:[
// LAST HEARED
{condID:1, strrep:'Last heared'
subconds:{
tree:[
{condID:5,strre p:'yesterday'}
,{condID:6,strr ep:'last week'}
,{condID:7,strr ep:'last month'}
,{condID:8,strr ep:'last year'}
]
}
}
// MUSIC
,
{condID:17, strrep:'Music',
subconds:{
tree:[
{condID:18,strr ep:'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(search Tree,searchCond ID){
var subconditions = searchTree.subc onds;
if (subconditions == null){
return;
}
var subconditions_t ree = searchTree.subc onds.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_t ree[i];
}
arguments.calle e(subconditions _tree[i],searchCondID);
}

}

I mean like function
scantree(criter ions, 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

[Evertjan.]

Re: recursion, data structure

Marek Mänd wrote on 27 okt 2004 in comp.lang.javas cript:
[color=blue]
> var criterions = {
> subconds:{
> tree:[
> // LAST HEARED
>[/color]

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)

[Michael Winter]

Re: recursion, data structure

On Wed, 27 Oct 2004 22:37:17 +0300, Marek Mänd <cador.soft@mai l.ee> wrote:
[color=blue]
> var criterions = {
> subconds:{
> tree:[
> // LAST HEARED
> {condID:1, strrep:'Last heared'[/color]

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.

[Marek Mänd]

Re: recursion, data structure

Michael Winter wrote:[color=blue]
> On Wed, 27 Oct 2004 22:37:17 +0300, Marek Mänd <cador.soft@mai l.ee> wrote:[color=green]
>> // LAST HEARED
>> {condID:1, strrep:'Last heared'[/color]
> An inconsequential correction: heard is the past participle of hear.
> You also missed the comma at the end of the line above. :)[/color]

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
[color=blue]
> 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.[/color]

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

[color=blue]
> var r = scanTree(c, i);
> /* If that search found a match, return it... */
> if(r) {return r;}[/color]

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...
[color=blue]
> Hope that helps, Mike[/color]

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

[Michael Winter]

Re: recursion, data structure

On Thu, 28 Oct 2004 02:52:37 +0300, Marek Mänd <cador.soft@mai l.ee> wrote:

[snip]
[color=blue][color=green]
>> This isn't the cleanest solution, but that structure doesn't really
>> seem amenable to clean solutions.[/color]
>
> the data structure is IMHO quite flexible for emulating XML file.[/color]

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...
[color=blue]
> 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.[/color]

....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]
[color=blue][color=green]
>> Hope that helps, Mike[/color]
>
> You managed to do it great.[/color]

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.