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 00020 00021 #include "util/pstl/iterator.h" 00022 #include <string.h> 00023 00024 namespace wiselib 00025 { 00026 00027 template<typename OsModel_P, 00028 typename Value_P, 00029 int SET_SIZE> 00030 class set_static 00031 { 00032 public: 00033 typedef Value_P value_type; 00034 typedef value_type* pointer; 00035 typedef value_type& reference; 00036 typedef const value_type& const_reference; 00037 00038 typedef set_static<OsModel_P, value_type, SET_SIZE> set_type; 00039 00040 typedef normal_iterator<OsModel_P, pointer, set_type> iterator; 00041 00042 typedef typename OsModel_P::size_t size_type; 00043 // -------------------------------------------------------------------- 00044 set_static() 00045 { 00046 start_ = &set_[0]; 00047 finish_ = start_; 00048 end_of_storage_ = start_ + SET_SIZE; 00049 } 00050 // -------------------------------------------------------------------- 00051 set_static( const set_static& set ) 00052 { *this = set; } 00053 // -------------------------------------------------------------------- 00054 ~set_static() {} 00055 // -------------------------------------------------------------------- 00056 set_static& operator=( const set_static& set ) 00057 { 00058 memcpy( set_, set.set_, sizeof(set_) ); 00059 start_ = &set_[0]; 00060 finish_ = start_ + (set.finish_ - set.start_); 00061 end_of_storage_ = start_ + SET_SIZE; 00062 return *this; 00063 } 00064 // -------------------------------------------------------------------- 00067 iterator begin() 00068 { return iterator( start_ ); } 00069 // -------------------------------------------------------------------- 00070 iterator end() 00071 { return iterator( finish_ ); } 00072 // -------------------------------------------------------------------- 00073 //TODO iterator rbegin() 00074 //TODO iterator rend() 00076 // -------------------------------------------------------------------- 00079 size_type size() const 00080 { return size_type(finish_ - start_); } 00081 // -------------------------------------------------------------------- 00082 size_type max_size() const 00083 { return SET_SIZE; } 00084 // -------------------------------------------------------------------- 00085 size_type capacity() const 00086 { return SET_SIZE; } 00087 // -------------------------------------------------------------------- 00088 bool empty() const 00089 { return size() == 0; } 00090 00091 /*/ -------------------------------------------------------------------- 00092 00093 // -------------------------------------------------------------------- 00094 * 00095 */ 00096 iterator insert( iterator position , const value_type& x ) 00097 { 00098 // no more elements can be inserted because vector is full 00099 if ( size() == max_size() ) 00100 return iterator(finish_); 00101 00102 value_type cur = x, temp; 00103 00104 for ( iterator it = position; it != end(); ++it ) 00105 { 00106 if(cur == *it) 00107 return iterator(finish_); 00108 temp = *it; 00109 *it = cur; 00110 cur = temp; 00111 } 00112 push_back( cur ); 00113 return position; 00114 } 00115 // -------------------------------------------------------------------- 00116 inline iterator insert(const value_type& x ) 00117 { return insert(this->begin(), x); } 00118 // -------------------------------------------------------------------- 00119 void insert( iterator position, size_type n, const value_type& x ) 00120 { 00121 for ( int i = 0; i < n; ++i ) 00122 insert( position, x ); 00123 } 00124 // -------------------------------------------------------------------- 00125 iterator erase( iterator position ) 00126 { 00127 if ( position == end() ) 00128 return end(); 00129 00130 for ( iterator cur = position; cur != end(); cur++ ) 00131 *cur = *(cur + 1); 00132 00133 pop_back(); 00134 00135 return position; 00136 } 00137 // ------------------------------------------------------------------- 00138 00139 // -------------------------------------------------------------------- 00140 // -------------------------------------------------------------------- 00141 size_type erase( const value_type& x ) 00142 { 00143 size_type count = 0; 00144 iterator it; 00145 while ( (it = find(x)) != this->end() ) 00146 { 00147 erase( it); 00148 count++; 00149 } 00150 return count; 00151 } 00152 // -------------------------------------------------------------------- 00155 iterator find( const value_type& x ) 00156 { 00157 for ( iterator it = this->begin(); it != this->end(); ++it ) 00158 { 00159 iterator cur = it; 00160 if ( *cur.base() == x ) 00161 return cur; 00162 } 00163 return this->end(); 00164 } 00165 // -------------------------------------------------------------------- 00166 size_type count(const value_type& x) 00167 { 00168 size_type count = 0; 00169 00170 for ( iterator it = this->begin(); it != this->end(); ++it ) 00171 { 00172 iterator cur = it; 00173 if ( cur.base() == x ) 00174 count++; 00175 } 00176 00177 return count; 00178 } 00180 // -------------------------------------------------------------------- 00181 // -------------------------------------------------------------------- 00182 iterator erase( iterator first, iterator last ) 00183 { 00184 if ( first == end() || first == last ) 00185 return first; 00186 00187 iterator ret = first; 00188 00189 while ( last != end() ) 00190 { 00191 *first = *last; 00192 first++; 00193 last++; 00194 } 00195 00196 finish_ = &(*first); 00197 return ret; 00198 } 00199 // -------------------------------------------------------------------- 00200 void swap( set_type& set ) 00201 { 00202 set_type tmp = *this; 00203 *this = set; 00204 set = tmp; 00205 } 00206 // -------------------------------------------------------------------- 00207 void clear() 00208 { 00209 finish_ = start_; 00210 } 00212 00213 protected: 00214 value_type set_[SET_SIZE]; 00215 00216 pointer start_, finish_, end_of_storage_; 00217 00218 uint16_t count_, size_; 00219 00220 00221 private: 00222 00223 /* 00225 // -------------------------------------------------------------------- 00228 reference operator[](size_type n) 00229 { 00230 return *(this->start_ + n); 00231 } 00232 // -------------------------------------------------------------------- 00235 const_reference operator[](size_type n) const 00236 { 00237 return *(this->start_ + n); 00238 } 00239 // -------------------------------------------------------------------- 00240 reference at(size_type n) 00241 { 00242 return (*this)[n]; 00243 } 00244 // -------------------------------------------------------------------- 00245 const_reference at(size_type n) const 00246 { 00247 return (*this)[n]; 00248 } 00249 // -------------------------------------------------------------------- 00250 */ 00251 reference front() 00252 { 00253 return *begin(); 00254 } 00255 // -------------------------------------------------------------------- 00256 const_reference front() const 00257 { 00258 return *begin(); 00259 } 00260 // -------------------------------------------------------------------- 00261 reference back() 00262 { 00263 return *(end() - 1); 00264 } 00265 // -------------------------------------------------------------------- 00266 const_reference back() const 00267 { 00268 return *(end() - 1); 00269 } 00270 // -------------------------------------------------------------------- 00271 pointer data() 00272 { return pointer(this->start_); } 00274 // -------------------------------------------------------------------- 00277 template <class InputIterator> 00278 void assign ( InputIterator first, InputIterator last ) 00279 { 00280 clear(); 00281 for ( InputIterator it = first; it != last; ++it ) 00282 push_back( *it ); 00283 } 00284 // -------------------------------------------------------------------- 00285 void assign( size_type n, const value_type& u ) 00286 { 00287 clear(); 00288 for ( int i = 0; i < n; ++i ) 00289 push_back( u ); 00290 } 00291 // -------------------------------------------------------------------- 00292 void push_back( const value_type& x ) 00293 { 00294 if ( finish_ != end_of_storage_ ) 00295 { 00296 *finish_ = x; 00297 ++finish_; 00298 } 00299 } 00300 // -------------------------------------------------------------------- 00301 void pop_back() 00302 { 00303 if ( finish_ != start_ ) 00304 --finish_; 00305 } 00306 00307 }; 00308 00309 } 00310 00311 00312