database( { 
	basic_ingredient( string, real, string ), 
	ingredient( string, [ quant( string, real ) ] ),
	on_hand( string, real )
	} ).

export recipe( $Item, IngrList, Cost ).

%
% Gives the basic ingredients and quantities which must be purchased
% (i.e. not on hand) for Recipe. Also returns the total cost of all 
% needed ingredients.
%
grocery_list( Recipe, NeededIngredients, Cost ) <-
	recipe( Recipe, SubIngredients, _ ),
	check_on_hand( SubIngredients, NeededIngredients, Cost ).

%
% Determines the quantity of ingredients needed which are not on hand.
%
check_on_hand( [], [], 0 ).
check_on_hand( [ quant( Ingred, Qty ) | Rest ], [ Needed | Rest0 ], Cost ) <-
	on_hand( Ingred, Qty1 ),
	Qty1 < Qty,
	Qty0 = Qty - Qty1,
	check_on_hand( Rest, Rest0, Cost1 ),
	basic_ingredient( Ingred, UnitCost, Unit ),
	Needed = need( Ingred, Qty0, Unit),
	Q = Qty0 * UnitCost,
	Cost = Cost1 + Q.
check_on_hand( [ quant( Ingred, Qty ) | Rest ], Rest0, Cost ) <-
	on_hand( Ingred, Qty1 ),
	check_on_hand( Rest, Rest0, Cost ),
	Qty1 >= Qty.
check_on_hand( [ quant( Ingred, Qty ) | Rest ], [ Needed | Rest0 ], Cost ) <-
	~on_hand( Ingred, _ ),
	check_on_hand( Rest, Rest0, Cost0 ),
	basic_ingredient( Ingred, UnitCost, Unit ),
	Needed = need( Ingred, Qty, Unit ),
	Q = Qty * UnitCost,
	Cost = Q + Cost0.
%	Cost = (Qty*UnitCost) + Cost0.

%
% Finds the list of all basic ingredients and the required quantities for a
% given recipe. The cost of all basic ingredients needed is also returned.
%
recipe( Ingredient, BasicIngredients, Cost ) <-
	ingredient( Ingredient, SubIngredients ),
	sub_ingredients( SubIngredients, BasicIngredients, Cost ).
recipe( Ingredient, [ quant( Ingredient, 1 ) ], Cost ) <-
	basic_ingredient( Ingredient, Cost, _ ).

%
% Finds the list of all basic ingredients and the required quantities for
% a list of ingredients.
%
sub_ingredients( [ quant( Ingredient, Qty ) | Rest ], ReqIngr, Cost ) <-
	recipe( Ingredient, ReqIngr1, Cost1 ),
	sub_ingredients( Rest, ReqIngr2, Cost2 ),
	Q = Qty * Cost1,
	Cost = Q + Cost2,
%	Cost = (Qty*Cost1) + Cost2,
	merge( Qty, ReqIngr1, ReqIngr2, ReqIngr ).
sub_ingredients( [], [], 0 ).

%
% Returns the result of combining Qty units of List1 with one unit of List2.
%
merge( Qty, List1, List2, List ) <-
	List1 = [ quant( Ingredient, Qty1 ) | Rest1 ],
	List2 = [ quant( Ingredient, Qty2 ) | Rest2 ],
	merge( Qty, Rest1, Rest2, Rest ),
	Q1 = Qty * Qty1,
	NewQuantity = Q1 + Qty2,
	List = [ quant( Ingredient, NewQuantity ) | Rest ].
%	List = [ quant( Ingredient, (Qty*Qty1)+Qty2 ) | Rest ].
merge( Qty, List1, List2, List ) <-
	List1 = [ quant( Ingredient1, Qty1 ) | Rest1 ],
	List2 = [ quant( Ingredient2, _ ) | _ ],
	Ingredient1 < Ingredient2,
	merge( Qty, Rest1, List2, Rest ),
	Q = Qty * Qty1,
	List = [ quant( Ingredient1, Q ) | Rest ].
merge( Qty, List1, List2, List ) <-
	List1 = [ quant( Ingredient1, _ ) | _ ],
	List2 = [ quant( Ingredient2, Qty2 ) | Rest2 ],
	Ingredient1 > Ingredient2,
	merge( Qty, List1, Rest2, Rest ),
	List = [ quant( Ingredient2, Qty2 ) | Rest ].
merge( Qty, List1, [], List ) <-
	List1 = [ quant( Ingredient, Qty1 ) | Rest1 ],
	merge( Qty, Rest1, [], Rest ),
	Q = Qty * Qty1,
	List = [ quant( Ingredient, Q ) | Rest1 ].
merge( _, [], List2, List2 ).