Mini-project: Extending the ADT Bag using vector: DATA STRUCTURE C++

In CISC 1100 or 1400, you learned how to compute the union, intersection, and difference of sets: A

={

A

} A =

B A

B= {

} The union, intersection, and difference of bags are defined analogously. The only real difference is that since bags may contain repeated elements, the union (or intersection or difference) of bags may contain repeated elements. For example, suppose that we define bags A = [1, 1, 2, 2, 3, 4, 4, 4] and B = [1, 2, 3, 3, 4, 4, 5]. (Here, we use [. . .] to denote bags, similarly to the way that {. . .} denotes a set. Also, theres no reason to assume that a bag is sorted; we show the bag elements in sorted order to simply to make it easier to follow the example.) Then

A

= [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5] A = [1, 2, 3, 4, 4] A

B=

[1, 2, 4] See Exercises 1.6 -1.8 for further discussion. The purpose of this project is to add these operations to our Bag ADT.

Before doing so, note that the author has given us two different implementations: array based and link-based. The main problem with the former is that the implementer must decide how big to make the underlying array. This problem doesnt exist for the latter; however, linked structures are more complicated than arrays. However, if we were to use a vector-based implementation, then we wouldnt need to worry about how to choose the size of an array; moreover, vectors are easier to handle than linked structures. So, the first thing to do is to create Vector Bag, a vector-based implementation. Since vectors may be thought of as safe arrays, the best thing to do would be to start with the array-based implementation and work from there.

Once youve done this, you should now add new operations to the Vector Bag class. Since the standard symbols and are not available on our keyboard and since union is

Example: Input: 1263456 Output: 12345

a reserved word lets use + and * to denote union and intersection; of course, - is the obvious choice for denoting set difference. This means that youll want to define operator+ (and so forth), making sure to add appropriate comments that describe what these do.

Your main task will be to design, write, and test the Vector Bag class. VectorBag.h: interface file for the Vector Bag class. VectorBag.cpp: the implementation file for Vector Bag class. Note: you will add 3 new functions operator+ (), operator- () and operator*(). The prototype of operator+ () function is

Vector Bag operator+ (Vector Bag &another Bag);

I am providing you with the following files, which may be found on the blackboard for this project: The file hw1_linkedlist.cpp: you should implement all the three functions in this file and write at least one test case for each of the function. The file proj1.cpp, for testing your Vector Bag class. This file is like the main.cpp that the authors provide for testing the Array Bag class. Of course, it works for Vector Bag, rather than for the Array Bag class. In addition: The display Bag () function will work for a Vector Bag. It also displays the items in sorted order. Hence the < operation must be defined for ItemType. The new operation (, , ) are tested. A working versiHence the < operation must be defined for ItemType. The new operation (, , ) are tested. A working version of the program, called proj1, for you to try out. Your recollection of overloaded operators (such as operator+ and such like) may be a bit rusty. I have provided you with a file point.cc, which defines a Point class that has an operator+ (for adding two Points) .