PLearn 0.1
SmallVector.h
Go to the documentation of this 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         PLASSERT(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
00502 
00503 
00504 /*
00505   Local Variables:
00506   mode:c++
00507   c-basic-offset:4
00508   c-file-style:"stroustrup"
00509   c-file-offsets:((innamespace . 0)(inline-open . 0))
00510   indent-tabs-mode:nil
00511   fill-column:79
00512   End:
00513 */
00514 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=79 :
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines