/* ===================================================================== */
/*                              AQa UTILITIES                            */
/* ===================================================================== */     


:- dynamic ex_bk:arff_type/1, ex_bk:train_test_validation/0.
                                                             
/* ===================================================================== */
/*                              ARFF FILES HANDLING                      */
/* ===================================================================== */     

/*         create_arff_neg(File_name) :

                1) read a ARFF file named File_name.arff (ARFF) containing 
                  with boolean attributs having three possible values {0,1,?},
                  where ? represents the value "unknown". 
                  each value ? two new interpretations : one with value 0, this
                  other one with value 1.
                
                2) for each attribute a, creates an attribute not_a representing
                   the negation of a.
                  
                3) creates a file File_name.bkg (background knowlege) 
                   containing :
                   a) for each attribute att the two clauses :
                      false :- a, not_a    % a and not_a cannot be both true
                      or([a, not_a]).      % a and not_a cannot be both false
                   b) clauses needed for AQa  
                   
                4) creates a new ARFF file containing attributes, their negation
                   and associated values.
*/
   
 
	/* convert an arff file containing ambiguous examples in a complete one */
	/* by replacing each ? by 0 */
ambiguous_to_complete(File_name) :-
    atom_concat(File_name, '.arff', Arff_file),    % data file
    open(Arff_file, read, In),
                     							    % complete arff file
    atom_concat('c', Arff_file, Arff_out1),
    open(Arff_out1, write, Out),
        
    read_line(In, Relation),
    write_line(Out, Relation),     
    
    get_attributes(In, LAttributes, LDomains),
    write_arff_attributes(In, Out, LAttributes, LDomains),
        
                % writing line @data
    string_to_list(SData, "@data"),                                                                                             
    write_line(Out,SData),
        
    write_complete_data(In, Out),                   % writing examples
        
    close(In),
    close(Out).
           

write_complete_data(In, Out) :-
        read_line(In, Line),
        !,
        get_values(Line, LValues),
        last(LValues, Class),
        delete_last_element(LValues, LValues1),      
        complete_values(LValues1, LValues2),
        append(LValues2, [Class], LValues3),
        convert_list_to_string(LValues3, Line1),
        write_line(Out, Line1),
        write_complete_data(In, Out).
                        
write_complete_data(_, _).


complete_values([], []) :-
   !.
   
complete_values([?|LValues], [0|LValues1]) :-
   !,
   complete_values(LValues, LValues1).
   
complete_values([V|LValues], [V|LValues1]) :-
   complete_values(LValues, LValues1).   
   
   
   /* create a file with positive and negative atoms */ 
create_arff_neg2(File_name) :-
        atom_concat(File_name, '.arff', Arff_file),    % data file
        open(Arff_file, read, In),
        read_line(In, Relation),
        get_attributes(In, LPos_attributes, LDomains),
        append(LPos_attributes1, [Class], LPos_attributes),
        append(LDomains1, [Class_domain], LDomains),
        build_neg_attributes(LPos_attributes1, LNeg_attributes),
        create_new_arff_file(In, File_name, Relation, Class, Class_domain,
                             LPos_attributes1, LNeg_attributes, LDomains1),
        close(In),
        !.
        
        
create_arff_neg(File_name) :-
        writeln(File_name),
        atom_concat(File_name, '.arff', Arff_file),    % data file
        open(Arff_file, read, In),
        read_line(In, Relation),
        get_attributes(In, LPos_attributes, LDomains),
        append(LPos_attributes1, [Class], LPos_attributes), 
        append(LDomains1, [Class_domain], LDomains),
        create_background_neg_file(File_name, LPos_attributes1, LNeg_attributes),
        create_new_arff_file(In, File_name, Relation, Class, Class_domain,
                             LPos_attributes1, LNeg_attributes, LDomains1),
        close(In),
        !.


create_background_neg_file(File_name, LPos_attributes, LNeg_attributes) :-
        atom_concat(File_name, '_neg.bkg', Background_file),    
        open(Background_file, write, Out),
        write_term_file(Out, loaded_background),
        nl(Out),
        write_term_file(Out, constants([])),
        nl(Out),
        write_term_file(Out, constants_oi([])),
        nl(Out),
        write_term_file(Out, oi([])),
        nl(Out),
        build_neg_attributes(LPos_attributes, LNeg_attributes),
        build_constraints_attributes(LPos_attributes, LNeg_attributes, 
                                     Tab_constraints, Tab_attributes),
        append(LPos_attributes, LNeg_attributes, LAttributes),
        write_attributes_background(Out, LAttributes),
        write_term_file(Out, tables_constraints(Tab_constraints)),
        nl(Out),
        write_term_file(Out, tables_attributes(Tab_attributes)),
        nl(Out),
        length(Tab_constraints, N),
        write_term_file(Out, nb_tables(N)),
        nl(Out),
        append(LPos_attributes, LNeg_attributes, LAttributes),
        write_term_file(Out, attributes(LAttributes)),
        close(Out).
     
     
build_neg_attributes([], []) :-
   !.
     
build_neg_attributes( [A|LA], [NegA|LNegA]) :-
        atom_concat(not_, A, NegA),
        build_neg_attributes(LA, LNegA).
   
   
build_constraints_attributes([], [], [], []) :-
        !.

build_constraints_attributes([A|LA], [NegA|LNegA], 
                            [[False, Or]|LConstraints],
                            [[A, NegA]|LAttributes]) :-
        atom_concat(not_, A, NegA), 
        False = (false :- A, NegA),
        Or = or([A, NegA]),
        build_constraints_attributes(LA, LNegA, LConstraints, LAttributes).        
   
                 
write_attributes_background(Out, LA) :-
        constitute_predicates(LA, LPredicates),
        constitute_dynamic(LA, Dynamic),
        Term_dynamic = (:- dynamic Dynamic), 
        write_term_file(Out, Term_dynamic),
        nl(Out),
        write_term_file(Out, predicates(LPredicates)),
        nl(Out).
        

