Trie

trie.lua

properties = box.schema.space.create('properties')
properties:create_index('primary', {parts = {1, 'str'}, type = 'HASH', unique = true, if_not_exists = true})
properties:replace({'node_id', 0})

nodes = box.schema.space.create('nodes')
nodes:create_index('primary', {parts = {1, 'num', 2, 'str'}, type = 'TREE', unique = true, if_not_exists = true})

function load_words()
  local words = "/opt/dict/words"
  for line in io.lines(words) do
    insert_string(line:lower())
  end
end

function insert_node(node, char, word)
  box.begin()
  id = box.space.properties:update('node_id', {{'+', 2, 1}})
  t = box.space.nodes:insert({node, char, id[2], word})
  box.commit()
  return t
end

function insert_string(str)
  local node = 0
  local len = #str
  for i = 1, len do
    local c = str:sub(i, i)
    local data = (box.space.nodes:select({node, c})[1] or insert_node(node, c, i == len))
    node = data[3]
  end
end

function find(prefix, max)
  local node = 0
  local data = nil
  local res = {}

  for i = 1, #prefix do
    local c = prefix:sub(i, i)
    data = box.space.nodes:select({node, c})[1]
    if data == nil then break; end
    node = data[3]
  end

  if data == nil then
    return res
  else
    local queue = {{prefix, data[3]}}
    if data[4] then res[#res+1] = prefix; end
    if #res < max then
      local i = 1
      repeat
        local node = queue[i]
        local all_nodes = box.space.nodes:select(node[2])
        for j = 1, #all_nodes do
          local n = all_nodes[j]
          local p = node[1] .. n[2]
          queue[#queue + 1] = {p, n[3]}
          if n[4] then res[#res+1] = p; end
          if #res >= max then break; end
        end
        if #res >= max then break; end
        i = i + 1
      until(queue[i] == nil)
    end
    return res
  end
end

-- tarantool:3301> find("anato", 100)
-- ---
-- - - anatox
--   - anatole
--   - anatoly
--   - anatomy
--   - anatolic
--   - anatomic
--   - anatoxin
--   - anatocism
--   - anatolian
--   - anatomism
--   - anatomist
--   - anatomize
--   - anatopism
--   - anatomical
--   - anatomizer
--   - anatomically
--   - anatomization
--   - anatomicomedical
--   - anatomicosurgical
--   - anatomopathologic
--   - anatomicobiological
--   - anatomicopathologic
--   - anatomopathological
--   - anatomicochirurgical
--   - anatomicophysiologic
--   - anatomicopathological
--   - anatomicophysiological
-- 
-- tarantool:3301> find("app", 10)
-- ---
-- - - appay
--   - appet
--   - apple
--   - apply
--   - appall
--   - appeal
--   - appear
--   - append
--   - appete
--   - appius
-- 
-- tarantool:3301> find("robo", 10)
-- ---
-- - - robot
--   - robomb
--   - robotry
--   - roborant
--   - roborate
--   - roborean
--   - robotian
--   - robotism
--   - robotize
--   - roboreous