// -*- C++ -*-
//      Copyright 1993, Center for Computer Vision and Visualization,
//      University of Florida.  All rights reserved.

#ifndef IA_Deque_h_
#define IA_Deque_h_

#include "ia.h"
#include "Cell.h"

static char IA_Deque_h_rcsid[] = "$Id: Deque.h,v 1.6 1994/04/27 18:26:09 rjj Exp $";

// $Log: Deque.h,v $
//Revision 1.6  1994/04/27  18:26:09  rjj
//Changed T operator[](int) const  to operator().
//
//Revision 1.5  1993/11/14  20:04:52  rjj
//Changed 'emptyp()' to 'empty()'.
//
//Revision 1.4  93/11/14  19:55:47  rjj
//Rename forwardp() to forward().
//
//Revision 1.3  1993/11/11  01:14:27  rjj
//Added op== and op!=,
//  removed  const  from reverse(), sub(), and concat() to allow
//  result to be an argument also.
//
//Revision 1.2  93/05/26  23:15:02  rjj
//Added copyright.
//	delNth(int n) appears to have a problem with negative args...
//	will have to worked on later.
//
//
//Revision 1.1  92/12/16  02:10:24  rjj
//Initial revision
//


template <class T>
class IA_DequeIter;  // Forward declaration


template <class T>
class IA_Deque {
private:
    void nullDeque() { front = rear = 0; }
    void unlinkCell(IA_Cell<T>*);

protected:
    void deleteCells();
    // This Deque\'s front  and rear pointers
    IA_Cell<T> *front;
    IA_Cell<T> *rear;
    
public:
    
    IA_Deque() {this->nullDeque();}

    IA_Deque(const IA_Deque<T>&);      // A copy of the Deque
    IA_Deque(T *, unsigned);        // where size = number of elements in vec

    IA_Deque(T v0);                 // Construct Deque with one element: v0
    IA_Deque(T v0, T v1);
    IA_Deque(T v0, T v1, T v2);
    IA_Deque(T v0, T v1, T v2, T v3);
    IA_Deque(T v0, T v1, T v2, T v3, T v4);

    virtual ~IA_Deque();

    IA_Deque<T>&  operator= (const IA_Deque<T>&);

    int           operator==(const IA_Deque<T>&) const;
    int           operator!=(const IA_Deque<T>& rhd) const {
	return ! (*this == rhd);
    }

    T             operator() (int index) const;
    T&            operator[] (int index);
    
    int           empty() const;     // Is the Deque empty? 
    T             first() const;       // The first element in the Deque
    T             last() const;

    void          insFront(T);
    void          insBack(T);

    void          delFront();
    void          delNth(int index);
    void          delValue(const T& aValueToDelete);
    void          delBack();

    void          reverse(IA_Deque<T>& theResult);
    void          sub(int start_index, int end_index, IA_Deque<T>& theResult);
    
    friend
    void          concat (const IA_Deque<T>&, const IA_Deque<T>&,
			  IA_Deque<T>& theResult);

    unsigned      length() const;  //  the number of elements in the Deque

    friend class  IA_DequeIter<T>; // Give it access to class IA_Cell

};

template <class T, class S>
void  IA_Deque_map(S (*f)(T),
		   const IA_Deque<T>& d,
		   IA_Deque<S>& theReceiver);



// NOTE:  The Iterator does not make a copy of the deque, hence
//        if the deque changes under the iterator the behavior
//        will work in this new context.

template <class T>
class IA_DequeIter {
private:
    void determineNextCell();
    void determineMyDirection(int);
    void determineMyFirstCell();

protected:
    IA_Deque<T> *myDeque;
    IA_Cell<T>  *myNextCell;   // The next IA_Cell we will answer with
    int         myDirection;  // >= is forward, otherwise backwards
public:

    // creating an iterator over the IA_Deque.
    //  This may require that reference counting on IA_Deques
    //  be done in order to avoid dangling references.

    // Default is a forward interator.
    IA_DequeIter(const IA_Deque<T>&);

    IA_DequeIter(const IA_Deque<T>& theDeque,
		 int direction); // direction < 0 if backwards

    // yields the next value by assigning it to  receptacle,
    // returns 1 if there was a next value,   0 otherwise.

    int operator() (T& receptacle);

    int forward(); // 1 if direction is forwards, 0 otherwise
};

#endif
