Data Structure and Algorithms- Tasks to be completed

archive2.zip

Home >Computer Science homework help >Data Structure and Algorithms- Tasks to be completed

Practical Task 6.1-resources.zip

Tester.cs

using System; using System.Collections.Generic; namespace Heap { class Tester { private class IntAscendingComparer : IComparer<int> { public int Compare(int A, int B) { return Math.Sign(A - B); } } private class IntDescendingComparer : IComparer<int> { public int Compare(int A, int B) { return -1 * Math.Sign(A - B); } } static void Main(string[] args) { // ------------------------ test instance (begin) string[] names = new string[] { "Kelly", "Cindy", "John", "Andrew", "Richard", "Michael", "Guy", "Elicia", "Tom", "Iman", "Simon", "Vicky", "Kevin", "David" }; int[] IDs = new int[] { 1, 6, 5, 7, 8, 3, 10, 4, 2, 9, 14, 12, 11, 13 }; int[] certificateAdd = new int[] { 1, 2, 3, 4, 5, 3, 7, 2, 2, 10, 11, 12, 13, 14 }; int[] certificateDelete = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }; int[] certificateMinHeapBuild = new int[] { 1, 8, 6, 9, 5, 3, 7, 4, 2, 10, 11, 12, 13, 14 }; int[] certificateMaxHeapBuild = new int[] { 11, 10, 14, 4, 5, 12, 7, 8, 9, 2, 1, 6, 13, 3 }; // ------------------------ test instance (end) Heap<int, string> minHeap = null; Heap<int, string> maxHeap = null; IHeapifyable<int, string>[] nodes = null; string result = ""; // test 1 try { Console.WriteLine("\n\nTest A: Create a min-heap by calling 'minHeap = new Heap<int, string>(new IntAscendingComparer());'"); minHeap = new Heap<int, string>(new IntAscendingComparer()); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); result = result + "A"; } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } // test 2 try { Console.WriteLine("\n\nTest B: Run a sequence of operations: "); for (int i = 0; i < Math.Min(names.Length, IDs.Length); i++) { Console.WriteLine("\nInsert a node with name {0} (data) and ID {1} (key).", names[i], IDs[i]); IHeapifyable<int, string> node = minHeap.Insert(IDs[i], names[i]); if (!(node.Position == certificateAdd[i] && minHeap.Count == i + 1)) throw new Exception("The min-heap has a wrong structure"); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); } result = result + "B"; } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } // test 3 try { Console.WriteLine("\n\nTest C: Run a sequence of operations: "); for (int i = 0; i < certificateDelete.Length; i++) { Console.WriteLine("\nDelete the minimum element from the min-heap."); IHeapifyable<int, string> node = minHeap.Delete(); if (node.Key != certificateDelete[i]) throw new Exception("The extracted node has a wrong key"); if (minHeap.Count != certificateDelete.Length - i - 1) throw new Exception("The heap has a wrong number of elements"); if (certificateDelete.Length - i - 1 > 0) { if ((minHeap.Min().Key != certificateDelete[i + 1]) && (minHeap.Min().Position != 1)) throw new Exception("The min-heap has a wrong structure"); } Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); } result = result + "C"; } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } // test 4 try { Console.WriteLine("\n\nTest D: Delete the minimum element from the min-heap."); IHeapifyable<int, string> node = minHeap.Delete(); Console.WriteLine("Last operation is invalid and must throw InvalidOperationException. Your solution does not match specification."); result = result + "-"; } catch (InvalidOperationException) { Console.WriteLine(" :: SUCCESS: InvalidOperationException is thrown because the min-heap is empty"); result = result + "D"; } catch (Exception) { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); Console.WriteLine("Last operation is invalid and must throw InvalidOperationException. Your solution does not match specification."); result = result + "-"; } // test 5 try { Console.WriteLine("\n\nTest E: Run a sequence of operations: "); Console.WriteLine("\nInsert a node with name {0} (data) and ID {1} (key).", names[0], IDs[0]); IHeapifyable<int, string> node = minHeap.Insert(IDs[0], names[0]); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); Console.WriteLine("\nBuild the min-heap for the pair of key-value arrays with \n[{0}] as keys and \n[{1}] as data elements", String.Join(", ", IDs), String.Join(", ", names)); nodes = minHeap.BuildHeap(IDs, names); Console.WriteLine("Last operation is invalid and must throw InvalidOperationException. Your solution does not match specification."); result = result + "-"; } catch (InvalidOperationException) { Console.WriteLine(" :: SUCCESS: InvalidOperationException is thrown because the min-heap is not empty"); result = result + "E"; } catch (Exception) { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); Console.WriteLine("Last operation is invalid and must throw InvalidOperationException. Your solution does not match specification."); result = result + "-"; } // test 6 try { Console.WriteLine("\n\nTest F: Run a sequence of operations: "); Console.WriteLine("\nClear the min-heap."); minHeap.Clear(); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); Console.WriteLine("\nBuild the min-heap for the pair of key-value arrays with \n[{0}] as keys and \n[{1}] as data elements", String.Join(", ", IDs), String.Join(", ", names)); nodes = minHeap.BuildHeap(IDs, names); if (minHeap.Count != certificateMinHeapBuild.Length) throw new Exception("The resulting min-heap has a wrong number of elements."); if (nodes.Length != certificateMinHeapBuild.Length) throw new Exception("The size of the resulting array returned by BuildHeap() is incorrect."); for (int i = 0; i < nodes.Length; i++) { if (!(nodes[i].Position == certificateMinHeapBuild[i])) throw new Exception("The min-heap has a wrong structure"); } result = result + "F"; Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } // test 7 try { Console.WriteLine("\n\nTest G: Run a sequence of operations: "); IHeapifyable<int, string> node = nodes[nodes.Length - 1]; Console.WriteLine("\nDelete the minimum element from the min-heap."); minHeap.Delete(); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); Console.WriteLine("\nDelete the minimum element from the min-heap."); minHeap.Delete(); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); Console.WriteLine("\nRun DecreaseKey(node,0) for node {0} by setting the new value of its key to 0", node); minHeap.DecreaseKey(node, 0); if (minHeap.Count != certificateMinHeapBuild.Length - 2) throw new Exception("The resulting min-heap has a wrong number of elements"); if (!((node.Position == 1) && (minHeap.Min().Key == node.Key))) throw new Exception("The min-heap has a wrong structure"); Console.WriteLine(" :: SUCCESS: min-heap's state " + minHeap.ToString()); result = result + "G"; } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: min-heap's state " + minHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } // test 8 try { Console.WriteLine("\n\nTest H: Run a sequence of operations: "); Console.WriteLine("\nCreate a max-heap by calling 'maxHeap = new Heap<int, string>(new IntDescendingComparer());'"); maxHeap = new Heap<int, string>(new IntDescendingComparer()); Console.WriteLine(" :: SUCCESS: max-heap's state " + maxHeap.ToString()); Console.WriteLine("\nBuild the max-heap for the pair of key-value arrays with \n[{0}] as keys and \n[{1}] as data elements", String.Join(", ", IDs), String.Join(", ", names)); nodes = maxHeap.BuildHeap(IDs, names); if (maxHeap.Count != certificateMaxHeapBuild.Length) throw new Exception("The resulting max-heap has a wrong number of elements"); if (nodes.Length != certificateMaxHeapBuild.Length) throw new Exception("The size of the resulting array returned by BuildHeap() is incorrect."); for (int i = 0; i < nodes.Length; i++) { if (!(nodes[i].Position == certificateMaxHeapBuild[i])) throw new Exception("The max-heap has a wrong structure"); } result = result + "H"; Console.WriteLine(" :: SUCCESS: max-heap's state " + maxHeap.ToString()); } catch (Exception exception) { try { Console.WriteLine(" :: FAIL: max-heap's state " + maxHeap.ToString()); } catch { }; Console.WriteLine(exception.ToString()); result = result + "-"; } Console.WriteLine("\n\n ------------------- SUMMARY ------------------- "); Console.WriteLine("Tests passed: " + result); Console.ReadKey(); } } }

Heap.cs

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace Heap { public class Heap<K, D> where K : IComparable<K> { // This is a nested Node class whose purpose is to represent a node of a heap. private class Node : IHeapifyable<K, D> { // The Data field represents a payload. public D Data { get; set; } // The Key field is used to order elements with regard to the Binary Min (Max) Heap Policy, i.e. the key of the parent node is smaller (larger) than the key of its children. public K Key { get; set; } // The Position field reflects the location (index) of the node in the array-based internal data structure. public int Position { get; set; } public Node(K key, D value, int position) { Data = value; Key = key; Position = position; } // This is a ToString() method of the Node class. // It prints out a node as a tuple ('key value','payload','index')}. public override string ToString() { return "(" + Key.ToString() + "," + Data.ToString() + "," + Position + ")"; } } // --------------------------------------------------------------------------------- // Here the description of the methods and attributes of the Heap<K, D> class starts public int Count { get; private set; } // The data nodes of the Heap<K, D> are stored internally in the List collection. // Note that the element with index 0 is a dummy node. // The top-most element of the heap returned to the user via Min() is indexed as 1. private List<Node> data = new List<Node>(); // We refer to a given comparer to order elements in the heap. // Depending on the comparer, we may get either a binary Min-Heap or a binary Max-Heap. // In the former case, the comparer must order elements in the ascending order of the keys, and does this in the descending order in the latter case. private IComparer<K> comparer; // We expect the user to specify the comparer via the given argument. public Heap(IComparer<K> comparer) { this.comparer = comparer; // We use a default comparer when the user is unable to provide one. // This implies the restriction on type K such as 'where K : IComparable<K>' in the class declaration. if (this.comparer == null) this.comparer = Comparer<K>.Default; // We simplify the implementation of the Heap<K, D> by creating a dummy node at position 0. // This allows to achieve the following property: // The children of a node with index i have indices 2*i and 2*i+1 (if they exist). data.Add(new Node(default(K), default(D), 0)); } // This method returns the top-most (either a minimum or a maximum) of the heap. // It does not delete the element, just returns the node casted to the IHeapifyable<K, D> interface. public IHeapifyable<K, D> Min() { if (Count == 0) throw new InvalidOperationException("The heap is empty."); return data[1]; } // Insertion to the Heap<K, D> is based on the private UpHeap() method public IHeapifyable<K, D> Insert(K key, D value) { Count++; Node node = new Node(key, value, Count); data.Add(node); UpHeap(Count); return node; } private void UpHeap(int start) { int position = start; while (position != 1) { if (comparer.Compare(data[position].Key, data[position / 2].Key) < 0) Swap(position, position / 2); position = position / 2; } } // This method swaps two elements in the list representing the heap. // Use it when you need to swap nodes in your solution, e.g. in DownHeap() that you will need to develop. private void Swap(int from, int to) { Node temp = data[from]; data[from] = data[to]; data[to] = temp; data[to].Position = to; data[from].Position = from; } public void Clear() { for (int i = 0; i<=Count; i++) data[i].Position = -1; data.Clear(); data.Add(new Node(default(K), default(D), 0)); Count = 0; } public override string ToString() { if (Count == 0) return "[]"; StringBuilder s = new StringBuilder(); s.Append("["); for (int i = 0; i < Count; i++) { s.Append(data[i + 1]); if (i + 1 < Count) s.Append(","); } s.Append("]"); return s.ToString(); } // TODO: Your task is to implement all the remaining methods. // Read the instruction carefully, study the code examples from above as they should help you to write the rest of the code. public IHeapifyable<K, D> Delete() { // You should replace this plug by your code. throw new NotImplementedException(); } // Builds a minimum binary heap using the specified data according to the bottom-up approach. public IHeapifyable<K, D>[] BuildHeap(K[] keys, D[] data) { // You should replace this plug by your code. throw new NotImplementedException(); } public void DecreaseKey(IHeapifyable<K, D> element, K new_key) { // You should replace this plug by your code. throw new NotImplementedException(); } } }

IHeapifyable.cs

namespace Heap { public interface IHeapifyable<K, D> { D Data { get; set; } K Key { get; } int Position { get; } } }

SIT221-Practical Task 6.1.pdf

SIT221 Data Structures and Algorithms Trimester 2, 2019

Practical Task 6.1 (Pass Task)

Submission deadline: 10:00am Monday, September 2 Discussion deadline: 10:00am Saturday, September 14

General Instructions

The objective of this task is to study implementation of a Binary Heap, a data structure which is seen as a special case of a complete binary tree. Like a binary tree, a heap consists of a collection of nodes that can be considered as building blocks of the data structure. The tree structure that a binary heap represents is complete; that is, every level, except possibly the last one, is completely filled, and all nodes are as far left as possible. This makes a binary heap with nodes be always of a log height. In addition to the standard binary tree properties, a binary heap must also adhere to the mandatory Heap Ordering property. The ordering can be one of the two types:

 The Min‐Heap Property: the value of each node is greater than or equal to the value of its parent, with the minimum‐value element at the root.

 The Max‐Heap Property: the value of each node is less than or equal to the value of its parent, with the maximum‐value element at the root.

Note that a binary heap is not a sorted structure and can be regarded as partially ordered. Indeed, there is no particular relationship among nodes on any given level, even among siblings. From a practical perspective, a binary heap is a very useful data structure when one needs to remove the object with the lowest (or highest, in case of the max‐heap ordering) priority.

A binary heap can be uniquely represented by storing its level order traversal in an array or an array‐based collection like a list (also known as a vector). Note that the links between nodes are not required. For the convenience of implementation, the first entry of the array with index 0 is skipped; it contains a dummy (default) element. Therefore, the root of a heap is the second item in the array at index 1, and the length of

the array is 1 for a heap with data elements. This implies that for the element of the array the following statements are valid:

 the left child is located at index 2 ∙ ;  the right child is located at index 2 ∙ 1;  the parent is located uniquely at index /2 .

Insertion of a new element initially appends it to the end of a heap as the last element of the array at index 1. The Heap Ordering property is then repaired by comparing the added element with its parent and

moving the added element up a level (swapping positions with the parent). This process is commonly known as “UpHeap”, or “Heapify‐Up”, or “Sift‐Up”. The comparison is repeated until the parent is larger (or smaller, in case of the max‐heap ordering) than or equal to the percolating element. The worst‐case runtime of the algorithm is log , since we need at most one swap on each level of a heap on the path from the inserted node to the root.

The minimum (or maximum, in case of the max‐heap ordering) element can be found at the root, which is the element of the array located at index 1. Deletion of the minimum element first replaces it with the last element of the array at index , and then restores the Heap Ordering property by following the process known as “DownHeap”, or “Heapify‐Down”, or “Sift‐Down”. Similar to insertion, the worst‐case runtime is log .

1. Explore the source code attached to this task. Create a new Microsoft Visual Studio project and import the enclosed Heap.cs, IHeapifyable.cs, and Tester.cs files. Your newly built project should compile and work without errors. The objective of the task is to develop the missing functionality of the Heap<K,D> class. The Heap.cs contains a template of the Heap<K,D>. The Tester.cs contains a prepared Main method

SIT221 Data Structures and Algorithms Trimester 2, 2019

that should help you to build a fully‐functional data structure. It enables a number of tests important for debugging and testing of the Heap<K,D> class and its interfaces for runtime and logical errors.

2. Find the nested Node class presented inside the Heap<K,D> and explore its structure. This is a generic class that represents a node of a binary heap. Think about it as an atomic data structure itself that serves the Heap<K,D> as a building block. It is a data structure consisting of

 a generic type raw data (a payload),  a generic type key necessary to place the node with regard to the order of nodes existing in the

Heap<K,D>, and

 an integer‐valued position (index) that locates the node in the array‐based collection of nodes of the Heap<K,D>.

Because both K and D types are generic, the key and the data may be of an arbitrary type: a string, an integer, or a user‐defined class. Finally, note that the Node class is ready for you to use. It provides the following functionality:

 Node(K key, D value, int position) Initializes a new instance of the Node class associated with the specified generic key. The node records the given generic data as well as its own index‐based position within the array‐based collection of data nodes privately owned by the related Heap<K,D>.

 D Data Property. Gets or sets the data of generic type D associated with the Node.

 K Key Property. Gets or sets the key of generic type K assigned to the Node.

 Position Property. Gets or sets the index‐based position of the Node in the array‐based collection of nodes constituting the Heap<K,D> .

 string ToString() Returns a string that represents the current Node.

The Node class implements the IHeapifyable<K,D> interface, which is defined in the attached IHeapifyable.cs. Note that this interface is parametrized by the same two generic data types as the Heap<K,D>. The reason for the use of the interface is that the Node class is a data structure internal to the Heap<K,D>, therefore an instance of the Node must not be exposed to a user. It must remain hidden for the user in order to protect the integrity of the whole data structure. Otherwise, manipulating the nodes directly, the user may easily corrupt the structure of a binary heap and violate the important Heap‐ Ordering rule. Nevertheless, because the user needs access to the data that the user owns and stores inside a binary heap, the Node implements the interface that permits reading and modifying the data. Therefore, the primal purpose of the IHeapifyable<K,D> is to record and retrieve the data associated with a particular node and track the position of the node in the array‐based collection of nodes of the Heap<K,D>.

Check the IHeapifyable<K,D> interface to see that the only property it allows to change is the Data. The other two properties, the Key and the Position, are read‐only. Note that the value of a key is set at the time the node is added to a heap. It then can be changed only via dedicated operations, like DecreaseKey. The Heap<K,D> is entirely responsible for Position, thus modification of this property by the user is impossible.

3. Proceed with the given template of the Heap<K,D> class and explore the methods that it has implemented for you for the purpose of example, in particular:

 Heap(IComparer<K> comparer) Initializes a new instance of the Heap<K,D> class and stores the specified reference to the object that enables comparison of two keys of type K.

SIT221 Data Structures and Algorithms Trimester 2, 2019

 Count Property. Gets the number of elements stored by the Heap<K,D>.

 IHeapifyable<K, D> Min() Returns the element with the minimum (or maximum) key positioned at the top of the Heap<K,D>, without removing it. The element is casted to the IHeapifyable<K,D>. The method throws InvalidOperationException if the Heap<K,D> is empty.

 IHeapifyable<K, D> Insert(K key, D value) Inserts a new node containing the specified key‐value pair into the Heap<K,D>. The position of the new element in the binary heap is determined according the Heap‐Order policy. It returns the newly created node casted to the IHeapifyable<K,D>.

 void Clear() Removes all nodes from the Heap<K,D> and sets the Count to zero.

 string ToString() Returns a string representation of the Heap<K,D>.

Rather than an array, the Heap<K,D> utilizes the native .NET Framework List<T> generic collection as the internal data structure. This collection is dynamic as opposed to an array, which is static. This fact should simplify your work. Furthermore, note that the internal structure of the Heap<K,D> can be explored only implicitly through the positions of the nodes constituting it.

As you may have noticed, the comparison of nodes is performed by the comparator originally set within the constructor of the Heap<K,D>. Providing different comparator to the constructor will change the behaviour of the Heap<K,D>. When keys are ordered in ascending order, the Heap<K,D> acts as a min‐ heap. When the comparator orders keys in descending order, the Heap<K,D> behaves as a max‐heap.

4. You must complete the Heap<K,D> class and provide the following functionality to the user:

 IHeapifyable<K, D> Delete() Deletes and returns the node casted to the IHeapifyable<K,D> positioned at the top of the Heap<K,D>. This method throws InvalidOperationException if the Heap<K,D> is empty.

 IHeapifyable<K, D>[] BuildHeap(K[] keys, D[] data) Builds a binary heap following the bottom‐up approach. Each new element of the heap is derived by the key‐ value pair (keys[i],data[i]) specified by the method’s parameters. It returns an array of nodes casted to the IHeapifyable<K,D>. Each node at index must match its key‐value pair at index of the two input arrays. This method throws InvalidOperationException if the Heap<K,D> is not empty.

 DecreaseKey(IHeapifyable<K, D> element, K new_key) Decreases the key of the specified element presented in the Heap<K,D>. The method throws InvalidOperationException when the node stored in the Heap<K,D> at the position specified by the element is different to the element. This signals that the given element is inconsistent to the current state of the Heap<K,D>.

Note that you are free in writing your code that is private to the Heap<K,D> unless you respect all the requirements in terms of functionality and signatures of the specified methods.

5. As you progress with the implementation of the Heap<K,D> class, you should start using the Tester class to thoroughly test the Heap<K,D> aiming on the coverage of all potential logical issues and runtime errors. This (testing) part of the task is as important as writing the Heap<K,D> class. The given version of the testing class covers only some basic cases. Therefore, you should extend it with extra cases to make sure that your data structure is checked against other potential mistakes.

Further Notes

 Explore the material of chapter 9.4 of the SIT221 course book “Data structures and algorithms in Java” (2014) by M. Goodrich, R. Tamassia, and M. Goldwasser. You may access the book on‐line for free from

SIT221 Data Structures and Algorithms Trimester 2, 2019

the reading list application in CloudDeakin available in Resources  Additional Course Resources  Resources on Algorithms and Data Structures  Course Book: Data structures and algorithms in Java. As a supplementary material, to learn more about the theory part and implementation issues of binary heaps, you may refer to the Section 9.2.3 of Chapter 9 of SIT221 Workbook available in CloudDeakin in

Resources  Additional Course Resources  Resources on Algorithms and Data Structures  SIT221 Workbook .

 The lecture notes of week 6 may be the best material to understand the logic behind a binary heap and its array‐based implementation.

Marking Process and Discussion

To get your task completed, you must finish the following steps strictly on time.

 Make sure that your program implements all the required functionality, is compliable, and has no runtime errors. Programs causing compilation or runtime errors will not be accepted as a solution. You need to test your program thoroughly before submission. Think about potential errors where your program might fail.

 Submit your program code as an answer to the task via OnTrack submission system. Cloud students must record a short video explaining their work and solution to the task.

 Meet with your marking tutor to demonstrate and discuss your program in one of the dedicated practical sessions. Be on time with respect to the specified discussion deadline.

 Answer all additional (theoretical) questions that your tutor can ask you. Questions are likely to cover lecture notes, so attending (or watching) lectures should help you with this compulsory interview part. Please, come prepared so that the class time is used efficiently and fairly for all the students in it. You should start your interview as soon as possible as if your answers are wrong, you may have to pass another interview, still before the deadline. Use available attempts properly.

Note that we will not check your solution after the submission deadline and will not discuss it after the discussion deadline. If you fail one of the deadlines, you fail the task and this reduces the chance to pass the unit. Unless extended for all students, the deadlines are strict to guarantee smooth and on‐time work through the unit.

Remember that this is your responsibility to keep track of your progress in the unit that includes checking which tasks have been marked as completed in the OnTrack system by your marking tutor, and which are still to be finalised. When marking you at the end of the unit, we will solely rely on the records of the OnTrack system and feedback provided by your tutor about your overall progress and quality of your solutions.

Expected Printout

This section displays the printout produced by the attached Tester class, specifically by its Main method. It is based on our solution. The printout is provided here to help with testing your code for potential logical errors. It demonstrates the correct logic rather than an expected printout in terms of text and alignment.

Test A: Create a min-heap by calling 'minHeap = new Heap<int, string>(new IntAscendingComparer());'

:: SUCCESS: min-heap's state []

Test B: Run a sequence of operations:

Insert a node with name Kelly (data) and ID 1 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1)]

SIT221 Data Structures and Algorithms Trimester 2, 2019

Insert a node with name Cindy (data) and ID 6 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1),(6,Cindy,2)]

Insert a node with name John (data) and ID 5 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1),(6,Cindy,2),(5,John,3)]

