Module:Test/lib/search

---

local Search = {}

---------------
-- conductor --
---------------
-- sibling_key: optional, deprecate the whole thing
-- query: {key, value}
-- query: {key, }
-- query: {, value}
-- query: key (string or number)
function Search.conductor(query, tbl, sibling_key)
  local f_name = "find"
  assert(query, string.format("bad argument #1 to '%s' (argument missing, search query)", f_name))
  assert(tbl, string.format("bad argument #2 to '%s' (argument missing, table to search through)", f_name))

  Search.state = {
    ["args"] = {},
    ["queried"] = {}
  }
  Search.ancestors = {}

  Search.state.args.query = query
  Search.state.args.table = tbl
  Search.state.args.sibling_key = sibling_key

  local result

  if not sibling_key then
    result = Search.find_first(query, tbl)
  else
    result = Search.find_sibling(query, sibling_key, tbl)
  end

  if result then
    Search.generate_anscestry_of_last_search(result)
    result.ancestors = Search.ancestors
    return result
  end
end

--------------
-- ancestry --
--------------
function Search.generate_anscestry_of_last_search(quad)
  quad = quad or {}

  for _,v in ipairs(Search.state.queried) do
    if v.value == quad.parent.table then
      table.insert(Search.ancestors, quad.parent.key)
      Search.generate_anscestry_of_last_search(v, Search.state.queried, ancestors)
    elseif not quad.parent.key then return nil
    end
  end
end

----------------------
-- search_condition --
----------------------
function Search.search_condition(query, key, value)
  local condition = false

  if type(query) == "string" or type(query) == "number" then
    condition = key == query
  elseif query[1] and query[2] then
    condition = key == query[1] and value == query[2]
  elseif query[1] then
    condition = key == query[1]
  elseif query[2] then
    condition = value == query[2]
  end

  return condition
end

----------------
-- find_first --
----------------
function Search.find_first(query, tbl, tbl_key)
  local subtables = {}

  for k,v in pairs(tbl) do

    local quad = {
      key = k,
      value = v,
      parent = {
        key = tbl_key,
        table = tbl
      }
    }

    -- I do this to be able to generate ancestry for the searh
    table.insert(Search.state.queried, quad)

    if Search.search_condition(query, k, v) then
      return quad
    elseif type(v) == "table" then
      table.insert(subtables, k)
    end

  end

  -- By doing it like this it will first search through all of the children and after that
  -- descend into grandchildren.
  for _,k in ipairs(subtables) do
    local f = Search.find_first(query, tbl[k], k)
    if f then return f
    end
  end
end

------------------
-- find_sibling --
------------------
function Search.find_sibling(query, sibling_key, tbl, tbl_key)
  local subtables = {}

  for k,v in pairs(tbl) do

    local quad = {
      key = k,
      value = v,
      parent = {
        key = tbl_key,
        value = table
      }
    }

    -- I do this to be able to generate ancestry for the searh
    table.insert(Search.state.queried, quad)

    if Search.search_condition(query, k, v) and tbl[sibling_key] then
      local sibling_quad = {
        key = sibling_key,
        value = tbl[sibling_key],
        parent = {
          key = tbl_key,
          table = tbl
        }
      }
      table.insert(Search.state.queried, sibling_quad)
      return sibling_quad
    elseif type(v) == "table" then
      table.insert(subtables, k)
    end

  end

  -- By doing it like this it will first search through all of the children and after that
  -- descend into grandchildren.
  for _,k in ipairs(subtables) do
    local f = Search.find_sibling(query, sibling_key, tbl[k], k)
    if f then return f
    end
  end
end

return Search