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

#include "Deque.h"

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

// $Log: Deque.c,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:31  rjj
//Changed 'emptyp()' to 'empty()'.
//
//Revision 1.4  93/11/14  19:55:29  rjj
//Rename forwardp() to forward().
//
//Revision 1.3  1993/11/11  01:13:42  rjj
//Added op== and op!=, squashed some buggs.
//
//Revision 1.2  93/05/26  23:15:49  rjj
//Added copyright notice.
//
//Revision 1.1  92/12/16  02:11:21  rjj
//Initial revision
//


/////////////////////////////////////////////////////////////////////////////
// IA_Deque<T> private and IA_Cell<T> helper functions
/////////////////////////////////////////////////////////////////////////////

template <class T>
void  IA_Deque<T>::unlinkCell(IA_Cell<T>* theCell) {

    (theCell->next())->setPrev(theCell->prev());
    (theCell->prev())->setNext(theCell->next());

    // Ensure that this cell is not pointing to other cells.
    theCell->setNext(theCell);
    theCell->setPrev(theCell);
}


template <class T>
void  IA_Deque<T>::deleteCells() {
    while (!this->empty()) {
	this->delFront();
    }
}


/////////////////////////////////////////////////////////////////////////////
//
// class IA_Deque
//
/////////////////////////////////////////////////////////////////////////////


//================================================================
// Constructors & Destructor
//================================================================

// yielding a copy of the IA_Deque d
// NOTE: this version does not share storage
template <class T>
IA_Deque<T>::IA_Deque(const IA_Deque<T>& d) {

    IA_DequeIter<T> dIter(d);
    T val;

    this->nullDeque();
    while( dIter(val) ) {
	this->insBack(val);
    }
}


template <class T>
IA_Deque<T>::IA_Deque(T *vec, unsigned size) {
    // where size = number of elements in vec

    this->nullDeque();
    for (int i=0; i<size; i++) {
	this->insBack(vec[i]);
    }
}


template <class T>
IA_Deque<T>::IA_Deque(T v0) {
    this->nullDeque();
    this->insFront(v0);
}

template <class T>
IA_Deque<T>::IA_Deque(T v0, T v1) {
    this->nullDeque();
    this->insFront(v1);
    this->insFront(v0);
}


template <class T>
IA_Deque<T>::IA_Deque(T v0, T v1, T v2) {
    this->nullDeque();
    this->insFront(v2);
    this->insFront(v1);
    this->insFront(v0);
}

template <class T>
IA_Deque<T>::IA_Deque(T v0, T v1, T v2, T v3) {
    this->nullDeque();
    this->insFront(v3);
    this->insFront(v2);
    this->insFront(v1);
    this->insFront(v0);
}

template <class T>
IA_Deque<T>::IA_Deque(T v0, T v1, T v2, T v3, T v4) {
    this->nullDeque();
    this->insFront(v4);
    this->insFront(v3);
    this->insFront(v2);
    this->insFront(v1);
    this->insFront(v0);
}


template <class T>
IA_Deque<T>::~IA_Deque() {
    // Our job is to ensure the removal of all of our cells...
    this->deleteCells();
}


//================================================================
// Operators
//================================================================

template <class T>
IA_Deque<T>&  IA_Deque<T>::operator= (const IA_Deque<T>& rhd)
{
    if (*this == rhd) {  // Nothing to do if true
	return *this;
    }

    // We will reuse any storage *this has currently
    IA_Cell<T> *cp = this->front;
    IA_DequeIter<T> rhdIter(rhd);
    T rhdVal;

    while( rhdIter( rhdVal ) ) {
	if (cp != 0) {
	    // A cell already exists, so reuse it
	    cp->setValue(rhdVal);
	    cp = (cp->next() != this->rear) ? cp->next() : 0; // don\'t wrap
	} else {
	    // No more cells exist, so add to end of *this
	    this->insBack(rhdVal);
	}
    }

    // Now we must be sure to reclaim any storage that was not reused
    if (cp != 0) {
	cp = cp->prev();  // Last valid cell to keep.
	while (this->rear != cp) {
	    this->delBack();   // Just get rid of it
	}
    }

    return *this;
}

template <class T>
int  IA_Deque<T>::operator==(const IA_Deque<T>& rhd) const
{
    T  thisValue, rhdValue;
    IA_DequeIter<T> thisIter(*this), rhdIter(rhd);

    // Run down the deques to see if they differ anywhere.
    while( thisIter(thisValue) && rhdIter(rhdValue) ) {
	if (thisValue != rhdValue)
	    return (int) 0;
    }
    // We now know they are the same so far.
    // Make sure one deque is not longer that the other
    if ( thisIter(thisValue) || rhdIter(rhdValue) ) {
	// Mismatched length
	return (int) 0;
    }
    return (int) 1;  // Same length and same values
}


