ext/OGDF/ogdf/basic/BoundedQueue.h

   1 /*
   2  * $Revision: 2615 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-16 14:23:36 +0200 (Mo, 16. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration and implementation of bounded queue class.
  11  *
  12  * \author Carsten Gutwenger
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43 #ifdef _MSC_VER
  44 #pragma once
  45 #endif
  46
  47 #ifndef OGDF_B_QUEUE_H
  48 #define OGDF_B_QUEUE_H
  49
  50
  51 #include <ogdf/basic/basic.h>
  52
  53
  54 namespace ogdf {
  55
  56 template<class E, class INDEX> class BoundedQueue;
  57
  58 // output
  59 template<class E, class INDEX>
  60 void print(ostream &os, const BoundedQueue<E,INDEX> &S, char delim = ' ');
  61
  62
  63 //! The parameterized class \a BoundedQueue<E,INDEX> implements queues with bounded size.
  64 /**
  65  * @tparam E     is the element type.
  66  * @tparam INDEX is the index type. The default index type is \c int, other possible types
  67  *               are \c short and <code>long long</code> (on 64-bit systems).
  68  */
  69 template<class E, class INDEX = int> class BoundedQueue {
  70
  71         E *m_pStart; //! Pointer to first element of current sequence.
  72         E *m_pEnd;   //! Pointer to one past last element of current sequence.
  73         E *m_pStop;  //! Pointer to one past last element of total array.
  74         E *m_pFirst; //! Pointer to  first element of total array.
  75
  76 public:
  77         //! Constructs an empty bounded queue for at most \a n elements.
  78         explicit BoundedQueue(INDEX n) {
  79                 OGDF_ASSERT(n >= 1)
  80                 m_pStart = m_pEnd = m_pFirst = new E[n+1];
  81                 if (m_pFirst == 0) OGDF_THROW(InsufficientMemoryException);
  82
  83                 m_pStop = m_pFirst+n+1;
  84         }
  85
  86         //! Constructs a bounded queue that is a copy of \a Q.
  87         BoundedQueue(const BoundedQueue<E> &Q) {
  88                 copy(Q);
  89         }
  90
  91         // destruction
  92         ~BoundedQueue() { delete [] m_pFirst; }
  93
  94         //! Returns front element.
  95         const E &top() const {
  96                 OGDF_ASSERT(m_pStart != m_pEnd)
  97                 return *m_pStart;
  98         }
  99
 100         //! Returns front element.
 101         E &top() {
 102                 OGDF_ASSERT(m_pStart != m_pEnd)
 103                 return *m_pStart;
 104         }
 105
 106         //! Returns back element.
 107         const E &bottom() const {
 108                 OGDF_ASSERT(m_pStart != m_pEnd)
 109                 if (m_pEnd == m_pFirst) return *(m_pStop-1);
 110                 else return *(m_pEnd-1);
 111         }
 112
 113         //! Returns back element.
 114         E &bottom() {
 115                 OGDF_ASSERT(m_pStart != m_pEnd)
 116                 if (m_pEnd == m_pFirst) return *(m_pStop-1);
 117                 else return *(m_pEnd-1);
 118         }
 119
 120         //! Returns current size of the queue.
 121         INDEX size() const {
 122                 return (m_pEnd >= m_pStart) ?
 123                         (m_pEnd - m_pStart) :
 124                         (m_pEnd-m_pFirst)+(m_pStop-m_pStart);
 125         }
 126
 127         //! Returns the capacity of the bounded queue.
 128         INDEX capacity() const { return (m_pStop - m_pFirst)-1; }
 129
 130         //! Returns true iff the queue is empty.
 131         bool empty() { return m_pStart == m_pEnd; }
 132
 133         //! Returns true iff the queue is full.
 134         bool full() {
 135                 INDEX h = m_pEnd-m_pStart
 136                 return ( h>=0 ) ?
 137                         (h == m_pStop-m_pFirst-1) :
 138                         (h == -1);
 139         }
 140
 141         //! Assignment operator.
 142         BoundedQueue<E> &operator=(const BoundedQueue<E> &Q) {
 143                 delete [] m_pFirst;
 144                 copy(Q);
 145                 return *this;
 146         }
 147
 148         //! Adds \a x at the end of queue.
 149         void append(const E &x) {
 150                 *m_pEnd++ = x;
 151                 if (m_pEnd == m_pStop) m_pEnd = m_pFirst;
 152                 OGDF_ASSERT(m_pStart != m_pEnd)
 153         }
 154
 155         //! Removes front element and returns it.
 156         E pop() {
 157                 OGDF_ASSERT(m_pStart != m_pEnd)
 158                 E x = *m_pStart++;
 159                 if (m_pStart == m_pStop) m_pStart = m_pFirst;
 160                 return x;
 161         }
 162
 163         //! Makes the queue empty.
 164         void clear() { m_pStart = m_pEnd = m_pFirst; }
 165
 166         //! Prints the queue to output stream \a os.
 167         void print(ostream &os, char delim = ' ') const
 168         {
 169                 for (const E *pX = m_pStart; pX != m_pEnd; ) {
 170                         if (pX != m_pStart) os << delim;
 171                         os << *pX;
 172                         if (++pX == m_pStop) pX = m_pFirst;
 173                 }
 174         }
 175
 176 private:
 177         void copy(const BoundedQueue<E> &Q) {
 178                 int n = Q.size()+1;
 179                 m_pEnd = m_pStart = m_pFirst = new E[n];
 180                 if (m_pFirst == 0) OGDF_THROW(InsufficientMemoryException);
 181
 182                 m_pStop = m_pStart + n;
 183                 for (E *pX = Q.m_pStart; pX != Q.m_pEnd; ) {
 184                         *m_pEnd++ = *pX++;
 185                         if (pX == Q.m_pStop) pX = Q.m_pFirst;
 186                 }
 187         }
 188 }; // class BoundedQueue
 189
 190
 191
 192 // output operator
 193 template<class E, class INDEX>
 194 ostream &operator<<(ostream &os, const BoundedQueue<E,INDEX> &Q)
 195 {
 196         Q.print(os);
 197         return os;
 198 }
 199
 200 } // end namespace ogdf
 201
 202
 203 #endif