/* ========================================================================== */
/*                          HANDLE BEST CONJUNCTION                           */  
/* ========================================================================== */
/*  Date                : 04/11/12                                            */
/*  Author              : Dominique BOUTHINON (db@lipn.univ-paris13.fr)       */            
/*                        LIPN Universite Paris 13 (France)                   */
/* History :		                                                          */
/*   - every example is now represented by its sets of maximal and            */
/*	    minimal possibilities					                       */
/*     (8/02/2013)                                                            */
/*   - stop the beam search taking into account the minimum acceptable number */
/*     of errors (option -y)                                                  */
/*     (4/11/12)                                                              */	
/*   - possibility to accept conjunction with p% of error of negative ex      */
/*     (option -p)                                                            */
/*     (2/11/12)                                                              */							  
/*   - ensures that there is a solution as soon as the seed is compatible-    */
/*     with all the negative examples                                         */
/*     (17/10/12)                                                             */
/* ========================================================================== */

:- module(
          best_conjunction6,
          [
            find_best_conjunction/7											
                       % LPos,                        not covered pos examples
                       % LTab_pos,
                       % LNeg,                        negative examples
                       % K,                            beam width
                       % (Best, Guidance, Quality, Errors, PC), % best conjunction
                       % LPos1,                        % remaining pos examples
                       % LTab_pos1
          ]
          ).
                  
/* =========================== CALL OTHERS MODULES ========================== */ 
  
call_modules :-
   getenv('LEAR_DIR', Lear),
   atom_concat(Lear, '/miscellaneous.pl', Misc),   
   use_module(Misc),
   atom_concat(Lear, '/specialization7.pl', Spec),
   use_module(Spec),
   atom_concat(Lear, '/assumptions2.pl', Assumptions),
   use_module(Assumptions),
   atom_concat(Lear, '/list.pl', List),
   use_module(List),
   atom_concat(Lear, '/domains.pl', Domains),
   use_module(Domains),
   atom_concat(Lear, '/term.pl', Term),
   use_module(Term),
   atom_concat(Lear, '/utilities_lear11.pl', Utils),
   use_module(Utils),
   atom_concat(Lear, '/formated_writing.pl', Writing),
   use_module(Writing),
   atom_concat(Lear, '/compatibility5.pl', Comp),
   use_module(Comp),
   atom_concat(Lear, '/graph_examples2.pl', Graph),
   use_module(Graph).
              
/* ==========================  FIND BEST CONJUNCTION ======================== */
        
find_best_conjunction(
                       LPos,                         % not covered pos examples
                       LTab_pos,
                       LNeg,                         % negative examples
                       K,                            % beam width
                       (Best, Guidance, Quality, Errors, PC, Cov), % best conjunction
                       LPos1,                        % remaining pos examples
                       LTab_pos1
                     ) :-  

        call_modules,  
	
        % check_compatibility_examples(LPos, LTab_pos, LNeg),
        
        choose_seed(LNeg, LPos, LTab_pos, seed(Head_seed, Heada_seed, Seed), 
                    LPos1, LTab_pos1),

        learn:verbosity(Verbose),
        (
          Verbose >= 2
           ->
           (
             length(LPos1, N),
             write('# remaining positive examples = '),
             display_ln(N),          	  
           	  
             writeln('Seed  = '),
             display_example((Head_seed, Seed))
           )
           ; true
        ),
        
        initialize_top(LPos1, LNeg, Id_top),  
        get_bottom((BOTTOM, GB, QB, EB, PCB, CovB)),

        learn:assert(first_step),

        best_conjunction(LPos1, LTab_pos1, LNeg, K,
                         [(Id_top, [(Head_seed, []), (Heada_seed, [])], Seed)],
                         (BOTTOM, GB, QB, EB, PCB, CovB),   % best conjunction so far
                         (Best, Guidance, Quality, Errors, PC, Cov),
                         -1).


	/* find the best conjunction */
best_conjunction(_ENC, _LTab_pos,  _LTab_neg, _K , 
                 [],                           % no more specialization
                                               % (by adding atom)
                 ((MC, LGraine), G, Q, Errors, PC, Cov),
                 ((MC, LGraine), G, Q, Errors, PC, Cov),
                 _Best_local):-                                  
        !.                                    

best_conjunction(
                 ENC,  _LTab_pos, LNeg,  _K, LC,
                 ((MC, LGraine), G, Q, Errors, PC, Cov),
                 ((MC, LGraine), G, Q, Errors, PC, Cov),
                 Best_local                % best coverage of the e+ of the 
                                           % preceding step of specilization
                                           % (not necessarily of the best hyp)
                 ):-
                                           % MC meilleure conjonction trouvee :
        Q > 0,                             % ne couvre aucun exemple negatif et
                                           % couvre tous les exemples positifs.
        stop(MC, Q, Errors, ENC, LNeg, PC, Best_local), 
        !,                                 % Aucune conjonction ne pourra
                                           % ameliorer le score de MC.
                                           % ou couvre le quota attendu
                                           % d'exemples positifs
        discard_candidate_hypothesis(LC).
         
