/* ========================================================================== */
/*                              LISTS HANDLING                                */
/* ========================================================================== */   

:- module(list,
           [			   			      
							/* MISCELLANEOUS */	
			all_parts/2,
		    sort_listes/2,
            intersection/4,
		    make_coples/3,
            split_list/4,
		    merge_lists/2,
            refresh_list/2,
            combinations/3,
            select_deb_end/5,
			flat_liste/2,
            empty/1,
            not_empty/1,
			split_ground_atoms/3,      % (L, L1, L2)
                                       % split the list L into 
                                       % a list L1 having ground atoms 
               				           % a list L2 having non ground atoms
		
							/* MEMBER */
		    member_LL/2,

							/* SUBSET */
            my_subset/2,               % (L1, L2)
                                       % check whether L1 is included in L2
                                       % (based on member and not on memberchk)
		    is_subset/2,
		    strict_member_nth/3,
            
   
							/* GETTING */
		    get_kth_arguments_tuples/3,
                                       % L     list of tuples
                                  	   % K     place of desired argument
                                       % LArgs List of found arguments
           
		    get_kth_arguments/3,
                                       % L     list of elements
                                       % K     place of desired argument
                                  	   % LArgs List of found arguments
		    select_nth/4,

							/* INSERTING */
		    insert_last/3,
		    insert_nth/4,

							/* NUMBERING */
            denumbers_elements/2,
            numbers_elements/3,
		    nb_occurrences/3, 

							/* ADDING */
            add_element_to_lists/4,
            add_element_to_lists/3,
            add_elements_to_lists/3,
            add_elements_to_list/3,
		    append_list_to_lists/3,
            add_check_element/3,

							/* REPLACING */
            replace_nth_list/4,

							/* DELETING */
            delete_all/3,
            delete_nth/3, 	   	    % delete_nth(N, L, L1) 
              				  	    % delete the Nth elements of L, 
                                 	% result in L1 
		    discard_grounded_terms/2,	
             
							/* CROSS PRODUCT */
            cross_product_lists/2,
            cross_product_lists_of_lists/2,
            list_to_single_element_lists/2,
		    product_list_with_lists/3,

							/* SUBSUMPTION */						 
            subsumes_a_list/2,
            subsumes_list/2, 
 
							/*  MINIMAL MAXIMALS LISTS */

		    minimal_lists/2,        % (LL1, LL2)
                                    % LL2 wil contain minimal lists of LL1  
            keep_minimal_lists/2,
            keep_minimal_lists/3,
            keep_maximal_lists/2,
            keep_maximal_lists/3,
         
								/* SIMILARITIES */
            have_similar_element/3,
            similar_elements/3,
            similar_lists/3,
		    discard_similar_elements/3,
            discard_similar_elements_tab/3,
            contains_similar_occurrences/2,
            member_similar/3,
            exists_similar_element/3,
		    delete_similar_elements/4,

								/* INCLUSION */
		    included_in_list/3,	
            includes_list/3,  
            included_list/3           
            
           ]).          

:- 
   getenv('LEAR_DIR', Lear),
   atom_concat(Lear, '/term.pl', Term),    
   use_module(Term).



/* ========================= INCLUSION OF LISTS ============================= */

	/* check wether L1 is included in L2 */

my_subset([], _L2) :-
   !.

my_subset([X|L1], L2) :-
   member(X,L2),
   my_subset(L1, L2).

/*  ======================== HANDLING Nth ELEMENT OF A LIST ================= */


	/* select the nth element (X) of the list given in 2nd argument */
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).


 /* delete the Nth elements of L */
delete_nth(1, [_|L], L) :-
	!.
	
delete_nth(N, [Y|L], [Y|L1]) :-
   N1 is N-1,
   delete_nth(N1, L, L1).
   

insert_last(X, L, L1) :-
   length(L, N),
   insert_nth(N, X, L, L1).

	/* insert X in Nth places in L */
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).


	/* replace the Nth element of L by X */
