Trie Data Structure
Posted: 14 Aug 2017, 10:42
An AHK implementation of a trie. Tries are a type of tree where the values are read from root to leaf, this makes them suited for things like typing suggestions because you are able to search through only the branches that start with a specific prefix.
Source
Intended Use
The only function that is meant to be manually used from outside the Class is __Set since trie[key] := "" behaves in an undesirable way for this class.
To get data from the trie use the syntax trie[key]
Test: Typing Suggestions
Code: Select all
Class Trie {
__Data := {}
__Count := 0
__Bool := False
__New(Max := False, params*) {
this.__Max := Max
for i, v in params {
this.__Set(v, "")
}
}
__Get(key) {
if(!__StrInList(key, ["__Data", "__Count", "__Max", "__Bool"])) {
if(StrLen(key) > 0) {
obj := this.__Data
for i, char in StrSplit(key) {
obj := obj[char]
}
this.__Count := 0
return obj ? StrSplit(SubStr(this.getKeys(obj, key), 1, -1), "`n") : []
}
}
}
__Set(key, val) {
if(!__StrInList(key, ["__Data", "__Count", "__Max", "__Bool"])) {
if(StrLen(key) > 0) {
this.__Bool := True
obj := this.__Data
for i, char in StrSplit(key) {
; Save reference to the parent of the leaf for use after loop
preObj := obj
obj := this.addCharToTrie(obj, char)
}
; Handle if word is ending inside the trie
if(!this.objIsEmty(obj)) {
obj["word"] := True
}
; If the key ends in a leaf it don't need to be an object
if(this.objIsEmty(obj)) {
preObj[char] := True ; (this is to save memory)
}
}
}
}
remove(key) {
if(this.__Data.HasKey(SubStr(key, 1, 1))) {
; Get references to all the characters in the branch
branch := [this.__Data[SubStr(key, 1, 1)]]
for i, char in StrSplit(SubStr(key, 2)) {
if(branch[i].HasKey(char)) {
branch.Push(branch[i][char])
} else {
return
}
}
len := branch.Length()
; Handle if the key is not ending in a leaf
branch[branch.MaxIndex()].Delete("word")
; Deleat chars from the leaf to the root if nothing else will disappear as a result of the deletion
loop % len {
index := len + 1 - A_Index
if(this.objIsEmty(branch[index], "")) {
branch[index - 1].Delete(SubStr(key, index, 1))
} else {
if(this.objIsEmty(branch[index])) {
branch[index - 1][SubStr(key, index, 1)] := True ; (this is to save memory)
}
return
}
}
}
}
getKeys(obj, key) {
if(this.objIsEmty(obj)) {
this.__Count++
return key "`n"
}
if(obj.HasKey("word")) {
this.__Count++
res := key "`n"
}
for char in obj {
if(this.__Max && this.__Count >= this.__Max) {
Break
}
if(StrLen(char) == 1) {
res .= this.getKeys(obj[char], key char)
}
}
return res
}
addCharToTrie(obj, key) {
if(!obj.HasKey(key)) {
; If a new leaf is added from an empty leaf, there must have been a word ending in the late leaf
if(this.__Bool && this.objIsEmty(obj) && obj != this.__Data) {
obj["word"] := True
}
this.addLeaf(obj, key)
this.__Bool := False
}
; If it is a leaf it will not ba an object
if(!IsObject(obj[key])){
this.addLeaf(obj, key)
}
return obj[key]
}
addLeaf(obj, char) {
obj[char] := {}
obj.SetCapacity(0) ; (this is to save memory)
}
objIsEmty(obj, except := "word") {
for key in obj {
if(key != except) {
return False
}
}
return True
}
}
__StrInList(str, lst) {
if str in % __Join(",", lst)
return True
return False
}
__Join(sep, params) {
for index, param in params {
str .= param sep
}
return SubStr(str, 1, -StrLen(sep))
}
MsgObj(obj) {
MsgBox, % SubStr(ObjectToString(obj), 1, -1)
}
ObjectToString(obj){
if(!IsObject(obj)){
return """" obj """"
}
res := "{"
for key, value in obj {
res .= """" key """ : " ObjectToString(value) ", "
}
return SubStr(res, 1, -2) "}"
}
To get data from the trie use the syntax trie[key]
Code: Select all
#Include Trie.ahk
SetBatchLines, -1
CoordMode, Mouse, Screen
Entries := new Trie(500, "Autohotkey")
BackgroundColor := "C6D43C"
WM_SETREDRAW := 0x0B
Gui, 1:New
Gui, +AlwaysOnTop +ToolWindow -SysMenu -Caption +HwndGuiHwnd +LastFound ; +E0x08000000
Gui, Color, %BackgroundColor%
Gui, Font, s15
Gui, Margin, 0, 0, 0, 0
Gui, Add, Edit, vAddress gSearch w300
Gui, Add, ListBox, vSuggestions w300 h200 +HwndCtrlHwnd
WinSet, TransColor, %BackgroundColor%
AddDict()
return
#s::
MouseGetPos, x, y
Gui, Show, % "x" x " y" y " AutoSize"
return
AddDict() {
Global Entries
lst := StrSplit(FileOpen("English British.txt", "r").Read(), "`n")
len := Round(lst.Length() / 100)
for index, line in lst {
if(!mod(index, len)) {
ToolTip, % Format("{:02.1d}", (index / lst.Length())*100)
}
Entries.__Set(Format("{:L}", (pos := InStr(line, "/")) ? SubStr(line, 1, pos - 1) : RegExReplace(line, "`n|`r")), "")
}
ToolTip
}
#If WinActive("ahk_id " GuiHwnd)
Enter::
Gui, Submit, NoHide
Entries.__Set(Address, "")
Goto, Search
return
Delete::
Gui, Submit, NoHide
Entries.remove(Address)
Goto, Search
return
#If
Search:
Gui, Submit, NoHide
GuiControl, -Redraw, Suggestions
GuiControl, , Suggestions, % "|" __Join("|", Entries[Address])
GuiControl, +Redraw, Suggestions
Return