/* File:      basics.P
** Author(s): David S. Warren, Kostis F. Sagonas
** Contact:   xsb-contact@cs.sunysb.edu
** 
** Copyright (C) The Research Foundation of SUNY, 1986, 1993-1998
** 
** XSB is free software; you can redistribute it and/or modify it under the
** terms of the GNU Library General Public License as published by the Free
** Software Foundation; either version 2 of the License, or (at your option)
** any later version.
** 
** XSB is distributed in the hope that it will be useful, but WITHOUT ANY
** WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
** FOR A PARTICULAR PURPOSE.  See the GNU Library General Public License for
** more details.
** 
** You should have received a copy of the GNU Library General Public License
** along with XSB; if not, write to the Free Software Foundation,
** Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**
** $Id: basics.P,v 1.11 2001/10/09 19:13:15 dwarren Exp $
** 
*/


/*----------------------------------------------------------------------*/
/* NOTE: This file needs compilation with the "sysmod" option.  	*/
/*----------------------------------------------------------------------*/

:- compiler_options([sysmod]).

/*----------------------------------------------------------------------*/

% append! ta-da!
append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

%---
/* copy_term is an inlined builtin */
copy_term(Term, Result) :- copy_term(Term, Result).

%---
flatten([],[]).
flatten([H|T],Flatlist):-
	flatten1([H|T],Flatlist,[]).

flatten1([],Var,Var).
flatten1([H|T],Flatlist,Flatout):-
	is_list(H) -> flatten1(H,Flatlist,Flatmid),
		      flatten1(T,Flatmid,Flatout)
		; 	Flatlist = [H|Flatmid],
			flatten1(T,Flatmid,Flatout).

%---
% ground/1 checks for ground term.

ground(T) :- ground(T).

%---
% ith/3 that works both ways
% ith(Index,List,Element)
ith(Index,List,Element) :-
	( integer(Index) -> ith0(Index,List,Element)
	;   ith1(List,1,Index,Element)
	).

ith0(I,[X|L],Y) :-
	I > 0,
	(I =< 1
	 ->	Y=X
	 ;	I1 is I-1,
		ith0(I1,L,Y)
	).

ith1([X|_],I,I,X).
ith1([_|L],I1,I,X) :- I2 is I1+1, ith1(L,I2,I,X).

%---
% log_ith/3 is a variant of ith, in which the ``list'' argument is a 
% tree, which is a list of full binary trees, each having depth one
% greater than the previous.  This guarantees log time access to any
% element in the ``list''

% Like ith/3, log_ith/3 works in both directions.  The major advantage
% is that when using log_ith with its first argument bound, the access
% time is (2)log, instead of linear.  Also, log_ith/3 only instantiates
% the portion of the list-tree structure it needs, so much of it can
% remain unbound.  For example, after inserting a value into the Kth
% location in a completely unbound list-tree, the structure constructed
% is of order log K.

% log_ith(Index,ListStr,Element)
log_ith(K,T,E) :- 
	term_type(K,Ty),
	(Ty =:= 2	% integer
	 ->	log_ith0(K,T,E,1)
	 ;	log_ith1(K,T,E,1)
	).

% K is bound
log_ith0(K,[L|R],E,N) :-
	(K < N
	 ->	bintree0(K,L,E,N)
	 ;	K1 is K-N,
		N2 is N+N,
		log_ith0(K1,R,E,N2)
	).

% First arg (K) is bound
bintree0(0,E,E,1).
bintree0(K,[L|R],E,N) :- 
	N > 1,
	N2 is N // 2,
	(K < N2
	 ->	bintree0(K,L,E,N2)
	 ;	K1 is K - N2,
		bintree0(K1,R,E,N2)
	).

% K is unbound
log_ith1(K,[L|_R],E,N) :-
	bintree1(K,L,E,N).
log_ith1(K,[_L|R],E,N) :-
	N1 is N + N,
	log_ith1(K1,R,E,N1),
	K is K1 + N.

