%------------------------------------------------------------- % 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), write(List). % 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([ ], Tree,Tree). insert_list_bst([Head|Tail],Tree0,Tree):- insert_bst(Head,Tree0,Tree1),insert_list_bst(Tail,Tree1,Tree). /* wrapper functor for inserting item to tdTree */ insert_list_td([ ],Tree ,Tree). insert_list_td([Head|Tail],Tree0,Tree):- insertTD(Head,Tree0,Tree1), insert_list_td(Tail,Tree1,Tree). /* Tokenize the list */ tokenize([ ],[ ]). tokenize([Line|RestLines],Words) :- phrase(words(LineWords),Line), append(Words1,RestWords,Words), tokenize(RestLines,RestWords). /* 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 */ /* Lines is list of lines created by split */ split(Text,Lines) :- split(Text,[],Lines). /* The actual work that split does, is here in split/3 */ % split(Text,Line,Lines) split([],[ ],[ ]). split([ ],Line,[Line]):- Line \= []. split(['\n'|RestText],[ ],Lines) :- split(RestText,[],Lines). split(['\n'|RestText],Line,[Line|Lines]):- Line \= [], split(RestText,[],Lines). split([Char|RestText],Line,Lines) :- Char \= '\n', append(Line,[Char],NewLine), split(RestText,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,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. searchBST(V,bst(Left,N,_),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,T,nil,empty,empty,empty,empty),tdTree(X,S,T,empty,empty,empty,empty)):-X@S,X@T. insertTD(X,tdTree(S1,S2,S3,C1,C2,C3,C4),tdTree(S1,S2,S3,R1,C2,C3,C4)):-X@S1,X@S2,X@S3,\+ isFourNode(C4),insertTD(X,C4,R4). insertTD(X,tdTree(S1,S2,S3,C1,C2,C3,C4),Result):-X@S1,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,C2,Count1,Count). searchTD(X,tdTree(S,_,nil,C1,_,_,empty),Count0,Count):-X@S,X@T,Count1 is Count0 + 1, searchTD(X,C3,Count1,Count). searchTD(X,tdTree(S,_,_,C1,_,_,_),Count0,Count):-X@S,X@T,X@K,Count1 is Count0 + 1, searchTD(X,C4,Count1,Count). %------------------------------------------------------------- isFourNode(tdTree(_,_,Key3,_,_,_,_)) :- Key3 \= nil.