//
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
// Created: MJF 05/22/89 -- Initial design.
// Updated: JCB 06/05/89 -- Implementation.
// Updated: LGO 08/09/89 -- Inherit from Generic
// Updated: MBN 08/20/89 -- Changed usage of template to reflect new syntax
// Updated: MBN 08/24/89 -- Added conditional exception handling and base class
// Updated: MBN 10/07/89 -- Fixed element count bug in get() method
// Updated: MBN 10/11/89 -- Changed "current_position" to "curpos" 
// Updated: MBN 10/19/89 -- Added optional argument to set_compare method
// Updated: MBN 11/01/89 -- Added constructor with user-provided storage param
// Updated: MBN 11/15/89 -- Fixed put() for case when there is no storage
// Updated: MBN 11/17/89 -- Fixed unget() for case when there is no storage
// Updated: LGO 02/02/90 -- Re-wrote practically everything
// Updated: MBN 02/22/90 -- Changed size arguments from long to unsigned long
// Updated: MJF 03/12/90 -- Added group names to RAISE
// Updated: MJF 05/31/90 -- Use "delete [size] data"
// Updated: MJF 06/30/90 -- Added base class name to constructor initializer
//
// The Queue<Type> class is  publicly  derived from   the base Queue class  and
// implements a circular buffer of a user-specified type.  This is accomplished
// by  using the  parameterized type capability   of C++. The queue  will  grow
// dynamically as necessary with the amount of growth  determined by  the value
// of an allocation   size slot. Fixed length queues    are also supported   by
// setting the value of the allocation size slot to INVALID.
//
// The (Base) Queue object contains in, out and limit indices into data
// which is in the Queue<Type> object.
// If in == out, the buffer is empty.
// If in > out, the area from out to in-1 contains available data.
// If out > in, the area from out to limit-1 contains the first part of
// the available data, and the area from first to in-1 contains the rest.
// Note that if the buffer was completely full, in would equal out. We
// we never let this happen, to preserve a simple empty check.
//
// There  are four   constructors   for the   Queue<Type> class.   The    first
// constructor takes  no arguments and creates   an  empty  Queue object of the
// specified type.  The second constructor takes a required argument specifying
// the initial  size  of the queue.  The  third takes a pointer   to a block of
// user-defined storage    and  the number of  elements  the   queue  can hold.
// Finally,  the   third constructor  takes a  single argument  consisting of a
// reference to a Queue<Type> and duplicates its size and element values.
//
// Methods are  provided to get  and unget an item  from the queue, and put and
// unput and item from the queue. This provides addition and removal operations
// for both ends of the queue. A look  method allows an  application to examine
// the item at the head of the queue without removing it. Methods to report the
// number of items in the queue, check the empty  status,  and clear  all items
// from the  queue  are also provided.  The   assignment, output, and  equality
// operators are overloaded and two methods to  set  the allocation growth size
// and compare function are available. Finally, find and  remove  methods allow
// an application  to search for  a particular item and/or  remove   it  from a
// queue.
//

#ifndef QUEUEH					// If no Queue class definition
#define QUEUEH					// Indiciate we have done it

#ifndef BASE_QUEUEH				// If no definition for class
#include <cool/Base_Queue.h>				// include definition file
#endif