Insert a node with name Andrew (data) and ID 7 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1),(6,Cindy,2),(5,John,3),(7,Andrew,4)]

Insert a node with name Richard (data) and ID 8 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1),(6,Cindy,2),(5,John,3),(7,Andrew,4),(8,Richard,5)]

Insert a node with name Michael (data) and ID 3 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1),(6,Cindy,2),(3,Michael,3),(7,Andrew,4),(8,Richard,5),(5,John,6)]

Insert a node with name Guy (data) and ID 10 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1),(6,Cindy,2),(3,Michael,3),(7,Andrew,4),(8,Richard,5),(5,John,6),(10,Guy,7)]

Insert a node with name Elicia (data) and ID 4 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1),(4,Elicia,2),(3,Michael,3),(6,Cindy,4),(8,Richard,5),(5,John,6),(10,Guy,7),(7,Andrew,8)]

Insert a node with name Tom (data) and ID 2 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1),(2,Tom,2),(3,Michael,3),(4,Elicia,4),(8,Richard,5),(5,John,6),(10,Guy,7),(7,Andrew,8),(6,Cindy,9)]

Insert a node with name Iman (data) and ID 9 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1),(2,Tom,2),(3,Michael,3),(4,Elicia,4),(8,Richard,5),(5,John,6),(10,Guy,7),(7,Andrew,8),(6,Cindy,9),(9,Iman,10)]