best_conjunction(
     ENC,                   % exemples ambigus positifs non couverts.
     LTab_pos,
     LNeg,                  % suppositions sur les exemples negatifs.
     K,                     % nb conjontions retenues a chaque passe.
     LC,                    % conjonctions retenues jusqu'ici.
     (MV, GV, QV, EV, PV, CovV),  % best conjunction so far.
     (MC, GC, QC, EC, PCC, CovC), % best final conjunction.
     _Best_local
                 ) :-
               
      length(ENC,  Npos),
      length(LNeg, Nneg),

        learn:verbosity(Verbose),  
        (
         Verbose >= 3
            ->
              nl, 
              nl,
              write('# positive examples : '),
              writeln(Npos),
              write('# negative examples : '),
              writeln(Nneg),
              nl,
              nl
            ; true
        ),
   
        clausal_to_conjunctive(LC, LCA),
        couv_sup_LC(LCA, LC1),  
                %  top down exploration

        maj_first_step,
        discard_doublets(LC1, LCB),
        conjunctive_to_clausal(LCB, LH),
 

                         % compute best conjunctions and prune hypotheses
        k_best_conjunctions((MV, GV, QV, EV, PV, CovV), 
                            ENC, LTab_pos, LNeg, LH, K, LQ),                 
        (
          Verbose >= 2
            ->
             length(LQ, NQ),
             nl,
             display_ln('===================================================='),
             write('# of candidate conjunctions: '),
             writeln(NQ),
             display_best_conjunctions(LQ, Npos, Nneg)
            ; true
        ),
        

        learn:retractall(best_have_changed), 

        best_candidate(LQ, 
                       (MV, GV, QV, EV, PV, CovV), 
                       (MC1, G1, Q1, E1, PC1, Cov1), 
                       LK, -1, Best_coverage_this_step),
                                            % conjonction de
                                            % meilleure qualite (compte tenu
                                            % des erreurs) + elagage.
        (
          Verbose >= 2
             ->
             nl,
             write('___________________Best candidate___________________  '),
             display_best_conjunction2((MC1, G1, Q1, E1, PC1, Cov1), Npos, Nneg),
             display_ln('____________________________________________________')
           ; true
        ),
        
        best_conjunction(ENC, LTab_pos, LNeg,  K, LK, 
                         (MC1, G1, Q1, E1, PC1, Cov1), (MC, GC, QC,EC, PCC, CovC),
                         Best_coverage_this_step).


	/* check whether we can stop the search for a valid conjunction */
	
	% no error and all positive examples are covered 
stop(_MC, _Quality, 0, ENC, _LNeg, 
     Positive_coverage, _Best_local_coverage) :- 
     length(ENC, Positive_coverage),   
     !.

     % no error and coverage will decrease (the best coverage
     % of the remaining hypothesis is less thant the current positive coverage)
stop(_MC, _Quality, 0, _ENC, _LNeg, 
    Positive_coverage, Best_local_coverage) :-
    Positive_coverage >= Best_local_coverage,
    !.             
                                    
   % no error and minimal required number of positive examples are covered. 
stop(_MC, Quality, 0, _ENC, _LNeg, 
   Positive_coverage, _Best_local_coverage) :- 
   current_option(min_coverage, Ratio_min_a), 
   atom_number(Ratio_min_a, Ratio_min),      
   Min_positive_covered is (1.0 * Ratio_min * Positive_coverage / 100.0), 
   Quality >= Min_positive_covered,
   !.

	% there are errors on negative examples (but Quality > 0) 
stop(_MC, _Quality, Errors, _ENC, LNeg, 
     _Positive_coverage, _Best_local_coverage) :-
  length(LNeg, Nb_negative),
  check_acceptable_errors(Errors, Nb_negative), % # errors is acceptable
  not_less_errors_made(Errors),                 % # errors has not decreased
  max_tries_reached.                            % No another try : we stop.                        


	/* check whether the number of errors has not decreased */
not_less_errors_made(Present_errors) :-
   learn:check_count_exists_value(past_nb_errors, Present_errors), 
   learn:read_count(past_nb_errors, Past_errors),
   Present_errors == Past_errors,   % # errors has not decreased
   !.

	% # errors has decreased,
not_less_errors_made(Present_errors) :-
   learn:delete_count(nb_tries), 
   learn:delete_count(past_nb_errors),
   learn:reset_count_value(past_nb_errors, Present_errors).    


   % count the number of try to decrease the number of errors of the
   % best hypothesis. 
max_tries_reached :-
   learn:nb_max_tries(Nb_max),     % Nb tries to decrease the # errors
   learn:check_count_exists_value(nb_tries, -1),
   !,
   learn:get_count(nb_tries, N),   % mandatory to increment the number of tries
                                   % don't put 'get_count(nb_tries, Nb_max)'
   N == Nb_max.


	/* discard the flag saying this is the first step of the iteration
      to find the best conjunction */
maj_first_step :-
   learn:retract(first_step),
   !.

maj_first_step.


discard_candidate_hypothesis([]) :-
   !.

discard_candidate_hypothesis([(Id,_)|LH]) :-
   discard_hypothesis(Id),
   discard_candidate_hypothesis(LH).
   

/* ========================================================================== */
/*                             FIND BEST HYPOTHESIS                           */
/* ========================================================================== */

                /* recherche dans LQ la "meilleure" conjonction          */
                /* supprime la qualite et les hypotheses de qualite      */
                /* non nulle. car Q > 0 => qualite ne pourra que se      */
                /* degrader, Q < 0 =>  MC ne couvrira jamais rien        */
                /* (garde hypotheses dont Q > 0 et Errors > 0 qui        */
                /* peuvent s'ameliorer                                   */
                
best_candidate([], (MC, GC, QC, EC, PC, CovC), (MC, GC, QC, EC, PC, CovC), 
               [], Best_PC, Best_PC) :-
        !.