replace_nth_list(1, X, [_Y|L], [X|L]) :-
   !.

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


	/* return N, rank of X in L, fail if X is not in L */
strict_member_nth(_X, [], _) :-
   !,
   fail.

strict_member_nth(X, [Y|_L], 1) :-
   X == Y,
   !.

strict_member_nth(X, [_|L], N) :-
   strict_member_nth(X, L, N1),
   N is N1+1.


/* ========================================================================== */

	/* delete all instance of E int L, L_out is the remaining list */
   
delete_all(L, E, L_out) :-
   copy_term(E, E1),
   select(E1, L, L1),
   !,
   delete_all(L1, E, L_out).
   
delete_all(L, _E, L).   


/* ----------------------------- ADD ------------------------------------ */

   /* add X at position Pos to each list of LL */
add_element_to_lists(_X, _Pos, [], []) :-
   !.

add_element_to_lists(X, Pos, [L|LL], [L_out|LL_out]) :-
   insert(X, Pos, L, L_out),
   add_element_to_lists(X, Pos, LL, LL_out).


  /* add X at the begining of each list of LL */
add_element_to_lists(_X, [], []) :-
   !.

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


   /* each element of L is add to the list L1, making new lists */
add_elements_to_list([], _L1, []) :-
   !.

add_elements_to_list([X|L], L1, [[X|L1]|LL]) :-
   add_elements_to_list(L, L1, LL).


   /* each element of L to each list of LL, making new lists of lists */
add_elements_to_lists([], _LL, []) :-
   !.

add_elements_to_lists([X|L], LL, LL_out) :-
   add_element_to_lists(X, LL, LL1),
   add_elements_to_lists(L, LL, LL2),
   append(LL1, LL2, LL_out).
   
   
   
	/* add X to L if X is not in L */
add_check_element(X, L, L) :-
   member(X, L),
   !.
   
add_check_element(X, L, [X|L]).   	  
         
   
   	/* insert X before the Posth element of the list L                */
	/* insert behind the last element if L has less than Pos elements */
	
insert(_X, Pos, _L, _L_out) :-
   Pos =< 0,
   !,
   fail.
      
     
insert(X, 1, [], [X]) :-
   !.
      
insert(X, 1, L, [X|L]) :-
   !.
   
insert(X, Pos, [Y|L], [Y|L_out]) :-
   Pos1 is Pos-1,
   insert(X, Pos1, L, L_out).
   
   
           /* discard all grounded atoms common to LTerm and L */
subtract_common_grounded_terms([], _L, []) :-
   !.
   
subtract_common_grounded_terms([Term|LTerm], L, LTerm_out) :-
   ground(Term),
   member(Term, L),
   !,
   subtract_common_grounded_terms(LTerm, L, LTerm_out).
   
 subtract_common_grounded_terms([Term|LTerm], L, [Term|LTerm_out]) :-
   subtract_common_grounded_terms(LTerm, L, LTerm_out).  


        /* discard all grounded atoms in a list */
discard_grounded_terms([], []) :-
   !.
   
discard_grounded_terms([Term|LTerm], LTerm_out) :-
   ground(Term),
   !,
   discard_grounded_terms(LTerm, LTerm_out).
   
 discard_grounded_terms([Term|LTerm], [Term|LTerm_out]) :-
   discard_grounded_terms(LTerm, LTerm_out).  
   

/* =========================== CONBINATIONS & ARRANGMENTS =================== */

	/* return all combinations of K elements among the N elements in L */

combinations(L, K, LL) :-
 length(L, N),
 K =< N,
 !,
 combinations2(L, N, K, LL).

	
combinations2(_L, _N, 0, [[]]) :-
   !.
   
combinations2(L, N, N, [L]) :-
   !.   
   	
