Step 1:

. A set is a special bag that does not allow duplicates. Specify each operation for a set of objects by stating its purpose, by describing its parameters, and by writing preconditions, postconditions, and a pseudocode version of its header. Then write a C++ interface for the set. Include javadoc -style comments in your code.

Step 2:

. Implement the ADT set that you specified in this programming problem in the previous step.

it was just writing out specifications for a "Set" ADT, which is just a slight variation on the "Bag" ADT. Your task this week is to write an "ArraySet" class to implement the "Set" ADT described in Programming Problem 5 of Chapter 1. You don't need to write out the specifications.

The vast majority of your code will be copied directly from the ArrayBag class given below. You just need to make minor adjustments, changing "bag" to "set" throughout the code and reflecting the fact that duplicate elements are not allowed.

Also, we won't have a frequencyOf() member function.

The add() function should throw a DuplicateItemError exception if the item passed in already exists in the Set.

Your ArraySet class must be derived from a "SetInterface" abstract class. There's almost no work for you to do here. Just copy the "BagInterface" class below. None of the code in that abstract class will need to be modified other than changing "bag" to "set", except that the frequencyOf() member function will be removed. Don't forget to change the namespace from cs_bag to cs_set. If you find the part about deriving the class from "SetInterface" confusing, be sure to ask about it in the discussion!

Here is the source code that you are to use as a starting point. It is based loosely on the source code given in the text.

//ArrayBag.cpp

namespace cs_bag { template void ArrayBag::add(const ItemType& newEntry) { if (itemCount >= maxItems) { throw CapacityExceededError(); } else { items[itemCount] = newEntry; itemCount++; } } template ArrayBag::ArrayBag() { itemCount = 0; maxItems = DEFAULT_CAPACITY; } template int ArrayBag::getCurrentSize() const { return itemCount; } template bool ArrayBag::isEmpty() const { return itemCount == 0; } template std::vector ArrayBag::toVector() const { std::vector bagContents; for (int i = 0; i < itemCount; i++) { bagContents.push_back(items[i]); } return bagContents; } template  bool ArrayBag::contains(const ItemType& anEntry) const { for (int i = 0; i < itemCount; i++) { if (items[i] == anEntry) { return true; } } return false; } template void ArrayBag::clear() { itemCount = 0; } template int ArrayBag::getIndexOf(const ItemType& target) const { for (int i = 0; i < itemCount; i++) { if (items[i] == target) { return i; } } return -1; } template void ArrayBag::remove(const ItemType& anEntry) { int locatedIndex = getIndexOf(anEntry); if (locatedIndex > -1) { itemCount--; items[locatedIndex] = items[itemCount]; } else { throw ItemNotFoundError(); } } template int ArrayBag::getFrequencyOf(const ItemType& anEntry) const { int frequency = 0; int curIndex = 0; while (curIndex < itemCount) { if (items[curIndex] == anEntry) { frequency++; } curIndex++; } return frequency; } }

//ArrayBag.h

#ifndef ARRAY_BAG_H #define ARRAY_BAG_H #include "BagInterface.h" namespace cs_bag { template class ArrayBag : public BagInterface { public: typedef ItemType value_type; class CapacityExceededError {}; class ItemNotFoundError {}; ArrayBag(); int getCurrentSize() const; bool isEmpty() const; void add(const ItemType& newEntry); void remove(const ItemType& anEntry); void clear(); bool contains(const ItemType& anEntry) const; int getFrequencyOf(const ItemType& anEntry) const; std::vector toVector() const; private: static const int DEFAULT_CAPACITY = 6; ItemType items[DEFAULT_CAPACITY]; int itemCount; int maxItems; // Returns either the index of the element in the array items that // contains the given target or -1, if the array does not contain // the target. int getIndexOf(const ItemType& target) const; }; } #include "ArrayBag.cpp" #endif

//BagInterface.h