Insert a node with name Simon (data) and ID 14 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1),(2,Tom,2),(3,Michael,3),(4,Elicia,4),(8,Richard,5),(5,John,6),(10,Guy,7),(7,Andrew,8),(6,Cindy,9),(9,Iman,10),( 14,Simon,11)]

Insert a node with name Vicky (data) and ID 12 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1),(2,Tom,2),(3,Michael,3),(4,Elicia,4),(8,Richard,5),(5,John,6),(10,Guy,7),(7,Andrew,8),(6,Cindy,9),(9,Iman,10),( 14,Simon,11),(12,Vicky,12)]

Insert a node with name Kevin (data) and ID 11 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1),(2,Tom,2),(3,Michael,3),(4,Elicia,4),(8,Richard,5),(5,John,6),(10,Guy,7),(7,Andrew,8),(6,Cindy,9),(9,Iman,10),( 14,Simon,11),(12,Vicky,12),(11,Kevin,13)]

Insert a node with name David (data) and ID 13 (key).

SIT221 Data Structures and Algorithms Trimester 2, 2019

:: SUCCESS: min-heap's state [(1,Kelly,1),(2,Tom,2),(3,Michael,3),(4,Elicia,4),(8,Richard,5),(5,John,6),(10,Guy,7),(7,Andrew,8),(6,Cindy,9),(9,Iman,10),( 14,Simon,11),(12,Vicky,12),(11,Kevin,13),(13,David,14)]

