PLearn: SmallVector.h Source File

00001 // -*- C++ -*- 00002 00003 // SmallVector.h: Small vectors 00004 // Copyright (c) 2000 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 00037 #ifndef SMALLVECTOR 00038 #define SMALLVECTOR 00039 00040 #include <typeinfo> 00041 #include <algorithm> 00042 00043 #include "ArrayAllocatorTrivial.h" 00044 #include "general.h" 00045 00046 namespace PLearn { 00047 using namespace std; 00048 00049 00050 00051 //########################### CLASS SMALLVECTOR ############################ 00060 template <class T, unsigned SizeBits, 00061 class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00062 class SmallVector 00063 { 00064 public: 00066 typedef SmallVector<T,SizeBits> self_type; 00067 typedef Allocator alloc_type; 00068 00069 typedef T value_type; 00070 typedef size_t size_type; 00071 typedef ptrdiff_t difference_type; 00072 00073 typedef T* iterator; 00074 typedef const T* const_iterator; 00075 00076 typedef T* pointer; 00077 typedef const T* const_pointer; 00078 typedef T& reference; 00079 typedef const T& const_reference; 00080 00081 public: 00083 inline iterator begin(); 00084 inline const_iterator begin() const; 00085 inline iterator end(); 00086 inline const_iterator end() const; 00087 00088 public: 00090 inline reference operator[](size_type n); 00091 inline const_reference operator[](size_type n) const; 00092 00094 reference at(size_type n); 00095 const_reference at(size_type n) const; 00096 00097 inline reference front(); 00098 inline const_reference front() const; 00099 inline reference back(); 00100 inline const_reference back() const; 00101 00102 public: 00104 inline SmallVector(); 00105 inline SmallVector(size_type n, const T& val=T()); 00106 ~SmallVector(); 00107 SmallVector(const self_type&); 00108 self_type& operator=(const self_type&); 00109 00111 template <class In> 00112 SmallVector(In first, In last) : i(0,0) { 00113 assign(first,last); 00114 } 00115 00116 template <class In> 00117 void assign(In first, In last) { 00119 resize(last-first); 00120 iterator dest = begin(); 00121 while (first != last) 00122 *dest++ = *first++; 00123 } 00124 00125 inline void assign(size_type n, const T& val); 00126 00127 public: 00129 void push_back(const T& x); 00130 void pop_back(); 00131 00132 public: 00134 00135 public: 00137 size_type size() const; 00138 bool empty() const { 00139 return size() == 0; 00140 } 00141 size_type max_size() { 00142 typename alloc_type::index_type dummy(unsigned(-1), unsigned(-1)); 00143 return dummy.size; 00144 } 00145 void resize(size_type sz, const T& val=T()); 00146 void reserve(size_type n); 00147 00148 public: 00150 void swap(SmallVector&); 00151 00153 static void allocator(alloc_type* the_alloc) { 00154 assert(the_alloc); 00155 alloc = the_alloc; 00156 } 00157 static alloc_type& allocator() { 00158 return *alloc; 00159 } 00160 00161 private: 00162 static alloc_type* alloc; 00163 typename alloc_type::index_type i; 00164 }; 00165 00167 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00168 //inline unsigned int hash(SmallVector<T,SizeBits,Allocator>& v) 00169 template <class T, unsigned SizeBits, class Allocator> 00170 inline unsigned int hashval(const SmallVector<T,SizeBits,Allocator>& v) 00171 { return hashbytes(const_cast<char*>(&v[0]),sizeof(T)*size()); } 00172 00174 template <class T, unsigned SizeBits, class Allocator> 00175 bool operator==(const SmallVector<T,SizeBits,Allocator>& a, 00176 const SmallVector<T,SizeBits,Allocator>& b); 00177 00178 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00179 //inline bool operator!=(const SmallVector<T,SizeBits,Allocator>& x, 00181 template <class T, unsigned SizeBits, class Allocator> 00182 inline bool operator!=(const SmallVector<T,SizeBits,Allocator>& x, 00183 const SmallVector<T,SizeBits,Allocator>& y) { return !(x==y); } 00184 00185 00187 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00188 //bool operator<(const SmallVector<T,SizeBits,Allocator>&, 00190 template <class T, unsigned SizeBits> 00191 bool operator<(const SmallVector<T,SizeBits>&, 00192 const SmallVector<T,SizeBits>&); 00193 00194 00195 //##### Static Members ###################################################### 00196 00197 template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00198 Allocator* SmallVector<T,SizeBits,Allocator>::alloc; 00199 00200 00201 00202 //##### Implementation of Iterators ######################################### 00203 00204 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00205 template <class T, unsigned SizeBits, class Allocator> 00206 typename SmallVector<T,SizeBits,Allocator>::iterator 00207 SmallVector<T,SizeBits,Allocator>::begin() 00208 { 00210 return allocator().toPointer(i); 00211 } 00212 00213 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00214 template <class T, unsigned SizeBits, class Allocator> 00215 typename SmallVector<T,SizeBits,Allocator>::const_iterator 00216 SmallVector<T,SizeBits,Allocator>::begin() const 00217 { 00219 return allocator().toPointer(i); 00220 } 00221 00222 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00223 template <class T, unsigned SizeBits, class Allocator> 00224 typename SmallVector<T,SizeBits,Allocator>::iterator 00225 SmallVector<T,SizeBits,Allocator>::end() 00226 { 00227 return begin() + size(); 00228 } 00229 00230 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00231 template <class T, unsigned SizeBits, class Allocator> 00232 typename SmallVector<T,SizeBits,Allocator>::const_iterator 00233 SmallVector<T,SizeBits,Allocator>::end() const 00234 { 00235 return begin() + size(); 00236 } 00237 00238 00239 //##### Implementation of Element Access #################################### 00240 00241 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00242 template <class T, unsigned SizeBits, class Allocator> 00243 typename SmallVector<T,SizeBits,Allocator>::reference 00244 SmallVector<T,SizeBits,Allocator>::operator[](size_type n) 00245 { 00246 #ifdef BOUNDCHECK 00247 if (n >= size()) 00248 PLERROR("%s: out-of-range.",typeid(*this).name()); 00249 #endif 00250 return *(begin()+n); 00251 } 00252 00253 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00254 template <class T, unsigned SizeBits, class Allocator> 00255 typename SmallVector<T,SizeBits,Allocator>::const_reference 00256 SmallVector<T,SizeBits,Allocator>::operator[](size_type n) const 00257 { 00258 #ifdef BOUNDCHECK 00259 if (n >= size()) 00260 PLERROR("%s: out-of-range.",typeid(*this).name()); 00261 #endif 00262 return *(begin()+n); 00263 } 00264 00265 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00266 template <class T, unsigned SizeBits, class Allocator> 00267 typename SmallVector<T,SizeBits,Allocator>::reference 00268 SmallVector<T,SizeBits,Allocator>::at(size_type n) 00269 { 00271 if (n >= size()) 00272 PLERROR("%s: out-of-range.",typeid(*this).name()); 00273 00274 return *(begin()+n); 00275 } 00276 00277 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00278 template <class T, unsigned SizeBits, class Allocator> 00279 typename SmallVector<T,SizeBits,Allocator>::const_reference 00280 SmallVector<T,SizeBits,Allocator>::at(size_type n) const 00281 { 00283 if (n >= size()) 00284 PLERROR("%s: out-of-range.",typeid(*this).name()); 00285 00286 return *(begin()+n); 00287 } 00288 00289 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00290 template <class T, unsigned SizeBits, class Allocator> 00291 typename SmallVector<T,SizeBits,Allocator>::reference 00292 SmallVector<T,SizeBits,Allocator>::front() 00293 { 00294 if (empty()) 00295 PLERROR("%s: out-of-range.",typeid(*this).name()); 00296 00297 return *begin(); 00298 } 00299 00300 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00301 template <class T, unsigned SizeBits, class Allocator> 00302 typename SmallVector<T,SizeBits,Allocator>::const_reference 00303 SmallVector<T,SizeBits,Allocator>::front() const 00304 { 00305 if (empty()) 00306 PLERROR("%s: out-of-range.",typeid(*this).name()); 00307 00308 return *begin(); 00309 } 00310 00311 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00312 template <class T, unsigned SizeBits, class Allocator> 00313 typename SmallVector<T,SizeBits,Allocator>::reference 00314 SmallVector<T,SizeBits,Allocator>::back() 00315 { 00316 if (empty()) 00317 PLERROR("%s: out-of-range.",typeid(*this).name()); 00318 00319 return *(end()-1); 00320 } 00321 00322 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00323 template <class T, unsigned SizeBits, class Allocator> 00324 typename SmallVector<T,SizeBits,Allocator>::const_reference 00325 SmallVector<T,SizeBits,Allocator>::back() const 00326 { 00327 if (empty()) 00328 PLERROR("%s: out-of-range.",typeid(*this).name()); 00329 00330 return *(end()-1); 00331 } 00332 00333 00334 //##### Implementation of Constructors, etc. ################################ 00335 00336 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00337 template <class T, unsigned SizeBits, class Allocator> 00338 void SmallVector<T,SizeBits,Allocator>::assign(size_type n, const T& val) 00339 { 00340 if (n > max_size()) 00341 PLERROR("%s: out-of-range.",typeid(*this).name()); 00342 00343 resize(n); 00344 for (size_type i=0; i<n; ++i) 00345 (*this)[i] = val; 00346 } 00347 00348 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00349 template <class T, unsigned SizeBits, class Allocator> 00350 inline SmallVector<T,SizeBits,Allocator>::SmallVector() 00351 : i(0,0) 00352 { } 00353 00354 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00355 template <class T, unsigned SizeBits, class Allocator> 00356 inline SmallVector<T,SizeBits,Allocator>::SmallVector(size_type n, const T& val) 00357 : i(0,0) 00358 { 00359 assign(n, val); 00360 } 00361 00362 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00363 template <class T, unsigned SizeBits, class Allocator> 00364 SmallVector<T,SizeBits,Allocator>::SmallVector(const self_type& other) 00365 : i(0) 00366 { 00367 assign(other.begin(), other.end()); 00368 } 00369 00370 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00371 template <class T, unsigned SizeBits, class Allocator> 00372 SmallVector<T,SizeBits,Allocator>::~SmallVector() 00373 { 00374 allocator().deallocate(i); 00375 } 00376 00377 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00378 template <class T, unsigned SizeBits, class Allocator> 00379 typename SmallVector<T,SizeBits,Allocator>::self_type& 00380 SmallVector<T,SizeBits,Allocator>::operator=(const self_type& other) 00381 { 00382 if (size() != other.size()) { 00383 self_type tmp(other); 00384 swap(tmp); 00385 } 00386 else { 00387 assign(other.begin(), other.end()); 00388 } 00389 return *this; 00390 } 00391 00392 00393 //##### Implementation of Stack Operations ################################## 00394 00395 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00396 template <class T, unsigned SizeBits, class Allocator> 00397 void SmallVector<T,SizeBits,Allocator>::push_back(const T& x) 00398 { 00399 size_type s = size(); 00400 resize(s+1); 00401 (*this)[s] = x; 00402 } 00403 00404 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00405 template <class T, unsigned SizeBits, class Allocator> 00406 void SmallVector<T,SizeBits,Allocator>::pop_back() 00407 { 00408 size_type s = size(); 00409 if (s == 0) 00410 PLERROR("%s: out-of-range.",typeid(*this).name()); 00411 resize(s-1); 00412 } 00413 00414 00415 //##### Implementation of Size/Capacity Operations ########################## 00416 00417 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00418 template <class T, unsigned SizeBits, class Allocator> 00419 typename SmallVector<T,SizeBits,Allocator>::size_type 00420 SmallVector<T,SizeBits,Allocator>::size() const 00421 { 00422 if (i.isNull()) 00423 return 0; 00424 else 00425 return i.size; 00426 } 00427 00428 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00429 template <class T, unsigned SizeBits, class Allocator> 00430 void SmallVector<T,SizeBits,Allocator>::resize(size_type sz, const T& val) 00431 { 00432 if (sz > max_size()) 00433 PLERROR("%s: out-of-range.",typeid(*this).name()); 00434 00435 pointer newdata = allocator().allocate(sz); 00436 typename alloc_type::index_type newi = allocator().toIndex(newdata, sz); 00437 00439 pointer olddata = allocator().toPointer(i); 00440 size_type n = std::min(int(sz), int(i.size)); 00441 while (n--) 00442 *newdata++ = *olddata++; 00443 00445 n = std::max(0, int(sz) - int(i.size)); 00446 while (n--) 00447 *newdata++ = val; 00448 00450 allocator().deallocate(i); 00451 i = newi; 00452 } 00453 00454 00455 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00456 template <class T, unsigned SizeBits, class Allocator> 00457 void SmallVector<T,SizeBits,Allocator>::reserve(size_type n) 00458 { 00459 if (n > max_size()) 00460 PLERROR("%s: out-of-range.",typeid(*this).name()); 00461 00462 } 00463 00464 00465 //##### Implementation of Other Functions ################################### 00466 00467 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00468 template <class T, unsigned SizeBits, class Allocator> 00469 void SmallVector<T,SizeBits,Allocator>::swap(SmallVector<T,SizeBits,Allocator>& other) 00470 { 00471 std::swap(i,other.i); 00472 } 00473 00474 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00475 template <class T, unsigned SizeBits, class Allocator> 00476 bool operator==(const SmallVector<T,SizeBits,Allocator>& x, 00477 const SmallVector<T,SizeBits,Allocator>& y) 00478 { 00479 bool equal = true; 00480 typename SmallVector<T,SizeBits,Allocator>::const_iterator 00481 xit=x.begin(), xend=x.end(), yit=y.begin(), yend=y.end(); 00482 if (xend-xit != yend-yit) 00483 return false; 00484 for ( ; equal && xit != xend && yit != yend ; ++xit, ++yit) 00485 equal = (*xit == *yit); 00486 return equal; 00487 } 00488 00489 //template <class T, unsigned SizeBits, class Allocator = ArrayAllocatorTrivial<T,SizeBits> > 00490 template <class T, unsigned SizeBits, class Allocator> 00491 bool operator<(const SmallVector<T,SizeBits,Allocator>& x, 00492 const SmallVector<T,SizeBits,Allocator>& y) 00493 { 00494 return std::lexicographical_compare(x.begin(), x.end(), 00495 y.begin(), y.end()); 00496 } 00497 00498 } // end of namespace PLearn 00499 00500 00501 #endif