#ifndef BAG_INTERFACE #define BAG_INTERFACE #include  namespace cs_bag { template class BagInterface { public: /** Gets the current number of entries in this bag. @return The integer number of entries currently in the bag. */ virtual int getCurrentSize() const = 0; /** Sees whether this bag is empty. @return True if the bag is empty, or false if not. */ virtual bool isEmpty() const = 0; /** Adds a new entry to this bag. @post If successful, newEntry is stored in the bag and the count of items in the bag has increased by 1. @param newEntry The object to be added as a new entry.*/ virtual void add(const ItemType& newEntry) = 0; /** Removes one occurrence of a given entry from this bag, if possible. @post If successful, anEntry has been removed from the bag and the count of items in the bag has decreased by 1. @param anEntry The entry to be removed.*/ virtual void remove(const ItemType& anEntry) = 0; /** Removes all entries from this bag. @post Bag contains no items, and the count of items is 0. */ virtual void clear() = 0; /** Counts the number of times a given entry appears in this bag. @param anEntry The entry to be counted. @return The number of times anEntry appears in the bag. */ virtual int getFrequencyOf(const ItemType& anEntry) const = 0; /** Tests whether this bag contains a given entry. @param anEntry The entry to locate. @return True if bag contains anEntry, or false otherwise. */ virtual bool contains(const ItemType& anEntry) const = 0; /** Empties and then fills a given vector with all entries that are in this bag. @return A vector containing all the entries in the bag. */ virtual std::vector toVector() const = 0; /** Destroys this bag and frees its assigned memory. (See C++ Interlude 2.) */ virtual ~BagInterface() { } }; } #endif

//bagtester.cpp

#include  #include  #include "ArrayBag.h" using std::cout; using std::endl; using std::string; using namespace cs_bag; void displayBag(ArrayBag& bag) { cout << "The bag contains " << bag.getCurrentSize() << " items:" << endl; std::vector bagItems = bag.toVector(); int numEntries = bagItems.size(); for (int i = 0; i < numEntries; i++) { cout << bagItems[i] << " "; } cout << endl << endl; } void bagTester(ArrayBag& bag) { cout << "isEmpty: returns " << bag.isEmpty() << "; should be 1 (true)" << endl; displayBag(bag); std::string items[] = {"one", "two", "three", "four", "five", "one"}; cout << "Add 6 items to the bag: " << endl; for (int i = 0; i < 6; i++) { bag.add(items[i]); } displayBag(bag); cout << "isEmpty: returns " << bag.isEmpty() << "; should be 0 (false)" << endl; cout << "getCurrentSize: returns " << bag.getCurrentSize() << "; should be 6" << endl; try { cout << "Try to add another entry: add(\"extra\")... "; bag.add("extra"); cout << "should cause exception but didn't" << endl; } catch (ArrayBag::CapacityExceededError e) { cout << "should cause exception and did!" << endl; } cout << "contains(\"three\"): returns " << bag.contains("three") << "; should be 1 (true)" << endl; cout << "contains(\"ten\"): returns " << bag.contains("ten") << "; should be 0 (false)" << endl; cout << "getFrequencyOf(\"one\"): returns " << bag.getFrequencyOf("one") << " should be 2" << endl; try { cout << "remove(\"one\")... "; bag.remove("one"); cout << "shouldn't cause exception and didn't!" << endl; } catch (ArrayBag::ItemNotFoundError e) { cout << "shouldn't cause exception but did." << endl; } cout << "getFrequencyOf(\"one\"): returns " << bag.getFrequencyOf("one") << " should be 1" << endl; try { cout << "remove(\"one\")... "; bag.remove("one"); cout << "shouldn't cause exception and didn't!" << endl; } catch (ArrayBag::ItemNotFoundError e) { cout << "shouldn't cause exception but did." << endl; } try { cout << "remove(\"one\")... "; bag.remove("one"); cout << "should cause exception but didn't" << endl; } catch (ArrayBag::ItemNotFoundError e) { cout << "should cause exception and did!" << endl; } cout << endl; displayBag(bag); cout << "After clearing the bag, "; bag.clear(); cout << "isEmpty: returns " << bag.isEmpty() << "; should be 1 (true)" << endl; } int main() { ArrayBag bag; cout << "Testing the Array-Based Bag:" << endl; cout << "The initial bag is empty." << endl; bagTester(bag); cout << "All done!" << endl; } 

Add member functions setUnion(), setIntersection(), and setDifference().

(Don't add them to the SetInterface class.)

The functions should all have one ArraySet parameter and should perform the operation on the ArraySet calling object and the ArraySet parameter and return the resulting ArraySet. The setUnion() function should throw a CapacityExceededError if the size of the result exceeds the capacity of the ArraySet). Here's a snippet of client code:

try { set1 = set2.setUnion(set3); } catch (CapacityExceededError e) { cout << "Operation exceeds the capacity of sets and therefore failed." << endl; } 

Don't call the toVector() function from any of these three functions.

Documentation

You will need to write the documentation for these three member functions. Follow the pattern used in the existing BagInterface class.

Name your source code files SetInterface.h, ArraySet.h, and ArraySet.cpp.