Test C: Run a sequence of operations:

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state [(2,Tom,1),(4,Elicia,2),(3,Michael,3),(6,Cindy,4),(8,Richard,5),(5,John,6),(10,Guy,7),(7,Andrew,8),(13,David,9),(9,Iman,10 ),(14,Simon,11),(12,Vicky,12),(11,Kevin,13)]

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state [(3,Michael,1),(4,Elicia,2),(5,John,3),(6,Cindy,4),(8,Richard,5),(11,Kevin,6),(10,Guy,7),(7,Andrew,8),(13,David,9),(9,Iman, 10),(14,Simon,11),(12,Vicky,12)]

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state [(4,Elicia,1),(6,Cindy,2),(5,John,3),(7,Andrew,4),(8,Richard,5),(11,Kevin,6),(10,Guy,7),(12,Vicky,8),(13,David,9),(9,Iman,1 0),(14,Simon,11)]

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state [(5,John,1),(6,Cindy,2),(10,Guy,3),(7,Andrew,4),(8,Richard,5),(11,Kevin,6),(14,Simon,7),(12,Vicky,8),(13,David,9),(9,Ima n,10)]

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state [(6,Cindy,1),(7,Andrew,2),(10,Guy,3),(9,Iman,4),(8,Richard,5),(11,Kevin,6),(14,Simon,7),(12,Vicky,8),(13,David,9)]

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state [(7,Andrew,1),(8,Richard,2),(10,Guy,3),(9,Iman,4),(13,David,5),(11,Kevin,6),(14,Simon,7),(12,Vicky,8)]

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state [(8,Richard,1),(9,Iman,2),(10,Guy,3),(12,Vicky,4),(13,David,5),(11,Kevin,6),(14,Simon,7)]

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state [(9,Iman,1),(12,Vicky,2),(10,Guy,3),(14,Simon,4),(13,David,5),(11,Kevin,6)]

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state [(10,Guy,1),(12,Vicky,2),(11,Kevin,3),(14,Simon,4),(13,David,5)]

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state [(11,Kevin,1),(12,Vicky,2),(13,David,3),(14,Simon,4)]

Delete the minimum element from the min-heap.

SIT221 Data Structures and Algorithms Trimester 2, 2019

:: SUCCESS: min-heap's state [(12,Vicky,1),(14,Simon,2),(13,David,3)]

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state [(13,David,1),(14,Simon,2)]

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state [(14,Simon,1)]

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state []

Test D: Delete the minimum element from the min-heap.

:: SUCCESS: InvalidOperationException is thrown because the min-heap is empty

Test E: Run a sequence of operations:

Insert a node with name Kelly (data) and ID 1 (key).

:: SUCCESS: min-heap's state [(1,Kelly,1)]

Build the min-heap for the pair of key-value arrays with

[1, 6, 5, 7, 8, 3, 10, 4, 2, 9, 14, 12, 11, 13] as keys and

[Kelly, Cindy, John, Andrew, Richard, Michael, Guy, Elicia, Tom, Iman, Simon, Vicky, Kevin, David] as data elements

:: SUCCESS: InvalidOperationException is thrown because the min-heap is not empty

Test F: Run a sequence of operations:

Clear the min-heap.

:: SUCCESS: min-heap's state []

Build the min-heap for the pair of key-value arrays with

[1, 6, 5, 7, 8, 3, 10, 4, 2, 9, 14, 12, 11, 13] as keys and

[Kelly, Cindy, John, Andrew, Richard, Michael, Guy, Elicia, Tom, Iman, Simon, Vicky, Kevin, David] as data elements

:: SUCCESS: min-heap's state [(1,Kelly,1),(2,Tom,2),(3,Michael,3),(4,Elicia,4),(8,Richard,5),(5,John,6),(10,Guy,7),(6,Cindy,8),(7,Andrew,9),(9,Iman,10),( 14,Simon,11),(12,Vicky,12),(11,Kevin,13),(13,David,14)]

Test G: Run a sequence of operations:

Delete the minimum element from the min-heap.

SIT221 Data Structures and Algorithms Trimester 2, 2019

:: SUCCESS: min-heap's state [(2,Tom,1),(4,Elicia,2),(3,Michael,3),(6,Cindy,4),(8,Richard,5),(5,John,6),(10,Guy,7),(13,David,8),(7,Andrew,9),(9,Iman,10 ),(14,Simon,11),(12,Vicky,12),(11,Kevin,13)]

Delete the minimum element from the min-heap.

:: SUCCESS: min-heap's state [(3,Michael,1),(4,Elicia,2),(5,John,3),(6,Cindy,4),(8,Richard,5),(11,Kevin,6),(10,Guy,7),(13,David,8),(7,Andrew,9),(9,Iman, 10),(14,Simon,11),(12,Vicky,12)]

Run DecreaseKey(node,0) for node (13,David,8) by setting the new value of its key to 0

:: SUCCESS: min-heap's state [(0,David,1),(3,Michael,2),(5,John,3),(4,Elicia,4),(8,Richard,5),(11,Kevin,6),(10,Guy,7),(6,Cindy,8),(7,Andrew,9),(9,Iman,1 0),(14,Simon,11),(12,Vicky,12)]

