Simple set using defined data structures
as the objects in the set.
In this demonstation program the items that the set can contain are structures.
Note how the void pointer in the SetItem
structure can be set pointing to any type of structure. The itemType field in
SetItem is used to identify the type of structure that setMember is pointing to.
Typecasting of the void pointer is then used to access the data in the appropriate structure type.
If only the key is needed then the void pointer can be typecast to a KeyStruct pointer
and the key field accessed in that way no matter what type of structure setMember
is actually pointing to.
This program also demonstrates the Union, Intersection, and Difference set operations.
Header file defining a Set class.
//===================================================================
// File: Set.h
// Purpose: Header file for a demonstration of a set class.
// Author: Dr. Rick Coleman
//===================================================================
#ifndef SET_H
#define SET_H
#include "SetItems.h"
class Set
{
private:
SetItem *head; // Head of linked list of items in the set
public:
Set(); // Constructor
~Set(); // Destructor
void addItem(SetItem *item); // Add an item to the set
bool removeItem(int itemType, int key); // Remove an item from the set
Set *Union(Set *aSet); // Return new set-Union this and aSet
Set *Intersection(Set *aSet); // Return new set--Intersection this and aSet
Set *Difference(Set *aSet); // Return new set--Differrence this and aSet
bool contains(int itemType, void *item); // Return true if item is in the set
bool contains(SetItem *item); // Return true if item in this SetItem is in the set
int itemCount(); // Return number of items in this set
SetItem *copy(SetItem *anItem); // Copy an item in the set
SetItem *copy(int index); // Copy item at index (item at head = index 0)
void PrintSet(); // Print all data in this set
};
#endif
Header file defining the data structures of items in the set.
//===================================================================
// File: SetItems.h
// Purpose: Structures defining the types of items that can be added
// to a demonstration of a set class.
// Author: Dr. Rick Coleman
//===================================================================
#ifndef SETITEMS_H
#define SETITEMS_H
// Define a structure to use as a set item
struct SetItem
{
int itemType; // Identify the type of item this is
SetItem *next;
void *setMember; // pointer to the set member object
};
// Define some constants for the data types
#define INTEGER 0
#define LONG 1
#define FLOAT 2
#define DOUBLE 3
// Define a generic structurd type with key only
struct KeyStruct
{
int key;
};
// Define four structures as item types
struct IntStruct
{
int key; // Unique key for this item type
int data;
};
struct LongStruct
{
int key; // Unique key for this item type
long data;
};
struct FloatStruct
{
int key; // Unique key for this item type
float data;
};
struct DoubleStruct
{
int key; // Unique key for this item type
double data;
};
#endif
Implementation file defining a Set class.
//===================================================================
// File: Set.cpp
// Purpose: Implementation file for a demonstration of a set class.
// Author: Dr. Rick Coleman
//===================================================================
#include "SetItems.h"
#include "Set.h"
#include <iostream>
using namespace std;
//------------------------------------------
// Class constructor
//------------------------------------------
Set::Set()
{
head = NULL;
}
//------------------------------------------
// Class destructor
//------------------------------------------
Set::~Set()
{
SetItem *temp;
temp = head;
while(temp != NULL)
{
head = head->next; // Advance head
delete temp->setMember; // Delete the setMember item structure
delete temp; // Delete this list item
temp = head;
}
}
//------------------------------------------
// Add an item to the set.
// Since order does not matter all new items
// will be added at the head of the list.
//------------------------------------------
void Set::addItem(SetItem *item)
{
item->next = head;
head = item;
}
//------------------------------------------
// Remove an item from the set
//------------------------------------------
bool Set::removeItem(int itemType, int key)
{
SetItem *back, *temp;
if(head == NULL) return false; // Nothing to remove
back = NULL;
temp = head;
while(temp != NULL)
{
// See if this is the correct type
if(temp->itemType == itemType)
{ // Use the generic structure type to fetch the key
if(key == ((KeyStruct *)(temp->setMember))->key)
{ // Found the one to delete
if(back == NULL) // Delete head of list
{
head = head->next;
}
else
{
back->next = temp->next;
}
// Delete the item just removed and its' list node
delete temp->setMember;
delete temp;
// Done so return
return true;
}
// If that was not the one we are searching for then advance pointers
back = temp;
temp = temp->next;
}
}
// If we get here we didn't find the one to remove
return false;
}
//------------------------------------------
// Return a new set which is the union of
// this set and the set passed in as an arg.
//------------------------------------------
Set *Set::Union(Set *aSet)
{
Set *newSet = new Set();
SetItem *temp;
int count;
// Add all the items from this set
temp = head;
while(temp != NULL)
{
newSet->addItem(this->copy(temp));
temp = temp->next;
}
// Now add all the items from the other set
count = aSet->itemCount();
for(int i=0; i<count; i++)
{
newSet->addItem(aSet->copy(i));
}
return newSet;
}
//------------------------------------------
// Return a new set which is the intersection
// of this set and the set passed in as an arg.
//------------------------------------------
Set *Set::Intersection(Set *aSet)
{
Set *newSet = new Set();
SetItem *temp;
// Add all the items in both sets
temp = head;
while(temp != NULL)
{
if(aSet->contains(temp))
newSet->addItem(this->copy(temp));
temp = temp->next;
} return newSet;
}
//------------------------------------------
// Return a new set which is the difference
// of this set and the set passed in as an
// arg. Difference means all itens in this
// set that are not in the arg set.
//------------------------------------------
Set *Set::Difference(Set *aSet)
{
Set *newSet = new Set();
SetItem *temp;
// Add all the items in this set but not in the other
temp = head;
while(temp != NULL)
{
if(!(aSet->contains(temp)))
newSet->addItem(this->copy(temp));
temp = temp->next;
}
return newSet;
}
//------------------------------------------
// Return true if this set contains the
// indicated item. We consider a match
// if the ItemType, Key, and data value
// matches the one in the given item.
//------------------------------------------
bool Set::contains(int itemType, void *item)
{
SetItem *temp;
temp = head;
while(temp != NULL)
{
if((itemType == temp->itemType) &&
(((KeyStruct *)item)->key == ((KeyStruct *)temp)->key))
{
switch(itemType)
{
case INTEGER :
if( ((IntStruct *)item)->data == ((IntStruct *)(temp->setMember))->data)
return true;
break;
case LONG :
if( ((LongStruct *)item)->data == ((LongStruct *)(temp->setMember))->data)
return true;
break;
case FLOAT :
if( ((FloatStruct *)item)->data == ((FloatStruct *)(temp->setMember))->data)
return true;
break;
case DOUBLE :
if( ((DoubleStruct *)item)->data == ((DoubleStruct *)(temp->setMember))->data)
return true;
break;
}
}
// That's not it so advance to next item
temp = temp->next;
}
// If still here we didn't find it
return false;
}
//------------------------------------------
// Return true if this set contains the
// indicated item. We consider a match
// if the ItemType, Key, and data value
// matches the one in the given item.
//------------------------------------------
bool Set::contains(SetItem *item)
{
SetItem *temp;
temp = head;
while(temp != NULL)
{
if((item->itemType == temp->itemType) &&
(((KeyStruct *)(item->setMember))->key == ((KeyStruct *)(temp->setMember))->key))
{
switch(item->itemType)
{
case INTEGER :
if( ((IntStruct *)(temp->setMember))->data == ((IntStruct *)(item->setMember))->data)
return true;
break;
case LONG :
if( ((LongStruct *)(temp->setMember))->data == ((LongStruct *)(item->setMember))->data)
return true;
break;
case FLOAT :
if( ((FloatStruct *)(temp->setMember))->data == ((FloatStruct *)(item->setMember))->data)
return true;
break;
case DOUBLE :
if( ((DoubleStruct *)(temp->setMember))->data == ((DoubleStruct *)(item->setMember))->data)
return true;
break;
}
}
// That's not it so advance to next item
temp = temp->next;
}
// If still here we didn't find it
return false;
}
//------------------------------------------
// Return the number of items in this set.
//------------------------------------------
int Set::itemCount()
{
SetItem *temp;
int count = 0;
temp = head;
while(temp != NULL)
{
count++;
temp = temp->next;
}
return count;
}
//------------------------------------------
// Copy a SetItem structure and its item.
//------------------------------------------
SetItem *Set::copy(SetItem *anItem)
{
SetItem *newNode = new SetItem();
newNode->itemType = anItem->itemType; // Set item type
newNode->next = NULL; // Set next pointer to NULL
switch(anItem->itemType)
{
case INTEGER : // Duplicate an INTEGER item
newNode->setMember = (void *)(new IntStruct()); // Cast pointer to void type
// Copy the setMember structure
*((IntStruct *)(newNode->setMember)) = *((IntStruct *)(anItem->setMember));
break;
case LONG : // Duplicate an LONG item
newNode->setMember = (void *)(new LongStruct()); // Cast pointer to void type
// Copy the setMember structure
*((LongStruct *)(newNode->setMember)) = *((LongStruct *)(anItem->setMember));
break;
case FLOAT : // Duplicate an FLOAT item
newNode->setMember = (void *)(new FloatStruct()); // Cast pointer to void type
// Copy the setMember structure
*((FloatStruct *)(newNode->setMember)) = *((FloatStruct *)(anItem->setMember));
break;
case DOUBLE : // Duplicate an DOUBLE item
newNode->setMember = (void *)(new DoubleStruct()); // Cast pointer to void type
// Copy the setMember structure
*((DoubleStruct *)(newNode->setMember)) = *((DoubleStruct *)(anItem->setMember));
break;
}
return newNode;
}
//------------------------------------------
// Copy a SetItem structure and its item at
// the given index. Assuming the index of
// of the item at the head of the list is 0.
//------------------------------------------
SetItem *Set::copy(int index)
{
SetItem *temp;
int count = 0;
SetItem *newNode = new SetItem();
// Find the item to copy
temp = head;
while(temp != NULL)
{
if(count == index) break; // terminate while loop
count++;
temp = temp->next;
}
if(temp == NULL) return NULL; // No node at this index
newNode->itemType = temp->itemType;
newNode->next = NULL;
switch(temp->itemType)
{
case INTEGER : // Duplicate an INTEGER item
newNode->setMember = (void *)(new IntStruct()); // Cast pointer to void type
// Copy the setMember structure
*((IntStruct *)(newNode->setMember)) = *((IntStruct *)(temp->setMember));
break;
case LONG : // Duplicate an LONG item
newNode->setMember = (void *)(new LongStruct()); // Cast pointer to void type
// Copy the setMember structure
*((LongStruct *)(newNode->setMember)) = *((LongStruct *)(temp->setMember));
break;
case FLOAT : // Duplicate an FLOAT item
newNode->setMember = (void *)(new FloatStruct()); // Cast pointer to void type
// Copy the setMember structure
*((FloatStruct *)(newNode->setMember)) = *((FloatStruct *)(temp->setMember));
break;
case DOUBLE : // Duplicate an DOUBLE item
newNode->setMember = (void *)(new DoubleStruct()); // Cast pointer to void type
// Copy the setMember structure
*((DoubleStruct *)(newNode->setMember)) = *((DoubleStruct *)(temp->setMember));
break;
}
return newNode;
}
//------------------------------------------
// Print all data in this set.
//------------------------------------------
void Set::PrintSet()
{
SetItem *temp;
temp = head;
cout << "========== Items in Set ==========\n";
cout << " Type\t\tKey\tValue\n";
cout << "----------------------------------\n";
while(temp != NULL)
{
switch(temp->itemType)
{
case INTEGER :
cout << "INTEGER " << "\t" << ((KeyStruct *)(temp->setMember))->key <<
"\t" << ((IntStruct *)(temp->setMember))->data << "\n";
break;
case LONG :
cout << "LONG " << "\t" << ((KeyStruct *)(temp->setMember))->key <<
"\t" << ((LongStruct *)(temp->setMember))->data << "\n";
break;
case FLOAT :
cout << "FLOAT " << "\t" << ((KeyStruct *)(temp->setMember))->key <<
"\t" << ((FloatStruct *)(temp->setMember))->data << "\n";
break;
case DOUBLE :
cout << "DOUBLE " << "\t" << ((KeyStruct *)(temp->setMember))->key <<
"\t" << ((DoubleStruct *)(temp->setMember))->data << "\n";
break;
}
temp = temp->next;
}
cout << "==================================\n\n";
cout.flush();
}
Demonstration program using the Set class.
//===================================================================
// File: Code401_Sets.cpp
// Purpose: Main file for a demonstration of a set class.
// Author: Dr. Rick Coleman
//===================================================================
#include "SetItems.h"
#include "Set.h"
#include <iostream>
using namespace std;
int main(int argc, char **argv)
{
Set *Set1, *Set2, *aSet;
SetItem *newItem;
// In this demonstration we will create two sets. The first contains
// int 1, int 2, long 4, float 5.6. The second contains int 1, long 2,
// float 3.4, double 4.5
Set1 = new Set();
// Add item 1 to this set
newItem = new SetItem();
newItem->itemType = INTEGER;
newItem->next = NULL;
newItem->setMember = new IntStruct();
((IntStruct *)(newItem->setMember))->data = 1;
((IntStruct *)(newItem->setMember))->key = 1;
Set1->addItem(newItem);
// Add item 2 to this set
newItem = new SetItem();
newItem->itemType = INTEGER;
newItem->next = NULL;
newItem->setMember = new IntStruct();
((IntStruct *)(newItem->setMember))->data = 2;
((IntStruct *)(newItem->setMember))->key = 2;
Set1->addItem(newItem);
// Add item 3 to this set
newItem = new SetItem();
newItem->itemType = LONG;
newItem->next = NULL;
newItem->setMember = new LongStruct();
((LongStruct *)(newItem->setMember))->data = 4L;
((LongStruct *)(newItem->setMember))->key = 1;
Set1->addItem(newItem);
// Add item 4 to this set
newItem = new SetItem();
newItem->itemType = FLOAT;
newItem->next = NULL;
newItem->setMember = new FloatStruct();
((FloatStruct *)(newItem->setMember))->data = 5.6F;
((FloatStruct *)(newItem->setMember))->key = 1;
Set1->addItem(newItem);
Set2 = new Set();
// Add item 1 to this set
// (Note: it is identical to the INTEGER in set 1)
newItem = new SetItem();
newItem->itemType = INTEGER;
newItem->next = NULL;
newItem->setMember = new IntStruct();
((IntStruct *)(newItem->setMember))->data = 1;
((IntStruct *)(newItem->setMember))->key = 1;
Set2->addItem(newItem);
// Add item 2 to this set
newItem = new SetItem();
newItem->itemType = LONG;
newItem->next = NULL;
newItem->setMember = new LongStruct();
((LongStruct *)(newItem->setMember))->data = 2L;
((LongStruct *)(newItem->setMember))->key = 1;
Set2->addItem(newItem);
// Add item 3 to this set
newItem = new SetItem();
newItem->itemType = FLOAT;
newItem->next = NULL;
newItem->setMember = new FloatStruct();
((FloatStruct *)(newItem->setMember))->data = 3.4F;
((FloatStruct *)(newItem->setMember))->key = 1;
Set2->addItem(newItem);
// Add item 4 to this set
newItem = new SetItem();
newItem->itemType = DOUBLE;
newItem->next = NULL;
newItem->setMember = new DoubleStruct();
((DoubleStruct *)(newItem->setMember))->data = 4.5;
((DoubleStruct *)(newItem->setMember))->key = 1;
Set2->addItem(newItem);
// Print both Sets
cout << "Set 1 contains \n";
Set1->PrintSet();
cout << "\nSet 2 contains \n";
Set2->PrintSet();
// Create and print a union of the two
aSet = Set1->Union(Set2);
cout << "Union of Set 1 and Set 2 contains \n";
aSet->PrintSet();
// Delete that set to avoid a memory leak
delete aSet;
// Create and print an intersection of the two
aSet = Set1->Intersection(Set2);
cout << "Intersection of Set 1 and Set 2 contains \n";
aSet->PrintSet();
// Delete that set to avoid a memory leak
delete aSet;
// Create and print a difference of the two
aSet = Set1->Difference(Set2);
cout << "Difference of Set 1 and Set 2 contains \n";
aSet->PrintSet();
delete Set1;
delete Set2;
delete aSet;
return 0;
}
Output from the demonstration program.
Set 1 contains
========== Items in Set ==========
Type Key Value
----------------------------------
FLOAT 1 5.6
LONG 1 4
INTEGER 2 2
INTEGER 1 1
==================================
Set 2 contains
========== Items in Set ==========
Type Key Value
----------------------------------
DOUBLE 1 4.5
FLOAT 1 3.4
LONG 1 2
INTEGER 1 1
==================================
Union of Set 1 and Set 2 contains
========== Items in Set ==========
Type Key Value
----------------------------------
INTEGER 1 1
LONG 1 2
FLOAT 1 3.4
DOUBLE 1 4.5
INTEGER 1 1
INTEGER 2 2
LONG 1 4
FLOAT 1 5.6
==================================
Intersection of Set 1 and Set 2 contains
========== Items in Set ==========
Type Key Value
----------------------------------
INTEGER 1 1
==================================
Difference of Set 1 and Set 2 contains
========== Items in Set ==========
Type Key Value
----------------------------------
INTEGER 2 2
LONG 1 4
FLOAT 1 5.6
==================================