partition([],[],[],_,_).
partition([(X,Y)|T],[(X,Y)|R],ResultatB,SurfaceA,SurfaceB) :-
	 X*Y #=< SurfaceA,
	 SurfaceA #= X*Y + NewSurfaceA,
	 partition(T,R,ResultatB,NewSurfaceA,SurfaceB).
partition([(X,Y)|T],ResultatA,[(X,Y)|R],SurfaceA,SurfaceB) :-
	 X*Y #=< SurfaceB,
	 SurfaceB #= X*Y + NewSurfaceB,
	 partition(T,ResultatA,R,SurfaceA,NewSurfaceB).

% calcule la surface totale d'une liste de morceaux
sommesurfaces([],0).
sommesurfaces([(X,Y)|R],Somme) :- sommesurfaces(R,RSomme), 
                                  Somme is (X*Y) + RSomme.

% ordonne les morceaux
ordonne([],[]).
ordonne([(X,Y)|T],[(X,Y)|RT]) :- X=<Y, ordonne(T,RT).
ordonne([(X,Y)|T],[(Y,X)|RT]) :- X>Y,  ordonne(T,RT).

coupe(Pieces,Largeur,Hauteur,Plan) :-
 sommesurfaces(Pieces,S),
 S =< Hauteur*Largeur,
 ordonne(Pieces,PiecesOrd),
 c(PiecesOrd,Largeur,Hauteur,Plan).

c(Pieces,Largeur,Hauteur,Plan) :-
	listcoupe(Pieces,Largeur,Hauteur,Plan),!.
c(Pieces,Largeur,Hauteur,vertical(Coupe,PlanA,PlanB)) :-
	fd_domain(Coupe,1,Largeur),
	2*Coupe #=< Largeur,
	RestLargeur #= Largeur-Coupe,
	SurfaceA #= Coupe*Hauteur,
	SurfaceB #= RestLargeur*Hauteur,
	partition(Pieces,ResultatA,ResultatB,SurfaceA,SurfaceB),
	nonempty(ResultatA), nonempty(ResultatB),
	fd_labeling(Coupe),
	c(ResultatA,Coupe,Hauteur,PlanA),
	c(ResultatB,RestLargeur,Hauteur,PlanB).
c(Pieces,Largeur,Hauteur,horizontal(Coupe,PlanA,PlanB)) :-
	fd_domain(Coupe,1,Hauteur),
	2*Coupe #=< Hauteur, 
	RestHauteur #= Hauteur-Coupe,
	SurfaceA #= Largeur*Coupe,
	SurfaceB #= Largeur*RestHauteur,
	partition(Pieces,ResultA,ResultB,SurfaceA,SurfaceB),
	nonempty(ResultA), nonempty(ResultB),
	fd_labeling(Coupe),
	c(ResultA,Largeur,Coupe,PlanA),
	c(ResultB,Largeur,RestHauteur,PlanB).

nonempty([_|_]).

listcoupe(Pieces, Largeur, Hauteur, list(Plan)) :-
Largeur #>= Hauteur, listcoupe_l(Pieces, Largeur, Hauteur, Plan).
listcoupe(Pieces, Largeur, Hauteur, stack(Plan)) :-
Largeur #< Hauteur, listcoupe_l(Pieces, Hauteur, Largeur, Plan1),
renversepieces(Plan1,Plan).

renversepieces([],[]).
renversepieces([(X,Y)|L],[(Y,X)|L1]) :- renversepieces(L,L1).

listcoupe_l([],_,_,[]).
listcoupe_l([(X,Y)|R], Largeur, Hauteur, [(X,Y)|PlanR]) :-
	Y #=< Hauteur,
	RestLargeur #= Largeur - X, RestLargeur #>= 0, 
	listcoupe_l(R,RestLargeur,Hauteur,PlanR).
listcoupe_l([(X,Y)|R], Largeur, Hauteur, [(Y,X)|PlanR]) :-
	Y #> Hauteur,
	X #=< Hauteur,
	RestLargeur #= Largeur - Y, RestLargeur #>= 0, 
	listcoupe_l(R,RestLargeur,Hauteur,PlanR).