Test H: Run a sequence of operations:

Create a max-heap by calling 'maxHeap = new Heap<int, string>(new IntDescendingComparer());'

:: SUCCESS: max-heap's state []

Build the max-heap for the pair of key-value arrays with

[1, 6, 5, 7, 8, 3, 10, 4, 2, 9, 14, 12, 11, 13] as keys and

[Kelly, Cindy, John, Andrew, Richard, Michael, Guy, Elicia, Tom, Iman, Simon, Vicky, Kevin, David] as data elements

:: SUCCESS: max-heap's state [(14,Simon,1),(9,Iman,2),(13,David,3),(7,Andrew,4),(8,Richard,5),(12,Vicky,6),(10,Guy,7),(4,Elicia,8),(2,Tom,9),(6,Cindy, 10),(1,Kelly,11),(3,Michael,12),(11,Kevin,13),(5,John,14)]

------------------- SUMMARY -------------------

Tests passed: ABCDEFGH

SIT221-Practical Task 5.1.pdf

SIT221 Data Structures and Algorithms Trimester 2, 2019

Practical Task 5.1 (Pass Task)

Submission deadline: 10:00am Monday, August 26 Discussion deadline: 10:00am Saturday, September 14

General Instructions

The objective of this task is to study implementation of a Doubly Linked List, a generic data structure capable to maintain an arbitrary number of data elements and support various standard operations to read, write, and delete data. Compared to other popular data structures, linked list like data structures offer a number of advantages with respect to time complexity and practical application. For example, where an array‐based data structure, such as a simple list (or a vector), requires a contiguous memory location to store data, a linked list may record new data elements anywhere in the memory. This is achievable by encapsulation of a payload (the user’s data record) into a node, then connecting nodes into a sequence via memory references (also known as links). Because of this, a linked list is not restricted in size and new nodes can be added increasing the size of the list to any extent. Furthermore, it is allowed to use the first free and available memory location with only a single overhead step of storing the address of memory location in the previous node of a linked list. This makes insertion and removal operations in a linked list of a constant 1 time; that is, as fast as possible. Remember that these operations generally run in a linear n time in an array since memory locations are consecutive and fixed.

A doubly linked list outperforms a singly linked list achieving better runtime for deletion of a given data node as it enables traversing the sequence of nodes in both directions, i.e. from starting to end and as well as from end to starting. For a given a node, it is always possible to reach the previous node; this is what a singly linked list does not permit. However, these benefits come at the cost of extra memory consumption since one additional variable is required to implement a link to previous node. In the case of a simpler singly linked list, just one link is used to refer to the next node. However, traversing is then possible in one direction only, from the head of a linked list to its end.

1. To start, follow the link below and explore the functionality of the LinkedList<T> generic class available within the Microsoft .NET Framework.

https://msdn.microsoft.com/en‐au/library/he2s3bh7(v=vs.110).aspx.

Because some operations that you are asked to develop in this task are similar to those in the LinkedList<T>, you may refer to the existing description of the class to get more insights about how your own code should work.

2. Explore the source code attached to this task. Create a new Microsoft Visual Studio project and import the DoublyLinkedList.cs file. This file contains a template of the DoublyLinkedList<T> class. The objective of the task is to develop the missing functionality of the class to obtain a fully‐functional data structure. Subsequently, import the Tester.cs file to the project to enable the prepared Main method important for the purpose of debugging and testing the expected program class and its interfaces for runtime and logical errors.

3. Find the nested Node<K> class presented inside the DoublyLinkedList<T> and learn its structure. This is a generic class whose purpose is to represent a node of a doubly linked list. Think about it as an atomic data structure itself that serves the DoublyLinkedList<T> as a building block. In fact, a doubly linked list is a linear collection of data elements, whose order is not given by their physical positions in memory, for example like in arrays. Instead, each element points to the next (and the previous) one. It is a data structure consisting of a set of nodes which together represent a sequence. Generally, a node of a doubly linked list consists of a data record that holds a payload and two auxiliary pointers referring to the

SIT221 Data Structures and Algorithms Trimester 2, 2019

preceding and succeeding nodes in the ordered sequence of nodes constituting the linked list. The two pointers allow to navigate back and forth between two adjacent nodes.

Note that the Node<K> class is ready for you to use. It provides the following functionality:

 Node(K value, Node<K> previous, Node<K> next) Initializes a new instance of the Node<K> class, containing the specified value and referring to previous and next arguments as nodes before and after the new node, respectively, in the sequence of the associated doubly linked list.

 K Value Property. Gets or sets the value (payload) of type K contained in the node.

 Node<K> Next Property. Gets a reference to the next node in the DoublyLinkedList<T>, or null if the current node is the last element of the DoublyLinkedList<T>.

 Node<K> Previous Property. Gets a reference to the previous node in the DoublyLinkedList<T>, or null if the current node is the first element of the DoublyLinkedList<T>.

 string ToString() Returns a string that represents the current Node<K>. ToString() is the major formatting method in the .NET Framework. It converts an object to its string representation so that it is suitable for display.

You may have already noticed that the Node<K> implements the INode<K> interface, which is available in the attached INode.cs file. The reason for the use of the interface is that the Node<K> is a data structure internal to the DoublyLinkedList<T> class, thus an instance of the Node<K> must not be exposed to the user. It must be hidden to protect an instance of the DoublyLinkedList<T> from potential corruption caused by the user’s activities. However, because a user needs access to the data that the user owns and stores inside an instance of the DoublyLinkedList<T>, the Node<K> implements the interfaces that permits to read and set (write) the data. Check the INode<K> and see that the only property it implies is Value of generic type K.

4. Proceed with the given template of the DoublyLinkedList<T> class and explore the methods that it has implemented for you for the purpose of example, in particular:

 DoublyLinkedList() Initializes a new instance of the DoublyLinkedList<T> class that is empty.

 First Property. Gets the first node of the DoublyLinkedList<T>. If the DoublyLinkedList<T> is empty, the First property returns null.

 Last Property. Gets the last node of the DoublyLinkedList<T>. If the DoublyLinkedList<T> is empty, the Last property returns null.

 Count Property. Gets the number of nodes actually contained in the DoublyLinkedList<T>.

 INode<T> After(INode<T> node) Returns the node casted to the INode<T> that succeeds the specified node in the DoublyLinkedList<T>. If the node given as parameter is null, it throws the ArgumentNullException. If the parameter is not in the current DoublyLinkedList<T>, the method throws the InvalidOperationException.

 public INode<T> AddLast(T value) Adds a new node containing the specified value at the end of the DoublyLinkedList<T>. Returns the new node casted to the INode<T> with the recorded value.

SIT221 Data Structures and Algorithms Trimester 2, 2019

 INode<T> Find(T value) Finds the first occurrence in the DoublyLinkedList<T> that contains the specified value. The method returns the node casted to INode<T>, if found; otherwise, null. The DoublyLinkedList<T> is searched forward starting at First and ending at Last.

 string ToString() Returns a string that represents the current DoublyLinkedList<T>. ToString() is the major formatting method in the .NET Framework. It converts an object to its string representation so that it is suitable for display.

As part of the prepared DoublyLinkedList<T> class, you can also observe a number of private properties and methods. An important aspect of the DoublyLinkedList<T> is the use of two auxiliary nodes: the Head and the Tail. The both are introduced in order to significantly simplify the implementation of the class and make insertion functionality reduced just to a single method designated here as

Node<T> AddBetween(T value, Node<T> previous, Node<T> next)

In fact, the Head and the Tail are invisible to a user of the data structure and are always maintained in it, even when the DoublyLinkedList<T> is formally empty. When there is no element in it, the Head refers to the Tail, and vice versa. Note that in this case the First and the Last properties are set to null. The first added node therefore is to be placed in between the Head and the Tail so that the former points to the new node as the Next node, while the latter points to it as the Previous node. Hence, from the perspective of the internal structure of the DoublyLinkedList<T>, the First element is the next to the Head, and similarly, the Last element is previous to the Tail. Remember about this crucial fact when you design and code other functions of the DoublyLinkedList<T> in this task.