template <class T>
T  IA_Deque<T>::operator() (int n) const {

    if (this->empty()) {
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return T(0);
    }

    // Should we wrap?  i.e.  n mod (this->length())  ??
    IA_Cell<T> *c = front;

    if (n > 0)
	{for (; n>0; n--) c = c->next();}
    else if (n < 0)
	{for (; n<0; n++) c = c->prev();}

    return c->value();
}

template <class T>
T&  IA_Deque<T>::operator[] (int n) {

    if (this->empty()) {
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return *(new T);
    }

    // Should we wrap?  i.e.  n mod (this->length())  ??
    IA_Cell<T> *c = front;

    if (n > 0)
	{for (; n>0; n--) c = c->next();}
    else if (n < 0)
	{for (; n<0; n++) c = c->prev();}

    return c->cellValue;
}


//================================================================
// Member functions
//================================================================


template <class T>
int  IA_Deque<T>::empty() const {
    return front == 0;
}


template <class T>
T  IA_Deque<T>::first() const {

    if (this->empty()) {
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return T(0);
    }

    return this->front->value();
}


template <class T>
T  IA_Deque<T>::last() const {

    if (this->empty()) {
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return T(0);
    }

    return this->rear->value();
}


template <class T>
unsigned  IA_Deque<T>::length() const {

    if (this->empty()) {
	return 0;
    }
    int CellCount = 0;
    IA_DequeIter<T>  dIter(*this);
    T  val;

    while (dIter(val)) {
	CellCount++;
    }

    return CellCount;
}



//
// Support operations
//

template <class T>
void  IA_Deque<T>::insFront(T val) {

    IA_Cell<T>* newCell = new IA_Cell<T>(val);

    if (this->front == 0) {
	this->rear  = newCell;
    } else {
	newCell->setNext(this->front);    // Point to current front
	newCell->setPrev(this->rear);     // Remember who is last
	this->front->setPrev(newCell);    // #1 now #2
	this->rear->setNext(newCell);
    }
    this->front = newCell;
}


template <class T>
void  IA_Deque<T>::insBack(T val) {

    IA_Cell<T>* newCell = new IA_Cell<T>(val);

    if (this->rear == 0) {
	this->front = newCell;
    } else {
	this->front->setPrev(newCell);  // #1 points to new rear
	this->rear->setNext(newCell);   // last now points to new rear
	newCell->setPrev(this->rear);
	newCell->setNext(this->front);
    }
    this->rear  = newCell;
}


template <class T>
void  IA_Deque<T>::delFront() {
    // When Unlinking the first cell, remember there may be only one...
    if (this->empty()) {
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
    } else {
	unlinkCell(this->front);
	delete this->front;

	if (this->front == this->rear) {  // Deleted last cell in deque
	    this->nullDeque();
	} else {                          // At least one more cells left
	    this->front = this->rear->next();
	}
    }
}


template <class T>
void  IA_Deque<T>::delNth(int n) {
    n = n % (this->length());

    IA_Cell<T> *c = this->front->skip(n);
    
    if (c == this->front) {
	this->delFront();
    } else if (c == this->rear) {
	this->delBack();
    } else {
	unlinkCell(c);
	delete c;
    }
}


template <class T>
void  IA_Deque<T>::delValue(const T& val) {
    if ( this->empty() ) {
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
    } else {
	IA_Cell<T> *c = this->front;
	while (c != this->rear) {
	    if (c->value() == val) {
		break;
	    } else {
		c = c->next();
	    }
	}

	if (c->value() == val) {
	    if (c == this->front) {
		this->delFront();
	    } else if (c == this->rear) {
		this->delBack();
	    } else {
		unlinkCell(c);
		delete c;
	    }
	} else {
	    // Should we throw here?
	}
    }
}


template <class T>
void  IA_Deque<T>::delBack() {
    // When unlinking the last cell, remember there may be only one...
    if (this->empty()) {
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
    } else {
	unlinkCell(this->rear);
	delete this->rear;

	if (this->front == this->rear) {   // Deleted last cell in deque
	    this->nullDeque();
	} else {                           // At least one more cells left
	    this->rear = this->front->prev();
	}
    }
}


template <class T>
void  IA_Deque<T>::reverse(IA_Deque<T>& theResult) {

    if (this->empty()) {
	theResult.deleteCells();  // Now both are empty
	return;
    }

    // We have a potential problem if theResult is us,
    //   but we can use a clever routine if this is the case.
    if (theResult != *this) {
	// could be very clever and try to reuse storage in theResult
	// but for now I will op for the simplist way..
	theResult.deleteCells();

	IA_DequeIter<T> dIter(*this);
	T val;

	while( dIter(val) ) {
	    theResult.insFront(val);
	}
    } else {
	// We can do an in place reverse here !
	IA_Cell<T> *cellToReverse, *cp;
	cellToReverse = this->front;
	while (cellToReverse != this->rear) {
	    cp = cellToReverse->next();
	    cellToReverse->setNext( cellToReverse->prev() );
	    cellToReverse->setPrev( cp );
	    cellToReverse = cp;
	}
	// Don\'t forget to switch the front and rear pointers.
	cp = this->front;
	this->front = this->rear;
	this->rear = cp;
    }
}