create_new_arff_file(In, File_name, Relation, Class, Class_domain,
                     LPos_attributes, LNeg_attributes, LDomains) :-
                     
                     % create new arff file
        atom_concat(File_name, '_neg.arff', Arff_file),
        open(Arff_file, write, Out),
        
        write_line(Out, Relation),                   % relation line,
        
                % writing attributes lines
        append(LPos_attributes, LNeg_attributes, LAttributes),
        append(LAttributes, [Class], LAttributes1),
        append(LDomains, LDomains, LDomains2),       % add domains for negated
                % attributes.
        append(LDomains2, [Class_domain], LDomains1),
        write_arff_attributes(In, Out, LAttributes1, LDomains1),
        
                % writing line @data
        string_to_list(SData, "@data"),                                                                                             
        write_line(Out,SData),
        
        write_arff_data(In, Out),                   % writing examples
        close(Out).
        

write_arff_data(In, Out) :-
        read_line(In, Line),
        get_values(Line, LValues),
        append(LValues1, [Class], LValues),          % select class
        inverse_values(LValues1, LValues2),
        append(LValues1, LValues2, LValues3),
        append(LValues3, [Class], LValues4),
        convert_list_to_string(LValues4, Line1),
        write_line(Out, Line1),
        write_arff_data(In, Out).
                        
write_arff_data(_, _).

inverse_values([], []) :-
        !.
        
inverse_values([1|LV], [0|LV1]) :-
        !,
        inverse_values(LV, LV1).
        
inverse_values([0|LV], [1|LV1]) :-
        !,
        inverse_values(LV, LV1).

inverse_values([V|LV], [V|LV1]) :-
        inverse_values(LV, LV1).        
        

write_arff_attributes(_, _, [], []) :-
        !.
        
write_arff_attributes(In, Out, [A|LA], [Domain|LDomains]) :-
        atom_concat('@attribute ', A, Attribute), 
        string_to_atom(Domain, ADomain),
        atom_concat(Attribute, ' ', Attribute1),
        atom_concat(Attribute1, ADomain, Line),
        write_line(Out, Line),
        write_arff_attributes(In, Out, LA, LDomains).
                      
        
constitute_predicates([], []) :-
        !.
        
constitute_predicates([A|LA],[(A,0)|LPA]) :-
        constitute_predicates(LA, LPA).
        
        
constitute_dynamic([A], A/0) :-
        !.
        
constitute_dynamic([A|LA], ','(A/0, DLA)) :-
        constitute_dynamic(LA, DLA).
        
        
/*      read_arff(File_name) :
        1) Lit :
             un fichier Nom_file.arff (ARFF) avec attributs booleens.
             valeurs possibles d''attribut {0,1,?},
             Chaque ? cree 2 nouvelles possibilites d''exemples.
             valeurs possibles de la classe {neg, pos}
        2) un fichier Nom_file.bkg (background knowlege contenant des clauses
           Prolog (y compris clauses false et or).
                   
        Construit les interpretations positives maximales, et negatives
        minimales, qui satisfont la theorie du domaine
*/
                
read_arff_neg_test(File_name) :-
        ex_bk:assert(arff_neg_file_for_test),
        read_arff_neg(File_name),
        ex_bk:retract(arff_neg_file_for_test).
        
        
read_arff_neg(File_name) :-
        ex_bk:assert(arff_type(arff_neg)),
        read_arff(File_name),
        ex_bk:retract(arff_type(_)).
        
        
read_arff(File_name) :-
        atom_concat(File_name, '.arff', Arff_file),
        atom_concat(File_name, '.bkg', Background_file),
        ex_bk:consult(Background_file),
        ex_bk:assert(background_loaded),
        open(Arff_file, read, In),
        read_line(In, _Relation),
        get_attributes(In, LAttributes, _LDomains),
        delete_last_element(LAttributes, LAttributes1),
        get_examples(0, In, LAttributes1, LExP, LExN),
        close(In),
        atom_concat(File_name, '.pl', Examples_file), % examples file
        open(Examples_file, write, Out),
        write_examples(Out, LExP, LExN),
        close(Out).
         
/* ========================================================================== */
/*                           MULTIPLE TABLES HANDLING                         */
/* ========================================================================== */
                
create_files_neg(File_train, File_test) :-
        create_arff_neg(File_train),
        create_arff_neg(File_test),
        writeln('Files with double representation and background files created'),
        !.

arff_neg_to_prolog(File_train, File_test) :-
        atom_concat(File_train, '_neg', File_train_neg),
        atom_concat(File_test, '_neg', File_test_neg),
        arff_to_prolog(File_train_neg, train),
        arff_to_prolog(File_test_neg, test).
        
       
   /* read an arff file and the correspond .bkg file and buile
      an equivalent prolog file */
   /* modif 2/09/11, ajout argument File_bkg */
arff_to_prolog(File, Background_file, Mode) :-
       
                        % read arff file
        atom_concat(File, '.arff', Arff_file),
        open(Arff_file, read, In),
        read_line(In, _Relation),
        get_attributes(In, _LAttribute, _LDomain),
        get_examples_arff(In, LEx),
        close(In),
        
        (
         ex_bk:train_test_validation
           -> true
           ;
           (
             atom_concat(Background_file, '.bkg', File_bkg),
             ex_bk:consult(File_bkg)
           )
        ),
        
                     
                        % write prolog file
        atom_concat(File, '.pl', Examples_file),
        open(Examples_file, write, Out),
        examples_to_tables(LEx, LTable_Lex, LTable_att),
        ex_bk:tables_constraints(LTable_constr),
        build_ambiguous_tab_examples(LTable_Lex, LTable_att, LTable_constr,
                                     LEx_posA, LEx_negA), 
        check_mode(Mode),
        write_examples(Out, LEx_posA, LEx_negA),
        close(Out),
        writeln('end of building prolog examples'),
        !.
     
check_mode(test) :-
   ex_bk:asserta(test),
   !.
   
check_mode(_).
       
write_examples_prolog(_Out, []) :-
   !.

write_examples_prolog(Out, [Ex|LEx]) :-
   write_term_file(Out, example(Ex)),
   write_examples_prolog(Out, LEx).