The given template of the DoublyLinkedList <T> class should help you with development of its remaining methods. Therefore, explore the existing code as other methods are to be similar in terms of logic and implementation.

5. You must complete the DoublyLinkedList<T> and provide the following functionality to the user:

 INode<T> Before(INode<T> node) Returns the node, casted to the INode<T>, which precedes the specified node in the DoublyLinkedList<T>. If the node given as parameter is null, the method throws the ArgumentNullException. If the parameter is not in the current DoublyLinkedList<T>, the method throws the InvalidOperationException.

 INode<T> AddFirst(T value) Adds a new node containing the specified value at the start of the DoublyLinkedList<T>. Returns the new node casted to the INode<T> containing the value.

 INode<T> AddBefore(INode<T> before, T value) Adds a new node before the specified node of the DoublyLinkedList<T> and records the given value as its payload. It returns the newly created node casted to the INode<T>. If the node specified as an argument is null, the method throws the ArgumentNullException. If the node specified as argument does not exist in the DoublyLinkedList<T>, the method throws the InvalidOperationException.

 INode<T> AddAfter(INode<T> after, T value) Adds a new node after the specified node of the DoublyLinkedList<T> and records the given value as its payload. It returns the newly created node casted to the INode<T>. If the node specified as argument is null, the method throws the ArgumentNullException. If the node specified as argument does not exist in the DoublyLinkedList<T>, the method throws the InvalidOperationException.

 void Clear() Removes all nodes from the DoublyLinkedList<T>. Count is set to zero. For each of the nodes, links to the previous and the next nodes must be nullified.

 void Remove(INode<T> node) Removes the specified node from the DoublyLinkedList<T>. If node is null, it throws the ArgumentNullException. If the node specified as argument does not exist in the DoublyLinkedList<T>, the method throws the InvalidOperationException.

SIT221 Data Structures and Algorithms Trimester 2, 2019

 void RemoveFirst() Removes the node at the start of the DoublyLinkedList<T>. If the DoublyLinkedList<T> is empty, it throws InvalidOperationException.

 void RemoveLast() Removes the node at the end of the DoublyLinkedList<T>. If the DoublyLinkedList<T> is empty, it throws InvalidOperationException.

Note that you are free in writing your code that is private to the DoublyLinkedList<T> unless you respect all the requirements in terms of functionality and signatures of the specified methods.

6. As you progress with the implementation of the DoublyLinkedList <T> class, you should start using the Tester class to thoroughly test the DoublyLinkedList<T> aiming on the coverage of all potential logical issues and runtime errors. This (testing) part of the task is as important as writing the DoublyLinkedList<T> class. The given version of the testing class covers only some basic cases. Therefore, you should extend it with extra cases to make sure that your doubly linked list class is checked against other potential mistakes.

Further Notes

 Learn the material of chapters 3.4 and especially that of section 7.3.3 of the SIT221 course book “Data structures and algorithms in Java” (2014) by M. Goodrich, R. Tamassia, and M. Goldwasser. You may

access the book on‐line for free from the reading list application in CloudDeakin available in Resources  Additional Course Resources  Resources on Algorithms and Data Structures  Course Book: Data structures and algorithms in Java. As a complementary material, to learn more about a singly linked and doubly linked lists, you may refer to Chapter 2 of SIT221 Workbook available in CloudDeakin in Resources

 Additional Course Resources  Resources on Algorithms and Data Structures  SIT221 Workbook.  If you still struggle with such OOP concepts as Generics and their application, you may wish to read

Chapter 11 of SIT232 Workbook available in Resources  Additional Course Resources  Resources on Object‐Oriented Programming. You may also have to read Chapter 6 of SIT232 Workbook about Polymorphism and Interfaces as you need excellent understanding of these topics to progress well through the practical tasks of the unit. Make sure that you are proficient with them as they form a basis to design and develop programming modules in this and all the subsequent tasks. You may find other important topics required to complete the task, like exceptions handling, in other chapters of the workbook.

 We will test your code in Microsoft Visual Studio 2017. Find the instructions to install the community version of Microsoft Visual Studio 2017 available on the SIT221 unit web‐page in CloudDeakin at

Resources  Additional Course Resources  Software  Visual Studio Community 2017. You are free to use another IDE if you prefer that, e.g. Visual Studio Code. But we recommend you to take a chance to learn this environment.

Marking Process and Discussion

To get your task completed, you must finish the following steps strictly on time.

 Submit your program code as an answer to the task via OnTrack submission system.  Meet with your marking tutor to demonstrate and discuss your program in one of the dedicated practical

sessions. Be on time with respect to the specified discussion deadline.

SIT221 Data Structures and Algorithms Trimester 2, 2019

Expected Printout

Test A: Create a new list by calling 'DoublyLinkedList<int> vector = new DoublyLinkedList<int>( );'

:: SUCCESS: list's state []

Test B: Add a sequence of numbers 2, 6, 8, 5, 1, 8, 5, 3, 5 with list.AddLast( )

:: SUCCESS: list's state [{XXX-(2)-6},{2-(6)-8},{6-(8)-5},{8-(5)-1},{5-(1)-8},{1-(8)-5},{8-(5)-3},{5-(3)-5},{3-(5)-XXX}]

Test C: Remove sequentially 4 last numbers with list.RemoveLast( )

:: SUCCESS: list's state [{XXX-(2)-6},{2-(6)-8},{6-(8)-5},{8-(5)-1},{5-(1)-XXX}]

Test D: Add a sequence of numbers 10, 20, 30, 40, 50 with list.AddFirst( )

:: SUCCESS: list's state [{XXX-(50)-40},{50-(40)-30},{40-(30)-20},{30-(20)-10},{20-(10)-2},{10-(2)-6},{2-(6)-8},{6-(8)-5},{8- (5)-1},{5-(1)-XXX}]

Test E: Remove sequentially 3 last numbers with list.RemoveFirst( )

:: SUCCESS: list's state [{XXX-(20)-10},{20-(10)-2},{10-(2)-6},{2-(6)-8},{6-(8)-5},{8-(5)-1},{5-(1)-XXX}]

Test F: Run a sequence of operations:

list.Find(40);

:: SUCCESS: list's state [{XXX-(20)-10},{20-(10)-2},{10-(2)-6},{2-(6)-8},{6-(8)-5},{8-(5)-1},{5-(1)-XXX}]

list.Find(0);

:: SUCCESS: list's state [{XXX-(20)-10},{20-(10)-2},{10-(2)-6},{2-(6)-8},{6-(8)-5},{8-(5)-1},{5-(1)-XXX}]

list.Find(2);

:: SUCCESS: list's state [{XXX-(20)-10},{20-(10)-2},{10-(2)-6},{2-(6)-8},{6-(8)-5},{8-(5)-1},{5-(1)-XXX}]

Test G: Run a sequence of operations:

Add 100 before the node with 2 with list.AddBefore(2,100)

:: SUCCESS: list's state [{XXX-(20)-10},{20-(10)-100},{10-(100)-2},{100-(2)-6},{2-(6)-8},{6-(8)-5},{8-(5)-1},{5-(1)-XXX}]

SIT221 Data Structures and Algorithms Trimester 2, 2019

Add 200 after the node with 2 with list.AddAfter(2,200)

:: SUCCESS: list's state [{XXX-(20)-10},{20-(10)-100},{10-(100)-2},{100-(2)-200},{2-(200)-6},{200-(6)-8},{6-(8)-5},{8-(5)- 1},{5-(1)-XXX}]

Add 300 before node list.First with list.AddBefore(list.First,300)

:: SUCCESS: list's state [{XXX-(300)-20},{300-(20)-10},{20-(10)-100},{10-(100)-2},{100-(2)-200},{2-(200)-6},{200-(6)- 8},{6-(8)-5},{8-(5)-1},{5-(1)-XXX}]

