Stxxl
1.3.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/containers/pq_helpers.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 1999 Peter Sanders <sanders@mpi-sb.mpg.de> 00007 * Copyright (C) 2003, 2004, 2007 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00008 * Copyright (C) 2007, 2009 Johannes Singler <singler@ira.uka.de> 00009 * Copyright (C) 2007, 2008 Andreas Beckmann <beckmann@cs.uni-frankfurt.de> 00010 * 00011 * Distributed under the Boost Software License, Version 1.0. 00012 * (See accompanying file LICENSE_1_0.txt or copy at 00013 * http://www.boost.org/LICENSE_1_0.txt) 00014 **************************************************************************/ 00015 00016 #ifndef STXXL_PQ_HELPERS_HEADER 00017 #define STXXL_PQ_HELPERS_HEADER 00018 00019 #include <queue> 00020 00021 __STXXL_BEGIN_NAMESPACE 00022 00026 00029 namespace priority_queue_local 00030 { 00037 template <typename _Tp, typename _Sequence = std::vector<_Tp>, 00038 typename _Compare = std::less<typename _Sequence::value_type> > 00039 class internal_priority_queue 00040 { 00041 // concept requirements 00042 typedef typename _Sequence::value_type _Sequence_value_type; 00043 00044 public: 00045 typedef typename _Sequence::value_type value_type; 00046 typedef typename _Sequence::reference reference; 00047 typedef typename _Sequence::const_reference const_reference; 00048 typedef typename _Sequence::size_type size_type; 00049 typedef _Sequence container_type; 00050 00051 protected: 00052 // See queue::heap for notes on these names. 00053 _Sequence heap; 00054 _Compare comp; 00055 size_type current_size; 00056 00057 public: 00061 explicit 00062 internal_priority_queue(size_type capacity) 00063 : heap(capacity), current_size(0) 00064 { } 00065 00069 bool 00070 empty() const 00071 { return current_size == 0; } 00072 00074 size_type 00075 size() const 00076 { return current_size; } 00077 00082 const_reference 00083 top() const 00084 { 00085 return heap.front(); 00086 } 00087 00096 void 00097 push(const value_type & __x) 00098 { 00099 heap[current_size] = __x; 00100 ++current_size; 00101 std::push_heap(heap.begin(), heap.begin() + current_size, comp); 00102 } 00103 00115 void 00116 pop() 00117 { 00118 std::pop_heap(heap.begin(), heap.begin() + current_size, comp); 00119 --current_size; 00120 } 00121 00125 void sort_to(value_type * target) 00126 { 00127 potentially_parallel:: 00128 sort(heap.begin(), heap.begin() + current_size, comp); 00129 std::reverse_copy(heap.begin(), heap.begin() + current_size, target); 00130 } 00131 00135 void clear() 00136 { 00137 current_size = 0; 00138 } 00139 }; 00140 00144 template <class Predicate, typename first_argument_type, typename second_argument_type> 00145 class invert_order 00146 { 00147 protected: 00148 Predicate pred; 00149 00150 public: 00151 explicit 00152 invert_order(const Predicate & _pred) : pred(_pred) { } 00153 00154 bool operator () (const first_argument_type & x, const second_argument_type & y) const 00155 { 00156 return pred(y, x); 00157 } 00158 }; 00159 00160 00166 template <typename Tp_, unsigned_type max_size_> 00167 class internal_bounded_stack 00168 { 00169 typedef Tp_ value_type; 00170 typedef unsigned_type size_type; 00171 enum { max_size = max_size_ }; 00172 00173 size_type size_; 00174 value_type array[max_size]; 00175 00176 public: 00177 internal_bounded_stack() : size_(0) { } 00178 00179 void push(const value_type & x) 00180 { 00181 assert(size_ < max_size); 00182 array[size_++] = x; 00183 } 00184 00185 const value_type & top() const 00186 { 00187 assert(size_ > 0); 00188 return array[size_ - 1]; 00189 } 00190 00191 void pop() 00192 { 00193 assert(size_ > 0); 00194 --size_; 00195 } 00196 00197 void clear() 00198 { 00199 size_ = 0; 00200 } 00201 00202 size_type size() const 00203 { 00204 return size_; 00205 } 00206 00207 bool empty() const 00208 { 00209 return size_ == 0; 00210 } 00211 }; 00212 } //priority_queue_local 00213 00215 00216 __STXXL_END_NAMESPACE 00217 00218 #endif // !STXXL_PQ_HELPERS_HEADER 00219 // vim: et:ts=4:sw=4