array_v.h

// FileName  : array_v.h
// programmer bj streller and general folklore

// PURPOSE : Provides an extended definition of an Array ADT.
// We assume IndexType is a finite collection of consecutively
// enumerated values such as integers, characters, or enum values,
// and that BaseData is any type.
// Bounds checking via the assert macro is also done.
// Furthermore, this array class as been given features similar to
// the STL vector class. Namely, array can be dynamically resized
// via the push_back method if the array is full.


#ifndef ARRAY_V_H
#define ARRAY_V_H

#include <cassert>

template < typename IndexType, typename BaseData >
class Array_V
  {
  public:


	IndexType partition(IndexType lo, IndexType hi);
	IndexType  sort(int numvals);
	void  qsRecursive(IndexType lo, IndexType hi);

    IndexType getHiIndex();
    IndexType getLoIndex();
    void setHiIndex( IndexType index );
    void setLoIndex( IndexType index );

    Array_V( IndexType lo, IndexType hi );  //constructor
    Array_V( int size = 0 );
    Array_V ( const Array_V< IndexType, BaseData >  &initArray );  //copy constructor
    ~Array_V();  //destructor

    BaseData& operator [] ( IndexType );

    Array_V< IndexType, BaseData >&
    operator = ( const Array_V< IndexType, BaseData > &initArray );


    void assign( IndexType i, const BaseData &val );
    // assigns val at location i

    BaseData retrieve( IndexType i );
    // returns the current value at i the array

    int getVolume() const;
    // returns the current volume of the array

    int getNumOf() const;
    // returns current number of elements in array

    bool empty() const;
    // returns true if array is empty and false otherwise


    void push_back( const BaseData& val );
    // insert item at the rear of the array.
    // as a result the array size is increased by 1




    //protected necessary for any derived classes
  private :
    BaseData *arrayData;		// the dynamic array
    IndexType loIndex, hiIndex;
    int volume;				// amount of available space
    int numElements;			// number of elements in the list

    int outOfRange( IndexType i );

    void reserve(int n, bool copy);
    // called by public functions only if n > volume. expands
    // the array capacity to n elements, copies the existing
    // elements to the new space if copy == true, and deletes
    // the old dynamic array. throws exception if memory allocation fails

  };



#include "array_v.t"


#endif

array_v.t

// FileName  : array_v.t
// programmer bj streller and general folklore
// template implementations of the Array_V class


#ifndef ARRAY_V_T
#define ARRAY_V_T

#include <iostream>
using std::cout;
using std::endl;
using std::cerr;

#include <new>
using std::bad_alloc;

#include <cassert>  //for asset macro

//partition
template < typename IndexType, typename BaseData >
IndexType
Array_V< IndexType, BaseData >::partition(IndexType lo, IndexType hi)
{
  BaseData pivot;

  pivot = (*this)[lo];
  while (lo < hi)
  {
    // Begin right-to-left scan

    while (  pivot < (*this)[hi]  && (lo < hi) )
      --hi;
    if (hi != lo) // move entry indexed by hi to left side of partition
      (*this)[lo++] = (*this)[hi];
    // Begin left-to-right scan
    while ( (*this)[lo] < pivot  && (lo < hi) )
      ++lo;
    if (hi != lo) // move entry indexed by lo to right side of partition
      (*this)[hi--] = (*this)[lo];
  }
  (*this)[hi] = pivot;
  return(hi);
}

template < typename IndexType, typename BaseData >
void 
Array_V< IndexType, BaseData >::qsRecursive(IndexType lo, IndexType hi)
{
  IndexType pivotPoint;

  pivotPoint = partition(lo, hi);
  if (lo < pivotPoint)
    qsRecursive(lo, pivotPoint - 1);
  if (pivotPoint < hi)
    qsRecursive(pivotPoint + 1, hi);
}

//sort
template < typename IndexType, typename BaseData >
IndexType
Array_V< IndexType, BaseData >::sort(int numvals)
{
  qsRecursive(loIndex, loIndex + numvals - 1);
}

template < typename IndexType, typename BaseData >
IndexType
Array_V< IndexType, BaseData >::getHiIndex()
{
  return  hiIndex;
}

template < typename IndexType, typename BaseData >
IndexType
Array_V< IndexType, BaseData >::getLoIndex()
{
  return  loIndex;
}


template < typename IndexType, typename BaseData >
void Array_V< IndexType, BaseData >::setLoIndex( IndexType index )
{
  loIndex = index;
}


