(**************************************************************************)
(*                                                                        *)
(*  Copyright (C) 2012 Johannes 'josch' Schauer <j.schauer@email.de>      *)
(*  Copyright (C) 2012 Pietro Abate <pietro.abate@pps.jussieu.fr>         *)
(*                                                                        *)
(*  This library is free software: 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, either version 3 of the    *)
(*  License, or (at your option) any later version.  A special linking    *)
(*  exception to the GNU Lesser General Public License applies to this    *)
(*  library, see the COPYING file for more information.                   *)
(**************************************************************************)

open! ExtLib
open Common

module StringSet = BootstrapCommon.StringSet

module Make (U : sig val univ : Cudf.universe end) = struct
  module G = BuildGraph.G
  module FindCyclesG = GraphUtils.FindCycles(G)
  module BGE = BuildGraphExtras.Make(struct let univ = U.univ end)

  let edges_in_most_cycles g cycles =
    let hist = FindCyclesG.get_cycles_per_edge_ht g cycles in
    let builddep_edges = List.filter (fun (k,_) -> match k with
      | (_,{BuildGraph.depend = BuildGraph.BuildDep},_) -> true
      | (_,{BuildGraph.depend = BuildGraph.BuildsFrom _},_) -> false
    ) (Hashtbl.fold (fun k v acc -> (k,v)::acc) hist []) in
    let cmp (v1, c1) (v2, c2) =
      let c = compare c2 c1 in
      if c <> 0 then c
      else match v1,v2 with
        | (sv1,{BuildGraph.depend = BuildGraph.BuildDep},iv1),(sv2,{BuildGraph.depend = BuildGraph.BuildDep},iv2) ->
          let srcpkgcmp = compare (BuildGraph.Unique.uid sv1) (BuildGraph.Unique.uid sv2) in
          if srcpkgcmp <> 0 then srcpkgcmp
          else
            compare (BuildGraph.Unique.uid iv1) (BuildGraph.Unique.uid iv2)
        | _ -> failwith "impossible"
    in
    List.sort ~cmp builddep_edges

  let min_builddep g =
    let src_vertices = G.fold_vertex (fun v acc ->
      let vertex = BuildGraph.Unique.value v in
      match vertex with
        | BuildGraph.SrcPkg id ->
            let p = CudfAdd.inttopkg U.univ id in
            (p, BGE.pkglist_of_vlist (G.succ g v))::acc
        | _ -> acc
    ) g [] in

    List.sort ~cmp:(fun (p1,a) (p2,b) ->
      let num_comp = compare (List.length a) (List.length b) in
      match num_comp with
        | 0 -> CudfAdd.compare p1 p2
        | n -> n
    ) src_vertices

  let get_src_bin_stats g =
    G.fold_vertex (fun v acc ->
        let succ = List.length (G.succ g v) in
        let pred = List.length (G.pred g v) in
        (v, succ, pred)::acc
      ) g []

  let ratio_source g =
    let src_vertices = G.fold_vertex (fun v acc ->
      let vertex = BuildGraph.Unique.value v in
      match vertex with
        | BuildGraph.SrcPkg id ->
            let p = CudfAdd.inttopkg U.univ id in
            let num_builddeps = List.length (G.succ g v) in
            let neededby = G.pred g v in
            let builddepof = List.fold_left (fun acc s -> (G.pred g s)@acc) [] neededby in
            (p, num_builddeps, BGE.pkglist_of_vlist neededby, (BootstrapCommon.CudfSet.elements (CudfAdd.to_set (BGE.pkglist_of_vlist builddepof))))::acc
        | _ -> acc
    ) g [] in

    List.sort ~cmp:(fun (p1,a1,_,a2) (p2,b1,_,b2) ->
      let num_comp = compare ((float_of_int b1)/.(float_of_int (List.length b2))) ((float_of_int a1)/.(float_of_int (List.length     a2))) in
      match num_comp with
        | 0 -> CudfAdd.compare p1 p2
        | n -> n
    ) src_vertices

  let ratio_binary g =
    let bin_vertices = G.fold_vertex (fun v acc ->
      let vertex = BuildGraph.Unique.value v in
      match vertex with
        | BuildGraph.InstSet (id,_) ->
            let p = CudfAdd.inttopkg U.univ id in
            let num_srcpkgs = List.length (G.succ g v) in
            let builddepof = G.pred g v in
            (p, num_srcpkgs, BGE.pkglist_of_vlist builddepof)::acc
        | _ -> acc
    ) g [] in

    List.sort ~cmp:(fun (p1,a1,a2) (p2,b1,b2) ->
      let num_comp = compare ((float_of_int b1)/.(float_of_int (List.length b2))) ((float_of_int a1)/.(float_of_int (List.length     a2))) in
      match num_comp with
        | 0 -> CudfAdd.compare p1 p2
        | n -> n
    ) bin_vertices

  let only_weak_missing weak_deps_set g =
    let only_weak = G.fold_vertex (fun v acc ->
      let vertex = BuildGraph.Unique.value v in
      match vertex with
        | BuildGraph.SrcPkg id ->
            let p = CudfAdd.inttopkg U.univ id in
            let bd = G.fold_succ (fun v2 acc ->
              let vertex2 = BuildGraph.Unique.value v2 in
              match vertex2 with
                | BuildGraph.InstSet (id,_) -> (CudfAdd.inttopkg U.univ id)::acc
                | _ -> failwith "impossible"
            ) g v [] in
            let bds = List.fold_left (fun acc p ->
              StringSet.add (p.Cudf.package) acc
            ) StringSet.empty bd in
            if StringSet.subset bds weak_deps_set then
              (p,bd)::acc
            else
              acc
        | _ -> acc
    ) g [] in
    List.sort ~cmp:(fun (s1,l1) (s2,l2) ->
      let num_comp = compare (List.length l2) (List.length l1) in
      match num_comp with
        | 0 -> CudfAdd.compare s1 s2
        | n -> n
    ) only_weak

end