ZeusBase-Library: Queue.hpp Source File

Go to the documentation of this file.
00001 /*****************************************************************************
00002  * Copyright (C) 2011 by Benjamin Hadorn (b_hadorn@bluewin.ch)
00003  *****************************************************************************
00004  * Project    : Zeus Base Library
00005  * Module     : Queue
00006  * Package    : Zeus.ZeusBase.System
00007  * Author     : Benjamin Hadorn
00008  * Date       : 27.12.2011
00009  * System     : Zeus-Framework
00010  *****************************************************************************
00011  * Licence:                                                                  *
00012  *   This library is free software; you can redistribute it and/or modify    *
00013  *   it under the terms of the GNU Lesser General Public License as          *
00014  *   published by the Free Software Foundation; either version               *
00015  *   2.1 of the License, or (at your option) any later version.              *
00016  *                                                                           *
00017  *   This library is distributed in the hope that it will be useful,         *
00018  *   but WITHOUT ANY WARRANTY; without even the implied warranty of          *
00019  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the            *
00020  *   GNU Lesser General Public License for more details.                     *
00021  *                                                                           *
00022  *   You should have received a copy of the GNU Lesser General Public        *
00023  *   License along with this library; if not, write to the Free Software     *
00024  *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110, USA    *
00025  *****************************************************************************/
00026 
00027 /*****************************************************************************
00028  * Changes:
00029  *  27.12.2011 bha: created zeus 2.0
00030  *****************************************************************************/
00031 
00032 #ifndef QueueHPP
00033 #define QueueHPP
00034 
00035 #ifdef _MSC_VER
00036   #pragma warning(push, 1)
00037 #endif
00038 
00039 #include <stddef.h>
00040 
00041 #ifdef _MSC_VER
00042   #pragma warning(pop)
00043 #endif
00044 
00045 #include <string.h>
00046 #include <zeusbase/System/ZObject.h>
00047 #include <zeusbase/System/Interfaces/IQueue.hpp>
00048 
00049 BEGIN_NAMESPACE_Zeus
00050 
00051 /******************************************************************************/
00054 /******************************************************************************/
00055 template <class T> class TQueue : public IQueue<T>
00056 {
00057   public:
00058     TQueue();
00059     TQueue(IQueue<T>& rQueue);
00060     TQueue(const T& rEmptyObject);
00061     virtual ~TQueue();
00062 
00063     //Methods of IQueue
00064     virtual void MQUALIFIER appendItem(const T& tData);
00065     virtual void MQUALIFIER copyToQueue(IQueue<T>& rQueue) const;
00066     virtual void MQUALIFIER copyToList(IList<T>& rList) const;
00067     virtual T MQUALIFIER removeItem();
00068     virtual Int MQUALIFIER getCount() const;
00069     virtual void MQUALIFIER flush();
00070     virtual bool MQUALIFIER isEmpty() const;
00071     virtual T& MQUALIFIER peekItem() ;
00072     virtual const T& MQUALIFIER peekItemConst() const;
00073 
00074     //operators
00075     TQueue<T>& operator=(const TQueue<T>& rQueue);
00076     TQueue<T>& operator=(const IQueue<T>& rQueue);
00077 
00078     
00079   protected:
00080     T getItem(Int iIndex) const;
00081 
00082   private:
00083     /***************************************************************/
00086     /***************************************************************/
00087     struct TBaseElement
00088     {
00089       /*************************************************************/
00092       /*************************************************************/
00093       inline TBaseElement(T tData1, TBaseElement* pNext1)
00094       {
00095         tData = tData1;
00096         pNext = pNext1;
00097       }
00098 
00100       T tData;
00102       TBaseElement* pNext;
00103     };
00104 
00105     /*********************************************************************/
00106     /* COMPILER PROBLEM:
00107        Change this if a compiler fails with : m_tEmpty(T()) (see constructors)
00108 
00109     #ifdef A_COMPILER_TYPE
00110     static const T& getDefaultEmpty()
00111     {
00112         static const T Empty; // is initialized by compiler
00113         return Empty;
00114     }
00115     #endif
00116 
00117     */
00118 
00120     TBaseElement* m_pElHead;
00122     TBaseElement* m_pElTail;
00124     Int m_iCount;
00126     T m_EmptyObject;
00127 
00128 };
00129 
00130 
00131 /******************************************************************************/
00134 /******************************************************************************/
00135 template <class T> inline TQueue<T>::TQueue()
00136  /* COMPILER PROBLEM*/
00137  /*#ifdef A_COMPILER_TYPE
00138     : m_EmptyObject(getDefaultEmpty())
00139    #else
00140     : m_EmptyObject(T())
00141    #endif
00142 */
00143   : m_EmptyObject(T())
00144 {
00145   m_pElHead = NULL;
00146   m_pElTail = NULL;
00147   m_iCount = 0;
00148 
00149   // DO NOT USE MEMSET. This causes memory leaks on complex objects
00150   //memset(&m_EmptyObject,0, sizeof(T));
00151 }
00152 
00153 /******************************************************************************/
00156 /******************************************************************************/
00157 template <class T> inline TQueue<T>::TQueue(IQueue<T>& rQueue)
00158  : m_EmptyObject(rQueue.m_EmptyObject)
00159 {
00160   m_pElHead = NULL;
00161   m_pElTail = NULL;
00162   m_iCount = 0;
00163   rQueue.copyToQueue(*this);
00164 }
00165 
00166 /******************************************************************************/
00169 /******************************************************************************/
00170 template <class T> inline TQueue<T>::TQueue(const T& rEmptyObject)
00171  : m_EmptyObject(rEmptyObject)
00172 {
00173   m_pElHead = NULL;
00174   m_pElTail = NULL;
00175   m_iCount = 0;
00176 }
00177 
00178 
00179 /******************************************************************************/
00182 /******************************************************************************/
00183 template <class T> inline TQueue<T>::~TQueue()
00184 {
00185   flush();
00186   m_pElHead = NULL;
00187   m_pElTail = NULL;
00188 }
00189 
00190 /******************************************************************************/
00195 /******************************************************************************/
00196 template <class T> T TQueue<T>::getItem(Int iIndex) const
00197 {
00198   T Retval = m_EmptyObject;
00199   if (m_pElHead != NULL && iIndex >= 0 && iIndex < m_iCount)
00200   {
00201     TBaseElement* pActElement = m_pElHead;
00202     while(iIndex > 0 && pActElement != NULL)
00203     {
00204       pActElement = pActElement->pNext;
00205       iIndex--;
00206     }
00207     
00208     if (pActElement != NULL)
00209     {
00210       Retval = pActElement->tData;
00211     }
00212   }
00213   return Retval;
00214 }
00215 
00216 /******************************************************************************/
00219 /******************************************************************************/
00220 template <class T> void MQUALIFIER TQueue<T>::appendItem(const T& tData)
00221 {
00222   if (m_pElTail == NULL)
00223   {
00224     m_pElTail = new TBaseElement(tData, NULL);
00225     m_pElHead = m_pElTail;
00226   }
00227   else
00228   {
00229     m_pElTail->pNext = new TBaseElement(tData, NULL);
00230     m_pElTail = m_pElTail->pNext;
00231   }
00232   m_iCount++;
00233 }
00234 
00235 /******************************************************************************/
00238 /******************************************************************************/
00239 template <class T> void MQUALIFIER TQueue<T>::copyToQueue(IQueue<T>& rQueue) const
00240 {
00241   TBaseElement* pActElement = m_pElHead;
00242   while(pActElement != NULL)
00243   {
00244     rQueue.appendItem(pActElement->tData);
00245     pActElement = pActElement->pNext;
00246   }
00247 
00248   /* NOT SO EFFICIENT O(n^2)
00249   for(int i = 0; i < m_iCount; i++)
00250   {
00251     rQueue.appendItem(this->getItem(i));
00252   }*/
00253 }
00254 
00255 /******************************************************************************/
00258 /******************************************************************************/
00259 template <class T> void MQUALIFIER TQueue<T>::copyToList(IList<T>& rList) const
00260 {
00261   TBaseElement* pActElement = m_pElHead;
00262   while(pActElement != NULL)
00263   {
00264     rList.add(pActElement->tData);
00265     pActElement = pActElement->pNext;
00266   }
00267 
00268   /* NOT SO EFFICIENT O(n^2)
00269   for(int i = 0; i < m_iCount; i++)
00270   {
00271     rList.add(this->getItem(i));
00272   }*/
00273 }
00274 
00275 /******************************************************************************/
00278 /******************************************************************************/
00279 template <class T> T MQUALIFIER TQueue<T>::removeItem()
00280 {
00281   if (m_pElHead != NULL)
00282   {
00283     T tRetval = m_pElHead->tData;
00284     TBaseElement* pDel = m_pElHead;
00285     m_pElHead = m_pElHead->pNext;
00286     delete pDel;
00287     m_iCount--;
00288     
00289     if (m_pElHead == NULL)
00290     {
00291       m_pElTail = NULL;
00292     }
00293     return tRetval;
00294   }
00295   else
00296   {
00297     return m_EmptyObject;
00298   }
00299 }
00300 
00301 /******************************************************************************/
00304 /******************************************************************************/
00305 template <class T> inline Int MQUALIFIER TQueue<T>::getCount() const
00306 {
00307   return m_iCount;
00308 }
00309 
00310 
00311 /******************************************************************************/
00314 /******************************************************************************/
00315 template <class T> void MQUALIFIER TQueue<T>::flush()
00316 {
00317   while(m_pElHead != NULL)
00318   {
00319     TBaseElement* pNext = m_pElHead->pNext;
00320     delete m_pElHead;
00321     m_pElHead = pNext;
00322   }
00323   m_iCount = 0;
00324   m_pElTail = NULL;
00325 }
00326 
00327 /******************************************************************************/
00330 /******************************************************************************/
00331 template <class T> inline bool MQUALIFIER TQueue<T>::isEmpty() const
00332 {
00333   return (m_iCount == 0);
00334 }
00335 
00336 /******************************************************************************/
00339 /******************************************************************************/
00340 template <class T> inline T& MQUALIFIER TQueue<T>::peekItem()
00341 {
00342   if (m_pElHead != NULL)
00343   {
00344     return m_pElHead->tData;
00345   }
00346   else
00347   {
00348     return m_EmptyObject;
00349   }
00350 }
00351 
00352 /******************************************************************************/
00355 /******************************************************************************/
00356 template <class T> inline const T& MQUALIFIER TQueue<T>::peekItemConst() const
00357 {
00358   if (m_pElHead != NULL)
00359   {
00360     return m_pElHead->tData;
00361   }
00362   else
00363   {
00364     return m_EmptyObject;
00365   }
00366 }
00367 
00368 
00369 
00370 /******************************************************************************/
00374 /******************************************************************************/
00375 template <class T> inline TQueue<T>& TQueue<T>::operator=(const TQueue<T>& rQueue)
00376 {
00377   rQueue.copyToQueue(*this);
00378   return *this;
00379 }
00380 
00381 /******************************************************************************/
00385 /******************************************************************************/
00386 template <class T> inline TQueue<T>& TQueue<T>::operator=(const IQueue<T>& rQueue)
00387 {
00388   rQueue.copyToQueue(*this);
00389   return *this;
00390 }
00391 
00392 END_NAMESPACE_Zeus
00393 
00394 
00395 #endif