best_candidate(
                   [(C, G, Q, E, PC, Cov)|LQ],   % liste des hypotheses
                    (MV, GV, QV, EV, PV, CovV),  % meilleure hypothese jusqu'ici
                    (MC, GC, QC, EC, PCC, CovC), % meilleure hypothese finale
                    LK,                          % liste finale hypotheses
                    Best_PC,                     % meilleure couverture courante
                                                 % des e+ (initialement -1)
                    Best_final_PC                % meilleure couverture finale des e+
                  ):-
                  
        (
          (Q == 0 ; E > 0)      % keep hypotheses that could lead to
                                % better hypotheses. 
                        ->  
                         (
                           Keep = [C],            % keep hypothesis C
                           Best is max(PC, Best_PC)
                         )  
                        ;
                        (                         % we will discard hypothesis C
                          Keep = [],
                          Best is Best_PC
                        )
        ),
        
        (
           better_evaluation(Q, G, E, QV, GV, EV)
                     ->
                      (
                        update_best_hypothesis(C),
                        best_candidate(LQ, (C, G, Q, E, PC, Cov), 
                                           (MC, GC, QC, EC, PCC, CovC),
                                       LK1, Best, Best_final_PC)
                      )
                      ;  best_candidate(LQ, (MV, GV, QV, EV, PV, CovV), 
                                            (MC, GC, QC, EC, PCC, CovC),
                                        LK1, Best, Best_final_PC)
        ),

        (
          Keep = []
           ->
             (
              C = (Indice, _),
              discard_hypothesis(Indice),
              LK = LK1
             )
           ; append(Keep, LK1, LK)
        ).

      
update_best_hypothesis((Indice, _New_best_hypothesis)) :-
   learn:recorded('best_hypothesis', _, Reference),
   learn:erase(Reference),
   learn:recorded(Indice, Memory),
   learn:recorda('best_hypothesis', Memory),
   learn:asserta('best_have_changed'). 
   

/* ============================= CHOOSING A SEED ============================ */

   /* choose the seed as the least ambigous example among the set of
      positive ambiguous examples */
choose_seed(_, [], [], _, [], []) :-
                             % No positive example is a valid seed :
                             % the variabilization of each possibility
                             % of each ambiguous example 'covers' each
                             % possibility of a negative example.
   writeln('!!!!!!!! NO POSSIBLE SEED !!!!!!!!!!!!!'), 
   !,
   learn:assert(no_seed),
   fail. 
   
       
choose_seed(
		   LNeg,        % negative ambiguous examples 
		   LPos,        % positive ambiguous examples  
             LTab_pos, 		
		   seed(VHead_seed, Head_seeda, Body_seed),    % variabilized seed
             LPos1,       % remaining positive examples
					           % including choosen seed
                          % (positive examples choosen as seed that are not 
                          %  consistent with LNeg have been discarded)  
             LTab_pos1              
	      ) :-

        find_least_ambiguous_examples(LPos, LTab_pos,
                                       (Id_seed, Head_seed, Exp_seed),
                                       (Id_seed, Tabs_seed),
                                       LPosA, LTab_posA), 
            			% LPosA is LPos minus (Id_seed, Head_seed, Seed)  

        Exp_seed   = min_max(Inter_seed, Graph_seed),
        
        		         % build tables and possibilites from graph examples
        build_tables_from_graph(
                                 graph(Id_seed, Head_seed, Graph_seed), 
                                 tabs(Id_seed, Tabs_seed), 
                                 tables(Id_seed, Head_seed, Seed)
                                ),	
	   write('seed is the '),
	   display_example_num((Id_seed, Head_seed, Seed)),

        Head_and_seed = [[[Head_seed]]|Seed],   % join Head_seed and Seed

        			     % variabilize constants whose type is not instantiable
        variabilize_example(not_instantiable, Head_and_seed, [], 
                             VHead_and_seed),
        discard_similar_elements_tab(VHead_and_seed, VHead_and_seeda, 
                                    structurally),

        writeln(' seeda is :'),
        VHead_and_seeda = [[[Heada1]]|Seeda1],   % join Head_seed and Seed
        display_example((Heada1, Seeda1)),

       
        check_seed_ok(
                      LPosA, 
                      LTab_posA, 
                      LNeg, 
                      Inter_seed,
                      graph(Id_seed, Head_seed, Graph_seed),
                      tabs(Id_seed, Tabs_seed),
                      VHead_and_seeda, 
                      seed(VHead_seed, Head_seeda, Body_seed),
                      LPos1, 
                      LTab_pos1
                     ).

	/* check the seed against negative examples */
check_seed_ok(
              LPosA, 
              LTab_posA, 
              _LNeg, 
              Inter_seed,
              graph(Id_seed, Head_seed, Graph_seed), 
              tabs(Id_seed, Tabs_seed),
              VHead_and_seeda, 
              seed(VHead_seed, Head_seeda, Body_seed), 
              [(Id_seed, Head_seed, min_max(Inter_seed,Graph_seed))|LPosA],
              [(Id_seed, Tabs_seed) |LTab_posA]
         ) :-
       			
	% build all possibilities of the seed (into LConj)
   % cross_product_lists_of_lists(VHead_and_seeda, LConj),
   % check_seed_against_examples(LConj, LNeg, Id_seed),     
   !,

     				% variabilize constants whose type is instantiable	
   variabilize_example(instantiable, VHead_and_seeda, [], VHead_and_seed2),
   
   VHead_and_seeda = [[[Head_seeda]]|Seeda],  
   VHead_and_seed2 = [[[VHead_seed]] |VBody_seed],
   
   writeln('variabilized seed is '),
   display_example((VHead_seed, VBody_seed)),

   join_seed_atoms(VBody_seed, Seeda, Body_seed),

   learn:retractall(id_seed(_)),
   learn:assert(id_seed(Id_seed)).


					% the current seed is not good, one discards the
					% associated example
check_seed_ok(
              LPosA, 
              LTab_posA, 
              LNeg, 
              _Inter_seed,
              _Graph_seed, 
              _Tabs_seed, 
              _VHead_and_seeda,
              Seed,
              LPos1, 
              LTab_pos1) :-
   writeln('!!!!!!!!!!!!!!!!! Current seed is not good !!!!!!!!!!!!!!!!!!'),
   writeln('one tries another seed...'),
   choose_seed(LNeg, LPosA,  LTab_posA, Seed, LPos1, LTab_pos1).
    
            
        
  /* check whether the seed is compatible- with all negative examples */
  /* (one possibility (Conj) must be compatible with all examples      */
