diff options
Diffstat (limited to 'boost/pending/bucket_sorter.hpp')
-rw-r--r-- | boost/pending/bucket_sorter.hpp | 37 |
1 files changed, 20 insertions, 17 deletions
diff --git a/boost/pending/bucket_sorter.hpp b/boost/pending/bucket_sorter.hpp index 8b7926d2df..97c26b2626 100644 --- a/boost/pending/bucket_sorter.hpp +++ b/boost/pending/bucket_sorter.hpp @@ -19,34 +19,37 @@ #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, + 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()) + + 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()), + 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 + + //check if i is the end of the bucket list if ( next_node != invalid_value() ) - prev[next_node] = prev_node; + 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; @@ -58,21 +61,21 @@ namespace boost { 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: + // 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; @@ -86,7 +89,7 @@ namespace boost { // 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]; @@ -114,7 +117,7 @@ namespace boost { IndexValueMap value; ValueIndexMap id; }; - + stack operator[](const bucket_type& i) { assert(i < head.size()); return stack(i, head.begin(), next.begin(), prev.begin(), @@ -128,7 +131,7 @@ namespace boost { Bucket bucket; ValueIndexMap id; }; - + } #endif |