%   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),

        writelist(List).





%

% The predicates below are useful for input and output.

%



/* 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]).

%-------------------------------------------------------
% 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.