combinations2(
              [X|L],  % list of elements
              N,      % # of elements in [X|L]
              K,      % # of elements of each combination
              LC      % list of combinations of length K
            ) :-
   N1 is N-1,
   K1 is K-1,         
   combinations2(L, N1, K,  L1),
   combinations2(L, N1, K1, L2),
   add_element_to_lists(X, L2, L3),
   append(L3, L1, LC).
           

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

	/* split the list between ground an non ground atoms */
split_ground_atoms([], [], []) :-
   !.

split_ground_atoms([A|L], [A|LGround], LNo_ground) :-
   ground(A),
   !,
   split_ground_atoms(L, LGround, LNo_ground).

split_ground_atoms([A|L], LGround, [A|LNo_ground]) :-
   split_ground_atoms(L, LGround, LNo_ground).


	/* get the kth argument of each element in the list L */
get_kth_arguments([], _K, []) :-
   !.

get_kth_arguments([Atom|LAtoms], K, [Arg|LArgs]) :-
   arg(K, Atom, Arg),
   get_kth_arguments(LAtoms, K, LArgs).
   

	/* get the kth argument of each tuple in the list L */
get_kth_arguments_tuples([], _K, []) :-
   !.

get_kth_arguments_tuples([Atom|LAtoms], K, [Arg|LArgs]) :-
   get_kth_argument_tuple(Atom, K, Arg),
   get_kth_arguments_tuples(LAtoms, K, LArgs).
   

   /* split a list into two lists, the first having N elements */
split_list(0, L, [], L) :-
   !.

split_list(N, [X|L], [X|L1], L2) :-
   N1 is N-1,
   split_list(N1, L, L1, L2).
  
 /* make cople with one element taken in L1 and one of same rank in L2 */
make_coples([], [], []) :-
   !.

make_coples([X1|L1], [X2|L2], [(X1,X2)|LL]) :-
   make_coples(L1, L2, LL).


   /* remove the number associated with each element of a list */
denumbers_elements([], []) :-
   !.

denumbers_elements([(_,X)|L], [X|L1]) :-
   denumbers_elements(L, L1).
   

   /* add a number to each element of a list */
numbers_elements(_, [], []) :-
   !.

numbers_elements(N, [X|L], [(N,X)|L1]) :-
   N1 is N+1,
   numbers_elements(N1, L, L1).
   

   /* merge all lists into a single list        */
   /* (no recursive process like with flatten)  */

merge_lists([L], L) :-
   !.

merge_lists([L|LL], L_out) :-
   merge_lists(LL, L1),
   append(L, L1, L_out).

 
  /* append the list L to each list of LL */     
append_list_to_lists(_, [], []) :-
        !.
        
append_list_to_lists(L, [L1|LL1], [L2|LL2]) :-
        append(L, L1, L2),
        append_list_to_lists(L, LL1, LL2).   



	/* check if a list is a subset of another one, equivalently
	   return a subset of a list (non deterministic predicate).
	   template : is_subset(+Sub, ?L).
	 */  
is_subset([], _L).

is_subset([X|L], L1) :-
  member(X, L1),
  is_subset(L, L1).


   /* refresh name of variables of all elements in a list */
   
refresh_list([], []) :-
   !.
   
refresh_list([Term|LTerm], [Term1|LTerm1]) :-
   copy_term(Term, Term1),
   refresh_list(LTerm, LTerm1).      
   

	/* check whether X is in at least one list of LL(list of lists) */
member_LL(_X, []) :-
    !,
    fail.
    
member_LL(X, [L|_LL]) :-
   member(X,L).
   
member_LL(X, [_L|LL]) :-
   member_LL(X,LL).       
  


        /* build all possible parts of a list */
all_parts([],[[]]) :-
   !.
   
all_parts([X|L], LL) :-
   all_parts(L, LL1),
   add_element_to_lists(X, LL1, LL2),
   append(LL1, LL2, LL).
   

empty([]).