build_ambiguous_tab_examples([], _LTable, _LTab_constr, [], []) :-
   !.

build_ambiguous_tab_examples([(Class, LTab_ex)|LTable_Lex], LTable_att,
                             LTab_constr, LEx_posA, LEx_negA) :-
     build_tab_attributes(LTab_ex, LTable_att, LTab_true, LTab_uncertain),
     build_ambiguous_tab_one_example(Class, LTab_constr,
                                     LTab_true, LTab_uncertain, LTab_exA),
     build_ambiguous_tab_examples(LTable_Lex, LTable_att, LTab_constr,
                                  LEx_posA1, LEx_negA1),
     place_example(Class, LTab_exA, LEx_posA1, LEx_negA1, LEx_posA, LEx_negA).


build_ambiguous_tab_one_example(_Class, _LConstr, [], [], []) :-
   !.

build_ambiguous_tab_one_example(
                                 Class,
                                 [Tab_constr|LTab_constr],
                                 [Tab_true|LTab_true],
                                 [Tab_uncertain|LTab_uncertain],
                                 [Tab_exA |LTab_exA]
                                ) :-
   inserer_dans_base(Tab_constr),
   build_ambiguous_example(Class, Tab_true, Tab_uncertain, Tab_exA),
   enlever_de_base(Tab_constr),
   build_ambiguous_tab_one_example(Class, LTab_constr,
                                   LTab_true, LTab_uncertain, LTab_exA).

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

build_tab_attributes([Tab_ex|LTab_ex], [Tab_att|LTab_att],
                     [Tab_true|LTab_true], [Tab_uncertain|LTab_uncertain]) :-
   identify_uncertain_attributes(Tab_ex, Tab_att, Tab_true, Tab_uncertain),
   build_tab_attributes(LTab_ex, LTab_att, LTab_true, LTab_uncertain).


examples_to_tables(LEx, LTable_Lex, LTable_attribute) :-
   ex_bk:tables_attributes(LTable_attribute),
   ex_bk:attributes(LAttribute),
   build_attributes_positions(LTable_attribute, LAttribute, LTable_pos),
   build_tables_ex(LEx, LTable_pos, LTable_Lex).
   
   
build_tables_ex([], _LTables_pos, []) :-
   !.
   
build_tables_ex([Ex|LEx], LTable_pos, [(Class, LTab_ex)|LTab_Lex]) :-
   build_tables_one_ex(LTable_pos, Ex, LTab_ex),
   last(Ex, Class),
   build_tables_ex(LEx, LTable_pos, LTab_Lex).


build_tables_one_ex([], _LValues, []) :-
   !.

build_tables_one_ex([Tab_pos|LTab_pos], LValues, [Tab_ex|LTab_ex]) :-
   build_one_table_one_ex(Tab_pos, LValues, Tab_ex),
   build_tables_one_ex(LTab_pos, LValues, LTab_ex).
   
   
build_one_table_one_ex([], _LValues, []) :-
   !.
   
build_one_table_one_ex([Pos|LPos], LValues, [Value|LValues_tab]) :-
   nth1(Pos, LValues, Value),
   build_one_table_one_ex(LPos, LValues, LValues_tab).


build_attributes_positions([], _, []) :-
   !.
   
build_attributes_positions([Table|LTable], LAttribute,
                           [Table_positions|LTable_positions]) :-
    build_positions(Table, LAttribute, Table_positions),
    build_attributes_positions(LTable, LAttribute, LTable_positions).
    

build_positions([], _ , []) :-
   !.
    
build_positions([Att|LAtt], LAttribute, [Pos|LPos]) :-
   nth1(Pos, LAttribute, Att),
   build_positions(LAtt, LAttribute, LPos).

get_examples_arff(In, [Ex|LEx]) :-
        read_line(In, Line),
        !,
        % writeln(Line),
        % nl,
        get_values(Line, Ex),
        get_examples_arff(In, LEx).

get_examples_arff(_In, []).


/* -------------------------------------------------------------------------- */
        
write_examples(Out, LExP, LExN) :-
        ex_bk:retract(test),
        !,
        write_term_file(Out, loaded_examples_test),
        write_term_file(Out,examplesP_test(LExP)),
        write_term_file(Out,examplesN_test(LExN)).
        
write_examples(Out, LExP, LExN) :-
        write_term_file(Out, loaded_examples),
        write_term_file(Out,examplesP(LExP)),
        write_term_file(Out,examplesN(LExN)).   
        
        
write_term_file(Out, Term) :-
        write(Out, Term),
        write(Out, '.'),
        nl(Out).
        

read_line(In, Ligne) :-
        read_line_to_codes(In, Codes),
        \+ end_of_file(Codes),
        string_to_list(Ligne, Codes).
        
        
write_line(Out, Ligne) :-
        write(Out, Ligne),
        nl(Out).
        
        
end_of_file(end_of_file) :-
        !.
        
end_of_file(_) :-
        fail.
        
        /* gestion des exemples */
get_examples(N, In, LAttributes, LExP, LExN) :-
        read_line(In, Line),
        !,
        writeln(N),
        writeln(Line),
        nl,
        traite_ligne_exemple(Line, LAttributes, ExpA, Class),   
        N1 is N+1,
        get_examples(N1,In, LAttributes, LExPos, LExNeg),
        place_example(Class, ExpA, LExPos, LExNeg, LExP, LExN).
        
get_examples(_, _, _, [], []).  % found "end of file"   
                

place_example(_, [], LExPos, LExNeg, LExPos, LExNeg) :-
        !.

place_example(pos, ExpA, LExPos, LExNeg, [ExpA|LExPos], LExNeg) :-
        !.
        
place_example(neg, ExpA, LExPos, LExNeg, LExPos, [ExpA|LExNeg]).        
        
 
traite_ligne_exemple(Ligne, LAttributes, ExpA, Class) :-
        get_values(Ligne, LValues),
        append(LValues1, [Class], LValues),
        identify_uncertain_attributes(
                                       LValues1,
                                       LAttributes, 
                                       LAtt_true,
                                       LAttributes_uncertain
                                      ),                                      
        build_ambiguous_example(Class, LAtt_true, LAttributes_uncertain, ExpA).
        