template <class Type> Queue {
  typedef Boolean (*Type##_Queue_Compare) (const Type&, const Type&);
}

template <class Type>
class Queue<Type> : public Queue {
private:
  Type* data;					// Pointer to allocated storage

protected:
  static Type##_Queue_Compare compare_s;	// Pointer operator== function
  friend Boolean Type##_Queue_is_data_equal (const Type&, const Type&);
  Boolean grow ();				// Make the queue bigger
  ostream& qprint(ostream& os) CONST;		// Print a queue

public:
  Queue<Type> ();				// Queue q;
  Queue<Type> (unsigned long);			// Queue q(10);
  Queue<Type> (void*, unsigned long);		// Queue with static storage
  Queue<Type> (const Queue<Type>&);		// Queue q = q2;
  ~Queue<Type> ();				// Queue destructor

  Type& get ();					// Get and remove first-in item
  Boolean Queue<Type>::get (Type& result);	// Get and remove first-in item
  Boolean unget (const Type&);			// Put back first-in item 
  Boolean put (const Type&);			// Put new last-in item
  Type& unput();				// Remove last-in item 
  Boolean Queue<Type>::unput (Type& result);	// Remove last-in item 
  inline Type& look();				// Just return next item to get

  inline Type& value ();			// Get current position value
  Boolean find (const Type&);			// Find/set current position 
  Boolean remove ();				// Remove current position item
  Boolean remove (const Type&);			// Find/remove item 
  
  Queue<Type>& operator= (const Queue<Type>&);	// Assignment q = q2;
  Boolean operator== (const Queue<Type>&) CONST; // is equal
  inline Boolean operator!= (const Queue<Type>&) CONST; // is not equal

  void resize (long);				// Resize for at least count
  inline void set_growth_ratio (float);		// Set growth percentage
  inline void set_alloc_size (int);		// Set alloc size
  inline void set_compare(Type##_Queue_Compare = NULL); // Set compare function

  friend ostream& operator<< (ostream&, const Queue<Type>&); 
  inline friend ostream& operator<< (ostream&, const Queue<Type>*);
};


// Type& get () -- Get and remove first-in item in this Queue
// Input:          None
// Output:         Reference to first-in Type value

template<class Type> 
Type& Queue<Type>::get () {
#if ERROR_CHECKING
  if (in == out)				// If no elements in queue
    RAISE (Error, SYM(Queue), SYM(No_Elements),
	   "Queue<%s>::get(): No elements in queue", #Type);
#endif
  long result = out;				// Get data
  if (++out >= limit) out = 0;			// increment and wrap
  return data[result];
}

// Boolean get (Type& result) -- Get and remove first-in item in this Queue
// Input:          None
// Output:         Reference to first-in Type value

template<class Type>
Boolean Queue<Type>::get (Type& result) {
  if (in == out) return FALSE;
  result = this->data[out];		// Get data
  if (++out >= limit) out = 0;		// Increment and wrap
  return TRUE;
}

// Boolean unget (Type&) -- Return TRUE if able to put a Type value on the
//                          front-end of this Queue
// Input:                   Reference to a Type value
// Output:                  TRUE or FALSE

template<class Type> 
Boolean Queue<Type>::unget (const Type& value) {
  long save = out;
  if (--out < 0) out = limit - 1;	// decrement and wrap
  if (in == out) {			// Check for full
    out = save;
    if (!this->grow()) return FALSE;
    if (--out < 0) out = limit - 1;	// decrement and wrap
  }
  data[out] = value;			// Stuff data
  return TRUE;
}

// Boolean put (Type&) -- Put a new last-in item on this Queue; return TRUE
///                       if successful
// Input:                 Reference to a Type value
// Output:                TRUE or FALSE

template<class Type> 
Boolean Queue<Type>::put (const Type& value) {
  long save = in;
  if (++in >= limit) in = 0;		// Increment and Wrap
  if (in == out) {			// Check for full
    in = save;
    if (!this->grow()) return FALSE;
    save = in;
    if (++in >= limit) in = 0;		// Increment and Wrap
  }
  data[save] = value;			// Store
  curpos = in;				// Invalidate curpos
  return TRUE;
}

// Type& unput () -- Remove and return last-in item of this Queue
// Input:            None
// Output:           Reference to the Type value of the last-in item

template<class Type> 
Type& Queue<Type>::unput () {
#if ERROR_CHECKING
  if (in == out)				// If no elements in queue
    RAISE (Error, SYM(Queue), SYM(No_Elements),
	   "Queue<%s>::unput(): No elements in queue", #Type);
#endif
  if (--in < 0) in = limit - 1;			// decrement and wrap
  curpos = in;					// Invalidate curpos
  return data[in];
}

template<class Type>
Boolean Queue<Type>::unput (Type& result) {
  if (in == out) return FALSE;			// If no elements in queue
  if (--in < 0) in = limit - 1;			// decrement and wrap
  curpos = in;					// Invalidate curpos
  result = this->data[in];	        	// Get data
  return TRUE;
}


// Type& look () -- Return first-in item in this Queue
// Input:           None
// Output:          Reference to the first-in item 

template<class Type> 
inline Type& Queue<Type>::look () {
#if ERROR_CHECKING
  if (in == out)				// If there are no elements
    this->look_error (#Type);			// Raise exception
#endif
  return (this->data[out]);
}


// Type& value () -- Return item at current position
// Input:            None
// Output:           Reference to item at current position 

template<class Type> 
inline Type& Queue<Type>::value () {
#if ERROR_CHECKING
  if (this->curpos == in)			// If invalid current position
    this->value_error (#Type);			// Raise exception
#endif
  return (this->data[curpos]);
}


// Boolean operator!= (Queue<Type>&) -- Compare this Queue with another Queue
// Input:  Reference to a Queue
// Output: TRUE or FALSE

template<class Type> 
inline Boolean Queue<Type>::operator!= (const Queue<Type>& q) CONST {
  return (!operator==(q));
}


// void set_growth_ratio(float) -- Set growth percentage of this Queue
// Input:                          Float ratio
// Output:                         None

template<class Type> 
inline void Queue<Type>::set_growth_ratio (float ratio) {
  this->Queue::set_growth_ratio (ratio, #Type);	// Pass size/type to base class
}


// void set_compare(Type##_Queue_Compare) -- Set this Queue's compare function
// Input:  Pointer to a compare function
// Output: None

template<class Type> 
inline void Queue<Type>::set_compare (Type##_Queue_Compare c) {
  if (c == NULL)
    this->compare_s = &Type##_Queue_is_data_equal; // Default equality function
  else
    this->compare_s = c;			// Else set to user function
}


// void set_alloc_size(int) -- Set the default allocation size growth size
// Input:  Integer size
// Output: None

template<class Type> 
inline void Queue<Type>::set_alloc_size (int size) {
  this->Queue::set_alloc_size (size, #Type);	// Pass size/type to base
}


// Queue<Type> () -- Empty constructor for the Queue class
// Input:            None
// Output:           None

template<class Type> 
Queue<Type>::Queue<Type> () {
  this->data = NULL;				// Intialize data
  if (compare_s == NULL)			// If no compare function
    compare_s = &Type##_Queue_is_data_equal;	// Default
}


// Queue<Type> (long) -- Constructor that specifies number of elements
// Input:                Integer number of elements
// Output:               None

template<class Type> 
Queue<Type>::Queue<Type> (unsigned long n)
#ifdef __cplusplus
 : Queue(n)
#else 
 : (n)
#endif
{
  this->data = (Type*) new Type[n];		// Allocate memory
  if (compare_s == NULL)			// If no compare function
    compare_s = &Type##_Queue_is_data_equal;	// Default
}


// Queue<Type> (void*, long) -- Constructor that specifies user-defined storage
//                              and number of elements
// Input:                       Integer number of elements
// Output:                      None

template<class Type> 
Queue<Type>::Queue<Type> (void* s, unsigned long n)
#ifdef __cplusplus
 : Queue(n)
#else
 : (n)
#endif
{
  this->data = (Type*) s;			// Pointer to storage
  this->alloc_size = INVALID;			// Indicate this is static size
  if (compare_s == NULL)			// If no compare function
    compare_s = &Type##_Queue_is_data_equal;	// Default
}


// Queue<Type> (Queue<Type>&) -- Constructor for reference to another Queue
// Input:                        Queue reference
// Output:                       None

template<class Type> 
Queue<Type>::Queue<Type> (const Queue<Type>& s)
#ifdef __cplusplus
 : Queue(s)
#else
 : (s)
#endif
{
  this->data = (Type*) new Type[s.limit];	// New memory allocation
  for (long i = 0; i < s.limit; i++)		// For each element
    this->data[i] = s.data[i];			// Copy data into this
}


// Boolean is_data_equal -- Default data comparison function if user has not
//                          provided another one.
// Input:                   Two Type references
// Output:                  TRUE or FALSE

template<class Type> Queue {
  Boolean Type##_Queue_is_data_equal (const Type& t1, const Type& t2) {
    return (t1 == t2);
  }
}


// ~Queue<Type> -- Destructor for Queue class that frees up storage
// Input:          None
// Output:         None

template<class Type> 
Queue<Type>::~Queue<Type> () {
  if (this->limit != 0 &&
      this->alloc_size != INVALID)		// If not static-size object
    delete [this->limit] this->data;		// Free up the memory
}


// Queue<Type>& operator= (Queue<Type>&) -- Assign this Queue the value
//					    of another Queue
// Input:  Reference to a Queue
// Output: Reference to modified this

template<class Type> 
Queue<Type>& Queue<Type>::operator= (const Queue<Type>& s) {
  long len = s.length();
  long i;
  if (this->limit < len) {			// If not enough memory
#if ERROR_CHECKING
    if (this->alloc_size == INVALID)		// If static size queue
      this->assign_error (#Type);		// Raise exception
#endif
    if (this->limit != 0)
      delete [this->limit] this->data;		// Free it up
    this->limit = s.limit;			// New Queue size
    this->data = (Type*) new Type[s.limit];	// Allocate bigger memory
  }
  out = 0;
  in = len;
  curpos = len;
  register Type* dp = this->data;
  if (s.in >= s.out)
    for (i = s.out; i < s.in; i++)		// copy from s.out to s.in-1
      *dp++ = s.data[i];			// Copy value
  else {
    for (i = s.out; i < s.limit; i++)		// copy from s.out to s.limit-1
      *dp++ = s.data[i];			// Copy value
    for (i = 0; i < s.in; i++)			// copy from first to s.in-1
      *dp++ = s.data[i];			// Copy value
  }
  return *this;					// Return reference
}


// Boolean operator== (Queue<Type>&) -- Compare this Queue with another
//                                      Queue; return TRUE if they are equal
// Input:  Reference to a Queue
// Output: TRUE or FALSE

template<class Type> 
Boolean Queue<Type>::operator== (const Queue<Type>& q) CONST {
  if (this->length() != q.length())		// If not same number
    return FALSE;				// Then not equal
  long tp = this->out;
  long qp = q.out;
  while (tp != this->in) {
    if (!(*this->compare_s)(this->data[tp], q.data[qp]))
      return FALSE;				// Return failure if no match
    if (++tp >= this->limit) tp = 0;		// increment and wrap
    if (++qp >= q.limit) tp = 0;		// increment and wrap
  }
  return TRUE;
}


// Boolean find (Type&) -- Return TRUE if value is found in this Queue
// Input:                  Reference to a Type value
// Output:                 TRUE or FALSE

template<class Type> 
Boolean Queue<Type>::find (const Type& value) {
  long i;
  if (in == out)				// Nothing is in queue
    return FALSE;				// Return failure
  if (in > out) {
    for (i = out; i < in; i++)			// check from out to in-1
      if ((*(this->compare_s))(this->data[i], value)) { // If found
        this->curpos = i;			// Set curpos to index 
        return TRUE;				// Return success
      }
  }
  else {
    for (i = out; i < limit; i++)		// check from out to limit-1
      if ((*(this->compare_s))(this->data[i], value)) { // If found
        this->curpos = i;			// Set curpos to index 
        return TRUE;				// Return success
      }
    for (i = 0; i < in; i++)			// check from first to in-1
      if ((*(this->compare_s))(this->data[i], value)) { // If found
        this->curpos = i;			// Set curpos to index 
        return TRUE;				// Return success
      }
  }
  return FALSE;					// Return failure
}

template<class Type> 
Boolean Queue<Type>::grow () {
  long new_size;
  if (this->alloc_size == INVALID) return FALSE;
  if (growth_ratio_s > 0.0)
     new_size = (long)(limit * (1.0 + growth_ratio_s)); // New size?
  else
    new_size = limit + alloc_size;
  resize(new_size);
  return TRUE;
}
  

// void resize (long)-- Adjust the memory size of a Queue to accomodate some
//                      new size
// Input:               Number of elements to hold
// Output:              None

template<class Type> 
void Queue<Type>::resize (long s) {
#if ERROR_CHECKING
  if (this->alloc_size == INVALID) {		// If not allowed to grow
    this->resize_error (#Type);			// Raise exception
#endif
    return;					// Return
  }
  Type* temp;					// Temporary variable
  Type* tp;
  long len = this->length();
  long i;
  tp = temp = (Type*) new Type[s];		// Allocate storage
  if (in > out) {
    for (i = out; i < in; i++)			// copy from out to in-1
      *tp++ = data[i];				// Copy value
  }
  if (in < out) {
    for (i = out; i < limit; i++)		// copy from out to limit-1
      *tp++ = data[i];				// Copy value
    for (i = 0; i < in; i++)			// copy from first to in-1
      *tp++ = data[i];				// Copy value
  }
  if (this->limit != 0)
    delete [this->limit] this->data;		// Free up old memory
  this->data = temp;				// Assign new memory block
  this->limit = s;				// Save new size value
  curpos = len;
  in = len;
  out = 0;
}


// Boolean remove () -- Destructively remove item at current position; return
//                      TRUE if successful
// Input:               None
// Output:              TRUE or FALSE
template<class Type> 
Boolean Queue<Type>::remove () {
  long i;
  if (in == out) return FALSE;			// Fail if nothing in queue
  if (in > out) {				// Data is between out and in-1
    if (curpos < out || curpos >= in)		// Fail if invalid curpos
      return FALSE;
    in--;
    for (i = curpos; i < in; i++)
      data[i] = data[i+1];
  }					       
  else {
    if (curpos >= out) {		       // Data is between out and limit
      if (curpos >= limit)		       // fail if invalid curpos
	return FALSE;
      out--;
      for (i = curpos; i >= out; i--)
	data[i] = data[i - 1];
    }
    else { 				       // data is between 0 and in-1
      if (curpos >= in)			       // fail if invalid curpos
	return FALSE;
      in--;
      for (i = curpos; i < in; i++)
	data[i] = data[i+1];
    }
  }
  return TRUE;					// Report success
}


// Boolean remove (Type&) -- Destructively remove the first occurence of an 
//                           element, starting from front of this Queue; return
//                           TRUE if element is found and removed
// Input:                    Reference to Type value
// Output:                   TRUE or FALSE

template<class Type> 
Boolean Queue<Type>::remove (const Type& value) {
 return find(value) && remove();	// find it, Remove it & return status
}

// operator<< -- Overload the output operator for Queue
// Input:        ostream reference, queue pointer
// Output:       Queue data is output to ostreamn

template<class Type> Queue {
inline ostream& operator<< (ostream& os, const Queue<Type>* q) {
  return q->qprint(os);
}
}


// operator<< -- Overload the output operator for Queue
// Input:        ostream reference, queue reference
// Output:       Queue data is output to ostream

template<class Type> Queue {
ostream& operator<< (ostream& os, const Queue<Type>& q) {
  return q.qprint(os);
}
}


// This is a method because Glockenspiel's Cfront 1.2 doesn't let 
// friend functions access the protected data members of our base class
template<class Type>
ostream& Queue<Type>::qprint(ostream& os) CONST {
  if (in == out)				// If no elements
    os << " Empty ";				// Report empty status
  else {
    long i;
    os << "[ ";
    if (in >= out)
      for (i = out; i < in; i++)		// copy from out to in-1
	os << data[i] << " ";
    else {
      for (i = out; i < limit; i++)		// copy from out to limit-1
	os << data[i] << " ";
      for (i = 0; i < in; i++)			// copy from first to in-1
	os << data[i] << " ";
    }
    os << "]";
  }
  return os;					// Return stream reference
}

#endif				// End #ifdef of QUEUEH

