1 /*************************************************************************** 2 * include/stxxl/bits/containers/pq_helpers.h 3 * 4 * Part of the STXXL. See http://stxxl.sourceforge.net 5 * 6 * Copyright (C) 1999 Peter Sanders <sanders@mpi-sb.mpg.de> 7 * Copyright (C) 2003, 2004, 2007 Roman Dementiev <dementiev@mpi-sb.mpg.de> 8 * Copyright (C) 2007, 2009 Johannes Singler <singler@ira.uka.de> 9 * Copyright (C) 2007, 2008 Andreas Beckmann <beckmann@cs.uni-frankfurt.de> 10 * 11 * Distributed under the Boost Software License, Version 1.0. 12 * (See accompanying file LICENSE_1_0.txt or copy at 13 * http://www.boost.org/LICENSE_1_0.txt) 14 **************************************************************************/ 15 16 #ifndef STXXL_CONTAINERS_PQ_HELPERS_HEADER 17 #define STXXL_CONTAINERS_PQ_HELPERS_HEADER 18 19 #include <vector> 20 #include <algorithm> 21 22 #include <stxxl/bits/deprecated.h> 23 #include <stxxl/bits/mng/block_manager.h> 24 #include <stxxl/bits/mng/typed_block.h> 25 #include <stxxl/bits/mng/block_alloc.h> 26 #include <stxxl/bits/mng/read_write_pool.h> 27 #include <stxxl/bits/mng/prefetch_pool.h> 28 #include <stxxl/bits/mng/write_pool.h> 29 #include <stxxl/bits/common/tmeta.h> 30 #include <stxxl/bits/algo/sort_base.h> 31 #include <stxxl/bits/parallel.h> 32 #include <stxxl/bits/common/is_sorted.h> 33 #include <stxxl/bits/common/error_handling.h> 34 35 #if STXXL_PARALLEL 36 37 #if defined(STXXL_PARALLEL_MODE) && ((__GNUC__ * 10000 + __GNUC_MINOR__ * 100) < 40400) 38 #undef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL 39 #undef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL 40 #undef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER 41 #define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL 0 42 #define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL 0 43 #define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER 0 44 #endif 45 46 // enable/disable parallel merging for certain cases, for performance tuning 47 #ifndef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL 48 #define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL 1 49 #endif 50 #ifndef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL 51 #define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL 1 52 #endif 53 #ifndef STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER 54 #define STXXL_PARALLEL_PQ_MULTIWAY_MERGE_DELETE_BUFFER 1 55 #endif 56 57 #endif //STXXL_PARALLEL 58 59 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_EXTERNAL 60 #define STXXL_PQ_EXTERNAL_LOSER_TREE 0 // no loser tree for the external sequences 61 #else 62 #define STXXL_PQ_EXTERNAL_LOSER_TREE 1 63 #endif 64 65 #if STXXL_PARALLEL && STXXL_PARALLEL_PQ_MULTIWAY_MERGE_INTERNAL 66 #define STXXL_PQ_INTERNAL_LOSER_TREE 0 // no loser tree for the internal sequences 67 #else 68 #define STXXL_PQ_INTERNAL_LOSER_TREE 1 69 #endif 70 71 #define STXXL_VERBOSE_PQ(msg) STXXL_VERBOSE2_THIS("priority_queue::" << msg) 72 73 STXXL_BEGIN_NAMESPACE 74 75 //! \defgroup stlcontinternals internals 76 //! \ingroup stlcont 77 //! Supporting internal classes 78 //! \{ 79 80 /*! \internal 81 */ 82 namespace priority_queue_local { 83 84 /*! 85 * Similar to std::priority_queue, with the following differences: 86 * - Maximum size is fixed at construction time, so an array can be used. 87 * - Provides access to underlying heap, so (parallel) sorting in place is possible. 88 * - Can be cleared "at once", without reallocation. 89 */ 90 template <typename ValueType, typename ContainerType = std::vector<ValueType>, 91 typename CompareType = std::less<ValueType> > 92 class internal_priority_queue 93 { 94 public: 95 typedef ValueType value_type; 96 typedef ContainerType container_type; 97 typedef CompareType compare_type; 98 typedef typename container_type::reference reference; 99 typedef typename container_type::const_reference const_reference; 100 typedef typename container_type::size_type size_type; 101 102 protected: 103 // See queue::heap for notes on these names. 104 container_type heap; 105 CompareType comp; 106 size_type current_size; 107 108 public: 109 //! Default constructor creates no elements. 110 explicit internal_priority_queue(size_type capacity)111 internal_priority_queue(size_type capacity) 112 : heap(capacity), current_size(0) 113 { } 114 115 //! Returns true if the %queue is empty. 116 bool empty()117 empty() const 118 { return current_size == 0; } 119 120 //! Returns the number of elements in the %queue. 121 size_type size()122 size() const 123 { return current_size; } 124 125 /*! 126 * Returns a read-only (constant) reference to the data at the first 127 * element of the %queue. 128 */ 129 const_reference top()130 top() const 131 { 132 return heap.front(); 133 } 134 135 /*! 136 * Add data to the %queue. 137 * @param x Data to be added. 138 * 139 * This is a typical %queue operation. 140 * The time complexity of the operation depends on the underlying 141 * container. 142 */ 143 void push(const value_type & x)144 push(const value_type& x) 145 { 146 heap[current_size] = x; 147 ++current_size; 148 std::push_heap(heap.begin(), heap.begin() + current_size, comp); 149 } 150 151 /*! 152 * Removes first element. 153 * 154 * This is a typical %queue operation. It shrinks the %queue 155 * by one. The time complexity of the operation depends on the 156 * underlying container. 157 * 158 * Note that no data is returned, and if the first element's 159 * data is needed, it should be retrieved before pop() is 160 * called. 161 */ 162 void pop()163 pop() 164 { 165 std::pop_heap(heap.begin(), heap.begin() + current_size, comp); 166 --current_size; 167 } 168 169 //! Sort all contained elements, write result to @c target. sort_to(value_type * target)170 void sort_to(value_type* target) 171 { 172 check_sort_settings(); 173 potentially_parallel:: 174 sort(heap.begin(), heap.begin() + current_size, comp); 175 std::reverse_copy(heap.begin(), heap.begin() + current_size, target); 176 } 177 178 //! Remove all contained elements. clear()179 void clear() 180 { 181 current_size = 0; 182 } 183 }; 184 185 //! Inverts the order of a comparison functor by swapping its arguments. 186 template <class Predicate, typename FirstType, typename SecondType> 187 class invert_order 188 { 189 protected: 190 Predicate pred; 191 192 public: 193 explicit invert_order(const Predicate & _pred)194 invert_order(const Predicate& _pred) : pred(_pred) { } 195 operator()196 bool operator () (const FirstType& x, const SecondType& y) const 197 { 198 return pred(y, x); 199 } 200 }; 201 202 /*! 203 * Similar to std::stack, with the following differences: 204 * - Maximum size is fixed at compilation time, so an array can be used. 205 * - Can be cleared "at once", without reallocation. 206 */ 207 template <typename ValueType, unsigned_type MaxSize> 208 class internal_bounded_stack 209 { 210 typedef ValueType value_type; 211 typedef unsigned_type size_type; 212 enum { max_size = MaxSize }; 213 214 size_type m_size; 215 value_type m_array[max_size]; 216 217 public: internal_bounded_stack()218 internal_bounded_stack() : m_size(0) { } 219 push(const value_type & x)220 void push(const value_type& x) 221 { 222 assert(m_size < max_size); 223 m_array[m_size++] = x; 224 } 225 top()226 const value_type & top() const 227 { 228 assert(m_size > 0); 229 return m_array[m_size - 1]; 230 } 231 pop()232 void pop() 233 { 234 assert(m_size > 0); 235 --m_size; 236 } 237 clear()238 void clear() 239 { 240 m_size = 0; 241 } 242 size()243 size_type size() const 244 { 245 return m_size; 246 } 247 empty()248 bool empty() const 249 { 250 return m_size == 0; 251 } 252 }; 253 254 } // namespace priority_queue_local 255 256 //! \} 257 258 STXXL_END_NAMESPACE 259 260 #endif // !STXXL_CONTAINERS_PQ_HELPERS_HEADER 261 // vim: et:ts=4:sw=4 262