identify_uncertain_attributes([],[],[], []) :-
        !.
        
identify_uncertain_attributes(
                              [1|LValeurs],
                              [A|LAttributes],
                              [A|LAttributes_true],
                              LAttributes_uncertain
                              ) :-
        !,                                               
    identify_uncertain_attributes(
                                  LValeurs,
                                  LAttributes,
                                  LAttributes_true,
                                  LAttributes_uncertain
                                  ).
                                                                  
identify_uncertain_attributes(
                               [0|LValeurs],
                               [_|LAttributes],
                               LAttributes_true,
                               LAttributes_uncertain
                             ) :-
        !,                                               
    identify_uncertain_attributes(
                                  LValeurs,
                                  LAttributes,
                                  LAttributes_true,
                                  LAttributes_uncertain
                                 ).
                                                                  
identify_uncertain_attributes(
                              [?|LValeurs],
                              [A|LAttributes],
                              LAttributes_true,
                              [A|LAttributes_uncertain]
                             ) :-
    identify_uncertain_attributes(
                                  LValeurs,
                                  LAttributes,
                                  LAttributes_true,
                                  LAttributes_uncertain
                                 ).
                                                                  
/* ==================================================================== */
/*      BUILDING AMBIGUOUS EXAMPLES (SET OF VALID INTERPRETATIONS)      */
/* ==================================================================== */      

build_ambiguous_example(_Class, LTrue, LAttributes_uncertain, ExpA) :-
        ex_bk:arff_type(arff_neg),
        !,
        separate_pos_neg_attributes(LAttributes_uncertain, LPos_att, LNeg_att),
        build_pairs_pos_neg(LPos_att, LNeg_att, LPairs),
        findall(I, arff_neg_interpretation(LPairs, I), LI),     
        append_list_to_lists(LTrue, LI, ExpA).

build_ambiguous_example(pos, LTrue, LAttributes_uncertain, ExpA) :-
           !,
           build_ambiguous_positive_example(LTrue, LAttributes_uncertain, ExpA).
                                                                                
build_ambiguous_example(neg, LTrue, LAttributes_uncertain, ExpA) :-
        !,
        build_ambiguous_negative_example(LTrue, LAttributes_uncertain, ExpA).

        
arff_neg_interpretation([], []) :-
        !.
        
arff_neg_interpretation([Pair|LPairs], [Att|I]) :-
        member(Att, Pair),
        arff_neg_interpretation(LPairs, I).
        
        
build_pairs_pos_neg([], [], []) :-
        !.
        
build_pairs_pos_neg([A_pos|LPos], [A_neg|LNeg], [[A_pos,A_neg]| LPairs]) :-
        build_pairs_pos_neg(LPos, LNeg, LPairs).
                
        % case where there is no uncertain attribute
separate_pos_neg_attributes([], [], []) :-
        !.
        
separate_pos_neg_attributes([A|LA], [], [A|LA]) :-
        atom_concat('not_', _A1, A),                % first neg attribute found
        !.
        
separate_pos_neg_attributes([A|LA], [A|LPos], LNeg) :-
        separate_pos_neg_attributes(LA, LPos, LNeg).
        
          
build_ambiguous_positive_example(LTrue, LAttributes_uncertain, ExpA) :-
        inserer_dans_base(LTrue),
        maximal_valid_interpretations(LAttributes_uncertain, ExpA1),
        enlever_de_base(LTrue),
        append_list_to_lists(LTrue, ExpA1, ExpA).
        
                
build_ambiguous_negative_example(LTrue, LAttributes_uncertain,ExpA) :-
        inserer_dans_base(LTrue),
        minimal_valid_interpretations(LAttributes_uncertain, ExpA1),
        enlever_de_base(LTrue),
        append_list_to_lists(LTrue, ExpA1, ExpA).
        
/* =================== build the maximal valid intepretations =============== */

maximal_valid_interpretations(
      LA,     % list of remaining attributes
      [LA]    % list of maximal valid interpretations
                              ) :-
     valid_interpretation(LA),   % LA containing uncertain attributes is maximal
                                % and satisfies all constraints
        !.
        
        /* there is no uncertain attribute so max interpreation is empty.
          no possibility to shrink it */        
maximal_valid_interpretations([], []) :-
        !.
                
        /* current interpretation satisfies false constraints and 
                can be extended by adding attributes */ 
maximal_valid_interpretations(  
                               LA,      % available attributes
                               LMax     % maximal valid interpretations
                              ):-
        check_possible_and_maxima([], [LA], [], LMax).

        
check_possible_and_maxima(_Max_found, [], LMax, LMax) :-
        !.      % there is no more possible interpretations.
        
check_possible_and_maxima(_Max_found, [[]], LMax, LMax) :-
        !.      % one cannot reduce empty interpretation []
        
check_possible_and_maxima(Max_found, LPossible_N, LMax_N, LMax) :-
        build_maximal_interpretations(Max_found, LPossible_N, LMax_N1),
        append(LMax_N1, LMax_N, LMax).
        

build_maximal_interpretations(_Max_found, [], _LMax) :-
        !.
        
build_maximal_interpretations(
                               Max_found,
                               LPos_N  ,       % possible int. of length N
                              LMax            % maximal  int. of length N
                                                         ) :-   
        dissociate_interpretations(LPos_N, LPos_N1A),
        discard_non_maximal_interpretations(LPos_N1A, Max_found, LPos_N1B),
        keep_possible_maxima(LPos_N1B, LPos_N1, LMax_N1),                                                
        append(Max_found, LMax_N1, Max_found1),
        check_possible_and_maxima(Max_found1, LPos_N1, LMax_N1, LMax).
        
                
discard_non_maximal_interpretations([], _LMax, []) :-
        !.
        
discard_non_maximal_interpretations([IP|LIP], LMax, LPos) :-
        has_superset(IP, LMax),
        !,
        discard_non_maximal_interpretations(LIP, LMax, LPos).
        
