1 // 2 //======================================================================= 3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. 4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek 5 // 6 // Distributed under the Boost Software License, Version 1.0. (See 7 // accompanying file LICENSE_1_0.txt or copy at 8 // http://www.boost.org/LICENSE_1_0.txt) 9 //======================================================================= 10 // 11 // 12 // Revision History: 13 // 13 June 2001: Changed some names for clarity. (Jeremy Siek) 14 // 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock) 15 // 16 #ifndef BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP 17 #define BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP 18 19 #include <vector> 20 #include <cassert> 21 #include <boost/limits.hpp> 22 #include <boost/concept/assert.hpp> 23 #include <boost/property_map/property_map.hpp> 24 25 namespace boost 26 { 27 28 template < class BucketType, class ValueType, class Bucket, 29 class ValueIndexMap > 30 class bucket_sorter 31 { 32 BOOST_CONCEPT_ASSERT( 33 (ReadablePropertyMapConcept< ValueIndexMap, ValueType >)); 34 35 public: 36 typedef BucketType bucket_type; 37 typedef ValueType value_type; 38 typedef typename std::vector< value_type >::size_type size_type; 39 bucket_sorter(size_type _length,bucket_type _max_bucket,const Bucket & _bucket=Bucket (),const ValueIndexMap & _id=ValueIndexMap ())40 bucket_sorter(size_type _length, bucket_type _max_bucket, 41 const Bucket& _bucket = Bucket(), 42 const ValueIndexMap& _id = ValueIndexMap()) 43 : head(_max_bucket, invalid_value()) 44 , next(_length, invalid_value()) 45 , prev(_length, invalid_value()) 46 , id_to_value(_length) 47 , bucket(_bucket) 48 , id(_id) 49 { 50 } 51 remove(const value_type & x)52 void remove(const value_type& x) 53 { 54 const size_type i = get(id, x); 55 const size_type& next_node = next[i]; 56 const size_type& prev_node = prev[i]; 57 58 // check if i is the end of the bucket list 59 if (next_node != invalid_value()) 60 prev[next_node] = prev_node; 61 // check if i is the begin of the bucket list 62 if (prev_node != invalid_value()) 63 next[prev_node] = next_node; 64 else // need update head of current bucket list 65 head[bucket[x]] = next_node; 66 } 67 push(const value_type & x)68 void push(const value_type& x) 69 { 70 id_to_value[get(id, x)] = x; 71 (*this)[bucket[x]].push(x); 72 } 73 update(const value_type & x)74 void update(const value_type& x) 75 { 76 remove(x); 77 (*this)[bucket[x]].push(x); 78 } 79 // private: 80 // with KCC, the nested stack class is having access problems 81 // despite the friend decl. invalid_value()82 static size_type invalid_value() 83 { 84 return (std::numeric_limits< size_type >::max)(); 85 } 86 87 typedef typename std::vector< size_type >::iterator Iter; 88 typedef typename std::vector< value_type >::iterator IndexValueMap; 89 90 public: 91 friend class stack; 92 93 class stack 94 { 95 public: stack(bucket_type _bucket_id,Iter h,Iter n,Iter p,IndexValueMap v,const ValueIndexMap & _id)96 stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v, 97 const ValueIndexMap& _id) 98 : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v), id(_id) 99 { 100 } 101 102 // Avoid using default arg for ValueIndexMap so that the default 103 // constructor of the ValueIndexMap is not required if not used. stack(bucket_type _bucket_id,Iter h,Iter n,Iter p,IndexValueMap v)104 stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v) 105 : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v) 106 { 107 } 108 push(const value_type & x)109 void push(const value_type& x) 110 { 111 const size_type new_head = get(id, x); 112 const size_type current = head[bucket_id]; 113 if (current != invalid_value()) 114 prev[current] = new_head; 115 prev[new_head] = invalid_value(); 116 next[new_head] = current; 117 head[bucket_id] = new_head; 118 } pop()119 void pop() 120 { 121 size_type current = head[bucket_id]; 122 size_type next_node = next[current]; 123 head[bucket_id] = next_node; 124 if (next_node != invalid_value()) 125 prev[next_node] = invalid_value(); 126 } top()127 value_type& top() { return value[head[bucket_id]]; } top() const128 const value_type& top() const { return value[head[bucket_id]]; } empty() const129 bool empty() const { return head[bucket_id] == invalid_value(); } 130 131 private: 132 bucket_type bucket_id; 133 Iter head; 134 Iter next; 135 Iter prev; 136 IndexValueMap value; 137 ValueIndexMap id; 138 }; 139 operator [](const bucket_type & i)140 stack operator[](const bucket_type& i) 141 { 142 assert(i < head.size()); 143 return stack(i, head.begin(), next.begin(), prev.begin(), 144 id_to_value.begin(), id); 145 } 146 147 protected: 148 std::vector< size_type > head; 149 std::vector< size_type > next; 150 std::vector< size_type > prev; 151 std::vector< value_type > id_to_value; 152 Bucket bucket; 153 ValueIndexMap id; 154 }; 155 156 } 157 158 #endif 159