473,322 Members | 1,431 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

recursion, data structure

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
4 1733
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
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
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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

12
by: da Vinci | last post by:
Greetings. I want to get everyone's opinion on the use of recursion. We covered it in class tonight and I want a good solid answer from people in the "know" on how well recursion is accepted...
3
by: csx | last post by:
Hi all, Ive got a problem with recursion in Javascript. For this tree: http://www.pcm.uklinux.net/structure.jpg If you input node 3 (i.e. C) which is represented as 'values' in the array, it...
43
by: Lorenzo Villari | last post by:
I've tried to transform this into a not recursive version but without luck... #include <stdio.h> void countdown(int p) { int x;
10
by: paulw | last post by:
Hi Please give problems that "HAS TO" to use recursion (recursive calls to itself.) Preferrably real world examples, not knights tour. I'm thinking about eliminating the use of stack... ...
10
by: MakeMineScotch | last post by:
What's the secret to writing recursive functions that won't crash the computer?
12
by: NOO Recursion | last post by:
Hi everyone! I am trying to write a program that will search a 12x12 for a thing called a "blob". A blob in the grid is made up of asterisks. A blob contains at least one asterisk. If an...
3
by: n.torrey.pines | last post by:
Hi I work with a nested tree-like data structure template (that happens to be a tuple of vectors of tuples of trees of something, with different tuple elements having different types) I need...
30
by: Jeff Bigham | last post by:
So, it appears that Javascript has a recursion limit of about 1000 levels on FF, maybe less/more on other browsers. Should such deep recursion then generally be avoided in Javascript?...
35
by: Muzammil | last post by:
int harmonic(int n) { if (n=1) { return 1; } else { return harmonic(n-1)+1/n; } } can any help me ??
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.