generic

  type Coefficient is digits <>;
  type Variable is (<>);

package Polynomials is

  --====================================================================
  -- Author    Christoph Grein
  -- Version   2.0
  -- Date      1 September 2004
  --====================================================================
  -- A polynomial is an expression like
  --
  --    P (x, y, z, ...) := a * x**2 * y**3 + b * x * z + ...
  --
  -- where a, b, ... are (constant) coefficients, x, y, z, ... are
  -- variables; the exponents must be non-negative.
  --
  -- Polynomials are ordered with increasing power
  --    (power 4) X**2 * Y**2 comes before (power 5) X**2 * Y**3
  -- within one power with decreasing power of the single variables
  --    (power 8) X**4 * Y**3 * Z comes before X**4 * Y * Z**3
  --
  -- For the Value function, the syntax of polynomials is as follows:
  --
  --      Polynomial ::= [Adding_Operator] Term {Adding_Operator Term}
  --            Term ::= Factor {* Factor}
  --          Factor ::= Primary [** Natural]
  --         Primary ::= Coefficient | Variable
  -- Adding_Operator ::= + | -
  --
  -- The exception Syntax_Error is raised if the sequence input does not
  -- have the required syntax (or if a coefficient is too large).
  -- Note: No white space is allowed between the syntax items, but
  --       lazy input for coefficients (real numbers) is accepted
  --       (e.g. 1. for 1.0).
  --
  -- Polynomials can be added, subtracted, multiplied, put to the n-th
  -- power.
  -- A variable may be substituted by another polynomial.
  --
  -- A polynomial may be evaluated by either providing a value for
  -- a selected variable (giving a simplified polynomial) or by
  -- providing values for all variables (giving a constant).
  --
  -- Polynomials can be differentiated and integrated.
  -- For multiple differentiation, the degree is given as a parameter.
  -- For multiple integration, the degree is given implicitly by the
  -- number of integration constants (an empty array returns the input
  -- polynomial unchanged; Const(Const'First) is the constant for the
  -- first integration...).
  --====================================================================
  -- History
  -- Author Version   Date    Reason for change
  --  C.G.    0.0  18.06.2004
  --  C.G.    1.0  07.07.2004 Final design
  --  C.G.    1.1  13.07.2004 Value added
  --  C.G.    1.2  20.07.2004 Multiple differentiation and integration
  --  C.G.    2.0  01.09.2004 Renamed from Multinomials to Polynomials
  --====================================================================

  type Polynomial is private;

  Zero: constant Polynomial;  -- 0.0
  One : constant Polynomial;  -- 1.0

  -- Input / Output -------------------------------------------------------

  function Image (Poly: Polynomial) return String;
  function Value (Image: String   ) return Polynomial;

  Syntax_Error: exception;

  -- Constructors ---------------------------------------------------------  X, Y variables

  function "+"  (Right: Variable) return Polynomial;                        -- +X
  function "-"  (Right: Variable) return Polynomial;                        -- -X

  function "+"  (Left, Right: Variable) return Polynomial;                  -- X + Y
  function "-"  (Left, Right: Variable) return Polynomial;                  -- X - Y
  function "*"  (Left, Right: Variable) return Polynomial;                  -- X * Y

  function "**" (Left: Variable; Right: Natural) return Polynomial;         -- X**2

  function "+"  (Left: Variable   ; Right: Coefficient) return Polynomial;  -- X + 1.0
  function "+"  (Left: Coefficient; Right: Variable   ) return Polynomial;  -- 1.0 + X
  function "-"  (Left: Variable   ; Right: Coefficient) return Polynomial;  -- X - 1.0
  function "-"  (Left: Coefficient; Right: Variable   ) return Polynomial;  -- 1.0 - X

  function "+"  (Left: Polynomial ; Right: Coefficient) return Polynomial;  -- X**2 + 1.0
  function "+"  (Left: Coefficient; Right: Polynomial ) return Polynomial;  -- 1.0 + X**2
  function "-"  (Left: Polynomial ; Right: Coefficient) return Polynomial;  -- X**2 - 1.0
  function "-"  (Left: Coefficient; Right: Polynomial ) return Polynomial;  -- 1.0 - X**2

  function "*"  (Left: Coefficient; Right: Variable   ) return Polynomial;  -- 2.0 * X
  function "*"  (Left: Coefficient; Right: Polynomial ) return Polynomial;  -- 2.0 * X**2

  function "+"  (Left: Polynomial ; Right: Variable   ) return Polynomial;  -- X**2 + Y
  function "+"  (Left: Variable   ; Right: Polynomial ) return Polynomial;  -- X + Y**2
  function "-"  (Left: Polynomial ; Right: Variable   ) return Polynomial;  -- X**2 - Y
  function "-"  (Left: Variable   ; Right: Polynomial ) return Polynomial;  -- X - Y**2

  function "*"  (Left: Polynomial ; Right: Variable   ) return Polynomial;  -- X**2 * Y
  function "*"  (Left: Variable   ; Right: Polynomial ) return Polynomial;  -- X * Y**2

  function "-"  (Right: Polynomial) return Polynomial;                      -- -2.0 * X**2

  function "+"  (Left, Right: Polynomial) return Polynomial;                -- X**2 + Y**3
  function "-"  (Left, Right: Polynomial) return Polynomial;                -- X**2 - Y**3
  function "*"  (Left, Right: Polynomial) return Polynomial;                -- X**2 * Y**3

  function "**" (Left: Polynomial; Right: Natural) return Polynomial;       -- (X + Y)**3

  -- Evaluation -----------------------------------------------------------

  -- 1. Replace a variable by the given value:  P (x, y => 4.0, z, ...)

  function Evaluate (Poly : Polynomial;
                     Var  : Variable;
                     Value: Coefficient) return Polynomial;

  -- 2. Replace all variables by values:  P (x => 1.0, y => 4.0, z => -5.0, ...):

  type Values is array (Variable) of Coefficient;

  function Evaluate (Poly : Polynomial;
                     Value: Values    ) return Coefficient;

  -- Substitution ---------------------------------------------------------

  -- Substitute a variable by another Polynomial:

  function Substitute (Poly: Polynomial;
                       Var : Variable;
                       By  : Polynomial) return Polynomial;

  -- Partial derivation and integration -----------------------------------

  function Derivative (Poly : Polynomial;
                       Var  : Variable   ) return Polynomial;
  function Integral   (Poly : Polynomial;
                       Var  : Variable;
                       Const: Coefficient) return Polynomial;

  type Coefficients is array (Positive range <>) of Coefficient;

  function Derivative (Poly  : Polynomial;
                       Var   : Variable;
                       Degree: Natural     ) return Polynomial;
  function Integral   (Poly  : Polynomial;
                       Var   : Variable;
                       Const : Coefficients) return Polynomial;

private

  ... (not shown)

end Polynomials;