Problems 1, 2, and 3
Problem 4
Problem 5
In this solution, the functions with small, fast implementations are inlined.
Alternatively, the inline keyword can be removed and the
function definitions moved to Set.cpp. (inline will be
mentioned at some point in class, so don't worry if you've never seen it
before.)
Notice which member functions are const, and observe the use of the
type alias ItemType.
// Set.h
#ifndef SET_INCLUDED
#define SET_INCLUDED
#include <string>
// Later in the course, we'll see that templates provide a much nicer
// way of enabling us to have Sets of different types. For now,
// we'll use a type alias.
using ItemType = std::string;
const int DEFAULT_MAX_ITEMS = 180;
class Set
{
public:
Set(); // Create an empty set (i.e., one whose size() is 0).
bool empty() const; // Return true if the set is empty, otherwise false.
int size() const; // Return the number of items in the set.
bool insert(const ItemType& value);
// Insert value into the set if it is not already present. Return
// true if the value is actually inserted. Leave the set unchanged
// and return false if value was not inserted (perhaps because it
// was already in the set or because the set has a fixed capacity and
// is full).
bool erase(const ItemType& value);
// Remove the value from the set if present. Return true if the
// value was removed; otherwise, leave the set unchanged and
// return false.
bool contains(const ItemType& value) const;
// Return true if the value is in the set, otherwise false.
bool get(int i, ItemType& value) const;
// If 0 <= i < size(), copy into value the item in the set that is
// strictly less than exactly i items in the set and return true.
// Otherwise, leave value unchanged and return false.
void swap(Set& other);
// Exchange the contents of this set with the other one.
private:
ItemType m_data[DEFAULT_MAX_ITEMS]; // the items in the set
int m_size; // number of items in the set
// At any time, the elements of m_data indexed from 0 to m_size-1
// are in use and are stored in decreasing order.
int findFirstAtMost(const ItemType& value) const;
// Return the position of the largest item in m_data that is <= value,
// or m_size if there are no such items.
};
// Inline implementations
inline
int Set::size() const
{
return m_size;
}
inline
bool Set::empty() const
{
return size() == 0;
}
inline
bool Set::contains(const ItemType& value) const
{
int pos = findFirstAtMost(value);
return pos < m_size && m_data[pos] == value;
}
#endif // SET_INCLUDED
===================================================================
// Set.cpp
#include "Set.h"
Set::Set()
: m_size(0)
{}
bool Set::insert(const ItemType& value)
{
if (m_size == DEFAULT_MAX_ITEMS)
return false;
int pos = findFirstAtMost(value);
if (pos < m_size && m_data[pos] == value)
return false;
for (int k = m_size; k > pos; k--)
m_data[k] = m_data[k-1];
m_data[pos] = value;
m_size++;
return true;
}
bool Set::erase(const ItemType& value)
{
int pos = findFirstAtMost(value);
if (pos == m_size || m_data[pos] != value)
return false;
for ( ; pos < m_size - 1; pos++)
m_data[pos] = m_data[pos+1];
m_size--;
return true;
}
bool Set::get(int i, ItemType& value) const
{
if (i < 0 || i >= m_size)
return false;
value = m_data[i];
return true;
}
void Set::swap(Set& other)
{
// Swap elements. Since the only elements that matter are those up to
// m_size and other.m_size, only they have to be moved.
int minSize = (m_size < other.m_size ? m_size : other.m_size);
for (int k = 0; k < minSize; k++)
{
ItemType tempItem = m_data[k];
m_data[k] = other.m_data[k];
other.m_data[k] = tempItem;
}
// If the sizes are different, assign the remaining elements from the
// longer one to the shorter.
if (m_size > minSize)
for (int k = minSize; k < m_size; k++)
other.m_data[k] = m_data[k];
else if (other.m_size > minSize)
for (int k = minSize; k < other.m_size; k++)
m_data[k] = other.m_data[k];
// Swap sizes
int tempSize = m_size;
m_size = other.m_size;
other.m_size = tempSize;
}
int Set::findFirstAtMost(const ItemType& value) const
{
int begin = 0;
int end = m_size;
while (begin < end)
{
int mid = (begin + end) / 2;
if (value < m_data[mid])
begin = mid + 1;
else if (m_data[mid] < value)
end = mid;
else
return mid;
}
return begin;
}
// PayerSet.h
#ifndef PAYERSET_INCLUDED
#define PAYERSET_INCLUDED
#include "Set.h" // ItemType is a type alias for unsigned long
class PayerSet
{
public:
PayerSet(); // Create an empty payer set.
bool add(unsigned long accountNumber);
// Add an account number to the PayerSet. Return true if and
// only if the account number was actually added.
int size() const;
// Return the number of account numbers in the PayerSet.
void print() const;
// Write to cout every account number in the PayerSet exactly
// once, one per line. Write no other text.
private:
Set m_accounts;
};
// Inline implementations
// Actually, we did not have to declare and implement the default
// constructor: If we declare no constructors whatsoever, the compiler
// writes a default constructor for us that would do nothing more than
// default construct the m_accounts data member.
inline
PayerSet::PayerSet()
{}
inline
bool PayerSet::add(unsigned long accountNumber)
{
return m_accounts.insert(accountNumber);
}
inline
int PayerSet::size() const
{
return m_accounts.size();
}
#endif // PAYERSET_INCLUDED
===================================================================
// PayerSet.cpp
#include "Set.h"
#include "PayerSet.h"
#include <iostream>
using namespace std;
void PayerSet::print() const
{
for (int k = 0; k < m_accounts.size(); k++)
{
unsigned long x;
m_accounts.get(k, x);
cout << x << endl;
}
}
The few differences from the Problem 3 solution are indicated in boldface.
// newSet.h
#ifndef NEWSET_INCLUDED
#define NEWSET_INCLUDED
#include <string>
// Later in the course, we'll see that templates provide a much nicer
// way of enabling us to have Sets of different types. For now,
// we'll use a type alias.
using ItemType = std::string;
const int DEFAULT_MAX_ITEMS = 180;
class Set
{
public:
Set(int capacity = DEFAULT_MAX_ITEMS);
// Create an empty set with the given capacity.
bool empty() const; // Return true if the set is empty, otherwise false.
int size() const; // Return the number of items in the set.
bool insert(const ItemType& value);
// Insert value into the set if it is not already present. Return
// true if the value is actually inserted. Leave the set unchanged
// and return false if value was not inserted (perhaps because it
// was already in the set or because the set has a fixed capacity and
// is full).
bool erase(const ItemType& value);
// Remove the value from the set if present. Return true if the
// value was removed; otherwise, leave the set unchanged and
// return false.
bool contains(const ItemType& value) const;
// Return true if the value is in the set, otherwise false.
bool get(int i, ItemType& value) const;
// If 0 <= i < size(), copy into value the item in the set that is
// strictly less than exactly i items in the set and return true.
// Otherwise, leave value unchanged and return false.
void swap(Set& other);
// Exchange the contents of this set with the other one.
// Housekeeping functions
~Set();
Set(const Set& other);
Set& operator=(const Set& rhs);
private:
ItemType* m_data; // dynamic array of the items in the set
int m_size; // the number of items in the set
int m_capacity; // the maximum number of items there could be
// At any time, the elements of m_data indexed from 0 to m_size-1
// are in use and are stored in decreasing order.
int findFirstAtMost(const ItemType& value) const;
// Return the position of the largest item in m_data that is <= value,
// or m_size if there are no such items.
};
// Inline implementations
inline
int Set::size() const
{
return m_size;
}
inline
bool Set::empty() const
{
return size() == 0;
}
#endif // NEWSET_INCLUDED
===================================================================
// newSet.cpp
#include "newSet.h"
#include <iostream>
#include <cstdlib>
Set::Set(int capacity)
: m_size(0), m_capacity(capacity)
{
if (capacity < 0)
{
std::cout << "A Set capacity must not be negative." << std::endl;
std::exit(1);
}
m_data = new ItemType[m_capacity];
}
bool Set::insert(const ItemType& value)
{
if (m_size == m_capacity)
return false;
int pos = findFirstAtMost(value);
if (pos < m_size && m_data[pos] == value)
return false;
for (int k = m_size; k > pos; k--)
m_data[k] = m_data[k-1];
m_data[pos] = value;
m_size++;
return true;
}
bool Set::erase(const ItemType& value)
{
int pos = findFirstAtMost(value);
if (pos == m_size || m_data[pos] != value)
return false;
for ( ; pos < m_size - 1; pos++)
m_data[pos] = m_data[pos+1];
m_size--;
return true;
}
bool Set::contains(const ItemType& value) const
{
int pos = findFirstAtMost(value);
return pos < m_size && m_data[pos] == value;
}
bool Set::get(int i, ItemType& value) const
{
if (i < 0 || i >= m_size)
return false;
value = m_data[i];
return true;
}
void Set::swap(Set& other)
{
// Swap pointers to the elements.
ItemType* tempData = m_data;
m_data = other.m_data;
other.m_data = tempData;
// Swap sizes
int tempSize = m_size;
m_size = other.m_size;
other.m_size = tempSize;
// Swap capacities
int tempCapacity = m_capacity;
m_capacity = other.m_capacity;
other.m_capacity = tempCapacity;
}
Set::~Set()
{
delete [] m_data;
}
Set::Set(const Set& other)
: m_size(other.m_size), m_capacity(other.m_capacity)
{
m_data = new ItemType[m_capacity];
// Since the only elements that matter are those up to m_size, only
// they have to be copied.
for (int k = 0; k < m_size; k++)
m_data[k] = other.m_data[k];
}
Set& Set::operator=(const Set& rhs)
{
if (this != &rhs)
{
Set temp(rhs);
swap(temp);
}
return *this;
}
int Set::findFirstAtMost(const ItemType& value) const
{
int begin = 0;
int end = m_size;
while (begin < end)
{
int mid = (begin + end) / 2;
if (value < m_data[mid])
begin = mid + 1;
else if (m_data[mid] < value)
end = mid;
else
return mid;
}
return begin;
}