--[[ 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


INVARIANTS FOR CandyBowl INSTANCES

This version of the CandyBowl ADT module has the same interface as the
hashed version but uses a different internal data representation.
This version uses with an unsorted, list-style table of candyTypes.

The interface invariants, preconditions, and postconditions are the
same as those specified in the hashed version of the module.  The
implementation variant changes to match the concrete data
representation uses.

An ADT Interface Invariant for CandyBowl "bowl" can be stated as

      (ForAll c: validCandyType(c) :: howMany(bowl,c) >= 0)
  and (Sum c,n: n == howMany(bowl,c) :: n) == howMany(bowl)

where validCandyType(c) has an appropriate definition.

An ADT Implementation Invariant for CandyBowl "bowl" using the
list-based representation can be stated as
 
  (ForAll i : 1 <= i <= #bowl :: validCandyType(bowl[i]))  and
  (ForAll c : validCandyType(c) ::
    howMany(bowl,c) == (Sum i : 1 <= i < #bowl and bowl[i] == c :: 1))

where validCandyType(c) == (c ~= nil).

We also need to refine the model as discussed in the section BETTER
APPROACH TO SEMANTICS in the hashed version of CandyBowl.

As currently implemented, all the required functions except "isEmpty"
are dependent upon the implementation.  Extended functions "putcp",
"takecp", "toBowl", and "combine2" are not.

For some function, the problem does not specify whether a function can
modify its input arguments.

--]]


-- 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