QueueArray.h

/*  _________________________________________________________________________
 *
 *  UTILIB: A utility library for developing portable C++ codes.
 *  Copyright (c) 2001, Sandia National Laboratories.
 *  This software is distributed under the GNU Lesser General Public License.
 *  For more information, see the README file in the top UTILIB directory.
 *  _________________________________________________________________________
 */

//
// QueueArray.h
//
#ifndef __QueueArray_h
#define __QueueArray_h

#ifdef __GNUC__
#pragma interface
#endif

#ifdef NON_ANSI
#include <iostream.h>
#else
#include <iostream>
using namespace std;
#endif

#ifndef ANSI_HDRS
#include <stddef.h>
#include <stdlib.h>
#else
#include <cstddef>
#include <cstdlib>
#endif

#include "_math.h"
#include "BasicArray.h"
#include "PackBuf.h"



template <class T>
class UTILIB_API QueueArray
{
public:

  QueueArray();
  virtual ~QueueArray() {}

  virtual T& top()
                {
                if (Len>0)
                   return Data[First];
                ErrAbort("QueueArray::top -- Empty stack.");
                return Data[0];
                }
  virtual void add( const T& );
  virtual void remove( T& val );

  int empty() const
                {return (Len == 0);}
  operator int() const
                {return (Len > 0);}
  size_type len() const
                {return Len;}

  void clear();

  void write(ostream& os) const;
  void read(istream& is);
  void write(PackBuffer& os) const;
  void read(UnPackBuffer& is);

protected:

  size_type Len;
  size_type First;
  size_type Last;
  BasicArray<T> Data;
  BasicArray<size_t> next;

};

template <class T>
inline UTILIB_API QueueArray<T>& operator>>(QueueArray<T>& list, T& val)
{list.remove(val); return list;}

template <class T>
inline UTILIB_API QueueArray<T>& operator<<(QueueArray<T>& list, const T& val)
{list.add(val); return list;}

template <class T>
inline UTILIB_API ostream& operator<<(ostream& output, const QueueArray<T>& set)
{ set.write(output); return(output); }

template <class T>
inline UTILIB_API istream& operator>>(istream& input, QueueArray<T>& set)
{ set.read(input); return(input); }

template <class T>
inline UTILIB_API PackBuffer& operator<<(PackBuffer& output, const QueueArray<T>& set)
{ set.write(output); return(output); }

template <class T>
inline UTILIB_API UnPackBuffer& operator>>(UnPackBuffer& input, QueueArray<T>& set){ set.read(input); return(input); }



//
// Note, we are using internal indeces that are 1-based, indexing into
// zero based arrays.  This is because the smallest value that the 'next'
// array can represent is zero.
//
template <class T>
QueueArray<T>::QueueArray()
 : Len(0), First(1), Last(1)
{ Data.resize(10); next.resize(10); next[0] = 0;}


template <class T>
void QueueArray<T>::clear()
{
Len=0;
First = 1;
Last = 1;
next[0] = 0;
}


template <class T>
void QueueArray<T>::remove( T& Value )
{
if (Len == 0)
   ErrAbort("QueueArray<T>::remove -- empty list!");

size_type curr = First;
Value = Data[curr];

//
// Move the First pointer down the list
//
if (next[curr] == 0) {
   //
   // The 'next' value is empty, so return to initial conditions for
   // code.
   //
   Len=0;
   First = 1;
   Last = 1;
   }
else {
   Len--;
   First = next[curr];
   }

//
// Setup the 'free list'
//
size_type tmp = next[0];
next[0] = curr;
next[curr] = tmp;
}


template <class T>
void QueueArray<T>::add( const T& val )
{
Len++;
size_type curr;
if (next[0] == 0)
   curr = Len;
else {
   //
   // Remove an element from the free list
   //
   curr = next[0];
   next[0] = next[curr];
   }
if (Data.size() == curr) {
   Data.resize(curr + max((Data.size() / 10),(size_type)10));
   next.resize(curr + max((next.size() / 10),(size_type)10));
   }

if (Len == 1)
   First = curr;
next[curr] = 0;
if (Len > 1)
   next[Last] = curr;
Data[curr] = val;
Last = curr;
}


template <class T>
void QueueArray<T>::write(ostream& os) const
{
os << Len << " [ ";
if (Len > 0) {
   size_type curr = First;
   os << Data[curr];
   for (size_type i=1; i<Len; i++) {
     curr = next[curr] ;
     os << ", " << Data[curr];
     }
   os << " ";
   }
os << "]";
}


template <class T>
void QueueArray<T>::read(istream& /*is*/)
{
}

template <class T>
void QueueArray<T>::write(PackBuffer& os) const
{
os << Len;
size_type curr = First;
for (size_type i=0; i<Len; i++) {
  os << Data[curr];
  curr = next[curr];
  }
}


template <class T>
void QueueArray<T>::read(UnPackBuffer& is)
{
is >> Len;
if (Data.len() <= (Len+1))
   Data.resize(max(1,(Len+1)));
Len=0;
First = 1;
Last = 1;
for (size_type i=0; i<Len; i++) {
  is >> Data[Len];
  add(Data[Len]);
  }
}

#endif