123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137 |
- //
- //=======================================================================
- // 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
|