%-------------------------------------------------------------
% Prolog Skeleton for assign3
% compile with
% gplc --no-top-level MainA.pl
% produces executable assign3
%
% The following is a required directive when compiling. You
% may comment it out when using the interpreter though.
%
:- initialization(main).
%
% Our main predicate. You should extend this as needed.
% Right now it just reads input from stdin and breaks it
% into a list of lines from the file.
%
main :- getContents(Contents),
split(Contents,List),
tokenize(List,W),
insert_list_bst(W,nil,ResultA),
insert_list_td(W,nil,ResultB),
searchBST(Key,ResultA,0,Count),
searchTD(Key,ResultB,0,Count2).
get_string([Head|Tail],Result):- atom_chars(Head,Result),get_string(Tail,
%
% The predicates below are useful for input and output.
%
/* wrapper functor for inserting item to BSTree */
insert_list_bst([],_,_).
insert_list_bst([Head|Tail],CurTree,Result):- insert_bst(Head,CurTree,Result0),insert_list_bst(Tail,Result0,Result).
/* wrapper functor for inserting item to tdTree */
insert_list_td([],_,_).
insert_list_td([Head|Tail],CurTree,Result):- insertTD(Head,CurTree,Result0),insert_list_td(Tail,Result0,Result).
/* Tokenize the list */
tokenize([],_).
tokenize([Head|Tail],W):- phrase(words(W),Head, []),tokenize(Tail,W).
/* Display a List of atoms on a line */
writelist([]):- nl.
writelist([First|Rest]) :- write(First), writelist(Rest).
/* Character based getContents */
getContents(Contents):- get_char(Char), getRest(Char,Contents).
getRest(end_of_file,[]) :- !.
getRest(Char,[Char|Rest]):-get_char(Next), getRest(Next,Rest).
/* Split */
split(String,List) :- split(String,[],List).
/* The actual work that split does, is here in split/3 */
split([],[],[]).
split([],Line,[Line]).
split(['\n'|Tail],[],Lines) :- split(Tail,[],Lines).
split(['\n'|Tail],Line,[Line|Lines]):- split(Tail,[],Lines).
split([Head|Tail],Line,Lines) :- append(Line,[Head],NewLine), split(Tail,NewLine,Lines).
%------------------------------------------------------------------
word(W) --> char_seq(W).
words([W]) --> word(W).
words([W]) --> word(W), whitespace.
words([W|Ws]) --> word(W), whitespace, words(Ws).
words([W|Ws]) --> word(W), delimeter, words(Ws).
whitespace --> [' '].
whitespace --> [' '], whitespace.
char_seq([C]) --> char(C).
char_seq([C|Cs]) --> char(C), char_seq(Cs).
% char_seq([C|Cs]) --> char(C), delimeter, char_seq(Cs).
char(C) --> [C], {\+ C = ' '}.
delimeter --> ['.'],delimeter;['['],delimeter.
delimeter --> ['.'];['\n'];['['];[']'];['{'];['}'];['('];[')'].
%-------------------------------------------------------
% Binary search tree & 2-3-4 tree (top-down) definitions
% bst(Left,Root,Right).
% tdTree(N1,N2,N3,T1,T2,T3,T4).
%-------------------------------------------------------
% Insert a new item to binary tree
insert_bst(X,nil,bst(empty,X,empty)).
insert_bst(X,bst(empty,S,Right),bst(bst(empty,X,empty),S,Right)):- X@<S.
insert_bst(X,bst(Left,S,empty),bst(Left,S,bst(empty,X,empty))):-X@>S.
insert_bst(X,bst(Left,S,Right),bst(Left,S,NewRight)):- X@>S, Right\=empty, insert_bst(X,Right,NewRight).
insert_bst(X,bst(Left,S,Right),bst(NewLeft,S,Right)):- X@<S, Left\=empty, insert_bst(X,Left,NewLeft).
%-------------------------------------------------------
% Search for a given item in binary tree. Count is used to keep track
% of number of comparisons done.
searchBST(_,nil,Count,Count).
searchBST(V,bst(_,V,_),Count, Count).
searchBST(V,bst(empty,S,empty),Count,Count):-V\=S.
searchBST(V,bst(empty,S,_),Count,Count):-V@<S.
searchBST(V,bst(_,S,empty),Count,Count):-V@>S.
searchBST(V,bst(Left,N,_),Count0, Count):-V@<N,Count1 is Count0 + 1, searchBST(V,Left,Count1, Count).
searchBST(V,bst(_,N,Right),Count0, Count):-V@>N,Count1 is Count0 + 1, searchBST(V,Right,Count1,Count).
%-------------------------------------------------------
% Insert a new item to 2-3-4 Tree
insertTD(X,nil,tdTree(X,nil,nil,empty,empty,empty,empty)).
insertTD(X,tdTree(S,nil,nil,empty,empty,empty,empty),tdTree(X,S,nil,empty,empty,empty)):-X@<S.
insertTD(X,tdTree(S,nil,nil,empty,empty,empty,empty),tdTree(S,X,nil,empty,empty,empty)):-X@>S.
insertTD(X,tdTree(S,T,nil,empty,empty,empty,empty),tdTree(X,S,T,empty,empty,empty,empty)):-X@<S.
insertTD(X,tdTree(S,T,nil,empty,empty,empty,empty),tdTree(S,X,T,empty,empty,empty,empty)):-X@>S,X@<T.
insertTD(X,tdTree(S,T,nil,empty,empty,empty,empty),tdTree(S,T,X,empty,empty,empty,empty)):-X@>T.
insertTD(X,tdTree(S1,S2,S3,C1,C2,C3,C4),tdTree(S1,S2,S3,R1,C2,C3,C4)):-X@<S1,\+ isFourNode(C1),insertTD(X,C1,R1).
insertTD(X,tdTree(S1,S2,S3,C1,C2,C3,C4),tdTree(S1,S2,S3,C1,R2,C3,C4)):-X@>S1,X@<S2,\+ isFourNode(C2),insertTD(X,C2,R2).
insertTD(X,tdTree(S1,S2,S3,C1,C2,C3,C4),tdTree(S1,S2,S3,C1,C2,R3,C4)):-X@>S2,X@<S3,\+ isFourNode(C3),insertTD(X,C3,R3).
insertTD(X,tdTree(S1,S2,S3,C1,C2,C3,C4),tdTree(S1,S2,S3,C1,C2,C3,R4)):-X@>S3,\+ isFourNode(C4),insertTD(X,C4,R4).
insertTD(X,tdTree(S1,S2,S3,C1,C2,C3,C4),Result):-X@<S1,isFourNode(C1),splitNode(tdTree(S1,S2,S3,C1,C2,C3,C4),C1,a,Result0),insertTD(X,Result0,Result).
insertTD(X,tdTree(S1,S2,nil,C1,C2,C3,C4),Result):-X@>S1,X@<S2,isFourNode(C2),splitNode(tdTree(S1,S2,nil,C1,C2,C3,C4),C2,b,Result0),insertTD(X,Result0,Result).
insertTD(X,tdTree(S1,S2,nil,C1,C2,C3,C4),Result):-X@>S2,isFourNode(C3),splitNode(tdTree(S1,S2,nil,C1,C2,C3,C4),C3,c,Result0),insertTD(X,Result0,Result).
insertTD(X,tdTree(S1,S2,S3,C1,C2,C3,C4),Result):-S3 \= nil, isFourNode(C4),splitNode(nil,tdTree(S1,S2,S3,C1,C2,C3,C4),a,Result0),insertTD(X,Result0,Result).
%------------------------------------------------------------
splitNode(nil,tdTree(T1,T2,T3,C1,C2,C3,C4),_,tdTree(T2,nil,nil,tdTree(T1,nil,nil,C1,C2,empty,empty),tdTree(T3,nil,nil,C3,C4,empty,empty),empty,empty)).
splitNode(tdTree(S,nil,nil,_,K2,empty,empty),tdTree(T1,T2,T3,C1,C2,C3,C4),a,tdTree(T2,S,nil,tdTree(T1,nil,nil,C1,C2,empty,empty),tdTree(T3,nil,nil,C3,C4,empty,empty),K2,empty)).
splitNode(tdTree(S,nil,nil,K1,_,empty,empty),tdTree(T1,T2,T3,C1,C2,C3,C4),b,tdTree(S,T2,nil,K1,tdTree(T1,nil,nil,C1,C2,empty),tdTree(T3,nil,nil,C3,C4,empty,empty),empty)).
splitNode(tdTree(S1,S2,nil,_,K2,K3,empty),tdTree(T1,T2,T3,C1,C2,C3,C4),a,tdTree(T2,S1,S2,
tdTree(T1,nil,nil,C1,C2,empty,empty),tdTree(T3,nil,nil,C3,C4,empty,empty),K2,K3)).
splitNode(tdTree(S1,S2,nil,K1,_,K3,empty),tdTree(T1,T2,T3,C1,C2,C3,C4),b,tdTree(S1,T2,S2,K1,tdTree(T1,nil,nil,C1,C2,empty,empty),tdTree(T3,nil,nil,C3,C4,empty,empty),K3)).
splitNode(tdTree(S1,S2,nil,K1,K2,_,empty),tdTree(T1,T2,T3,C1,C2,C3,C4),c,tdTree(S1,S2,T2,K1,K2,tdTree(T1,nil,nil,C1,C2,empty,empty),tdTree(T3,nil,nil,C3,C4,empty,empty))).
%-----------------------------------------------------------
/*
Search the 2-3-4 tree. Signiture of the function is:
searchTD(Key,Root,Count(always passed zero at start),Count(result))
*/
searchTD(_,nil,Count,Count).
searchTD(X,tdTree(K1,K2,K3,_,_,_,_),Count,Count):- X=K1;X=K2;X=K3.
searchTD(X,tdTree(S,nil,nil,C1,_,empty,empty),Count0,Count):-X@<S,Count1 is Count0 + 1, searchTD(X,C1,Count1,Count).
searchTD(X,tdTree(S,nil,nil,_,C2,empty,empty),Count0,Count):-X@>S,Count1 is Count0 + 1, searchTD(X,C2,Count1,Count).
searchTD(X,tdTree(S,_,nil,C1,_,_,empty),Count0,Count):-X@<S,Count1 is Count0 + 1, searchTD(X,C1,Count1,Count).
searchTD(X,tdTree(S,T,nil,_,C2,_,empty),Count0,Count):-X@>S,X@<T,Count1 is Count0 + 1, searchTD(X,C2,Count1,Count).
searchTD(X,tdTree(_,T,nil,_,_,C3,empty),Count0,Count):-X@>T,Count1 is Count0 + 1, searchTD(X,C3,Count1,Count).
searchTD(X,tdTree(S,_,_,C1,_,_,_),Count0,Count):-X@<S,Count1 is Count0 +1, searchTD(X,C1,Count1,Count).
searchTD(X,tdTree(S,T,_,_,C2,_,_),Count0,Count):-X@>S,X@<T,Count1 is Count0 + 1, searchTD(X,C2,Count1,Count).
searchTD(X,tdTree(_,T,K,_,_,C3,_),Count0,Count):-X@>T,X@<K,Count1 is Count0 + 1, searchTD(X,C3,Count1,Count).
searchTD(X,tdTree(_,_,K,_,_,_,C4),Count0,Count):-X@>K,Count1 is Count0 + 1, searchTD(X,C4,Count1,Count).
%-------------------------------------------------------------
isFourNode(tdTree(_,_,Key3,_,_,_,_)) :- Key3 \= nil.