:- module(tree_abstract, [ concepts_in_search_state/2,     % +State, -Nodes
			   tree_abstract/3,             % +Nodes, +Max, -Reduced
			   group_items_by_nodes/4,	% +Nodes, +Items, +SearchGraph, -Pairs
			   target_to_nodes/4,            % +Nodes, +Rel, +Graph, -Nodes
			   nodes_to_tree/2              % +Nodes, -Tree
			 ]).


:- use_module(library(semweb/rdf_db)).
:- use_module(library(semweb/rdfs)).
:- use_module(library(semweb/rdf_label)).
:- use_module(library(lists)).
:- use_module(library(debug)).
:- use_module(rdf_graph).
:- use_module(rdf_search).
:- use_module(graph_search).
:- use_module(owl_ultra_lite).

%%	group_items_by_nodes(+Nodes, +Items, +Graph, -Pairs:score-cluster)
%
%	Clusters is a collection of a list each containing the Items
%	directly related to a member of Nodes.

group_items_by_nodes([], _, _, []).
group_items_by_nodes([node(root,_,_)|Ns], Items, Graph, Cs) :- !,
	%debug(concept_group, '~w', Children),
	group_items_by_nodes(Ns, Items, Graph, Cs).
group_items_by_nodes([node(R0,_P,_)|Ns], Items, Graph, [R-Results|Cs]) :-
	(   R0 = [Random|_]
	->  R = more(Random),
	    items_related_to_group(Items, R0, Graph, Results, Rest)
	;   R = R0,
	    items_related_to_node(Items, R0, Graph, Results, Rest)
	),
	length(Items, ICount),
	length(Results, RCount),
	debug(concept_group, '~w total ~w, results ~w', [R,ICount,RCount]),
	Results \== [], !,
	group_items_by_nodes(Ns, Rest, Graph, Cs).
group_items_by_nodes([_|Ns], Items, Graph, Cs) :-
	group_items_by_nodes(Ns, Items, Graph, Cs).


items_related_to_node([], _, _, [], []).
items_related_to_node([Score-URI|Is], R, Graph, [Score-URI|Rs], Rest) :-
	search_graph_rdf(Graph, URI, _, R), !,
	items_related_to_node(Is, R, Graph, Rs, Rest).
items_related_to_node([Item|Is], R, Graph, Rs, [Item|Rest]) :-
	items_related_to_node(Is, R, Graph, Rs, Rest).

items_related_to_group([], _, _, [], []).
items_related_to_group([Score-URI|Is], Group, Graph, [Score-URI|Rs], Rest) :-
	item_related_to_group(Group, URI, Graph), !,
	items_related_to_group(Is, Group, Graph, Rs, Rest).
items_related_to_group([Item|Is], Group, Graph, Rs, [Item|Rest]) :-
	items_related_to_group(Is, Group, Graph, Rs, Rest).

item_related_to_group([R|_], S, Graph) :-
	search_graph_rdf(Graph, S, _, R).
item_related_to_group([_|T], S, Graph) :-
	item_related_to_group(T, S, Graph).

% %	concepts_in_search_state(+SearchState, -Pairs:score-[node(uri,parent,children)])
%
%	Pairs is a list of score-node pairs contained in the search
%	state.

concepts_in_search_state(State, Concepts) :-
	rdf_search_property(State, node_score_list(Nodes)),
	rdf_search_property(State, graph(Graph)),
	findall(Score-Node,
		(   member(Concept-Score, Nodes),
		    concept(Concept, Graph, Node)
		),
		Concepts).

concept(R, Graph, node(R,Parent,Children)) :-
	rdfs_individual_of(R, skos:'Concept'),
	rdf_equal(skos:broader, Rel),
	%rdfs_individual_of(R, flor:'Sense'), !,
	%rdf_equal(flor:isWNSubClass, Rel),
	parent(R, Rel, Graph, Parent),
	children(R, Rel, Graph, Children).


%%	target_to_nodes(+Targets, +Rel, +Graph, -Nodes)
%
%	Nodes is contains targets and for each target its parent and
%	children.

target_to_nodes([], _, _, []).
target_to_nodes([Score-R|Ts], Rel, Graph, [Score-Node|Ns]) :-
	Node = node(R, Parent, Children),
	parent(R, Rel, Graph, Parent),
	children(R, Rel, Graph, Children),
	target_to_nodes(Ts, Rel, Graph, Ns).

parent(R, Rel, Graph, Parent) :-
	search_graph_owl_inv(Graph, R, Rel, Parent), !.
parent(_, _, _, root).

children(R, Rel, Graph, Children) :-
	findall(C,
		search_graph_owl_inv(Graph, C, Rel, R),
		Children).


:- rdf_meta
         search_graph_owl_inv(+, r, r, o).

%%	search_graph_owl_inv(+Graph, +S, +P, +O)
%
%	Similar as search_graph, but with support for inverse
%	properties.

