#ifndef _VECTOR_H
#define _VECTOR_H

#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define VECTOR_MINSIZE 16
#define VECTOR_GROWFACTOR 2

template<class T>
class VectorIter;

template<class T>
class Vector
{
 public:
  Vector()
    {
      items=NULL;
      allocated=0;
      size=0;
    }

  void put(int idx, T item)
    {
      assert(idx<size);
      items[idx]=item;
    }

  T get(int idx)
    {
      if (idx>=size)
	return NULL;

      return items[idx];
    }

  void add(T item)
    {
      while (size+1>allocated)
	grow();

      items[size]=item;
      size++;
    }


  int getSize()
    {
      return size;
    }

  void sort(int (*compar)(const void *, const void *))
    {
      qsort(items,size,sizeof(T),compar);
    }

  Vector<T> *clone()
    {
      Vector<T> *v;
      v=new Vector<T>();
      
      for (int idx=0;idx<size;idx++)
	{
	  v->add(get(idx));
	}

      return v;
    }

  /* delete all items that equal value d. The order of the elements
     may be changed. */
  void deleteAll(T d)
    {
      for (int i=0;i<size;i++)
	{
	loop:
	  if (i<size && items[i]==d)
	    {
	      // "shuffle" delete.
	      items[i]=items[size-1];
	      size--;
	      // must try entry i again in case items[size-1] 
	      // was equal to d.
	      goto loop;
	    }
	}
    }

  /* delete an element. The order of the elements may be changed */
  void deleteShuffle(int idx)
    {
      items[idx]=items[size-1];
      
      size--;
    }
  
  VectorIter<T> *elements()
    {
      return new VectorIter<T>(this);
    }

  bool isMember(T t)
    {
      for (int pos=0;pos<size;pos++)
	{
	  if (items[pos]==t)
	    return true;
	}
      return false;
    }
 private:
  T *items;
  
  void grow()
    {
      if (allocated==0)
	allocated=VECTOR_MINSIZE;
      else
	allocated=allocated*VECTOR_GROWFACTOR;

      items=(T*) realloc(items,sizeof(T)*allocated);

      if (items==NULL)
	exit(1);   /* fatal error */

    }

  int allocated;
  int size;
};

template<class T>
class VectorIter
{
 public:
  VectorIter<T>(Vector<T> *vect)
    {
      _vect=vect;
      _pos=0;
    }

  T next()
    {
      if (_pos<_vect->getSize())
	return (_vect->get(_pos++));

      return NULL;
    }

 private:
  Vector<T> *_vect;
  int _pos;
};


#endif