template <class T>
void  IA_Deque<T>::sub (int m, int n, IA_Deque<T>& theResult) {

    int dLen = this->length();
    if ( (this->empty()) || (n-m<0) || (dLen <= (n-m)) ) {
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return;
    }

    IA_Cell<T> *c = this->front->skip(m);   // Start Cell for this job
    if (*this != theResult) {
	// Take the easy way and just reclaim all of theResult\'s storage
	theResult.deleteCells();

	// NOTE:  We use the cell pointers rather than a IA_DequeIter
	//        to allow the wrap around the ends.
	IA_Cell<T> *c = this->front->skip(m);   // Start Cell for this job
	theResult.insFront(c->value());

	for (int i=m; i<n; i++) {
	    c = c->next();
	    theResult.insBack( c->value() );
	}
    } else {
	// Since we are eating at ourself, we need to be a little careful.
	// Set the front pointer correctly and the delete off the back.
	this->front = c;            // Force front pointer
	this->rear = c->prev();     // Force back pointer
	for ( ; dLen > (n-m+1); dLen-- ) {
	    this->delBack();        // Delete unwanted cells
	}
    }
}


//================================================================
// Friend functions
//================================================================

template <class T>
void  concat (const IA_Deque<T>& lhd, const IA_Deque<T>& rhd,
	      IA_Deque<T>& theResult) {
    if ((theResult == lhd) && (theResult == rhd)) {
	ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);
	return;
    }

    if (lhd.empty()) {
	theResult = rhd;
    } else if (rhd.empty()) {
	theResult = lhd;
    } else if (theResult == lhd) {
        IA_DequeIter<T> dIter(rhd);  // Prepare to iterate over the rhd
        T val;                       // Our receptacle
        while( dIter(val) ) {
            theResult.insBack(val);
        }
    } else if (theResult == rhd) {
	IA_DequeIter<T> dIter(lhd, -1);  // Backwards iterator
	T val;
	while( dIter(val) ) {
	    theResult.insFront(val);
	}
    } else {
	if ((theResult != lhd) && (theResult != rhd)) {
	    theResult = lhd;

	    IA_DequeIter<T> dIter(rhd);  // Prepare to iterate over the rhd
	    T val;                       // Our receptacle
	    
	    while( dIter(val) ) {
		theResult.insBack(val);
	    }
	}
    }
}




/////////////////////////////////////////////////////////////////////////////
//
//  class IA_DequeIter
//
/////////////////////////////////////////////////////////////////////////////

template <class T>
IA_DequeIter<T>::IA_DequeIter(const IA_Deque<T>& d) {

    myDeque = (IA_Deque<T> *) &d;
    myDirection = 1;  // Forward
    this->determineMyFirstCell();
}


template <class T>
IA_DequeIter<T>::IA_DequeIter(const IA_Deque<T>& theDeque,
			int direction) {
    // direction < 0 if backwards
    myDeque = (IA_Deque<T> *) &theDeque;
    this->determineMyDirection(direction);
    this->determineMyFirstCell();
}


template <class T>
int  IA_DequeIter<T>::operator() (T& receptacle) {

    if (myNextCell != 0) {
	receptacle = myNextCell->value();
	this->determineNextCell();
	return 1;
    }

    // We must be at the end, so return 0 and leave;
    return 0;
}



// Here we will try to encapsulate the knowledge of what special values
// for myDirection actually mean.

template <class T>
int  IA_DequeIter<T>::forward() {
    return (myDirection >= 0);
}

template <class T>
void  IA_DequeIter<T>::determineMyDirection(int dValue) {
    if (dValue >= 0) {
	this->myDirection = 1;
    } else {
	this->myDirection = -1;
    }
}


// Our job here is to set my first IA_Cell to either point to the
// first or the last IA_Cell of the IA_Deque, based on our direction.

template <class T>
void  IA_DequeIter<T>::determineMyFirstCell() {
    if (this->forward()) {
	myNextCell = myDeque->front;
    } else {
	myNextCell = myDeque->rear;
    }
}


// Our job is to assign myNextCell based on its current value
// and myDirection.  If we are at the end of the list, we will
// set myNextCell to 0

template <class T>
void  IA_DequeIter<T>::determineNextCell() {

    if (this->forward()) {
	// direction is forward, make sure we do not overshoot the end
	if (myNextCell == myDeque->rear) {
	    myNextCell = 0;
	} else {
	    myNextCell = myNextCell->next();
	}
    } else {
	// Direction is backwards, so do not overshoot the front
	if (myNextCell == myDeque->front) {
	    myNextCell = 0;
	} else {
	    myNextCell = myNextCell->prev();
	}
    }
}
