-
-
Save magcius/1236638 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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 | |
#include <cstdlib> | |
//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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include "set.h" | |
int main() | |
{ | |
Set<int> A(1,10); | |
Set<int> B(1,10); | |
Set<int> C(1,10); | |
Set<int> outSet(1,10); | |
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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#ifndef ARRAY_I_T | |
#define ARRAY_I_T | |
//----------------I added this---------------------- | |
template <class Universe> | |
Set<Universe> Set<Universe>::operator / ( Set<Universe>&t ) | |
{ | |
return ((*this) || t) - ((*this) && t); | |
} | |
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]) && ((*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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment