MODULE ObjectOrientedLists
IMPORT
Node, OutExt;
TYPE
(** Lists.List class: generic singly-linked non-circular list *)
List* = POINTER TO ListDesc;
ListDesc* = RECORD
head*: Node.Node;
current*: Node.Node;
END;
(**
head: the sentinel node of any given list, always has its .next-property pointing to the first node of a list, in the case of a circular doubly-linked list its .previous-property to the last node in the list
current: pointer to the element the last operation was performed on, in case of a delete it will point to the node prior of the deleted node, enumerating in any direction does not change it (or should it?)
*)
(** Lists: CircularList class: generic singly-linked circular list *)
CircularList* = POINTER TO CircularListDesc;
CircularListDesc = RECORD
(ListDesc)
END;
(** Lists: DoublyLinkedList class: generic doubly-linked non-circular list *)
DoublyLinkedList* = POINTER TO DoublyLinkedListDesc;
DoublyLinkedListDesc = RECORD
(ListDesc)
END;
(** Lists: CircularDoublyLinkedList class: generic circular doubly-linked list *)
CircularDoublyLinkedList* = POINTER TO CircularDoublyLinkedListDesc;
CircularDoublyLinkedListDesc = RECORD
(ListDesc)
END;
(** type for procedures you wish to execute on each element (= enumerating) *)
NodeProcedure* = PROCEDURE(node: Node.Node);
PROCEDURE (this: List) Empty*();
(*
Description: empty the list
Parameters: -
Return: -
Algorithm: -
*)
BEGIN
this^.head^.next := NIL;
this^.SetCurrent(this^.head);
END Empty;
PROCEDURE (this: List) Enumerate*(nodeProcedure: NodeProcedure);
(*
Description: execute a procedure on every node in the list (e.g. a print procedure)
Parameters:
- nodeProcedure: the procedure to perform on each node
Return: -
Algorithm: -
*)
VAR
currentNode: Node.Node;
BEGIN
currentNode := this^.head^.next;
WHILE currentNode # NIL DO
nodeProcedure(currentNode);
currentNode := currentNode^.next;
END;
END Enumerate;
PROCEDURE (this: List) EnumerateReverse*(nodeProcedure: NodeProcedure);
(*
Description: execute a procedure on every node, but in the opposite order
Parameters:
- nodeProcedure: the procedure to perform on each node
Return: -
Algorithm: for singly-linked lists one of the dirtiest things possible, it takes n! steps (why not make it n^(n!)?), instead of n for List.Enumerate()
*)
VAR
currentNode: Node.Node;
BEGIN
currentNode := this^.ReturnLastNode();
WHILE currentNode # this^.head DO
nodeProcedure(currentNode);
currentNode := this^.ReturnPreviousNode(currentNode);
END;
END EnumerateReverse;
PROCEDURE (this: List) Init*();
(*
Description: initialize the list, thus creating the sentinel node
Parameters: -
Return: -
Algorithm: -
*)
VAR
head: Node.Node;
BEGIN
NEW(head);
this^.head := head;
this^.SetCurrent(this^.head);;
END Init;
PROCEDURE (this: List) IsEmpty*(): BOOLEAN;
(*
Description: checks whether a list is empty or not
Parameters: -
Return: TRUE if it's empty, FALSE if it's not
Algorithm: -
*)
BEGIN
IF this^.head^.next = NIL THEN
RETURN TRUE;
END;
RETURN FALSE;
END IsEmpty;
PROCEDURE (this: List) NodeDelete*(node: Node.Node);
(*
Description: delete a certain node from the list
Parameters:
- node: the node which should be deleted
Return: -
Algorithm: -
*)
VAR
previousNode: Node.Node;
BEGIN
previousNode := this^.ReturnPreviousNode(node);
previousNode^.next := node^.next;
this^.SetCurrent(previousNode);
END NodeDelete;
PROCEDURE (this: List) NodeExchange*(firstNode: Node.Node; secondNode: Node.Node);
(*
Description: exchanges two nodes, e.g. let the first one get the place of the second and vice versa
Parameters:
- firstNode, secondNode: the nodes that must be exchanged
Return: -
Algorithm: -
*)
VAR
firstNodePrevious, secondNodePrevious: Node.Node;
BEGIN
(* if the first node is the second node, an exchange is impossible *)
IF firstNode = secondNode THEN
RETURN;
END;
(* we should find a nicer way of exchanging nodes next to eachother *)
IF firstNode^.next = secondNode THEN
this^.NodeDelete(firstNode);
this^.NodeInsertAfter(firstNode, secondNode);
ELSIF secondNode^.next = firstNode THEN
this^.NodeDelete(secondNode);
this^.NodeInsertAfter(secondNode, firstNode);
ELSE
firstNodePrevious := this^.ReturnPreviousNode(firstNode);
secondNodePrevious := this^.ReturnPreviousNode(secondNode);
this^.NodeDelete(firstNode);
this^.NodeDelete(secondNode);
this^.NodeInsertAfter(firstNode, secondNodePrevious);
this^.NodeInsertAfter(secondNode, firstNodePrevious);
END;
END NodeExchange;
PROCEDURE (this: List) NodeInsert*(node: Node.Node);
(*
Description: insert a node at the end of the list
Parameters:
- node: the node that has to be inserted
Return: -
Algorithm: -
*)
VAR
lastNode: Node.Node;
BEGIN
lastNode := this^.ReturnLastNode();
lastNode^.next := node;
this^.SetCurrent(node);
END NodeInsert;
PROCEDURE (this: List) NodeInsertAfter*(node: Node.Node; currentNode: Node.Node);
(*
Description: insert a node after a given node
Parameters:
- node: the new node
- currentNode: the node after which the new node should be inserted
Return: -
Algorithm: -
*)
VAR
nextNode: Node.Node;
BEGIN
IF currentNode^.next = NIL THEN
currentNode^.next := node;
ELSE
nextNode := currentNode^.next;
currentNode^.next := node;
node^.next := nextNode;
END;
this^.SetCurrent(node);
END NodeInsertAfter;
PROCEDURE (this: List) Print*();
(*
Description: print the list, = call the PrintNode() pass-through function for each node through List.Enumerate(), mostly for debugging purposes
Parameters: -
Return: -
Algoritm: -
*)
VAR
currentNode: Node.Node;
BEGIN
IF this^.IsEmpty() THEN
OutExt.String("De lijst is leeg.");
OutExt.Ln;
RETURN;
END;
OutExt.String("Inhoud van de lijst:");
OutExt.Ln;
this^.Enumerate(Node.PrintNode);
OutExt.Ln;
END Print;
PROCEDURE (this: List) ReturnLastNode*(): Node.Node;
(*
Description: loop through the list to get to the last element
Parameters: -
Return: the last node of the list
Algorithm: -
*)
VAR
currentNode: Node.Node;
BEGIN
currentNode := this^.head;
WHILE currentNode^.next # NIL DO
currentNode := currentNode^.next;
END;
RETURN currentNode;
this^.SetCurrent(currentNode);
END ReturnLastNode;
PROCEDURE (this: List) ReturnPreviousNode*(node: Node.Node): Node.Node;
(*
Description: find the node prior to a given node
Parameters:
- node: the node after the node we which to look up
Return: the node before the given node
Algorithm: -
*)
VAR
currentNode: Node.Node;
BEGIN
currentNode := this^.head;
WHILE currentNode^.next # NIL DO
IF currentNode^.next = node THEN
RETURN currentNode;
END;
currentNode := currentNode^.next;
END;
this^.SetCurrent(currentNode);
END ReturnPreviousNode;
PROCEDURE (this: List) SetCurrent*(node: Node.Node);
(*
Description: sets the pointer of the .current-property in List to the element the last operation was performed on
Parameters:
- node: the element subject to the last operation
Return: -
Algorithm: -
*)
BEGIN
this^.current := node;
END SetCurrent;
(**
methods for the Lists: CircularList class
*)
PROCEDURE (this: CircularList) Empty*();
(*
Description: empty the list (sentinel node pointing to itself)
Parameters: -
Return: -
Description: -
*)
BEGIN
this^.head^.next := this^.head;
this^.SetCurrent(this^.head);
END Empty;
PROCEDURE (this: CircularList) Enumerate*(nodeProcedure: NodeProcedure);
(*
Description: execute a given procedure for all the nodes in the list
Parameters:
- nodeProcedure: the procedure to perform on each node
Return: -
Algorithm: -
*)
VAR
currentNode: Node.Node;
BEGIN
currentNode := this^.head^.next;
WHILE currentNode # this^.head DO
nodeProcedure(currentNode);
currentNode := currentNode^.next;
END;
END Enumerate;
PROCEDURE (this: CircularList) Init*();
(*
Description: initializes the circular list, thus creating the sentinel node and making it point to itself
Parameters: -
Return: -
Algorithm: -
*)
VAR
head: Node.Node;
BEGIN
NEW(head);
head^.next := head;
this^.head := head;
this^.SetCurrent(this^.head);
END Init;
PROCEDURE (this: CircularList) IsEmpty*(): BOOLEAN;
(*
Description: check whether the list is empty or not (= the sentinel node pointing to itself)
Parameters: -
Return: TRUE if the list is empty, FALSE is not
Algorithm: -
*)
BEGIN
IF this^.head^.next = this^.head THEN
RETURN TRUE;
ELSE
RETURN FALSE;
END;
END IsEmpty;
PROCEDURE (this: CircularList) NodeDelete*(node: Node.Node);
(*
Description: delete a given node from the list
Parameters:
- node: the node that has to be deleted
Return: -
Algorithm: -
*)
VAR
previousNode: Node.Node;
BEGIN
previousNode := this^.ReturnPreviousNode(node);
previousNode^.next := node^.next;
this^.SetCurrent(previousNode);
END NodeDelete;
PROCEDURE (this: CircularList) NodeInsert*(node: Node.Node);
(*
Description: insert a given node at the end of the list
Parameters:
- node: the to be inserted node
Return: -
Algorithm: -
*)
VAR
lastNode: Node.Node;
BEGIN
(* get the last node, after which it will be inserted *)
lastNode := this^.ReturnLastNode();
lastNode^.next := node;
node^.next := this^.head;
this^.SetCurrent(node);
END NodeInsert;
PROCEDURE (this: CircularList) ReturnLastNode*(): Node.Node;
(*
Description: return the last node of the list
Parameters: -
Return: the last node in the list
Algorithm: -
*)
VAR
currentNode: Node.Node;
BEGIN
currentNode := this^.head^.next;
WHILE currentNode^.next # this^.head DO
currentNode := currentNode^.next;
END;
this^.SetCurrent(currentNode);
RETURN currentNode;
END ReturnLastNode;
(**
methods for the Lists: DoublyLinkedList class
*)
PROCEDURE (this: DoublyLinkedList) Empty*();
(*
Description: empty a doubly-linked list
Parameters: -
Return: -
Algorithm: -
*)
BEGIN
this^.head^.next := NIL;
this^.SetCurrent(this^.head);
END Empty;
PROCEDURE (this: DoublyLinkedList) EnumerateReverse*(nodeProcedure: NodeProcedure);
(*
Description: execute a procedure on all the nodes in reversed order
Parameters:
- nodeProcedure: the to be executed procedure
Return: -
Algorithm: something nicer than a O(n!) approach, this one is executed in O(n) (1 pass forwards, 1 pass backwards)
*)
VAR
currentNode: Node.Node;
BEGIN
currentNode := this^.ReturnLastNode();
WHILE currentNode # this^.head DO
nodeProcedure(currentNode);
currentNode := this^.ReturnPreviousNode(currentNode);
END;
END EnumerateReverse;
PROCEDURE (this: DoublyLinkedList) NodeDelete*(node: Node.Node);
(*
Description: delete a given node from the list
Parameters:
- node: the to be deleted node
Return: -
Algorithm: -
*)
BEGIN
this^.SetCurrent(node(Node.DoublyLinkedNode)^.previous);
IF node^.next = NIL THEN
node(Node.DoublyLinkedNode)^.previous^.next := NIL;
ELSE
node^.next(Node.DoublyLinkedNode)^.previous := node(Node.DoublyLinkedNode)^.previous;
node(Node.DoublyLinkedNode)^.previous^.next := node^.next;
END;
END NodeDelete;
PROCEDURE (this: DoublyLinkedList) NodeInsert*(node: Node.Node);
(*
Description: insert a node at the end of the list
Parameters:
- node: the to be inserted node
Return: -
Algorithm: -
*)
VAR
lastNode: Node.Node;
BEGIN
(* determine the last node of the list *)
lastNode := this^.ReturnLastNode();
lastNode^.next := node;
node(Node.DoublyLinkedNode)^.previous := lastNode;
node^.next := NIL;
this^.SetCurrent(node);
END NodeInsert;
PROCEDURE (this: DoublyLinkedList) NodeInsertAfter*(node: Node.Node; currentNode: Node.Node);
(*
Description: insert a node after a given node
Parameters:
- node: the new node
- currentNode: the node after which it should be inserted
Return: -
Algorithm: -
*)
BEGIN
currentNode^.next(Node.DoublyLinkedNode)^.previous := node;
node^.next := currentNode^.next;
currentNode^.next := node;
node(Node.DoublyLinkedNode)^.previous := currentNode;
this^.SetCurrent(node);
END NodeInsertAfter;
PROCEDURE (this: DoublyLinkedList) ReturnPreviousNode*(node: Node.Node): Node.Node;
(*
Description: give the node prior to a given node
Parameters:
- node: the node you have to look in front of
Return: the node prior to the given node
Algorithm: something nicer than a plain List.ReturnPreviousNode(), as this one makes use of node^.previous is possible, resulting in 0(1)
*)
VAR
previousNode: Node.Node;
BEGIN
IF this^.head = node THEN
(* a person will have to make sure he stops calling this function after a while *)
previousNode := this^.head;
ELSE
previousNode := node(Node.DoublyLinkedNode)^.previous;
END;
this^.SetCurrent(previousNode);
RETURN previousNode;
END ReturnPreviousNode;
(**
methods for the Lists: CircularDoublyLinkedList class
*)
PROCEDURE (this: CircularDoublyLinkedList) Empty*();
(*
Description: empty the list
Parameters: -
Return: -
Algorithm: -
*)
BEGIN
this^.head^.next := this^.head;
this^.head(Node.DoublyLinkedNode)^.previous := this^.head;
this^.SetCurrent(this^.head);
END Empty;
PROCEDURE (this: CircularDoublyLinkedList) Enumerate*(nodeProcedure: NodeProcedure);
(*
Description: execute a given procedure on all the nodes in the list
Parameters:
- nodeProcedure: the to be executed procedure
Return: -
Algorithm: -
*)
VAR
currentNode: Node.Node;
BEGIN
currentNode := this^.head^.next;
WHILE currentNode # this^.head DO
nodeProcedure(currentNode);
currentNode := currentNode^.next;
END;
END Enumerate;
PROCEDURE (this: CircularDoublyLinkedList) EnumerateReverse*(nodeProcedure: NodeProcedure);
(*
Description: execute a procedure on all the nodes, in reversed order
Parameters:
- nodeProcedure: the to be executed procedure
Return: -
Algorithm: something way nicer, with O(n) complexity
*)
VAR
currentNode: Node.Node;
BEGIN
currentNode := this^.ReturnLastNode();
WHILE currentNode # this^.head DO
nodeProcedure(currentNode);
currentNode := this^.ReturnPreviousNode(currentNode);
END;
END EnumerateReverse;
PROCEDURE (this: CircularDoublyLinkedList) Init*();
(*
Description: initializes the list, thus setting the sentinel node and letting it point to itself in both directions
Parameters: -
Return: -
Algorithm: -
*)
VAR
head: Node.DoublyLinkedNode;
BEGIN
NEW(head);
head^.next := head;
head^.previous := head;
this^.head := head;
this^.SetCurrent(this^.head);
END Init;
PROCEDURE (this: CircularDoublyLinkedList) IsEmpty*(): BOOLEAN;
(*
Description: check whether a list is empty or not (sentinel pointing to itself)
Parameters: -
Return: TRUE if the list is empty, FALSE if not
Algorithm: -
*)
BEGIN
IF this^.head^.next = this^.head THEN
RETURN TRUE;
ELSE
RETURN FALSE;
END;
END IsEmpty;
PROCEDURE (this: CircularDoublyLinkedList) NodeDelete*(node: Node.Node);
(*
Description: delete a given node from the list
Parameters:
- node: the node to be deleted
Return: -
Algorithm: -
*)
BEGIN
this^.SetCurrent(node(Node.DoublyLinkedNode)^.previous);
node(Node.DoublyLinkedNode)^.previous^.next := node^.next;
node^.next(Node.DoublyLinkedNode)^.previous := node(Node.DoublyLinkedNode)^.previous;
END NodeDelete;
PROCEDURE (this: CircularDoublyLinkedList) NodeInsert*(node: Node.Node);
(*
Description: insert a node at the end of the list
Parameters:
- node: the to be inserted node
Return: -
Algorithm: -
*)
VAR
lastNode: Node.Node;
BEGIN
lastNode := this^.ReturnLastNode();
lastNode^.next := node;
node(Node.DoublyLinkedNode)^.previous := lastNode;
node^.next := this^.head;
this^.head(Node.DoublyLinkedNode)^.previous := node;
this^.SetCurrent(node);
END NodeInsert;
PROCEDURE (this: CircularDoublyLinkedList) NodeInsertAfter(node: Node.Node; currentNode: Node.Node);
(*
Description: insert a node after a given node
Parameters:
- node: the node to be inserted
- currentNode: the node after which it should be inserted
Return: -
Algorithm: -
*)
BEGIN
IF node(Node.DoublyLinkedNode)^.previous = this^.head THEN
this^.head^.next := node^.next;
END;
currentNode^.next(Node.DoublyLinkedNode)^.previous := node;
node^.next := currentNode^.next;
currentNode^.next := node;
node(Node.DoublyLinkedNode)^.previous := currentNode;
this^.SetCurrent(node);
END NodeInsertAfter;
PROCEDURE (this: CircularDoublyLinkedList) ReturnLastNode(): Node.Node;
(*
Description: this is nothing but at nice way of getting the last node by doing this^.head^.previous, and we just got rid of the method List.ReturnLastNode that would break our list too
Parameters: -
Return: the last node of the list
Algorithm: -
*)
BEGIN
RETURN this^.ReturnPreviousNode(this^.head);
END ReturnLastNode;
PROCEDURE (this: CircularDoublyLinkedList) ReturnPreviousNode(node: Node.Node): Node.Node;
BEGIN
this^.SetCurrent(node(Node.DoublyLinkedNode)^.previous);
RETURN node(Node.DoublyLinkedNode)^.previous;
END ReturnPreviousNode;
BEGIN
END ObjectOrientedLists.