MODULE IntegerList;
	IMPORT
		Node, ObjectOrientedLists, In, OutExt;
	
	TYPE
		IntegerNode = POINTER TO IntegerNodeDesc;
		IntegerNodeDesc = RECORD
			(Node.DoublyLinkedNodeDesc)
			value: INTEGER;
		END;
	
	VAR
		input, list: ObjectOrientedLists.CircularDoublyLinkedList;
	
	PROCEDURE (this: IntegerNode) Print*();
	BEGIN
		OutExt.Int(this^.value, 0);
		OutExt.Ln;
	END Print;
	
	PROCEDURE BubbleSort*;
		VAR
			currentNode, lastNode: Node.Node;
			switched: BOOLEAN;
			
	BEGIN
			(* we start by iterating through the entire list, decreasing the size of the unsorted part by bubbling the largest elements *)
		lastNode := list^.ReturnLastNode();
			(* we only continue with sorting if there has been a switch, otherwise the list is already in order *)
		switched := TRUE;

		WHILE switched DO
				(* the unsorted part is at the beginning of the list *)
			currentNode := list^.head^.next;
				(* we put the boolean on false, and if there is an exchange, we'll set it on true for this iteration *)
			switched := FALSE;
			
				(* we loop through the list until we encounter the last unsorted element *)
			WHILE currentNode # lastNode DO
				IF currentNode(IntegerNode)^.value > currentNode^.next(IntegerNode)^.value THEN
						(* if we try to exchange a node at the end of our list, things go wrong *)
					IF currentNode^.next = lastNode THEN
						list^.NodeExchange(currentNode, lastNode);
						lastNode := currentNode;
					ELSE
						list^.NodeExchange(currentNode, currentNode^.next);	
					END;
						(* there has been a switch, so this must be true *)
					switched := TRUE;
				ELSE
						(* there was no need for switching, we look at the next element *)
					currentNode := currentNode^.next;
				END;
			END;
				
				(* we can decrease the size of the unsorted part *)					
			lastNode := list^.ReturnPreviousNode(lastNode);
		END;
		
		OutExt.String("De lijst is gesorteerd door middel van een bubble sort.");
		OutExt.Ln;
	END BubbleSort;
	
	PROCEDURE SelectionSort*;
		VAR
			currentNode, lastSortedNode, smallestNode: Node.Node;

	BEGIN
			(* obviously, the list starts unsorted *)
		lastSortedNode := list^.head;
			
			(* lastSortedNode will indicate which node is currently the last sorted, so lastSortedNode will be the last node of the list when it's sorted *)	
		WHILE lastSortedNode^.next # list^.head DO
				(* the node next to lastSortedNode is the first node of the part of the list where we will look for the smallest node *)
			currentNode := lastSortedNode^.next;
				(* we start with the first unsorted node as smallest node *)
			smallestNode := currentNode;
				
				(* we loop through the unsorted part, until the end of the list *)
			WHILE currentNode # list^.head DO
				IF currentNode(IntegerNode)^.value < smallestNode(IntegerNode)^.value THEN
						(* currentNoe is smaller than the former smallest node, so we change smallestNode *)
					smallestNode := currentNode;
				END;
				
				currentNode := currentNode^.next;
			END;
					list^.NodeExchange(lastSortedNode^.next, smallestNode);
					
			lastSortedNode := smallestNode;
		END;
		
		OutExt.String("De lijst is gesorteerd volgens een selection sort.");
		OutExt.Ln;
	END SelectionSort;
	
	
	PROCEDURE Initiate*;
		VAR
			integerNode: IntegerNode;
			integer: INTEGER;

	BEGIN
		OutExt.Open();
		OutExt.Clear();
		
		NEW(input);
		NEW(list);
		input^.Init();
		list^.Init();
		
		In.Open();
		In.Int(integer);
		
		WHILE In.Done DO
			NEW(integerNode);
			integerNode^.value := integer;
			input^.NodeInsert(integerNode);
			
			In.Int(integer);
		END;
		
		OutExt.String("De lijst is ingelezen.");
		OutExt.Ln;
		
		list^ := input^;
	END Initiate;
	
	PROCEDURE Print*;
	BEGIN
		input^.Print();
		
		OutExt.String("Het resultaat van de uitgevoerde acties:");
		OutExt.Ln;
		list^.Print();
	END Print;
	
	PROCEDURE Reset*;
	BEGIN
		OutExt.String("De lijst is overschreven door de (onbewerkte) input.");
		OutExt.Ln;
		
		list := input;
	END Reset;
		
BEGIN
END IntegerList.