Rosetta Code

Doubly-linked list/Definition: Difference between revisions

Page Discussion

Doubly-linked list/Definition (view source)

Revision as of 02:07, 4 October 2013

845 bytes removed ,  10 years ago
→‎{{header|ALGOL 68}}: now using operators
(→‎{{header|ALGOL 68}}: now using operators)
Line 18:
{{works with|ALGOL 68|Revision 1 - one extension to language used - PRAGMA READ - a non standard feature similar to C's #include directive.}}{{works with|ALGOL 68G|Any - tested with release algol68g-2.7}}
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}
'''''File: prelude/Doubly-linked_list_Elementlinked_list_Link.a68'''<lang algol68># -*- coding: utf-8 -*- #
COMMENT REQUIRES:
MODE NODENEW = STRUCT (
MODE VALUE = ~;
NODE pred,
# For example: #
succ,
MODE VALUE = UNION(INT, REAL, COMPL)
DATA value
END COMMENT
 
MODE LINKNEW = STRUCT (
LINK next, prev,
VALUE value
);
 
MODE NODELINK = REF NODENEWLINKNEW;
 
SKIP</lang>'''File: prelude/Doubly-linked_list_Classlinked_list_Operator.a68'''<lang algol68># -*- coding: utf-8 -*- #
MODE LISTNEW = LINKNEW;
STRUCT (
MODE LIST = REF LISTNEW;
PROC LIST new list,
PROC (LIST)BOOL is empty,
PROC (LIST)NODE get head,
get tail,
PROC (LIST, NODE)NODE add tail,
add head,
PROC (LIST)NODE remove head,
remove tail,
PROC (LIST, NODE, NODE)NODE insert after,
PROC (LIST, NODE)NODE remove node
) list;
 
OP LISTINIT = (LIST self)LIST: (
SKIP</lang>'''File: prelude/Doubly-linked_list_Definition.a68'''<lang algol68># -*- coding: utf-8 -*- #
self := (self, self, ~);
MODE LIST = REF NODENEW;
self
 
new list OF list := LIST: (
HEAP NODENEW master link;
master link := (master link, master link, ~);
master link
);
 
isOP emptyISEMPTY OF list := (LIST self)BOOL:
(LIST(predprev OF self) :=: LIST(self)) AND (LIST(self) :=: LIST(succnext OF self));
 
getOP headHEAD OF list := (LIST self)NODELINK: next OF self;
succ OF self;
 
getOP tailTAIL OF list := (LIST self)NODELINK: prev OF self;
pred OF self;
 
# insert after #
add tail OF list := (LIST self, NODE node)NODE:
OP +:= = (LINK cursor, LINK link)LINK: (
(insert after OF list)(self, pred OF self, node);
next OF link := next OF cursor;
prev OF link := cursor;
next OF cursor := link;
prev OF next OF link := link;
link
);
 
# insert before #
add head OF list := (LIST self, NODE node)NODE:
OP +=: = (insertLINK afterlink, OFLINK listcursor)(self,LINK: succprev OF self,cursor node)+:= link;
 
# delete current and step forward #
remove head OF list := (LIST self)NODE:
OP -:= = (LIST ignore, LINK link)LINK: (
(remove node OF list)(self, succ OF self);
next OF prev OF link := next OF link;
 
remove tail prev OF listnext OF link := (LISTprev self)NODE:OF link;
next OF link := prev OF link := NIL; # garbage collection hint #
(remove node OF list)(self, pred OF self);
link
 
insert after OF list := (LIST self, NODE cursor, NODE node)NODE: (
succ OF node := succ OF cursor;
pred OF node := cursor;
succ OF cursor := node;
pred OF succ OF node := node;
node
);
 
# delete current and step backward #
remove node OF list := (LIST self, NODE node)NODE: (
PRIO -=: = 1;
succ OF pred OF node := succ OF node;
OP -=: = (LIST link, LIST ignore)LINK: (
pred OF succ OF node := pred OF node;
ignore -:= link; prev OF link
succ OF node := pred OF node := NIL; # garbage collection hint #
node
);
 
PRIO ISIN = 1; # low priority #
SKIP</lang>'''File: test/Doubly-linked_list_Usage.a68'''<lang algol68>#!/usr/bin/a68g --script #
 
OP ISIN = (LINK link, LIST self)BOOL:
link ISNT LINK(self);
 
SKIP</lang>'''File: test/Doubly-linked_list_Operator_Usage.a68'''<lang algol68>#!/usr/bin/a68g --script #
# -*- coding: utf-8 -*- #
MODE VALUE = STRING; # user defined data type #
PR READ "prelude/Doubly-linked_list_Element.a68" PR;
PR READ "prelude/Doubly-linked_list_Classlinked_list_Link.a68" PR;
PR READ "prelude/Doubly-linked_list_Definitionlinked_list_Operator.a68" PR;
MODE DATA = STRING; # user defined data type #
 
main: (
 
[]DATAVALUE sample = ("Was", "it", "a", "cat", "I", "saw");
LIST example list := LISTINIT HEAP LISTNEW;
 
LINK this;
LIST list a := new list OF list;
 
NODE tmp;
 
IF list a :/=: REF LIST(NIL) THEN # technically "list a" is never NIL #
# Add some data to a list #
FOR i TO UPB sample DO
tmpthis := HEAP NODENEWLINKNEW;
value OF this := sample[i];
IF tmp :/=: NODE(NIL) THEN # technically "tmp" is never NIL #
TAIL example list value OF tmp +:= sample[i];this
OD;
(add tail OF list)(list a, tmp)
FI
OD;
 
# Iterate throught the list forward #
NODE nodethis := (getHEAD head OFexample list)(list a);
print("Iterate forward: ");
WHILE this nodeISIN :/=:example NODE(list a) DO
print((value OF nodethis, " "));
nodethis := succnext OF nodethis
OD;
print(new line);
 
# Iterate throught the list backward #
nodethis := (getTAIL tail OFexample list)(list a);
print("Iterate backward: ");
WHILE this nodeISIN :/=:example NODE(list a) DO
print((value OF nodethis, " "));
nodethis := predprev OF nodethis
OD;
print(new line);
 
# Finally empty the list #
print("Empty from tail: ");
WHILE NOT (isISEMPTY empty OFexample list)(list a) DO
this := (example list tmp -:= (removeTAIL tail OFexample list)(list a);
print((value OF tmpthis, " "))
OD;
# sweep heap #
print(new OD;line)
print(new line)
# sweep heap #
FI
)</lang>'''Output:'''
<pre>
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/94662"