Its functioning but there are a few bugs that I just cant pin down.

1.  If you enter a substring of an existing string you get a found result.
          If "format" is entered and you search for "form" you get a found result

2.  Running the program over an over shows a different result in number of nodes created.
           Its the same program, the results should be identical.  See gNodeCount

3. According to the article you should be able to traverse the nodes and print all the inserted
    strings in alpha order using fn traverse.  I dont see how and it shows.  It must be something
    in my implementation.


I worked on a number of seemingly clever ways to create mixed strings to keep the overhead
 of creating C strings.  Multiple runs produced different results, so I abandoned that effort.
          Appending a null character to the end of an existing string without changing the length byte
          which keeps the string pascal type but the extra nil character just beyond the string length.
          passing the string @myString + 1 keeps the overhead of blockmoving data around and its
          still null terminated.

This was run in console so I could see the results.

Hopefully someone can spot the errors.

I thought this algorithm would be good for a dictionay, symbol table, lexer, word counter.
Based on everything I've read it should be blazingly fast.  If I can only get it to work.


W.


// TERNARY SEARCH TREE

begin globals

begin record tnode
dim splitchar    as char
dim & // seems like a good idea but untested for speed
dim lokid        as ptr
dim eqkid        as ptr
dim hikid        as ptr
end record

//#define Tptr as pointer to tnode

dim gRoot as ^tNode
dim as long gNumItems, gDeleteNodeCount, gNodeCount
dim dynamic gTestStr(_maxLong) as str255

end globals


// Simple Insertion Algorithm
local fn insert1( p as ^tNode, s as ptr )
'~'1
long if ( p == 0 )
gNodeCount++ // new node created
p = fn newptr( sizeof(Tnode) )
p.splitchar`` = s.nil``
p.hikid = 0
p.eqkid = p.hikid
p.lokid = p.eqkid
end if

long if ( s.nil`` < p.splitchar`` )
p.lokid = fn insert1( p.lokid, s )
xelse
long if ( s.nil`` == p.splitchar`` )
s++
if ( s.nil`` != 0 ) then p.eqkid = fn insert1( p.eqkid, s )
xelse
p.hikid = fn insert1( p.hikid, s )
end if
end if

end fn  = p


// Search Algorithm
local fn search1( s as ptr )
'~'1
dim found as long
dim p     as ^tNode

found = _false
p = gRoot
while( p )
long if ( s.nil`` < p.splitchar )
p = p.lokid
xelse
long if ( s.nil`` == p.splitchar )
//print chr$(s.nil``), s.nil``
s++
long if ( s.nil`` == 0 )
//print chr$(s.nil``), s.nil``
 found = _zTrue
exit fn
end if

p = p.eqkid
xelse
p = p.hikid
end if

end if
wend

//print

end fn = found

// node destruction
local fn cleanup1( p as ^tNode)
'~'1
long if ( p )
gDeleteNodeCount++
fn cleanup1( p.lokid )
fn cleanup1( p.eqkid )
fn cleanup1( p.hikid )
fn disposeptr( p )
end if
end fn


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

term = fn newptrclear( sizeof(Tnode) )

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

for index = 0 to i

tempStr = gTestStr( index )
s = @tempStr +1
strLen = tempStr[0]

while ( strLen )
fn insert1( gRoot, s )
s++
strLen--
wend

fn insert1( gRoot,  term )// terminate C string

next

end fn

local fn printCString( p as ptr )
'~'1
while ( p.nil`` )
print chr$(p.nil``);
p++
wend
print
end fn


local fn traverse( p as ^tNode )
'~'1
if ( p  == 0 ) then exit fn
fn traverse( p.lokid )
long if ( p.splitchar )
fn traverse( p.eqkid )
xelse
fn printCString( p.eqkid )
end if
fn traverse( p.hikid )
end fn


local fn showIfFound ( found as long, @strPtr as ^str255 )
'~'1
long if ( found )
print "found    ";strPtr.nil$
xelse
print "missing  ";strPtr.nil$
end if

end fn


local fn testCStrings
'~'1
dim as long i, index, found
dim as str255 tempStr, displayStr

index = gNumItems

// all test should pass
for i = 0 to index
tempStr    = gTestStr( i )
displayStr = tempStr

fn FBPStr2CStr( tempStr )// convert to a C string
found = fn search1( @tempStr )
fn showIfFound ( found , displayStr )

next

print
print
tempStr    = "form"// should fail because its a substring
displayStr = tempStr
fn FBPStr2CStr( tempStr )// convert to a C string
found = fn search1( @tempStr )
fn showIfFound ( found , displayStr )

// all test should fail
for i = 0 to index
tempStr    = gTestStr( i ) + "x"
displayStr = tempStr
fn FBPStr2CStr( tempStr )// convert to a C string
found = fn search1( @tempStr )
fn showIfFound ( found , displayStr)
next

end fn


