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