// | |
//======================================================================= | |
// 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> | |
namespace boost { | |
template <class BucketType, class ValueType, class Bucket, | |
class ValueIndexMap> | |
class bucket_sorter { | |
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 |