not_empty(L) :-
   \+ empty(L).


                % 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).
         
        
                /* return the list formed of the Nth first elements of L */
prefix_list(0, _L, []) :-
        !.
        
prefix_list(N, [X|L], [X|LPref]) :-
        N1 is N-1,
        prefix_list(N1, L, LPref).


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).
 
 
    /* keep the minimal lists of LL */
minimal_lists(LL, LMin) :-
    length(LL, N),
    check_minimal_lists(N, LL, LMin).
    
    
   /* keep the minimal lists of the list of lists LL */
check_minimal_lists(0, LL, LL) :-
   !.
   
check_minimal_lists(N, [L|LL], LL2) :-
   is_minimal_list(L, LL),
   !,
   N1 is N-1,
   append(LL,[L], LL1),
   check_minimal_lists(N1, LL1, LL2).
   
   
check_minimal_lists(N, [_L|LL], LL1) :-
   N1 is N-1,								% L is discard
   check_minimal_lists(N1, LL, LL1).
   

/* check if L includes no list of LL */
is_minimal_list(_L, []) :-
   !.
   
is_minimal_list(L, [L1|_LL]) :-
   subset(L1, L),
   \+ subset(L, L1),           
   !,
   fail.
   
is_minimal_list(L, [_L1|LL]) :-
   is_minimal_list(L, LL).
   
        
	/* keep the minimal lists of the list of lists LL */
keep_minimal_lists([], []) :-
   !.
   
keep_minimal_lists([L], [L]) :-
   !.   	
   
keep_minimal_lists([L|LL], LL_out) :-
   discard_non_minimal_successors(L, LL, LL1, Result),
   check_minimal_result(Result, L, LL1, LL_out).
   
   /* check whether L is minimal */
check_minimal_result(true, L, LL, [L|LL_out]) :-
   !,
   keep_minimal_lists(LL, LL_out).
   
check_minimal_result(false, _L, LL, LL_out) :-
   keep_minimal_lists(LL, LL_out).   
   
    
discard_non_minimal_successors(_L, [], [], true) :-
   !.      
   
discard_non_minimal_successors(L, [L1|LL], [L1|LL], false) :-
   subset(L1, L),       % L is not minimal
   !.
   
discard_non_minimal_successors(L, [L1|LL], LL_out, Result) :-
   subset(L, L1),       % L1 is not minimal
   !,
   discard_non_minimal_successors(L, LL, LL_out, Result).
   

discard_non_minimal_successors(L, [L1|LL], [L1|LL_out], Result) :-	   
   discard_non_minimal_successors(L, LL, LL_out, Result).  
   
   
	/* keep the maximal lists of the list of lists LL */
keep_maximal_lists([], []) :-
   !.
   
keep_maximal_lists([L], [L]) :-
   !.   	
   
keep_maximal_lists([L|LL], LL_out) :-
   discard_non_maximal_successors(L, LL, LL1, Result),
   check_maximal_result(Result, L, LL1, LL_out).
   
   /* check whether L is minimal */
check_maximal_result(true, L, LL, [L|LL_out]) :-
   !,
   keep_maximal_lists(LL, LL_out).
   
check_maximal_result(false, _L, LL, LL_out) :-
   keep_maximal_lists(LL, LL_out).   
   
    
discard_non_maximal_successors(_L, [], [], true) :-
   !.      
   
discard_non_maximal_successors(L, [L1|LL], [L1|LL], false) :-
   subset(L, L1),       % L is not maximal
   !.
   
discard_non_maximal_successors(L, [L1|LL], LL_out, Result) :-
   subset(L1, L),       % L1 is not maximal
   !,
   discard_non_maximal_successors(L, LL, LL_out, Result).
   

discard_non_maximal_successors(L, [L1|LL], [L1|LL_out], Result) :-	   
   discard_non_maximal_successors(L, LL, LL_out, Result).        
      
