Vector.h

Go to the documentation of this file.
00001 //
00002 //  Copyright (c) 2003-2006 by Autodesk, Inc.
00003 //
00004 //  By using this code, you are agreeing to the terms and conditions of
00005 //  the License Agreement included in the documentation for this code.
00006 //
00007 //  AUTODESK MAKES NO WARRANTIES, EXPRESS OR IMPLIED,
00008 //  AS TO THE CORRECTNESS OF THIS CODE OR ANY DERIVATIVE
00009 //  WORKS WHICH INCORPORATE IT.
00010 //
00011 //  AUTODESK PROVIDES THE CODE ON AN "AS-IS" BASIS
00012 //  AND EXPLICITLY DISCLAIMS ANY LIABILITY, INCLUDING
00013 //  CONSEQUENTIAL AND INCIDENTAL DAMAGES FOR ERRORS,
00014 //  OMISSIONS, AND OTHER PROBLEMS IN THE CODE.
00015 //
00016 //  Use, duplication, or disclosure by the U.S. Government is subject to
00017 //  restrictions set forth in FAR 52.227-19 (Commercial Computer Software
00018 //  Restricted Rights) and DFAR 252.227-7013(c)(1)(ii) (Rights in Technical
00019 //  Data and Computer Software), as applicable.
00020 //
00021 //  $Header: //DWF/Development/Components/Internal/DWF Core/v1.6/develop/global/src/dwfcore/Vector.h#1 $
00022 //  $DateTime: 2008/02/20 08:38:28 $
00023 //  $Author: appacsviewers $
00024 //  $Change: 84992 $
00025 //  $Revision: #1 $
00026 //
00027 
00028 #ifndef _DWFCORE_SORTED_VECTOR_H
00029 #define _DWFCORE_SORTED_VECTOR_H
00030 
00031 
00036 
00037 #include "dwfcore/Core.h"
00038 #include "dwfcore/STL.h"
00039 #include "dwfcore/Exception.h"
00040 #include "dwfcore/Comparator.h"
00041 #include "dwfcore/Iterator.h"
00042 
00043 #include <algorithm>
00044 
00045 namespace DWFCore
00046 {
00047 
00060 template < class T, class Pr = tDWFCompareLess<T>, class Eq = tDWFCompareEqual<T> >
00061 class DWFVector : virtual public DWFCoreMemory
00062 {
00063 
00064 public:
00065 
00069     typedef typename DWFCore::DWFVectorConstIterator<T>      ConstIterator;
00070 
00071 public:
00072 
00078     DWFVector()
00079         throw()
00080         : _oVector()
00081     {;}
00082 
00089     DWFVector( const std::vector<T>& oVector )
00090         throw()
00091         : _oVector( oVector )
00092     {;}
00093 
00100     DWFVector( const DWFVector<T>& oVector )
00101         throw()
00102         : _oVector( oVector._oVector )
00103     {;}
00104 
00110     virtual ~DWFVector()
00111         throw()
00112     {;}
00113 
00121     bool erase( const T& oValue )
00122         throw()
00123     {
00124         _tSTLIterator iterNewEnd = std::remove( _oVector.begin(), _oVector.end(), oValue );
00125 
00126         if (iterNewEnd==_oVector.end())
00127         {
00128             return false;
00129         }
00130         else
00131         {
00132             _oVector.erase( iterNewEnd, _oVector.end() );
00133             return true;
00134         }
00135     }
00136 
00143     void eraseAt( size_t index )
00144         throw( DWFException )
00145     {
00146         if (index<size())
00147         {
00148             _oVector.erase( _oVector.begin()+index );
00149         }
00150         else
00151         {
00152             _DWFCORE_THROW( DWFUnexpectedException, /*NOXLATE*/L"Vector index is past the end of range" );
00153         }
00154     }
00155 
00165     void eraseAt( size_t iStart, size_t iStop )
00166         throw( DWFException )
00167     {
00168         if (iStart<size())
00169         {
00170             if (iStop<=size())
00171             {
00172                 _oVector.erase( _oVector.begin()+iStart, _oVector.begin()+iStop );
00173             }
00174             else
00175             {
00176                 _oVector.erase( _oVector.begin()+iStart, _oVector.end() );
00177             }
00178         }
00179         else
00180         {
00181             _DWFCORE_THROW( DWFUnexpectedException, /*NOXLATE*/L"Starting vector index is past the end of range" );
00182         }
00183     }
00184 
00191     void clear()
00192         throw()
00193     {
00194         _oVector.clear();
00195     }
00196 
00203     bool empty() const
00204     {
00205         return _oVector.empty();
00206     }
00207 
00214     size_t size() const
00215         throw()
00216     {
00217         return _oVector.size();
00218     }
00219 
00227     virtual size_t count( const T& oValue ) const
00228         throw() = 0;
00229 
00236     virtual const T& front() const
00237         throw( DWFException ) = 0;
00238 
00245     virtual const T& back() const
00246         throw( DWFException ) = 0;
00247 
00255     virtual const T& operator[]( size_t index ) const
00256         throw( DWFException ) = 0;
00257 
00268     virtual bool findFirst( const T& oValue, size_t& iFirst ) const
00269         throw() = 0;
00270 
00278     virtual bool operator==( const DWFVector<T, Pr, Eq>& oVector ) const
00279         throw()
00280     {
00281         return (_oVector==oVector._oVector);
00282     }
00283 
00294     virtual ConstIterator* constIterator() const
00295         throw() = 0;
00296 
00297 protected:
00298 
00299     typedef typename std::vector<T>::iterator            _tSTLIterator;
00300     typedef typename std::vector<T>::const_iterator      _tSTLConstIterator;
00301 
00302 protected:
00303 
00304     // The STL vector in which all the elements are stored
00305     std::vector<T>      _oVector;
00306 
00307     Pr                  _tCompares;
00308     Eq                  _tEquals;
00309 
00310 private:
00311 
00312     DWFVector& operator=( const DWFVector<T, Pr, Eq>& oVector );
00313 
00314 };
00315 
00316 
00330 template < class T, class Pr = tDWFCompareLess<T>, class Eq = tDWFCompareEqual<T> >
00331 class DWFOrderedVector : public DWFVector<T, Pr, Eq>
00332                        , virtual public DWFCoreMemory
00333 {
00334 
00335 public:
00336 
00340     typedef DWFVectorIterator<T>                Iterator;
00341 
00346     typedef enum
00347     {
00351         eDefault        = 0,
00352 
00356         eFront          = 1,
00357 
00361         eBack           = 2
00362 
00363     } teVectorInsertLocation;
00364 
00365 public:
00366 
00372     DWFOrderedVector<T, Pr, Eq>()
00373         throw()
00374         : DWFVector<T, Pr, Eq>()
00375     {;}
00376 
00387     DWFOrderedVector<T, Pr, Eq>( size_t nSize, const T& tValue )
00388         throw()
00389         : DWFVector<T, Pr, Eq>( std::vector<T>( nSize, tValue ) )
00390     {;}
00391 
00398     DWFOrderedVector<T, Pr, Eq>( const std::vector<T>& oVector )
00399         throw()
00400         : DWFVector<T, Pr, Eq>( oVector )
00401     {;}
00402 
00409     DWFOrderedVector<T, Pr, Eq>( const DWFOrderedVector<T, Pr, Eq>& oVector )
00410         throw()
00411         : DWFVector<T, Pr, Eq>( oVector )
00412     {;}
00413 
00419     ~DWFOrderedVector()
00420         throw()
00421     {;}
00422 
00429     virtual DWFOrderedVector<T, Pr, Eq>& operator=( const DWFOrderedVector<T, Pr, Eq>& oVector )
00430         throw()
00431     {
00432         if (this != &oVector)
00433         {
00434             this->_oVector = oVector._oVector;
00435         }
00436 
00437         return *this;
00438     }
00439 
00447     void insert( const T& oValue, 
00448                  teVectorInsertLocation eLoc = eDefault )
00449         throw()
00450     {
00451         switch (eLoc)
00452         {
00453             case eFront:
00454             {
00455                 this->_oVector.insert( this->_oVector.begin(), oValue );
00456                 break;
00457             }
00458             case eBack:
00459             case eDefault:
00460             default:
00461             {
00462                 this->_oVector.push_back( oValue );
00463                 break;
00464             }
00465         }
00466     }
00467 
00475     void insert( const std::vector<T>& oVector, 
00476                  teVectorInsertLocation eLoc = eDefault )
00477         throw()
00478     {
00479         switch (eLoc)
00480         {
00481             case eFront:
00482             {
00483                 this->_oVector.insert( this->_oVector.begin(), oVector.begin(), oVector.end() );
00484                 break;
00485             }
00486             case eBack:
00487             case eDefault:
00488             default:
00489             {
00490                 this->_oVector.insert( this->_oVector.end(), oVector.begin(), oVector.end() );
00491                 break;
00492             }
00493         }
00494     }
00495 
00503     void insert( const DWFOrderedVector<T>& oOrderedVector, 
00504                  teVectorInsertLocation eLoc = eDefault )
00505         throw()
00506     {
00507         const std::vector<T>& oVector = oOrderedVector._oVector;
00508         insert( oVector, eLoc );
00509     }
00510 
00518     void insertAt( const T& oValue, size_t index )
00519         throw( DWFException )
00520     {
00521         if (index>this->size())
00522         {
00523             _DWFCORE_THROW( DWFUnexpectedException, /*NOXLATE*/L"The insertion index is larger than the vector size" );
00524         }
00525 
00526         if (index==this->size())
00527         {
00528             push_back( oValue );
00529         }
00530         else
00531         {
00532             this->_oVector.insert( this->_oVector.begin()+index, oValue );
00533         }
00534     }
00535 
00542     void push_back( const T& oValue )
00543         throw()
00544     {
00545         this->_oVector.push_back( oValue );
00546     }
00547 
00555     virtual size_t count( const T& oValue ) const
00556         throw()
00557     {
00558         int nCount=0;
00559 
00560         _tSTLConstIterator iter = this->_oVector.begin();
00561         for (; iter!=this->_oVector.end(); ++iter)
00562         {
00563             if (_tEquals(*iter, oValue))
00564             {
00565                 ++nCount;
00566             }
00567         }
00568 
00569         return nCount;
00570     }
00571 
00572 
00583     virtual bool findFirst( const T& oValue, size_t& iFirst ) const
00584         throw()
00585     {
00586         iFirst = 0;
00587 
00588         _tSTLConstIterator iter = this->_oVector.begin();
00589         for (; iter!=this->_oVector.end(); ++iter)
00590         {
00591             if (_tEquals( oValue, *iter ))
00592             {
00593                 return true;
00594             }
00595             else
00596                 ++iFirst;
00597         }
00598  
00599         // The value was not found
00600         return false;
00601     }
00602 
00613     virtual size_t findAll( const T& oValue, DWFOrderedVector<unsigned int>& oIndices ) const
00614         throw()
00615     {
00616         oIndices.clear();
00617 
00618         _tSTLConstIterator it = this->_oVector.begin();
00619         unsigned int i = 0;
00620         for (; it != this->_oVector.end(); ++it, ++i)
00621         {
00622             if (_tEquals( oValue, *it ))
00623             {
00624                 oIndices.push_back( i );
00625             }
00626         }
00627 
00628         return oIndices.size();
00629     }
00630 
00637     T& front()
00638         throw( DWFException )
00639     {
00640         if (this->empty())
00641         {
00642             _DWFCORE_THROW( DWFUnexpectedException, /*NOXLATE*/L"The vector has no elements" );
00643         }
00644 
00645         return this->_oVector.front();
00646     }
00647 
00651     virtual const T& front() const
00652         throw( DWFException )
00653     {
00654         if (this->empty())
00655         {
00656             _DWFCORE_THROW( DWFUnexpectedException, /*NOXLATE*/L"The vector has no elements" );
00657         }
00658 
00659         return this->_oVector.front();
00660     }
00661 
00668     T& back()
00669         throw( DWFException )
00670     {
00671         if (this->empty())
00672         {
00673             _DWFCORE_THROW( DWFUnexpectedException, /*NOXLATE*/L"The vector has no elements" );
00674         }
00675 
00676         return this->_oVector.back();
00677     }
00678 
00682     virtual const T& back() const
00683         throw( DWFException )
00684     {
00685         if (this->empty())
00686         {
00687             _DWFCORE_THROW( DWFUnexpectedException, /*NOXLATE*/L"The vector has no elements" );
00688         }
00689 
00690         return this->_oVector.back();
00691     }
00692 
00700     T& operator[]( size_t index )
00701         throw( DWFException )
00702     {
00703         if (index<this->size())
00704         {
00705             return this->_oVector[index];
00706         }
00707         else
00708         {
00709             _DWFCORE_THROW( DWFUnexpectedException, /*NOXLATE*/L"Vector index is past the end of range" );
00710         }
00711     }
00712 
00720     const T& operator[]( size_t index ) const
00721         throw( DWFException )
00722     {
00723         if (index<this->size())
00724         {
00725             return this->_oVector[index];
00726         }
00727         else
00728         {
00729             _DWFCORE_THROW( DWFUnexpectedException, /*NOXLATE*/L"Vector index is past the end of range" );
00730         }
00731     }
00732 
00741     virtual typename DWFOrderedVector<T>::Iterator* iterator()
00742         throw()
00743     {
00744         return DWFCORE_ALLOC_OBJECT( DWFVectorIterator<T>( this->_oVector ) );
00745     }
00746 
00750     virtual typename DWFOrderedVector<T>::ConstIterator* constIterator() const
00751         throw()
00752     {
00753         return DWFCORE_ALLOC_OBJECT( DWFVectorConstIterator<T>( this->_oVector ) );
00754     }
00755 
00756 private:
00757 
00758     typedef typename std::vector<T>::iterator            _tSTLIterator;
00759     typedef typename std::vector<T>::const_iterator      _tSTLConstIterator;
00760 
00761 };
00762 
00763 
00779 template < class T, class Pr = tDWFCompareLess<T>, class Eq = tDWFCompareEqual<T> >
00780 class DWFSortedVector : public DWFVector<T, Pr, Eq>
00781                       , virtual public DWFCoreMemory
00782 {
00783 
00784 public:
00785 
00793     DWFSortedVector<T, Pr, Eq>( bool bAllowDuplicates = true )
00794         throw()
00795         : DWFVector<T, Pr, Eq>()
00796         , _bAllowDuplicates( bAllowDuplicates )
00797     {;}
00798 
00806     DWFSortedVector<T, Pr, Eq>( const std::vector<T>& oVector, bool bAllowDuplicates = true )
00807         throw()
00808         : DWFVector<T, Pr, Eq>( oVector )
00809         , _bAllowDuplicates( bAllowDuplicates )
00810     {
00811         std::sort( this->_oVector.begin(), this->_oVector.end(), this->_tCompares );
00812         
00813         // Remove duplicates if they are not allowed
00814         if (_bAllowDuplicates==false)
00815         {
00816             // Since the vector already sorted, we can use std::unique
00817             typename DWFVector<T>::_tSTLIterator iterNewEnd  = std::unique( 
00818                 this->_oVector.begin(), 
00819                 this->_oVector.end(), 
00820                 this->_tEquals );
00821             this->_oVector.erase( iterNewEnd, this->_oVector.end() );
00822         }
00823     }
00824 
00831     DWFSortedVector<T, Pr, Eq>( const DWFSortedVector<T, Pr, Eq>& oVector )
00832         throw()
00833         : DWFVector<T, Pr, Eq>( oVector )
00834         , _bAllowDuplicates( oVector._bAllowDuplicates )
00835     {;}
00836 
00842     ~DWFSortedVector()
00843         throw()
00844     {;}
00845 
00846 
00853     DWFSortedVector<T, Pr, Eq>& operator=( const DWFSortedVector<T, Pr, Eq>& oVector )
00854         throw()
00855     {
00856         if (this!=&oVector)
00857         {
00858             this->_oVector = oVector._oVector;
00859             _bAllowDuplicates = oVector._bAllowDuplicates;
00860         }
00861 
00862         return *this;
00863     }
00864 
00871     void insert( const T& oValue )
00872         throw()
00873     {
00874         // Lower bound returns the position with a value that is greater (lesser depending on predicate)
00875         // than or equivalent to the given value.
00876         _tSTLIterator iter = std::lower_bound( this->_oVector.begin(), this->_oVector.end(), oValue, this->_tCompares );
00877 
00878         if (_bAllowDuplicates == true)
00879         {
00880             this->_oVector.insert( iter, oValue );
00881         }
00882         else
00883         {
00884             // Insert only if the value was not found 
00885             if ( iter==this->_oVector.end() || _tCompares( oValue, *iter) )
00886             {
00887                 this->_oVector.insert( iter, oValue );
00888             }
00889             else
00890             {
00891                 return;
00892             }
00893         }
00894     }
00895 
00902     void insert( const std::vector<T>& oVector )
00903         throw()
00904     {
00905         DWFSortedVector<T, Pr, Eq> v( oVector );
00906         insert( v );
00907     }
00908 
00915     void insert( const DWFSortedVector<T, Pr, Eq>& oSortedVector )
00916         throw()
00917     {
00918         // Get a reference directly to the STL vector of the input DWFSortedVector
00919         const std::vector<T>& oVectorIn = oSortedVector._oVector;
00920 
00921         // Make a copy, since we will overwrite _oVector
00922         std::vector<T>  oOriginal = this->_oVector;
00923 
00924         // Resize _oVector to hold it original elements and the new ones
00925         this->_oVector.resize( this->_oVector.size() + oVectorIn.size() );
00926 
00927         std::merge( oOriginal.begin(), oOriginal.end(), 
00928                     oVectorIn.begin(), oVectorIn.end(),
00929                     this->_oVector.begin(), this->_tCompares );
00930 
00931         if (_bAllowDuplicates==false)
00932         {
00933             // Since the vector already sorted, we can use std::unique
00934             _tSTLIterator iterNewEnd  = std::unique( this->_oVector.begin(), this->_oVector.end(), this->_tEquals );
00935             this->_oVector.erase( iterNewEnd, this->_oVector.end() );
00936         }
00937     }
00938 
00946     virtual size_t count( const T& oValue ) const
00947         throw()
00948     {
00949         std::pair< _tSTLConstIterator, _tSTLConstIterator > iterResult;
00950         iterResult = std::equal_range( this->_oVector.begin(), this->_oVector.end(), oValue, this->_tCompares );
00951 
00952         return (iterResult.second - iterResult.first);
00953     }
00954 
00958     virtual const T& front() const
00959         throw( DWFException )
00960     {
00961         if (this->empty())
00962         {
00963             _DWFCORE_THROW( DWFUnexpectedException, /*NOXLATE*/L"The vector has no elements" );
00964         }
00965 
00966         return this->_oVector.front();
00967     }
00968 
00972     virtual const T& back() const
00973         throw( DWFException )
00974     {
00975         if (this->empty())
00976         {
00977             _DWFCORE_THROW( DWFUnexpectedException, /*NOXLATE*/L"The vector has no elements" );
00978         }
00979 
00980         return this->_oVector.back();
00981     }
00982 
00990     virtual const T& operator[]( size_t index ) const
00991         throw( DWFException )
00992     {
00993         if (index<this->size())
00994         {
00995             return this->_oVector[index];
00996         }
00997         else
00998         {
00999             _DWFCORE_THROW( DWFUnexpectedException, /*NOXLATE*/L"Vector index is past the end of range" );
01000         }
01001     }
01002 
01013     virtual bool findFirst( const T& oValue, size_t& iFirst ) const
01014         throw()
01015     {
01016         // Using lower_bound is twice as fast as using equal_range, hence the rationale
01017         // for this method.
01018         _tSTLConstIterator iter = std::lower_bound( this->_oVector.begin(), this->_oVector.end(), oValue, this->_tCompares );
01019 
01020         if ( iter==this->_oVector.end() || _tCompares( oValue, *iter) )
01021         {
01022             // The value was not found
01023             return false;
01024         }
01025         else
01026         {
01027             iFirst = iter - this->_oVector.begin();
01028             return true;
01029         }
01030     }
01031 
01044     bool find( const T& oValue, size_t& iFirst, size_t& iLast ) const
01045         throw()
01046     {
01047         std::pair<_tSTLConstIterator, _tSTLConstIterator> iterResult;
01048         iterResult = std::equal_range( this->_oVector.begin(), this->_oVector.end(), oValue, this->_tCompares );
01049         
01050         size_t diff = iterResult.second - iterResult.first;
01051         if (diff > 0)
01052         {
01053             iFirst = iterResult.first - this->_oVector.begin();
01054             iLast  = iFirst + diff - 1;
01055             return true;
01056         }
01057         else
01058         {
01059             return false;
01060         }
01061     }
01062 
01070     void allowDuplicates( bool bAllow = true )
01071         throw()
01072     {
01073         if (bAllow==_bAllowDuplicates)
01074         {
01075             return;
01076         }
01077 
01078         if (bAllow==false)
01079         {
01080             _tSTLIterator iterNewEnd = std::unique( this->_oVector.begin(), this->_oVector.end(), this->_tEquals );
01081             this->_oVector.erase( iterNewEnd, this->_oVector.end() );
01082         }
01083 
01084         _bAllowDuplicates = bAllow;
01085     }
01086 
01093     bool duplicatesAllowed() const
01094         throw()
01095     {
01096         return _bAllowDuplicates;
01097     }
01098 
01102     virtual typename DWFSortedVector<T>::ConstIterator* constIterator() const
01103         throw()
01104     {
01105         return DWFCORE_ALLOC_OBJECT( DWFVectorConstIterator<T>( this->_oVector ) );
01106     }
01107 
01108 private:
01109 
01110     bool                _bAllowDuplicates;
01111 
01112 
01113 private:
01114 
01115     typedef typename std::vector<T>::iterator            _tSTLIterator;
01116     typedef typename std::vector<T>::const_iterator      _tSTLConstIterator;
01117 
01118 };
01119 
01120 }
01121 
01122 #endif
01123 

Generated on Tue Jan 6 22:39:29 2009 for Autodesk DWF Core Library by  doxygen 1.4.5