TDArray

// TDArrayMain.cpp

#include <cstdlib>
#include <iostream>
using namespace std;

#include "TDArray.h"
#include "TDArray.cpp"

int main(int argc, char *argv[])
{
  TDArray<int> arr1, arr2(5);
  cout << "arr1.length: " << arr1.Length() << "; arr2.length: " << arr2.Length() << endl;
  if ((argc>1) && (atoi(argv[1]) == 1))	// testing level 1
    {
      cout << "attempt access arr1[0]," << endl;
      cout << arr1[0];
    }
  cout << "arr2: ";
  for (int i=0; i<arr2.Length(); i++)
    {
      cout << arr2[i] << " ";
    }
  cout << endl;

  arr2[0] = 1, arr2[1] = 6, arr2[2] = 9, arr2[3] = 3, arr2[4] = 7;
  cout << "After filling, arr2: ";
  for (int i=0; i<arr2.Length(); i++)
    {
      cout << arr2[i] << " ";
    }
  cout << endl;

  TDArray<int> arr3 = arr2;
  cout << "arr3 = arr2, arr3: ";
  for (int i=0; i<arr3.Length(); i++)
    {
      cout << arr3[i] << " ";
    }
  cout << endl;

  arr1 = arr3(1, 4);
  cout << "arr1 = arr3(1, 4), arr1: ";
  for (int i=0; i<arr1.Length(); i++)
    {
      cout << arr1[i] << " ";
    }
  cout << endl;

  TDArray<int> arr4 = arr3 & arr1;
  cout << "arr4 = arr3 & arr1, arr4: ";
  for (int i=0; i<arr4.Length(); i++)
    {
      cout << arr4[i] << " ";
    }
  cout << endl;

  arr3.Delete(0);
  cout << "arr3.Delete(0), arr3: ";
  for (int i=0; i<arr3.Length(); i++)
    {
      cout << arr3[i] << " ";
    }
  cout << endl;

  arr3.Delete(3);
  cout << "arr3.Delete(3), arr3: ";
  for (int i=0; i<arr3.Length(); i++)
    {
      cout << arr3[i] << " ";
    }
  cout << endl;

  arr3.Insert(7, 3);
  cout << "arr3.Insert(7, 3), arr3: ";
  for (int i=0; i<arr3.Length(); i++)
    {
      cout << arr3[i] << " ";
    }
  cout << endl;

  arr3.Insert(1, 0);
  cout << "arr3.Insert(1, 0), arr3: ";
  for (int i=0; i<arr3.Length(); i++)
    {
      cout << arr3[i] << " ";
    }
  cout << endl;

  cout << "arr4.LSearch(9) = " << arr4.LSearch(9) << endl;
  cout << "arr4.IndexOfMin(3, 6) = " << arr4.IndexOfMin(3, 6) << endl;
  cout << "arr4.IndexOfMin() = " << arr4.IndexOfMin() << endl;

  arr3.SSort();
  cout << "arr3.SSort(), arr3: ";
  for (int i=0; i<arr3.Length(); i++)
    {
      cout << arr3[i] << " ";
    }
  cout << endl;

  arr4.QSort();
  cout << "arr4.QSort(), arr4: ";
  for (int i=0; i<arr4.Length(); i++)
    {
      cout << arr4[i] << " ";
    }
  cout << endl;
  cout << "arr4.BSearch(9) = " << arr4.BSearch(9) << endl;

  return 0;
}

// TDArray.h
#ifndef TDARRAY_
#define TDARRAY_

#include <cstdlib>		// for size_t

template <typename ArrayElem>
class TDArray
{
  // helper function for recursive version of BSearch
  const ArrayElem* BinarySearch(const ArrayElem& elem, const ArrayElem *array, size_t length) const;
  // helper function for QSort
  unsigned int Split(unsigned int low, unsigned int high);
  void QuickSort(unsigned int low, unsigned int high);
protected:
  ArrayElem *array_;
  size_t length_;
public:
  TDArray(size_t length=0);
  TDArray(const TDArray& tdArray);
  ~TDArray(void);

  const ArrayElem& operator[](unsigned int i) const;
  ArrayElem& operator[](unsigned int i);
  size_t Length(void) const { return length_; }

  TDArray& operator=(const TDArray& tdArray);
  TDArray operator()(unsigned int first, unsigned int last) const;
  TDArray operator&(const TDArray& tdArray) const;

  bool Insert(const ArrayElem& elem, unsigned int pos);
  bool Delete(unsigned int pos);

  int LSearch(const ArrayElem& elem) const;
  int BSearch(const ArrayElem& elem) const;

