aboutsummaryrefslogtreecommitdiff
path: root/lua/colorizer/trie.lua
diff options
context:
space:
mode:
Diffstat (limited to 'lua/colorizer/trie.lua')
-rw-r--r--lua/colorizer/trie.lua362
1 files changed, 185 insertions, 177 deletions
diff --git a/lua/colorizer/trie.lua b/lua/colorizer/trie.lua
index 21794ef..21ea543 100644
--- a/lua/colorizer/trie.lua
+++ b/lua/colorizer/trie.lua
@@ -13,7 +13,7 @@
-- You should have received a copy of the GNU General Public License
-- along with this program. If not, see <http://www.gnu.org/licenses/>.
-local ffi = require 'ffi'
+local ffi = require "ffi"
ffi.cdef [[
struct Trie {
@@ -24,219 +24,227 @@ void *malloc(size_t size);
void free(void *ptr);
]]
-local Trie_t = ffi.typeof('struct Trie')
-local Trie_ptr_t = ffi.typeof('$ *', Trie_t)
+local Trie_t = ffi.typeof "struct Trie"
+local Trie_ptr_t = ffi.typeof("$ *", Trie_t)
local Trie_size = ffi.sizeof(Trie_t)
local function trie_create()
- local ptr = ffi.C.malloc(Trie_size)
- ffi.fill(ptr, Trie_size)
- return ffi.cast(Trie_ptr_t, ptr)
+ local ptr = ffi.C.malloc(Trie_size)
+ ffi.fill(ptr, Trie_size)
+ return ffi.cast(Trie_ptr_t, ptr)
end
local function trie_destroy(trie)
- if trie == nil then
- return
- end
- for i = 0, 61 do
- local child = trie.character[i]
- if child ~= nil then
- trie_destroy(child)
- end
- end
- ffi.C.free(trie)
+ if trie == nil then
+ return
+ end
+ for i = 0, 61 do
+ local child = trie.character[i]
+ if child ~= nil then
+ trie_destroy(child)
+ end
+ end
+ ffi.C.free(trie)
end
-local INDEX_LOOKUP_TABLE = ffi.new 'uint8_t[256]'
-local CHAR_LOOKUP_TABLE = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
+local INDEX_LOOKUP_TABLE = ffi.new "uint8_t[256]"
+local CHAR_LOOKUP_TABLE = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
do
- local b = string.byte
- for i = 0, 255 do
- if i >= b'0' and i <= b'9' then
- INDEX_LOOKUP_TABLE[i] = i - b'0'
- elseif i >= b'A' and i <= b'Z' then
- INDEX_LOOKUP_TABLE[i] = i - b'A' + 10
- elseif i >= b'a' and i <= b'z' then
- INDEX_LOOKUP_TABLE[i] = i - b'a' + 10 + 26
- else
- INDEX_LOOKUP_TABLE[i] = 255
- end
- end
+ local b = string.byte
+ for i = 0, 255 do
+ if i >= b "0" and i <= b "9" then
+ INDEX_LOOKUP_TABLE[i] = i - b "0"
+ elseif i >= b "A" and i <= b "Z" then
+ INDEX_LOOKUP_TABLE[i] = i - b "A" + 10
+ elseif i >= b "a" and i <= b "z" then
+ INDEX_LOOKUP_TABLE[i] = i - b "a" + 10 + 26
+ else
+ INDEX_LOOKUP_TABLE[i] = 255
+ end
+ end
end
local function trie_insert(trie, value)
- if trie == nil then return false end
- local node = trie
- for i = 1, #value do
- local index = INDEX_LOOKUP_TABLE[value:byte(i)]
- if index == 255 then
- return false
- end
- if node.character[index] == nil then
- node.character[index] = trie_create()
- end
- node = node.character[index]
- end
- node.is_leaf = true
- return node, trie
+ if trie == nil then
+ return false
+ end
+ local node = trie
+ for i = 1, #value do
+ local index = INDEX_LOOKUP_TABLE[value:byte(i)]
+ if index == 255 then
+ return false
+ end
+ if node.character[index] == nil then
+ node.character[index] = trie_create()
+ end
+ node = node.character[index]
+ end
+ node.is_leaf = true
+ return node, trie
end
local function trie_search(trie, value, start)
- if trie == nil then return false end
- local node = trie
- for i = (start or 1), #value do
- local index = INDEX_LOOKUP_TABLE[value:byte(i)]
- if index == 255 then
- return
- end
- local child = node.character[index]
- if child == nil then
- return false
- end
- node = child
- end
- return node.is_leaf
+ if trie == nil then
+ return false
+ end
+ local node = trie
+ for i = (start or 1), #value do
+ local index = INDEX_LOOKUP_TABLE[value:byte(i)]
+ if index == 255 then
+ return
+ end
+ local child = node.character[index]
+ if child == nil then
+ return false
+ end
+ node = child
+ end
+ return node.is_leaf
end
local function trie_longest_prefix(trie, value, start)
- if trie == nil then return false end
- -- insensitive = insensitive and 0x20 or 0
- start = start or 1
- local node = trie
- local last_i = nil
- for i = start, #value do
- local index = INDEX_LOOKUP_TABLE[value:byte(i)]
--- local index = INDEX_LOOKUP_TABLE[bor(insensitive, value:byte(i))]
- if index == 255 then
- break
- end
- local child = node.character[index]
- if child == nil then
- break
- end
- if child.is_leaf then
- last_i = i
- end
- node = child
- end
- if last_i then
- -- Avoid a copy if the whole string is a match.
- if start == 1 and last_i == #value then
- return value
- else
- return value:sub(start, last_i)
- end
- end
+ if trie == nil then
+ return false
+ end
+ -- insensitive = insensitive and 0x20 or 0
+ start = start or 1
+ local node = trie
+ local last_i = nil
+ for i = start, #value do
+ local index = INDEX_LOOKUP_TABLE[value:byte(i)]
+ -- local index = INDEX_LOOKUP_TABLE[bor(insensitive, value:byte(i))]
+ if index == 255 then
+ break
+ end
+ local child = node.character[index]
+ if child == nil then
+ break
+ end
+ if child.is_leaf then
+ last_i = i
+ end
+ node = child
+ end
+ if last_i then
+ -- Avoid a copy if the whole string is a match.
+ if start == 1 and last_i == #value then
+ return value
+ else
+ return value:sub(start, last_i)
+ end
+ end
end
local function trie_extend(trie, t)
- assert(type(t) == 'table')
- for _, v in ipairs(t) do
- trie_insert(trie, v)
- end
+ assert(type(t) == "table")
+ for _, v in ipairs(t) do
+ trie_insert(trie, v)
+ end
end
--- Printing utilities
local function index_to_char(index)
- if index < 0 or index > 61 then return end
- return CHAR_LOOKUP_TABLE:sub(index+1, index+1)
+ if index < 0 or index > 61 then
+ return
+ end
+ return CHAR_LOOKUP_TABLE:sub(index + 1, index + 1)
end
local function trie_as_table(trie)
- if trie == nil then
- return nil
- end
- local children = {}
- for i = 0, 61 do
- local child = trie.character[i]
- if child ~= nil then
- local child_table = trie_as_table(child)
- child_table.c = index_to_char(i)
- table.insert(children, child_table)
- end
- end
- return {
- is_leaf = trie.is_leaf;
- children = children;
- }
+ if trie == nil then
+ return nil
+ end
+ local children = {}
+ for i = 0, 61 do
+ local child = trie.character[i]
+ if child ~= nil then
+ local child_table = trie_as_table(child)
+ child_table.c = index_to_char(i)
+ table.insert(children, child_table)
+ end
+ end
+ return {
+ is_leaf = trie.is_leaf,
+ children = children,
+ }
end
local function print_trie_table(s)
- local mark
- if not s then
- return {'nil'}
- end
- if s.c then
- if s.is_leaf then
- mark = s.c.."*"
- else
- mark = s.c.."─"
- end
- else
- mark = "├─"
- end
- if #s.children == 0 then
- return {mark}
- end
- local lines = {}
- for _, child in ipairs(s.children) do
- local child_lines = print_trie_table(child, thicc)
- for _, child_line in ipairs(child_lines) do
- table.insert(lines, child_line)
- end
- end
- local child_count = 0
- for i, line in ipairs(lines) do
- local line_parts = {}
- if line:match("^%w") then
- child_count = child_count + 1
- if i == 1 then
- line_parts = {mark}
- elseif i == #lines or child_count == #s.children then
- line_parts = {"└─"}
- else
- line_parts = {"├─"}
- end
- else
- if i == 1 then
- line_parts = {mark}
- elseif #s.children > 1 and child_count ~= #s.children then
- line_parts = {"│ "}
- else
- line_parts = {" "}
- end
- end
- table.insert(line_parts, line)
- lines[i] = table.concat(line_parts)
- end
- return lines
+ local mark
+ if not s then
+ return { "nil" }
+ end
+ if s.c then
+ if s.is_leaf then
+ mark = s.c .. "*"
+ else
+ mark = s.c .. "─"
+ end
+ else
+ mark = "├─"
+ end
+ if #s.children == 0 then
+ return { mark }
+ end
+ local lines = {}
+ for _, child in ipairs(s.children) do
+ local child_lines = print_trie_table(child, thicc)
+ for _, child_line in ipairs(child_lines) do
+ table.insert(lines, child_line)
+ end
+ end
+ local child_count = 0
+ for i, line in ipairs(lines) do
+ local line_parts = {}
+ if line:match "^%w" then
+ child_count = child_count + 1
+ if i == 1 then
+ line_parts = { mark }
+ elseif i == #lines or child_count == #s.children then
+ line_parts = { "└─" }
+ else
+ line_parts = { "├─" }
+ end
+ else
+ if i == 1 then
+ line_parts = { mark }
+ elseif #s.children > 1 and child_count ~= #s.children then
+ line_parts = { "│ " }
+ else
+ line_parts = { " " }
+ end
+ end
+ table.insert(line_parts, line)
+ lines[i] = table.concat(line_parts)
+ end
+ return lines
end
local function trie_to_string(trie)
- if trie == nil then
- return 'nil'
- end
- local as_table = trie_as_table(trie)
- return table.concat(print_trie_table(as_table), '\n')
+ if trie == nil then
+ return "nil"
+ end
+ local as_table = trie_as_table(trie)
+ return table.concat(print_trie_table(as_table), "\n")
end
local Trie_mt = {
- __new = function(_, init)
- local trie = trie_create()
- if type(init) == 'table' then
- trie_extend(trie, init)
- end
- return trie
- end;
- __index = {
- insert = trie_insert;
- search = trie_search;
- longest_prefix = trie_longest_prefix;
- extend = trie_extend;
- };
- __tostring = trie_to_string;
- __gc = trie_destroy;
+ __new = function(_, init)
+ local trie = trie_create()
+ if type(init) == "table" then
+ trie_extend(trie, init)
+ end
+ return trie
+ end,
+ __index = {
+ insert = trie_insert,
+ search = trie_search,
+ longest_prefix = trie_longest_prefix,
+ extend = trie_extend,
+ },
+ __tostring = trie_to_string,
+ __gc = trie_destroy,
}
-return ffi.metatype('struct Trie', Trie_mt)
+return ffi.metatype("struct Trie", Trie_mt)