--[[ Carrie's Candy Bowl Module: List Version
     CSci 658: Software Language Engineering, Fall 2013
     Exam 1, Problem 4
     H. Conrad Cunningham, Professor
     Computer and Information Science
     University of Mississippi

1234567890123456789012345678901234567890123456789012345678901234567890

2013-11-25: Developed from hashed Candy Bowl module
2013-12-03: Changes to match hashed version semantics.
            Improved comments. Changes from 4:00 p.m. version.
2013-12-08: Improved documentation
2017-02-25: Moved documentation of the semantics to separate 
            Carrie's Candy Bowl Semantics document

--]]


-- Utility function copy(t) returns a new list that is a shallow copy
-- of list "t".

local function copy(t)
  local c = {}
  for i = 1,#t do c[i] = t[i] end
  return c
end


-- Utility function append(a,b) returns a new list consisting of the
-- elements of list "a" followed by those of list "b".

local function append(a,b)
  local c = copy(a)
  for i = 1,#b do c[#c+1] = b[i] end
  return c
end


-- Utility function index(t,v) returns the smallest index at which
-- value "v" occurs in list-style table "t".  If "v" does not occur,
-- then "index" returns 0.

local function index(t,v)
  for i = 1,#t do
    if t[i] == v then return i end
  end
  return 0
end


-- Constructor function CandyBowl(bowl) returns a new empty candy bowl
-- if "bowl" is nil or unspecified; otherwise, it returns a shallow
-- copy of the argument "bowl".  Note: The functionality of returning
-- a copy of an existing bowl is not required by the specification.

local function CandyBowl(bowl)
  if bowl then return copy(bowl) end
  return {}
end


-- Function has(bowl,candyType) returns true if and only if "bowl"
-- contains some pieces of type "candyType" candy.

local function has(bowl, candyType)
  if not candyType then
    error("Invalid candy type in 'has' " .. tostring(candyType))
  end
  return index(bowl,candyType) > 0
end


-- Function put(bowl,candyType,n) adds "n" pieces of "candyType" candy
-- to the "bowl".  "n" defaults to 1 if nil or unspecified.  "put"
-- modifies its argument.  Function "putcp" returns a modified copy of
-- the argument instead.  The specification does not specify whether
-- the function can mutate its table argument.

local function put(bowl, candyType, n)
  if not candyType then
    error("Invalid candy type in 'put' " .. tostring(candyType))
  end
  if not n then n = 1 end
  assert(n > 0,"Attempt to add zero or negative pieces to bowl.")
  for i = 1,n do
    bowl[#bowl+1] = candyType
  end
  return bowl
end

local function putcp(bowl, candyType, n)
  return put(CandyBowl(bowl), candyType, n)
end


-- Function take(bowl,candyType) removes one piece of "candyType"
-- candy from the "bowl". "take" modifies its argument.  Function
-- "takecp" returns a modified copy of the argument instead.  The
-- specification does not specify whether the function can mutate its
-- table argument.

local function take(bowl, candyType)
  if not candyType then
    error("Invalid candy type in 'take' " .. tostring(candyType))
  end
  local i = index(bowl,candyType)
  if i > 0 then
    table.remove(bowl,i)
    return bowl
  else
    error("Bowl does not contain type " .. tostring(candyType))
  end 
end

local function takecp(bowl, candyType)
  return take(CandyBowl(bowl), candyType)
end


-- Function howMany(bowl,candyType) returns the number of pieces of
-- candy that are in the "bowl" overall if " candyType" is nil;
-- otherwise, the function returns the number of pieces of "candyType"
-- candy that are in the bowl.

local function howMany(bowl, candyType)
  if not candyType then return #bowl end
  local k = 0
  for i = 1,#bowl do
    if bowl[i] == candyType then k = k + 1 end
  end
  return k
end


-- Function isEmpty(bowl) returns true if and only if the "bowl" is
-- empty.

local function isEmpty(bowl)
  return howMany(bowl) == 0
end


-- Function inventory(bowl) returns a list-style table of pairs
-- {candyType, count} with the list in ascending order by "candyType".
   
local function inventory(bowl)
  local types = {}
  for i = 1,#bowl do
    types[bowl[i]] = (types[bowl[i]] or 0) + 1
  end
  local res = {}
  for c,n in pairs(types) do
    res[#res+1] = {c,n}
  end
  table.sort(res,function(r,s) return r[1] < s[1] end)
  return res
end


-- Function toBowl(inv) takes an inventory "inv" (as returned by the
-- "inventory" function) and returns the corresponding bowl.  This
-- function is not required by the specification.
   
local function toBowl(inv)
  local bowl = CandyBowl()
  for _,p in ipairs(inv) do
    put(bowl,p[1],p[2])
  end
  return bowl
end


-- Function combine(bowl1,bowl2) returns the bowl resulting from
-- pouring bowl1 and bowl2 together to form a new bowl.

local function combine(bowl1,bowl2)
  return append(bowl1,bowl2)
end


-- Function combine2(bowl1,bowl2) returns the bowl resulting from
-- pouring "bowl1" and "bowl2" together to form a new bowl.  Unlike
-- "combine", "combine2" does so without directly examining the
-- internal data representation.

local function combine2(bowl1, bowl2)

  -- icopy list a into b from indexes i and j, respectively
  local function icopy(a,i,b,j)
    if i > #a then
      return b
    else
      b[j] = a[i]
      return icopy(a,i+1,b,j+1)
    end
  end

  -- merge ascending lists a and b into c from indexes i, j, and k
  local function merge(a,i,b,j,c,k)
    if i > #a then
      return icopy(b,j,c,k)
    elseif j > #b then
      return icopy(a,i,c,k)
    else 
      if a[i][1] < b[j][1] then
        c[k] = a[i]
        return merge(a,i+1,b,j,c,k+1)
      elseif a[i][1] == b[j][1] then
        c[k] = { a[i][1], a[i][2] + b[j][2] }
        return merge(a,i+1,b,j+1,c,k+1)
      else -- a[i][1] > b[j][1]
        c[k] = b[j]
        return merge(a,i,b,j+1,c,k+1)
      end
    end
  end

  local a, b, c = inventory(bowl1), inventory(bowl2), {}
  return toBowl(merge(a,1,b,1,c,1))
end


-- Module export

return { CandyBowl = CandyBowl,
         put       = put,
         putcp     = putcp,     -- extension
         take      = take,
         takecp    = takecp,    -- extension
         combine   = combine,
         combine2  = combine2,  -- extension
         inventory = inventory,
         toBowl    = toBowl,    -- extension
         has       = has,
         howMany   = howMany,
         isEmpty   = isEmpty
       }

-- list utility functions copy, append, and index are not exported