Sierra Toolkit  Version of the Day
iterator_eastl.h
1 /*
2 Copyright (C) 2009-2010 Electronic Arts, Inc. All rights reserved.
3 
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions
6 are met:
7 
8 1. Redistributions of source code must retain the above copyright
9  notice, this list of conditions and the following disclaimer.
10 2. Redistributions in binary form must reproduce the above copyright
11  notice, this list of conditions and the following disclaimer in the
12  documentation and/or other materials provided with the distribution.
13 3. Neither the name of Electronic Arts, Inc. ("EA") nor the names of
14  its contributors may be used to endorse or promote products derived
15  from this software without specific prior written permission.
16 
17 THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY
18 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28 
30 // EASTL/iterator.h
31 //
32 // Copyright (c) 2005, Electronic Arts. All rights reserved.
33 // Written and maintained by Paul Pedriana.
35 
36 
37 #ifndef EASTL_ITERATOR_H
38 #define EASTL_ITERATOR_H
39 
40 
41 #include <stk_util/util/config_eastl.h>
42 
43 #ifdef _MSC_VER
44  #pragma warning(push, 0)
45 #endif
46 
47 #include <stddef.h>
48 
49 #ifdef _MSC_VER
50  #pragma warning(pop)
51 #endif
52 
53 // If the user has specified that we use std iterator
54 // categories instead of EASTL iterator categories,
55 // then #include <iterator>.
56 #if EASTL_STD_ITERATOR_CATEGORY_ENABLED
57  #ifdef _MSC_VER
58  #pragma warning(push, 0)
59  #endif
60  #include <iterator>
61  #ifdef _MSC_VER
62  #pragma warning(pop)
63  #endif
64 #endif
65 
66 
67 #ifdef _MSC_VER
68  #pragma warning(push) // VC++ generates a bogus warning that you cannot code away.
69  #pragma warning(disable: 4619) // There is no warning number 'number'.
70  #pragma warning(disable: 4217) // Member template functions cannot be used for copy-assignment or copy-construction.
71 #elif defined(__SNC__)
72  #pragma control %push diag
73  #pragma diag_suppress=187 // Pointless comparison of unsigned integer with zero
74 #endif
75 
76 
77 namespace eastl
78 {
90  {
91  isf_none = 0x00,
92  isf_valid = 0x01,
93  isf_current = 0x02,
95  };
96 
97 
98 
99  // The following declarations are taken directly from the C++ standard document.
100  // input_iterator_tag, etc.
101  // iterator
102  // iterator_traits
103  // reverse_iterator
104 
105  // Iterator categories
106  // Every iterator is defined as belonging to one of the iterator categories that
107  // we define here. These categories come directly from the C++ standard.
108  #if !EASTL_STD_ITERATOR_CATEGORY_ENABLED // If we are to use our own iterator category definitions...
109  struct input_iterator_tag { };
110  struct output_iterator_tag { };
111  struct forward_iterator_tag : public input_iterator_tag { };
112  struct bidirectional_iterator_tag : public forward_iterator_tag { };
113  struct random_access_iterator_tag : public bidirectional_iterator_tag { };
114  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.
115  #endif
116 
117 
118  // struct iterator
119  template <typename Category, typename T, typename Distance = ptrdiff_t,
120  typename Pointer = T*, typename Reference = T&>
121  struct iterator
122  {
123  typedef Category iterator_category;
124  typedef T value_type;
125  typedef Distance difference_type;
126  typedef Pointer pointer;
127  typedef Reference reference;
128  };
129 
130 
131  // struct iterator_traits
132  template <typename Iterator>
133  struct iterator_traits
134  {
135  typedef typename Iterator::iterator_category iterator_category;
136  typedef typename Iterator::value_type value_type;
137  typedef typename Iterator::difference_type difference_type;
138  typedef typename Iterator::pointer pointer;
139  typedef typename Iterator::reference reference;
140  };
141 
142  template <typename T>
143  struct iterator_traits<T*>
144  {
145  typedef EASTL_ITC_NS::random_access_iterator_tag iterator_category; // To consider: Change this to contiguous_iterator_tag for the case that
146  typedef T value_type; // EASTL_ITC_NS is "eastl" instead of "std".
147  typedef ptrdiff_t difference_type;
148  typedef T* pointer;
149  typedef T& reference;
150  };
151 
152  template <typename T>
153  struct iterator_traits<const T*>
154  {
155  typedef EASTL_ITC_NS::random_access_iterator_tag iterator_category;
156  typedef T value_type;
157  typedef ptrdiff_t difference_type;
158  typedef const T* pointer;
159  typedef const T& reference;
160  };
161 
162 
163 
164 
165 
179  template <typename Iterator>
180  class reverse_iterator : public iterator<typename eastl::iterator_traits<Iterator>::iterator_category,
181  typename eastl::iterator_traits<Iterator>::value_type,
182  typename eastl::iterator_traits<Iterator>::difference_type,
183  typename eastl::iterator_traits<Iterator>::pointer,
184  typename eastl::iterator_traits<Iterator>::reference>
185  {
186  public:
187  typedef Iterator iterator_type;
188  typedef typename eastl::iterator_traits<Iterator>::pointer pointer;
189  typedef typename eastl::iterator_traits<Iterator>::reference reference;
190  typedef typename eastl::iterator_traits<Iterator>::difference_type difference_type;
191 
192  protected:
193  Iterator mIterator;
194 
195  public:
196  reverse_iterator() // It's important that we construct mIterator, because if Iterator
197  : mIterator() { } // is a pointer, there's a difference between doing it and not.
198 
199  explicit reverse_iterator(iterator_type i)
200  : mIterator(i) { }
201 
203  : mIterator(ri.mIterator) { }
204 
205  template <typename U>
207  : mIterator(ri.base()) { }
208 
209  // This operator= isn't in the standard, but the the C++
210  // library working group has tentatively approved it, as it
211  // allows const and non-const reverse_iterators to interoperate.
212  template <typename U>
213  reverse_iterator<Iterator>& operator=(const reverse_iterator<U>& ri)
214  { mIterator = ri.base(); return *this; }
215 
216  iterator_type base() const
217  { return mIterator; }
218 
219  reference operator*() const
220  {
221  iterator_type i(mIterator);
222  return *--i;
223  }
224 
225  pointer operator->() const
226  { return &(operator*()); }
227 
228  reverse_iterator& operator++()
229  { --mIterator; return *this; }
230 
231  reverse_iterator operator++(int)
232  {
233  reverse_iterator ri(*this);
234  --mIterator;
235  return ri;
236  }
237 
238  reverse_iterator& operator--()
239  { ++mIterator; return *this; }
240 
241  reverse_iterator operator--(int)
242  {
243  reverse_iterator ri(*this);
244  ++mIterator;
245  return ri;
246  }
247 
248  reverse_iterator operator+(difference_type n) const
249  { return reverse_iterator(mIterator - n); }
250 
251  reverse_iterator& operator+=(difference_type n)
252  { mIterator -= n; return *this; }
253 
254  reverse_iterator operator-(difference_type n) const
255  { return reverse_iterator(mIterator + n); }
256 
257  reverse_iterator& operator-=(difference_type n)
258  { mIterator += n; return *this; }
259 
260  reference operator[](difference_type n) const
261  { return mIterator[-n - 1]; }
262  };
263 
264 
265  // The C++ library working group has tentatively approved the usage of two
266  // template parameters (Iterator1 and Iterator2) in order to allow reverse_iterators
267  // and const_reverse iterators to be comparable. This is a similar issue to the
268  // C++ defect report #179 regarding comparison of container iterators and const_iterators.
269  template <typename Iterator1, typename Iterator2>
270  inline bool
271  operator==(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
272  { return a.base() == b.base(); }
273 
274 
275  template <typename Iterator1, typename Iterator2>
276  inline bool
277  operator<(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
278  { return a.base() > b.base(); }
279 
280 
281  template <typename Iterator1, typename Iterator2>
282  inline bool
283  operator!=(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
284  { return a.base() != b.base(); }
285 
286 
287  template <typename Iterator1, typename Iterator2>
288  inline bool
289  operator>(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
290  { return a.base() < b.base(); }
291 
292 
293  template <typename Iterator1, typename Iterator2>
294  inline bool
295  operator<=(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
296  { return a.base() >= b.base(); }
297 
298 
299  template <typename Iterator1, typename Iterator2>
300  inline bool
301  operator>=(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
302  { return a.base() <= b.base(); }
303 
304 
305  template <typename Iterator1, typename Iterator2>
306  inline typename reverse_iterator<Iterator1>::difference_type
307  operator-(const reverse_iterator<Iterator1>& a, const reverse_iterator<Iterator2>& b)
308  { return b.base() - a.base(); }
309 
310 
311  template <typename Iterator>
312  inline reverse_iterator<Iterator>
313  operator+(typename reverse_iterator<Iterator>::difference_type n, const reverse_iterator<Iterator>& a)
314  { return reverse_iterator<Iterator>(a.base() - n); }
315 
316 
317 
318 
319 
320 
321 
327  template <typename Container>
328  class back_insert_iterator : public iterator<EASTL_ITC_NS::output_iterator_tag, void, void, void, void>
329  {
330  public:
331  typedef Container container_type;
332  typedef typename Container::const_reference const_reference;
333 
334  protected:
335  Container& container;
336 
337  public:
338  explicit back_insert_iterator(Container& x)
339  : container(x) { }
340 
341  back_insert_iterator& operator=(const_reference value)
342  { container.push_back(value); return *this; }
343 
344  back_insert_iterator& operator*()
345  { return *this; }
346 
347  back_insert_iterator& operator++()
348  { return *this; } // This is by design.
349 
350  back_insert_iterator operator++(int)
351  { return *this; } // This is by design.
352  };
353 
354 
359  template <typename Container>
361  back_inserter(Container& x)
362  { return back_insert_iterator<Container>(x); }
363 
364 
365 
366 
372  template <typename Container>
373  class front_insert_iterator : public iterator<EASTL_ITC_NS::output_iterator_tag, void, void, void, void>
374  {
375  public:
376  typedef Container container_type;
377  typedef typename Container::const_reference const_reference;
378 
379  protected:
380  Container& container;
381 
382  public:
383  explicit front_insert_iterator(Container& x)
384  : container(x) { }
385 
386  front_insert_iterator& operator=(const_reference value)
387  { container.push_front(value); return *this; }
388 
389  front_insert_iterator& operator*()
390  { return *this; }
391 
392  front_insert_iterator& operator++()
393  { return *this; } // This is by design.
394 
395  front_insert_iterator operator++(int)
396  { return *this; } // This is by design.
397  };
398 
399 
404  template <typename Container>
406  front_inserter(Container& x)
407  { return front_insert_iterator<Container>(x); }
408 
409 
410 
411 
428  template <typename Container>
429  class insert_iterator : public iterator<EASTL_ITC_NS::output_iterator_tag, void, void, void, void>
430  {
431  public:
432  typedef Container container_type;
433  typedef typename Container::iterator iterator_type;
434  typedef typename Container::const_reference const_reference;
435 
436  protected:
437  Container& container;
438  iterator_type it;
439 
440  public:
441  // This assignment operator is defined more to stop compiler warnings (e.g. VC++ C4512)
442  // than to be useful. However, it does an insert_iterator to be assigned to another
443  // insert iterator provided that they point to the same container.
444  insert_iterator& operator=(const insert_iterator& x)
445  {
446  EASTL_ASSERT(&x.container == &container);
447  it = x.it;
448  return *this;
449  }
450 
451  insert_iterator(Container& x, iterator_type itNew)
452  : container(x), it(itNew) {}
453 
454  insert_iterator& operator=(const_reference value)
455  {
456  it = container.insert(it, value);
457  ++it;
458  return *this;
459  }
460 
461  insert_iterator& operator*()
462  { return *this; }
463 
464  insert_iterator& operator++()
465  { return *this; } // This is by design.
466 
467  insert_iterator& operator++(int)
468  { return *this; } // This is by design.
469 
470  }; // insert_iterator
471 
472 
477  template <typename Container, typename Iterator>
479  inserter(Container& x, Iterator i)
480  {
481  typedef typename Container::iterator iterator;
482  return eastl::insert_iterator<Container>(x, iterator(i));
483  }
484 
485 
486 
487 
495  template <typename InputIterator>
496  inline typename eastl::iterator_traits<InputIterator>::difference_type
497  distance_impl(InputIterator first, InputIterator last, EASTL_ITC_NS::input_iterator_tag)
498  {
499  typename eastl::iterator_traits<InputIterator>::difference_type n = 0;
500 
501  while(first != last)
502  {
503  ++first;
504  ++n;
505  }
506  return n;
507  }
508 
509  template <typename RandomAccessIterator>
510  inline typename eastl::iterator_traits<RandomAccessIterator>::difference_type
511  distance_impl(RandomAccessIterator first, RandomAccessIterator last, EASTL_ITC_NS::random_access_iterator_tag)
512  {
513  return last - first;
514  }
515 
516  // Special version defined so that std C++ iterators can be recognized by
517  // this function. Unfortunately, this function treats all foreign iterators
518  // as InputIterators and thus can seriously hamper performance in the case
519  // of large ranges of bidirectional_iterator_tag iterators.
520  //template <typename InputIterator>
521  //inline typename eastl::iterator_traits<InputIterator>::difference_type
522  //distance_impl(InputIterator first, InputIterator last, ...)
523  //{
524  // typename eastl::iterator_traits<InputIterator>::difference_type n = 0;
525  //
526  // while(first != last)
527  // {
528  // ++first;
529  // ++n;
530  // }
531  // return n;
532  //}
533 
534  template <typename InputIterator>
535  inline typename eastl::iterator_traits<InputIterator>::difference_type
536  distance(InputIterator first, InputIterator last)
537  {
538  typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
539 
540  return eastl::distance_impl(first, last, IC());
541  }
542 
543 
544 
545 
553  template <typename InputIterator, typename Distance>
554  inline void
555  advance_impl(InputIterator& i, Distance n, EASTL_ITC_NS::input_iterator_tag)
556  {
557  while(n--)
558  ++i;
559  }
560 
561  template <typename BidirectionalIterator, typename Distance>
562  inline void
563  advance_impl(BidirectionalIterator& i, Distance n, EASTL_ITC_NS::bidirectional_iterator_tag)
564  {
565  if(n > 0)
566  {
567  while(n--)
568  ++i;
569  }
570  else
571  {
572  while(n++)
573  --i;
574  }
575  }
576 
577  template <typename RandomAccessIterator, typename Distance>
578  inline void
579  advance_impl(RandomAccessIterator& i, Distance n, EASTL_ITC_NS::random_access_iterator_tag)
580  {
581  i += n;
582  }
583 
584  // Special version defined so that std C++ iterators can be recognized by
585  // this function. Unfortunately, this function treats all foreign iterators
586  // as InputIterators and thus can seriously hamper performance in the case
587  // of large ranges of bidirectional_iterator_tag iterators.
588  //template <typename InputIterator, typename Distance>
589  //inline void
590  //advance_impl(InputIterator& i, Distance n, ...)
591  //{
592  // while(n--)
593  // ++i;
594  //}
595 
596  template <typename InputIterator, typename Distance>
597  inline void
598  advance(InputIterator& i, Distance n)
599  {
600  typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
601 
602  eastl::advance_impl(i, n, IC());
603  }
604 
605 
606 } // namespace eastl
607 
608 
609 #if defined(_MSC_VER)
610  #pragma warning(pop)
611 #elif defined(__SNC__)
612  #pragma control %pop diag
613 #endif
614 
615 
616 #endif // Header include guard
eastl::insert_iterator< Container > inserter(Container &x, Iterator i)
The iterator is valid and points to the same element it did when created. For example, if an iterator points to vector::begin() but an element is inserted at the front, the iterator is valid but not current. Modification of elements in place do not make iterators non-current.
front_insert_iterator< Container > front_inserter(Container &x)
back_insert_iterator< Container > back_inserter(Container &x)
iterator_status_flag
eastl::iterator_traits< InputIterator >::difference_type distance_impl(InputIterator first, InputIterator last, EASTL_ITC_NS::input_iterator_tag)
void advance_impl(InputIterator &i, Distance n, EASTL_ITC_NS::input_iterator_tag)
The iterator is valid, which means it is in the range of [begin, end].
This is called none and not called invalid because it is not strictly the opposite of invalid...
EA Standard Template Library.