Add 400 after node list.First with list.AddAfter(list.First,400)

:: SUCCESS: list's state [{XXX-(300)-400},{300-(400)-20},{400-(20)-10},{20-(10)-100},{10-(100)-2},{100-(2)-200},{2-(200)- 6},{200-(6)-8},{6-(8)-5},{8-(5)-1},{5-(1)-XXX}]

Add 500 before node list.First with list.AddBefore(list.Last,500)

:: SUCCESS: list's state [{XXX-(300)-400},{300-(400)-20},{400-(20)-10},{20-(10)-100},{10-(100)-2},{100-(2)-200},{2-(200)- 6},{200-(6)-8},{6-(8)-5},{8-(5)-500},{5-(500)-1},{500-(1)-XXX}]

Add 600 after node list.First with list.AddAfter(list.Last,600)

:: SUCCESS: list's state [{XXX-(300)-400},{300-(400)-20},{400-(20)-10},{20-(10)-100},{10-(100)-2},{100-(2)-200},{2-(200)- 6},{200-(6)-8},{6-(8)-5},{8-(5)-500},{5-(500)-1},{500-(1)-600},{1-(600)-XXX}]

Test H: Run a sequence of operations:

Remove the node list.First with list.Remove(list.First)

:: SUCCESS: list's state [{XXX-(400)-20},{400-(20)-10},{20-(10)-100},{10-(100)-2},{100-(2)-200},{2-(200)-6},{200-(6)- 8},{6-(8)-5},{8-(5)-500},{5-(500)-1},{500-(1)-600},{1-(600)-XXX}]

Remove the node list.Last with list.Remove(list.Last)

:: SUCCESS: list's state [{XXX-(400)-20},{400-(20)-10},{20-(10)-100},{10-(100)-2},{100-(2)-200},{2-(200)-6},{200-(6)- 8},{6-(8)-5},{8-(5)-500},{5-(500)-1},{500-(1)-XXX}]

Remove the node list.Before, which is before the node containing element 2, with list.Remove(list.Before(...))

:: SUCCESS: list's state [{XXX-(400)-20},{400-(20)-10},{20-(10)-2},{10-(2)-200},{2-(200)-6},{200-(6)-8},{6-(8)-5},{8-(5)- 500},{5-(500)-1},{500-(1)-XXX}]

Remove the node containing element 2 with list.Remove(...)

:: SUCCESS: list's state [{XXX-(400)-20},{400-(20)-10},{20-(10)-200},{10-(200)-6},{200-(6)-8},{6-(8)-5},{8-(5)-500},{5- (500)-1},{500-(1)-XXX}]

Test I: Remove the node containing element 2, which has been recently deleted, with list.Remove(...)

:: SUCCESS: list's state [{XXX-(400)-20},{400-(20)-10},{20-(10)-200},{10-(200)-6},{200-(6)-8},{6-(8)-5},{8-(5)-500},{5- (500)-1},{500-(1)-XXX}]

Test J: Clear the content of the vector via calling vector.Clear();

:: SUCCESS: list's state []

Test K: Remove last element for the empty list with list.RemoveLast()

:: SUCCESS: list's state []

------------------- SUMMARY -------------------

Tests passed: ABCDEFGHIJK

Practical Task 5.1-resources.zip

DoublyLinkedList.cs