check_seed_against_examples([], _ , Id) :-
   !,
   write('the example '),
   writeln(Id),
   writeln('is not compatible- with some negative examples'),
   fail.                                               
  
check_seed_against_examples([[Head|Body]|_LConj], LNeg, Id) :- 
   conj_compatible_neg_examples(LNeg,  (Head,Body), Id),   
                                                         % ok at least one Conj
   !.                                                    % is comp- with all 
                                                         % negative examples
check_seed_against_examples([_Conj|LConj], LNeg, Id) :- 
   check_seed_against_examples(LConj, LNeg, Id).


        /* check whether Hyp is comp- with all negative examples */
conj_compatible_neg_examples([], _Hyp, _Id) :-
   !.

conj_compatible_neg_examples([(Id_ex, Head_exp, _Body_exp) |LNeg], Hyp, Id)  :-
   get_negative_assumptions(Id_ex, LAssumptions),
   compatible_neg(neg, Hyp, Id_ex, Head_exp, LAssumptions),
   !,
   conj_compatible_neg_examples(LNeg, Hyp, Id).


conj_compatible_neg_examples([(Id_ex, Head_exp, min_max(Body_exp, _))|_LNeg], Hyp, Id) :-
   get_negative_assumptions(Id_ex, LAssumptions),
   nl,
   nl,
   writeln(' !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! '),
   writeln(' The variabilized possibility of the seed '),
   writeln(Id),
   writeln(Hyp),
   writeln('is not compatible- with the following negative example : '),
   writeln(Id_ex),
   display_example_num((Id_ex, Head_exp, Body_exp)),
   writeln('assumptions :'),
   writeln(LAssumptions),
   nl,
   gtrace,
   fail.

       
  /* check whether the (partially variabilized) positive example 
     is compatible- with the negative examples  
     (one possibility (Conj) must be compatible  */
check_pos_against_neg_examples([], _ , Id) :-
   !,
   write('the example '),
   writeln(Id),
   writeln('is not compatible with some negative examples').
                                              
  
check_pos_against_neg_examples([[Head|Body]|_LConj], LNeg, Id) :- 
   conj_compatible_neg_examples(LNeg,  (Head,Body), Id),   
                                                 % ok at least one Possibility
   !.                                            % is comp- with all 
                                                 % negative examples
check_pos_against_neg_examples([_Conj|LConj], LNeg, Id) :- 
   conj_pos_against_neg_examples(LConj, LNeg, Id).


/* ================ Check compatibility between set of examples ============= */

	/* check whether the positive examples of LPos are compatible
        with the negative examples of LNeg */
check_compatibility_examples([], _LTab_pos, _LNeg) :-
   !.

check_compatibility_examples(
                             [(Id, Head, min_max(_,Graph))|LPos], 
                             [(Id, Tabs)|LTabs],
                             LNeg
                            ) :-
      		         %build tables and possibilities from graph examples
   build_tables_from_graph(
                            graph(Id, Head, Graph), 
                            tabs(Id, Tabs), 
                            tables(Id, Head, Seed)
                          ),	

   Head_and_seed = [[[Head]]|Seed],   % join Head_seed and Seed

        			     % variabilize constants whose type is not instantiable
   variabilize_example(not_instantiable, Head_and_seed, [], 
                             VHead_and_seed),
   discard_similar_elements_tab(VHead_and_seed, VHead_and_seed1, 
                                structurally),

   cross_product_lists_of_lists(VHead_and_seed1, LConj),
   check_pos_against_neg_examples(LConj, LNeg, Id),
  
   check_compatibility_examples(LPos, LTabs, LNeg).


   /* get the least ambiguous examples */
find_least_ambiguous_examples(
                              [Ex|LEx], 
                              [Tab|LTab],
                              Ex_least, 
                              Tab_least,
                              LEx1,
                              LTab1
                             ) :-
   least_ambiguous_examples(LEx, LTab, Ex, Tab, Ex_least, Tab_least,
                            LEx1, LTab1).

	/* fin the least ambiguous examples */
least_ambiguous_examples([], 
                         [],
                         Ex_least, 
                         Tab_least,
                         Ex_least, 
                         Tab_least,
                         [], 
                         []) :-
   !.
   
least_ambiguous_examples(
                         [(Id, Head, Ex)|LPos],           % examples to explore
                         [(Id, Tab)|LTab],
                         (Id_ex1, Head1, Ex1),            % least example so far
                         (Id_ex1, Tab1),
                         (Id_least, Head_least, Ex_least), % least ambigous example
                         (Id_least, Tab_least),
                         [(Id_ex1, Head1, Ex1)|LEx1],
                         [(Id_ex1, Tab1)|LTab1]
                         ) :-   
   less_ambiguous(Tab, Tab1),
   !,
   least_ambiguous_examples(LPos, 
                            LTab, 
                            (Id, Head, Ex), 
                            (Id, Tab),
                            (Id_least, Head_least, Ex_least), 
                            (Id_least, Tab_least),
                            LEx1, 
                            LTab1).
                         
  
  least_ambiguous_examples(
                           [Ex|LPos],          % examples to explore
                           [Tab|LTab],
					            Ex1,                % least ambiguous example so far
                           Tab1,
                           Ex_least,           % final least ambiguous example
                           Tab_least,
                           [Ex|LEx1],
                           [Tab|LTab1]
                         ) :-   
   least_ambiguous_examples(LPos, LTab, 
                            Ex1, Tab1,
                            Ex_least, Tab_least,
                            LEx1, LTab1).
        

	/* make coples of atoms (a, b) of the seed where a is the variabilized 
        atom and b is the original (non variabilized) atom */
join_seed_atoms([], [], []) :-
   !.

