with ada.finalization;
package p9 is
   --  an abstract data type for unbounded integers
   type extended_integer is private;
   --  all operations may raise constraint_error for an unitialized object
   --  the arithmetic operations have the usual mathematical meanings
   function "+"  (L, R : extended_integer) return extended_integer;
   function "-"  (R : extended_integer)    return extended_integer;
   function "-"  (L, R : extended_integer) return extended_integer;
   function "*"  (L, R : extended_integer) return extended_integer;
   procedure divide
     (L, R : extended_integer;
      quotient, remainder : out extended_integer);
   --  postcondition: L = quotient * R + remainder
   --  the relational operations have the usual mathematical meanings
   --  raises constraint_error if the quotient is zero
   function "="  (L, R : extended_integer) return boolean;
   function "<"  (L, R : extended_integer) return boolean;
   function "<=" (L, R : extended_integer) return boolean;
   function ">"  (L, R : extended_integer) return boolean;
   function ">=" (L, R : extended_integer) return boolean;
   function extend (value: integer) return extended_integer;
   --  convert integer value into extended_integer representation
   function shorten (value : extended_integer) return integer;
   --  convert extended_integer value into ordinary integer representation
   --  raises overflow exception if value does not fit
   function image (value : extended_integer) return string;
   --  convert extended_integer value into decimal character string
   function value (image : string) return extended_integer;
   --  convert decimal-coded character string
   --  into extended_integer representation
   --  negative numbers begin with '-', and non-negative numbers begin with '0'
   --  raises constraint_error if the string does not represent an integer
   overflow : exception;
   --  is raised by any operation that would result in
   --  an extended_integer whose absolute value is too large to represent
private
   --  In this data representation,
   --  an extended integer is represented as a sign, plus a
   --  linked list of digits.  Each digit is in the range 0 .. B-1.
   --  If X_i is is the value of the ith digit in a list with N digits,
   --  the absolute value of the number represented by the list is
   --  X_1 + X_2 * (B ** 1)) + ... + X_N * (B ** (N-1)).
   K : constant := 4;
   B : constant := 10**K;
   --  B is the radix, a value that is less than integer'last.
   --  It is chosen small enough to allow squaring without overflow.
   --  It is chosen to be a power of 10, so that conversion to and from
   --  decimal character string representation is easy.
   type digit is mod B;
   type int_node;
   type access_node is access int_node;
   type digit_vector is array (natural range <>) of digit;
   type int_node (length : natural := 0) is record 
         is_negative : boolean := false;
         dig : digit_vector (1 .. length);
      end record;
   --  We use a tagged type derived from Ada.Finalization.Controlled,
   --  so that we can inherit automatic finalization and initialization,
   --  and we can define our own assignment operation, which will allow us
   --  to do automatic storage recovery.
   type extended_integer is new ada.finalization.controlled
      with record
         ref : access_node;
      end record;
   --  inherited operations on tagged type extended_integer,
   --  to be overridden in package body
   procedure finalize (object : in out extended_integer);
   procedure adjust (object : in out extended_integer);
end p9;