//
|
//=======================================================================
|
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
|
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
|
//
|
// 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)
|
//=======================================================================
|
//
|
//
|
// Revision History:
|
// 13 June 2001: Changed some names for clarity. (Jeremy Siek)
|
// 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
|
//
|
#ifndef BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP
|
#define BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP
|
|
#include <vector>
|
#include <cassert>
|
#include <boost/limits.hpp>
|
#include <boost/concept/assert.hpp>
|
#include <boost/property_map/property_map.hpp>
|
|
namespace boost
|
{
|
|
template < class BucketType, class ValueType, class Bucket,
|
class ValueIndexMap >
|
class bucket_sorter
|
{
|
BOOST_CONCEPT_ASSERT(
|
(ReadablePropertyMapConcept< ValueIndexMap, ValueType >));
|
|
public:
|
typedef BucketType bucket_type;
|
typedef ValueType value_type;
|
typedef typename std::vector< value_type >::size_type size_type;
|
|
bucket_sorter(size_type _length, bucket_type _max_bucket,
|
const Bucket& _bucket = Bucket(),
|
const ValueIndexMap& _id = ValueIndexMap())
|
: head(_max_bucket, invalid_value())
|
, next(_length, invalid_value())
|
, prev(_length, invalid_value())
|
, id_to_value(_length)
|
, bucket(_bucket)
|
, id(_id)
|
{
|
}
|
|
void remove(const value_type& x)
|
{
|
const size_type i = get(id, x);
|
const size_type& next_node = next[i];
|
const size_type& prev_node = prev[i];
|
|
// check if i is the end of the bucket list
|
if (next_node != invalid_value())
|
prev[next_node] = prev_node;
|
// check if i is the begin of the bucket list
|
if (prev_node != invalid_value())
|
next[prev_node] = next_node;
|
else // need update head of current bucket list
|
head[bucket[x]] = next_node;
|
}
|
|
void push(const value_type& x)
|
{
|
id_to_value[get(id, x)] = x;
|
(*this)[bucket[x]].push(x);
|
}
|
|
void update(const value_type& x)
|
{
|
remove(x);
|
(*this)[bucket[x]].push(x);
|
}
|
// private:
|
// with KCC, the nested stack class is having access problems
|
// despite the friend decl.
|
static size_type invalid_value()
|
{
|
return (std::numeric_limits< size_type >::max)();
|
}
|
|
typedef typename std::vector< size_type >::iterator Iter;
|
typedef typename std::vector< value_type >::iterator IndexValueMap;
|
|
public:
|
friend class stack;
|
|
class stack
|
{
|
public:
|
stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v,
|
const ValueIndexMap& _id)
|
: bucket_id(_bucket_id), head(h), next(n), prev(p), value(v), id(_id)
|
{
|
}
|
|
// Avoid using default arg for ValueIndexMap so that the default
|
// constructor of the ValueIndexMap is not required if not used.
|
stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v)
|
: bucket_id(_bucket_id), head(h), next(n), prev(p), value(v)
|
{
|
}
|
|
void push(const value_type& x)
|
{
|
const size_type new_head = get(id, x);
|
const size_type current = head[bucket_id];
|
if (current != invalid_value())
|
prev[current] = new_head;
|
prev[new_head] = invalid_value();
|
next[new_head] = current;
|
head[bucket_id] = new_head;
|
}
|
void pop()
|
{
|
size_type current = head[bucket_id];
|
size_type next_node = next[current];
|
head[bucket_id] = next_node;
|
if (next_node != invalid_value())
|
prev[next_node] = invalid_value();
|
}
|
value_type& top() { return value[head[bucket_id]]; }
|
const value_type& top() const { return value[head[bucket_id]]; }
|
bool empty() const { return head[bucket_id] == invalid_value(); }
|
|
private:
|
bucket_type bucket_id;
|
Iter head;
|
Iter next;
|
Iter prev;
|
IndexValueMap value;
|
ValueIndexMap id;
|
};
|
|
stack operator[](const bucket_type& i)
|
{
|
assert(i < head.size());
|
return stack(i, head.begin(), next.begin(), prev.begin(),
|
id_to_value.begin(), id);
|
}
|
|
protected:
|
std::vector< size_type > head;
|
std::vector< size_type > next;
|
std::vector< size_type > prev;
|
std::vector< value_type > id_to_value;
|
Bucket bucket;
|
ValueIndexMap id;
|
};
|
|
}
|
|
#endif
|