join_seed_atoms([VTable|VLTables], [Table|LTables], [Table1|LTables1]) :-
   join_seed_atoms_table(VTable, Table, Table1),
   join_seed_atoms(VLTables, LTables, LTables1).


join_seed_atoms_table([], [], []) :-
   !.

join_seed_atoms_table([VPossi|VLPossi], [Possi|LPossi], [Possi1|LPossi1]) :-
   join_seed_atoms_possibility(VPossi, Possi, Possi1),
   join_seed_atoms_table(VLPossi, LPossi, LPossi1).


join_seed_atoms_possibility([], [], []) :-
   !.

join_seed_atoms_possibility(
                            [VAtom|LVAtom], 
                            [Atom|LAtom], 
                            [(VAtom,Atom)|LVA]) :-
   join_seed_atoms_possibility(LVAtom, LAtom, LVA).
  



 /* compare the ambiguity of two ambiguous examples */
less_ambiguous(Tabs1, Tabs2) :-
   number_possibilities(Tabs1, Np1),  
   number_possibilities(Tabs2, Np2),
   length(Tabs1, Nb_tabs1),
   length(Tabs2, Nb_tabs2),
   check_possibilities(Nb_tabs1, Nb_tabs2, Np1, Np2).
   
   /* compare ambiguity by comparing number of possibilities and number of tables */  
check_possibilities(_Tabs1, _Tabs2, Np1, Np2) :-
   Np1 < Np2,                            % Ex1 has less possibilities than Ex2
   !.           
   
check_possibilities(Nb_tabs1, Nb_tabs2, Np, Np) :-              
   Nb_tabs1 < Nb_tabs2,      % Ex1 has the same number of possibilities than Ex2
   !.                        % but has less tables.
 

 /* compute the number of possibilities of an ambiguous examples */
number_possibilities([(_, Table)], N) :-
   length(Table, N),
   !.
   
number_possibilities([(_, Table)|LTables], Nout) :-
   number_possibilities(LTables, N1),
   length(Table, N),
   Nout is N * N1.

    
/* ============================== INITIALIZATION ============================ */
     
get_top_conjunction([[Top]|VSeed], Top, VSeed).  % most general hypothesis 
                               
get_bottom(((id_bottom, hyp_bottom), -1, -1, Max_errors, 0, 0)) :-
   learn:max_errors(Max_errors).
                                    % most specific conjunctive hypothesis
                                    % (it covers no example)
                                    % guidance = 1, quality = -1, 
                                    % Errors = Max_errors
                                    % nb pos ex covered = 0
                                    

initialize_top(LPosA, LNegA, 'hyp_0') :-
   get_examples_indices(LPosA, LN_pos),
   get_examples_indices(LNegA, LN_neg),
   learn:recorda('hyp_0',(LN_pos, LN_pos, [], LN_neg, 0)),
   learn:recorda('best_hypothesis', (LN_pos, LN_pos, [], LN_neg, 0)).
                                    

get_examples_indices([], []):-
   !.
   
get_examples_indices([(Indice, _Exp)|LExp], [Indice|LIndices]) :-
   get_examples_indices(LExp, LIndices).
                                       
/* ====================== NUMBERS COMPATIBLES EXAMPLES ====================== */ 

      /* count the number of positive examples compatible+ with (Hyp, LSeed) */
nb_compatible_positive_examples(Id, Hyp, LGraph_pos, LTab_pos,
                                Nb_pos_compatible, Nb_pos_covered):-
     
       learn:recorded(
                        Id,
                        (
                         LNum_pos_covered, 
                         LNum_pos_compatible, 
                         _LNum_pos_not_compatible,
                         LNum_neg_not_compatible, 
                         Nb_neg_compatible
                        ),
                         Reference
                      ),

       get_examples_from_nums(LNum_pos_compatible, LGraph_pos, 
                              LGraph_pos_compatible),
       get_examples_from_nums(LNum_pos_compatible, LTab_pos, 
                              LTab_pos_compatible),


       numbers_compatible_positive_examples(
                                             LGraph_pos_compatible,
                                             LTab_pos_compatible,
                                             Hyp,
                                             LNum_pos_compatible1,
                                             Nb_pos_compatible
                                            ),
       subtract( 
                 LNum_pos_compatible, 
                 LNum_pos_compatible1,
                 LNum_pos_not_compatible1
                ),

	  get_examples_from_nums(LNum_pos_covered, LGraph_pos, LPos_covered),	



	  numbers_covered_positive_examples(
                                             LPos_covered,
                                             Hyp,
                                             LNum_pos_covered1,
                                             Nb_pos_covered
                                         ),

       % check_comp_cov(LNum_pos_compatible1, LNum_pos_covered1),

       learn:erase(Reference),
       learn:recorda(Id,(
                         LNum_pos_covered1,
                         LNum_pos_compatible1,
                         LNum_pos_not_compatible1,
                         LNum_neg_not_compatible, 
                         Nb_neg_compatible
                        )
                     ).


	/* check wether the two lists are equals (the order does not matter) */
check_comp_cov(L1, L2) :-
   sort(L1, LA),
   sort(L2, LB),
   check_dif(LA, LB).

check_dif(L, L) :-
   !.

check_dif(LA, LB) :-
   gtrace,
   subtract(LA, LB, L),
   writeln(L).

/* ========= Compute the number of positive examples covered by Hyp ========= */


numbers_covered_positive_examples([], _, [], 0) :-
   !.

numbers_covered_positive_examples(
                                    [(Indice, Head_ex, min_max(Ex_min, _))|LEx],
                                    [Hyp, Hypa], 
                                    [Indice|LIndices],
                                    NR1
                                 ) :-
   covered_pos(Hyp, Indice, Head_ex, Ex_min),
   !,
   numbers_covered_positive_examples(LEx, [Hyp, Hypa], LIndices, NR),
   NR1 is NR + 1.

 numbers_covered_positive_examples([_Ex|LExp], Hyp, LIndices, NR) :-
    numbers_covered_positive_examples(LExp, Hyp, LIndices, NR).

