% -------------------------------------------------------------
% general predicates for chart parsers with agenda
% of Gazdar/Mellish, pp. 208/209
% -------------------------------------------------------------

start_agenda([],_,[]).
start_agenda([Word|Words],V0,Agenda) :-
	V1 is V0+1,
	findall(edge(V0,V1,Category,[]),
		word(Category,Word),
		Agenda1),
   start_agenda(Words,V1,Agenda2),
   append(Agenda1,Agenda2,Agenda).

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

extend_edges([], Chart, Chart).
extend_edges([Edge|Agenda1], Chart1, Chart2) :-
   member(Edge,Chart1), !,
   extend_edges(Agenda1,Chart1,Chart2).
extend_edges([Edge|Agenda1], Chart1, Chart3) :-
   Chart2 = [Edge|Chart1],
	new_edges(Edge,Chart2,Edges),
%	add_edges(Edges,Agenda1,Agenda2),      % depth-first processing
	add_edges(Agenda1,Edges,Agenda2),      % breadth-first processing
	extend_edges(Agenda2,Chart2,Chart3).

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

add_edge(Edge,Edges,Edges) :-
	member(Edge,Edges).
add_edge(Edge,Edges,[Edge|Edges]).

add_edges([],Edges,Edges).
add_edges([Edge|Edges],Edges1,Edges3) :-
	add_edge(Edge,Edges1,Edges2),
	add_edges(Edges,Edges2,Edges3).

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

found_parse(Chart) :-
	initial(Symbol),
	member(edge(0,M,Symbol,[]),Chart),
	N is M + 1,
	not(member(edge(_,N,_,_),Chart)).

% -------------------------------------------------------------
% some auxilary predicates:

not(X) :- \+(X).

member(X,[X|_]).
member(X,[_|L]) :- member(X,L).

append([],L,L).
append([H|T],L,[H|R]) :-
	append(T,L,R).