search_graph_owl_inv(Graph, S, P, O) :-
	search_graph_rdf(Graph, S, P, O).
search_graph_owl_inv(Graph, S, P, O) :-
	inverse_predicate(P, IP),
	search_graph_rdf(Graph, O, IP, S),
	\+ search_graph_rdf(Graph, S, P, O).

%%	tree_abstract(+TreeIn, +MaxNumberOfLeaves, -TreeOut)
%
%	TreeOut is a reduced version of TreeIn containing only
%	MaxNumberOfLeafs.

tree_abstract(Nodes0, Max, TreeOut) :-
	%nodes(TreeIn, Nodes0),
	Nodes1 = [0.5-node(root,noparent,[])|Nodes0],
	keysort(Nodes1, Nodes),
	tree_reduce(Nodes, Max, TreeOut).

%%	tree_reduce(+Nodes, +Max, -Nodes)
%
%	Reduce the number of nodes to Max, by
%	* merging leafs
%	* merge child with parent

tree_reduce(Nodes, Max, Nodes) :-
	length(Nodes, Count),
	debug(tree_reduce, '~w nodes', [Count]),
	Count =< Max,
	!.
tree_reduce([Score-node(R,P,C)|Ns], Max, Reduced) :-
	(   C = []
	->  debug(tree_reduce, 'leaf', []),
	    leaf_reduce(Ns, Score, R, P, Rest)
	;   debug(tree_reduce, 'node', []),
	    node_reduce(Ns, Score, R, P, C, Rest)
	),  !,
	tree_reduce(Rest, Max, Reduced).
tree_reduce(Nodes, _, Nodes).

leaf_reduce(Nodes, Score, R, P, Reduced) :-
	leaf_merge(Nodes, Score, R, P, Bag, Rest), !,
	keysort([Bag|Rest], Reduced).
leaf_reduce(Nodes, _Score, R, P, Reduced) :-
	leaf_collapse(Nodes, R, P, Reduced).

node_reduce(Nodes, Score, R, root, Cs, Reduced) :-
	Score1 is Score*2,
	keysort([Score1-node(R,root,Cs)|Nodes], Reduced).
node_reduce(Nodes, _Score, R, P, _Cs, Reduced) :-
	merge_nodes(Nodes, P, R, Reduced).
	%Score1 is Score*2,
	%keysort([Score1-node(R,P,[])|Nodes], Reduced).


%%	leaf_merge(+Nodes, -Bag, -NodesOut)
%
%	Leaf nodes with lowest score is merged with similar sibblings.

leaf_merge(T, Score, R, Parent, Bag, Rest) :-
	Bag  = Score1-node([R|Sibblings], Parent, []),
	sibblings(T, Score, Parent, Sibblings, Rest),
	length(Sibblings, Count),
	rdf_label(R, Label),
	debug(tree_reduce, 'merge ~w: ~w sibblings found', [Label, Count]),
	Sibblings \== [],
	Score1 = Score.
	%Score1 is Score*2.

%%	leaf_collapse(+Nodes, +R, +Parent, -Reduced)
%
%	Reduced contains all Nodes and Parent is merged with R.

leaf_collapse(Nodes, R, Parent, Rest) :-
	rdf_label(R, Label),
	rdf_label(Parent, PLabel),
	debug(tree_reduce, 'collapse ~w with ~w', [Label, PLabel]),
	%Rest = Nodes.
	merge_nodes(Nodes, Parent, R, Rest).

merge_nodes([Score-node(Rs,P,C)|T], R, Add, [Score-Node|T]) :-
	Node = node(Merged,P,C),
	(   is_list(Rs),
	    member(R, Rs)
	->  (	is_list(Add)
	    ->	append(Rs,Add,Merged)
	    ;	append(Rs,[Add],Merged)
	    )
	;   R == Rs
	->  (	is_list(Add)
	    ->	Merged = [R|Add]
	    ;	Merged = [R,Add]
	    )
	),
	!.
merge_nodes([Node|T], R, Add, [Node|Rest]) :-
	merge_nodes(T, R, Add, Rest).



%tree_reduce(Nodes, Max, Reduced) :-
%	node_abstract(Nodes, Merged),
%	tree_reduce(Merged, Max, Reduced).


%%	node_abstract(+NodesIn, -NodesOut)
%
%	Node with lowest score in NodesIn is folded with parent.
/*
node_abstract([_Score-Node|Rest], Rest) :-
	Node = node(_, _, []),
	!.
node_abstract([_Score-Node0|T], [Score-Node|Rest]) :-
	Node0 = node(R, P, C),
	Node = node(Rs, P, []),
	add_children(T, P, C, Rest0),
	replace_parent(Rest0, R, P, Rest).
*/

add_children([Score-Node0|T], R, C, [Score-Node|T]) :-
	Node0 = node(R, P, C0),
	Node  = node(R, P, Children),
	append(C, C0, Children),
	!.
add_children([Node|T], P, C, [Node|Rest]) :-
	add_children(T, P, C, Rest).

replace_parent([], _, _, []).
replace_parent([Score-Node0|T], P0, P, [Score-Node|Rest]) :-
	Node0 = node(R,P0,C),
	!,
	Node  = node(R,P,C),
	replace_parent(T, P0, P, Rest).
replace_parent([Node|T], P0, P, [Node|Rest]) :-
	replace_parent(T, P0, P, Rest).




sibblings([S-node(R,P,[])|T], S, P, Sibblings, Rest) :- !,
	(   is_list(R)
	->  append(R,Rs,Sibblings)
	;   Sibblings = [R|Rs]
	),
	sibblings(T, S, P, Rs, Rest).
sibblings([S-Node|T], S, P, Sibblings, [S-Node|Rest]) :- !,
	sibblings(T, S, P, Sibblings, Rest).
sibblings(T, _, _, [], T).




tree_test(Keyword, Max, Tree) :-
	do_query(Keyword, State),
	concepts_in_search_state(State, Nodes),
	tree_abstract(Nodes, Max, Reduced),
	nodes_to_tree(Reduced, Tree).
	%nodes_to_clusters(Reduced, Clusters).


do_query(Keyword, State) :-
	setting(cluster_search:basic_search_target, Class),
	Filter = [type(Class)],
	graph_search(Keyword, State, [filter(Filter),prune(true),literal_threshold(0)]).





tree0(node(a,0,[
		node(b,0,[
			  node(c1,0.2,[
				      node(d1,1,[]),
				      node(d2,1,[])
				     ]),
			  node(c2,0,[
				     node(d3,0.5,[
						 node(e1,0.2,[])
						 ]),
				     node(d4,0.5,[]),
				     node(d5,0.5,[])
				    ])
			 ])
	       ])).


nodes_to_clusters([], []).
nodes_to_clusters([Score-node(R,P,Children)|T], [cluster(Score,Label,Count)|Rest]) :-
	node_label(R, P, Label),
	length(Children, Count),
	nodes_to_clusters(T, Rest).


nodes_to_tree(Nodes, node(root, [], Children)) :-
	children_of_node(Nodes, root, Nodes, Children).

children_of_node([], _, _, []).
children_of_node([Score-node(Rs,Parent,_)|T], Parent, Nodes, [Node|Rest]) :- !,
	(   Rs = [R|_]
	->  true
	;   Rs = R
	),
	Node = node(R, [score(Score),label(Label)], Children),
	node_label(R, Parent, Label),
	children_of_node(Nodes, R, Nodes, Children),
	children_of_node(T, Parent, Nodes, Rest).
children_of_node([_|T], Parent, Nodes, Rest) :-
	children_of_node(T, Parent, Nodes, Rest).


node_label(R, Parent, Label) :-
	(   is_list(R)
	->  rdfs_label(Parent,L),
	    atom_concat('specific ', L, Label)
	;   rdfs_label(R, Label), !
	).


%%	nodes(+Tree, -Pairs:score-node) is det
%
%	Pairs is a list of score-node pairs contained in Tree.

nodes(Tree, Leaves) :-
	nodes(Tree, root, Leaves, []).

nodes(node(N,S,[]), P, [S-node(N,P,[])|T], T) :- !.
nodes(node(N,S,Children), P, [S-node(N,P,Rs)|Nodes], T) :-
	maplist(node_resource, Children, Rs),
	children_nodes(Children, N, Nodes, T).

children_nodes([], _, T, T).
children_nodes([Node|Ns], P, Leaves, T) :-
	nodes(Node, P, Leaves, L),
	children_nodes(Ns, P, L, T).

node_resource(node(R,_,_), R).

%%	leaves(+Tree, -Pairs:score-leaf) is det
%
%	Pairs is a list of score-leaf pairs contained in Tree.

leaves(Tree, Leaves) :-
	leaves(Tree, root, Leaves, []).

leaves(node(N,S,[]), P, [S-node(N,P)|T], T) :- !.
leaves(node(N,_,Children), _, Leaves, T) :-
	   children_leaves(Children, N, Leaves, T).

children_leaves([], _, T, T).
children_leaves([Node|Ns], P, Leaves, T) :-
	leaves(Node, P, Leaves, L),
	children_leaves(Ns, P, L, T).


%%	leaf_count(+Tree, -Count) is det
%
%	Count is the number of leafs in Tree.

leaf_count(node(_,_,[]), 1) :- !.
leaf_count(node(_,_,Children), C) :-
	   children_leaf_count(Children, C).

children_leaf_count([], 0).
children_leaf_count([Node|Ns], C) :-
	leaf_count(Node, C1),
	children_leaf_count(Ns, C2),
	C is C1+C2.