--  FILE:    denominations.ads
--
--  PROJECT: Programmieruebungen, Uebungsblatt 1
--  VERSION: $Revision: 41 $
--  DATE:    $Date: 2006-10-27 13:38:01 +0200 (Fri, 27 Oct 2006) $
--  AUTHOR:  $Author: keulsn $
--
-------------------------------------------------------------------------------
--
--  PACKAGE Denominations
--
--  Enthaelt Datentypen und Unterprogramme mit denen Stueckelungen von
--  Geldbetraegen dargestellt und Muenzverteilungen berechnet werden
--  koennen.
--


package Denominations is


   subtype Money_Amount is Integer range 0 .. 10_000_000;
   subtype Coin_Value is Money_Amount range 1 .. 1_000;

   --  TYPE Denomination
   --
   --  Werte dieses Typs repraesentieren die verfuegbaren
   --  Muenzen. Jede Muenze besitzt einen eindeutigen Index. Ein
   --  'Denomination'-Wert ordnet einem solchen Index den Wert der
   --  entsprechenden Muenze zu.
   type Denomination is array (Positive range <>) of Coin_Value;

   --  TYPE Denomination_Usage
   --
   --  Werte dieses Typs werden im Zusammenhang mit einer bestimmten
   --  'Denomination' verwendet. Durch 'Denomination_Usage' wird eine
   --  Abbildung von Index einer Muenze zur Anzahl der verwendeten
   --  Muenzen (zum Erreichen eines bestimmten Geldbetrags)
   --  hergestellt.
   type Denomination_Usage is array (Positive range <>) of Natural;


   --  FUNCTION Split_Greedy
   --
   --  Benutzt einen "greedy"-Algorithmus um die Anzahl und Art der
   --  Muenzen einer bestimmten Stueckelung zu berechnen, um einen
   --  bestimmten Betrag darzustellen. Falls das mit diesem
   --  Algorithmus nicht gelingt, so wird ein leeres Array zurueckgegeben.
   --
   --  PARAMETERS:
   --  + Amount: Geldbetrag, der dargestellt werden soll
   --  + Coins: Zu verwendende Stueckelung, muss aufsteigend sortiert sein.
   --  RETURNS: Entweder eine Liste von Muenzverwendungen, die genau
   --    den Betrag 'Amount' darstellt, oder falls nicht moeglich, ein
   --    leeres Array.
   --  PRE: for all I: Coins'First < I <= Coins'Last ==>
   --          Coins (I - 1) < Coins (I)
   function Split_Greedy
     (Amount : in Money_Amount;
      Coins  : in Denomination)
     return Denomination_Usage;


   --  FUNCTION Split_Backtracking
   --
   --  Berechnet die Anzahl und Art der benoetigten Muenzen, um einen
   --  bestimmten Betrag darzustellen. Die Anzahl Muenzen ist
   --  minimal. Falls der geforderte Betrag mit der Stueckelung nicht
   --  darstellbar ist, so wird ein leeres Array zurueckgegeben.
   --
   --  PARAMETERS:
   --  + Amount: Geldbetrag, der dargestellt werden soll
   --  + Coins: Zu verwendende Stueckelung, muss aufsteigend sortiert sein.
   --  RETURNS: Entweder eine Liste von Muenzverwendungen, die genau
   --    den Betrag 'Amount' darstellt, oder falls nicht moeglich, ein
   --    leeres Array.
   --  PRE: for all I: Coins'First < I <= Coins'Last ==>
   --          Coins (I - 1) < Coins (I)
   function Split_Backtracking
     (Amount : in Money_Amount;
      Coins  : in Denomination)
     return Denomination_Usage;


   --  PROCEDURE Put_Usage
   --
   --  Gibt 'Usage' nach 'Standard_Output' aus:
   --  * Falls keine Muenze verwendet wird, gibt "Nicht darstellbar." aus
   --  * Andernfalls wird ein oder mehrere Paare "<m>x<n>" ausgegeben,
   --  getrennt durch ein einfaches Leerzeichen. <m> und <n> sind
   --  positive natuerliche Zahlen. <m> steht fuer die Anzahl Muenzen
   --  mit einem Index 'I' wobei gilt 'Coins (I) = <n>'. Paare mit
   --  '<m> = 0' werden nicht ausgegeben. Ebenso werden keine
   --  Zeilenumbrueche ausgegeben.
   --
   --  PARAMETERS:
   --  + Usage: Abbildung von Index einer Muenze auf Anzahl der
   --  verwendeten Muenzen
   --  + Coins: Abbildung von Index einer Muenze auf den Wert dieser
   --  Muenze
   procedure Put_Usage
     (Usage : in Denomination_Usage;
      Coins : in Denomination);


end Denominations;