template < typename IndexType, typename BaseData >
void Array_V< IndexType, BaseData >::setHiIndex( IndexType index )
{
  hiIndex = index;
}




//constructor
template < typename IndexType, typename BaseData >
Array_V< IndexType, BaseData >::Array_V(IndexType lo, IndexType hi)
{
  arrayData = new BaseData[ hi - lo + 1 ];
  assert( arrayData != 0 );
  loIndex = lo;
  hiIndex = hi;
  volume = hi - lo + 1;
  numElements = hi - lo + 1;

  // copy BaseData() into each array element
  int i;
  for (i = 0; i < hi - lo + 1 ; i++)
    arrayData[i] = BaseData( );

}




// constructor. initialize numElements and volume.
// allocate a dynamic array of numElements integers
// and initialize the array with T()
template < typename IndexType, typename BaseData >
Array_V< IndexType, BaseData >::Array_V( int size ):
    arrayData(NULL), loIndex(0), hiIndex(size - 1), volume(0), numElements(0)
{
  int i;

  // if size is 0, volume/numElements are 0 and arrayData is NULL.
  // just return
  if (size == 0)
    return;

  // set capacity to numElements. since we are building the array,
  // copy is false
  reserve( size, false );
  numElements = size;

  // copy BaseData() into each array element
  for (i = 0; i < size; i++)
    arrayData[i] = BaseData( );


}



// set the volumw to n elements
template < typename IndexType, typename BaseData >
void Array_V< IndexType, BaseData >::reserve(int n, bool copy)
{

  BaseData *new_arrayData;
  int i;

  // allocate a new dynamic array with n elements
  new_arrayData = new BaseData[ n ];

  if (new_arrayData == NULL)
    {
      throw  bad_alloc ();
      cerr << "Array_V::reserve(): memory allocation failure";
      abort();
    }



  // if copy is true, copy elements from the old list to the new list
  // may have to set loIndex and hiIndex if copy
  if ( copy )
    for ( i = 0; i < numElements; i++ )
      new_arrayData[ i ] = arrayData[ i ];


  // delete original dynamic array. if arrayData is NULL, the array was
  // originally empty and there is no memory to delete
  if ( arrayData != NULL )    
    delete [] arrayData;


  // set arrayData to the value newArr. update volume
  arrayData = new_arrayData;
  volume = n;

}




// copy constructor. make the current object a copy of init.
// for starters, use initialization list to create an empty
// array
template < typename IndexType, typename BaseData >
Array_V< IndexType, BaseData >::Array_V( const Array_V< IndexType, BaseData > &initArray ):
    arrayData(NULL), loIndex(0), hiIndex(-1), volume(0), numElements(0)
{
  // if size is 0, numElements/volume  are 0 and arrayData is NULL - just return
  if ( initArray.numElements == 0 )
    return;


  //otherwise
  // set numElements to initArray.numElements. since we are building the array,
  // copy is false

  reserve( initArray.numElements, false );

  loIndex = initArray.loIndex;
  hiIndex = initArray.hiIndex;
  numElements = initArray.numElements;


  //the following is the object's []
  IndexType i;
  BaseData* p;
  p = initArray.arrayData;

  // copy items from the init.array to the newly allocated array
  for (i = loIndex; i <= hiIndex; i++, p++)
    ( (*this)[i] ) = *p;


}





//void return implies no chaining
// replace existing object (left-hand operand) by
// init ( the right-hand operand)
template < typename IndexType, typename BaseData >
Array_V< IndexType, BaseData >&
Array_V< IndexType, BaseData >::operator = ( const Array_V< IndexType, BaseData > &initArray )
{

  if (this == &initArray)
    return *this;   //avoid self assignment



  ////  Why ????   // and causes problems /////////////
  // delete [] arrayData;
  // next line is the error
  // program in free(): error: chunk is already free

  
  IndexType i;

  // check volume to see if a new array must be allocated
  if ( volume < initArray.numElements )
    // make volume of current object the size of initArray. don't
    // do a copy, since we will replace the old values

    reserve( initArray.numElements, false );

  // assign current object to have same size as rhs and indices
  numElements = initArray.numElements;
  loIndex = initArray.loIndex;
  hiIndex = initArray.hiIndex;

  // copy items from initArray.arrayData to the this array

  BaseData* p;
  p = initArray.arrayData;

  for (i = loIndex; i <= hiIndex; i++, p++)
    ((*this)[i]) = *p;


  return *this;

}