% ----------------------------------------------------------------


numbers_compatible_positive_examples([], [], _, [], 0) :-
   !.

numbers_compatible_positive_examples(
                                      [(Indice, Head_ex, Graph_ex)|LEx],
                                      [(Indice, Tab_ex)|LTab],
                                      [Hyp, Hypa], 
                                      [Indice|LIndices],
                                      NR1
                                     ) :-
   Graph_ex = min_max(_Graph_min, Graph_max),
   compatible_pos(Hyp, (Indice, Head_ex, Graph_max), (Indice, Tab_ex)),
   !,
   numbers_compatible_positive_examples(LEx, LTab, [Hyp, Hypa], LIndices, NR),
   NR1 is NR + 1.

 numbers_compatible_positive_examples([_Exp|LExp], [_Tab|LTab],
                                      Hyp, LIndices, NR) :-
    numbers_compatible_positive_examples(LExp, LTab, Hyp, LIndices, NR).


/* ---------------------------- negative examples --------------------------- */

nb_compatible_negative_examples(Id, Hyp, LNeg, Nb_neg_compatible2):- 
        learn:recorded(
                       Id,
                       (
                        LNum_pos_covered,
                        LNum_pos_compatible, 
                        LNum_pos_not_compatible,
                        LNum_neg_not_compatible, 
                        Nb_neg_compatible),
                        Reference
                      ),          

       get_examples_from_nums(LNum_neg_not_compatible,
                              LNeg, LNeg_not_compatible),  

       numbers_compatible_negative_examples(LNeg_not_compatible,
                                            Hyp, 
                                            LNum_neg_compatible,
                                            Nb_neg_compatible1),   
                           
       subtract(LNum_neg_not_compatible, LNum_neg_compatible,
                                       LNum_neg_not_compatible1),

       Nb_neg_compatible2 is Nb_neg_compatible + Nb_neg_compatible1,
       learn:erase(Reference),
       learn:recorda(Id,(LNum_pos_covered,
                         LNum_pos_compatible,
                         LNum_pos_not_compatible, 
                         LNum_neg_not_compatible1,
                         Nb_neg_compatible2)).
              
          
numbers_compatible_negative_examples([], _, [], 0) :-
   !.
                     
numbers_compatible_negative_examples(
                                      [(Indice, Head_exp, _Body_exp)|LExp], 
                                      [Hyp, Hypa], 
                                      [Indice|LIndices],
                                      NR1
                                    ) :-
   get_negative_assumptions(Indice, LAssumptions),                                  
   compatible_neg(neg, Hyp, Indice, Head_exp, LAssumptions),
   !,
   numbers_compatible_negative_examples(LExp, [Hyp, Hypa], LIndices, NR),
   NR1 is NR + 1.
   
numbers_compatible_negative_examples([_|LExp], Hyp, LIndices, NR) :-
    numbers_compatible_negative_examples(LExp, Hyp, LIndices, NR).
    
            
get_examples_from_nums([], _, []) :-
   !.

get_examples_from_nums([Num|LNum], LExp,  [(Num, Exp)|LExp1]) :-
   select((Num, Exp), LExp, LExpA),
   !,
   get_examples_from_nums(LNum, LExpA, LExp1).


/* ========================================================================== */
/*                        GUIDANCE AND QUALITY HANDLING                       */
/* ========================================================================== */

                          /* recherche les k conjonctions de meilleur guidage */
k_best_conjunctions(
                        Best,       % Best conjunction so far
                        LPos,       % # non compatible+ positive examples
                        LTab_pos,
                        LNeg,
                        LConj,      % list des conjonctions candidates
                        K,          % nombre de conjonction a retenir
                        LQ          % list des conjonctions retenues
                    ):-            
        learn:compatibility_weight(Compatibility_weight),   
        compute_guidances_qualities(Compatibility_weight,
                                    LPos, LTab_pos, LNeg, LConj, LGQ),
        check_discard_hypothesis_coverage(LGQ, Best, LGQ1),
        k_best_evaluations(LGQ1, K, LQ, Remain),
        discard_remaining_hypothesis(Remain).
        

    /* discard the hypotheses that cannot improve the current best hypothesis */

check_discard_hypothesis_coverage(
                                  LGQ, (HBest, CBest, QBest, 0, CBest, CovBest), 
                                  LGQ1
                                 ) :-
   !,
   discard_hypothesis_coverage(LGQ, 
                               (HBest, CBest, QBest, 0, CBest, CovBest), LGQ1).

check_discard_hypothesis_coverage(LGQ, _Best, LGQ).
   
	   
discard_hypothesis_coverage([], _Best, []) :-
     !.
              
   % H cannot become better than HBest.
   % HBest has no error (so QBest == CBest), and H covers potentially
   % less e+ than HBest (C <= CBest)                    
discard_hypothesis_coverage(
                              [((Id, _H), _G, _Q, _E, C, _Cov)|LH], 
                              (HBest, GBest, CBest, 0, CBest, CovBest),     
                              LH_out 
                           ) :-                       
   C =< CBest,
   !,
   discard_hypothesis(Id),
   writeln('discarded'),
   discard_hypothesis_coverage(LH,  (HBest, GBest, CBest, 0, CBest, CovBest), 
                               LH_out).
   

discard_hypothesis_coverage([H|LH], Best, [H|LH_out]) :- 
   discard_hypothesis_coverage(LH, Best, LH_out).  


discard_remaining_hypothesis([]) :-
   !.
        
discard_remaining_hypothesis([((Id, _), _, _, _)|LH]) :-
   discard_hypothesis(Id),
   discard_remaining_hypothesis(LH).


       /* compute the guidance and the quality of each conjunctive hypothesis */
compute_guidances_qualities(_, _, _, _,  [], []) :-
   !.

compute_guidances_qualities(Compatibility_weight, LPos, LTab_pos, LNeg, 
                            [Conj|LConj],
                            [(Conj, G, Q, E, PC, Cov)| LGuidances]) :-
        guidance_quality(Compatibility_weight,
                         LPos, LTab_pos, LNeg, Conj, G, Q, E, PC, Cov),
        Q >= 0,                            
        !,
        compute_guidances_qualities(Compatibility_weight,
                                    LPos, LTab_pos, LNeg, LConj, LGuidances).


compute_guidances_qualities(Compatibility_weight,
                            LPos, LTab_pos, LNeg, [_|LConj], LGuidances):-
        compute_guidances_qualities(Compatibility_weight,
                                    LPos, LTab_pos, LNeg, LConj, LGuidances).


                       /* calcule la valeur de guidage de la conjonction Conj */
guidance_quality(
                  Compatibility_weight, % poids associe aux examples positifs
                                        % compatible mais non couverts
                  LPos,                 % exemples positifs non encore couverts
                  LTab_pos,
                  LNeg,                 % suppositions sur les negatifs
                  (Id, Hyp, Seed),      % conjunction hypothesis
                  Guidance,
                  Quality,
                  Errors,               % Nb negative ex not compatible-
                  Nb_pos_compatible,    % # compatible positive examples
                  Nb_pos_covered        % # covered positive examples
               ):-
  
        length(LNeg, N),
        length(LPos,P),
     
        nb_compatible_negative_examples(Id, Hyp, LNeg, Nb_neg_compatible),
        nb_compatible_positive_examples(Id, Hyp, LPos, LTab_pos,
                                        Nb_pos_compatible, Nb_pos_covered),
   
	   Nb_pos_comp_not_covered is Nb_pos_compatible - Nb_pos_covered,
        Nb_attributed_pos is Nb_pos_covered + 
                             Compatibility_weight * Nb_pos_comp_not_covered,

        compute_guidance(Nb_attributed_pos, P, 
                         Nb_neg_compatible, N, 
                         Guidance1, _Guidance_pos, _Guidance_neg), 

       set_final_guidance(Guidance1, Nb_pos_covered, Guidance),   
  
        Errors is N-Nb_neg_compatible,

		/*
        compute_quality(Nb_attributed_pos, Nb_neg_compatible, N, 
                        Quality, Errors), */
      
		compute_quality(Nb_pos_compatible, Nb_neg_compatible, N, 
                        Quality, Errors),
        
        learn:verbosity(Verbose),
        (
         Verbose >= 3
            ->
              display_best_conjunction2(
                                          (
                                           (Id, Hyp,Seed), 
                                            Guidance, 
                                            Quality, 
                                            Errors, 
                                            Nb_pos_compatible,
                                            Nb_pos_covered
                                          ),
                                          P, N
                                       ),               
              (
                Verbose >= 7
                 ->
                 (
                  learn:recorded(Id,(
                                     LNum_pos_covered,
                                     LNum_pos_compatible,
                                     _LNum_pos_not_compatible, 
                                     LNum_neg_not_compatible,
                                     _Nb_neg_compatible
                                    )
                                 ),
                   writeln('LNum_pos_covered   : '),
                   writeln(LNum_pos_covered),
                   writeln('pos compatible     : '),
                   writeln(LNum_pos_compatible),
                   writeln('neg not compatible : '),
                   writeln(LNum_neg_not_compatible),
                   writeln('')
                 ) 
                 ;
                 true
              ),
              nl
            ;
            true
        ).
        

/* ajust the guidance according to the number of covered examples */


set_final_guidance(Guidance, _, Guidance).

/*
set_final_guidance(Guidance, 0, Guidance) :-
   !.

			% gros poids donne si couverture d'au moins un exemple positif
set_final_guidance(Guidance1, _Nb_pos_covered, Guidance) :-
   Guidance is Guidance1 + 1000000.
*/

       

	/* compute a guidance */
compute_guidance(
                 Nb_attributed_pos,
                 Nb_pos, 
                 Nb_neg_compatible, 
                 Nb_neg, 
                 Guidance,
                 Guidance_pos,
                 Guidance_neg
                 ) :-

        Guidance_pos is  (100.0 * Nb_attributed_pos)/Nb_pos,
        Guidance_neg is  (100.0 * Nb_neg_compatible)/Nb_neg,
        (
          learn:guidance(average)              
             -> Guidance is (0.5 * (Guidance_pos + Guidance_neg))
             ;  Guidance is  100.0 * (Nb_attributed_pos + Nb_neg_compatible)/
                                     (Nb_pos + Nb_neg)
        ).
     

	/* compute the quality of the current hypothesis */

	% no positive examples is and will be covered
compute_quality(0, _N_neg_compatible, _N, -1, _Errors) :-
   !.                   

   % correct hypothesis compatible+ with Nb_pos_compatible positive examples
   % and compatible- with the N negative examples.
compute_quality(Nb_attributed_pos, N, N, Nb_attributed_pos, 0) :-
   !.      
              
   % current hypothesis is not corrrect but we accept it because it makes
   % less than the number of acceptable errors on the negative examples											 
compute_quality(Nb_attributed_pos, _N_neg_compatible, N, 
                Nb_attributed_pos, Errors) :-
   check_acceptable_errors(Errors, N),
   !.

   % current hypothesis is not corrrect but could be in the future 											 
compute_quality(_Nb_attributed_pos, _N_neg_compatible, _N, 0, _Errors).


	/* return the K "best" hypothesis */
k_best_evaluations(Remain, 0, [], Remain) :-
        !.

k_best_evaluations([], _, [], []) :-
        !.

