# Data Structures and Intermediate Programming Program Assignment 4

Overview"

In this assignment, you will implement an abstract data

type Set and its two subclasses TreeSet and HashSet. The Set class is a pure abstract super class, so

you cannot create its instance. The actual set you will use in a program is an

instance of either the TreeSet or the HashSet subclass. The TreeSet subclass

implements the set abstraction using a binary search tree, while the HashSet

does it by using a hash table. The TreeSet instance has a better worst case

performance for updates. In contrast, the HashSet instance has a much better

average case performance for search. !

Problem Statement"

An abstract data type Set realizes the mathematical set,

which is a collection of items with no duplicates. A set does not have a notion

of order, unlike a list. Your task is to implement the Set type and support

basic set operations such as union and intersection. The Set type is realized

by three classes, the Set superclass and two subclasses TreeSet and HashSet.

The complete declaration for the Set superclass is provided to you. Your task

is to implement the concrete subclasses TreeSet and HashSet. You use some

variation of a binary tree structure to implement the TreeSet subclass and a

hash table for the HashSet subclass. You are not allowed to use any system

library classes such as the vector or the list when implementing the internal

data structure for the subclasses.!

Specification"

Here’s the

declaration for the Set superclass.! ! class! Set

{ public! :

//--------- Update Operations ----------------------------//

! virtual

void insert(string

item) = 0;

! virtual

void remove(string

item) = 0;

//--------- Set Operations ----------------------------// ! virtual

Set* set_union(Set* s2) = 0; //set

union

! virtual

Set* set_intersect(Set* s2) = 0; //set

intersection virtual

Set* set_diff(Set*

s2) = 0; //set difference

!!

//--------- Access Operations --------------------// ! virtual

vector<string

scan( ) = 0;

//--------- Queries ----------------------------//

! virtual

int size( ) = 0; ! virtual

bool isEmpty( ) = 0;

virtual bool

in(string

item) = 0; };

Function

Specification

void insert(string item)

Insert an item into the

set. If the item already exists in the set, do nothing.

void remove(string item)

Delete the designated item

from the set. If the designated item is not found, do nothing.

Set* set_union(Set* s2)

Return the set union of

this set and s2. This set and s2 remain unchanged.

Set* set_intersect(Set* s2)

Return the set intersection

of this set and s2. This set and s2 remain unchanged.

Set* set_diff(Set* s2)

Return the set difference

of this set and s2. This set and s2 remain unchanged. Remove all items in s2

from this set. An item in this set but not in s2 remains in the result.

vector<string scan( );

Return the items in the set

as a vector of items. If the set is empty, then return an empty vector, i.e.,

a vector with no elements, not a NULL.

int size( );

Return the number of items

in the set.

bool isEmpty( );

Return true if the set is

empty; otherwise, return false.

bool in(string item);

Return true if the item is

in the set. Otherwise, return false.

!

!

Here’s a sample use:!

!

! Set * ps1 = new

TreeSet();

Set * ps2 = new

TreeSet();

Set * ps3;

!

ps1-insert("Hello");

!

ps1-insert("World"); ps2-insert("C++");

!

ps2-insert("Hello"); ps3 = ps1-set_union(ps2);!

Requirements"

1. All

functions must have good performance. For example, when taking a union of two

set, you should aim for an algorithm that performs better than inserting all

elements from s1 and s2, one by one, into s3. !

2. There

should be absolutely NO input and output statements in the functions. You may

place temporary I/O statements in a function for testing/debugging purposes

during the development, but you must remove them before the submission.!

3. DO

NOT CHANGE the public member functions defined in the file Set.h. The instructor's test program will import

functions from your module so it is critical that the function signatures are

not changed. !

4. DO

NOT ADD any new public member functions to the Set class. But, you may add as

many private data members and private helper functions as you wish.!

5. Functions

you define in the program should not access any global variables, those define

outside of the class. Use of the global symbolic constants is fine.!

6. In

your source files, include a header comment with your name, the course number,

the assignment number, and any detailed explanation of your functions as

appropriate.!

7. Format

the program in a clean manner. Group statements into logical groups and include

a descriptive comment for each group. Group comments do not have to be verbose.

One sentence would suffice if the statements in a group are written correctly

and precisely. Include enough blank lines between logical groups.!

8. Insert

one or more blank lines between statements as necessary to make the code more

readable and easier to follow. Do not pack statements too densely (e.g., 20

statements with no blank lines between them).! 9. Use comments judiciously. Do

not include redundant and meaningless comments.!

!

Starter Code"

The following source files are provided to you.!

set.h

The source file for the

abstract superclass Set.

prog4.cpp

This sample main program illustrates a basic interaction

with a set.

vectorset.h! vectorset.cpp

This is a partially

completed sample subclass to illustrate how the set union can be implemented

using a vector. This class is provided solely for the purpose of giving you

some idea. You do not have to do anything to this class.

!

Development Ideas"

1. Implement

the TreeSet class using some variation of a binary search tree. Consider making

modifications to the base BST class so the set union, intersection, and

difference can be implemented efficiently.!

2. Implement

the HashSet class using one of the hashing techniques. Again, aim for the

hashing technique that will allow you to implement the set operations

efficiently.!

!

Testing the Functions"

As always, you need to plan

effective testing methodology to verify the implementation.!

!

Submission"

Submit the source files for the

HashSet and TreeSet class—hashset.h, hashset.cpp, treeset.h,

and treeset.cpp—that fully implements the

Set class, via the Sakai course website’s Program Assignment 4 page.!

In this assignment, you will implement an abstract data

type Set and its two subclasses TreeSet and HashSet. The Set class is a pure abstract super class, so

