Wiselib
|
00001 /*************************************************************************** 00002 ** This file is part of the generic algorithm library Wiselib. ** 00003 ** Copyright (C) 2008,2009 by the Wisebed (www.wisebed.eu) project. ** 00004 ** ** 00005 ** The Wiselib is free software: you can redistribute it and/or modify ** 00006 ** it under the terms of the GNU Lesser General Public License as ** 00007 ** published by the Free Software Foundation, either version 3 of the ** 00008 ** License, or (at your option) any later version. ** 00009 ** ** 00010 ** The Wiselib is distributed in the hope that it will be useful, ** 00011 ** but WITHOUT ANY WARRANTY; without even the implied warranty of ** 00012 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ** 00013 ** GNU Lesser General Public License for more details. ** 00014 ** ** 00015 ** You should have received a copy of the GNU Lesser General Public ** 00016 ** License along with the Wiselib. ** 00017 ** If not, see <http://www.gnu.org/licenses/>. ** 00018 ***************************************************************************/ 00019 #ifndef __WISELIB_INTERNAL_INTERFACE_STL_PRIORITY_QUEUE_H 00020 #define __WISELIB_INTERNAL_INTERFACE_STL_PRIORITY_QUEUE_H 00021 00022 #include "util/pstl/iterator.h" 00023 00024 namespace wiselib 00025 { 00026 00027 template<typename OsModel_P, 00028 typename Value_P, 00029 int QUEUE_SIZE> 00030 class priority_queue 00031 { 00032 public: 00033 typedef Value_P value_type; 00034 typedef value_type* pointer; 00035 00036 typedef typename OsModel_P::size_t size_type; 00037 // -------------------------------------------------------------------- 00038 priority_queue() 00039 { 00040 start_ = &vec_[0]; 00041 finish_ = start_; 00042 end_of_storage_ = start_ + QUEUE_SIZE; 00043 } 00044 // -------------------------------------------------------------------- 00045 priority_queue( const priority_queue& pq ) 00046 { *this = pq; } 00047 // -------------------------------------------------------------------- 00048 ~priority_queue() {} 00049 // -------------------------------------------------------------------- 00050 priority_queue& operator=( const priority_queue& pq ) 00051 { 00052 memcpy( vec_, pq.vec_, sizeof(vec_) ); 00053 start_ = &vec_[0]; 00054 finish_ = start_ + (pq.finish_ - pq.start_); 00055 end_of_storage_ = start_ + QUEUE_SIZE; 00056 return *this; 00057 } 00058 // -------------------------------------------------------------------- 00061 size_type size() 00062 { return size_type(finish_ - start_); } 00063 // -------------------------------------------------------------------- 00064 size_type max_size() 00065 { return QUEUE_SIZE; } 00066 // -------------------------------------------------------------------- 00067 size_type capacity() 00068 { return QUEUE_SIZE; } 00069 // -------------------------------------------------------------------- 00070 bool empty() 00071 { return size() == 0; } 00072 // -------------------------------------------------------------------- 00073 pointer data() 00074 { return pointer(this->start_); } 00076 // -------------------------------------------------------------------- 00079 value_type top() 00080 { 00081 return vec_[0]; 00082 } 00084 // -------------------------------------------------------------------- 00087 void clear() 00088 { 00089 finish_ = start_; 00090 } 00091 // -------------------------------------------------------------------- 00092 void push( const value_type& x ) 00093 { 00094 int i = size(); 00095 while ( i != 0 && x < vec_[i/2] ) 00096 { 00097 vec_[i] = vec_[i/2]; 00098 i = i/2; 00099 } 00100 vec_[i] = x; 00101 ++finish_; 00102 } 00103 // -------------------------------------------------------------------- 00104 value_type pop() 00105 { 00106 int n = size() - 1; 00107 value_type e = vec_[0]; 00108 value_type x = vec_[n]; 00109 --finish_; 00110 int i = 0; 00111 int c = 1; 00112 while ( c <= n ) 00113 { 00114 if ( c < n && vec_[c + 1] < vec_[c] ) 00115 ++c; 00116 if ( !( vec_[c] < x ) ) 00117 break; 00118 vec_[i] = vec_[c]; 00119 i = c; 00120 c = 2 * i; 00121 } 00122 vec_[i] = x; 00123 return e; 00124 } 00126 00127 protected: 00128 value_type vec_[QUEUE_SIZE]; 00129 00130 pointer start_, finish_, end_of_storage_; 00131 }; 00132 00133 } 00134 00135 #endif