--[[ Carrie's Candy Bowl Module: Hashed 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-17: Experimental version before exam
2013-11-25: Modified, documented, and separated into module & driver
2013-12-03: Added ADT interface and implementation invariants, 
            preconditions, and postconditions.
            Corrections from what was distributed in class that day.
2013-12-08: Improved documentation
2017-02-25: Moved documentation of the semantics to separate 
            Carrie's Candy Bowl Semantics document

PROBLEM 4 DESCRIPTION FROM EXAM 1

Carrie's Candy Bowl. As you may have noticed, Carrie, the Department's
Administrative Secretary, has a candy bowl on her desk.  Often this
bowl gets filled with candy, which is quickly consumed by students and
professors.  Your task in this exercise is to represent that candy
bowl by a Lua module.

Design and implement Carrie's Candy Bowl as either a module or a
class.  Your module/class likely will need functions/methods similar
to the following:

CandyBowl() to create a new empty candy bowl

put(bowl,candyType) to add one piece of candy of type candyType to the
  bowl

take(bowl,candyType) to remove one piece of candy of type candyType
  from the bowl

has(bowl,candyType) to determine whether or not the bowl contains any
  candy of type candyType

howMany(bowl) to determine how many pieces of candy are in the bowl
  overall and howMany(bowl,candyType) to determine how many pieces of
  candy of type candyType are in the bowl

isEmpty(bowl) to determine whether or not the bowl is empty

inventory(bowl) to return a list-style table of pairs {candyType,
  count}.  The list should be in ascending order by candyType.  For
  example, if candyType is denoted by a string and there are two
  Snickers and one Hershey Kiss in the bowl, then the list returned
  would be something like { {'Hershey Kiss', 1}, {'Snickers', 2} }

combine(bowl1,bowl2) returns the bowl resulting from pouring bowl1 and
  bowl2 together to form a "larger" bowl

Note: The Lua functions in this module implement the above
functionality, plus some additional capability.

DESCRIPTION OF SEMANTICS

See the Carrie's Candy Bowl Semantics document.

--]]


-- Index in bowl table to hold count of elements
local SIZE = -1


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

local function CandyBowl(bowl)
  local newbowl = {}
  if not bowl then
    newbowl[SIZE] = 0
  else -- do a shallow copy of argument
    for k,v in pairs(bowl) do
      newbowl[k] = v
    end
  end
  return newbowl
end


-- Function has(bowl,candyType) returns true if and only if "bowl"
-- contains one or more pieces of type "candyType" candy.  The
-- argument "bowl" is not modified.

local function has(bowl, candyType)
  if not candyType or candyType == SIZE then
    error("Invalid candy type in 'has' " .. tostring(candyType))
  end
  local c = bowl[candyType]
  return c ~= nil and c > 0  -- c > 0 not needed
end


-- Function put(bowl,candyType,n) adds "n" pieces of "candyType" candy
-- to the argument "bowl".  "n" defaults to 1 if nil or unspecified.
-- "put" modifies its argument "bowl", but function "putcp" returns a
-- modified shallow copy of the argument instead.  The description
-- does not specify whether the function can mutate its table
-- argument; these two functions implement both possibilities.
          
local function put(bowl, candyType, n)
  if not candyType or candyType == SIZE 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.")
  if has(bowl,candyType) then
    bowl[candyType] = bowl[candyType] + n
  else
    bowl[candyType] = n
  end
  bowl[SIZE] = bowl[SIZE] + n
  return bowl
end

-- "putcp" is like "put" except it returns a modified "shallow"
-- copy of the input bowl.

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 argument "bowl". "take" modifies its argument
-- "bowl".  Function "takecp" returns a modified copy of the argument
-- "bowl" instead.  The specification does not specify whether the
-- function can mutate its table argument; these two functions
-- implement both possibilities.

local function take(bowl, candyType) 
  if not candyType or candyType == SIZE then
    error("Invalid candy type in 'take' " .. tostring(candyType))
  end
  if has(bowl,candyType) then 
    bowl[candyType] = bowl[candyType] - 1
    if bowl[candyType] == 0 then bowl[candyType] = nil end 
    bowl[SIZE] = bowl[SIZE] - 1
    return bowl 
  else 
    error("Bowl does not contain type " .. tostring(candyType))
  end 
end


-- "takecp" is like "take" except it returns a modified "shallow"
-- copy of the input bowl.

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 count of the pieces of
-- "candyType" candy that are in the bowl.

local function howMany(bowl, candyType)
  candyType = candyType or SIZE
  return bowl[candyType] or 0
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 c,n in pairs(bowl) do
    if c ~= SIZE then
      types[#types+1] = {c,n}
    end
  end
  table.sort(types,function(r,s) return r[1] < s[1] end)
  return types
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)
  local bowl3 = CandyBowl(bowl1)
  for c,n in pairs(bowl2) do
    if c ~= SIZE and n > 0 then put(bowl3,c,n) end
  end
  return bowl3
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
       }