#ifndef GENERICDLLIST_H
#define GENERICDLLIST_H

template <class T> class Vector;


template <class T>
class VectorNode
{
public:

  // Constructor.
  VectorNode()
    {
      prev = next = NULL;
      elem = NULL;
    };

  // Constructor.
  VectorNode(T *e)
    {
      prev = next = NULL;
      elem = e;
    }

  // Constructor.
  VectorNode(T *e,VectorNode *p,VectorNode *n)
    {
      prev = p;
      next = n;
      elem = e;
    };


  friend class Vector<T>;


private:
  VectorNode<T> *next;
  VectorNode<T> *prev;
  T             *elem;
};


template <class T>
class Vector
{
  // This class implements a vector.
  // Elements are numbered from 0 to getNumberOfElements()-1.


public:
  // Constructor.
  // POST: an empty vector has been created.
  Vector()
    {
      first = last = NULL;
      count = 0;
    };


  // Destructor.
  // POST: ressources taken by the Vector are freed.
  ~Vector()
    {
      VectorNode<T>* tp;
      
      tp = first;
      while (tp != NULL)
	{
	  tp = first->next;
	  delete first;
	  first = tp;
	}
    };
  

  // Get the number of elements.
  int getSize()
    { return count; };
  

  // Insert a VectorNode
  int insert(T *e,int n)
    {
      VectorNode<T> *tp;
    
      tp = new VectorNode<T>(e);
    
      // Can't insert -- memory allocation failed
      if (tp == NULL)
	return FALSE;
      else
	{
	  insertVectorNode(tp,n);
	  return TRUE;
	}
    };

  // Get the Nth element.
  T* get(int n)
    { return (getVectorNode(n))->elem; };
  
  T* remove(int n)
    {
      VectorNode<T>* tp;
      T*             e;
    
      tp = removeVectorNode(n);
      e = tp->elem;
    
      delete tp;
  
      return e;
    };
  
  // Move an element
  void up(int n)
    {
      VectorNode<T>* tp;
      
      tp = removeVectorNode(n);
      insertVectorNode(tp,n-1);
    };

  void down(int n)
    {
      VectorNode<T>* tp;
  
      tp = removeVectorNode(n);
      insertVectorNode(tp,n+1);
    };
  
  
private:
  int            count;
  VectorNode<T>* first,*last;
  

  VectorNode<T>* getVectorNode(int n)
    {
      VectorNode<T>* tp;
  
      tp = first;
      while (n>0)
	{
	  tp = tp->next;
	  n--;
	}
  
      return tp;
    };

  VectorNode<T>* removeVectorNode(int n)
    {
      VectorNode<T>* tp;
  
      tp = getVectorNode(n);
      
      if (tp == first)
	first = first->next;
      
      if (tp == last)
	last = last->prev;

      if (tp->prev != NULL)
	tp->prev->next = tp->next;
  
      if (tp->next != NULL)
	tp->next->prev = tp->prev;
  
      count--;
      return tp;
    };


  void           insertVectorNode(VectorNode<T>* tp,int n)
    {
      VectorNode<T>* right;
  
      // Special case :: the last one
      if (n == count)
	{
	  tp->next = NULL;
	  tp->prev = last;
      
	  if (last != NULL)
	    last->next = tp;
	  else
	    first = tp;
      
	  last = tp;
	}
      else
	{
	  right = getVectorNode(n);
	  tp->next = right;
	  tp->prev = right->prev;
	  
	  if (right == first)
	    first = tp;
	  else	 
	    right->prev->next = tp;
      
	  right->prev = tp;
	}

      count++;
    };

};



#endif // GENERICDLLIST_H