///////////////////////////////////////////////////////////////////////////////
//                                                                           //
//  Copyright (C) 1995-2002 by the Board of Trustees of Leland Stanford      //
//  Junior University.  See LICENSE for details.                             //
//                                                                           //
///////////////////////////////////////////////////////////////////////////////

#ifndef _arraylist_h_
#define _arraylist_h_

#include <iostream.h>
#include "misc.h"

const int DEFAULT_ARRAY_SIZE=4;

template <class _Data>
class Array_List {
private:
  int _size;
  int _numItems;
  _Data *_array;

  void Copy(const Array_List&);
  void Destroy() { delete [] _array; }
  void Resize();
  void QuickSort(Bool (*)(_Data, _Data), int, int);
  int Partition(Bool (*)(_Data, _Data), int, int);
  void QuickSortReverse(Bool (*)(_Data, _Data), int, int);
  int PartitionReverse(Bool (*)(_Data, _Data), int, int);

public:
  Array_List(int size=DEFAULT_ARRAY_SIZE) 
    : _size(size), _numItems(0), _array(new _Data[size]) {}
  Array_List(_Data d, int size=DEFAULT_ARRAY_SIZE)
    : _size(size), _numItems(0), _array(new _Data[size]) { Append(d); }
  Array_List(const Array_List &a) { Copy(a); }
  ~Array_List() { Destroy(); }
  Array_List& operator=(const Array_List&);

  void Append(const _Data);
  void Append(const Array_List<_Data>&);
  void Insert(int, _Data);
  void Delete(int);
  void Grow(int i)
    { ASSERT(_numItems<i); while (_size < i) Resize(); _numItems = i; }
  void Shrink(int i) { ASSERT(i<=_numItems); _numItems = i; }
  int NumItems() const { return _numItems; }
  _Data& operator[](int i) const { return _array[i]; }
  void Sort(Bool (*)(_Data, _Data));
  void SortReverse(Bool (*)(_Data, _Data));
  template<class _D> friend ostream& operator<<(ostream&, const Array_List<_D>&);
};


template <class _Data>
void Array_List<_Data>::Copy(const Array_List<_Data> &a) 
{
  _size = a._size;
  _numItems = a._numItems;
  _array = new _Data[_size];

  for (int i=0; i<_numItems; i++)
    _array[i] = a._array[i];
}


template <class _Data>
Array_List<_Data>& Array_List<_Data>::operator=(const Array_List<_Data> &a)
{
  if (&a!=this) {
    Destroy();
    Copy(a);
  }
  return *this;
}


template <class _Data>
void Array_List<_Data>::Resize()
{
  _size *= 2;
  _Data *tmp = new _Data[_size];
  for (int i=0; i<_numItems; i++)
    tmp[i] = _array[i];
  delete [] _array;
  _array = tmp;
}


template <class _Data>
void Array_List<_Data>::QuickSort(Bool (*LT)(_Data, _Data), int p, int r)
{
  if (p < r) {
    int q = Partition(LT, p, r);
    QuickSort(LT, p, q);
    QuickSort(LT, q+1, r);
  }
}


template <class _Data>
int Array_List<_Data>::Partition(Bool (*LT)(_Data, _Data), int p, int r)
{
  const _Data& x = _array[p];
  int i = p - 1;
  int j = r + 1;
  while (TRUE) {
    do {
      j = j - 1;
    } while ((*LT)(x, _array[j]));
    do {
      i = i + 1;
    } while ((*LT)(_array[i], x));
    if (i < j) {
      _Data d = _array[i];
      _array[i] = _array[j];
      _array[j] = d;
    }
    else return j;
  }
}


template <class _Data>
void Array_List<_Data>::QuickSortReverse(Bool (*LT)(_Data, _Data), int p, int r)
{
  if (p < r) {
    int q = PartitionReverse(LT, p, r);
    QuickSortReverse(LT, p, q);
    QuickSortReverse(LT, q+1, r);
  }
}


template <class _Data>
int Array_List<_Data>::PartitionReverse(Bool (*LT)(_Data, _Data), int p, int r)
{
  const _Data& x = _array[p];
  int i = p - 1;
  int j = r + 1;
  while (TRUE) {
    do {
      j = j - 1;
    } while ((*LT)(_array[j], x));
    do {
      i = i + 1;
    } while ((*LT)(x, _array[i]));
    if (i < j) {
      _Data d = _array[i];
      _array[i] = _array[j];
      _array[j] = d;
    }
    else return j;
  }
}


template <class _Data>
void Array_List<_Data>::Insert(int index, _Data d)
{
  ASSERT(index<=_numItems);
  if (_size==_numItems) Resize();
  for (int i=_numItems-1; i>=index; i--)
    _array[i+1] = _array[i];
  _array[index] = d;
  _numItems++;
}    


template <class _Data>
void Array_List<_Data>::Delete(int index)
{
  ASSERT(index<_numItems);
  for (int i=index+1; i<_numItems; i++)
    _array[i-1] = _array[i];
  _numItems--;
}    


template <class _Data>
void Array_List<_Data>::Append(const _Data d)
{
  if (_size==_numItems) Resize();
  _array[_numItems] = d;
  _numItems++;
}    


template <class _Data>
void Array_List<_Data>::Append(const Array_List<_Data> &al)
{
  for (int i=0; i<al.NumItems(); i++)
    Append(al._array[i]);
}    


template <class _Data>
void Array_List<_Data>::Sort(Bool (*LT)(_Data, _Data))
{
  QuickSort(LT, 0, _numItems-1);
}


template <class _Data>
void Array_List<_Data>::SortReverse(Bool (*LT)(_Data, _Data))
{
  QuickSortReverse(LT, 0, _numItems-1);
}


template <class _Data>
ostream& operator<<(ostream &os, const Array_List<_Data> &a)
{
  for (int i=0; i<a._numItems; i++)
    os << a._array[i] << ' ';
  return os;
}

#endif