Saf/Collection/PriorityQueue.h

Go to the documentation of this file.

/*
    This file is part of Simple Application Framework (Saf) library.
    Copyright (C) 2010 - 2012 Ondrej Danek <ondrej.danek@gmail.com>

    This library is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published 
    by the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Saf 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 General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Simple Application Framework library. If not, 
    see <http://www.gnu.org/licenses/>.
*/

#ifndef SAF_COLLECTION_PRIORITYQUEUE_H
#define SAF_COLLECTION_PRIORITYQUEUE_H

#include "../Type.h"
#include "../Algo/Swap.h"
#include "../Algo/Predicate.h"
#include "../Algo/Struct/Heap.h"
#include "DynArray.h"

namespace Saf
{
    namespace Collection
    {
        template <class ValType, class CompType = Algo::Predicate::Less<ValType>,
            class ContainerType = DynArray<ValType> > 
        class PriorityQueue
        {
        protected:
            typedef PriorityQueue<ValType,CompType,ContainerType> MyType;

        private:
            ContainerType m_storage;
            CompType m_pred;

        public:
            PriorityQueue()
            {}

            PriorityQueue(const MyType& queue)
                : m_storage(queue.m_storage), m_pred(queue.m_pred)
            {}

            explicit PriorityQueue(const ContainerType& cont)
                : m_storage(cont)
            {
                Algo::Struct::Heap::MakeHeap(m_storage.Begin(), m_storage.End(), m_pred);
            }

            MyType& operator=(MyType& queue)
            {
                m_storage = queue.m_storage;
                m_pred = queue.m_pred;
                return *this;
            }

            MyType& Swap(MyType& queue)
            {
                Algo::Swap(m_storage, queue.m_storage);
                Algo::Swap(m_pred, queue.m_pred);
                return *this;
            }

            bool IsEmpty() const
            {
                return m_storage.IsEmpty();
            }

            Size Elements() const
            {
                return m_storage.Elements();
            }

            ValType& Top()
            {
                return *m_storage.Front();
            }

            const ValType& Top() const
            {
                return *m_storage.Front();
            }

            MyType& Push(const ValType& val)
            {
                m_storage.PushBack(val);
                Algo::Struct::Heap::PushHeap(m_storage.Begin(), m_storage.End(), m_pred);
                return *this;
            }

            MyType& Pop()
            {
                Algo::Struct::Heap::PopHeap(m_storage.Begin(), m_storage.End(), m_pred);
                m_storage.PopBack();
                return *this;
            }

            const ContainerType& Storage()
            {
                return m_storage;
            }
        };
    }

    namespace Algo
    {
        // Swap specialization for a priority queue container.
        template <class ValType, class CompType, class ContainerType>
        struct SwapFunc< Collection::PriorityQueue<ValType,CompType,ContainerType> >
        {
            void operator()(Collection::PriorityQueue<ValType,CompType,ContainerType>& x, 
                Collection::PriorityQueue<ValType,CompType,ContainerType>& y)
            {
                x.Swap(y);
            }
        };
    }
}

#endif