boost/pending/bucket_sorter.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 //
0012 // Revision History:
0013 //   13 June 2001: Changed some names for clarity. (Jeremy Siek)
0014 //   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
0015 //
0016 #ifndef BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP
0017 #define BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP
0018
0019 #include <vector>
0020 #include <cassert>
0021 #include <boost/limits.hpp>
0022 #include <boost/concept/assert.hpp>
0023 #include <boost/property_map/property_map.hpp>
0024
0025 namespace boost
0026 {
0027
0028 template < class BucketType, class ValueType, class Bucket,
0029     class ValueIndexMap >
0030 class bucket_sorter
0031 {
0032     BOOST_CONCEPT_ASSERT(
0033         (ReadablePropertyMapConcept< ValueIndexMap, ValueType >));
0034
0035 public:
0036     typedef BucketType bucket_type;
0037     typedef ValueType value_type;
0038     typedef typename std::vector< value_type >::size_type size_type;
0039
0040     bucket_sorter(size_type _length, bucket_type _max_bucket,
0041         const Bucket& _bucket = Bucket(),
0042         const ValueIndexMap& _id = ValueIndexMap())
0043     : head(_max_bucket, invalid_value())
0044     , next(_length, invalid_value())
0045     , prev(_length, invalid_value())
0046     , id_to_value(_length)
0047     , bucket(_bucket)
0048     , id(_id)
0049     {
0050     }
0051
0052     void remove(const value_type& x)
0053     {
0054         const size_type i = get(id, x);
0055         const size_type& next_node = next[i];
0056         const size_type& prev_node = prev[i];
0057
0058         // check if i is the end of the bucket list
0059         if (next_node != invalid_value())
0060             prev[next_node] = prev_node;
0061         // check if i is the begin of the bucket list
0062         if (prev_node != invalid_value())
0063             next[prev_node] = next_node;
0064         else // need update head of current bucket list
0065             head[bucket[x]] = next_node;
0066     }
0067
0068     void push(const value_type& x)
0069     {
0070         id_to_value[get(id, x)] = x;
0071         (*this)[bucket[x]].push(x);
0072     }
0073
0074     void update(const value_type& x)
0075     {
0076         remove(x);
0077         (*this)[bucket[x]].push(x);
0078     }
0079     //  private:
0080     //    with KCC, the nested stack class is having access problems
0081     //    despite the friend decl.
0082     static size_type invalid_value()
0083     {
0084         return (std::numeric_limits< size_type >::max)();
0085     }
0086
0087     typedef typename std::vector< size_type >::iterator Iter;
0088     typedef typename std::vector< value_type >::iterator IndexValueMap;
0089
0090 public:
0091     friend class stack;
0092
0093     class stack
0094     {
0095     public:
0096         stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v,
0097             const ValueIndexMap& _id)
0098         : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v), id(_id)
0099         {
0100         }
0101
0102         // Avoid using default arg for ValueIndexMap so that the default
0103         // constructor of the ValueIndexMap is not required if not used.
0104         stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v)
0105         : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v)
0106         {
0107         }
0108
0109         void push(const value_type& x)
0110         {
0111             const size_type new_head = get(id, x);
0112             const size_type current = head[bucket_id];
0113             if (current != invalid_value())
0114                 prev[current] = new_head;
0115             prev[new_head] = invalid_value();
0116             next[new_head] = current;
0117             head[bucket_id] = new_head;
0118         }
0119         void pop()
0120         {
0121             size_type current = head[bucket_id];
0122             size_type next_node = next[current];
0123             head[bucket_id] = next_node;
0124             if (next_node != invalid_value())
0125                 prev[next_node] = invalid_value();
0126         }
0127         value_type& top() { return value[head[bucket_id]]; }
0128         const value_type& top() const { return value[head[bucket_id]]; }
0129         bool empty() const { return head[bucket_id] == invalid_value(); }
0130
0131     private:
0132         bucket_type bucket_id;
0133         Iter head;
0134         Iter next;
0135         Iter prev;
0136         IndexValueMap value;
0137         ValueIndexMap id;
0138     };
0139
0140     stack operator[](const bucket_type& i)
0141     {
0142         assert(i < head.size());
0143         return stack(i, head.begin(), next.begin(), prev.begin(),
0144             id_to_value.begin(), id);
0145     }
0146
0147 protected:
0148     std::vector< size_type > head;
0149     std::vector< size_type > next;
0150     std::vector< size_type > prev;
0151     std::vector< value_type > id_to_value;
0152     Bucket bucket;
0153     ValueIndexMap id;
0154 };
0155
0156 }
0157
0158 #endif