discard_non_maximal_interpretations([IP|LIP], LMax, [IP|LPos]) :-       
        discard_non_maximal_interpretations(LIP, LMax, LPos).
        
        
has_superset(L, [L1|_]) :-
        my_subset(L, L1),
        !.
        
has_superset(L, [_L1|LL]) :-
        has_superset(L, LL).
        
        /* built interpretations of lenght N-1 from interpretations of length N */
dissociate_interpretations([], []) :-
        !.

dissociate_interpretations([I|LI], LPos) :-
        dissociate_one_interpretation(I, LPos1), 
        dissociate_interpretations(LI, LPos2),
        append(LPos1, LPos2, LPos3),
        sort(LPos3, LPos).
        
        
dissociate_one_interpretation(I, LI) :-
                findall(I1, select(_X, I, I1), LI).
                
        
keep_possible_maxima([], [], []) :-
        !.
        
keep_possible_maxima([I|LI], LPos, LMax) :-
        check_maximal_interpretation(I, Code),
        keep_possible_maxima(LI, LPos1, LMax1),
        place_maximal_interpretation(Code, I, LPos1, LMax1, LPos, LMax).
        
        
place_maximal_interpretation(ok_base, I, LPos, LMax, LPos, [I|LMax]) :-
        !.

place_maximal_interpretation(ok_or, I, LPos, LMax, [I|LPos], LMax) :-
        !.      
        
place_maximal_interpretation(_, _, LPos, LMax, LPos, LMax).
                
        
/* ==================  build the minimal valid interpretations ============ */          
                                
minimal_valid_interpretations(
                   _LA,    % list of remaining attributes
                   [[]]    % list of minimal valid interpretations
                             ) :-
        base_ok,             % empty interpretation is valid
        !.
        
        /* no available attribute : empty interpretation cannot be extended */  
minimal_valid_interpretations([], []) :-
        !.
                
        /* empty interpretation satisfies false constraints and 
                can be extended by adding attributes */ 
minimal_valid_interpretations(  
        LA,     % available attributes
        LMin    % minimal valid interpretations
                              ):-
        minimal_interpretations_of_length1(LA, LPossible1, LMin1),
        check_possible_and_minima([], 1, LPossible1, LMin1, LMin).
        

check_possible_and_minima(_Min_found, _, [], LMin, LMin) :-
        !.
        
check_possible_and_minima(Min_found, N, LPossible_N1, LMin_N1, LMin) :-
        N1 is N+1,
        build_minimal_interpretations(Min_found, N1, LPossible_N1, LMin_N),
        append(LMin_N, LMin_N1, LMin).
        

build_minimal_interpretations(_, _, [], _LMin) :-
        !.
        
build_minimal_interpretations(
                                Min_found,
                                N,         % current length of interpretations
                                LP_N1,     % possible int. of length N-1
                                LMin       % minimal int. of length N
                               ) :-
        merge_all_interpretations(N, LP_N1, LP_NA),
        discard_non_minimal_interpretations(LP_NA, Min_found, LP_NB),   
        keep_possible_minima(LP_NB, LP_N, LMin_N),
        append(Min_found, LMin_N, Min_found1),
        check_possible_and_minima(Min_found1, N, LP_N, LMin_N, LMin).
        
        
minimal_interpretations_of_length1([], [], []) :-
        !.

minimal_interpretations_of_length1([A|LA], LPossible, [[A]|LMinimal]) :-
        valid_interpretation([A]),
        !,
        minimal_interpretations_of_length1(LA, LPossible, LMinimal).
        
minimal_interpretations_of_length1([A|LA], [[A]|LPossible], LMinimal) :-
        interpretation_ok_for_false([A]),
        !,
        minimal_interpretations_of_length1(LA, LPossible, LMinimal).    
        
minimal_interpretations_of_length1([_A|LA], LPossible, LMinimal) :-
        minimal_interpretations_of_length1(LA, LPossible, LMinimal).    
                
        
discard_non_minimal_interpretations([], _LMin, []) :-
        !.
        
discard_non_minimal_interpretations([IP|LIP], LMin, LPos) :-
        has_subset(IP, LMin),
        !,
        discard_non_minimal_interpretations(LIP, LMin, LPos).
        
discard_non_minimal_interpretations([IP|LIP], LMin, [IP|LPos]) :-       
        discard_non_minimal_interpretations(LIP, LMin, LPos).
        
        
has_subset(L, [L1|_]) :-
        my_subset(L1, L),
        !.
        
has_subset(L, [_L1|LL]) :-
        has_subset(L, LL).

        
merge_all_interpretations(_N, [], []) :-
        !.

merge_all_interpretations(N, [I|LI], LLI) :-
        merge_interpretations(N, I, LI, LLI1),
        merge_all_interpretations(N, LI, LLI2),
        append(LLI1, LLI2, LLI3),
        sort(LLI3, LLI).
        

merge_interpretations(_N, _I, [], []) :-
        !.

merge_interpretations(N, I, [I1|LI], [IMerged|LIMerged]) :-
        merge_two_interpretations(N, I, I1, IMerged),
        !,
        merge_interpretations(N, I, LI, LIMerged).

        
merge_interpretations(N, I, [_I1|LI], LIMerged) :-
        merge_interpretations(N, I, LI, LIMerged).
        
        
merge_two_interpretations(N, I1, I2, IMerged) :-
        append(I1, I2, I3),
        sort(I3, IMerged),
        length(IMerged, N).
        
        
keep_possible_minima([], [], []) :-
        !.
        
keep_possible_minima([I|LI], LPos, LMin) :-
        check_minimal_interpretation(I, Code),
        keep_possible_minima(LI, LPos1, LMin1),
        place_minimal_interpretation(Code, I, LPos1, LMin1, LPos, LMin).
        
        
place_minimal_interpretation(ok_base, I, LPos, LMin, LPos, [I|LMin]) :-
        !.

place_minimal_interpretation(ok_false, I, LPos, LMin, [I|LPos], LMin) :-
        !.      
        
place_minimal_interpretation(_, _, LPos, LMin, LPos, LMin).
                
/* ==================================================================== */
/*                       ARFF ATTRIBUTES HANDLING                       */
/* ==================================================================== */
        
