/************************************************************/
/* FILE: list.H                                             */
/************************************************************/

#ifndef LIST_H
#define LIST_H

#include <iostream.h>

/**********************************************************************
 * FIGarray:
 *
 *      Templated array-based list. It resizes itself as necessary.
 *      Constructor lets you specify the expected size, which is
 *      useful for large arrays (as it improves efficiency in that
 *      case).
 **********************************************************************/
template <class Type>
class FIGarray {
 protected:
   Type*        _array;         // pointer to the data
   int          _num;           // number of elements in the array
   int          _max;           // max elements for currently allocated array

   // realloc() is called automatically as necessary
   // when the array runs out of room. twice as much
   // memory is allocated as previously, and old data
   // is copied to new memory. old memory is deleted:
   void realloc() {
      Type* tmp;
      _max *= 2;
      if((tmp = new Type [_max]) == 0)
         cerr << "FIGarray: realloc failed" << endl;
      for(int i=0; i<_num; i++)
         tmp[i] = _array[i];
      delete [] _array;
      _array = tmp;
   }
   
 public:
   // constructor. 'size' indicates initial size of array (in elements):
   FIGarray(int size=16) : _max(size), _num(0) {
         if((_array = new Type [_max]) == 0)
            cerr << "FIGarray: can't allocate array" << endl;
      }

   // copy constructor:
   FIGarray(const FIGarray& l) : _max(l._max), _num(0) {
         if((_array = new Type [_max]) == 0)
             cerr << "FIGarray: can't allocate array" << endl;
         *this = l;
      }

   // destructor frees allocated memory:
   ~FIGarray() { if (_array != 0) 
                   delete [] _array; }

   // delete memory
   void deleteFIGarray() { if (_array != 0) 
                                delete [] _array; }
               
   // assignment operator:
   FIGarray& operator =(const FIGarray& l) {
      clear();
      for(int i=0; i<l.num(); i++)
         *this += l[i];
      return *this;
   }

   // append an element to array, resize if necessary:
   void operator +=(const Type& el) {
      if(_num == _max)
         realloc();
      _array[_num++] = el;
   }

   // search for given element, remove it:
   int operator -=(Type el)            { return remove(get_element_index(el)); }

   // append element to list only if it isn't in list already:
   int append_uniquely(const Type& el) {
      if(get_element_index(el) == -1) {
         *this += el;
         return 1;
      } else {
         return 0;
      }
   }

   // return index of element, or -1 if element is not found:
   int get_element_index(Type el) const {
      for(int k=_num-1; k>=0; k--)
         if(_array[k] == el)
            return k;
      return -1;
   }

   // base array address:
   Type* array()                                { return _array; }

   // array dereference. can assign into array with this:
   Type& operator [](int j)             const   { return _array[j]; }

   int          valid_index(int k)      const   { return (k>=0 && k<_num); }
   int          num()                   const   { return _num; }
   int          empty()                 const   { return (_num<1); }
   void         truncate(int n)                 { _num = valid_index(n) ? n : _num; }
   void         clear()                         { _num=0; }
   

   // return last element in list:
   Type& last() const {
      if(empty())
         cerr << "FIGarray::last: error: list is empty. returning garbage value..." << endl;
      return _array[_num-1];
   }

   // delete last element in list and return it:
   Type& pop() {
      if(empty()) {
         cerr << "FIGarray::pop: error: list is empty. returning garbage value..." << endl;
         return _array[0];
      } else {
         return _array[--_num];
      }
   }

   // remove element k from list, return 1 on success, 0 on failure:
   int remove(int k) {
      if(valid_index(k)) {
         // replace element k with last element and shorten list:
         _array[k] = _array[--_num];
         return 1;
      } else {
         err_msg("FIGarray::remove: invalid index %d", k);
         dbx_target_stop();
         return 0;
      }
   }
};

#endif  // LIST_H

/* end of file list.H */