/*
 * Vector.h : a set or dynamic array templates
 *            This comes from a tutorial Robert Harris gave me March 1998.
 *
 * See Copyright for the status of this software.
 *
 * eric@w3.org
 *
 * $Id: Vector.h,v 1.2 1999/11/29 01:19:06 eric Exp $
 */
#define VECT_GROWBY	3
#define VECT_SHRINKBY	5

template <class T>
class VectorComp
{
public:
    virtual int comp(T) = 0;
};

template <class T>
class Vector
{
public:
    Vector(int size = 0, int growBy = VECT_GROWBY, int shrinkBy = VECT_SHRINKBY);
    virtual ~Vector(void)		{Flush();}
    T &	    operator[](int i);
    int	    Delete(int start, int size = 1);
    int	    Delete(T lookFor);
    void    Flush(void)		{delete [] m_vect; m_vesselSize = m_size = 0;}
    int	    Size(void)		{return m_size;}
    int	    Insert(int start, int size, T * newbies);
    int	    Append(int size, T * newbies);
    int	    Append(T newby);
    int	    findIndex(T lookFor);
    int	    findIndex(VectorComp<T> * comp);
    int	    sortIn(VectorComp<T> * comp, T newEl);
    int	    sortOut(VectorComp<T> * comp);
    void    show();

protected:
    virtual int	    insure(int size, int base, int end);

protected:
    int	m_size;
    int	m_vesselSize;
    int	m_growBy;
    int	m_shrinkBy;
    T *	m_vect;
};

template <class T>
Vector<T>::Vector(int size, int growBy, int shrinkBy)
{
    m_vesselSize = m_size = size;
    m_growBy = growBy;
    m_shrinkBy = shrinkBy;
    if (size > 0)
	m_vect = new T[size];
    else
	m_vect = NULL;
}

template <class T>
T & Vector<T>::operator[](int i)
{
    if (i+1 > m_size)
	insure(i+1, m_size, m_size);

    return m_vect[i];
}

/*	Move data around while doing re-allocation copy 
 */
template <class T>
int Vector<T>::insure(int newSize, int base, int end)
{
    T *	newVect;
    int newVesselSize = m_vesselSize;
    if (newSize > m_vesselSize || m_vesselSize - newSize > m_shrinkBy) {
	newVesselSize = newSize + m_growBy; /* we want some room after growth */
	/*	printf("insure to %d/%d\n", newSize, newVesselSize); */
	newVect = new T[newVesselSize];
    } else
	newVect = m_vect;

    if (newVect == NULL)
	return 0;

    if (m_vect) {
	for (int i = 0; i < m_size && i < base && newVect != m_vect; ++i)
	    newVect[i] = m_vect[i];
	if (newSize < m_size) {
	    for (int i = 0; i < end; ++i)
		newVect[newSize - end + i] = m_vect[m_size - end + i];
	} else {   /* copy it backwords to avoid stepping on tail */
	    for (int i = end-1; i >= 0; --i)
		newVect[newSize - end + i] = m_vect[m_size - end + i];
	}
	if (m_vect != newVect) /* delete the old one if we're not */
	    delete [] m_vect;  /* moving data in the same element */
    }

    m_vesselSize = newVesselSize;
    m_size = newSize;
    m_vect = newVect;

    return 1;
}

template <class T>
int Vector<T>::Insert(int start, int size, T* newbies)
{
    insure(m_size + size, start, m_size - start);
    for (int i = 0; i < size; ++i)
	m_vect[start + i] = newbies[i];
    return 1;
}

template <class T>
int Vector<T>::Append(int size, T* newbies)
{
    return Insert(m_size, size, newbies);
}

template <class T>
int Vector<T>::Append(T newby)
{
    return Insert(m_size, 1, &newby);
}

template <class T>
int Vector<T>::Delete(int start, int size)
{
    insure(m_size - size, start, m_size - start - size);
    return 1;
}

template <class T>
int Vector<T>::Delete(T lookFor)
{
    int i = findIndex(lookFor);
    if (i < 0)
	return 0;
    return Delete(i, 1);
}

template <class T>
int Vector<T>::findIndex(T lookFor)
{
    for (int i = 0; i < m_size; ++i)
	if (m_vect[i] == lookFor)
	    return i;
    return -1;
}

template <class T>
int Vector<T>::findIndex(VectorComp<T> * comp)
{
    int i, ret;
    for (i = 0; i < m_size; ++i) {
	if ((ret = comp->comp(m_vect[i])) < 0)
	    return ret;
	if (ret == 0)
	    break;
    }
    return i; /* callers should check against size to see if at end */
}

template <class T>
int Vector<T>::sortIn(VectorComp<T> * comp, T newEl)
{
    int i = findIndex(comp);
    if (i < 0)
	return i;
    Insert(i, 1, &newEl);
    return 0;
}

template <class T>
int Vector<T>::sortOut(VectorComp<T> * comp)
{
    int i = findIndex(comp);
    if (i < 0)
	return i;
    Delete(i, 1);
    return 0;
}

template <class T>
void Vector<T>::show()
{
    for (int i = 0; i < m_size; ++i)
	printf("%p[%d]: %p\n", m_vect, i, m_vect[i]);
}

typedef int Index;

/* IVector: protect indexes into the Vector by maintaining an list of indexes registered with addIndex */
template <class T>
class IVector : public Vector<T>
{
public:
    IVector(int size = 0, int growBy = VECT_GROWBY, int shrinkBy = VECT_SHRINKBY) : Vector<T>(size, growBy, shrinkBy), indexes() {}
    int addIndex(Index * i) {return indexes.Insert(0, 1, &i);}
    int delIndex(Index * i) {return indexes.Delete(i);}
protected:
    virtual int	    insure(int size, int base, int end);
    int adjust(int start, int len, int newPos);
private:
    Vector<int*> indexes;
};

template <class T>
int IVector<T>::insure(int newSize, int base, int end)
{
    adjust(base, m_size, newSize - end);
    return Vector<T>::insure(newSize, base, end);
}

template <class T>
int IVector<T>::adjust(int start, int len, int newPos)
{
    int i;
    for (i = 0; i < indexes.Size(); i++)
	if (*indexes[i] >= start && *indexes[i] <= start+len)
	   *indexes[i] = newPos;
    return 1;
}