using System; using System.Text; namespace DoublyLinkedList { public class DoublyLinkedList<T> { // Here is the the nested Node<K> class private class Node<K> : INode<K> { public K Value { get; set; } public Node<K> Next { get; set; } public Node<K> Previous { get; set; } public Node(K value, Node<K> previous, Node<K> next) { Value = value; Previous = previous; Next = next; } // This is a ToString() method for the Node<K> // It represents a node as a tuple {'the previous node's value'-(the node's value)-'the next node's value')}. // 'XXX' is used when the current node matches the First or the Last of the DoublyLinkedList<T> public override string ToString() { StringBuilder s = new StringBuilder(); s.Append("{"); s.Append(Previous.Previous == null ? "XXX" : Previous.Value.ToString()); s.Append("-("); s.Append(Value); s.Append(")-"); s.Append(Next.Next == null ? "XXX" : Next.Value.ToString()); s.Append("}"); return s.ToString(); } } // Here is where the description of the methods and attributes of the DoublyLinkedList<T> class starts // An important aspect of the DoublyLinkedList<T> is the use of two auxiliary nodes: the Head and the Tail. // The both are introduced in order to significantly simplify the implementation of the class and make insertion functionality reduced just to a AddBetween(...) // These properties are private, thus are invisible to a user of the data structure, but are always maintained in it, even when the DoublyLinkedList<T> is formally empty. // Remember about this crucial fact when you design and code other functions of the DoublyLinkedList<T> in this task. private Node<T> Head { get; set; } private Node<T> Tail { get; set; } public int Count { get; private set; } = 0; public DoublyLinkedList() { Head = new Node<T>(default(T), null, null); Tail = new Node<T>(default(T), Head, null); Head.Next = Tail; } public INode<T> First { get { if (Count == 0) return null; else return Head.Next; } } public INode<T> Last { get { if (Count == 0) return null; else return Tail.Previous; } } public INode<T> After(INode<T> node) { if (node == null) throw new NullReferenceException(); Node<T> node_current = node as Node<T>; if (node_current.Previous == null || node_current.Next == null) throw new InvalidOperationException("The node referred as 'before' is no longer in the list"); if (node_current.Next.Equals(Tail)) return null; else return node_current.Next; } public INode<T> AddLast(T value) { return AddBetween(value, Tail.Previous, Tail); } // This is a private method that creates a new node and inserts it in between the two given nodes referred as the previous and the next. // Use it when you wish to insert a new value (node) into the DoublyLinkedList<T> private Node<T> AddBetween(T value, Node<T> previous, Node<T> next) { Node<T> node = new Node<T>(value, previous, next); previous.Next = node; next.Previous = node; Count++; return node; } public INode<T> Find(T value) { Node<T> node = Head.Next; while (!node.Equals(Tail)) { if (node.Value.Equals(value)) return node; node = node.Next; } return null; } public override string ToString() { if (Count == 0) return "[]"; StringBuilder s = new StringBuilder(); s.Append("["); int k = 0; Node<T> node = Head.Next; while (!node.Equals(Tail)) { s.Append(node.ToString()); node = node.Next; if (k < Count - 1) s.Append(","); k++; } s.Append("]"); return s.ToString(); } // TODO: Your task is to implement all the remaining methods. // Read the instruction carefully, study the code examples from above as they should help you to write the rest of the code. public INode<T> Before(INode<T> node) { // You should replace this plug by your code. throw new NotImplementedException(); } public INode<T> AddFirst(T value) { // You should replace this plug by your code. throw new NotImplementedException(); } public INode<T> AddBefore(INode<T> before, T value) { // You should replace this plug by your code. throw new NotImplementedException(); } public INode<T> AddAfter(INode<T> after, T value) { // You should replace this plug by your code. throw new NotImplementedException(); } public void Clear() { // You should replace this plug by your code. throw new NotImplementedException(); } public void Remove(INode<T> node) { // You should replace this plug by your code. throw new NotImplementedException(); } public void RemoveFirst() { // You should replace this plug by your code. throw new NotImplementedException(); } public void RemoveLast() { // You should replace this plug by your code. throw new NotImplementedException(); } } }

INode.cs

using System; using System.Collections.Generic; using System.Text; namespace DoublyLinkedList { public interface INode<K> { K Value { get; set; } } }

Tester.cs

using DoublyLinkedList; using System; namespace DoubleLinkedList { class Tester { private static bool CheckIntSequence(int[] certificate, DoublyLinkedList<int> list) { if (certificate.Length != list.Count) return false; INode<int> node = list.First; for (int i = 0; i < certificate.Length; i++) { if (certificate[i] != node.Value) return false; node = list.After(node); } return true; } static void Main(string[] args) { DoublyLinkedList<int> list = null; string result = ""; // test 1 try { Console.WriteLine("\nTest A: Create a new list by calling 'DoublyLinkedList<int> vector = new DoublyLinkedList<int>( );'"); list = new DoublyLinkedList<int>(); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); result = result + "A"; } catch (Exception exception) { Console.WriteLine(" :: FAIL: list's state " + list.ToString()); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 2 try { Console.WriteLine("\nTest B: Add a sequence of numbers 2, 6, 8, 5, 1, 8, 5, 3, 5 with list.AddLast( )"); list.AddLast(2); list.AddLast(6); list.AddLast(8); list.AddLast(5); list.AddLast(1); list.AddLast(8); list.AddLast(5); list.AddLast(3); list.AddLast(5); if (!CheckIntSequence(new int[] { 2, 6, 8, 5, 1, 8, 5, 3, 5 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); result = result + "B"; } catch (Exception exception) { Console.WriteLine(" :: FAIL: list's state " + list.ToString()); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 3 try { Console.WriteLine("\nTest C: Remove sequentially 4 last numbers with list.RemoveLast( )"); list.RemoveLast(); list.RemoveLast(); list.RemoveLast(); list.RemoveLast(); if (!CheckIntSequence(new int[] { 2, 6, 8, 5, 1 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); result = result + "C"; } catch (Exception exception) { Console.WriteLine(" :: FAIL: list's state " + list.ToString()); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 4 try { Console.WriteLine("\nTest D: Add a sequence of numbers 10, 20, 30, 40, 50 with list.AddFirst( )"); list.AddFirst(10); list.AddFirst(20); list.AddFirst(30); list.AddFirst(40); list.AddFirst(50); if (!CheckIntSequence(new int[] { 50, 40, 30, 20, 10, 2, 6, 8, 5, 1 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); result = result + "D"; } catch (Exception exception) { Console.WriteLine(" :: FAIL: list's state " + list.ToString()); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 5 try { Console.WriteLine("\nTest E: Remove sequentially 3 last numbers with list.RemoveFirst( )"); list.RemoveFirst(); list.RemoveFirst(); list.RemoveFirst(); if (!CheckIntSequence(new int[] { 20, 10, 2, 6, 8, 5, 1 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); result = result + "E"; } catch (Exception exception) { Console.WriteLine(" :: FAIL: list's state " + list.ToString()); Console.WriteLine(exception.ToString()); result = result + "-"; } INode<int> node1 = null; // test 6 try { Console.WriteLine("\nTest F: Run a sequence of operations: "); Console.WriteLine("list.Find(40);"); if (list.Find(40) == null) Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); else throw new Exception("40 must no longer be in the list"); Console.WriteLine("list.Find(0);"); if (list.Find(0) == null) Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); else throw new Exception("0 must not be in the list"); Console.WriteLine("list.Find(2);"); node1 = list.Find(2); if (node1 != null && node1.Value == 2) Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); else throw new Exception("2 must be in the list, but 'list.Find(2)' does not return the correct result"); result = result + "F"; } catch (Exception exception) { Console.WriteLine(" :: FAIL: list's state " + list.ToString()); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 7 try { Console.WriteLine("\nTest G: Run a sequence of operations: "); Console.WriteLine("Add {1} before the node with {0} with list.AddBefore({0},{1})", node1.Value, 100); list.AddBefore(node1, 100); if (!CheckIntSequence(new int[] { 20, 10, 100, 2, 6, 8, 5, 1 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); Console.WriteLine("Add {1} after the node with {0} with list.AddAfter({0},{1})", node1.Value, 200); list.AddAfter(node1, 200); if (!CheckIntSequence(new int[] { 20, 10, 100, 2, 200, 6, 8, 5, 1 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); Console.WriteLine("Add {0} before node list.First with list.AddBefore(list.First,{0})", 300); list.AddBefore(list.First, 300); if (!CheckIntSequence(new int[] { 300, 20, 10, 100, 2, 200, 6, 8, 5, 1 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); Console.WriteLine("Add {0} after node list.First with list.AddAfter(list.First,{0})", 400); list.AddAfter(list.First, 400); if (!CheckIntSequence(new int[] { 300, 400, 20, 10, 100, 2, 200, 6, 8, 5, 1 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); Console.WriteLine("Add {0} before node list.First with list.AddBefore(list.Last,{0})", 500); list.AddBefore(list.Last, 500); if (!CheckIntSequence(new int[] { 300, 400, 20, 10, 100, 2, 200, 6, 8, 5, 500, 1 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); Console.WriteLine("Add {0} after node list.First with list.AddAfter(list.Last,{0})", 600); list.AddAfter(list.Last, 600); if (!CheckIntSequence(new int[] { 300, 400, 20, 10, 100, 2, 200, 6, 8, 5, 500, 1, 600 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); result = result + "G"; } catch (Exception exception) { Console.WriteLine(" :: FAIL: list's state " + list.ToString()); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 8 try { Console.WriteLine("\nTest H: Run a sequence of operations: "); Console.WriteLine("Remove the node list.First with list.Remove(list.First)"); list.Remove(list.First); if (!CheckIntSequence(new int[] { 400, 20, 10, 100, 2, 200, 6, 8, 5, 500, 1, 600 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); Console.WriteLine("Remove the node list.Last with list.Remove(list.Last)"); list.Remove(list.Last); if (!CheckIntSequence(new int[] { 400, 20, 10, 100, 2, 200, 6, 8, 5, 500, 1 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); Console.WriteLine("Remove the node list.Before, which is before the node containing element {0}, with list.Remove(list.Before(...))", node1.Value); list.Remove(list.Before(node1)); if (!CheckIntSequence(new int[] { 400, 20, 10, 2, 200, 6, 8, 5, 500, 1 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); Console.WriteLine("Remove the node containing element {0} with list.Remove(...)", node1.Value); list.Remove(node1); if (!CheckIntSequence(new int[] { 400, 20, 10, 200, 6, 8, 5, 500, 1 }, list)) throw new Exception("The list stores incorrect sequence of integers"); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); result = result + "H"; } catch (Exception exception) { Console.WriteLine(" :: FAIL: list's state " + list.ToString()); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 9 try { Console.WriteLine("\nTest I: Remove the node containing element {0}, which has been recently deleted, with list.Remove(...)", node1.Value); list.Remove(node1); Console.WriteLine(" :: FAIL: list's state " + list.ToString()); Console.WriteLine("Last operation is invalid and must throw InvalidOperationException. Your solution does not match specification."); result = result + "-"; } catch (InvalidOperationException) { Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); result = result + "I"; } catch (Exception) { Console.WriteLine(" :: FAIL: list's state " + list.ToString()); Console.WriteLine("Last operation is invalid and must throw InvalidOperationException. Your solution does not match specification."); result = result + "-"; } // test 10 try { Console.WriteLine("\nTest J: Clear the content of the vector via calling vector.Clear();"); list.Clear(); if (!CheckIntSequence(new int[] { }, list)) throw new Exception("The list stores incorrect data. It must be empty."); Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); result = result + "J"; } catch (Exception exception) { Console.WriteLine(" :: FAIL: list's state " + list.ToString()); Console.WriteLine(exception.ToString()); result = result + "-"; } // test 11 try { Console.WriteLine("\nTest K: Remove last element for the empty list with list.RemoveLast()"); list.RemoveLast(); Console.WriteLine(" :: FAIL: list's state " + list.ToString()); Console.WriteLine("Last operation is invalid and must throw InvalidOperationException. Your solution does not match specification."); result = result + "-"; } catch (InvalidOperationException) { Console.WriteLine(" :: SUCCESS: list's state " + list.ToString()); result = result + "K"; } catch (Exception) { Console.WriteLine(" :: FAIL: list's state " + list.ToString()); Console.WriteLine("Last operation is invalid and must throw InvalidOperationException. Your solution does not match specification."); result = result + "-"; } Console.WriteLine("\n\n ------------------- SUMMARY ------------------- "); Console.WriteLine("Tests passed: " + result); Console.ReadKey(); } } }