addressable_queues.h

/***************************************************************************
 *  include/stxxl/bits/common/addressable_queues.h
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright (C) 2010-2011 Raoul Steffen <R-Steffen@gmx.de>
 *
 *  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_ADDRESSABLE_QUEUES_HEADER
#define STXXL_ADDRESSABLE_QUEUES_HEADER

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

#include <stxxl/bits/namespace.h>

__STXXL_BEGIN_NAMESPACE

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:
    typedef meta_iter_t handle;

    addressable_fifo_queue() {}
    ~addressable_fifo_queue() {}

    bool empty() const
    { return vals.empty(); }

    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;
    }

    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;
    }

    void erase(handle i)
    {
        vals.erase(i->second);
        meta.erase(i);
    }

    const KeyType & top() const
    { return vals.front(); }

    KeyType pop()
    {
        assert(! empty());
        const KeyType e = top();
        meta.erase(e);
        vals.pop_front();
        return e;
    }
};

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:
    typedef meta_iter_t handle;

    addressable_priority_queue() {}
    ~addressable_priority_queue() {}

    bool empty() const
    { return vals.empty(); }

    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;
    }

    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;
    }

    void erase(handle i)
    {
        vals.erase(i->second);
        meta.erase(i);
    }

    const KeyType & top() const
    { return vals.begin()->second; }

    KeyType pop()
    {
        assert(! empty());
        const KeyType e = top();
        meta.erase(e);
        vals.erase(vals.begin());
        return e;
    }
};

__STXXL_END_NAMESPACE

#endif /* STXXL_ADDRESSABLE_QUEUES_HEADER */