SIT221 Data Structures and Algorithms Practical Task 1.1 tutorials
Practical Task 1.1
General Instructions
1. Your task is to implement a generic data structure Vector<T>, which is similar to the collection className List<T> offered within the Microsoft .NET Framework. Here, T refers to a generic type, which can be substituted in practice by a specific data type such as bool, int, string, an array, or any className. An object of the List<T> can maintain an arbitrary number of data elements and provide broad functionality including, but not limited to, such basic operations as accessing, recording, and deleting elements from the data collection. It is known that the core of the List<T> is a simple internal array wrapped by the classNameexposing special methods and properties. This is done to make work with the data structure more convenient for the user and to give illusion that it is dynamic so that you can add/delete elements as you go. Because of the similarity of the Vector<T> to the List<T>, we strongly recommend you to become familiar with the specification of the latter classNameavailable at https://msdn.microsoft.com/en-us/library/6sh2ey19(v=vs.110).aspx
You may then address to this description when are in doubt about how a particular method of the Vector<T> should behave.
2. Download two C# source code files attached to this task. These files serve as a template for the program that you need to develop. Create a new Microsoft Visual Studio project and import the files. Your newly built project should compile and work without errors. Note that file Tester.cs already provides you with a Main method as a starting point of your program. Another file, Vector.cs, contains a template of the Vector<T>, which has some functionality implemented for you for the purpose of example, in particular:
Vector() Constructor. Initializes a new instance of the Vector<T> classNamethat is empty and has a default initial capacity, say 10 elements.
Vector( int capacity ) Constructor. Initializes a new instance of the Vector<T> classNamethat is empty and has a specified initial capacity. As an input parameter, this constructor accepts a number of elements that the data structure can initially store. If the size of the collection can be estimated beforehand, specifying the initial capacity eliminates the need to perform a number of resizing operations while adding new elements to it.
Count Property. Gets the number of elements physically contained in the Vector<T>.
Capacity Property. Gets the total number of elements that the internal array can potentially hold without resizing. Capacity represents the number of elements that the Vector<T> can store before resizing is required, whereas Count is the number of elements that are actually in the Vector<T>. Capacity is always greater than or equal to Count. If Count exceeds Capacity while adding elements, the capacity is increased by automatically reallocating the internal array to one of a larger size before adding the new elements.
void Add( T item ) Adds a new item of type T to the end of the Vector<T>. If Count already equals Capacity, the capacity of the Vector<T> is increased by automatically reallocating the internal array, and the existing elements are copied to the new larger array before the new element is added.
int IndexOf( T item ) Searches for the specified item and returns the zero‐based index of the first occurrence within the entire data structure. It returns the zero‐based index of the item, if found; otherwise, –1.
T this[ int index ] Returns the element at a specified index of the sequence. As an argument, it accepts a zero‐based index of the element to retrieve. This method throws IndexOutOfRangeException when the index’s value is invalid.
The given template of the Vector<T> classNameshould help you with development of its remaining methods. Therefore, explore the existing code as other methods are to be very similar in terms of implementation.
3. You must complete the Vector<T> and provide the following functionality to the user:
void Insert( int index, T item ) Inserts a new element into the data structure at the specified index. If Count already equals Capacity, the capacity of the Vector<T> is increased by automatically reallocating the internal array, and the existing elements are copied to the new larger array before the new element is added. If index is equal to Count, item is added to the end of the Vector<T>. This method throws IndexOutOfRangeException when the index’s value is invalid.
void Clear() Removes all elements from the Vector<T>. Count is set to 0, but capacity remains unchanged.
bool Contains( T item ) Determines whether a specified item is in the data collection. It returns true when the item is presented, and false otherwise.
bool Remove( T item ) Removes the first occurrence of the specified item from the data collection. It returns true if item is successfully removed; otherwise, false. This method also returns false if item was not found in the Vector<T>.
void RemoveAt( int index ) Removes the element at a specified index of the Vector<T>. When you call RemoveAt to remove an item, the remaining items in the list are renumbered to replace the removed item. For example, if you remove the item at index 3, the item at index 4 is moved to the 3rd position. In addition, the number of items in the data collection (as represented by the Count property) is reduced by 1. This method throws IndexOutOfRangeException when the index’s value is invalid.
string ToString() Returns a string that represents the current object. 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.
Note that you are free in writing the code of your vector classNameunless you respect all the requirements in terms of functionality and signatures of the specified methods. For simplicity, you may assume that the value of Capacity can only be increased. The format of the string returned by the ToString() method is [a,b,c,d], where a, b, c, and d are string values returned by the corresponding ToString() method of the data type T.
Expected Printout
This section displays the printout produced by the attached Tester className, specifically by its Main method. It is based on our solution. It is likely you get a different printout as the ToString method written by you might differ from one in the official solution. This is certainly acceptable. 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 new vector by calling 'Vector<int> vector = new Vector<int>(50);'
:: SUCCESS
Test B: Add a sequence of numbers 2, 6, 8, 5, 5, 1, 8, 5, 3, 5
:: SUCCESS
Test C: Remove number 3, 7, and then 6
:: SUCCESS
Test D: Insert number 50 at index 6, then number 0 at index 0, then number 60 at index 'vector.Count-1', then number 70 at index 'vector.Count'
:: SUCCESS
Test E: Insert number -1 at index 'vector.Count+1'
:: SUCCESS
Test F: Remove number at index 4, then number index 0, and then number at index 'vector.Count-1'
:: SUCCESS
Test G: Remove number at index 'vector.Count'
:: SUCCESS
Test H: Run a sequence of operations: vector.Contains(1);
:: SUCCESS
vector.Contains(2);
:: SUCCESS
vector.Contains(4);
:: SUCCESS
vector.Add(4); vector.Contains(4);
:: SUCCESS
Test I: Print the content of the vector via calling vector.ToString();
[2,8,5,1,8,50,5,60,5,4]
:: SUCCESS
Test J: Clear the content of the vector via calling vector.Clear();
:: SUCCESS
