The concept of a finite set is actually pretty simple

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Background:

The concept of a finite set is actually pretty simple: taken from some domain, a set is simply a selection of some (or all, or none) elements to include. Each element may appear either one or zero times, and there's no concept of sequence.

For the sake of this exercise, you can assume that the domain is always 0..255 (i.e. there are only 256 possible members that may or may not be present).

 

For visualization, if the domain had been 0..2, then possible selections it could have contained would be:

• {} (the empty set), {0}, {1}, {2}, {0,1}, {0,2}, {0,1,2}, {1,2}

The set can be represented (internally) based on whether or not the members are present, so the same sets as above might be:

• [000], [100], [010], [001], [110], [101], [111], [011]

◦ Naturally, it wouldn't matter if one had [100] or [001], so long as it was consistent (as it's internal) Of course, since the domain goes to 255, the number of possible sets increases a wee bit.

The defined operations are as such:

Expr Name Description C++

A𝖴B Union set of all elements contained within A and/or B A+B, A+b

A∩B Intersection set of all elements common to both A and B A^B, A^b

A\B Difference set of all elements contained within A, but not within B A-B, A-b

a∈B Element test if a is a member of A B[a]

A⊆B Subset test if all elements of A are included within B A<=B

A⊇B Superset test if all elements of B are included within A A=>B

A⊊B Strict subset test if all elements of A are within B, but A≠B A<B

A⊋B Strict superset test if all elements of B are within A, but A≠B A>B

A=B Equality test if both sets contain exactly the same elements A==B

A≠B Inequality test if there exists an element within A or B not found in the other A!=B

U\A Complement set of all possible elements not found within A ~A

|A| Cardinality number of elements within A A()

U Universe set of all possible elements +A

Ø Empty set set containing no elements -A

A=Ø Empty test Test if set is empty !A

Output Stream insertion ostream<<A

Input Stream extraction istream>>A

 

You've been provided a header file to match this specification. You may make slight modifications (e.g. to tweak consts versions), but probably don't need to.

 

Your primary task is to write the corresponding implementation, and then write a very simple test harness to demonstrate it.

 

You'll notice that there's both a public constructor and a private one. Should be obvious why, right?

 

You shouldn't need any dynamic allocation, and similarly shouldn't need to worry about assignment operator overloading, copy constructors, or destructors.

 

Tips:

• Sets are treated as immutable. That means all operations modifying sets actually return a new set containing the result of the operation

◦ This is why we don't have operators like +=, and why [] doesn't return a reference

◦ The stream extraction is the only exception here. Initialization is far easier if it can bend the rules

• Union, difference, and intersection have two versions each: one that accepts two sets, and one that accepts a set and an element

◦ That's why there's an extra to receive an int, and that's what the A+b/A-b stuff above is

• We aren't including the bool() operator (test if not empty), but we can simulate it: !!A

• {1,2,3} is the same as {3,2,1}, so it's perfectly fine for us to store each set in ascending sequence

For your submission, in addition to including your source files, also include a sample execution or two. Because it's somewhat of a nuisance, one possible version of stream extraction is:

std::istream& operator>>(std::istream &in, Set &set) { bool arr[256];

char open; in>>open;

if (in.fail() || open!='{') {

in.setstate(std::ios::failbit); return in;

}

for (int i=0;i<256;i++)

arr[i]=false; std::string buff; std::getline(in,buff,'}'); std::stringstream ss(buff); std::string field;

while (true) {

std::getline(ss,field,','); if (ss.fail()) break;

int el;

std::stringstream se(field); se>>el;

if (el>=0&&el<256)

arr[el]=true;

}

set=Set(arr); return in;

}

You're certainly not required to use this; you're welcome to write something better, if you prefer.

 

As stated above, write your own test harness, just make sure you demonstrate the operators, insertion, extraction, etc.

It isn't a 'real' test harness (it's not like we've covered exceptions yet), so don't knock yourself out here.

 

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of