get_attributes(In, LAttributes, LDomains):-     
        read_line(In, Line),
        !,
        traite_ligne_attribut(In, Line, LAttributes, LDomains).
        
get_attributes(_, [], []).   % si fin de fichier rencontre      
        

traite_ligne_attribut(_, Line, [], []) :-
        code_data(Line),
        !.

traite_ligne_attribut(In, Ligne, [Attribute|LAttributes], 
                                          [Domain|LDomains]) :- 
        ligne_attribut(Ligne, Attribute, Domain),
        !,
        get_attributes(In, LAttributes, LDomains).
        
        
ligne_attribut(Line, Attribute, Domain) :- 
        code_attribut(Code_attribute),
        string_length(Code_attribute,N),
        Nm1 is N-1,
        prefix(Line, Nm1, Code_attribute), 
        Np1 is N+1,
        suffix(Line, Np1, After),
        recupere_attribut(After, Attribute1, Domain),
        retire_espaces(Attribute1, Attribute).
        
        
recupere_attribut(String, Attribute, Domain) :- 
        accolade_ouvrante(Accolade_ouvrante),
        sub_string(String, K, 1, _, Accolade_ouvrante),
        K1 is K-1, 
        sous_chaine(String, 0, K1, Attribute),
        suffix(String, K, Domain).
                
        
traite_ligne_classe(Ligne, Valeurs_classe) :-
        accolade_ouvrante(Accolade_ouvrante),
        accolade_fermante(Accolade_fermante),
        sub_string(Ligne, Debut, 1, _, Accolade_ouvrante),
        sub_string(Ligne, Fin, 1, _, Accolade_fermante),
        Debut1 is Debut + 1,
        Fin1 is Fin - 1,
        Longueur is Fin1 - Debut1 + 1,
        sub_string(Ligne, Debut1, Longueur, _, String),
        get_values(String, Valeurs_classe).
        
        
get_values(String, [Valeur]) :-
        virgule(Virgule),
        \+ sub_string(String, _, 1, _,Virgule),
        !,
        retire_espaces(String, Valeur).

        
get_values(String, [Valeur|LValeurs]) :-
        virgule(Virgule),
        sub_string(String, Deb, 1, _,Virgule),
        !,
        Deb1 is Deb-1,
        prefix(String, Deb1, SValeur),
        retire_espaces(SValeur, Valeur),
        Debp1 is Deb+1,
        suffix(String, Debp1,Reste),
        get_values(Reste, LValeurs).
        
        
retire_espaces(SValeur, Valeur) :-
        espace(Espace),
        retire_espaces_avant(Espace, SValeur, SValeur1),
        retire_espaces_apres(Espace,SValeur1, SValeur2),
        string_to_atom(SValeur2, Valeur1),
        check_value(Valeur1, Valeur).
                
check_value(Value_in, Value_out) :-
   catch(atom_number(Value_in, Value_out), _E, fail),
   !.
   
check_value(Valeur, Valeur).   
                
        
retire_espaces_avant(Espace, SValeur, SValeur) :-
        \+ sub_string(SValeur, 0, 1, _, Espace),
        !.
        
retire_espaces_avant(Espace, SValeur, SValeur2) :-
        sub_string(SValeur, 0, 1, _, Espace),
        string_length(SValeur, N),
        N1 is N -1,
        sub_string(SValeur, 1, N1, _, SValeur1),
        retire_espaces_avant(Espace, SValeur1, SValeur2).       
        
        
retire_espaces_apres(Espace, SValeur, SValeur) :-
        string_length(SValeur, N),
        N1 is N-1,
        \+sub_string(SValeur, N1, 1, _, Espace),
        !.
        
retire_espaces_apres(Espace, SValeur, SValeur2) :-
        string_length(SValeur, N),
        N1 is N-1,
        sub_string(SValeur, N1, 1, _, Espace),
        sub_string(SValeur,0, N1, _, SValeur1), 
        retire_espaces_apres(Espace, SValeur1, SValeur2).               

/* ======================================================================= */
/*                              MISCELLENAOUS                              */
/* ======================================================================= */      
       

enumerate_numbers(1, [1]) :-
   !.

enumerate_numbers(N, L) :-
   N1 is N - 1,
   enumerate_numbers(N1, L1),
   append(L1, [N], L).

                
/* ======================================================================= */
/*                              DISPLAY                                    */
/* ======================================================================= */      

effacer :-
        shell('clear').
        
newline :-
        nl.
        
println(T) :-
        print(T),
        nl.
        
                /* affiche Terme avec renommage des variables */
display_term(Term) :-
        copy_term(Term, T),
        numbervars(T, 0, _),            
        write_term(T, [numbervars(true)]).
        
display_nl(Term) :-
        display_term(Term),
        nl.
        
                        /* affiche une liste, chaque element a la ligne */
display_list([]) :-
        !.
        
display_list([X]) :-
   display_term(X),
   !.
        
display_list([X|L]) :-
        display_term(X),
        write(','),
        display_list(L).
        
        
get_increment(4).       /* increment initial */

get_indentation(0).     /* indentation initiale */


indenter :-
        retract(get_indentation(N)),
        get_increment(I),
        N1 is (N + I),
        asserta(get_indentation(N1)).
        
desindenter :-
        retract(get_indentation(N)),
        get_increment(I),
        N1 is N - I,
        asserta(get_indentation(N1)).
        
variabilize_term(Term, Term1) :-                     
        Term  =..[Functor|LArgs],
        length(LArgs, N),
        length(LArgs1, N),
        Term1 =..[Functor|LArgs1].     
        
/* ========================================================================  */
/*                              LISTS HANDLING                               */
/* ========================================================================  */              

empty([]).

insert_nth(1, X, L, [X|L]) :-
   !.
   
insert_nth(N, X, [Y|L], [Y|L1]) :-
   N1 is N-1,
   insert_nth(N1, X, L, L1).


select_nth(1, [X|L], X, L) :-
   !.
   
select_nth(N, [Y|L], X, [Y|L1]) :-
   N1 is N-1,
   select_nth(N1, L, X, L1).


