// Oldham, Jeffrey D.
// 2000 Feb 28
// CS1321
//
// Modified by:
// Massingill, Berna L.
// Sometime

// Dynamic Array Class

// A class that supports a a subset of dynamic array operations.
// Associated with a dynamic array is its size, which is initially
// zero and increases and decreases as elements are added and removed.

// The typedef item_type defines the type of variables to be stored
// the array.

// Implementation Decisions:

// We decide to store the array's values in a heap-allocated array
// called "array".  "sz" must always indicate the number of elements
// that can be stored in the array.

// We also provide a function show_op_counts() that writes to a
// specified output stream two numbers that reflect the overhead
// associated with making the array resizable:  
// (1) a count of how many times we reallocated memory for the
// array, and
// (2) a count of how many times we copied an array element from
// one location to another (excluding copying as part of a copy 
// constructor).

#include <iostream>		// has ostream
#include <assert.h>		// has assert()

class dynamicArray {
public:
  typedef unsigned int length_pos;
  typedef int item_type;

private:
  item_type * array;
  length_pos sz;
  unsigned long realloc_count;		// number of reallocations.
  unsigned long copy_count;		// number of elements copied.

  // Copy from the source to the destination.
  static void copy(const item_type *source, item_type *destination,
		   const int sze) {
    for (int i = 0; i < sze; ++i)
      destination[i] = source[i];
    return;
  }

  // Resize array:  Reallocate at correct size and copy contents.
  void resize(length_pos new_sz) {
    item_type * newArray;
    if (new_sz == 0)
      newArray = 0;
    else {
      newArray = new item_type[new_sz];
      length_pos copy_sz = (new_sz < sz ? new_sz : sz);
      copy(array, newArray, copy_sz);
      copy_count += copy_sz;
    }
    ++realloc_count;
    sz = new_sz;
    delete [] array;
    array = newArray;
    return;
  }


public:

  // Constructor with no parameters.
  dynamicArray(void) {
    realloc_count = 0; copy_count = 0; array = 0; sz = 0;
  }

  // Copy constructor:
  // Make a copy of all of dv's contents.  Be sure to copy dv's array.
  dynamicArray(const dynamicArray & dv) {
    realloc_count = 0;
    copy_count = 0;
    sz = dv.sz;
    if (sz == 0)
      array = 0;
    else {
      array = new item_type[sz];
      copy(dv.array, array, sz);
    }
    return;
  }

  // Destructor.
  // Return dynamically-allocated memory to bit bucket.
  ~dynamicArray(void) {
    delete [] array;
  }

  // Overloaded assignment operator.
  // Return dynamically-allocated memory to bit bucket, then make a
  //   copy of dv's contents, as in copy constructor.
  dynamicArray & operator=(const dynamicArray & dv) {
    if (this != &dv) {		// nothing to do if assigning to self
      sz = dv.sz;
      delete [] array;
      if (sz == 0)
	array = 0;
      else {
	array = new item_type[sz];
	copy(dv.array, array, sz);
      }
      ++realloc_count;
      copy_count += sz;
    }
    return *this;
  }

  // Add element to end of array.
  // Pre:  none.
  // Post:  size of array increased by 1; last element is now item.
  void push_back(const item_type & item) {
    resize(sz+1);		// make array one bigger.
    array[sz-1] = item;
    return;
  }

  // Remove element from end of array.
  // Pre:  size of array > 0.
  // Post:  size of array decreased by 1; former last element
  //          returned.
  item_type pop_back(void) {
    assert(sz > 0);
    item_type temp = array[sz-1];
    resize(sz-1);
    return temp;
  }

  // Get size of array.
  // Post:  returns number of elements in array.
  length_pos size(void) const { return sz; }

  // Get array element.
  // Pre:  i < number of elements in array.
  // Post:  returns i-th element of array.
  item_type get(const length_pos i) const {
    assert(i < sz);
    return array[i];
  }

  // Set array element.
  // Pre:  i < number of elements in array.
  // Post:  sets i-th element of array to item.
  void set(const length_pos i, const item_type & item) {
    assert (i < sz);
    array[i] = item;
    return;
  }

  // Show operation counts (reallocations, elements copied).
  // Post:  id and counts of reallocations and elements copied printed 
  //          to ostr.
  void show_op_counts(ostream & ostr, const char id[]) const {
    ostr << "Operation counts for dynamic array " << id << ":\n"
	 << "\t" << realloc_count << " reallocations\n"
	 << "\t" << copy_count << " elements copied\n";
    return;
  }

};