% First arg (K) is unbound
bintree1(0,E,E,1).
bintree1(K,[L|R],E,N) :- 
	N > 1,
	N2 is N // 2,
	(bintree1(K,L,E,N2)
	 ;
	 bintree1(K1,R,E,N2),
	 K is K1 + N2
	).

% log_ith_bound(Index,ListStr,Element) is like log_ith, but only
% succeeds if the Index_th element of ListStr is nonvariable and equal
% to Element.  This can be used in both directions, and is most useful
% with Index unbound, since it will then bind Index and Element for each
% nonvariable element in ListStr (in time proportional to N*logN, for N
% the number of nonvariable entries in ListStr.)

log_ith_bound(K,T,E) :- 
	nonvar(T),
	term_type(K,Ty),
	(Ty =:= 2	% integer
	 ->	log_ith2(K,T,E,1)
	 ;	log_ith3(K,T,E,1)
	).

log_ith2(K,[L|R],E,N) :-
	(K < N
	 ->	nonvar(L),bintree2(K,L,E,N)
	 ;	nonvar(R),
		K1 is K-N,
		N2 is N+N,
		log_ith2(K1,R,E,N2)
	).

bintree2(0,E,E,1).
bintree2(K,[L|R],E,N) :- 
	N > 1,
	N2 is N // 2,
	(K < N2
	 ->	nonvar(L),
		bintree2(K,L,E,N2)
	 ;	nonvar(R),
		K1 is K - N2,
		bintree2(K1,R,E,N2)
	).

log_ith3(K,[L|_R],E,N) :-
	nonvar(L),
	bintree3(K,L,E,N).
log_ith3(K,[_L|R],E,N) :-
	nonvar(R),
	N1 is N + N,
	log_ith3(K1,R,E,N1),
	K is K1 + N.

bintree3(0,E,E,1).
bintree3(K,[L|R],E,N) :- 
	N > 1,
	N2 is N // 2,
	(nonvar(L), 
	 bintree3(K,L,E,N2)
	 ;
	 nonvar(R),
	 bintree3(K1,R,E,N2),
	 K is K1 + N2
	).

%---
% length/2 that works both ways
length(L,N) :-
	var(N)
	 ->	length1(L,N)
	 ;	length2(L,N).

length1([], 0).
length1([_|R], N) :- length1(R, N1), N is N1 + 1.

length2(L,N) :-
	N =< 0
	 ->	L=[]
	 ;	N1 is N-1, L=[_|L1],
		length2(L1,N1).

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

%---
memberchk(X,[X|_]) :- !.
memberchk(X,[_|L]) :- memberchk(X,L).

%---
% subset
subset([],_).
subset([H|T],List) :-
	memberchk(H,List),
        subset(T,List).

%---
% A not so naive reverse
reverse(L, R) :- reverse_acc(L, [], R).

reverse_acc([], Acc, Acc).
reverse_acc([Head|Tail], Acc, Reversed) :-
	reverse_acc(Tail, [Head|Acc], Reversed).

%---
% Some Prologs like to call this delete!
select(Element, [Element|Rest_Elements], Rest_Elements).
select(Element, [Element1|Rest_L1], [Element1|Rest_L2]) :-
	select(Element, Rest_L1, Rest_L2).

%%% for(?I,+B1,+B2) nondeterministically binds I to all integer values
%%% from B1 to B2.  B1 and B2 must be integers, but either may be larger.
for(I,B1,B2) :-
	(B1 =< B2
	 ->	forup(I,B1,B2)
	 ;	fordown(I,B1,B2)
	).

forup(L,L,H) :- L =< H.
forup(I,L,H) :- L < H, L1 is L+1, forup(I,L1,H).

fordown(H,H,L) :- H >= L.
fordown(I,H,L) :- H > L, H1 is H-1, fordown(I,H1,L).
/* --------------------- end of file basics.P ------------------------- */
nonDeterministicGoal(InterestingVarsTerm,G,L) :-
  findall(InterestingVarsTerm,G,L).