http://stxxl.sourceforge.net
<R-Steffen@gmx.de>
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)
{
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
{
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)
{
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