substitute_nth(1, X, [_|L], [X|L]) :-
   !.

        /* substitute the Nth elements of L by X and returns L_out */
substitute_nth(N, X, [Y|L], [Y|L1]) :-
   N1 is N-1,
   substitute_nth(N1, X, L, L1).


                % LSub_list is the sublist of List made of elements from
                % Deb to End
select_deb_end(List, Deb, End, LSub_list, LRemaining_list) :-
        N1 is Deb-1,
        prefix_list(N1, List, LPrefix),
        append(LPrefix, L, List),
        N2 is End-Deb + 1,
        prefix_list(N2, L, LSub_list),
        append(LSub_list, LSuffix, L),
        append(LPrefix, LSuffix, LRemaining_list).
        
        
prefix_list(0, _L, []) :-
        !.
        
prefix_list(N, [X|L], [X|LPref]) :-
        N1 is N-1,
        prefix_list(N1, L, LPref).


product_list_with_list([], LL, LL) :-
        !.

product_list_with_list([X|L], LL, LLout) :-
        product_list_with_list(L, LL, LL1),
        add_element_to_lists(X, LL1, LLout).

        
append_list_to_lists(_, [], []) :-
        !.
        
append_list_to_lists(L, [L1|LL1], [L2|LL2]) :-
        append(L, L1, L2),
        append_list_to_lists(L, LL1, LL2).


add_element_to_lists(_X, [], []) :-
        !.

add_element_to_lists(X, [L|LL], [[X|L]|LL1]) :-
        add_element_to_lists(X, LL, LL1).
        

convert_list_to_string(L, String) :-
        concat_atoms(L, Atoms),
        string_to_atom(String, Atoms). 
        

concat_atoms([A], A) :-
        !.
        
concat_atoms([A|LA], A1) :-
        concat_atoms(LA, A2),
        atom_concat(A, ',', Atom),
        atom_concat(Atom, A2, A1).

        /* ajoute Element a chaque liste de LL */
        
ajoute_element_listes(_, [], []) :-
        !.
        
ajoute_element_listes(Element, [L|LL], [[Element|L]|LL1]) :-
        ajoute_element_listes(Element, LL, LL1). 

                        /* transforme la liste de listes LL en une liste L */
flat_liste([], []) :-
        !.

flat_liste([L1|LL],L) :-
        flat_liste(LL,L2),
        append(L1,L2,L).        
        
                        /* retire le second composant de chaque doublet */
retirer_deuxieme_composant([], []) :-
        !.

retirer_deuxieme_composant([(A,_)|LC], [A|L]) :-
                retirer_deuxieme_composant(LC, L).      

/* ------------- LIST HANDLING USING A SIMILARITY RELATION ---------------- */

        /* vrai si les termes de L1 forment un shema relationel qui est 
            present dans L2 (au nom des variables pres) */
            
subsumes_list_OI(L1, L2) :-
        sort(L1, LA),
        sort(L2, LB),
        subsomption_list_OI(LA, LB).
        
subsumption_list_OI(LA, LB) :-    % LA and LB are structurally equal
   LA =@= LB,
   !.
   
subsumption_list_OI(LA, LB) :-
        copy_term(LA, LX),
        copy_term(LB, LY),
        occurrence_list_included(LX, LY, LZ1),   % LZ1 is an occurrence of LA in LB...
        length(LA, NA),                             
        length(LZ1, NZ),
        NA < NZ,                                 % ...greater than LA.
        sort(LZ1, LZ),
        subsumes_chk(LA, LZ),
        !.                                       % Discards leaving choice points.
        
        
occurrence_list_included([], _, []) :-
   !.
        
occurrence_list_included([X|L], L1, [X|L2]) :-
        selectchk(X, L1, LA),
        occurrence_list_included(L, LA, L2).

            
        /* verifie la similarite de 2 listes aux noms des variables pres */
listes_similaires(L1, L2, Similarite) :-
        liste_incluse(L1, L2, Similarite),
        liste_incluse(L2, L1, Similarite).
        
        
                /* verifie que L est incluse dans au moins une liste de LL */
inclus_dans_une_liste(_, [], _) :-
        !,
        fail.
        
inclus_dans_une_liste(L, [L1|_], Similarite) :-
        liste_incluse(L, L1, Similarite),
        !.

inclus_dans_une_liste(L, [_|LL], Similarite) :-
        inclus_dans_une_liste(L, LL, Similarite).
        
        
        /* verifie que L contient au moins une liste de LL */
inclut_une_liste(_, [], _) :-
        !,
        fail.
        
inclut_une_liste(L, [L1|_], Similarite) :-
        liste_incluse(L1, L, Similarite),
        !.

inclut_une_liste(L, [_|LL], Similarite) :-
        inclut_une_liste(L, LL, Similarite).    
        
        
                /* verifie que chaque element de L1 est similaire a au moins */
                /* un element de L2                                          */
liste_incluse([], _, _) :-
        !.

liste_incluse([X|L1], L2, Similarite) :-
        existe_un_element_similaire(X, L2, Similarite),
        liste_incluse(L1, L2, Similarite).      
        
        
position_premier_element_similaire(_, _, [], _, _) :-
        !,
        fail.
                
position_premier_element_similaire(X, PosR, [Y|_], Similarite, PosR) :-
        elements_similaires(X, Y, Similarite),
        !.
        
position_premier_element_similaire(X, Pos, [_|L], Similarite, PosR) :-
        Pos1 is Pos+1,
        position_premier_element_similaire(X, Pos1, L, Similarite, PosR).       
        
        
nb_occurrences(_, [], 0) :-
        !.
        
nb_occurrences(X, [X|L], N1) :-
        !,
        nb_occurrences(X, L, N),
        N1 is N+1.
        
nb_occurrences(X, [_|L], N) :-
        nb_occurrences(X,L,N).
                        
                        
sort_listes([], []) :-
        !.
        
sort_listes([L|LL], [L2|LL1]) :-
        copy_term(L, L1),
        sort(L1, L2),
        sort_listes(LL, LL1).
        
        
