//========================================================== // General Purpose Library //========================================================== // deque.h // // Template for a fast, array-based deque // // Copyright 1995-96 Scott Robert Ladd. All rights reserved //========================================================== #ifndef COYOTE_DEQUE_H #define COYOTE_DEQUE_H #include "limits.h" #include "contx.h" using namespace Coyote; namespace Coyote { //--------------------------- // Deque (Double-ended queue) //--------------------------- template < class T, size_t Limit > class Deque { public: // construct empty deque Deque(); // copy constructor Deque ( const Deque & deq ); // assignment operator void operator = ( const Deque & deq ); // push item at head of deque void PushTop ( const T & item ); // push item at end of deque void PushBtm ( const T & item ); // pop head item T PopTop(); // pop tail item T PopBtm(); // remove all items void Erase(); // interrogators size_t GetCount(); size_t GetLimit(); protected: // data items T Data[Limit]; // indexes to head and tail size_t Head; size_t Tail; // number of items in deque size_t Count; // utility functions void DeepCopy ( const Deque & deq ); }; template < class T, size_t Limit > void Deque::DeepCopy ( const Deque & deq ) { Count = deq.Count; Head = deq.Head; Tail = deq.Tail; for (size_t n = 0; n < Limit; ++n) Data[n] = deq.Data[n]; } template < class T, size_t Limit > inline Deque::Deque() { Count = 0; Head = 0; Tail = 0; } template < class T, size_t Limit > inline Deque::Deque ( const Deque & deq ) { Count = 0; DeepCopy(deq); } template < class T, size_t Limit > inline Deque::~Deque() { Erase(); } template < class T, size_t Limit > void Deque::operator = ( const Deque & deq ) { Erase(); DeepCopy(deq); } template < class T, size_t Limit > void Deque::PushTop(const T & item) { if (Count == Limit) throw ContainerEx(CX_OVERFLOW); if (Count == 0) { Tail = 0; Head = 0; Data[0] = item; } else { if (Head == 0) Head = Limit - 1; else --Head; Data[Head] = item; } ++Count; } template < class T, size_t Limit > void Deque::PushBtm(const T & item) { if (Count == Limit) throw ContainerEx(CX_OVERFLOW); if (Count == 0) { Tail = 0; Head = 0; Data[0] = item; } else { ++Tail; if (Tail == Limit) Tail = 0; Data[Tail] = item; } ++Count; } template < class T, size_t Limit > T Deque::PopTop() { if (Count == 0) throw ContainerEx(CX_NULL); T result = Data[Head]; --Count; if (Count != 0) { ++Head; if (Head == Limit) Head = 0; } return result; } template < class T, size_t Limit > T Deque::PopBtm() { if (Count == 0) throw ContainerEx(CX_NULL); T result = Data[Tail]; --Count; if (Count != 0) { if (Tail == 0) Tail = Limit - 1; else --Tail; } return result; } template < class T, size_t Limit > inline void Deque::Erase() { Count = 0; } template < class T, size_t Limit > inline size_t Deque::GetCount() { return Count; } template < class T, size_t Limit > inline size_t Deque::GetLimit() { return Limit; } } // end namespace Coyote #endif