Trie
Posted: Thu Sep 16, 2010 7:49 pm
Trie structure, to stores a dictionary and option value
http://en.wikipedia.org/wiki/Trie
edited, bug fix
uses
Search for a list of words from a given root
Auto complete
Spell Checker
Store keys / values pairs
The Enum function is a bit convoluted and could be improved, if someone can do it, please do
Also probably needs a remove function too
http://en.wikipedia.org/wiki/Trie
edited, bug fix
uses
Search for a list of words from a given root
Auto complete
Spell Checker
Store keys / values pairs
The Enum function is a bit convoluted and could be improved, if someone can do it, please do
Also probably needs a remove function too
Code: Select all
;Trie, Stores a dictionay with an optional value for each entry
;see http://en.wikipedia.org/wiki/Trie
;mTrie.clsTree = NewTrie(@mTrie)
;mTrie\Add("someword",value=1)
;mTrie\LookUp("someword") returns the key Value or 0
;mTrie\Enum("wordroot",@MyTrieCallBack()) returns all the words under the root
;mTrie\Free() ;releases the memory
;Note for Enum you need to declare a callback function
;Procedure MyTreeCallBack(*item)
; Debug PeekS(*item)
;EndProcedure
;Things to do
;Sort out the Enum function, it's a bit messy
;Add a remove function
Structure edge
edge.i[256]
EndStructure
Structure TrieNode;
Value.i;
Count.i;
Vertex.edge
EndStructure;
Structure Trie
*vt.i
*root.TrieNode;
EndStructure;
Declare FreeNodes(*node.TrieNode)
Declare NewTrie(*obj.Trie)
Declare FreeTrie(*this.Trie)
Declare AddTrie(*this.Trie,key.s,value.i=1)
Declare lookupTrie(*this.Trie,key.s)
Declare iEnumTrie(*this.Trie,*node.TrieNode,key.s,*fn)
Declare EnumTrie(*this.Trie,key.s,*fn.i)
Interface clsTrie
Free()
Add(key.s,item.i=1)
LookUp(key.s)
Enum(key.s,*fn.i)
EndInterface
Procedure FreeNodes(*node.TrieNode)
;Free all Trie Nodes
Protected a.i
If Not *node
ProcedureReturn;
EndIf
For a=0 To 255
FreeNodes(*node\Vertex\edge[a]);
Next
If *node
FreeMemory(*node)
EndIf
EndProcedure
Procedure NewTrie(*obj.Trie)
*obj = AllocateMemory(SizeOf(Trie))
If *obj
*obj\vt=?vt_Trie
EndIf
*obj\root = AllocateMemory(SizeOf(TrieNode))
ProcedureReturn *obj
EndProcedure
Procedure FreeTrie(*this.Trie)
;free the Trie
FreeNodes(*this\root)
FreeMemory(*this)
EndProcedure
Procedure AddTrie(*this.Trie,key.s,value.i=1)
;Add item to the Trie, value is optional
Protected *tnode.TrieNode,*node.TrieNode,len.i,tkey.i,lkey.i,pos.i
len = Len(key)
lkey.i
If Not len
ProcedureReturn;
EndIf
*node = *this\root;
While pos < Len+1
tkey = PeekB(@key+pos) & $FF
If Not *node
*node = AllocateMemory(SizeOf(TrieNode))
*tnode\Vertex\edge[lkey] = *node
EndIf
*node\count + 1
If pos = len
*node\value = value
EndIf
*tnode = *node
*node = *node\Vertex\edge[tkey]
lkey = tkey
pos+1
Wend
EndProcedure
Procedure lookupTrie(*this.Trie,key.s)
;Find the value of the key returns the value or 0
Protected *node.TrieNode,*bkey.byte,result.i
*node = *this\root
*bkey = @key
*node = *node\Vertex\edge[*bkey\b & $FF]
While *bkey\b <> 0
If Not *node
ProcedureReturn 0
EndIf
*bkey+1
result = *node\value
*node = *node\Vertex\edge[*bkey\b & $FF]
Wend
ProcedureReturn result
EndProcedure
Procedure iEnumTrie(*this.Trie,*node.TrieNode,key.s,*fn)
;internal Enum trie
Protected a.i,tkey.s
If Not *node
ProcedureReturn;
EndIf
;build the key
For a=0 To 255
If *node\Vertex\edge[a]
tkey = key + Chr(a)
iEnumTrie(*this,*node\Vertex\edge[a],tkey,*fn);
Else
tkey = key
EndIf
Next
;lookup the key
If lookupTrie(*this,tkey)
CallFunctionFast(*fn,@tkey)
key=tkey
ProcedureReturn *node
EndIf
EndProcedure
Procedure EnumTrie(*this.Trie,key.s,*fn.i)
;enumerate all the entries below given root key
Protected *node.TrieNode,*tnode.TrieNode,tkey.i,len.i,pos.i
*node = *this\root;
tkey = PeekB(@key) & $FF;
len = Len(key)
*node = *node\Vertex\edge[tkey]
;find the root
While *node
If *node
*tnode =*node
EndIf
pos+1
tkey = PeekB(@key+pos) & $FF
*node = *node\Vertex\edge[tkey]
Wend
;enum the root
While *tnode
*tnode = iEnumTrie(*this,*tnode,key,*fn)
tkey = PeekB(@key+pos) & $FF
If *tnode
*tnode = *tnode\Vertex\edge[tkey]
EndIf
Wend
EndProcedure
DataSection: vt_Trie:
Data.i @FreeTrie()
Data.i @AddTrie()
Data.i @lookupTrie()
Data.i @EnumTrie()
EndDataSection
;Test code_____________________________________________________________________
Procedure MyTreeCallBack(*item)
Debug PeekS(*item)
EndProcedure
Global mt.clsTrie = NewTrie(@mt)
mt\Add("a",1)
mt\Add("abba",2)
mt\Add("abracadabbra",3)
mt\Add("ant",4)
mt\Add("and",5)
mt\Add("andy",6)
mt\Add("andrew",7)
mt\Add("andrews",8)
mt\Add("bob",9)
mt\Add("bobo",10)
mt\Add("bobob",11)
Debug mt\LookUp("andy")
mt\Enum("ab",@MyTreeCallBack())
mt\Free()