template < typename IndexType, typename BaseData >
Array_V< IndexType, BaseData >::~Array_V()
{
  if ( arrayData != NULL)
   {
    delete [] arrayData;
    arrayData = NULL; 
   }
    
}



template < typename IndexType, typename BaseData >
int Array_V< IndexType, BaseData >::outOfRange(IndexType i)
{
  if ( (i < loIndex) || (i > hiIndex) )
    {
      cerr << "Index " << i <<  " out of range"<< endl;
      return (1);
    }
  else
    return (0);

}



template < typename IndexType, typename BaseData >
void Array_V< IndexType, BaseData >::assign( IndexType i, const BaseData &val )
{
  assert(!outOfRange(i));
  arrayData[ i - loIndex ] = val;
}



template < typename IndexType, typename BaseData >
BaseData Array_V< IndexType, BaseData >::retrieve(IndexType i)
{
  assert(!outOfRange(i));
  return(arrayData[ i - loIndex ]);
}



//returns an address so can be an lvalue
template < typename IndexType, typename BaseData >
BaseData& Array_V< IndexType, BaseData >::operator [] (IndexType i)
{
  assert(!outOfRange(i));
  return(arrayData[ i - loIndex ]);
}


//this ok
template < typename IndexType, typename BaseData >
int Array_V< IndexType, BaseData >::getVolume() const
  {
    return volume;
  }



template < typename IndexType, typename BaseData >
int Array_V< IndexType, BaseData >::getNumOf() const
  {
    return numElements;
  }



template < typename IndexType, typename BaseData >
bool Array_V< IndexType, BaseData >::empty() const
  {
    return  numElements == 0;
  }




// insure that list has sufficient volume,
// add the new item to the list, and increment numElements
template < typename IndexType, typename BaseData >
void Array_V< IndexType, BaseData >::push_back(const BaseData& item)
{
  // if space is full, allocate more capacity
  if ( numElements == volume )
    {
      if (volume == 0)
        // if volume is 0, set volume to 1.
        // set copy to false because there are
        // no existing elements
        reserve( 1, false );
      else
        // double the volume
        reserve( 2 * volume, true );

      hiIndex++;
    }

  else if ( hiIndex - loIndex + 1  == numElements )
    hiIndex++;

  // add item to the list, update numElements
  arrayData[ numElements ] = item;
  numElements++;

}




#endif

lab_three_client_driver.cpp

#include "set.h"

int main()
{
	Set<int> A(1,8);
	Set<int> B(2,10);
	Set<int> C(4,6);
	Set<int> outSet(0,20);

	A.add(1);A.add(3);A.add(8);
	B.add(2);B.add(3);B.add(5);B.add(10);
	C.add(4);C.add(6);

	A.writeSet();
	B.writeSet();
	C.writeSet();

	outSet = A&&B; //test assignment and intersection operator
	outSet.writeSet();

	//incompatible ranges? Huh?

	/*
	outSet = A-B; //test difference
	outSet.writeSet();

	outSet = A||B; //test union
	outSet.writeSet();
	
	outSet = A/B; //test whatever the hell '/' is supposed to be
	outSet.writeSet();

	/*Do all that again, but with A and C.

	outSet = A&&C;
	outSet.writeSet();

	outSet = A-C;
	outSet.writeSet();

	outSet = A||C;
	outSet.writeSet();

	outSet = A/C;
	outSet.writeSet();
	*/
	

	return 0;
}

set.h

//demo for the set class
//programmer: bj streller

#ifndef SET_H
#define SET_H


#include "array_v.h"
#include <iostream>
#include <cassert>


template <class Universe>
class Set : protected Array_V<Universe,bool>
  {
  public:
    Set (Universe loElement, Universe hiElement);
    Set (Set <Universe> &initSet);
    ~Set();
    void operator = ( Set<Universe> &source );
    bool empty();
    bool operator == ( Set<Universe> &t );
    bool operator <= ( Set<Universe> &t );
    Set operator || ( Set<Universe> &t );//union
    Set operator && ( Set<Universe> &t );//intersection
    Set operator - ( Set<Universe> &t ); //a-b= elements in a not in b
    Set operator / ( Set<Universe> &t ); //a/b= elements in union ab minus
    					//elements in intersection ab
    void add( Universe element );
    void remove( Universe element );
    void writeSet();
    bool inSet( Universe element );
  protected:
    Universe loElement, hiElement;
  };




#include "set.t"



#endif

set.t

#ifndef ARRAY_I_T
#define ARRAY_I_T

