PriorityQueue.hpp

Go to the documentation of this file.

/*****************************************************************************
 * Copyright (C) 2011 by Benjamin Hadorn (b_hadorn@bluewin.ch)
 *****************************************************************************
 * Project    : Zeus Base Library
 * Module     : PriorityQueue
 * Package    : Zeus.ZeusBase.System
 * Author     : Benjamin Hadorn
 * Date       : 27.12.2011
 * System     : Zeus-Framework
 *****************************************************************************
 * Licence:                                                                  *
 *   This library is free software; you can redistribute it and/or modify    *
 *   it under the terms of the GNU Lesser General Public License as          *
 *   published by the Free Software Foundation; either version               *
 *   2.1 of the License, or (at your option) any later version.              *
 *                                                                           *
 *   This library is distributed in the hope that it will be useful,         *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of          *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the            *
 *   GNU Lesser General Public License for more details.                     *
 *                                                                           *
 *   You should have received a copy of the GNU Lesser General Public        *
 *   License along with this library; if not, write to the Free Software     *
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110, USA    *
 *****************************************************************************/

/*****************************************************************************
 * Changes:
 *  27.12.2011 bha: created zeus 2.0
 *****************************************************************************/

#ifndef PriorityQueueHPP
#define PriorityQueueHPP

#include <string.h>
#include <zeusbase/System/ZObject.h>
#include <zeusbase/System/Queue.hpp>
#include <zeusbase/System/SingleLinkedList.hpp>
#include <zeusbase/System/Interfaces/IPriorityQueue.hpp>

#ifdef _MSC_VER
  #pragma warning(push, 1) // Avoid Visual Studio 6.0 level 4 and 3 compiler warnings.
#endif

#include <stddef.h>
#include <map>

#ifdef _MSC_VER
  #pragma warning(pop)
#endif


BEGIN_NAMESPACE_Zeus

using namespace std;

/******************************************************************************/
/******************************************************************************/
template <class TKeyType, class TValueType> class TPriorityQueue
 : public TZObject,
   public IPriorityQueue<TKeyType, TValueType>
{
  public:
    typedef std::map<TKeyType, TQueue<TValueType> > TPriorityMap;

    /************************************************************************/
    /************************************************************************/
    inline TPriorityQueue(bool bReplaceExisting = false)
     : m_EmptyObject(TValueType()),
       m_EmptyPriority(TKeyType())
    {
      m_iCount = 0;
      m_bReplaceExisting = bReplaceExisting;
    }

    /************************************************************************/
    /************************************************************************/
    inline TPriorityQueue(const TValueType& rEmptyObject, bool bReplaceExisting = false)
     : m_EmptyObject(rEmptyObject),
       m_EmptyPriority(TKeyType())
    {
      m_iCount = 0;
      m_bReplaceExisting = bReplaceExisting;
    }

    /************************************************************************/
    /************************************************************************/
    inline virtual ~TPriorityQueue()
    {
      flush();
    }

    /************************************************************************/
    /************************************************************************/
    virtual void MQUALIFIER appendPriorityItem(const TKeyType& rKey, const TValueType& tData)
    {
      TQueue<TValueType>& rQueue = m_Map[rKey];

      if (m_bReplaceExisting)
      {
        m_iCount -= rQueue.getCount();
        rQueue.flush();
      }

      rQueue.appendItem(tData);
      ++m_iCount;
    }

    /************************************************************************/
    /************************************************************************/
    virtual void MQUALIFIER copyToPriorityQueue(IPriorityQueue<TKeyType, TValueType>& rQueue) const
    {
      for (typename TPriorityMap::const_iterator Iterator = m_Map.begin();
           Iterator != m_Map.end();
           Iterator++)
      {
        TSingleLinkedList<TValueType> lstItems;
        (*Iterator).second.copyToList(lstItems);

        IListIterator<TValueType>* pIt = lstItems.getIterator();
        while(pIt->hasNextItem())
        {
          rQueue.appendPriorityItem((*Iterator).first, pIt->getNextItem());
        }
        lstItems.releaseIterator(pIt);
      }
    }

    /************************************************************************/
    /************************************************************************/
    inline virtual const TKeyType& MQUALIFIER peekPriority() const
    {
      typename TPriorityMap::const_iterator Iterator = m_Map.begin();

      if (Iterator != m_Map.end())
      {
        return (*Iterator).first;
      }
      else
      {
        return m_EmptyPriority;
      }
    }

    /************************************************************************/
    /************************************************************************/
    inline virtual void MQUALIFIER appendItem(const TValueType& tData)
    {
      this->appendPriorityItem(m_EmptyPriority, tData);
    }

    /************************************************************************/
    /************************************************************************/
    inline virtual void MQUALIFIER copyToQueue(IQueue<TValueType>& rQueue) const
    {
      for (typename TPriorityMap::const_iterator Iterator = m_Map.begin();
           Iterator != m_Map.end();
           Iterator++)
      {
        (*Iterator).second.copyToQueue(rQueue);
      }
    }

    /************************************************************************/
    /************************************************************************/
    inline virtual void MQUALIFIER copyToList(IList<TValueType>& rList) const
    {
      for (typename TPriorityMap::const_iterator Iterator = m_Map.begin();
           Iterator != m_Map.end();
           Iterator++)
      {
       (*Iterator).second.copyToList(rList);
      }
    }

    /************************************************************************/
    /************************************************************************/
    virtual TValueType MQUALIFIER removeItem()
    {
      TValueType tRetval(m_EmptyObject);
      typename TPriorityMap::iterator it = m_Map.begin();
      if (it != m_Map.end())
      {
        tRetval = (*it).second.removeItem();

        //If there are no items any more ->remove from map
        if ((*it).second.isEmpty())
        {
          m_Map.erase((*it).first);
        }
        --m_iCount;
      }
      return tRetval;
    }

    /************************************************************************/
    /************************************************************************/
    inline virtual Int MQUALIFIER getCount() const
    {
      return m_iCount;
    }

    /************************************************************************/
    /************************************************************************/
    inline virtual void MQUALIFIER flush()
    {
      m_Map.clear();
      m_iCount = 0;
    }

    /************************************************************************/
    /************************************************************************/
    inline virtual bool MQUALIFIER isEmpty() const
    {
      return m_Map.empty();
    }

    /************************************************************************/
    /************************************************************************/
    inline virtual TValueType& MQUALIFIER peekItem()
    {
      typename TPriorityMap::iterator it = m_Map.begin();
      if (it != m_Map.end())
      {
        return (*it).second.peekItem();
      }
      else
      {
        return m_EmptyObject;
      }
    }

    /************************************************************************/
    /************************************************************************/
    inline virtual const TValueType& MQUALIFIER peekItemConst() const
    {
      typename TPriorityMap::const_iterator it = m_Map.begin();
      if (it != m_Map.end())
      {
        return (*it).second.peekItemConst();
      }
      else
      {
        return m_EmptyObject;
      }
    }

  protected:
    //Interface IZUnknown
    MEMORY_MANAGER_INLINEIMPL()
    MEMORY_MANAGER_IMPL_END;

  private:
    TValueType m_EmptyObject;
    TKeyType m_EmptyPriority;
    TPriorityMap m_Map;
    Int m_iCount;
    bool m_bReplaceExisting;

};

END_NAMESPACE_Zeus

#endif