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.