local fn initTernaryTree
'~'1
gRoot = fn newptrclear( sizeof(Tnode) )
end fn

fn initTernaryTree
fn loadCStrings
fn testCStrings

//fn traverse( gRoot ) // doesnt work

fn cleanup1( gRoot )

print gDeleteNodeCount, gNodeCount






-----Original Message-----
From: Edwards, Waverly [mailto:Waverly.Edwards@...]
Sent: Thu 8/24/2006 6:51 PM
To: futurebasic@...
Subject: RE: [FB] Ternary Search Trees


Hey Jay,

I got a version working.  It still uses C string but its functional.
I'm leery of bugs and will post this evening or tomorrow morning.


W.

________________________________

From: Jay Reeve [mailto:jayreeve@...]
Sent: Thursday, August 24, 2006 2:15 AM
To: futurebasic@...
Subject: Re: [FB] Ternary Search Trees


On Aug 23, 2006, at 6:18 PM, Edwards, Waverly wrote:


        since PASCAL type are different than C style strings there may
be a better way to implement the code.
       


To show how I would handle the string differences, here is my version of
fn Search( s ). I've introduced a var c to track which char of string s
we're testing, because that's the only way to know when we've reached
the end of a pString.

BTW, this code assumes creation of separate pointers for each node. It
may be easier to put all the nodes in a dynamic array, and refer to them
by their elem numbers rather than with pointers, but pointers should be
slightly faster. You can actually do both (at least in OSX), creating
new nodes as members of a dynamic array, but then taking their addresses
to use as pointers.

/*typedef struct tnode *Tptr;
typedef struct tnode {
   char splitchar;
   Tptr lokid, eqkid, hikid;
} Tnode; */

begin record tNode
dim as ptr loKid, eqKid, hiKid
dim as char splitChar
dim & ' optional--test for effect on speed
end record

dim root as tNode

/*int search(char *s)
{   Tptr p;
    p = root;
    while (p) {
       if (*s < p->splitchar)
           p = p->lokid;
       else if (*s == p->splitchar) {
          if (*s++ == 0)
              return 1;
          p = p->eqkid;
      } else
          p = p->hikid;
    }
    return 0;
} */

local fn search( s as ^str255 )
dim c, found
dim node as ^tNode
found = _false
c     = 1' start w 1st char of s
node  = @root

while node ' if node becomes 0, our search has failed
select s.0$[c] - node.splitChar ' compare chars
case < 0 ' no match, check lower kid
node = node.loKid

case > 0' no match, check higher kid
node = node.hiKid

case 0 ' char matches
c ++' check next char of s
if c > s.0``  then found = _zTrue: exit fn ' no more chars?
node = node.eqKid ' move to next char of tree

end select
wend

end fn = found





--------
Hey Jay,

I got a version working.  It still uses C string but its functional.
I'm leery of bugs and will post this evening or tomorrow morning.


W.

________________________________

From: Jay Reeve [mailto:jayreeve@...]
Sent: Thursday, August 24, 2006 2:15 AM
To: futurebasic@...
Subject: Re: [FB] Ternary Search Trees


On Aug 23, 2006, at 6:18 PM, Edwards, Waverly wrote:


        since PASCAL type are different than C style strings there may
be a better way to implement the code.
       


To show how I would handle the string differences, here is my version of
fn Search( s ). I've introduced a var c to track which char of string s
we're testing, because that's the only way to know when we've reached
the end of a pString.

BTW, this code assumes creation of separate pointers for each node. It
may be easier to put all the nodes in a dynamic array, and refer to them
by their elem numbers rather than with pointers, but pointers should be
slightly faster. You can actually do both (at least in OSX), creating
new nodes as members of a dynamic array, but then taking their addresses
to use as pointers.

/*typedef struct tnode *Tptr;
typedef struct tnode {
   char splitchar;
   Tptr lokid, eqkid, hikid;
} Tnode; */

begin record tNode
dim as ptr loKid, eqKid, hiKid
dim as char splitChar
dim & ' optional--test for effect on speed
end record

dim root as tNode

/*int search(char *s)
{   Tptr p;
    p = root;
    while (p) {
       if (*s < p->splitchar)
           p = p->lokid;
       else if (*s == p->splitchar) {
          if (*s++ == 0)
              return 1;
          p = p->eqkid;
      } else
          p = p->hikid;
    }
    return 0;
} */

local fn search( s as ^str255 )
dim c, found
dim node as ^tNode
found = _false
c     = 1' start w 1st char of s
node  = @root

while node ' if node becomes 0, our search has failed
select s.0$[c] - node.splitChar ' compare chars
case < 0 ' no match, check lower kid
node = node.loKid

case > 0' no match, check higher kid
node = node.hiKid

case 0 ' char matches
c ++' check next char of s
if c > s.0``  then found = _zTrue: exit fn ' no more chars?
node = node.eqKid ' move to next char of tree

end select
wend

end fn = found





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



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



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