[futurebasic] RE: [FB] Ternary Search Trees

Message: < previous - next > : Reply : Subscribe : Cleanse
Home   : August 2006 : Group Archive : Group : All Groups

From: "Edwards, Waverly" <Waverly.Edwards@...>
Date: Sun, 27 Aug 2006 17:21:49 -0400
I understand the traverse code.  I just had to put it down for
a little bit before it made sense.  Cool.


From: Edwards, Waverly [mailto:Waverly.Edwards@...]
Sent: Sun 8/27/2006 1:27 PM
To: futurebasic@...
Subject: RE: [FB] Ternary Search Trees 

You caught it too!  I kept thinking last night that it seems really silly
to enter each character from the string one at a time.  That would
be aweful wasteful so I studied the code more to see how I could
avoid it and behold it was already built in.  I made that change and
one other.  The way I'm initializing the root is wrong.  You only need
to begin entering strings.  If a node does not exist then it is created
and a pointer to the node is returned. That  applies to the root as
well if done correctly.

I love what you've done.   I dont understand the traverse code yet
but I'm working on it.  I understand why you returned found instead
of userData.  I figure on another installment if anyone is interested
I'll add some user data because its great that you can fined if a word
is in the tree quickly but its even better that you can associate data
with that entry.



gRoot = fn insert( gRoot , s , userData )

which completely eliminates this:

local fn initTernaryTree
     No way was ever discussed in any article on how to initialize
     the tree.  This seems like the best way.
gRoot = fn newptrclear( sizeof(Tnode) )
end fn

local fn loadCStrings
dim as long i, index, strLen
dim as ptr s, nullCharPtr, userData
dim as str255 tempStr

userData = fn newptrclear( sizeof(ptr) )

     Install strings into ternary tree.  Convert FB (Pascal style)
     strings to C strings. 

     There is a trick that can be done to reduce the cost of loading
     the ternary tree.  Its done by not having to convert the loaded string into a C string
     to a C style string but we will keep it simple here.

     userData is currently an empty pointer.  You decide what to add here
     and how to read it.

i = 0

gTestStr( i ) = "apple"     : i++
gTestStr( i ) = "dog"       : i++
gTestStr( i ) = "easy"      : i++
gTestStr( i ) = "fall"      : i++
gTestStr( i ) = "fellow"    : i++
gTestStr( i ) = "zebra"     : i++
gTestStr( i ) = "cat"       : i++
gTestStr( i ) = "xray"      : i++
gTestStr( i ) = "bath"      : i++
gTestStr( i ) = "water"     : i++
gTestStr( i ) = "rain"      : i++
gTestStr( i ) = "elephant"  : i++
gTestStr( i ) = "for"       : i++
gTestStr( i ) = "format"    : i++

gNumItems = i -1
i = gNumItems

_useMixedStyleString = _zTrue
#if _useMixedStyleString

for index = 0 to i

tempStr = gTestStr( index )// create a copy so we dont change original string
strLen = tempStr[0] + 1// add one byte to length where nil character will reside
s = @tempStr+1// address of first character (skipped length byte)
nullCharPtr = @tempStr + strLen
nullCharPtr.nil`` = _nil
     Create a mixed FB & C style string

     find location one byte beyond string length
     insert nil character to give the illusion of a C style string
     Will fail if string is already 255 characters in length
gRoot = fn insert( gRoot , s , userData )



for index = 0 to i

tempStr = gTestStr( index )
fn FBPStr2CStr( tempStr )// convert to a C string
s = @tempStr
gRoot = fn insert( gRoot , s , userData )



end fn

-----Original Message-----
From: Jay Reeve [mailto:jayreeve@...]
Sent: Sun 8/27/2006 3:33 AM
To: futurebasic@...
Subject: Re: [FB] Ternary Search Trees

On Aug 25, 2006, at 5:55 PM, Edwards, Waverly wrote:

> There was probably something wrong with my translation of the C 
> code of the first source code.
> I've looked over it dozens of times and there was only one line 
> where I felt questionable but didn't see a different way to do it.
> I'll go back -anyway- to see if there was something I overlooked.


You piqued my interest, so I've been working at creating the tree 
from concept rather than by translating the c. I got the recursive 
version working--very much like the c--but when I tested it with a 
sizeable dictionary (several hundred words, already sorted), the 
recursion quickly went too deep. So I created a non-recursive version.

Like you, I have something that seems to work, but then gets weird. 
At the moment, everything works perfectly up until it crashes when I 
create the 2048th node in a dynamic array--or rather when I exit the 
fn that creates it.

I've checked var sizes, globals, var and field names. It must be 
related to memory management, but dynamic arrays have always been so 
solid, so I can't imagine how that could be. I find it highly 
suspicious that the crash comes at certain binary round numbers.

On receiving your "finished" code, I spent some time getting it 
working, then added a fn Traverse which seems to work fine. I 
replaced your test with mine, using a dictionary of 4-letter words I 
had used for something else. Don't worry about the strange format of 
the input DATA stmts, but do notice how I format the strings for use 
by your code. (line 221) This code suffers from the same problem as 
my original, in that it dies from "functions nested too deeply" if 
you add any more data. (If you remove the <end> in line 343, you 
should see this.)

I've replaced the return from fn Search with _zTrue or _false, 
because otherwise it returns 0 when found (since there is no userData 

You might want to look at your test code:
tempStr = gTestStr( index )
s = @tempStr +1
strLen = tempStr[0]

while ( strLen )
fn insert1( gRoot, s )

What this loop does is send the word, then remove the first char and 
send the remainder, then repeat until only the last char is sent. 
It's only necessary to send the word once--the recursion does the rest.

Now that I have your solid code, I will try to create an non-
recursive version (for full usability) using pStrings (just because c-
strings are so NOT FB :-)

My apologies for being out of touch during all your travails, but 
every time I started to reply, I'd either have a fresh idea I had to 
try first, or I'd get interrupted by everyday life--which is pressing 
again now. I hope you find my Traverse a bit useful, or at least 

   =J= a  y
To unsubscribe, send ANY message to: futurebasic-unsubscribe@...

To unsubscribe, send ANY message to: futurebasic-unsubscribe@...