PLearn: TinyVector.h Source File

00001 // -*- C++ -*- 00002 00003 // TinyVector.h: Definition of a tiny vector 00004 // Copyright (c) 2002 by Nicolas Chapados 00005 00006 // Redistribution and use in source and binary forms, with or without 00007 // modification, are permitted provided that the following conditions are met: 00008 // 00009 // 1. Redistributions of source code must retain the above copyright 00010 // notice, this list of conditions and the following disclaimer. 00011 // 00012 // 2. Redistributions in binary form must reproduce the above copyright 00013 // notice, this list of conditions and the following disclaimer in the 00014 // documentation and/or other materials provided with the distribution. 00015 // 00016 // 3. The name of the authors may not be used to endorse or promote 00017 // products derived from this software without specific prior written 00018 // permission. 00019 // 00020 // THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR 00021 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00022 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN 00023 // NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 00024 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 00025 // TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 00026 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 00027 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 00028 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 00029 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00030 // 00031 // This file is part of the PLearn library. For more information on the PLearn 00032 // library, go to the PLearn Web site at www.plearn.org 00033 00034 #ifndef TINYVECTOR_H 00035 #define TINYVECTOR_H 00036 00037 //#include <utility> 00038 //#include <stdexcept> // for out_of_range 00039 //#include <algorithm> // for lexicographical_compare 00040 #include <typeinfo> 00041 00042 #include "plerror.h" 00043 00046 namespace PLearn { 00047 using namespace std; 00048 //using namespace std::rel_ops; // ne compile pas, pour une raison etrange 00049 00051 template <class T> class TinyVectorTrait; 00052 00053 00054 //############################ CLASS TINYVECTOR ######################## 00068 template < class T, unsigned N, class TTrait = TinyVectorTrait<T> > 00069 class TinyVector 00070 { 00071 public: 00073 typedef T value_type; 00074 typedef size_t size_type; 00075 typedef ptrdiff_t difference_type; 00076 00077 typedef T* iterator; 00078 typedef const T* const_iterator; 00079 00080 typedef T* pointer; 00081 typedef const T* const_pointer; 00082 typedef T& reference; 00083 typedef const T& const_reference; 00084 00085 public: 00087 inline iterator begin(); 00088 inline const_iterator begin() const; 00089 inline iterator end(); 00090 inline const_iterator end() const; 00091 00092 public: 00094 inline reference operator[](size_type n); 00095 inline const_reference operator[](size_type n) const; 00096 00098 reference at(size_type n); 00099 const_reference at(size_type n) const; 00100 00101 inline reference front(); 00102 inline const_reference front() const; 00103 inline reference back(); 00104 inline const_reference back() const; 00105 00106 public: 00108 inline TinyVector(); 00109 inline explicit TinyVector(size_type n, const T& val=T()); 00111 00113 template <class In> 00114 TinyVector(In first, In last); 00115 00116 template <class In> 00117 void assign(In first, In last) { 00119 resize(last-first); 00120 for (size_type i=0; first != last && i < N; ++i, ++first) 00121 arr[i] = *first; 00122 } 00123 00124 inline void assign(size_type n, const T& val); 00125 00126 public: 00128 void push_back(const T& x); 00129 void pop_back(); 00130 00131 public: 00133 00134 public: 00136 size_type size() const; 00137 bool empty() const { 00138 return size() == 0; 00139 } 00140 size_type max_size() { 00141 return N; 00142 } 00143 void resize(size_type sz, const T& val=T()); 00144 void reserve(size_type n); 00145 00146 public: 00148 void swap(TinyVector&); 00149 00150 private: 00151 T arr[N]; 00152 }; 00153 00154 00156 template <class T, unsigned N, class TTrait> 00157 bool operator==(const TinyVector<T,N,TTrait>&, 00158 const TinyVector<T,N,TTrait>&); 00159 00161 template <class T, unsigned N, class TTrait> 00162 bool operator<(const TinyVector<T,N,TTrait>&, 00163 const TinyVector<T,N,TTrait>&); 00164 00167 template <class T, unsigned N, class TTrait> 00168 inline bool operator!=(const TinyVector<T,N,TTrait>& x, 00169 const TinyVector<T,N,TTrait>& y) 00170 { 00171 return !(x == y); 00172 } 00173 00174 template <class T, unsigned N, class TTrait> 00175 inline bool operator> (const TinyVector<T,N,TTrait>& x, 00176 const TinyVector<T,N,TTrait>& y) 00177 { 00178 return y < x; 00179 } 00180 00181 template <class T, unsigned N, class TTrait> 00182 inline bool operator<=(const TinyVector<T,N,TTrait>& x, 00183 const TinyVector<T,N,TTrait>& y) 00184 { 00185 return !(y < x); 00186 } 00187 00188 template <class T, unsigned N, class TTrait> 00189 inline bool operator>=(const TinyVector<T,N,TTrait>& x, 00190 const TinyVector<T,N,TTrait>& y) 00191 { 00192 return !(x < y); 00193 } 00194 00195 00196 //######################### CLASS TINYVECTORTRAIT ###################### 00204 template <typename T> class TinyVectorTrait {}; 00205 00206 template <> class TinyVectorTrait<unsigned char> { 00207 public: 00208 static const unsigned char Missing = UCHAR_MAX; // norman: initialize here 00209 }; 00210 template <> class TinyVectorTrait<char> { 00211 public: 00212 static const unsigned char Missing = UCHAR_MAX; // norman: initialize here 00213 }; 00214 template <> class TinyVectorTrait<unsigned int> { 00215 public: 00216 static const unsigned int Missing = UINT_MAX; // norman: initialize here 00217 }; 00218 template <> class TinyVectorTrait<int> { 00219 public: 00220 static const int Missing = INT_MAX; // norman: initialize here 00221 }; 00222 00223 00224 //##### Implementation of Iterators ##################################### 00225 00226 template <class T, unsigned N, class TTrait> 00227 typename TinyVector<T,N,TTrait>::iterator 00228 TinyVector<T,N,TTrait>::begin() 00229 { 00231 return &arr[0]; 00232 } 00233 00234 template <class T, unsigned N, class TTrait> 00235 typename TinyVector<T,N,TTrait>::const_iterator 00236 TinyVector<T,N,TTrait>::begin() const 00237 { 00239 return &arr[0]; 00240 } 00241 00242 template <class T, unsigned N, class TTrait> 00243 typename TinyVector<T,N,TTrait>::iterator 00244 TinyVector<T,N,TTrait>::end() 00245 { 00246 return &arr[0] + size(); 00247 } 00248 00249 template <class T, unsigned N, class TTrait> 00250 typename TinyVector<T,N,TTrait>::const_iterator 00251 TinyVector<T,N,TTrait>::end() const 00252 { 00253 return &arr[0] + size(); 00254 } 00255 00256 00257 //##### Implementation of Element Access ################################ 00258 00259 template <class T, unsigned N, class TTrait> 00260 typename TinyVector<T,N,TTrait>::reference 00261 TinyVector<T,N,TTrait>::operator[](size_type n) 00262 { 00263 #ifdef BOUNDCHECK 00264 if (n >= size()) 00265 PLERROR("%s: out-of-range.",typeid(*this).name()); 00266 #endif 00267 return arr[n]; 00268 } 00269 00270 template <class T, unsigned N, class TTrait> 00271 typename TinyVector<T,N,TTrait>::const_reference 00272 TinyVector<T,N,TTrait>::operator[](size_type n) const 00273 { 00274 #ifdef BOUNDCHECK 00275 if (n >= size()) 00276 PLERROR("%s: out-of-range.",typeid(*this).name()); 00277 #endif 00278 return arr[n]; 00279 } 00280 00281 template <class T, unsigned N, class TTrait> 00282 typename TinyVector<T,N,TTrait>::reference 00283 TinyVector<T,N,TTrait>::at(size_type n) 00284 { 00286 if (n >= size()) 00287 PLERROR("%s: out-of-range.",typeid(*this).name()); 00288 00289 return arr[n]; 00290 } 00291 00292 template <class T, unsigned N, class TTrait> 00293 typename TinyVector<T,N,TTrait>::const_reference 00294 TinyVector<T,N,TTrait>::at(size_type n) const 00295 { 00297 if (n >= size()) 00298 PLERROR("%s: out-of-range.",typeid(*this).name()); 00299 00300 return arr[n]; 00301 } 00302 00303 template <class T, unsigned N, class TTrait> 00304 typename TinyVector<T,N,TTrait>::reference 00305 TinyVector<T,N,TTrait>::front() 00306 { 00307 if (empty()) 00308 PLERROR("%s: out-of-range.",typeid(*this).name()); 00309 00310 return arr[0]; 00311 } 00312 00313 template <class T, unsigned N, class TTrait> 00314 typename TinyVector<T,N,TTrait>::const_reference 00315 TinyVector<T,N,TTrait>::front() const 00316 { 00317 if (empty()) 00318 PLERROR("%s: out-of-range.",typeid(*this).name()); 00319 00320 return arr[0]; 00321 } 00322 00323 template <class T, unsigned N, class TTrait> 00324 typename TinyVector<T,N,TTrait>::reference 00325 TinyVector<T,N,TTrait>::back() 00326 { 00327 if (empty()) 00328 PLERROR("%s: out-of-range.",typeid(*this).name()); 00329 00330 return *(end()-1); 00331 } 00332 00333 template <class T, unsigned N, class TTrait> 00334 typename TinyVector<T,N,TTrait>::const_reference 00335 TinyVector<T,N,TTrait>::back() const 00336 { 00337 if (empty()) 00338 PLERROR("%s: out-of-range.",typeid(*this).name()); 00339 00340 return *(end()-1); 00341 } 00342 00343 00344 //##### Implementation of Constructors, etc. ############################ 00345 00346 template <class T, unsigned N, class TTrait> 00347 void TinyVector<T,N,TTrait>::assign(size_type n, const T& val) 00348 { 00349 if (n > N) 00350 PLERROR("%s: out-of-range.",typeid(*this).name()); 00351 00352 resize(n); 00353 for (size_type i=0; i<n; ++i) 00354 arr[i] = val; 00355 } 00356 00357 template <class T, unsigned N, class TTrait> 00358 TinyVector<T,N,TTrait>::TinyVector() 00359 { 00360 assign(static_cast<size_type>(N), 00361 static_cast<const T&>(TTrait::Missing)); 00362 } 00363 00364 template <class T, unsigned N, class TTrait> 00365 TinyVector<T,N,TTrait>::TinyVector(size_type n, const T& val) 00366 { 00367 assign(n, val); 00368 if (n<N) 00369 for (size_type i=n; i<N; ++i) 00370 arr[i] = TTrait::Missing; 00371 } 00372 00373 00374 //##### Implementation of Stack Operations ############################## 00375 00376 template <class T, unsigned N, class TTrait> 00377 void TinyVector<T,N,TTrait>::push_back(const T& x) 00378 { 00379 size_type s = size(); 00380 if (s >= N) 00381 PLERROR("%s: out-of-range.",typeid(*this).name()); 00382 00383 arr[s] = x; 00384 } 00385 00386 template <class T, unsigned N, class TTrait> 00387 void TinyVector<T,N,TTrait>::pop_back() 00388 { 00389 size_type s = size(); 00390 if (s == 0) 00391 PLERROR("%s: out-of-range.",typeid(*this).name()); 00392 00393 arr[s-1] = TTrait::Missing; 00394 } 00395 00396 00397 //##### Implementation of Size/Capacity Operations ###################### 00398 00399 template <class T, unsigned N, class TTrait> 00400 typename TinyVector<T,N,TTrait>::size_type 00401 TinyVector<T,N,TTrait>::size() const 00402 { 00403 difference_type p = N-1; 00404 00405 while (p >= 0 && arr[p] == static_cast<T>(TTrait::Missing)) 00406 p--; 00407 return p+1; 00408 } 00409 00410 template <class T, unsigned N, class TTrait> 00411 void TinyVector<T,N,TTrait>::resize(size_type sz, const T& val) 00412 { 00413 if (sz > max_size()) 00414 PLERROR("%s: out-of-range.",typeid(*this).name()); 00415 00416 size_type s = size(); 00417 while (s < sz) 00418 arr[s++] = val; 00419 while (sz < N) 00420 arr[sz++] = TTrait::Missing; 00421 } 00422 00423 template <class T, unsigned N, class TTrait> 00424 void TinyVector<T,N,TTrait>::reserve(size_type n) 00425 { 00426 if (n > max_size()) 00427 PLERROR("%s: out-of-range.",typeid(*this).name()); 00428 00429 } 00430 00431 00432 //##### Implementation of Other Functions ############################### 00433 00434 template <class T, unsigned N, class TTrait> 00435 void TinyVector<T,N,TTrait>::swap(TinyVector<T,N,TTrait>& other) 00436 { 00437 using namespace std; 00438 00439 for (size_type i=0; i<N; ++i) 00440 swap(arr[i], other.arr[i]); 00441 } 00442 00443 template <class T, unsigned N, class TTrait> 00444 bool operator==(const TinyVector<T,N,TTrait>& x, 00445 const TinyVector<T,N,TTrait>& y) 00446 { 00447 bool equal = true; 00448 typename TinyVector<T,N,TTrait>::const_iterator 00449 xit=x.begin(), xend=x.end(), yit=y.begin(), yend=y.end(); 00450 if (xend-xit != yend-yit) 00451 return false; 00452 for ( ; equal && xit != xend && yit != yend ; ++xit, ++yit) 00453 equal = (*xit == *yit); 00454 return equal; 00455 } 00456 00457 template <class T, unsigned N, class TTrait> 00458 bool operator<(const TinyVector<T,N,TTrait>& x, 00459 const TinyVector<T,N,TTrait>& y) 00460 { 00461 return std::lexicographical_compare(x.begin(), x.end(), 00462 y.begin(), y.end()); 00463 } 00464 00465 } // end of namespace PLearn 00466 00467 #endif // TINYVECTOR_H