Thread: Derived Class Templates

Background:

I have two templated classes, one derived from another. Both of them seperated out into header files and templated implementations. In my client_driver.cpp I am suppose to use the sets:

Code:

A {1,3,8}
B {2,3,5,10}
C {4,6}

and show:

Code:

A && B
A - B
A || B
A / B
A && C
A - C
A || C
A / C

I understand that the operators aren't working because the high and lo indexes don't match up, but I cannot figure out a way to correct this.
Please help.

*/

Code:

//  array_v.h




#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.h




#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




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);
}


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



// set.h




#ifndef SET_H_
#define SET_H_

#include <iostream>
#include <cassert>

#include "array_v.h"


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 SET_T_
#define SET_T_

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

#include <new>
using std::bad_alloc;

#include <cassert>  //for asset macro

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






// client_driver.cpp





#include "set.h"
#include "array_v.h"

#include <iostream>
#include <cassert>


using namespace std;

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

    A.add(1);
    A.add(3);
    A.add(8);
    A.writeSet();

    B.add(2);
    B.add(3);
    B.add(5);
    B.add(10);
    B.writeSet();

    C.add(4);
    C.add(6);
    C.writeSet();

    A && B;   //  I need these to work.
    A - B;
    A || B;
    A / B;
    A && C;
    A - C;
    A || C;
    A / C;
}

In the first set (A), I have the elements of 1 as the low, and 8 as the high.
In the second set (B), I have the elements of 2 as the low, and 10 as the high.
For the operator && code below, it checks if the low values of A and B are not equal. They are always going to be not equal... and give me an error of invalid ranges.

Code:

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;
}