/* ========================================================================== */
/*                  CROSS PRODUCTS BETWEEN LISTS                              */
/* ========================================================================== */
	
		/* compute the cross product of one list L with a list of lists LL */
product_list_with_lists([X], LL, LLout) :-
        !,
        add_element_to_lists(X, LL, LLout).

product_list_with_lists([X|L], LL, LLout) :-
	product_list_with_lists(L, LL, LL1),
	add_element_to_lists(X, LL, LLX),	
	append(LLX, LL1, LLout).
           
   
	/* compute the cross_product of lists */
cross_product_lists([L], LL) :-
   !,
   list_to_single_element_lists(L, LL).
   
cross_product_lists([L|LL], LL_out) :-
   cross_product_lists(LL, LL1),   	
   product_list_with_lists(L, LL1, LL_out).
 
 
	/* transforms a list L, in a list of lists each one containing
	   one element of L */
list_to_single_element_lists([X], [[X]]) :-
   !.

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


	/* compute the cross-product of lists of lists */
cross_product_lists_of_lists([LL], LL) :-
   !.

cross_product_lists_of_lists([LL|LLL], LLout) :-
   cross_product_lists_of_lists(LLL, LL1),
   cross_product_two_lists_of_lists(LL, LL1, LLout).


       /* compute the cross_product of two lists of lists */
cross_product_two_lists_of_lists([L], LL, LLout) :-
   !,
   merge_list_to_lists(L, LL, LLout).

cross_product_two_lists_of_lists([L|LL], LL1, LLout) :-
   cross_product_two_lists_of_lists(LL, LL1, LL3),
   merge_list_to_lists(L, LL1, LL2),
   append(LL2, LL3, LLout).
   
/* ==========================================================================- */   

	/* merge the list L to each list of a list of lists */
merge_list_to_lists(L, [L1], [L2]) :-
   append(L, L1, L2),
   !.

merge_list_to_lists(L, [L1|LL], [L2|LL1]) :-
   append(L, L1, L2),
   merge_list_to_lists(L, 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 */
discard_deuxieme_composant([], []) :-
        !.

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

        /* substitute X by Y in L, result in L_out */
substitute(_, _, [], []) :-
   !.
        
substitute(X, Y, [X|L], [Y|L_out]) :-
   !,
   substitute(X, Y, L, L_out).
   
substitute(X, Y, [Z|L], [Z|L_out]) :-
   substitute(X, Y, L, L_out).
   
 discard_sublists_tab([], []) :-
   !.
   
discard_sublists_tab([Tab|LTab], [Tab1|LTab1]) :-
   discard_sublists(Tab, Tab1),
   discard_sublists_tab(LTab,LTab1).

   /* discard non maximal lists (remaining lists do not subsume another
      lists) of LL */
discard_sublists([], []) :-
   !.
   
discard_sublists(LL, LL_out) :-  
   discard_subsuming_lists(LL, LL1),
   reverse(LL1, LL2),
   discard_subsuming_lists(LL2,LL3),
   reverse(LL3, LL_out).
   
   
   /* discard lists that subsume successor lists in LL */   
discard_subsuming_lists([], []) :-
   !.
  
discard_subsuming_lists([L|LL], LL_out) :-
   subsumes_a_list(L, LL),
   !,
   discard_subsuming_lists(LL, LL_out).
   
discard_subsuming_lists([L|LL], [L|LL_out]) :-
   discard_subsuming_lists(LL, LL_out).
   

        /* check if L subsumes a list of LL */   
subsumes_a_list(_L, []) :-
   !,
   fail.
   
subsumes_a_list(L, [L1|_LL]) :-
   subsumes_list(L, L1),
   !.
   
subsumes_a_list(L, [_L1|LL]) :-
   subsumes_a_list(L, LL).
 

        /* vrai si les termes de L1 forment un shema relationel qui est 
            present dans L2 (au nom des variables pres) */     
            
subsumes_list([], _) :-
   !.
   
subsumes_list(_, []) :-
   !,
   fail.

subsumes_list(L1, L2) :-
        sort(L1, LA),
        sort(L2, LB),
        subsumption_list(LA, LB).
 
 
subsumption_list(LA, LB) :-    % LA and LB are structurally equal
   LA =@= LB,
   !.
   
subsumption_list(LA, LB) :-
        occurrence_list_included(LA, LB, LZ1),   % LZ1 is an occurrence of LA in LB...
        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).  
        
        
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).        
        
       
nb_variables_distinctes(Terme, N) :-
        term_variables(Terme, LV),
        length(LV, N).  
  
  
