-- prefixes.lua: handle expansions, abbrev tables and tables of prefixes.
-- This file:
--   http://angg.twu.net/dednat5/prefixes.lua.html
--   http://angg.twu.net/dednat5/prefixes.lua
--                    (find-dn5 "prefixes.lua")
-- Author: Eduardo Ochs <eduardoochs@gmail.com>
-- Version: 2011apr10
-- License: GPL3
--

-- «.unabbrev»	(to "unabbrev")

-- (find-dn4 "dednat5.lua" "prefixes-and-ptables")
-- (find-dn4 "dednat5.lua" "heads")
-- (find-dn4 "dednat5.lua" "abbrevs")

-- We have two standard "prefix tables" in dednat5: abbrevs and heads.
-- The way to search for a "longest prefix" is the same in both...
-- Here is an example, to explain both the data structure and the
-- basic algorithm. If we only have two abbreviations, "a"->"<a>" and
-- "abc"->"<abc>", then the table "abbrevs" will be like this:
--   abbrevs = { ["a"]="<a>",
--               ["ab"]=0,
--               ["abc"]="<abc>" }
-- and then:
--   unabbrev("ababc")
-- returns:
--   "<a>b<abc>"
-- To calculate the "unabbreviated form" of the string "ababc" we
-- start at the left, and try to find the longest substring of
-- "ababc", starting at 1, which has an expansion... "a" has an
-- expansion, and "ab" has not; but the table abbrevs has an entry
-- ["ab"]=0, that means "keep trying" - because even though "ab" does
-- not have an expansion, some strings starting with "ab" may have.

abbrevs = {}
longestprefix = function (str, j, pt)
    j  = j  or 1          -- starting position
    pt = pt or abbrevs    -- prefix table
    local longest = nil   -- longest prefix having an expansion
    for k=j,#str do
      local candidate = str:sub(j, k)
      local e = pt[candidate]
      if e == nil then break end   -- if e==nil we can stop
      if e ~= 0 then               -- if e==0 we keep trying
        longest = candidate        -- if e~=nil and e~=0 we record the match
      end
    end
    return longest, pt[longest]    -- return the best match and its "expansion"
  end
findfirstexpansion = function (str, i, pt)
    for j=i,#str do
      local longest, expansion = longestprefix(str, j, pt)
      if longest then return j, longest, expansion end
    end
  end
-- «unabbrev»  (to ".unabbrev")
unabbrev = function (str, i, pt)
    i = i or 1
    local j, longest, expansion = findfirstexpansion(str, i, pt)
    if j then
      return str:sub(i, j-1) ..               -- the unexpandable part, then
             expansion ..                     -- the expansion, then...
             unabbrev(str, j+#longest, pt)    -- recurse!
    end
    return str:sub(i)                         -- or all the rest of the string.
  end


-- (find-dn4 "dednat4.lua" "abbrevs")
addabbrev = function (abbrev, expansion, pt)
    pt = pt or abbrevs
    for i=1,#abbrev-1 do
      local prefix = abbrev:sub(1, i)
      pt[prefix] = pt[prefix] or 0
    end
    pt[abbrev] = expansion
  end
addabbrevs = function (...)
    local arg = {...}
    for i=1,#arg,2 do
      addabbrev(arg[i], arg[i+1])
    end
  end
delabbrev = function (abbrev, pt)
    (pt or abbrevs)[abbrev] = 0    -- yep!
  end




-- dump-to: tests
--[==[
* (eepitch-lua51)
* (eepitch-kill)
* (eepitch-lua51)
dofile "common.lua"
dofile "prefixes.lua"
abbrevs = {}
addabbrevs("a", "<a>", "abc", "<abc>")
PP(abbrevs)
print(unabbrev("ababc"))

--]==]

-- Local Variables:
-- coding:             raw-text-unix
-- ee-anchor-format:   "«%s»"
-- End: