%
% sort objects according to precedence between object pairs
%
:- module(sort_procedence,[	sort/1,
				add_precedence/2,
				remove_precedence/2,
				directly_proceed/2,
				indirectly_proceed/2,
				clean_up/0
				]
		).

:- dynamic(proceed/2).

:- use_module('cif_util').
:- use_module('prolog_detect').
:- prolog_detect:prolog(Prolog),
	(	(	Prolog=sicstus,
			use_module(library(lists))
		);
		(	Prolog=pfdm,
			use_module(library(lists))
		);
		true
	).

%
% add_precedence/2
%
% adding a piece of precedence information between 2 objects
%
add_procedence(A,B) :-
	proceed(A,B),			%already exist, no need to assert
	!.
add_procedence(A,B) :-
	assertz(proceed(A,B)).

%
% remove_precedence/2
%
% remove all occurences of proceed(A,B)
%
remove_precedence(A,B) :-
	proceed(A,B),
	retract(proceed(A,B)),
	fail.
remove_precedence(_,_).


%
% directly_proceed/2
%
% see if 1 object directly proceeds another
%
directly_proceed(A,B) :-
	proceed(A,B).

%
% indirectly_proceed/2
%
% see if 1 object indirectly proceeds another
%
indirectly_proceed(A,B) :-
	proceed(A,B).
indirectly_proceed(A,B) :-
	proceed(A,X),
	indirectly_proceed(X,B).

%
% sort/1
%
% sort all objects that appear in proceed/2
% result is a list of sorted list
% each list is indenpent of the others
%
sort(Sorted_groups) :-
	find_all_objects(Objects),			%find all objects as a set
	sort_into_trees(Objects,[],Sorted_groups).	%sort them

find_all_objects(Set) :-
	findall(pair(A,B),proceed(A,B),Pairs),		%find all objects as pairs
	pairs_to_set(Pairs,[],Set).			%convert list of pairs to a list (set) of objects

%
% convert a list of pairs to a set
%
pairs_to_set([],Set,Set) :-
	!.
pairs_to_set([pair(A,B)|Ps],Old_set,New_set) :-
	!,
	add_to_set(A,Old_set,Temp_set),
	add_to_set(B,Temp_set,Temp_set2),
	pairs_to_set(Ps,Temp_set2,New_set).
pairs_to_set(X,Set,Set) :-
	member(X,Set),
	!.
pairs_to_set(X,Set,[X|Set]).

%
%
%
% sort a list of objects in trees
% each tree contains a set of classes w/ dependence
%
sort_into_trees([],Tree,Tree).					%nothing to sort

sort_into_trees([X|Xs],[],Trees) :-				%empty tree list
	sort_into_trees(Xs,[tree(nil,X,nil)],Trees).		%create new tree, then proceed

sort_into_trees([X|Xs],Old_trees,New_trees) :-
	member(Tree,Old_trees),					%take a tree in the list
	Tree=tree(_,Node,_),					%get node value & left right subtrees
	in_same_tree(Node,X),					%X should be in same tree as Node
	!,
	sort_into_tree(X,Tree,New_tree),			%sort X into this tree
	delete(Old_trees,Tree,Temp_trees),
	sort_into_trees(Xs,[New_tree|Temp_trees],New_trees).

sort_into_trees([X|Xs],Old_trees,New_trees) :-
	sort_into_tree(X,nil,X_tree),				%create a new tree
	sort_into_trees(Xs,[X_tree|Old_trees],New_trees).	%proceed to sort
%
% sort X into a tree
%
sort_into_tree(X,nil,tree(nil,X,nil)).
sort_into_tree(X,tree(Left,Node,Right),tree(Left,Node,New_right)) :-
	indirectly_proceed(X,Node),
	!,
	sort_into_tree(X,Right,New_right).
sort_into_tree(X,tree(Left,Node,Right),tree(New_left,Node,Right)) :-
	indirectly_proceed(Node,X),
	!,
	sort_into_tree(X,Left,New_left).
sort_into_tree(X,tree(Left,Node,Right),tree(New_left,Node,Right)) :-
	sort_into_tree(X,Left,New_left).


%
% if X & Y is indirectly related, they should go into the same binary tree
%
in_same_tree(X,Y) :-
	indirectly_proceed(X,Y),
	!.
in_same_tree(X,Y) :-
	indirectly_proceed(Y,X),
	!.

in_same_tree(X,Y) :-
	indirectly_proceed(X,Z),
	indirectly_proceed(Y,Z),
	!.

in_same_tree(X,Y) :-
	indirectly_proceed(Z,X),
	indirectly_proceed(Z,Y).

