UMBC CMSC 202, Computer Science II, Spring 1999, Sections 0201, 0202

Project 2: A Collection of Strings

Due: Monday, March 14, 1999

Pseudocode Due: March 5

Objective

1. to practice writing and testing classesin C++,
2. to practice using the new and delete operators, and
3. to use quicksort to sort a collection of strings.

Background

Collections of strings are also frequently required. Classes that represent a collection of objects are called collection or container classes. As a second step in this project, you will write a container class for strings.

Class header files are provided, but you will need to add the documentation for member functions. You will also need to design and write a test program to throroughly test the String class and its member functions.

Assignment

1. Begin thinking about this project early. Draw pictures and write pseudocode. To help motivate you to do this, 10 points of this project will be earned by turning in pseudocode for the following functions:
   • From the String class:
     • Overloaded assignment operator
     • Overloaded + operator
   • From the StringCollection class:
     • Add
     • Contains

   Your pseudocode will be collected in the discussion sections during the week of March 1. It may be printed by computer or handwritten. Be sure your name, SSN, and section number appears. You will lose points if your section number is missing. No pseudocode will be accepted after March 5.

2. Write a class called String. The class body is given below. Put the class body in String.H and implement the member functions in String.C. Note that Length() is an inline function, so it will be defined in String.H. class String { private: char* _cptr; int _length; public: String(); String (char* str); String (const String& str); ~String(); inline int Length(); void Display(); String& operator= (const String& str); String operator+ (const String& str); int operator== (const String& str); int operator!= (const String& str); int operator< (const String& str); int operator> (const String& str); int operator<= (const String& str); int operator>= (const String& str); }; Here are some notes and hints on some of the String member functions:
   • default constructor: construct a empty string (_length = 0, _cptr = NULL)
   • constructor that takes argument of type char*: It is assumed that the char pointer points to a null-terminated array of characters. The String object should be initialized to contain a copy of the characters in this array.
   • Length: return the length of the string
   • overloaded + operator: return a String which is the result of concatenating the strings represented by the host object and the object passed as a parameter. Do not change the host object.
   • overloaded relational operators: compare two String objects lexographically (Hint: use strcmp())
   • Display: print the character string on the screen followed by a newline character

3. Write a test program to test all of the member functions of your String class. Your main() function should be defined in a source file called TestString.C. The statements in your test program should be clearly commented to indicate where each member function is being tested.

4. Write a class called StringCollection. This will be a container class that does not allow duplicates. The class body is given below. Put the class body in StringCollection.H and implement the member functions in StringCollection.C. Note that Count() is an inline function, so it will be defined in StringCollection.H. class StringCollection { private: int _count; String* _array; void Quicksort (String a[], int i, int j); inline void Exchange (String b[], int i, int j); int Partition (String a[], int low, int high); public: StringCollection(); ~StringCollection(); int Add (const String& str); inline int Count(); int Contains (const String& str); void Sort(); void Display(); };

   Here are some notes and hints on some of the StringCollection member functions:

   • default constructor: construct an empty collection
   • Add: add a String object to the collection. This is a boolean function that returns false if a String with the same characters is already in the set.
   • Count: return the number of objects in the collection
   • Contains: return true or false to indicate if there is an object in the collection that contains the same characters as the String object specified as a parameter
   • Sort: sort the collection (using quicksort)
   • Quicksort, Partition, and Exchange: adapt the source code in the textbook (pp. 80-81).
   • Display: print the collection on the screen, one per line (Hint: call the Display() function in the String class for each String in the collection.)

5. Put the main() shown below in a file called Proj2.C. Use this to test your StringCollection class. The executable should be called Proj2. int main() { const int num_words = 13; char* words[num_words] = {"virtual", "class", "operator", "try", "friend", "this", "delete", "private", "inline", "template", "friend", "const", "new" }; StringCollection some_keywords; for (int i = 0; i < num_words; ++i) { String temp (words[i]); if (! some_keywords.Add (temp)) { cout << words[i] << " is a duplicate, not added" << endl; } } some_keywords.Display(); some_keywords.Sort(); cout << "After sort: " << endl; some_keywords.Display(); return 0; }

6. Adapt your makefile for this project so that your test program for the String class is an additional target. The name of the executable should be TestString, and the following command line should make it: make TestString

Implementation Issues

1. In the String class, the memory for the character array must be dynamically allocated, with no predefined limit on the length of the string.

2. Your StringCollection class should use a dynamically allocated array of String objects. There should be no limit on the number of String objects that can be stored in the collection. You will have to decide on an allocation strategy. It does not have to efficient, but make sure that it works! Here are three possibilities:
   • Each time you add a String to the collection, allocate a new array which is one element bigger. Copy all the elements from the old array to the new array, then destroy the old array.
   • Instead of just making room for one new element at a time, expand the array in "chunks", say 10 elements. Then you will only have to reallocate and copy on every tenth add.
   • Whenever you have the expand the array, make it twice as big.

3. You must have quicksort coded in your project. You may not use qsort() from the C run-time library.

4. For this project, you should submit a makefile and six source files named as follows:
   • Proj2.C
   • String.h
   • String.C
   • StringCollection.h
   • StringCollection.C
   • TestString.C

Extra Credit

Note: in order to get extra credit, the item you implement must work completely. In other words, extra credit is all-or-nothing.

• Add an overloaded += operator to the String class. Add statements in TestString.C to test it.
• Add a copy constructor to the StringCollection class. Add statements in Proj2.C to test it.
• Implement a binary search in the Contains() function in the StringCollection class.