/* ==========  LIST HANDLING USING A SIMILARITY RELATION ==================== */
    
similar_elements(X, Y, structurally) :-
        !,
        X =@= Y.
        
similar_elements(X, Y, strictly) :-
        !,
        X == Y.
                
similar_elements(X, X, _).  % by default two elements are similar
                            % if they can be unified. 
     

   /* check whether L1 and L2 has at last one similar element */
have_similar_element([], _L2, _Similarity) :-
   !,
   fail.

have_similar_element([X|_L1], L2, Similarity) :-
   member_similar(X, L2, Similarity),
   !.

have_similar_element([_X|L1], L2, Similarity) :-
   have_similar_element(L1, L2, Similarity).


   

   /* check if X is contained in L according to the similarity relation */
member_similar(_, [], _) :-
   !,
   fail.
   
member_similar(X, [Y|_L], Similarity) :-
   similar_elements(X,Y, Similarity),
   !.

member_similar(X, [_Y|L], Similarity) :-
   member_similar(X, L, Similarity).
  
   
        /* verifie la similarite de 2 listes aux noms des variables pres */
similar_lists(L1, L2, Similarite) :-
        included_list(L1, L2, Similarite),
        included_list(L2, L1, Similarite).


        /* keep only the maximal lists of LL */
keep_maximal_lists(
                    LL,
                    LL_out,
                   Similarity
                   ) :-
    keep_maximal_lists_successors(LL, LL1, Similarity),
    reverse(LL1, LL2),
    keep_maximal_lists_successors(LL2, LL_out, Similarity).
    
    /* keep only lists that are maximal with respect to their successors */
keep_maximal_lists_successors(
                   [],       % list of lists contains at least one element
                   [],       % result
                   _Similarity
                   ) :-
   !.                   
    
keep_maximal_lists_successors(
                   [L|LL],       % list of lists contains at least one element
                   LL_out,       % result
                   Similarity
                   ) :-
   included_in_list(L, LL, Similarity),
   !,
   keep_maximal_lists_successors(LL, LL_out, Similarity).
   
 keep_maximal_lists_successors(
                   [L|LL],       
                   [L|LL_out],  
                   Similarity
                   ) :-
   keep_maximal_lists_successors(LL, LL_out, Similarity).  


        /* keep only the miminimal lists of LL */
keep_minimal_lists(
                    LL,
                    LL_out,
                   Similarity
                   ) :-
    keep_minimal_lists_successors(LL, LL1, Similarity),
    reverse(LL1, LL2),
    keep_minimal_lists_successors(LL2, LL_out, Similarity).
    
    /* keep only lists that are minimal with respect their successors */
keep_minimal_lists_successors(
                   [],       
                   [],       
                   _Similarity
                   ) :-
   !.                   
    
keep_minimal_lists_successors(
                   [L|LL],       % list of lists contains at least one element
                   LL_out,       % result
                   Similarity
                   ) :-
   includes_list(L, LL, Similarity),
   !,
   keep_minimal_lists_successors(LL, LL_out, Similarity).
   
 keep_minimal_lists_successors(
                   [L|LL],       
                   [L|LL_out],  
                   Similarity
                   ) :-
   keep_minimal_lists_successors(LL, LL_out, Similarity).  

  
                /* verifie que L est incluse dans au moins une liste de LL */