you cannot create its instance. The actual set you will use in a program is an

instance of either the TreeSet or the HashSet subclass. The TreeSet subclass

implements the set abstraction using a binary search tree, while the HashSet

does it by using a hash table. The TreeSet instance has a better worst case

performance for updates. In contrast, the HashSet instance has a much better

average case performance for search. !

Problem Statement"

An abstract data type Set realizes the mathematical set,

which is a collection of items with no duplicates. A set does not have a notion

of order, unlike a list. Your task is to implement the Set type and support

basic set operations such as union and intersection. The Set type is realized

by three classes, the Set superclass and two subclasses TreeSet and HashSet.

The complete declaration for the Set superclass is provided to you. Your task

is to implement the concrete subclasses TreeSet and HashSet. You use some

variation of a binary tree structure to implement the TreeSet subclass and a

hash table for the HashSet subclass. You are not allowed to use any system

library classes such as the vector or the list when implementing the internal

data structure for the subclasses.!

Specification"

Here’s the

declaration for the Set superclass.! ! class! Set

{ public! :

//--------- Update Operations ----------------------------//

! virtual

void insert(string

item) = 0;

! virtual

void remove(string

item) = 0;

//--------- Set Operations ----------------------------// ! virtual

Set* set_union(Set* s2) = 0; //set

union

! virtual

Set* set_intersect(Set* s2) = 0; //set

intersection virtual

Set* set_diff(Set*

s2) = 0; //set difference

!!

//--------- Access Operations --------------------// ! virtual

vector<string

scan( ) = 0;

//--------- Queries ----------------------------//

! virtual

int size( ) = 0; ! virtual

bool isEmpty( ) = 0;

virtual bool

in(string

item) = 0; };

**Operations"**

!*Please read the specification for each function very, very*

carefully. !carefully. !

Function

Specification

void insert(string item)

Insert an item into the

set. If the item already exists in the set, do nothing.

void remove(string item)

Delete the designated item

from the set. If the designated item is not found, do nothing.

Set* set_union(Set* s2)

Return the set union of

this set and s2. This set and s2 remain unchanged.

Set* set_intersect(Set* s2)

Return the set intersection

of this set and s2. This set and s2 remain unchanged.

Set* set_diff(Set* s2)

Return the set difference

of this set and s2. This set and s2 remain unchanged. Remove all items in s2

from this set. An item in this set but not in s2 remains in the result.

vector<string scan( );

Return the items in the set

as a vector of items. If the set is empty, then return an empty vector, i.e.,

a vector with no elements, not a NULL.

int size( );

Return the number of items

in the set.

bool isEmpty( );

Return true if the set is

empty; otherwise, return false.

bool in(string item);

Return true if the item is

in the set. Otherwise, return false.

!

!

Here’s a sample use:!

!

! Set * ps1 = new

TreeSet();

Set * ps2 = new

TreeSet();

Set * ps3;

!

ps1-insert("Hello");

!

ps1-insert("World"); ps2-insert("C++");

!

ps2-insert("Hello"); ps3 = ps1-set_union(ps2);!

Requirements"

1. All

functions must have good performance. For example, when taking a union of two

set, you should aim for an algorithm that performs better than inserting all

elements from s1 and s2, one by one, into s3. !

2. There

should be absolutely NO input and output statements in the functions. You may

place temporary I/O statements in a function for testing/debugging purposes

during the development, but you must remove them before the submission.!

3. DO

NOT CHANGE the public member functions defined in the file Set.h. The instructor's test program will import

functions from your module so it is critical that the function signatures are

not changed. !

4. DO

NOT ADD any new public member functions to the Set class. But, you may add as

many private data members and private helper functions as you wish.!

5. Functions

you define in the program should not access any global variables, those define

outside of the class. Use of the global symbolic constants is fine.!

6. In

your source files, include a header comment with your name, the course number,

the assignment number, and any detailed explanation of your functions as

appropriate.!

7. Format

the program in a clean manner. Group statements into logical groups and include

a descriptive comment for each group. Group comments do not have to be verbose.

One sentence would suffice if the statements in a group are written correctly

and precisely. Include enough blank lines between logical groups.!

8. Insert

one or more blank lines between statements as necessary to make the code more

readable and easier to follow. Do not pack statements too densely (e.g., 20

statements with no blank lines between them).! 9. Use comments judiciously. Do

not include redundant and meaningless comments.!

!

Starter Code"

The following source files are provided to you.!

**Filename****Description**set.h

The source file for the

abstract superclass Set.

*Do not make any changes to the public segment of the*

class declaration. The private segment, however, is under your complete

control.class declaration. The private segment, however, is under your complete

control.

prog4.cpp

This sample main program illustrates a basic interaction

with a set.

vectorset.h! vectorset.cpp

This is a partially

completed sample subclass to illustrate how the set union can be implemented

using a vector. This class is provided solely for the purpose of giving you

some idea. You do not have to do anything to this class.

!

Development Ideas"

1. Implement

the TreeSet class using some variation of a binary search tree. Consider making

modifications to the base BST class so the set union, intersection, and

difference can be implemented efficiently.!

2. Implement

the HashSet class using one of the hashing techniques. Again, aim for the

hashing technique that will allow you to implement the set operations

efficiently.!

!

Testing the Functions"

As always, you need to plan

effective testing methodology to verify the implementation.!

!

Submission"

Submit the source files for the

HashSet and TreeSet class—hashset.h, hashset.cpp, treeset.h,

and treeset.cpp—that fully implements the

Set class, via the Sakai course website’s Program Assignment 4 page.!

You'll get 1 file (107.6KB)