November 28, 2020, 11:14:03 AM

### Author Topic: [bmx] Simple prefix tree by matibee [ 1+ years ago ]  (Read 527 times)

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bmx] Simple prefix tree by matibee [ 1+ years ago ]
« on: June 29, 2017, 12:28:41 AM »
Title : Simple prefix tree
Author : matibee
Posted : 1+ years ago

Description : This is a fairly naive implementation of a prefix tree..

<a href="http://en.wikipedia.org/wiki/Trie" target="_blank">http://en.wikipedia.org/wiki/Trie[/url]

It only works with lower case, basic ascii [a..z] strings.

Code :
Code: BlitzMax
1. SuperStrict
2.
3. Type wordTreeNode
4.         Field move:Object[26]   ' pointers to the next node for each letter [a-z]
5.         Field stop:Int[26]      ' denotes a word ending with at this node
6.
8.                 Local ch:Int = word\$[0] - 97
9.                 If ( Len (word\$ ) = 1 )
10.                         stop[ ch ] = True
11.                 Else
12.                         If ( Not move[ ch ] )
13.                                 move[ ch ] = New wordTreeNode
14.                         End If
15.                         wordTreeNode( move[ ch ] ).AddWord( Right( word\$, Len( word\$ ) - 1 ) )
16.                 End If
17.         End Method
18.
19.         Method CheckWord:Int ( word\$ )
20.                 Local ch:Int = word\$[0] - 97
21.                 If ( Len ( word\$ ) = 1 )
22.                         Return stop[ ch ]
23.                 Else If ( move[ ch ] )
24.                         Return wordTreeNode( move[ ch ] ).CheckWord( Right( word\$, Len( word\$ ) - 1 ) )
25.                 End If
26.                 Return False
27.         End Method
28.
29. End Type
30.
31. Type wordTree
32.         Field base:wordTreeNode[26]
33.
35.                 Assert( Len( word\$ ) > 1 ) Else "Word too short ~q" + word\$ + "~q"
36.                 Local ch:Int = word\$[0] - 97
37.                 If ( Not base[ ch ] ) base[ ch ] = New wordTreeNode
38.                 base[ ch ].AddWord( Right( word\$, Len( word\$ ) - 1 ) )
39.         End Method
40.
41.         Method CheckWord:Int ( word\$ )
42.                 If ( Len( word\$ ) < 2 ) Return False
43.                 Local ch:Int = word\$[0] - 97
44.                 If ( base[ ch ] ) Return base[ ch ].CheckWord( Right( word\$, Len( word\$ ) - 1 ) )
45.                 Return False
46.         End Method
47.
48. End Type
49.
50. ' example usage..
51. Local tree:wordTree = New wordTree