included_in_list(_, [], _) :-
        !,
        fail.
        
included_in_list(L, [L1|_], Similarite) :-
        included_list(L, L1, Similarite),
        !.

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

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

included_list([X|L1], L2, Similarite) :-
        exists_similar_element(X, L2, Similarite),
        included_list(L1, L2, Similarite).      
        
        
position_premier_element_similaire(_, _, [], _, _) :-
        !,
        fail.
                
position_premier_element_similaire(X, PosR, [Y|_], Similarite, PosR) :-
        similar_elements(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).       
        
               
                        /* verifie que L contient un element similaire a X */
exists_similar_element(_, [], _) :-
        !,
        fail.

exists_similar_element(X, [Y|_], Similarity) :-
        similar_elements(X,Y, Similarity),
        !.

exists_similar_element(X, [_|L], Similarity) :-
        exists_similar_element(X, L, Similarity).
        
        
discard_similar_elements_tab([],[], _) :-
   !.
   
discard_similar_elements_tab([Tab|LTab],[Tab1|LTab1], Similarity) :-
   discard_similar_elements(Tab, Tab1, Similarity),
   discard_similar_elements_tab(LTab, LTab1, Similarity).

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

discard_similar_elements([X|L], L1, Similarite) :-
        exists_similar_element(X,L,Similarite),
        !,
        discard_similar_elements(L, L1, Similarite).
        
discard_similar_elements([X|L], [X|L1],Similarite) :-
        discard_similar_elements(L, L1, Similarite). 
        
        
discard_similar_elements(_, [], [], _) :-
        !.
        
discard_similar_elements(X, [X1|L], L1, Similarite) :-
        similar_elements(X, X1, Similarite),
        !,
        discard_similar_elements(X, L, L1, Similarite).
        
discard_similar_elements(X, [X1|L], [X1|L1], Similarite) :-
        discard_similar_elements(X, L, L1, Similarite).      
        
        /* vrai si L contient plusieurs occurrences similaires */
contains_similar_occurrences([], _) :-
        !,
        fail.
        
        /* vrai si L contient plusieurs occurrences similaires */
contains_similar_occurrences([X|L], Similarite) :-
        exists_similar_element(X, L, Similarite),
        !.
        
        /* vrai si L contient plusieurs occurrences similaires */
contains_similar_occurrences([_|L], Similarite) :-
        contains_similar_occurrences(L, Similarite).


        /* vrai si L1 et L2 possedent des elements similaires */
contains_similar_elements([], _, _) :-
        !,
        fail.
        
contains_similar_elements([X|_], L2, Similarite) :-
        exists_similar_element(X, L2, Similarite),
        !.
        
contains_similar_elements([_|L1], L2, Similarite) :-
        contains_similar_elements(L1, L2, Similarite).  
        
	/* return the intersection of two lists according to a similarity relation */        
intersection([], _L2, [], _) :-
   !.
   
intersection([X|L1], L2, [X|L3], Similarity) :-
   in(X, L2, Similarity),
   intersection(L1, L2, L3, Similarity).
   
 intersection([_X|L1], L2, L3, Similarity) :-
   intersection(L1, L2, L3, Similarity).  
   
   
	/* delete from L1 all elements common (according to Similariy) to L1 and L2 
	   result in L3 */

delete_similar_elements([], _L2, [], _) :-
   !.
	   
delete_similar_elements([X|L1], L2, L3, Similarity) :-
   member_similar(X, L2, Similarity),
   !,
   delete_similar_elements(L1, L2, L3, Similarity).

   
delete_similar_elements([X|L1], L2, [X|L3], Similarity) :-
   delete_similar_elements(L1, L2, L3, Similarity).   
   
  
/* =============================== END OF THE LISTING ======================= */                 
