open Big_int;;
open Printf;;
  
(* polynôme *)
type polynome =
  |Empty
  |Monome of int*int*polynome;;

type degres = Degres of int*int*int;;

let lex_smaller d = match d with
  |Degres(a,b,c) ->      if (a <= b) && (a <= c) then a
                    else if (b <= a) && (b <= c) then b
                    else c;;

let add_degree (Degres(a,b,c)) (Degres(d,e,f)) = Degres(a+d,b+e,c+f);;

let print_degree (Degres(a,b,c)) = printf "aX^%d + bX^%d + cX^%d\n" a b c;;
  
let test = print_degree (Degres(5,9,12));;

let rec print_poly p = match p with
  |Empty         -> printf "\n"
  |Monome(c,d,q) -> if q = Empty then let t = printf "%dX^%d"   c d in print_poly q
                                 else let t = printf "%dX^%d +" c d in print_poly q;;

let monomial c d = Monome(c,d,Empty);;

let poly_zero = Monome(0,0,Empty);;

let rec leading_coefficient p = match p with
  |Empty         -> 0
  |Monome(c,d,q) -> if q = Empty then c
                                 else leading_coefficient q;;

let rec degree p = match p with
  |Empty         -> 0
  |Monome(c,d,q) -> if q = Empty then d
                                 else degree q;;

let rec reductum p = match p with
  |Empty         -> Empty
  |Monome(c,d,q) -> match q with
                    |Empty         -> Empty
                    |Monome(x,y,r) -> if y = degree p then Monome(c,d,Empty)
                                      else Monome(c,d,reductum q);;
let rec correct_rep p = match p with
  |Empty                     -> true
  |Monome(a,b,Empty)         -> true
  |Monome(a,b,Monome(c,d,q)) -> (d < b) && correct_rep (Monome(c,d,q));;

let rec poly_equal p q = match (p,q) with
  |(Empty,Empty)                 -> true
  |(Empty,q)                     -> false
  |(p,Empty)                     -> false
  |(Monome(a,b,r),Monome(c,d,s)) -> (a = c) && (b = d) && poly_equal r s;;

let rec poly_addr p q t = if t = 0 then Empty else
  match (p,q) with
  |(Empty,Empty)                 -> Empty
  |(Empty,q)                     -> q
  |(p,Empty)                     -> p
  |(Monome(a,b,r),Monome(c,d,s)) ->      if b = d then Monome(a+c,b,poly_addr r s (t-1))
                                    else if b > d then Monome(a, b, poly_addr r q (t-1))
                                                  else Monome(c, d, poly_addr p s (t-1));;

let poly_add p q = poly_addr p q 3;;
                                                                

module type Coeffs =
  sig
    type t
    val cnull : t
    val cisnull : t -> bool
    val cplus : t -> t -> t
    val cmoins : t -> t -> t
    val cfois : t -> t -> t
    val cdiviser : t -> t -> t
    val ccarres : t -> t
    val crac : t -> t
    val ccompare : t -> t -> t
  end

module type Deg =
  sig
    type t
    val dnull : t
    val disnull : t -> bool                                     
    val maxdeg : t -> int
    val mindeg : t -> int
    val middeg : t -> int
    val dcompare : t -> t -> int
    val fusion : t -> t -> t
  end

module Entiers : Coeffs =
  struct
    type t = big_int

    let cnull = zero_big_int
                 
    let cisnull x = x = zero_big_int

    let cplus x y = add_big_int x y

    let cmoins x y = sub_big_int x y

    let cfois x y = mult_big_int x y

    let cdiviser x y = div_big_int x y

    let ccarres x = square_big_int x
                         
    let crac x = sqrt_big_int x

    let ccompare x y = compare_big_int x y
  end

module Triplets : Deg =
  struct
    type t = degres;;

    let dnull = Degres(0,0,0);;

    let disnull x = x = null;;

    let maxdeg Degres(a,b,c) = a;;

    let mindeg Degres(a,b,c) = c;;

    let middeg Degres(a,b,c) = b;;

    let dcompare x y = if x = y then 0 else
                        match (x,y) with
                        |null,y -> -1
                        |x,null -> 1
                        |Degres(a,b,c),Degres(d,e,f) ->      if a > d then  1
                                                        else if a < d then -1
                                                        else if b > e then  1
                                                        else if b < e then -1
                                                        else if c > f then  1
                                                        else if c < f then -1
                                                        else if c = f then  0;;

    let rec max l = match l with
      |[]   -> 0
      |h::q -> if h > max q then h else max q;;

    let rec rm l e = match l with
      |[]   -> []
      |h::q -> if h = e then q else h::(rm q e);;
              
    let rec trimax l n Degres(a,b,c) = match l with
      |[] ->      if n = 2 then Degres(a,b,0)
             else if n = 1 then Degres(a,0,c)
             else if n = 0 then Degres(0,a,b)
      |_  -> let m = max l in
             let s = rm l m in
             let t = if n = 2 then Degres(a,b,m)
                else if n = 1 then Degres(a,m,c)
                else if n = 0 then Degres(m,b,c)
                else Degres(a,b,c) in
             trimax s (n+1) t;;
                                  
    let fusion x y = match x,y with
      |null,null                   -> null
      |null,y                      -> x
      |x,null                      -> y
      |Degres(a,b,c),Degres(d,e,f) -> trimax [a,b,c,d,e,f] 0 (0,0,0);;

  end
      
module Z_Zn =
  struct
    type t = int
    let themod = 5
    let plus x y = (x + y) mod themod
    let from_int n = n mod themod
    let rec moins x y = if x - y < 0 then moins (x - y + themod) 0 else x - y
    let rec fois x y = (x * y) mod themod
  end