Comp 388 Lab 1: lists of Strings

Comp 388 lab 1 - Lists of Strings, TLists

Goals

Introduction to Arrays
Introduction to for loops
Random numbers

Overview

This lab deals with a class StrList, which is supposed to work a lot like List<String>. But some things need fixing. You will implement StrList in both C# and C++.

After that, you will create a modification of the C# version called TList which supports generic component types. In this it will behave almost exactly like List<T>
The strings themselves are stored in an array elements[ ]. Not all of the array is necessarily used; only the first currsize slots are (elements[0] through elements[currsize-1]). The variable currsize thus represents the active length of the StrList not elements.Length. This way our StrList can easily grow in length, at least up until the hard limit of elements.Length. The main task of this lab is to grow past that point.

I've given you a starter/demo file for both C# (StrList.cs) and C++ (StrList.cpp) to get started. It contains the following methods:

add(int y)
int get(int n)
void set(int n, int val)
int size()
void print()

The zipped files are here: C# and C++.

You are to do the following:

1. Make `add()` work even when `elements[]` is full

The trick here is to allocate a new array, say newelements, of larger size (doubling works, or increasing by 10, or increasing by 1.5 although that's trickier because of the floating-point conversions):

string[] newelements = new string[newsize];

Next you copy from elements[i] to newelements[i], for i<currsize. This is done with a straightforward for or while loop. Finally, you replace elements by newelements:

elements = newelements

does it. Note that in C# there is no need to do anything with the "old" elements. In C++ you should call delete[] on it; see the destructor ~StrList for an example.

At this point, you now have space to add the new item, so you go ahead and do it. The overall add structure looks like:

    if (currsize == elements.length) {
        // do the space expansion as above to ensure room
}
// now add the usual way; one way or another we know there is space!
    elements[currsize] = y;
    currsize += 1;

Once you do this, the program should behave quite differently; you shouldn't get those "no more room to add ...." messages, and the entire list should print out.

In C++ there is no analogue of elements.Length. You will have to keep the current allocated size of the array elements[] in a third instance variable, capacity.

For the C++ version, don't forget to delete[] the old array!

2. Add a fill() method

Create a method void fill(string val) that is like Add(val) until the current capacity is reached. That is, element[i] is set to val provided i>currsize and i<elements.Length (or i<capacity in the C++ version). I suppose calling it Fill() rather than fill() would be more consistent.

With this, the following combination would create a list of 10 empty strings:

StrList sl = new StrList(10); // currsize = 0 but potential capacity = 10
sl.fill("");

3. Convert the C# version to TList<T>

That is, instead of creating a class StrList of lists of strings, make the list-component type be a generic-class parameter T. The starter file here is TList.cs. There shouldn't be any peculiarities. The goal, again, is to make the associated WordList program run properly.

Submit your work on Sakai (or via email) by putting it all into a zip file.