
:- module(bitcodesets,
	[ bitset_empty/1,
	  bitset_equal/2,
	  bitset_member/2,
	  not_bitset_member/2,
	  bitset_member_SoS/2,
	  bitset_subset/2,
	  bitset_union/3,
	  bitset_union_list/2,
	  bitset_union_list_list_s/4,
	  bitset_intersect/3,
	  bitset_subtract/3,
	  bitset_subtract_list/3,
	  bitset_size/2,
	%
	  bitcode_to_listofbitcode/2,
	  bitcode_to_set/2,	
	  bitcode_to_set/3,
	  bitcode_to_set_array/2,
	  int_to_bitcode/2,
	  lbitcode_to_llist/2,
	  lbitcode_to_llistS/2,
	  llist_to_lbitcode/2,
	  set_to_bitcode/2

	],
	[ assertions
	]).

:- use_module(library(sort),[ sort/2 ]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
:- comment(title,"Bit-coded-set operations").
:- comment(module,"Only finite sets and complements of finite sets.").
:- comment(author,"Adapted by Francisco Bueno from code by Ann Mulkers").
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

/*
:- mode
	bitset_empty(+),
	bitset_equal(+,+),
	bitset_member(+,+),		
	bitset_member_SoS(+,+),		
	bitset_subset(+,+),		
	bitset_union(+,+,-),		
	bitset_union_list(+,-),		
	bitset_union_list_list_s(+,+,+,-),
	bitset_intersect(+,+,-),	
	bitset_subtract(+,+,-),		
	bitset_subtract_list(+,+,-),	
	bitset_size(+,-).		
*/

bitset_empty(0). 

bitset_equal(Bc,Bc).

bitset_member(Bc,Bcs) :-  Bc /\ Bcs =\= 0.

not_bitset_member(Bc,Bcs) :-  0 is Bc /\ Bcs.

bitset_member_SoS(Bc,[H|_]) :-   Bc /\ H =\= 0,!.
bitset_member_SoS(Bc,[_|Tail]) :-  bitset_member_SoS(Bc,Tail).

bitset_subset(Subset,Set) :- 	     Subset is Subset /\ Set.

bitset_intersect(Bcs1,Bcs2,Bcs3) :-  Bcs3 is Bcs1 /\ Bcs2.

bitset_subtract(Bcs1,Bcs2,Bcs3) :-   Bcs3 is Bcs1 /\ \(Bcs2).

bitset_union(Bcs1,Bcs2,Bcs3) :-      Bcs3 is Bcs1 \/ Bcs2.

%-------------------------------------------------------------------------
% bitset_union_list(+,-)
% bitset_union_list(LBcs,Union)
%-------------------------------------------------------------------------
:- push_prolog_flag(multi_arity_warnings,off).

bitset_union_list(LBcs,Union):-
	bitset_union_list(LBcs,0,Union).

bitset_union_list([],Union,Union). 
bitset_union_list([H|List],Acc,Union) :- 
	NewAcc is H \/ Acc,
	bitset_union_list(List,NewAcc,Union).

:- pop_prolog_flag(multi_arity_warnings).

%-------------------------------------------------------------------------
% bitset_union_list_list_s(+,+,+,-)
% bitset_union_list_list_s(LBcs,Bcs,LAcc,LUnion)
%-------------------------------------------------------------------------
bitset_union_list_list_s([],_,LAcc,LUnion):-
	sort(LAcc,LUnion).
bitset_union_list_list_s([H|List],Bcs,LAcc,LUnion) :- 
	NH is H \/ Bcs,
	bitset_union_list_list_s(List,Bcs,[NH|LAcc],LUnion). 

%-------------------------------------------------------------------------
% bitset_subtract_list(+,+,-)
% bitset_subtract_list(LBcs,Bcs,LSubtract)
%-------------------------------------------------------------------------
bitset_subtract_list([],_,[]). 
bitset_subtract_list([H|List],Bcs,[NH|NList]) :- 
	NH is H /\ \(Bcs),
	bitset_subtract_list(List,Bcs,NList). 

%-------------------------------------------------------------------------
% bitset_size(+,+,-)
% bitset_sixe(Bcs,Num,Size)
%-------------------------------------------------------------------------
:- push_prolog_flag(multi_arity_warnings,off).

bitset_size(0,Size,Size) :- !.
bitset_size(Bcs,Num,Size) :- 
	(Bcs /\ 1)  =\=  0,!,
	NNum is Num + 1,
	NBcs is Bcs >> 1,
	bitset_size(NBcs,NNum,Size).
bitset_size(Bcs,Num,Size) :- 
	NBcs is Bcs >> 1,
	bitset_size(NBcs,Num,Size).

bitset_size(0,0)  :- !.
bitset_size(Bcs,'$infty')  :-  Bcs < 0,!.
bitset_size(Bcs,Result) :-
	bitset_size(Bcs,0,Result).

:- pop_prolog_flag(multi_arity_warnings).

/*
:- mode 
	int_to_bitcode(+,-),			
	set_to_bitcode(+,-),			
	bitcode_to_listofbitcode(+,?),		
	bitcode_to_set(+,?),			
	bitcode_to_set(+,+,?),		
	llist_to_lbitcode(+,-),			
	lbitcode_to_llist(+,-).			
*/

%-------------------------------------------------------------------------
% Transforms an integer into its bitcode. The definition (rather than the
% predicate) is usually used for efficiency.
%-------------------------------------------------------------------------

int_to_bitcode(X,Y) :-  Y is 1 << X .

%-------------------------------------------------------------------------
% set_to_bitcode(+,-)
% set_to_bitcode(LNum,Bcs)
% Transforms a list of integers into its bitcode representation
%-------------------------------------------------------------------------
:- push_prolog_flag(multi_arity_warnings,off).

set_to_bitcode(LNum,Bcs):-
	set_to_bitcode(LNum,0,Bcs).

set_to_bitcode([],Bcs,Bcs)  .
set_to_bitcode([H|T],Acc,Bcs) :-  
	Hc is 1 << H,			%	int_to_bitcode(H,Hc),
	Acc0 is Hc \/ Acc,
	set_to_bitcode(T,Acc0,Bcs).

:- pop_prolog_flag(multi_arity_warnings).

%-------------------------------------------------------------------------
% llist_to_lbitcode(+,-)
% llist_to_lbitcode(LLNum,LBcs)
% Transfomrs each list of numbers in LLNum into its bitcode representation
%-------------------------------------------------------------------------
llist_to_lbitcode([],[]).
llist_to_lbitcode([H|T], [Hc|Tc] ) :-
	set_to_bitcode(H, Hc),
	llist_to_lbitcode(T, Tc ) .

%-------------------------------------------------------------------------
% bitcode_to_set(+,-)
% bitcode_to_set(Bcs,LNum)
% Transforms a bitcode representation into its list of integers 
%-------------------------------------------------------------------------
:- push_prolog_flag(multi_arity_warnings,off).

bitcode_to_set(0,[])  :- ! .
bitcode_to_set(C,S) :-
	bitcode_to_set(C,0,S) .

bitcode_to_set(0,_,[]) :- ! .
bitcode_to_set(Code,Num,LNum):-
	( (Code /\ 1)  =\=  0 ->
	    LNum = [Num|Tail]
	;   LNum = Tail),
	NNum is Num + 1,
	NCode is Code >> 1, 
	bitcode_to_set(NCode,NNum,Tail) .

:- pop_prolog_flag(multi_arity_warnings).

%-------------------------------------------------------------------------
% lbitcode_to_llistS(+,-)
% lbitcode_to_llistS(LBcs,LLNum)
% Transfomrs each bitcode representation in LBcs into its list of integers
%-------------------------------------------------------------------------
lbitcode_to_llistS([],[]).
lbitcode_to_llistS([Hc|Tc], [H|T] ) :-
	bitcode_to_set(Hc, H),
	lbitcode_to_llistS(Tc, T ) .

%-------------------------------------------------------------------------
% ??
%-------------------------------------------------------------------------

lbitcode_to_llist(ps(InSHr,ExShr),ps(InSHr_ec,ExShr_ec)) :- !,
	bitcode_to_set(InSHr,InSHr_ec),
	lbitcode_to_llistS(ExShr,ExShr_ec) .
lbitcode_to_llist(List_i,List_o) :- lbitcode_to_llistS(List_i,List_o) .

%-------------------------------------------------------------------------
% bitcode_to_listofbitcode(+,-)
% bitcode_to_listofbitcode(Bcs,LBcs)
% Transforms a bitcode into the list of bitcodes which form it. It is like
% bitcode to_set but the output is in bitcode rather than integers
%-------------------------------------------------------------------------
:- push_prolog_flag(multi_arity_warnings,off).

bitcode_to_listofbitcode(0,[])  :- ! .
bitcode_to_listofbitcode(C,S) :-
	bitcode_to_listofbitcode(C,1,S) .

bitcode_to_listofbitcode(0,_,[]) :- ! .
bitcode_to_listofbitcode(Code,Num,List) :- 
	( (Code /\ 1)  =\=  0 ->
	    List = [Num|Tail]
	;   List = Tail),
	NNum is Num << 1,
	NCode is Code >> 1, 
	bitcode_to_listofbitcode(NCode,NNum,Tail) .

:- pop_prolog_flag(multi_arity_warnings).

%-------------------------------------------------------------------------
% bitcode_to_set_array(+,-)
% bitcode_to_set_array(Array1, Array2)
%-------------------------------------------------------------------------
% Each bitcode element in Array1 is transformed into its list of bitcodes
% and added to Array2.
%-------------------------------------------------------------------------
:- push_prolog_flag(multi_arity_warnings,off).

bitcode_to_set_array(array($(A0,A1,A2,A3),Size), array($(L0,L1,L2,L3),Size)) :-
	N is Size-2,
	bitcode_to_set_array(0, N, 0, A0, L0), 
	bitcode_to_set_array(1, N, 0, A1, L1), 
	bitcode_to_set_array(2, N, 0, A2, L2), 
	bitcode_to_set_array(3, N, 0, A3, L3).

bitcode_to_set_array(_K, _N, _M, $, $) :- ! .
bitcode_to_set_array(_K, 0, _M, Item, Item_lic) :- !,
	bitcode_to_listofbitcode( Item, Item_lic ) .
bitcode_to_set_array(K, N, M, $(A0,A1,A2,A3), $(L0,L1,L2,L3) ) :-
	N1 is N-2,
	M1 is (K+M)<<2,
	bitcode_to_set_array(0, N1, M1, A0, L0),
	bitcode_to_set_array(1, N1, M1, A1, L1),
	bitcode_to_set_array(2, N1, M1, A2, L2),
	bitcode_to_set_array(3, N1, M1, A3, L3).

:- pop_prolog_flag(multi_arity_warnings).

%-------------------------------------------------------------------------
:- comment(version_maintenance,dir('../version')).

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