  // helper function for SSort, but also useful for it own
  unsigned int IndexOfMin(unsigned int first, unsigned int last) const;
  unsigned int IndexOfMin() const { return IndexOfMin(0, length_-1); }
  void Swap(unsigned int i1, unsigned int i2)
    {
      ArrayElem temp = array_[i1];
      array_[i1] = array_[i2];
      array_[i2] = temp;
    }
  void SSort(void);
  void QSort(void);
};

#endif

// TDArray.cpp

#include <cstdlib>		// for exit()
#include <iostream>
using namespace std;

#include "TDArray.h"

template <typename ArrayElem>
TDArray<ArrayElem>::TDArray(size_t length)
{
  length_ = length;
  if (length_ == 0)
    array_ = NULL;
  else
    {
      array_ = new ArrayElem[length_];
      if (array_ == NULL)
	{
	  cerr << "\n*** unable allocate TDArray in call to TDArray constructor\n";
	  exit(-1);
	}
    }
}

template <typename ArrayElem>
TDArray<ArrayElem>::TDArray(const TDArray& tdArray)
{
  length_ = tdArray.length_;
  if (tdArray.array_ == NULL)
    array_ = NULL;
  else
    {
      array_ = new ArrayElem[length_];
      if (array_ == NULL)
	{
	  cerr << "\n*** unable allocate TDArray in call to TDArray copy constructor\n";
	  exit(-1);
	}
      else
	{
	  for (int i=0; i<length_; i++)
	    array_[i] = tdArray.array_[i];
	}
    }
}

template <typename ArrayElem>
TDArray<ArrayElem>::~TDArray(void)
{
  length_ = 0;
  if (array_ != NULL)
    {
      delete []array_;
      array_ = NULL;
    }
}

template <typename ArrayElem>
const ArrayElem& TDArray<ArrayElem>::operator[](unsigned int i) const
{
  if (i < length_)
    return array_[i];
  else
    {
      cerr << "\n*** attempt access past end of TDArray in call to operator[]\n";
      exit(-1);
    }
}

template <typename ArrayElem>
ArrayElem& TDArray<ArrayElem>::operator[](unsigned int i)
{
  if (i < length_)
    return array_[i];
  else
    {
      cerr << "\n*** attempt access past end of TDArray in call to operator[]\n";
      exit(-1);
    }
}

template <typename ArrayElem>
TDArray<ArrayElem>& TDArray<ArrayElem>::operator=(const TDArray& tdArray)
{
  if (this != &tdArray)		// self-test
    {
      if (length_ != tdArray.length_)
	{
	  length_ = tdArray.length_;
	  if (array_ != NULL)
	    delete []array_;
	  if (tdArray.array_ == NULL)
	    array_ = NULL;
	  else
	    {
	      array_ = new ArrayElem[length_];
	      if (array_ == NULL)
		{
		  cerr << "\n*** unable reallocate TDArray in call to operator=\n";
		  exit(-1);
		}
	    }
	}
      if (array_ != NULL)
	{
	  for (int i=0; i<length_; i++)
	    array_[i] = tdArray.array_[i];
	}
    }
  return *this;
}

template <typename ArrayElem>
TDArray<ArrayElem> TDArray<ArrayElem>::operator()(unsigned int first, unsigned int last) const
{
  if (last >= length_)
    {
      cerr << "\n*** last too big in call to operator()\n";
      last = length_ - 1;
    }
  if (first > last)
    {
      cerr << "\n*** first pass last in call to operator()\n";
      exit(-1);
    }
  TDArray tdArray;
  tdArray.length_ = last - first + 1;
  tdArray.array_ = new ArrayElem[tdArray.length_];
  if (tdArray.array_ == NULL)
    {
      cerr << "\n*** unable allocate TDArray in call to operator()\n";
      exit(-1);
    }
  else
    {
      for (int i=0, j=first; i<length_; i++, j++)
	tdArray.array_[i] = array_[j];
    }
  return tdArray;
}

template <typename ArrayElem>
TDArray<ArrayElem> TDArray<ArrayElem>::operator&(const TDArray& tdArray) const
{
  TDArray tdArray2;
  if (array_ != NULL && tdArray.array_ != NULL)
    {
      tdArray2.length_ =length_ + tdArray.length_;
      tdArray2.array_ = new ArrayElem[tdArray2.length_];
      if (tdArray2.array_ == NULL)
	{
	  cerr << "\n*** unable allocate TDArray in call to operator&\n";
	  exit(-1);
	}
      else
	{
	  int i, j;
	  for (i=0; i<length_; i++)
	    tdArray2.array_[i] = array_[i];
	  for (j=0; j<tdArray.length_; i++, j++)
	    tdArray2.array_[i] = tdArray.array_[j];
	}
      return tdArray2;
    }
  else if (array_ != NULL)
    return *this;
  else				// if (tdArray.array_ != NULL)
    return tdArray;
}

template <typename ArrayElem>
bool TDArray<ArrayElem>::Insert(const ArrayElem& elem, unsigned int pos)
{
  if (pos > length_)
    {
      cerr << "\n*** attempt insert past end of TDArray\n";
      pos = length_;
    }
  ArrayElem *temp = new ArrayElem[length_+1];
  if (temp == NULL)
    {
      cerr<<"\n*** unable reallocate TDArray in call to Insert\n";
      return false;
    }
  else
    {
      int i;
      for (i=length_; i>pos; i--)
	{
	  temp[i] = array_[i-1];
	}
      temp[i] = elem;
      for (i--; i>=0; i--)
	{
	  temp[i] = array_[i];
	}
      length_++;
      if (array_ != NULL)
	delete []array_;
      array_ = temp;
    }
  return true;
}

template <typename ArrayElem>
bool TDArray<ArrayElem>::Delete(unsigned int pos)
{
  if (pos >= length_)
    {
      cerr << "\n*** last too big in call to Delete\n";
      pos = length_ - 1;
    }
  ArrayElem *temp = new ArrayElem[length_-1];
  if (temp == NULL)
    {
      cerr << "\n*** unable reallocate TDArray in call to Delete\n";
      return false;
    }
  else
    {
      int i;
      for (i=0; i<pos; i++)
	temp[i] = array_[i];
      for (; i<length_; i++)
	temp[i] = array_[i+1];
      length_--;
      if (array_ != NULL)
	delete []array_;
      array_ = temp;
    }
  return true;
}

template <typename ArrayElem>
int TDArray<ArrayElem>::LSearch(const ArrayElem& elem) const
{
  for (int i=0; i<length_; i++)
    {
      if (array_[i] == elem)
	return i;
    }
  return -1;
}

template <typename ArrayElem>
int TDArray<ArrayElem>::BSearch(const ArrayElem& elem) const
{
  int first=0, last = length_-1, mid;
  while (last >= first)
    {
      mid = (first+last) / 2;
      if (array_[mid] == elem)
	return mid;
      else if (array_[mid] > elem)
	last = mid - 1;
      else
	first = mid + 1;
    }
  return -1;
}

/* Recursive version */
/*
template <typename ArrayElem>
int TDArray<ArrayElem>::BSearch(const ArrayElem& elem) const
{
  const ArrayElem *temp = BinarySearch(elem, array_, length_);
  if (temp == NULL)
    return -1;
  else
    return (temp-array_);
}
*/

template <typename ArrayElem>
const ArrayElem* TDArray<ArrayElem>::BinarySearch(const ArrayElem& elem, const ArrayElem *array, size_t length) const
{
  int mid = length / 2;
  if (length == 0)
    return NULL;
  else if (array[mid] == elem)
    return (&array[mid]);
  else if (array[mid] > elem)
    return BinarySearch(elem, array, mid);
  else
    {
      if (length%2 == 0)
	return BinarySearch(elem, array+mid+1, length-mid-1);
      else
	return BinarySearch(elem, array+mid+1, length-mid);
    }
}

template <typename ArrayElem>
unsigned int TDArray<ArrayElem>::IndexOfMin(unsigned int first, unsigned int last) const
{
  if (last >= length_)
    {
      cerr << "\n*** last too big in call to IndexOfMin\n";
      last = length_ - 1;
    }
  if (first > last)
    {
      cerr << "\n*** first pass last in call IndexOfMin\n";
      exit(-1);
    }

  unsigned int minPos = first;
  for (int i=first+1; i<=last; i++)
    {
      if (array_[i] < array_[minPos])
	minPos = i;
    }
  return minPos;
}

template <typename ArrayElem>
void TDArray<ArrayElem>::SSort(void)
{
  unsigned int minPos;
  for (int i=0; i<length_; i++)
    {
      minPos = IndexOfMin(i, length_-1);
      if (minPos != i)
	Swap(i, minPos);
    }
}

template <typename ArrayElem>
unsigned int TDArray<ArrayElem>::Split(unsigned int low, unsigned int high)
{
  int left = low, right = high;
  ArrayElem pivot = array_[low];
  while (left < right)
    {
      while ((right>0) && (array_[right] > pivot))
	right--;
      while ((left<right) && (array_[left] <= pivot))
	left++;
      if (left < right)
	Swap(left, right);
    }
  if (right != low)
    {
      array_[low] = array_[right];
      array_[right] = pivot;
    }
  return right;
}
template <typename ArrayElem>
void TDArray<ArrayElem>::QuickSort(unsigned int low, unsigned int high)
{
  if (low < high)		// has 2 more items
    {
      unsigned int mid = Split(low, high);
      if (mid > 0)
	QuickSort(low, mid-1);
      QuickSort(mid+1, high);
    }
}
template <typename ArrayElem>
void TDArray<ArrayElem>::QSort(void)
{
  if (length_ > 1)
    QuickSort(0, length_-1);
}