/* File: dynlist.C       Copyright glh 10/12/82 */
#include "dynlist.H"

template<class T>
DynList<T>::DynList(const DynList<T>& lst)
{
  length = lst.length;
  size = lst.size;
  element = new T[size];
  for (int i=0; i<length; i++)
    element[i] = lst.element[i];
}

template<class T>
Boolean DynList<T>::Insert(const T& elm, int pos)
{
  if(pos <= 0 || pos > length)
    return false;
  if (length == size) {   // load factor is 1
    size *= 2;            // double the size of the array
    T* new_array = new T[size];
    if (new_array == 0)
      return false;
    for (int i=0; i<pos-1; i++)  // copy 1st part of old array to new array
      new_array[i] = element[i];
    new_array[pos-1] = elm;      // place elm in new array
    for (i=pos; i<=length; i++)  // copy last part of old array to new array
      new_array[i] = element[i-1];
    delete [] element;           // get rid of old array
    element = new_array;
  }
  else {                         // load factor is < 1
    for (int i=length; i>=pos; i--)
      element[i] = element[i-1];
    element[pos-1] = elm;
  }
  length++;
  return true;
}

template<class T>
Boolean DynList<T>::Append(const T& elm)
{
  if (length == size) {   // load factor is 1
    size *= 2;            // double the size of the aray
    T* new_array = new T[size];
    if (new_array == 0)
      return false;
    for (int i=0; i<length; i++)  // copy the old list to the new list
      new_array[i] = element[i];
    new_array[length] = elm;      // append element to the new list
    delete [] element;            // get rid of the old list
    element = new_array;
  }
  else                            // load factor is < 1
    element[length] = elm;
  length++;
  return true;
}

template<class T>
Boolean DynList<T>::Replace(const T& elm, int pos)
{
  if (pos <= 0 || pos > length)
    return false;
  T* new_elm = new T;
  if (new_elem == 0)
    return false;
  *new_elm = elm;
  element[pos-1] = *new_elm;
  return true;
}

template<class T>
T& DynList<T>::Retrieve(int pos) const
{
  assert((pos > 0) && (pos <= length));
  return element[pos-1];
}

template<class T>
Boolean DynList<T>::Delete(int pos)
{
  if (pos <= 0 && pos > length)
    return false;
  if (length-1 <= 0.25 * size)  {  // load factor is <= 1/4 
    size /= 2;                     // reduce the size of the array by 1/2
    T* new_array = new T[size];
    if (new_array == 0)
      return false;
    for (int i=0; i<pos-1; i++)  // copy 1st part of old array to new array
      new_array[i] = element[i]; 
    for (i=pos; i<length; i++)   // copy last part of old array to new array
      new_array[i-1] = element[i];
    delete [] element;           // get rid of old array
    element = new_array;
  } 
  else                           // load factor is > 1/4
    for (int i=pos; i<length; i++)
      element[i-1] = element[i];
  length--;
  return true;
}

template<class T>
DynList<T>& DynList<T>::operator=(const DynList<T>& lst)
{
  if (element != lst.element) {  // check if list is being assigned to itself
    delete [] element;           // get rid of the old list
    length = lst.length;
    size = lst.size;
    element = new T[size];
    for (int i=0; i<length; i++)
      element[i] = lst.element[i];
  }
  return *this;
}

template<class T>
ostream& operator<<(ostream& os, const DynList<T>& lst)
{
  os << "(";
  if (lst.Length() != 0) {
    for (int i=0; i<lst.length; i++)
      os << lst.element[i] << ",";
    os << "\b)";
  }
  else
    os << ")";
  return os;
}