diff options
Diffstat (limited to 'gamemode/utility')
| -rw-r--r-- | gamemode/utility/fn.lua | 229 | ||||
| -rw-r--r-- | gamemode/utility/fuzzel.lua | 286 | ||||
| -rw-r--r-- | gamemode/utility/stream.lua | 85 |
3 files changed, 600 insertions, 0 deletions
diff --git a/gamemode/utility/fn.lua b/gamemode/utility/fn.lua new file mode 100644 index 0000000..7c53150 --- /dev/null +++ b/gamemode/utility/fn.lua @@ -0,0 +1,229 @@ +--[[ + Various functional programming bits and bobs + Function signatures: + fn.curry(func,...) :: function(...) :: any + fn.map(tbl,func) :: table + fn.compose(...) :: function(...) :: any + fn.filter(tbl,func) :: table + fn.zip(...) :: table + fn.fill(arg,times) :: table + fn.amalg(...) :: function(...) :: any + fn.cycle(tbl) :: table + fn.fold(tbl) :: function(func(T1,T2)::T) :: T + fn.flatten(tbl) :: table +]] +--AddCSLuaFile() +local fn = {} + +if table.Copy == nil then + function table.Copy(tbl) + local ntbl = {} + for k,v in pairs(tbl) do ntbl[k] = v end + return ntbl + end +end + +--[[ + Puts some arguments "in" a function so that it can be called with some number fewer arguments. + Ex: + local f = include("nightz/gamemode/utility/functional.lua") + local debugprint = f.curry(print,"[DEBUG]") + debugprint("Hello, world!") + --Is the same as + print("[DEBUG]","Hello, world!") +]] +function fn.curry(func,...) + local nargs = {...} + return function(...) + for k,v in pairs({...}) do + nargs[k + #nargs] = v + end + func(unpack(nargs)) + end +end + +--[[ + calls each function from first to last on every element of tbl, and returns a table with the function called. + Ex: + local f = include("nightz/gamemode/utility/functional.lua") + local playerents = { + Player(1), + Player(2), + Player(3) + } + local getname = function(ply) return ply:Nick() end + local playernames = f.map(playerents) + --playernames is now a table { + "Player1_name", + "Player2_name", + "Player3_name" + } +]] +function fn.map(tbl,...) + local nfuncs = {...} + local ntbl = table.Copy(tbl) + for i,j in pairs(nfuncs) do + for k,v in pairs(tbl) do + ntbl[k] = j(v) + end + end + return ntbl +end + +--[[ + Calls a list of functions, starting with the last, going to the first, and passes the arguments as whatever was outputed from the previous function. + Ex: + local f = include("nightz/gamemode/utility/functional.lua") + local printf = f.compose(print,string.format) + printf("Thanks, I love %d",5) + --Is the same as + print(string.format("Thanks, I love %d", 5)) +]] +function fn.compose(...) + local nargs = {...} + local n = #nargs + local lastresult + return function(...) + lastresult = {...} + while n > 0 do + lastresult = {nargs[n](unpack(lastresult))} + n = n - 1 + end + end +end + +--[[ + Removes elements from tbl for which func returns nil or false (returns new table). this WILL mess up order for arrays. + Ex: + local f = include("nightz/gamemode/utility/functional.lua") + local sometable = { + 1,3,4,5,5,6,7,8,9 + } + for k,v in pairs(sometable) do print(k,":",v) end + --this will print: + 1:1 + 2:3 + 3:4 + 4:5 + 5:5 + 6:6 + 7:7 + 8:8 + 9:9 + local function iseven(k) return k%2 == 0 end + local evens = f.filter(sometable,iseven) + for k,v in pairs(evens) do print(k,":",v) end + --this will print: + 3:4 + 6:6 + 8:8 +]] +function fn.filter(tbl,func) + local ntbl = table.Copy(tbl) + for k,v in pairs(ntbl) do + if not func(v) then + ntbl[k] = nil + end + end +end + +--Takes n tables that have the same indexes, and returns a table that for every index, it's value is {tbl1[index],tbl2[index],...,tbln[index]} +function fn.zip(...) + local nargs = {...} + local ntbl = table.Copy(nargs[1]) + for k,v in pairs(ntbl) do + local ttbl = {} + for i,j in pairs(nargs) do + ttbl[#ttbl + 1] = v[i] + end + ntbl[k] = ttbl + end + return ntbl +end + +--Creates a table filled with <times> number of arg +function fn.fill(arg,times) + local ret = {} + for i = 1,times do + ret[i] = arg + end + return ret +end + +--Calls all functions passed in order, and returns all results for all functions called.S +function fn.amalg(...) + local nargs = {...} + return function(...) + local nret = {} + for k,v in pairs(nargs) do + local tret = {v(unpack({...}))} + for i,j in pairs(tret) do + nret[#nret + 1] = j + end + end + return unpack(nret) + end +end + +--[[ +Cycles a table infinitely + Ex: + local sometbl = {1,2,3} + fn.cycle(sometbl) + for i = 1, 100 do + print(sometbl[i]) + end + Outputs: + 1 + 2 + 3 + 1 + 2 + : + : + : +]] +function fn.cycle(tbl) + local ntbl = table.Copy(tbl) + local tbllen = #tbl + local mt = { + __index = function(self, ind) + local id = (ind % tbllen) + 1 + return tbl[id] + end + } + setmetatable(ntbl,mt) + return ntbl +end + +--[[ + Iterates over a table applying a function to each item + Ex: + local sometbl = {1,4,5,6,7,10} + local add = function(a,b) return a + b end + local sum = fn.fold(sometbl)(add) + print(sum) + Output: + 33 +]] +function fn.fold(tbl) + return function(func) + local running = tbl[1] + for k = 2, #tbl do + running = func(running,tbl[k]) + end + return running + end +end + +--[[ + Returns an array-type table +]] +function fn.flatten(tbl) + local ret = {} + for k,v in pairs(tbl) do + ret[#ret + 1] = v + end + return ret +end +return fn diff --git a/gamemode/utility/fuzzel.lua b/gamemode/utility/fuzzel.lua new file mode 100644 index 0000000..6aad45f --- /dev/null +++ b/gamemode/utility/fuzzel.lua @@ -0,0 +1,286 @@ +--[[ + Fuzzel v1.3 - Alexander "Apickx" Pickering + Entered into the public domain June 2, 2016 + You are not required to, but consider putting a link to the source in your file's comments! + + Some helper functions for calculateing distance between two strings + + Provides: + fuzzel.LevenshteinDistance_extended(string_first, string_second, number_addcost, number_substituecost, number_deletecost) + Calculates the Levenshtein Distance between two strings, useing the costs given. "Real" Levenshtein Distance uses values 1,1,1 for costs. + returns number_distance + + fuzzel.LevenshteinDistance(string_first, strings_second) + Calculates the "real" Levenshtein Distance + returns number_distance + + fuzzel.LevensteinRatio(string_first, string_second) + The Levenshtein Ratio divided by the first string's length. Useing a ratio is a decent way to determin if a spelling is "close enough" + returns number_distance + + fuzzel.DamerauLevenshteinDistance_extended(string_first, string_second, number_addcost, number_substituecost, number_deletecost, number_transpositioncost) + Damerau-Levenshtein Distance is almost exactly like Levenshtein Distance, with the caveat that two letters next to each other, with swapped positions only counts as "one" cost (in "real" Damerau-Levenshtein Distance) + returns number + + fuzzel.DamerauLevenshteinDistance(stirng_first, strings_second) + Calculates the "real" Damerau-Levenshtein Distance + returns number + + fuzzel.DamerauLevenshteinRatio(string_first, string_second) + The Damerau-Levenshtein Distance divided by the first string's length + returns number_ratio + + fuzzel.HammingDistance(string_first, string_second) + Purely the number of substitutions needed to change one string into another. Note that both strings must be the same length. + returns number_distance + + fuzzel.HammingRatio(string_first, string_second) + The hamming distance divided by the length of the first string + returns number_ratio + + fuzzel.FuzzyFindDistance(string_needle, vararg_in) + in may be either a table, or a list of arguments. fuzzel.FuzzySearchDistance will find the string that most closely resembles needle, based on Damerau-Levenshtein Distance. If multiple options have the same distance, it will return the first one encountered (This may not be in any sort of order!) + returns string_closest, number_distance + + fuzzel.FuzzyFindRatio(string_needle, vararg_in) + in may be either a table, or a list of arguments. Same as above, except it returns the string with the closest Damerau-Levenshtein ratio. + returns string_closest, nubmer_ratio + + fuzzel.FuzzySortDistance(string_needle, vararg_in) + Sorts either the table, or the arguments, and returns a table. Uses Damerau-Levenshtein Distance + returns table_sorted + + fuzzel.FuzzySortRatio(string needle, vararg_in) + Same as above, but uses Damerau-Levenshtein Ratio instead + returns table_sorted + + fuzzel.FuzzyAutocompleteDistance(string_needle, vararg in) + vararg_in can be either a table, or a list of entries, this will fuzzy sort based on the length of the input, which makes it better at autocompletion than fuzzy sorting. Uses Damerau-Levenshtein Distance. + returns table_sorted + + fuzzel.FuzzyAutocompleteRatio(string_needle, vararg_in) + Same as above, but uses DamerauLevenshteinRatio + returns table_sorted + + Example: + Returns a function that will return the closest string to the string it was passed + -----------------FuzzelExample.lua------------------ + --Include the module + local fuzzel = require("fuzzel.lua") + + --A couple of options + local options = { + "Fat Cat", + "Lazy Dog", + "Brown Fox", + } + + --And use it, to see what option closest matches "Lulzy Cat" + local close,distance = fuzzel.FuzzyFindDistance("Lulzy Cat", options) + print("\"Lulzy Cat\" is close to \"" .. close .. "\", distance:" .. distance) + + --Sort the options to see the order in which they most closely match "Frag God" + print("\"Frag God\" is closest to:") + for k,v in ipairs(fuzzel.FuzzySortRatio("Frag God",options)) do + print(k .. "\t:\t" .. v) + end + -------------End FuzzelExample.lua------------------ + Outputs: + "Lulzy Cat" is close to "Fat Cat" + "Frag God" is closest to: + 1 : Fat Cat + 2 : Lazy Dog + 3 : Brown Fox + + Some easy-to-use mnemonics + fuzzel.ld_e = fuzzel.LevenshteinDistance_extended + fuzzel.ld = fuzzel.LevenshteinDistance + fuzzel.lr = fuzzel.LevensteinRatio + fuzzel.dld_e = fuzzel.DamerauLevenshteinDistance_extended + fuzzel.dld = fuzzel.DamerauLevenshteinDistance + fuzzel.dlr = fuzzel.DamerauLevenshteinRatio + fuzzel.hd = fuzzel.HammingDistance + fuzzel.hr = fuzzel.HammingRatio + fuzzel.ffd = fuzzel.FuzzyFindDistance + fuzzel.ffr = fuzzel.FuzzyFindRatio + fuzzel.fsd = fuzzel.FuzzySortDistance + fuzzel.fsr = fuzzel.FuzzySortRatio + fuzzel.fad = fuzzel.FuzzyAutocompleteDistance + fuzzel.far = fuzzel.FuzzyAutocompleteRatio + +]]--You probably don't want to touch anything past this point + +--Assign locals to these to the minifier can compress the file better +local strlen,chrat,min,asrt,prs,iprs,typ,upack,tblins,tblsrt,strsub,tru,fal = string.len,string.byte,math.min,assert,pairs,ipairs,type,unpack,table.insert,table.sort,string.sub,true,false + +local fuzzel = {} + +--A clever way to allow the minifier to minify function names, this basically just assigns variables with their string equivalent. +local da, le, di, ra, fu, fi, so, ex, ha, au = "Damerau", "Levenshtein", "Distance", "Ratio", "Fuzzy", "Find", "Sort", "_extended", "Hamming", "Autocomplete" +local LevenshteinDistance_extended,LevenshteinDistance,LevenshteinRatio,DamerauLevenshteinDistance_extended,DamerauLevenshteinDistance,DamerauLevenshteinRatio,FuzzyFindDistance,FuzzyFindRatio,FuzzySortDistance,FuzzySortRatio,HammingDistance,HammingRatio,FuzzyAutocompleteDistance,FuzzyAutocompleteRatio = le..di..ex,le..di,le..ra,da..le..di..ex,da..le..di,da..le..ra,fu..fi..di,fu..fi..ra,fu..so..di,fu..so..ra,ha..di,ha..ra,fu..au..di,fu..au..ra + +local function genericDistance( stringa, stringb, addcost, subcost, delcost, ...) + local arg = {...} + + --Length of each string + local salen, sblen = strlen(stringa), strlen(stringb) + + --Create a 0 matrix the size of len(a) x len(b) + local dyntbl = {} + for i = 0,salen do + dyntbl[i] = {} + for j = 0,sblen do + dyntbl[i][j] = 0 + end + end + + --Initalize the matrix + for i = 1,salen do + dyntbl[i][0] = i + end + for j = 1,sblen do + dyntbl[0][j] = j + end + + --And build up the matrix based on costs-so-far + for j = 1,sblen do + for i = 1,salen do + local ca,cb = chrat(stringa,i),chrat(stringb,j) + dyntbl[i][j] = min( + dyntbl[i-1][j] + delcost, --deletion + dyntbl[i][j-1] + addcost, --insertion + dyntbl[i-1][j-1] + (ca == cb and 0 or subcost) --substituion + ) + if arg[1] and i > 1 and j > 1 and ca == chrat(stringb,j-1) and chrat(stringa,i-1) == cb then + dyntbl[i][j] = min(dyntbl[i][j], + dyntbl[i-2][j-2] + (ca == cb and 0 or arg[2])) --transposition + end + end + end + + return dyntbl[salen][sblen] +end + +fuzzel[LevenshteinDistance_extended] = function(stringa, stringb, addcost, subcost, delcost) + return genericDistance(stringa, stringb, addcost, subcost, delcost) +end +fuzzel.ld_e = fuzzel[LevenshteinDistance_extended] + +fuzzel[LevenshteinDistance] = function(stringa,stringb) + return fuzzel.ld_e(stringa,stringb,1,1,1) +end +fuzzel.ld = fuzzel[LevenshteinDistance] + +fuzzel[LevenshteinRatio] = function(stringa,stringb) + return fuzzel.ld(stringa,stringb) / strlen(stringa) +end +fuzzel.lr = fuzzel[LevenshteinRatio] + +fuzzel[DamerauLevenshteinDistance_extended] = function(stringa, stringb, addcost, subcost, delcost, trncost) + return genericDistance(stringa,stringb,addcost,subcost,delcost,tru,trncost) +end +fuzzel.dld_e = fuzzel[DamerauLevenshteinDistance_extended] + +fuzzel[DamerauLevenshteinDistance] = function(stringa,stringb) + return fuzzel.dld_e(stringa,stringb,1,1,1,1) +end +fuzzel.dld = fuzzel[DamerauLevenshteinDistance] + +fuzzel[DamerauLevenshteinRatio] = function(stringa,stringb) + return fuzzel.dld(stringa,stringb) / strlen(stringa) +end +fuzzel.dlr = fuzzel[DamerauLevenshteinRatio] + +fuzzel[HammingDistance] = function(stringa,stringb) + local len,dist = strlen(stringa),0 + asrt(len == strlen(stringb), ha.." "..di.." cannot be calculated on two strings of different lengths:\"" .. stringa .. "\" \"" .. stringb .. "\"") + for i = 1,len do + dist = dist + ((chrat(stringa,i) ~= chrat(stringb,i)) and 1 or 0) + end + return dist +end +fuzzel.hd = fuzzel[HammingDistance] + +fuzzel[HammingRatio] = function(stringa,stringb) + return fuzzel.hd(stringa,stringb) / strlen(stringa) +end +fuzzel.hr = fuzzel[HammingRatio] + +local function FuzzySearch(str,func,...) + local arg = {...} + + --Allow varargs, or a table + local looparg = typ(arg[1]) == "table" and arg[1] or arg + + --Find the string with the shortest distance to the string we were supplied + local tmin,sout = func(looparg[1],str),looparg[1] + for k,v in prs(looparg) do + local t = func(v,str) + if t <= tmin then + tmin,sout = t,k + end + end + return looparg[sout], tmin +end + +fuzzel[FuzzyFindDistance] = function(str,...) + return upack{FuzzySearch(str,fuzzel.dld,...)} +end +fuzzel.ffd = fuzzel[FuzzyFindDistance] + +fuzzel[FuzzyFindRatio] = function(str,...) + return upack{FuzzySearch(str,fuzzel.dlr,...)} +end + +local function FuzzySort(str, func, short, ...) + local arg = {...} + + --allow varargs, or a table + local looparg = typ(arg[1]) == "table" and arg[1] or arg + + --Roughly sort everything by it's distance to the string + local usorted,sorted,otbl,slen = {},{},{},strlen(str) + for k,v in prs(looparg) do + local sstr = short and strsub(v,0,slen) or v + local dist = func(str,sstr) + if usorted[dist] == nil then + usorted[dist] = {} + tblins(sorted,dist) + end + tblins(usorted[dist],v) + end + + --Actually sort them into something can can be iterated with ipairs + tblsrt(sorted) + + --Then build our output table + for k,v in iprs(sorted) do + for i,j in prs(usorted[v]) do + tblins(otbl,j) + end + end + return otbl +end +fuzzel.ffr = fuzzel[FuzzyFindRatio] + +fuzzel[FuzzySortDistance] = function(str,...) + return FuzzySort(str,fuzzel.dld,fal,...) +end +fuzzel.fsd = fuzzel[FuzzySortDistance] + +fuzzel[FuzzySortRatio] = function(str,...) + return FuzzySort(str,fuzzel.dlr,fal,...) +end +fuzzel.fsr = fuzzel[FuzzySortRatio] + +fuzzel[FuzzyAutocompleteDistance] = function(str, ...) + return FuzzySort(str,fuzzel.dld,tru,...) +end +fuzzel.fad = fuzzel[FuzzyAutocompleteDistance] + +fuzzel[FuzzyAutocompleteRatio] = function(str,...) + return FuzzySort(str,fuzzel.dlr,tru,...) +end +fuzzel.far = fuzzel[FuzzyAutocompleteRatio] + +return fuzzel diff --git a/gamemode/utility/stream.lua b/gamemode/utility/stream.lua new file mode 100644 index 0000000..cdf3933 --- /dev/null +++ b/gamemode/utility/stream.lua @@ -0,0 +1,85 @@ +--[[ + A stream object, has the methods: + stream:WriteString(string) :: nil + stream:WriteInt(num,bytes) :: nil + + stream:ReadString() :: string + stream:ReadInt(bytes) :: number + + stream:ToString() :: string +]] + +local ss = {} + +local function WriteString(self,string) + local buflen = #self.buf + for i=1,#string do + self.buf[buflen+i] = string.byte(string,i) + end + self.buf[#self.buf + 1] = 0 +end + +local function WriteInt(self,num,bytes) + local buflen = #self.buf + local byte = 255 + for i = 1,bytes do + --[[ + pack[i] = (num & byte) >> (i-1)*8 + byte = 255 << i*8 + ]] + self.buf[buflen + i] = bit.rshift(bit.band(num,byte),(i-1)*8) + byte = bit.lshift(255,i*8) + end +end + +local function ReadInt(self,len) + local tbl = {} + for i = 1, len do + tbl[i] = self.buf[i] + end + for i = 1, #self.buf do + self.buf[i] = self.buf[i+len] + end + local byte = 1 + local num = 0 + for i = 1, #tbl do + num = num + (tbl[i] * byte) + byte = 2 ^ (i*8) + end + return num +end + +local function ReadString(self) + local str = {} + local strlen = 1 + while self.buf[strlen] ~= 0 do + str[#str + 1] = string.char(self.buf[strlen]) + strlen = strlen + 1 + end + for i = 1,strlen do + self.buf[i] = self.buf[i+strlen] + end + return table.concat(str) +end + +local function ToString(self) + return table.concat(self.buf) +end + +function ss.CreateStream(str) + local ns = {} + ns.buf = {} + if str ~= nil then + for i = 1, #str do + ns[i] = str[i] + end + end + ns.ReadString = ReadString + ns.ReadInt = ReadInt + ns.WriteString = WriteString + ns.WriteInt = WriteInt + ns.ToString = ToString + return ns +end + +return ss |