Path: utzoo!mnetor!tmsoft!torsqnt!lethe!yunexus!ists!helios.physics.utoronto.ca!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!uunet!mcsun!ub4b!kulcs!saturnus.cs.kuleuven.ac.be
From: bimandre@saturnus.cs.kuleuven.ac.be (Andre Marien)
Newsgroups: comp.lang.prolog
Subject: Cyclic structures
Message-ID: <2026@n-kulcs.cs.kuleuven.ac.be>
Date: 19 Feb 91 08:18:59 GMT
Sender: news@cs.kuleuven.ac.be
Organization: BIM
Lines: 226
Originator: bimandre@saturnus

Cyclic structures are certainly possible, and do have some use.
As M. Johnson says in reply to D. Bowen, a database can be used but is
undesirable. It is indeed almost always "a BAD thing", to quote an expert.

Examples can always be criticized, but it helps to focus the discussion.
So, one more example: a tree with next and previous pointers.

One can build nice programs on top of this. Just one idea: in the
beginning you use an open ended tree (additions/search can be combined).
Then you 'link in' the next and previous pointers and now you can
walk around very easily and very fast.

Andre' Marien
bimandre@cs.kuleuven.ac.be

% copyrigth notice (sorry)
% author : Andre' Marien
% company : BIM
%
% please keep this notice with the code
% use is free for academic and research purposes
%

:-compatibility.

% list_to_tree(List,Tree)
%
%	List : + : list of pairs Key-Data
%
%	Tree : - :a tree with next and previous pointers instead of nil elements
%		  (called linked tree in this file)

list_to_tree(L,T) :-
	make_base_tree(L,T),
	link_tree(T) .

% make_base_tree(List,Tree)
%
%	List : + : list of pairs Key-Data
%
%	Tree : - : an open ended tree
%

make_base_tree([],T) .
make_base_tree([E|L],T) :-
	insert_base_tree(T,E),
	make_base_tree(L,T) .

insert_base_tree(T,K-D) :-
	insert_base_tree(T,K,K-D) .

insert_base_tree(T,K,KD) :- var(T), !,
	T = t(L,KD,R) .
insert_base_tree(t(L,K0-_,R),K,KD) :-
	K @=< K0, !,
	insert_base_tree(L,K,KD) .
insert_base_tree(t(L,K0-_,R),K,KD) :-
	insert_base_tree(R,K,KD) .

% link_tree(Tree)
%
%	Tree :	in  : an open ended tree
%		out : a tree with next and previous pointers instead of free vars
%		      (these are wrapped in s/1 functor)
%

link_tree(T) :- var(T), !,
	T = [] .
link_tree(T) :-
	T = t(L,KD,R),
	link_tree_l(L,[],T),
	link_tree_r(R,T,[]) .

link_tree_l(T,Prev,Next) :- var(T), !,
	T = s(Prev) .
link_tree_l(T,Prev,Next) :-
	T = t(L,KD,R),
	link_tree_l(L,Prev,T),
	link_tree_r(R,T,Next) .

link_tree_r(T,Prev,Next) :- var(T), !,
	T = s(Next) .
link_tree_r(T,Prev,Next) :-
	T = t(L,KD,R),
	link_tree_l(L,Prev,T),
	link_tree_r(R,T,Next) .

% tree_to_list_a(Tree,AscendingList)
%
%	Tree : + : a linked list
%
%	AscendingList : - : a ascending list of the Key-Data pairs
%

tree_to_list_a(T,L) :-
	min(T,MT),
	tree_to_list_a_h(MT,L) .

tree_to_list_a_h([],[]) .
tree_to_list_a_h(t(LN,D,RN),[D|L]) :-
	next(t(LN,D,RN),NT),
	tree_to_list_a_h(NT,L) .

% tree_to_list_d(Tree,DecendingList)
%
%	Tree : + : a linked tree
%
%	DecendingList : - : a decending list of the Key-Data pairs
%

tree_to_list_d(T,L) :-
	max(T,MT),
	tree_to_list_d_h(MT,L) .

tree_to_list_d_h([],[]) .
tree_to_list_d_h(t(LN,D,RN),[D|L]) :-
	previous(t(LN,D,RN),NT),
	tree_to_list_d_h(NT,L) .

% min(Tree,Node)
%
%	Tree : + : a linked tree
%
%	Node : - : the smallest Node in this Tree
%

min(T,MT) :-
	T = t(L,D,R),
	min(L,T,MT) .

min(s(_),MT,MT) .
min([],MT,MT) .
min(t(L,D,R),_,MT) :-
	min(L,t(L,D,R),MT) .

% max(Tree,Node)
%
%	Tree : + : a linked tree
%
%	Node : - : the biggest Node in this Tree
%

max(T,MT) :-
	T = t(L,D,R),
	max(R,T,MT) .

max(s(_),MT,MT) .
max([],MT,MT) .
max(t(L,D,R),_,MT) :-
	max(R,t(L,D,R),MT) .

% previous(Node,PreviousNode)
%
%	Node : + : some node of a linked tree
%
%	PreviousNode : - : the previous node in the linked tree
%

previous(t(L,D,R),P) :-
	previous_n(L,P) .

previous_n(s(P),P) .
previous_n(t(L,D,R),P) :-
	max(R,t(L,D,R),P) .

% next(Node,NextNode)
%
%	Node : + : some node of a linked tree
%
%	NextNode : - : the next node in the linked tree
%

next(t(L,D,R),P) :-
	next_n(R,P) .

next_n(s(P),P) .
next_n(t(L,D,R),P) :-
	min(L,t(L,D,R),P) .

% write_rdbl(Tree)
%
%	Tree : + : a linked tree
%
%	This predicate writes a linked tree in a more readable form.
%	If you look at it from the right of the page, it almost looks ok.
%

write_rdbl(T) :-
	rewrite_tree(T,WT),
	write_rdbl(WT,0) .

rewrite_tree(s([]),bp([])) :- ! .
rewrite_tree(s(t(_,PD,_)),bp(PD)) .
rewrite_tree(t(L,KD,R),t(NL,KD,NR)) :-
	rewrite_tree(L,NL),
	rewrite_tree(R,NR) .

write_rdbl(bp(D),N) :-
	NN is N + 3,
	spaces(NN), write('<-'), write(D), nl .
write_rdbl(t(L,KD,R),N) :-
	NN is N + 3,
	write_rdbl(R,NN),		% yes, this is odd, but ok
	spaces(NN), write(KD), nl,
	write_rdbl(L,NN) .		% yes, this is odd, but ok

% some tests (?)
%

list([4-vier,8-acht,2-twee,1-een,3-drie,5-vijf,6-zes,7-zeven]) .
list([e-1,f-2,a-3,c-4,b-5,d-6]) .

t0 :-
	list(L),
	list_to_tree(L,T),
	write_rdbl(T), nl .

t1 :-
	list(L), write(L), nl,
	list_to_tree(L,T), write_rdbl(T), nl,
	tree_to_list_a(T,AL), write(AL), nl .

t2 :-
	list(L), write(L), nl,
	list_to_tree(L,T), write_rdbl(T), nl,
	tree_to_list_d(T,AL), write(AL), nl .