|
Post by andrian on Jan 20, 2009 16:20:05 GMT -5
You can do this:
struc city dim &ohai as city dim x end struc
Can anyone say "tree walking"?
|
|
|
Post by Nicky Peter Hollyoake on Jan 20, 2009 16:44:53 GMT -5
Whats that really useful for?
- Nicky
|
|
|
Post by matthew on Jan 20, 2009 17:08:42 GMT -5
I think andrian may be referring to Binary Search Trees or something similar, xenovacivus wrote a BSP example a few years ago & it can be found here.
|
|
|
Post by andrian on Jan 21, 2009 18:23:53 GMT -5
Tree walking is useful for things like recursive functions (Can we do these in b4gl?)
Allow me to explain. What if we are taking the subway from one stop to another? We would want to find the route which would require the least travel time. The stops are arranged like this:
A to B - 12 minutes A to C - 15 minutes B to D - 3 minutes B to C - 5 minutes
If you want to find the quickest path between D and C, you must hop from one stop to the next, to the next to the next until you reach your destination. Tree walking allows you to do that. The variable (a structure) contains a reference to the stops connected to it. When you go through each stop looking for the fastest route, you will want to know if the stops connected to the stops connected to the stop you're at are the destination. Its the same with the stops connected to the stops connected to the stops connected to you point of origin and so on. You can ride the subway in circles all day and then arrive at your stop - it is possible in real life, so we can simulate it with a program.
This can be useful for determining paths of all kinds, such as the path a packet must take to reach the client from the server or where a chess piece can move in its consecutive turns. It can be used to implement web crawlers and indexing services. Anything which needs to jump from one destination to another can benefit from tree walking.
|
|
|
Post by DJLinux on Jan 21, 2009 23:19:48 GMT -5
yes you can do all the usefull things with "pointers" in B4GL too a better name are "nodes" (trees, chains, stacks, queue, linked lists ...)
Joshy
|
|
|
Post by andrian on Jan 26, 2009 16:12:30 GMT -5
Well, here's a real-life example of how this can be useful. It really should use recursion, but I am still having trouble getting simple programs to work, so here it is. I used it to answer problem number 6 from this site: www.cis.uab.edu/programs/hspc/2005/2005-problems.pdf struc city dim &dest() as city dim dist(3) dim Name as string end struc
dim Al(6) as city Al(0).Name = "Alabaster" Al(1).Name = "Birmingham" Al(2).Name = "Demopolis" Al(3).Name = "Mobile" Al(4).Name = "Montgomery" Al(5).Name = "Huntsville" Al(6).Name = "Tuscaloosa"
dim &tcity() as city
alloc tcity, 1 tcity(0) = Al(1) tcity(1) = Al(4) &Al(0).dest = &tcity Al(0).dist(0) = 24 Al(0).dist(1) = 71
alloc tcity, 2 tcity(0) = Al(0) tcity(1) = Al(5) tcity(2) = Al(6) &Al(1).dest = &tcity Al(1).dist(0) = 24 Al(1).dist(1) = 103 Al(1).dist(2) = 59 alloc tcity, 2 tcity(0) = Al(3) tcity(1) = Al(4) tcity(2) = Al(6) &Al(2).dest = &tcity Al(2).dist(0) = 141 Al(2).dist(1) = 101 Al(2).dist(2) = 65
alloc tcity, 1 tcity(0) = Al(4) tcity(1) = Al(2) &Al(3).dest = &tcity Al(3).dist(0) = 169 Al(3).dist(1) = 141
alloc tcity, 3 tcity(0) = Al(6) tcity(1) = Al(0) tcity(2) = Al(2) tcity(3) = Al(3) &Al(4).dest = &tcity Al(4).dist(0) = 134 Al(4).dist(1) = 71 Al(4).dist(2) = 141 Al(4).dist(3) = 169
alloc tcity, 0 tcity(0) = Al(1) &Al(5).dest = &tcity Al(5).dist(0) = 103
alloc tcity, 2 tcity(0) = Al(1) tcity(1) = Al(2) tcity(2) = Al(4) &Al(6).dest = &tcity Al(6).dist(0) = 59 Al(6).dist(1) = 65 Al(6).dist(2) = 134 dim city1 as string, city2 as string function stocity(string$) as city dim x, c as city for x = 0 to 6 if lcase$(string$) = lcase$(Al(x).name) then c = al(x) endif next return c end function dim c1 as city, c2 as city dim x dim ok = false while not ok Input "Enter city #1:", city1 x = 0 while x < 7 land lcase$(city1) <> lcase$(Al(x).name) x = x + 1 wend ok = x <> 7 if not ok then printr "Invalid city name" endif wend ok = false while not ok Input "Enter city #2:", city2 x = 0 while x < 7 land lcase$(city2) <> lcase$(Al(x).name) x = x + 1 wend ok = x <> 7 if not ok then printr "Invalid city name" endif wend c1 = stocity(city1) c2 = stocity(city2)
dim x1, x2, x3, x4, x5, td, t, p1, p2, p3, p4, p5
for x1 = 0 to arraymax(c1.dest) c1.dest(x1) = stocity(c1.dest(x1).name) if c1.dest(x1).name = c2.name then printr c1.name + " - " + c2.name + " " + c1.dist(x1) + " miles" end endif next td = 1000 for x1 = 0 to arraymax(c1.dest) for x2 = 0 to arraymax(c1.dest(x1).dest) c1.dest(x1).dest(x2) = stocity(c1.dest(x1).dest(x2).name) if c1.dest(x1).dest(x2).name = c2.name then t = c1.dist(x1)+ c1.dest(x1).dist(x2) if t < td then td = t p1 = x1 p2 = x2 endif endif next next if td <> 1000 then printr c1.name + " - " + c1.dest(p1).name + " - " + c2.name + " " + (c1.dist(p1)+ c1.dest(p1).dist(p2)) + " miles" end endif for x1 = 0 to arraymax(c1.dest) for x2 = 0 to arraymax(c1.dest(x1).dest) for x3 = 0 to arraymax(c1.dest(x1).dest(x2).dest) c1.dest(x1).dest(x2).dest(x3) = stocity(c1.dest(x1).dest(x2).dest(x3).name) if c1.dest(x1).dest(x2).dest(x3).name = c2.name then t = c1.dist(x1)+ c1.dest(x1).dist(x2) + c1.dest(x1).dest(x2).dist(x3) if t < td then td = t p1 = x1 p2 = x2 p3 = x3 endif endif next next next if td <> 1000 then printr c1.name + " - " + c1.dest(p1).name + " - " + c1.dest(p1).dest(p2).name + " - " + c2.name + " " + (c1.dist(p1)+ c1.dest(p1).dist(p2) + c1.dest(p1).dest(p2).dist(p3)) + " miles" end endif for x1 = 0 to arraymax(c1.dest) for x2 = 0 to arraymax(c1.dest(x1).dest) for x3 = 0 to arraymax(c1.dest(x1).dest(x2).dest) for x4 = 0 to arraymax(c1.dest(x1).dest(x2).dest(x3).dest) c1.dest(x1).dest(x2).dest(x3).dest(x4) = stocity(c1.dest(x1).dest(x2).dest(x3).dest(x4).name) if c1.dest(x1).dest(x2).dest(x3).dest(x4).name = c2.name then t = c1.dist(x1)+ c1.dest(x1).dist(x2) + c1.dest(x1).dest(x2).dist(x3) + c1.dest(x1).dest(x2).dest(x3).dist(x4) if t < td then td = t p1 = x1 p2 = x2 p3 = x3 p4 = x4 endif endif next next next next if td <> 1000 then printr c1.name + " - " + c1.dest(p1).name + " - " + c1.dest(p1).dest(p2).name + " - " + c1.dest(p1).dest(p2).dest(p3).name + " - " + c2.name + " " + (c1.dist(p1)+ c1.dest(p1).dist(p2) + c1.dest(p1).dest(p2).dist(p3) + c1.dest(p1).dest(p2).dest(p3).dist(p4)) + " miles" end endif for x1 = 0 to arraymax(c1.dest) for x2 = 0 to arraymax(c1.dest(x1).dest) for x3 = 0 to arraymax(c1.dest(x1).dest(x2).dest) for x4 = 0 to arraymax(c1.dest(x1).dest(x2).dest(x3).dest) for x5 = 0 to arraymax(c1.dest(x1).dest(x2).dest(x3).dest(x4).dest) c1.dest(x1).dest(x2).dest(x3).dest(x4).dest(x5) = stocity(c1.dest(x1).dest(x2).dest(x3).dest(x4).dest(x5).name) if c1.dest(x1).dest(x2).dest(x3).dest(x4).dest(x5).name = c2.name then t = c1.dist(x1)+ c1.dest(x1).dist(x2) + c1.dest(x1).dest(x2).dist(x3) + c1.dest(x1).dest(x2).dest(x3).dist(x4) + c1.dest(x1).dest(x2).dest(x3).dest(x4).dist(x5) if t < td then td = t p1 = x1 p2 = x2 p3 = x3 p4 = x4 endif endif next next next next next if td <> 1000 then printr c1.name + " - " + c1.dest(p1).name + " - " + c1.dest(p1).dest(p2).name + " - " + c1.dest(p1).dest(p2).dest(p3).name + " - " + c1.dest(p1).dest(p2).dest(p3).dest(p4).name + " - " + c2.name + " " + (c1.dist(p1)+ c1.dest(p1).dist(p2) + c1.dest(p1).dest(p2).dist(p3) + c1.dest(p1).dest(p2).dest(p3).dist(p4) + c1.dest(p1).dest(p2).dest(p3).dest(p4).dist(p5)) + " miles" end endif
|
|
|
Post by Nicky Peter Hollyoake on Jan 26, 2009 16:25:11 GMT -5
You what? I've never seen this before, this is new to me. I've tried to look, maybe after I clean up the code abit (no offence) I'll be able to see whats happening. I can't see, I mean I don't get, well .. this.
for x1 = 0 to arraymax(c1.dest) for x2 = 0 to arraymax(c1.dest(x1).dest) for x3 = 0 to arraymax(c1.dest(x1).dest(x2).dest) for x4 = 0 to arraymax(c1.dest(x1).dest(x2).dest(x3).dest) for x5 = 0 to arraymax(c1.dest(x1).dest(x2).dest(x3).dest(x4).dest)
c1.dest(x1), etc .. How are you doing that with just one structure?
- Nicky
|
|
|
Post by andrian on Jan 26, 2009 20:32:20 GMT -5
Its the tree walking! Each city points to all the cities you can get to from there, which in turn point to all the cities you can get to from each of them. I just have to make sure the pointers are set properly. I can then iterate through the destinations until I find the right one. This is why I was so excited when I first realized this was possible. I'm sorry about the loss of indentation, it happened when I pasted into the comment box. And I also apologize for not commenting the code.
|
|