<commit_before>(**************************************************************************)
(*                                                                        *)
(*  This file is part of Frama-C.                                         *)
(*                                                                        *)
(*  Copyright (C) 2007-2016                                               *)
(*    CEA (Commissariat à l'énergie atomique et aux énergies              *)
(*         alternatives)                                                  *)
(*                                                                        *)
(*  you can redistribute it and/or modify it under the terms of the GNU   *)
(*  Lesser General Public License as published by the Free Software       *)
(*  Foundation, version 2.1.                                              *)
(*                                                                        *)
(*  It is distributed in the hope that it will be useful,                 *)
(*  but WITHOUT ANY WARRANTY; without even the implied warranty of        *)
(*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *)
(*  GNU Lesser General Public License for more details.                   *)
(*                                                                        *)
(*  See the GNU Lesser General Public License version 2.1                 *)
(*  for more details (enclosed in the file LICENCE).                      *)
(*                                                                        *)
(**************************************************************************)

open Pilat_math

(* The functor that given a ring structure returns a polynomial structure.
   One must be careful to make the type of coefficients consistent with the
   type of the elements of the ring structure received as parameter *)

module Vmod_id = State_builder.SharedCounter(struct let name = "pilat_vid_counter" end)
module Xmod_id = State_builder.SharedCounter(struct let name = "pilat_xmod_counter" end)
module Tab_index = State_builder.SharedCounter(struct let name = "pilat_to_str_counter" end)
let next_index () = Tab_index.next () - 1

module Make (A : Ring) (V : Pilat_math.Variable) : 
  Polynomial with type c = A.t
	     and type v = V.t
	     and type Var.Set.t = V.Set.t =
struct
  
    (* 1. Type declaration *)
  type c = A.t
    
  type v = V.t
    
  module R = A
  module Var = V
  module Monom: Datatype.S_with_collections with type t = (int V.Map.t) = struct 
  include (
    Datatype.Make_with_collections(
      struct
	include Datatype.Undefined
	type t = (int V.Map.t)
	let name = "Monom_"  ^ V.name  ^ "_" ^ (string_of_int (Vmod_id.next ()))
	let equal = V.Map.equal (fun (a:int) (b:int) -> a = b)   
	let hash = Hashtbl.hash (* For now, do not hash monomials *)
	let compare = V.Map.compare Pervasives.compare
	let varname (x:t) = 
	  V.Map.fold
	    (fun var pow acc -> (V.varname var) ^ (string_of_int pow) ^ acc)
	    x
	    ""
	let reprs = [V.Map.empty]
	  
	let copy = Datatype.identity
	let rehash = Datatype.identity
	let mem_project = Datatype.never_any_project
      end)
  )
  let pretty fmt (m:t) = 
    V.Map.iter
      (fun var pow ->  
	match pow with
	| 1 -> Format.fprintf fmt "%a" V.pretty var
	| _ -> 
	  Format.fprintf fmt "(%a^%i)" V.pretty var pow)
      m
  end
    
      
  type m = (int V.Map.t) (* x2*y -> map from x to 2 and y to 1 *)
   
  (* for simplicity *)
  module P = Monom.Map
  type t = c P.t 
    

   

  let (zero:t) = P.empty
    
  let empty_monom = V.Map.empty

  let equal (p1:t) (p2:t) : bool = P.equal A.equal p1 p2

    
      
    (* monomial creation *)
  let mono_poly (a:A.t) (m:Monom.t) : t =
    P.singleton m a

  let mono_minimal (l:(v * int) list) : Monom.t = 
    List.fold_left
      (fun acc (v,i) -> 
	if i = 0 then acc else
	V.Map.add v i acc
      )
      V.Map.empty l

  let monomial (a:A.t) (l:(v * int) list) : t = 
    mono_poly a (mono_minimal l)
       
  let var_to_monom (v:v) = mono_minimal [v,1]

  let to_var (m:Monom.t) : v list = 
    let rec add_i_var v i acc = 
      match i with 
	0 -> acc
      | _ -> add_i_var v (i-1) (v :: acc)
    in
    V.Map.fold
      add_i_var
      m
      []

  let to_var_set (m:Monom.t) : v list = 
    V.Map.fold
      (fun v p acc -> if p <> 0 then v :: acc else acc)
      m
      []

  let deg_of_var (m:Monom.t) (v:v) : int = 
    try V.Map.find v m with Not_found -> 0 

  let const (c:A.t) = mono_poly c V.Map.empty

    (* a pacticular case *)
    let (one:t) = const A.one


    let simple_op (op: A.t -> A.t -> A.t) : t -> t -> t = 
      P.merge
	(fun _ m1 m2 -> 
	  match m1,m2 with
	    None, None -> None
	  | None, Some m -> Some (op A.zero m)
	  | Some m, None -> Some m
	  | Some c1, Some c2 -> Some (op c1 c2)
	) 
 

    let add : t -> t -> t =
      simple_op A.add
      
    let sub : t -> t -> t = simple_op A.sub

    let mono_mul : m -> m -> m = 
      V.Map.merge
	(fun _ v1 v2 -> 
	  match v1,v2 with
	    None,None -> None
	  | Some k, None 
	  | None, Some k -> Some k
	  | Some k1, Some k2 -> Some (k1+k2)
	)
        
    let coef (p:t) (m:Monom.t) : c = 
      try P.find m p with Not_found -> A.zero

    let fois (k:A.t) (m:m) (p:t) : t =
      
      P.fold
	(fun monom coeff acc -> 
	  let new_monom = mono_mul monom m
	  in
	  add acc (mono_poly (A.mul coeff k) new_monom)	  
	)
	p
	zero

    let scal_mul (c:c) = 
      P.map (A.mul c)
      

    let mul (p1:t) (p2:t) : t =     
      P.fold
	(fun monom coeff acc -> 
	  let new_monom = (fois coeff monom p2)
	  in
	  add acc new_monom
	)
	p1
	zero
    
    let div _ _ = assert false<commit_msg>allowing polynomial division for constants<commit_after>(**************************************************************************)
(*                                                                        *)
(*  This file is part of Frama-C.                                         *)
(*                                                                        *)
(*  Copyright (C) 2007-2016                                               *)
(*    CEA (Commissariat à l'énergie atomique et aux énergies              *)
(*         alternatives)                                                  *)
(*                                                                        *)
(*  you can redistribute it and/or modify it under the terms of the GNU   *)
(*  Lesser General Public License as published by the Free Software       *)
(*  Foundation, version 2.1.                                              *)
(*                                                                        *)
(*  It is distributed in the hope that it will be useful,                 *)
(*  but WITHOUT ANY WARRANTY; without even the implied warranty of        *)
(*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *)
(*  GNU Lesser General Public License for more details.                   *)
(*                                                                        *)
(*  See the GNU Lesser General Public License version 2.1                 *)
(*  for more details (enclosed in the file LICENCE).                      *)
(*                                                                        *)
(**************************************************************************)

open Pilat_math

(* The functor that given a ring structure returns a polynomial structure.
   One must be careful to make the type of coefficients consistent with the
   type of the elements of the ring structure received as parameter *)

module Vmod_id = State_builder.SharedCounter(struct let name = "pilat_vid_counter" end)
module Xmod_id = State_builder.SharedCounter(struct let name = "pilat_xmod_counter" end)
module Tab_index = State_builder.SharedCounter(struct let name = "pilat_to_str_counter" end)
let next_index () = Tab_index.next () - 1

module Make (A : Ring) (V : Pilat_math.Variable) : 
  Polynomial with type c = A.t
	     and type v = V.t
	     and type Var.Set.t = V.Set.t =
struct
  
    (* 1. Type declaration *)
  type c = A.t
    
  type v = V.t
    
  module R = A
  module Var = V
  module Monom: Datatype.S_with_collections with type t = (int V.Map.t) = struct 
  include (
    Datatype.Make_with_collections(
      struct
	include Datatype.Undefined
	type t = (int V.Map.t)
	let name = "Monom_"  ^ V.name  ^ "_" ^ (string_of_int (Vmod_id.next ()))
	let equal = V.Map.equal (fun (a:int) (b:int) -> a = b)   
	let hash = Hashtbl.hash (* For now, do not hash monomials *)
	let compare = V.Map.compare Pervasives.compare
	let varname (x:t) = 
	  V.Map.fold
	    (fun var pow acc -> (V.varname var) ^ (string_of_int pow) ^ acc)
	    x
	    ""
	let reprs = [V.Map.empty]
	  
	let copy = Datatype.identity
	let rehash = Datatype.identity
	let mem_project = Datatype.never_any_project
      end)
  )
  let pretty fmt (m:t) = 
    V.Map.iter
      (fun var pow ->  
	match pow with
	| 1 -> Format.fprintf fmt "%a" V.pretty var
	| _ -> 
	  Format.fprintf fmt "(%a^%i)" V.pretty var pow)
      m
  end
    
      
  type m = (int V.Map.t) (* x2*y -> map from x to 2 and y to 1 *)
   
  (* for simplicity *)
  module P = Monom.Map
  type t = c P.t 
    

   

  let (zero:t) = P.empty
    
  let empty_monom = V.Map.empty

  let equal (p1:t) (p2:t) : bool = P.equal A.equal p1 p2

    
      
    (* monomial creation *)
  let mono_poly (a:A.t) (m:Monom.t) : t =
    P.singleton m a

  let mono_minimal (l:(v * int) list) : Monom.t = 
    List.fold_left
      (fun acc (v,i) -> 
	if i = 0 then acc else
	V.Map.add v i acc
      )
      V.Map.empty l

  let monomial (a:A.t) (l:(v * int) list) : t = 
    mono_poly a (mono_minimal l)
       
  let var_to_monom (v:v) = mono_minimal [v,1]

  let to_var (m:Monom.t) : v list = 
    let rec add_i_var v i acc = 
      match i with 
	0 -> acc
      | _ -> add_i_var v (i-1) (v :: acc)
    in
    V.Map.fold
      add_i_var
      m
      []

  let to_var_set (m:Monom.t) : v list = 
    V.Map.fold
      (fun v p acc -> if p <> 0 then v :: acc else acc)
      m
      []

  let deg_of_var (m:Monom.t) (v:v) : int = 
    try V.Map.find v m with Not_found -> 0 

  let const (c:A.t) = mono_poly c V.Map.empty

    (* a pacticular case *)
    let (one:t) = const A.one


    let simple_op (op: A.t -> A.t -> A.t) : t -> t -> t = 
      P.merge
	(fun _ m1 m2 -> 
	  match m1,m2 with
	    None, None -> None
	  | None, Some m -> Some (op A.zero m)
	  | Some m, None -> Some m
	  | Some c1, Some c2 -> Some (op c1 c2)
	) 
 

    let add : t -> t -> t =
      simple_op A.add
      
    let sub : t -> t -> t = simple_op A.sub

    let mono_mul : m -> m -> m = 
      V.Map.merge
	(fun _ v1 v2 -> 
	  match v1,v2 with
	    None,None -> None
	  | Some k, None 
	  | None, Some k -> Some k
	  | Some k1, Some k2 -> Some (k1+k2)
	)
        
    let coef (p:t) (m:Monom.t) : c = 
      try P.find m p with Not_found -> A.zero

    let fois (k:A.t) (m:m) (p:t) : t =
      
      P.fold
	(fun monom coeff acc -> 
	  let new_monom = mono_mul monom m
	  in
	  add acc (mono_poly (A.mul coeff k) new_monom)	  
	)
	p
	zero

    let scal_mul (c:c) = 
      P.map (A.mul c)
      

    let mul (p1:t) (p2:t) : t =     
      P.fold
	(fun monom coeff acc -> 
	  let new_monom = (fois coeff monom p2)
	  in
	  add acc new_monom
	)
	p1
	zero
    
    let div p1 p2 = 
      assert ((Monom.Map.cardinal p1 = 1) && (Monom.Map.cardinal p2 = 1));
      let c1 = coef p1 empty_monom and c2 = coef p2 empty_monom in
      let c1oc2 = R.div c1 c2 in const c1oc2
{'fraction_non_alphanumeric': 0.13087597571552473, 'fraction_numerical': 0.00971379011274935, 'mean_word_length': 1.5471614755908991, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 71, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 50, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2517772', 'n_tokens_mistral': 3959, 'n_tokens_neox': 3739, 'n_words': 1229}