LAB 2—Dynamic ListArray ADT. (Due Friday February 1st at 11:59pm).

Remark: if you are using Windows you must only use the eclipse compiler to write your program and if you are using Linux you must use the command line compilers javac (for java users) and g++ (for c++ users).

Remark: late submissions wont be marked.

Problem Statement.

In this lab exercise you need to implement the ADT ListArray from lab1 using dynamic arrays. Please refer to the lecture notes on Monday January 21st for an insight on dynamic arrays. Implement the new ADT in a class called SortedListDynamicArrayBased. This class must have three constructors as follows:

1) SortedListDynamicArrayBased();
2) SortedListDynamicArrayBased(int initCapacity);
3) SortedListDynamicArrayBased(int initCapacity, int capacityIncrement);

The first constructor creates a List with initial capacity of 0 and each time an expansion of the list is needed a list of twice the capacity of the current list is created. The second constructor creates a List with initial capacity of initCapacity and each time an expansion of the list is needed a list of twice the capacity of the current list is created.
The third constructor creates a List with initial capacity of initCapacity and each time an expansion of the list is needed a list with capacity C is created where C is defined as follows;

 

 

 

 

 

SortedListDynamicArrayBased methods.

The SortedListDynamicArrayBased provides the same operations are SortedListArrayBased plus two additional methods.

Shrink()
The shrink method creates a new array with the same values are before but with no waste space. That is if the number of the elements in the list is less than the capacity of the list then it will create a new list with the same elements but with the capacity equal to the number of the elements.

getNumberOfExpansions()
this method returns the number of times the expansion has occurred so far.

Remark: note that the insert method in this new implementation does not throw an exception.

Testing

input

In your main method write a code that reads data from an input file called “data.txt” and performs the proper actions. The first line of the data.txt file contains two integers (separated by space): the first number is the initial capacity of the list and the second number is the incrementCapacity parameter. The next lines of the data file contains numbers that are needed to be inserted or deleted form the list. If a number is positive it must be inserted to the list and if it’s negative it must be deleted from the list. Below is a sample of data file

0 1
15
23
-9
7
-23
-15
15
7

output

After reading the data file is finished your program must first shrink the list to release the unused space in the list, then print the currents elements in the list and finally print the number of times an expansion has occurred. The output of your program should like below given the above data.txt file.

inserting 15
inserting 23
removing 9
remark: 9 was not found in the list
inserting 7
removing 23
removing 15
inserting 15
inserting 7
remark: 7 already exists in the list.
List contents:
7
15
Number of expansions : 3

Optional

You can try to set different value for the capacityIncrease parameter and experience the effect of this value on the efficiency of the list (note that if you want to feel the difference when you change the parameter need to insert many elements in the list.)

 

Style: part of the grade is for having proper style which includes proper indenting and having enough comments.

Submission: zip all your source files and submit it through submission server submit.cs.sfu.ca. The submission server only accepts the zipped files. You can zip your assignment files using the winzip program or the zip, gzip linux command. Include your name and student number in your source file and includes the main function.

Remark: there will be four submission groups for each lab assignment make sure you submit to the group that you belong to (if you are registered in the first lab submit to the first group, and so on) otherwise there will be a 50% penalty.

What Compiler to use:  If you want to write your program in Windows you must use the eclipse compiler and if you want to write it in Linux use the command line compilers javac (for java users) and g++ (for c++ users).

 

Implementation Language: The programming problems in assignments, can be written in either JAVA or C++. It’s not necessary to learn JAVA for those who know only C++ and to learn C++ for those who know only JAVA.

---