elements_similaires(X, Y, structurellement) :-
        !,
        X =@= Y.
        
elements_similaires(X, Y, strictement) :-
        !,
        X == Y.
                
elements_similaires(X, X, unification).         
        
        
                        /* verifie que L contient un element similaire a X */
existe_un_element_similaire(_, [], _) :-
        !,
        fail.

existe_un_element_similaire(X, [Y|_], Similarite) :-
        elements_similaires(X,Y, Similarite),
        !.

existe_un_element_similaire(X, [_|L], Similarite) :-
        existe_un_element_similaire(X, L, Similarite).
        
                /* ne conserve qu''une occurrence des elements similaires */
                /* de la liste L                                          */
retirer_elements_similaires([], [], _) :-
        !.

retirer_elements_similaires([X|L], L1, Similarite) :-
        existe_un_element_similaire(X,L,Similarite),
        !,
        retirer_elements_similaires(L, L1, Similarite).
        
retirer_elements_similaires([X|L], [X|L1],Similarite) :-
        retirer_elements_similaires(L, L1, Similarite). 
        
        
retirer_elements_similaires_element(_, [], [], _) :-
        !.
        
retirer_elements_similaires_element(X, [X1|L], L1, Similarite) :-
        elements_similaires(X, X1, Similarite),
        !,
        retirer_elements_similaires_element(X, L, L1, Similarite).
        
retirer_elements_similaires_element(X, [X1|L], [X1|L1], Similarite) :-
        retirer_elements_similaires_element(X, L, L1, Similarite).      
        
        /* vrai si L contient plusieurs occurrences similaires */
contient_des_occurrences_similaires([], _) :-
        !,
        fail.
        
        /* vrai si L contient plusieurs occurrences similaires */
contient_des_occurrences_similaires([X|L], Similarite) :-
        existe_un_element_similaire(X, L, Similarite),
        !.
        
        /* vrai si L contient plusieurs occurrences similaires */
contient_des_occurrences_similaires([_|L], Similarite) :-
        contient_des_occurrences_similaires(L, Similarite).


        /* vrai si L1 et L2 possedent des elements similaires */
contient_des_elements_similaires([], _, _) :-
        !,
        fail.
        
contient_des_elements_similaires([X|_], L2, Similarite) :-
        existe_un_element_similaire(X, L2, Similarite),
        !.
        
contient_des_elements_similaires([_|L1], L2, Similarite) :-
        contient_des_elements_similaires(L1, L2, Similarite).
                                

        /* dans LIn remplace Y par X, resultat dans LOut */
remplacer_terme(_, _, [], []) :-
        !.

remplacer_terme(X, Y, [T|LIn], [X|LOut]) :-
        T == Y,                % == a cause unification possible des variables
        !,
        remplacer_terme(X, Y, LIn, LOut).

        
remplacer_terme(X, Y, [T|LIn], [T|LOut]) :-
        remplacer_terme(X, Y, LIn, LOut).
        
        
nb_variables_distinctes(Terme, N) :-
        term_variables(Terme, LV),
        length(LV, N).
        
/* ========================================================================= */
/*                           STRINGS HANDLING                                */
/* ========================================================================= */      


virgule(V) :-
   string_to_list(V, ",").

accolade_ouvrante(A) :-
    string_to_list(A, "{").

accolade_fermante(A) :-
    string_to_list(A, "}").

code_data(C) :-
    string_to_list(C, "@data").


code_attribut(C) :-
    string_to_list(C, "@attribute").


nom_classe(N) :-
    string_to_list(N, "@class").


espace(E) :-
    string_to_list(E, " ").

        /* creation de strings utiles */

/* 
:- string_to_list(Virgule, ","), assert(virgule(Virgule)).
:- string_to_list(Accolade_ouvrante, "{"), 
   assert(accolade_ouvrante(Accolade_ouvrante)).
:- string_to_list(Accolade_fermante, "}"), 
   assert(accolade_fermante(Accolade_fermante)).
:- string_to_list(Data, "@data"), 
   assert(code_data(Data)).
:- string_to_list(Code_attribut, "@attribute"), 
   assert(code_attribut(Code_attribut)).
:- string_to_list(Nom_classe, "@Class"), 
   assert(nom_classe(Nom_classe)). 
:- string_to_list(Espace, " "), assert(espace(Espace)).   
*/


        /* retourne le suffixe de String commencant en position Deb */
suffix(String, Deb, S) :-
        string_length(String, N),
        Longueur is N-Deb,
        sub_string(String, Deb, Longueur, _, S).
        
        
        /* retourne le prefixe de String finissant en position Fin */
prefix(String, Fin, S) :-
        Fin1 is Fin+1,
        sub_string(String, 0, Fin1, _, S).
        
        
   /* retourne la sous chaine de String commencant a Deb et finissant a Fin */
sous_chaine(String, Deb, Fin, S) :-
        Longueur is Fin - Deb + 1,
        sub_string(String, Deb, Longueur, _, S).
        
        
/* ======================================================================== */
/*                           TIME HANDLING                                  */
/* ======================================================================== */  

get_current_time(H, M, S) :-
   get_time(T),
   stamp_date_time(T, date(_, _, _, H, M, S1, _, _, _), local),
   S is round(S1).


duration(H1, M1, S1, H2, M2, S2, D) :-
   D1 is H1*3600 + M1*60 + S1,
   D2 is H2*3600 + M2*60 + S2,
   D is D2 - D1.
   
   
display_duration(D) :-
   H is D // 3600,
   RH is D rem 3600,
   M is RH // 60,
   S is RH rem 60,
   display_hms(H, M, S).
   
 
display_hms(H, M, S) :-
   write(H),
   write(' h '),
   display_ms(M,S).
   
   
display_ms(M, S) :-
   write(M),
   write(' m '),
   display_s(S).

   
display_s(S) :-
   write(S),
   writeln(' s').


/* ======================================================================== */
/*                           LIST HANDLING                                  */
/* ======================================================================== */

delete_last_element(L, Lout) :-
   reverse(L, [_|L1]),
   reverse(L1, Lout).
                 
        