k_best_evaluations(L, K, [(Conj, G, Q, E, PC, Cov)|Lmax], Remain):-
        best_evaluated_conjunction(L, (Conj, G, Q, E, PC, Cov)),
        select((Conj, G, Q, E, PC, Cov), L, L1),
        !,
        K1 is K-1,
        k_best_evaluations(L1, K1, Lmax, Remain).
        
        
 	/* return the conjunction having the best quality or guidance */
best_evaluated_conjunction([], (_Conj, -1,-1, Max_errors, _, _)) :-
        learn:max_errors(Max_errors),
        !.                      % guidage/qualite artificiellement mauvais

best_evaluated_conjunction([(_Conj, G, Q, E, _, _)|L], 
                             (Conj1, G1, Q1, E1, PC1, Cov1)):-
        best_evaluated_conjunction(L, (Conj1, G1, Q1, E1, PC1, Cov1)),
        better_evaluation(Q1, G1, E1, Q, G, E),
        !.

best_evaluated_conjunction([(Conj, G, Q, E, PC, Cov)|_], 
                            (Conj, G, Q, E, PC, Cov)).

  
	/* compare two hypotheses according to their qualities, guidances and
      errors (number of non compatible negative examples) */

	% when no error the best quality wins */
better_evaluation(Q1, G1, 0, Q, G, 0) :-
  !,
  better_guidance_quality(Q1, G1, Q, G).

	% E1 = 0 (so Q1 > 0) and E > 0
   % the hypothesis with no error wins 
better_evaluation(_Q1, _G1,  0 , _Q, _G, _E) :-
  !.

	% E1 > 0 and E > 0 (so Q = 0)
   % the hypothesis with no error wins 
better_evaluation(_Q1, _G1,  _E1 , _Q, _G, 0) :-
  !,
  false.

	% both hypotheses have errors */
better_evaluation(Q1, G1, _E1, Q, G, _E2) :-
  better_guidance_quality(Q1, G1, Q, G).

   
	/* evaluates the best hypothese without taking account the errors on
      the negative examples*/
	% the best quality wins
better_guidance_quality(Q1, _G1,  Q, _G) :-
   Q1 > Q,
   !.
   
	% when the qualities are equal the best guidance wins
better_guidance_quality(Q, G1, Q, G) :-
   G1 > G.
	
/* ========================================================================== */
/*                             MISCELLENAOUS                                  */
/* ========================================================================== */


	/* get the number of acceptables_errors */
check_acceptable_errors(Errors, Nb_negative_examples) :-
   learn:acceptable_errors(P),               % percentage of acceptable errors
                                             % on negative examples.
   Nb_acceptable_errors is P * Nb_negative_examples / 100.0,
   Errors < Nb_acceptable_errors.
   
sort_arguments([], []) :-
   !.

sort_arguments([(Id, Hyp, LSeed)|LHyp], [(Id, Hyp, LSeed1)|LHyp1]) :-
   % sort(Hyp, Hyp1),
   sort_tables(LSeed, LSeed1),
   sort_arguments(LHyp, LHyp1).


sort_tables([], []) :-
        !.

sort_tables([Tab|LTab], [Tab1|LTab1]) :-
        sort(Tab, Tab1),
        sort_tables(LTab, LTab1).   
   

       /* discard similar hypothesis */        
discard_doublets(LHyp, LHyp_out) :-
   sort_arguments(LHyp, LHyp1),
   discard_similar_hypotheses(LHyp1, LHyp_out).
   


discard_similar_hypotheses([], []) :-
        !.

discard_similar_hypotheses([(Id,H, LSeed) |L], L1) :-
        exists_a_similar_hypothesis( (Id, H, LSeed),L),
        !,
        discard_hypothesis(Id),
        discard_similar_hypotheses(L, L1).

discard_similar_hypotheses([H|L], [H|L1]) :-
        discard_similar_hypotheses(L, L1).
        
       

                        /* verifie que L contient un element similaire a X */
exists_a_similar_hypothesis(_, [], _) :-
        !,
        fail.

exists_a_similar_hypothesis(H1, [H2|_]) :-
        similar_hypotheses(H1,H2),
        !.

exists_a_similar_hypothesis(H, [_|L]) :-
        exists_a_similar_hypothesis(H, L).


        /* two hypothesis + seeds are similar if they are similar and their seeds are 
           similar */
similar_hypotheses((_, [Hyp1, Hypa1], LSeed1), (_, [Hyp2, Hypa2], LSeed2)) :-
         
         T1 = t(Hyp1, Hypa1, LSeed1),  
         duplicate_term(T1, TA),
         numbervars(TA, 0, _, [functor_name('$$var')]),
         TA = t(HypX1, HypaX1, LSeedX1), 
         
         T2 = t(Hyp2, Hypa2, LSeed2),  
         duplicate_term(T2, TB),
         numbervars(TB, 0, _, [functor_name('$$var')]),
         TB = t(HypX2, HypaX2, LSeedX2),

         similar_terms(HypX1, HypX2),
         similar_terms(HypaX1, HypaX2),

         similar_seeds(LSeedX1, LSeedX2).
        

similar_seeds([], []) :-
   !.
        
similar_seeds([Tab1|LTab1], [Tab2|LTab2]) :-
   similar_tables(Tab1, Tab2),
   similar_seeds(LTab1, LTab2).


similar_tables([], []) :-
   !.
        
similar_tables([Pos1|LPos1], [Pos2|LPos2]) :-
   similar_possibilities(Pos1, Pos2),
   similar_tables(LPos1, LPos2).


similar_possibilities(Pos1, Pos2) :-
   sort(Pos1, Pos),
   sort(Pos2, Pos).

        
discard_hypothesis(Indice) :- 
   learn:recorded(Indice, _, Reference),
   learn:erase(Reference).            


/* ================================ END OF LISTING ========================== */
