addressable_queues.h

Go to the documentation of this file.

/***************************************************************************
 *  include/stxxl/bits/common/addressable_queues.h
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright (C) 2010-2011 Raoul Steffen <[email protected]>
 *
 *  Distributed under the Boost Software License, Version 1.0.
 *  (See accompanying file LICENSE_1_0.txt or copy at
 *  http://www.boost.org/LICENSE_1_0.txt)
 **************************************************************************/

#ifndef STXXL_COMMON_ADDRESSABLE_QUEUES_HEADER
#define STXXL_COMMON_ADDRESSABLE_QUEUES_HEADER

#include <set>
#include <list>
#include <map>

#include <stxxl/bits/namespace.h>

STXXL_BEGIN_NAMESPACE

//! An internal fifo queue that allows removing elements addressed with (a copy of) themselves.
//! \tparam KeyType Type of contained elements.
template <typename KeyType>
class addressable_fifo_queue
{
    typedef std::list<KeyType> container_t;
    typedef typename container_t::iterator container_iter_t;
    typedef std::map<KeyType, container_iter_t> meta_t;
    typedef typename meta_t::iterator meta_iter_t;

    container_t vals;
    meta_t meta;

public:
    //! Type of handle to an entry. For use with insert and remove.
    typedef meta_iter_t handle;

    //! Create an empty queue.
    addressable_fifo_queue() { }
    ~addressable_fifo_queue() { }

    //! Check if queue is empty.
    //! \return If queue is empty.
    bool empty() const
    { return vals.empty(); }

    //! Insert new element. If the element is already in, it is moved to the back.
    //! \param e Element to insert.
    //! \return pair<handle, bool> Iterator to element; if element was newly inserted.
    std::pair<handle, bool> insert(const KeyType& e)
    {
        container_iter_t ei = vals.insert(vals.end(), e);
        std::pair<handle, bool> r = meta.insert(std::make_pair(e, ei));
        if (! r.second)
        {
            // element was already in
            vals.erase(r.first->second);
            r.first->second = ei;
        }
        return r;
    }

    //! Erase element from the queue.
    //! \param e Element to remove.
    //! \return If element was in.
    bool erase(const KeyType& e)
    {
        handle mi = meta.find(e);
        if (mi == meta.end())
            return false;
        vals.erase(mi->second);
        meta.erase(mi);
        return true;
    }

    //! Erase element from the queue.
    //! \param i Iterator to element to remove.
    void erase(handle i)
    {
        vals.erase(i->second);
        meta.erase(i);
    }

    //! Access top element in the queue.
    //! \return Const reference to top element.
    const KeyType & top() const
    { return vals.front(); }

    //! Remove top element from the queue.
    //! \return Top element.
    KeyType pop()
    {
        assert(! empty());
        const KeyType e = top();
        meta.erase(e);
        vals.pop_front();
        return e;
    }
};

//! An internal priority queue that allows removing elements addressed with (a copy of) themselves.
//! \tparam KeyType Type of contained elements.
//! \tparam PriorityType Type of Priority.
template <typename KeyType, typename PriorityType, class Cmp = std::less<PriorityType> >
class addressable_priority_queue
{
    struct cmp // like < for pair, but uses Cmp for < on first
    {
        bool operator () (const std::pair<PriorityType, KeyType>& left,
                          const std::pair<PriorityType, KeyType>& right) const
        {
            Cmp c;
            return c(left.first, right.first) ||
                   ((! c(right.first, left.first)) && left.second < right.second);
        }
    };

    typedef std::set<std::pair<PriorityType, KeyType>, cmp> container_t;
    typedef typename container_t::iterator container_iter_t;
    typedef std::map<KeyType, container_iter_t> meta_t;
    typedef typename meta_t::iterator meta_iter_t;

    container_t vals;
    meta_t meta;

public:
    //! Type of handle to an entry. For use with insert and remove.
    typedef meta_iter_t handle;

    //! Create an empty queue.
    addressable_priority_queue() { }
    ~addressable_priority_queue() { }

    //! Check if queue is empty.
    //! \return If queue is empty.
    bool empty() const
    { return vals.empty(); }

    //! Insert new element. If the element is already in, it's priority is updated.
    //! \param e Element to insert.
    //! \param o Priority of element.
    //! \return pair<handle, bool> Iterator to element; if element was newly inserted.
    std::pair<handle, bool> insert(const KeyType& e, const PriorityType o)
    {
        std::pair<container_iter_t, bool> s = vals.insert(std::make_pair(o, e));
        std::pair<handle, bool> r = meta.insert(std::make_pair(e, s.first));
        if (! r.second && s.second)
        {
            // was already in with different priority
            vals.erase(r.first->second);
            r.first->second = s.first;
        }
        return r;
    }

    //! Erase element from the queue.
    //! \param e Element to remove.
    //! \return If element was in.
    bool erase(const KeyType& e)
    {
        handle mi = meta.find(e);
        if (mi == meta.end())
            return false;
        vals.erase(mi->second);
        meta.erase(mi);
        return true;
    }

    //! Erase element from the queue.
    //! \param i Iterator to element to remove.
    void erase(handle i)
    {
        vals.erase(i->second);
        meta.erase(i);
    }

    //! Access top (= min) element in the queue.
    //! \return Const reference to top element.
    const KeyType & top() const
    { return vals.begin()->second; }

    //! Remove top (= min) element from the queue.
    //! \return Top element.
    KeyType pop()
    {
        assert(! empty());
        const KeyType e = top();
        meta.erase(e);
        vals.erase(vals.begin());
        return e;
    }
};

STXXL_END_NAMESPACE

#endif // !STXXL_COMMON_ADDRESSABLE_QUEUES_HEADER