CSC232 Data Structures HW01 - Extending the Bag ADT
HW01 - Extending the Bag ADT
In this assignment, the student shall add operations, i.e., extend the functionality of the VectorBag (first encountered in Lab 01) by adding operations above and beyond those found in the Bag interface.
Due Date
This assignment is due by 11:59:59 PM on Saturday, 18 February 2023.
Background
As presented in Geeks for Geeks,
The capability of a class to derive properties and characteristics from another class is called Inheritance. Inheritance is one of the most important features of Object-Oriented Programming.
Inheritance is a feature or a process in which, new classes are created from the existing classes. The new class created is called “derived class” or “child class” and the existing class is known as the “base class” or “parent class”. The derived class now is said to be inherited from the base class.
When we say derived class inherits the base class, it means, the derived class inherits all the properties of the base class, without changing the properties of base class and may add new features to its own. These new features in the derived class will not affect the base class. The derived class is the specialized class for the base class.
Advanced Reading
- General > Files > Class Materials > Setting Up WSL for CSC232.pdW
- Walls & Mirrors, Chapter 1: Data Abstraction
- Exercises 6, 7 & 8
- Programming Problem 6
Objectives
Upon successful completion of this assignment, the student has
- gained experience in extending a class hierarchy
- defined operations in terms of existing operations
- learned how to easily encapsulate their classes in a custom namespace
Tasks
In this assignment, you'll be working on Programming Problem 6 from Chapter 1 of our textbook. This problem refers back to Exercises 6-8 in the same chapter and repeated below:
Set Operations with Bags
Union
The union of two bags is a new bag containing the combined contents of the original two bags. Design and specify a method
unionWithfor the ADT bag that returns as a new bag the union of the bag receiving the call to the method and the bag that is the method’s one argument. Include sufficient comments to fully specify the method.Note that the union of two bags might contain duplicate items. For example, if object x occurs five times in one bag and twice in another, the union of these bags contains x seven times. Specifically, suppose that
bag1andbag2are bags;bag1contains the stringsa,b, andc; andbag2contains the stringsb,b,d, ande. The expressionbag1.unionWith(bag2)returns a bag containing the stringsa,b,b,b,c,d, ande. Note thatunionWithdoes not affect the contents ofbag1andbag2.
Intersection
The intersection of two bags is a new bag containing the entries that occur in both of the original two bags. Design and specify a method
intersectionWithfor the ADT bag that returns as a new bag the intersection of the bag receiving the call to the method and the bag that is the method’s one argument. Include sufficient comments to fully specify the method.Note that the intersection of two bags might contain duplicate items. For example, if object
xoccurs five times in one bag and twice in another, the intersection of these bags containsxtwo times. Specifically, suppose thatbag1andbag2are bags;bag1contains the stringsa,b, andc; andbag2contains the stringsb,b,d, ande. The expressionbag1.intersectionWith(bag2)returns a bag containing only the stringb. Note that intersection does not affect the contents ofbag1andbag2.
Difference
The difference of two bags is a new bag containing the entries that would be left in one bag after removing those that also occur in the second. Design and specify a method
differenceWithfor the ADT bag that returns as a new bag the difference of the bag receiving the call to the method and the bag that is the method’s one argument. Include sufficient comments to fully specify the method.Note that the difference of two bags might contain duplicate items. For example, if object
xoccurs five times in one bag and twice in another, the difference of these bags containsxthree times. Specifically, suppose thatbag1andbag2are bags;bag1contains the stringsa,b, andc; andbag2contains the stringsb,b,d, ande. The expressionbag1.differenceWith(bag2)returns a bag containing only the stringsaandc. Note that difference does not affect the contents ofbag1andbag2.
We shall develop these methods in a subclass of the VectorBag class with
the following tasks:
- Task 1: Declare the
SetOpVectorBagsubclass of theVectorBagclass - Task 2: Define the
unionWith( )operation - Task 3: Define
instersectionWith( )operation - Task 4: Define
differenceWith( )operation - Task 5: Encapsulate class hierarchy in the
csc232namespace
Task 1: Declaring the SetOpVectorBag class
In this task we declare our new subclass of the VectorBag class.
Discussion of Subclasses
This task requires a very specific syntax for a class declaration. The following rules must be adhered to in order for the first set of unit test suite to pass.
-
Your template declaration (e.g.,
template <typename...) and class declaration (e.g.,class foo...) are on two separate lines, with no blank space in between them. For example:template <typename T> class foo : public bar<T> { public: foo( ) = default; // explicitly define default construct ~f( ) = default; // explicitly define default destructor }; -
Your template parameter must be as shown above, simply
T -
You must have one space character in between each element of the declarations
-
You must match the spelling and case of the class you'll be asked to declare in this task.
Now on to the steps to take for this task.
-
Open the file named
set-op-vector-bag.hand look for the firstTODO. At this point, just make a "bare-bones" declaration similar to the one shown in the rules above. That is, only a template declaration, class declaration with an empty body:template <typename T> class SetOpVectorBag : public VectorBag<T> { public: SetOpVectorBag( ) = default; ~SetOpVectorBag( ) = default; }; -
When you have completed this task, open the
csc232.hheader file and toggle theSKIP_TESTING_TASK_1macro fromTRUEtoFALSE. -
Build and execute the
test_task1target to test your solution (or runctest). -
When all the tests for this task pass, commit and push your changes to GitHub.
Task 2: Define the unionWith( ) operation
In this task, we define the unionWith() operation.
Discussion of the union operation
In this task, we actually set about extending the VectorBag<T> template class. We begin with the unionWith() operation. Let's discuss the use of this operation first.
SetOpVectorBag<string> a{ };
SetOpVectorBag<string> b{ };
// ... populate bags with items
a.add( "a" ); a.add( "b" ); a.add( "c" );
b.add( "b" ); b.add( "b" ); b.add( "d" ); b.add( "e" );
SetOpVectorBag<string> c = a.unionWith( b );
// c = { "a", "b", "c", "b", "b", "d", "e" }This is a new method to be added to the SetOpVectorBag<T> class declaration. Take a look at how it's used and note
- The operation returns something; since whatever it is returning is getting assigned to an instance of
SetOpVectorBag<T>(i.e.,c), we can infer that the return type isSetOpVectorBag<T>. - The operation is given an argument (i.e.,
b); look at the argument's declaration, we can infer that the parameter's type is alsoSetOpVectorBag<T>. - There are two bags involved in this operation:
- The receiver of the message (i.e.,
a) - The argument passed along with this message (i.e.,
b)
- The receiver of the message (i.e.,
Note that this new method must be declared as public if we are to access it as shown above. All this analysis and design thus leads to the following change to our template class declaration:
// In set-op-vector-bag.h
template <typename T>
class SetOpVectorBag : public VectorBag<T>
{
public:
SetOpVectorBag( ) = default;
~SetOpVectorBag( ) = default;
SetOpVectorBag<T> unionWith( SetOpVectorBag<T> rhs );
};And we define this method in the set-op-vector-bag.cpp source file:
// In set-op-vector-bag.cpp
template <typename T>
SetOpVectorBag<T> SetOpVectorBag<T>::unionWith( SetOpVectorBag<T> rhs )
{
SetOpVectorBag<T> result;
// Use bag operations to populate result with appropriate values
// Note: Directly referring to an inherited operation is invoking the
// receiver object's method, e.g.,
// int size = VectorBag<T>::getCurrentSize(); // this is the size of this bag
// int otherSize = rhs.getCurrentSize(); // this is the size of the argument
return result;
}Let's get started on this task:
-
Open the
set-op-vector-bag.hheader file and modify your class declaration by adding the new operation:template <typename T> class SetOpVectorBag : public VectorBag<T> { public: SetOpVectorBag( ) = default; ~SetOpVectorBag( ) = default; SetOpVectorBag<T> unionWith( SetOpVectorBag<T> rhs ); }; -
Now open the
set-op-vector-bag.cppsource file and implement this method using the skeleton presented in the task discussion above. -
When you have completed this task, open the
csc232.hheader file and toggle theSKIP_TESTING_TASK_2macro fromTRUEtoFALSE. -
Build and execute the
test_task2target to test your solution (or runctest). -
When all the tests for this task pass, commit and push your changes to GitHub.
Task 3: Define instersectionWith( ) operation
In this task, we define the intersectionWith() operation.
Discussion of the intersection operation
In this task, we continue to extend the VectorBag<T> template class by adding the intersectionWith() operation. Let's discuss the use of this operation first.
SetOpVectorBag<string> a{ };
SetOpVectorBag<string> b{ };
// ... populate bags with items
a.add( "a" ); a.add( "b" ); a.add( "c" );
b.add( "b" ); b.add( "b" ); b.add( "d" ); b.add( "e" );
SetOpVectorBag<string> c = a.intersectionWith( b );
// c = { "b" }This is a new method to be added to the SetOpVectorBag<T> class declaration. Take a look at how it's used and note
- The operation returns something; since whatever it is returning is getting assigned to an instance of
SetOpVectorBag<T>(i.e.,c), we can infer that the return type isSetOpVectorBag<T>. - The operation is given an argument (i.e.,
b); look at the argument's declaration, we can infer that the parameter's type is alsoSetOpVectorBag<T>. - There are two bags involved in this operation:
- The receiver of the message (i.e.,
a) - The argument passed along with this message (i.e.,
b)
- The receiver of the message (i.e.,
The last bullet is notable in that the definition of this operation will access either the receiver's methods or the arguments methods (or both) in order to fulfill the requirements of this method.
Finally, note that this new method must be declared as public if we are to access it as shown above. All this analysis and design thus leads to the following change to our template class declaration:
template <typename T>
class SetOpVectorBag : public VectorBag<T>
{
public:
SetOpVectorBag( ) = default;
~SetOpVectorBag( ) = default;
SetOpVectorBag<T> unionWith( SetOpVectorBag<T> rhs );
SetOpVectorBag<T> intersectionWith( SetOpVectorBag<T> rhs );
};And we define this method in the set-op-vector-bag.cpp source file:
// In set-op-vector-bag.cpp
template <typename T>
SetOpVectorBag<T> SetOpVectorBag<T>::intersectionWith( SetOpVectorBag<T> rhs )
{
SetOpVectorBag<T> result;
// Use bag operations to populate result with appropriate values
// Note: Directly referring to an inherited operation is invoking the
// receiver object's method, e.g.,
// int size = VectorBag<T>::getCurrentSize(); // this is the size of this bag
// int otherSize = rhs.getCurrentSize(); // this is the size of the argument
return result;
}Let's get started on this task:
-
Open the
set-op-vector-bag.hheader file and modify your class declaration by adding the new operation:template <typename T> class SetOpVectorBag : public VectorBag<T> { public: SetOpVectorBag( ) = default; ~SetOpVectorBag( ) = default; SetOpVectorBag<T> unionWith( SetOpVectorBag<T> rhs ); SetOpVectorBag<T> intersectionWith( SetOpVectorBag<T> rhs ); }; -
Now open the
set-op-vector-bag.cppsource file and implement this method using the skeleton presented in the task discussion above. -
When you have completed this task, open the
csc232.hheader file and toggle theSKIP_TESTING_TASK_3macro fromTRUEtoFALSE. -
Build and execute the
test_task3target to test your solution (or runctest). -
When all the tests for this task pass, commit and push your changes to GitHub.
Task 4: Define differenceWith( ) operation
In this task, we define the differenceWith() operation.
Discussion of the difference operation
In this task, we continue to extend the VectorBag<T> template class by adding the differenceWith() operation. Let's discuss the use of this operation first.
SetOpVectorBag<string> a{ };
SetOpVectorBag<string> b{ };
// ... populate bags with items
a.add( "a" ); a.add( "b" ); a.add( "c" );
b.add( "b" ); b.add( "b" ); b.add( "d" ); b.add( "e" );
SetOpVectorBag<string> c = a.differenceWith( b );
// c = { "a", "c" }This is a new method to be added to the SetOpVectorBag<T> class declaration. Take a look at how it's used and note
- The operation returns something; since whatever it is returning is getting assigned to an instance of
SetOpVectorBag<T>(i.e.,c), we can infer that the return type isSetOpVectorBag<T>. - The operation is given an argument (i.e.,
b); look at the argument's declaration, we can infer that the parameter's type is alsoSetOpVectorBag<T>. - There are two bags involved in this operation:
- The receiver of the message (i.e.,
a) - The argument passed along with this message (i.e.,
b)
- The receiver of the message (i.e.,
The last bullet is notable in that the definition of this operation will access either the receiver's methods or the arguments methods (or both) in order to fulfill the requirements of this method.
Finally, note that this new method must be declared as public if we are to access it as shown above. All this analysis and design thus leads to the following change to our template class declaration:
template <typename T>
class SetOpVectorBag : public VectorBag<T>
{
public:
SetOpVectorBag( ) = default;
~SetOpVectorBag( ) = default;
SetOpVectorBag<T> unionWith( SetOpVectorBag<T> rhs );
SetOpVectorBag<T> intersectionWith( SetOpVectorBag<T> rhs );
SetOpVectorBag<T> differenceWith( SetOpVectorBag<T> rhs );
};And we define this method in the set-op-vector-bag.cpp source file:
// In set-op-vector-bag.cpp
template <typename T>
SetOpVectorBag<T> SetOpVectorBag<T>::differenceWith( SetOpVectorBag<T> rhs )
{
SetOpVectorBag<T> result;
// Use bag operations to populate result with appropriate values
// Note: Directly referring to an inherited operation is invoking the
// receiver object's method, e.g.,
// int size = VectorBag<T>::getCurrentSize(); // this is the size of this bag
// int otherSize = rhs.getCurrentSize(); // this is the size of the argument
return result;
}Let's get started on this task:
-
Open the
set-op-vector-bag.hheader file and modify your class declaration by adding the new operation:template <typename T> class SetOpVectorBag : public VectorBag<T> { public: SetOpVectorBag( ) = default; ~SetOpVectorBag( ) = default; SetOpVectorBag<T> unionWith( SetOpVectorBag<T> rhs ); SetOpVectorBag<T> intersectionWith( SetOpVectorBag<T> rhs ); SetOpVectorBag<T> differenceWith( SetOpVectorBag<T> rhs ); }; -
Now open the
set-op-vector-bag.cppsource file and implement this method using the skeleton presented in the task discussion above. -
When you have completed this task, open the
csc232.hheader file and toggle theSKIP_TESTING_TASK_4macro fromTRUEtoFALSE. -
Build and execute the
test_task4target to test your solution (or runctest). -
When all the tests for this task pass, commit and push your changes to GitHub.
Task 5: Encapsulate class hierarchy in the csc232 namespace
Looking back at the UML Class Diagram at the beginning of this README, we note that each of the classes in the class hierarchy actually appear to be members of the csc232 namespace. In this task, we make that happen.
Discussion of namespaces
While unlikely in today's programming exercise, it is possible that we come up with a class name that is common enough that it might clash with another similarly named class pulled in by some dependency in our project. To help mitigate this name clash, we can encapsulate our classes within a namespace. For us, we'll create a namespace named csc232 to do just that.
Creating a namespace is easy; just use the keyword namespace followed by an identifier (of your choice) and then provide a pair of parentheses to define the scope of this namespace:
namespace csc232
{
}If we declare a class in that namespace, as in
namespace csc232
{
class Foo {};
}Then, when we want to create an instance of that class, we must provide context:
csc232::Foo bar{ }; // creates an instance of csc232::Foo named barWe can shorten our typing with a using clause as well:
using csc232::Foo;
Foo bar{ }; // creates an instance of csc232::Foo named bar-
Open up the
bag.hheader file and put theBag<T>template class declaration inside a namespace namedcsc232. -
Next, do the same thing to the
VectorBag<T>template class declaration found invector-bag.h. -
So that the definitions found in
vector-bag.cppare still properly defined, add ausingclause to the beginning of the file (on a line after the#include "vector-bag.h"):using csc232::VectorBag; -
Next, do the same thing to the
SetOpVectorBag<T>template class declaration found inset-op-vector-bag.h. -
So that the definitions found in
set-op-vector-bag.cppare still properly defined, add a using clause to the beginning of the file (on a line after the#include "set-op-vector-bag.h"):using csc232::SetOpVectorBag; -
When you have completed this task, open the
csc232.hheader file and toggle theSKIP_TESTING_TASK_5macro fromTRUEtoFALSE. -
Build and execute the
test_task5target to test your solution (or runctest). -
When all the tests for this task pass, commit and push your changes to GitHub.