//----------------I added this----------------------

template<class Universe>
Set <Universe> Set<Universe>::operator / ( Set<Universe>&t)
{
  Set<Universe> temp(loElement,hiElement);
  Set<Universe> temp = (A||B)-(A&&B) 

  //this obviously won't work, but I don't know how parameters
  //work for overloaded operators. ask professor

    return temp ;
}

template<class Universe>
Set <Universe> Set<Universe>::operator - ( Set<Universe>&t )
{
  Set<Universe> temp(loElement,hiElement);
  if ((loElement!=t.loElement)-(hiElement!=t.hiElement))
    {
      cout << " - invalid ranges" << endl;
      return (*this);
    }
  else for (Universe u = loElement; u <= hiElement; ++u)
      temp[u] = ((*this)[u] - t[u]);
  return temp;
}

//---------------end added this----------------------
template <class Universe>
Set<Universe>::Set(Universe lo, Universe hi):
    Array_V<Universe,bool>(lo,hi)
{
  loElement = lo;
  hiElement = hi;
  for (Universe element = loElement; element <=hiElement; ++element)
    (*this)[element] = false;

}


template <class Universe>
Set <Universe>:: Set(Set<Universe> &initSet)
    :Array_V<Universe, bool> (initSet.loElement,initSet.hiElement)
{
  loElement = initSet.loElement;
  hiElement = initSet.hiElement;

  for (Universe element = loElement; element <=hiElement; ++element)
    (*this)[element] = initSet[element];

}


template<class Universe>
Set <Universe> Set<Universe>::operator || ( Set<Universe>&t)
{
  Set<Universe> temp(loElement,hiElement);
  if ((loElement!=t.loElement)||(hiElement!=t.hiElement))
    {
      cout << " && invalid ranges" << endl;
      return (*this);
    }
  else for (Universe u = loElement; u <= hiElement; ++u)
      temp[u] = ((*this)[u] || t[u]);
  return temp;
}

template<class Universe>
Set <Universe> Set<Universe>::operator && ( Set<Universe>&t )
{
  Set<Universe> temp(loElement,hiElement);
  if ((loElement!=t.loElement)||(hiElement!=t.hiElement))
    {
      cout << " && invalid ranges" << endl;
      return (*this);
    }
  else for (Universe u = loElement; u <= hiElement; ++u)
      temp[u] = ((*this)[u] && t[u]);
  return temp;
}

template <class Universe>
Set<Universe>::~Set()
{}
template <class Universe>
void Set<Universe>:: operator = ( Set<Universe> &source )
{
  if ((loElement != source.loElement) || (hiElement != source.hiElement))
    cout << " invalid assignment: incompatable ranges " << endl;

  else
    for (Universe el = loElement; el <= hiElement; el ++)
      (*this)[el] = source[el];

}

template <class Universe>
bool Set<Universe>::empty()
{
  bool temp = true;
  for (Universe el = loElement; el <= hiElement; el++)
    if ((*this)[el]) temp = false;
  return temp;
}

template <class Universe>
bool Set<Universe>::operator == ( Set<Universe> &t )
{
  bool temp = true;
  if ((loElement!=t.loElement)||(hiElement!=t.hiElement))
    {
      cout << " == invalid ranges" << endl;
      return false;
    }
  else
    {
      for (Universe el = loElement; el <=hiElement; el++)
        if ((*this)[el]!=t[el])
          temp = false;
      return temp;
    }
}


template <class Universe>
bool Set<Universe>::operator <= ( Set<Universe>&t )
{
  bool temp = true;
  if ((loElement!=t.loElement)||(hiElement!=t.hiElement))
    {
      cout << " <= invalid ranges" << endl;
      return false;
    }
  else
    {
      for (Universe el = loElement; el <=hiElement; el++)
        if ((*this)[el]&&(!t[el]))
          temp = false;
      return temp;
    }
}



template <class Universe>
void Set<Universe>::add(Universe el )
  {
    (*this).assign(el, true);
  }

template <class Universe>
void Set<Universe>::remove(Universe el )
  {
    (*this)[el] = false;
  }

template <class Universe>
void Set<Universe>:: writeSet()
{
  bool comma = false;
  cout << '(';
  for (Universe el = loElement; el <=hiElement; el++ )
    {
      if (comma && (*this)[el]) cout << ',';
      if ((*this)[el])
        {
          cout << el ;
          comma = true;
        }
    }
  cout << ')' << endl;

}

#endif