Sierra Toolkit Version of the Day
iterator_eastl.h
00001 /*
00002 Copyright (C) 2009-2010 Electronic Arts, Inc.  All rights reserved.
00003 
00004 Redistribution and use in source and binary forms, with or without
00005 modification, are permitted provided that the following conditions
00006 are met:
00007 
00008 1.  Redistributions of source code must retain the above copyright
00009     notice, this list of conditions and the following disclaimer.
00010 2.  Redistributions in binary form must reproduce the above copyright
00011     notice, this list of conditions and the following disclaimer in the
00012     documentation and/or other materials provided with the distribution.
00013 3.  Neither the name of Electronic Arts, Inc. ("EA") nor the names of
00014     its contributors may be used to endorse or promote products derived
00015     from this software without specific prior written permission.
00016 
00017 THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY
00018 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00019 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00020 DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY
00021 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00022 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00023 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00024 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027 */
00028 
00030 // EASTL/iterator.h
00031 //
00032 // Copyright (c) 2005, Electronic Arts. All rights reserved.
00033 // Written and maintained by Paul Pedriana.
00035 
00036 
00037 #ifndef EASTL_ITERATOR_H
00038 #define EASTL_ITERATOR_H
00039 
00040 
00041 #include <stk_util/util/config_eastl.h>
00042 
00043 #ifdef _MSC_VER
00044     #pragma warning(push, 0)
00045 #endif
00046 
00047 #include <stddef.h>
00048 
00049 #ifdef _MSC_VER
00050     #pragma warning(pop)
00051 #endif
00052 
00053 // If the user has specified that we use std iterator
00054 // categories instead of EASTL iterator categories,
00055 // then #include <iterator>.
00056 #if EASTL_STD_ITERATOR_CATEGORY_ENABLED
00057     #ifdef _MSC_VER
00058         #pragma warning(push, 0)
00059     #endif
00060     #include <iterator>
00061     #ifdef _MSC_VER
00062         #pragma warning(pop)
00063     #endif
00064 #endif
00065 
00066 
00067 #ifdef _MSC_VER
00068     #pragma warning(push)           // VC++ generates a bogus warning that you cannot code away.
00069     #pragma warning(disable: 4619)  // There is no warning number 'number'.
00070     #pragma warning(disable: 4217)  // Member template functions cannot be used for copy-assignment or copy-construction.
00071 #elif defined(__SNC__)
00072     #pragma control %push diag
00073     #pragma diag_suppress=187       // Pointless comparison of unsigned integer with zero
00074 #endif
00075 
00076 
00077 namespace eastl
00078 {
00089     enum iterator_status_flag
00090     {
00091         isf_none            = 0x00, 
00092         isf_valid           = 0x01, 
00093         isf_current         = 0x02, 
00094         isf_can_dereference = 0x04  
00095     };
00096 
00097 
00098 
00099     // The following declarations are taken directly from the C++ standard document.
00100     //    input_iterator_tag, etc.
00101     //    iterator
00102     //    iterator_traits
00103     //    reverse_iterator
00104 
00105     // Iterator categories
00106     // Every iterator is defined as belonging to one of the iterator categories that
00107     // we define here. These categories come directly from the C++ standard.
00108     #if !EASTL_STD_ITERATOR_CATEGORY_ENABLED // If we are to use our own iterator category definitions...
00109         struct input_iterator_tag { };
00110         struct output_iterator_tag { };
00111         struct forward_iterator_tag       : public input_iterator_tag { };
00112         struct bidirectional_iterator_tag : public forward_iterator_tag { };
00113         struct random_access_iterator_tag : public bidirectional_iterator_tag { };
00114         struct contiguous_iterator_tag    : public random_access_iterator_tag { };  // Extension to the C++ standard. Contiguous ranges are more than random access, they are physically contiguous.
00115     #endif
00116 
00117 
00118     // struct iterator
00119     template <typename Category, typename T, typename Distance = ptrdiff_t,
00120               typename Pointer = T*, typename Reference = T&>
00121     struct iterator
00122     {
00123         typedef Category  iterator_category;
00124         typedef T         value_type;
00125         typedef Distance  difference_type;
00126         typedef Pointer   pointer;
00127         typedef Reference reference;
00128     };
00129 
00130 
00131     // struct iterator_traits
00132     template <typename Iterator>
00133     struct iterator_traits
00134     {
00135         typedef typename Iterator::iterator_category iterator_category;
00136         typedef typename Iterator::value_type        value_type;
00137         typedef typename Iterator::difference_type   difference_type;
00138         typedef typename Iterator::pointer           pointer;
00139         typedef typename Iterator::reference         reference;
00140     };
00141 
00142     template <typename T>
00143     struct iterator_traits<T*>
00144     {
00145         typedef EASTL_ITC_NS::random_access_iterator_tag iterator_category;     // To consider: Change this to contiguous_iterator_tag for the case that
00146         typedef T                                        value_type;            //              EASTL_ITC_NS is "eastl" instead of "std".
00147         typedef ptrdiff_t                                difference_type;
00148         typedef T*                                       pointer;
00149         typedef T&                                       reference;
00150     };
00151 
00152     template <typename T>
00153     struct iterator_traits<const T*>
00154     {
00155         typedef EASTL_ITC_NS::random_access_iterator_tag iterator_category;
00156         typedef T                                        value_type;
00157         typedef ptrdiff_t                                difference_type;
00158         typedef const T*                                 pointer;
00159         typedef const T&                                 reference;
00160     };
00161 
00162 
00163 
00164 
00165 
00179     template <typename Iterator>
00180     class reverse_iterator : public iterator<typename eastl::iterator_traits<Iterator>::iterator_category,
00181                                              typename eastl::iterator_traits<Iterator>::value_type,
00182                                              typename eastl::iterator_traits<Iterator>::difference_type,
00183                                              typename eastl::iterator_traits<Iterator>::pointer,
00184                                              typename eastl::iterator_traits<Iterator>::reference>
00185     {
00186     public:
00187         typedef Iterator                                                   iterator_type;
00188         typedef typename eastl::iterator_traits<Iterator>::pointer         pointer;
00189         typedef typename eastl::iterator_traits<Iterator>::reference       reference;
00190         typedef typename eastl::iterator_traits<Iterator>::difference_type difference_type;
00191 
00192     protected:
00193         Iterator mIterator;
00194 
00195     public:
00196         reverse_iterator()      // It's important that we construct mIterator, because if Iterator
00197             : mIterator() { }   // is a pointer, there's a difference between doing it and not.
00198 
00199         explicit reverse_iterator(iterator_type i)
00200             : mIterator(i) { }
00201 
00202         reverse_iterator(const reverse_iterator& ri)
00203             : mIterator(ri.mIterator) { }
00204 
00205         template <typename U>
00206         reverse_iterator(const reverse_iterator<U>& ri)
00207             : mIterator(ri.base()) { }
00208 
00209         // This operator= isn't in the standard, but the the C++
00210         // library working group has tentatively approved it, as it
00211         // allows const and non-const reverse_iterators to interoperate.
00212         template <typename U>
00213         reverse_iterator<Iterator>& operator=(const reverse_iterator<U>& ri)
00214             { mIterator = ri.base(); return *this; }
00215 
00216         iterator_type base() const
00217             { return mIterator; }
00218 
00219         reference operator*() const
00220         {
00221             iterator_type i(mIterator);
00222             return *--i;
00223         }
00224 
00225         pointer operator->() const
00226             { return &(operator*()); }
00227 
00228         reverse_iterator& operator++()
00229             { --mIterator; return *this; }
00230 
00231         reverse_iterator operator++(int)
00232         {
00233             reverse_iterator ri(*this);
00234             --mIterator;
00235             return ri;
00236         }
00237 
00238         reverse_iterator& operator--()
00239             { ++mIterator; return *this; }
00240 
00241         reverse_iterator operator--(int)
00242         {
00243             reverse_iterator ri(*this);
00244             ++mIterator;
00245             return ri;
00246         }
00247 
00248         reverse_iterator operator+(difference_type n) const
00249             { return reverse_iterator(mIterator - n); }
00250 
00251         reverse_iterator& operator+=(difference_type n)
00252             { mIterator -= n; return *this; }
00253 
00254         reverse_iterator operator-(difference_type n) const
00255             { return reverse_iterator(mIterator + n); }
00256 
00257         reverse_iterator& operator-=(difference_type n)
00258             { mIterator += n; return *this; }
00259 
00260         reference operator[](difference_type n) const
00261             { return mIterator[-n - 1]; }
00262     };
00263 
00264 
00265     // The C++ library working group has tentatively approved the usage of two
00266     // template parameters (Iterator1 and Iterator2) in order to allow reverse_iterators
00267     // and const_reverse iterators to be comparable. This is a similar issue to the
00268     // C++ defect report #179 regarding comparison of container iterators and const_iterators.
00269     template <typename Iterator1, typename Iterator2>
00270     inline bool
00271     operator==(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
00272         { return a.base() == b.base(); }
00273 
00274 
00275     template <typename Iterator1, typename Iterator2>
00276     inline bool
00277     operator<(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
00278         { return a.base() > b.base(); }
00279 
00280 
00281     template <typename Iterator1, typename Iterator2>
00282     inline bool
00283     operator!=(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
00284         { return a.base() != b.base(); }
00285 
00286 
00287     template <typename Iterator1, typename Iterator2>
00288     inline bool
00289     operator>(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
00290         { return a.base() < b.base(); }
00291 
00292 
00293     template <typename Iterator1, typename Iterator2>
00294     inline bool
00295     operator<=(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
00296         { return a.base() >= b.base(); }
00297 
00298 
00299     template <typename Iterator1, typename Iterator2>
00300     inline bool
00301     operator>=(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
00302         { return a.base() <= b.base(); }
00303 
00304 
00305     template <typename Iterator1, typename Iterator2>
00306     inline typename reverse_iterator<Iterator1>::difference_type
00307     operator-(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
00308         { return b.base() - a.base(); }
00309 
00310 
00311     template <typename Iterator>
00312     inline reverse_iterator<Iterator>
00313     operator+(typename reverse_iterator<Iterator>::difference_type n, const reverse_iterator<Iterator>& a)
00314         { return reverse_iterator<Iterator>(a.base() - n); }
00315 
00316 
00317 
00318 
00319 
00320 
00321 
00327     template <typename Container>
00328     class back_insert_iterator : public iterator<EASTL_ITC_NS::output_iterator_tag, void, void, void, void>
00329     {
00330     public:
00331         typedef Container                           container_type;
00332         typedef typename Container::const_reference const_reference;
00333 
00334     protected:
00335         Container& container;
00336 
00337     public:
00338         explicit back_insert_iterator(Container& x)
00339             : container(x) { }
00340 
00341         back_insert_iterator& operator=(const_reference value)
00342             { container.push_back(value); return *this; }
00343 
00344         back_insert_iterator& operator*()
00345             { return *this; }
00346 
00347         back_insert_iterator& operator++()
00348             { return *this; } // This is by design.
00349 
00350         back_insert_iterator operator++(int)
00351             { return *this; } // This is by design.
00352     };
00353 
00354 
00359     template <typename Container>
00360     inline back_insert_iterator<Container>
00361     back_inserter(Container& x)
00362         { return back_insert_iterator<Container>(x); }
00363 
00364 
00365 
00366 
00372     template <typename Container>
00373     class front_insert_iterator : public iterator<EASTL_ITC_NS::output_iterator_tag, void, void, void, void>
00374     {
00375     public:
00376         typedef Container                           container_type;
00377         typedef typename Container::const_reference const_reference;
00378 
00379     protected:
00380         Container& container;
00381 
00382     public:
00383         explicit front_insert_iterator(Container& x)
00384             : container(x) { }
00385 
00386         front_insert_iterator& operator=(const_reference value)
00387             { container.push_front(value); return *this; }
00388 
00389         front_insert_iterator& operator*()
00390             { return *this; }
00391 
00392         front_insert_iterator& operator++()
00393             { return *this; } // This is by design.
00394 
00395         front_insert_iterator operator++(int)
00396             { return *this; } // This is by design.
00397     };
00398 
00399 
00404     template <typename Container>
00405     inline front_insert_iterator<Container>
00406     front_inserter(Container& x)
00407         { return front_insert_iterator<Container>(x); }
00408 
00409 
00410 
00411 
00428     template <typename Container>
00429     class insert_iterator : public iterator<EASTL_ITC_NS::output_iterator_tag, void, void, void, void>
00430     {
00431     public:
00432         typedef Container                           container_type;
00433         typedef typename Container::iterator        iterator_type;
00434         typedef typename Container::const_reference const_reference;
00435 
00436     protected:
00437         Container&     container;
00438         iterator_type  it;
00439 
00440     public:
00441         // This assignment operator is defined more to stop compiler warnings (e.g. VC++ C4512)
00442         // than to be useful. However, it does an insert_iterator to be assigned to another
00443         // insert iterator provided that they point to the same container.
00444         insert_iterator& operator=(const insert_iterator& x)
00445         {
00446             EASTL_ASSERT(&x.container == &container);
00447             it = x.it;
00448             return *this;
00449         }
00450 
00451         insert_iterator(Container& x, iterator_type itNew)
00452             : container(x), it(itNew) {}
00453 
00454         insert_iterator& operator=(const_reference value)
00455         {
00456             it = container.insert(it, value);
00457             ++it;
00458             return *this;
00459         }
00460 
00461         insert_iterator& operator*()
00462             { return *this; }
00463 
00464         insert_iterator& operator++()
00465             { return *this; } // This is by design.
00466 
00467         insert_iterator& operator++(int)
00468             { return *this; } // This is by design.
00469 
00470     }; // insert_iterator
00471 
00472 
00477     template <typename Container, typename Iterator>
00478     inline eastl::insert_iterator<Container>
00479     inserter(Container& x, Iterator i)
00480     {
00481         typedef typename Container::iterator iterator;
00482         return eastl::insert_iterator<Container>(x, iterator(i));
00483     }
00484 
00485 
00486 
00487 
00495     template <typename InputIterator>
00496     inline typename eastl::iterator_traits<InputIterator>::difference_type
00497     distance_impl(InputIterator first, InputIterator last, EASTL_ITC_NS::input_iterator_tag)
00498     {
00499         typename eastl::iterator_traits<InputIterator>::difference_type n = 0;
00500 
00501         while(first != last)
00502         {
00503             ++first;
00504             ++n;
00505         }
00506         return n;
00507     }
00508 
00509     template <typename RandomAccessIterator>
00510     inline typename eastl::iterator_traits<RandomAccessIterator>::difference_type
00511     distance_impl(RandomAccessIterator first, RandomAccessIterator last, EASTL_ITC_NS::random_access_iterator_tag)
00512     {
00513         return last - first;
00514     }
00515 
00516     // Special version defined so that std C++ iterators can be recognized by
00517     // this function. Unfortunately, this function treats all foreign iterators
00518     // as InputIterators and thus can seriously hamper performance in the case
00519     // of large ranges of bidirectional_iterator_tag iterators.
00520     //template <typename InputIterator>
00521     //inline typename eastl::iterator_traits<InputIterator>::difference_type
00522     //distance_impl(InputIterator first, InputIterator last, ...)
00523     //{
00524     //    typename eastl::iterator_traits<InputIterator>::difference_type n = 0;
00525     //
00526     //    while(first != last)
00527     //    {
00528     //        ++first;
00529     //        ++n;
00530     //    }
00531     //    return n;
00532     //}
00533 
00534     template <typename InputIterator>
00535     inline typename eastl::iterator_traits<InputIterator>::difference_type
00536     distance(InputIterator first, InputIterator last)
00537     {
00538         typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
00539 
00540         return eastl::distance_impl(first, last, IC());
00541     }
00542 
00543 
00544 
00545 
00553     template <typename InputIterator, typename Distance>
00554     inline void
00555     advance_impl(InputIterator& i, Distance n, EASTL_ITC_NS::input_iterator_tag)
00556     {
00557         while(n--)
00558             ++i;
00559     }
00560 
00561     template <typename BidirectionalIterator, typename Distance>
00562     inline void
00563     advance_impl(BidirectionalIterator& i, Distance n, EASTL_ITC_NS::bidirectional_iterator_tag)
00564     {
00565         if(n > 0)
00566         {
00567             while(n--)
00568                 ++i;
00569         }
00570         else
00571         {
00572             while(n++)
00573                 --i;
00574         }
00575     }
00576 
00577     template <typename RandomAccessIterator, typename Distance>
00578     inline void
00579     advance_impl(RandomAccessIterator& i, Distance n, EASTL_ITC_NS::random_access_iterator_tag)
00580     {
00581         i += n;
00582     }
00583 
00584     // Special version defined so that std C++ iterators can be recognized by
00585     // this function. Unfortunately, this function treats all foreign iterators
00586     // as InputIterators and thus can seriously hamper performance in the case
00587     // of large ranges of bidirectional_iterator_tag iterators.
00588     //template <typename InputIterator, typename Distance>
00589     //inline void
00590     //advance_impl(InputIterator& i, Distance n, ...)
00591     //{
00592     //    while(n--)
00593     //        ++i;
00594     //}
00595 
00596     template <typename InputIterator, typename Distance>
00597     inline void
00598     advance(InputIterator& i, Distance n)
00599     {
00600         typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
00601 
00602         eastl::advance_impl(i, n, IC());
00603     }
00604 
00605 
00606 } // namespace eastl
00607 
00608 
00609 #if defined(_MSC_VER)
00610     #pragma warning(pop)
00611 #elif defined(__SNC__)
00612     #pragma control %pop diag
00613 #endif
00614 
00615 
00616 #endif // Header include guard
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines