% type btr(T) ---> n
%	;	btr(T,btr,btr)

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

satrak(satrak(Ss,Os,Fs),Res):-
	mkrow(Ss,L,Btr),mkbin_tree(Os,Obtr),!,satrak1(L,Btr,Obtr,Fs,Fs,[],Res).
 
%------------------------------------------------------------------------------
% satrak1(L,Btr,Obtr,Fs,Fstest,Sator,Res), 
% satrak3(L,Btr,Obtr,Fs,Fstest,Sator,Res): L is a list of pairs. These pairs 
% corredpond to the rows in wich more tents can be placed. Btr is a binary
% tree where the serial numbers of those rows are placed, where infinite tents 
% can be placed. Obstr is the binary tree of pairs consisting the serial numbers
% of rows and the number of tents which can be placed on the rows. Fs is the
% list of trees, which tents are supposed to be attached to. Fstest
% is the list of serial numbers of rows, where tents can still be placed.
% Sator is the list of those tents placed in the matrix, which are not in
% rows with too small serial numbers. Res is the result of the clause: the
% list of e,w,s,n.
%
% :- pred satrak1( list(int-int)::in, btr(int)::in,		% rows
%		btr(int-int)::in,				% columns
%		list(int-int)::in, list(int-int)::in,		% trees
%		list(int-int)::in,list::out).			% tents
% :- pred satrak2( list(int-int)::in, btr(int)::in,		% rows
%		btr(int-int)::in,				% columns
%		list(int-int)::in, list(int-int)::in,		% trees
%		list(int-int)::in,list::out).			% tents

satrak1(L,Btr,Obtr,Fs,Fstest,Sator,Res):-
	Fs=[Y-_|_],!,
	Ymin is Y-1,
	getoutFs(Fstest,Ymin,Fstest1),
	getoutL(L,Ymin,L1),
	satrak2(L1,Btr,Obtr,Fs,Fstest1,Sator,Res).


satrak1(L,_,Obtr,[],_,_,[]):-check_final_columns(Obtr),check_rows(L).

satrak2(L,Btr,Obtr,[Y-X|T],Fstest,Sator,[Z|Res]):-	
	side_neighbour(Y1-X1,Z),
	Y2 is Y+Y1,
	X2 is X+X1,
	iscolumn(X2,Obtr,Obtr1),	
	istree(Fstest,Y2-X2),
	istent(Sator,Y,Y2-X2,Sator1),
	isrow(L,Btr,Y2,L1),
	satrak1(L1,Btr,Obtr1,T,Fstest,[Y2-X2|Sator1],Res).

%------------------------------------------------------------------------------
% check_final_columns(Obtr): true if in Obtr the rows values are non positive
%
% :- pred check_final_columns(btr(parc).

check_final_columns(Obtr):-
	Obtr=btr(_-X,BtrL,BtrR),!,
	X=<0,
	check_final_columns(BtrL),
	check_final_columns(BtrR).

check_final_columns(n).

%------------------------------------------------------------------------------
% check_rows(L): true if for every pair in the list L the second element in
% the pair is 0
%
% :- pred check_rows(list(int-int)).

check_rows(L):-
	L=[_-B|T],!,
	B=0,check_rows(T).
	
check_rows([]).

%------------------------------------------------------------------------------
% getoutFs(Fs,Y,Fs1): Fs1 is Fs minus the head of Fs where the first elements of
% pairs are smaller than Y.
%
% :- pred getoutFs(list(parc)::in,int::in,list(parc)::out).

getoutFs(Fs,Y,Fs1):-
	Fs=[Y1-X1|T],!,
	(Y1<Y -> getoutFs(T,Y,Fs1)
	;Fs1=[Y1-X1|T]
	).

getoutFs([],_,[]).

%------------------------------------------------------------------------------
% getoutL(L,Y,L1): L1 is the same as L, excepted that the pairs in it,
% corresponding to rows with smaller serial number than Y-1 are thrown away if
% in every pair the second element is 0. If that criteria isn't fulfilled,
% the clause is false.
%
% getoutL(list(int-int)::in,int::in,list(int-int)::out).

getoutL(L,Y,L1):-
	L=[N-S|T],!,
	(N<Y-> S=0,getoutL(T,Y,L1)
	; L=L1
	).		

getoutL([],_,[]).

%------------------------------------------------------------------------------
% iscolumn(X,Btr0,Btr) : if column X is found in the binary tree Btr0 and if 
% there's still place for a tent in that column, the clause is true and the 
% difference between Btr and Btr0 is that in the pair corresponding to column
% X the second element of the pair is reduced by 1.
%
% :- pred iscolumn(int::in,btr::in,btr::out).

iscolumn(X,btr(X1-Y,BtrL,BtrR),Btr):-
	(X=X1->
		(Y>=0->
			Y>0,
			Y1 is Y-1,
			Btr=btr(X-Y1,BtrL,BtrR)
		;
			Btr=btr(X-Y,BtrL,BtrR)
		)	
	;X>X1->
		iscolumn(X,BtrR,Btr1),Btr=btr(X1-Y,BtrL,Btr1)
	;
		iscolumn(X,BtrL,Btr1),Btr=btr(X1-Y,Btr1,BtrR)
	).

%------------------------------------------------------------------------------
% isrow(L,Btr,Y,Y2,L1): Y2 is in Btr or it's one of L's pairs' first element,
% and the second element of that pair is positive.
% L1 is same as L excepted, that if Y2 is in one of L's pairs, than the second
% element of that pair is reduced by 1 and those pairs of which first element
% is smaller than Y-1 is thrown away. Those pairs which are examined and 
% correspond to rows where there cannot be put any more tents are also thrown
% away
%
% :- pred isrow(list(int)::in,btr(int)::in,int::in,int::in,list(int)::out).

isrow(L,Btr,Y2,L1):-
	(isrow_first_step(Btr,Y2)->L1=L
	;isrow_second_step(L,Y2,L1)
	).

%------------------------------------------------------------------------------
% isrow_first_step(Btr,Y):-Y is in binary tree Btr
%
% :- pred isrow_first_step(btr(int)::in,int::in).

isrow_first_step(btr(X,BtrL,BtrR),Y):-
	(X>Y->isrow_first_step(BtrL,Y)
	;X<Y->isrow_first_step(BtrR,Y)
	;true
	).

%------------------------------------------------------------------------------
% isrow_second_step(L,Y,L1): true if there's in list L a pair, in which the 
% first element is Y, and the second element is greater than 0. We can get L1
% if we throw away those pairs which are examined and the second elements of
% them is 0.
%
% pred isrow_second_step(list(int-int)::in,int::in,list(int-int)::out).

isrow_second_step([N-S|T],Y,L1):-
	(S=0->
		isrow_second_step(T,Y,L1)
	;
		(N=Y->
			Z is S-1,L1=[N-Z|T]
		;
			N>Y->false
		;
			L1=[N-S|T1],isrow_second_step(T,Y,T1)
		)
	).

%------------------------------------------------------------------------------
% istent(Tents,Y1,Y-X,Tents1): true if Y-X is not in the list of Tents. Tent1
% is the list of tents the y coordinates of which is less than Y1-2.
%
% :- pred(list(parc)::in,int::in,parc::in,list(parc)::out).

istent(Tents,Y1,Y-X,Tents1):-
	Tents=[Y2-X2|T],!,
	Y3 is Y1-Y2,
	(Y3>4->
		Tents1=[]
	;
		Y4 is abs(Y-Y2),
		(Y4<2->X4 is abs(X-X2),X4>=2
		;true
		),
		Tents1=[Y2-X2|Tents2],
		istent(T,Y1,Y-X,Tents2)
	).

istent([],_,_,[]).

%------------------------------------------------------------------------------
% istree(Fs,Y-X): is true if Y-X is not member of Fs
%
% :- pred istree(list(parc)::in,parc::in).

istree(Fs,Y-X):-
	Fs=[Y1-X1|T],!,
	(Y1>Y->true
	;Y1<Y->istree(T,Y-X)
	;X\=X1,istree(T,Y-X)
	).

istree([],_).

%------------------------------------------------------------------------------
% mkbin_tree(Os,Bintree): Bintree is the binary tree version of the pairs
% consisting of list Os's elements and their positions in the list.
%
% :- pred mkbin_tree(list(any)::in,btr::out),

mkbin_tree(Os,Bintree):-
	mkbin_tree(Os,0,0,n,Bintree),!.

%------------------------------------------------------------------------------
% mkbin_tree(Os,N,Level,Bintree0,Bintree): Bintree - Bintree is the binary 
% tree version of the pairs, consisting Os's elements and their position
% numbers in the original list.
% Bintree0 is one of the subtrees of Bintree consisting the first N pairs.
% There's Level levels in Bintree0.
%
% :- pred mkbin_tree(list(any)::in,int::in,int::in,btr::in,btr::out).

mkbin_tree(Os,N,Level,Bintree0,Bintree):-
	Os=[H|T],!,
	Level1 is Level+1,
	N1 is N+1,
	mkbin_tree(T,T1,N1,N2,1,Level,n,Btr_left),
	mkbin_tree(T1,N2,Level1,btr(N1-H,Bintree0,Btr_left),Bintree).

mkbin_tree([],_,_,Tree,Tree).

%------------------------------------------------------------------------------
% mkbin_tree(L0,L,N0,N,Level,Maxlevel,Btr0,Btr): L0 is the remaining part of
% list L after construating a binary tree, which has as many elements as it's
% possible and maximum Maxlevel levels. N is N0 plus the number of elements in
% the tree. Btr is the tree itself.
%
% :- pred mkbin_tree( list(any)::in,list(any)::out,
%		int::in,int::out, int::in,int::in, btr::in,btr::out).

mkbin_tree(L0,L,N0,N,Level,Maxlevel,Btr0,Btr):-
	L0=[H|T],Level=<Maxlevel,!,
	Level1 is Level+1,
	Level0 is Level-1,
	N1 is N0+1,
	mkbin_tree(T,T1,N1,N2,1,Level0,n,Btr_left),
	mkbin_tree(T1,L,N2,N,Level1,Maxlevel,btr(N1-H,Btr0,Btr_left),Btr).
	

mkbin_tree(L,L,N,N,_,_,Btr,Btr).

%------------------------------------------------------------------------------
% mkrow(L1,L2,Btr): L2 is the list of pairs of L1's non negative members and
% their positions. Btr is a binary tree which comprises the L1's negative 
% members' positions.
%
% :- pred mkrow(list(int)::in,list(int)::out,btr(int)::out).

mkrow(L1,L2,Btr):-
	mkrow_first_part(L1,L2,L3,0),
	mkrow_second_part(L3,0,n,Btr).

%------------------------------------------------------------------------------
% mkrow_first_part(L1,L2,L3,N): L2 is the list of pairs comprising L1's 
% positive members, and their original position, and L3 is the
% list of L1's negative members' position, in the same order as it was in L1.

mkrow_first_part(L1,L2,L3,N):-
	L1=[H|T],!,
	N1 is N+1,
	(H<0->
		L3=[N1|L4],
		mkrow_first_part(T,L2,L4,N1)
	;H>0->
		L2=[N1-H|L4],
		mkrow_first_part(T,L4,L3,N1)
	;
		mkrow_first_part(T,L2,L3,N1)
	).

mkrow_first_part([],[],[],_).

%------------------------------------------------------------------------------
% mkrow_second_part(Os,Level,Bintree0,Bintree): Bintree -Bintree0 is a binary 
% tree consisting of Os list's elements. Level is the level of Bintree0.
%
% :- pred mkrow_second_part(list(any)::in,int::in,btr::in,btr::out).

mkrow_second_part(Os,Level,Bintree0,Bintree):-
	Os=[H|T],!,
	Level1 is Level+1,
	mkrow_second_part(T,T1,1,Level,n,Btr_left),
 	mkrow_second_part(T1,Level1,btr(H,Bintree0,Btr_left),Bintree).

mkrow_second_part([],_,Tree,Tree).

%------------------------------------------------------------------------------
% mkrow_second_part(L0,L,Level,Maxlevel,Btr0,Btr): Btr-Btr0 is a binary tree
% consisting of that much of L0's elements, that Btr's level is not greater
% than Maxlevel. Btr0 is one of the subtrees of Btr, having Level levels.
% L is the list of L0's elements for which there's no room in Btr.
%
% :- pred mkrow_second_part( list(any)::in,list(any)::out,
%		int::in,int::in, btr::in,btr::out).

mkrow_second_part(L0,L,Level,Maxlevel,Btr0,Btr):-
	L0=[H|T],Level=<Maxlevel,!,
	Level1 is Level+1,
	Level0 is Level-1,
	mkrow_second_part(T,T1,1,Level0,n,Btr_left),
	mkrow_second_part(T1,L,Level1,Maxlevel,btr(H,Btr0,Btr_left),Btr).	

mkrow_second_part(L,L,_,_,Btr,Btr).

%------------------------------------------------------------------------------
% side_neighbour(X-Y,Z) : X-Y is the disaplacement coordinates of a
% sideneighbour square and Z is the point of the compass of this displacement.
%
% :- pred side_neighbour(int-int::both,int::both).

side_neighbour(1 - 0,s).
side_neighbour(-1 - 0,n).
side_neighbour(0 - 1,e).
side_neighbour(0 - -1,w).