uiterator.h

   1 // This file is part of the ustl library, an STL implementation.
   2 //
   3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
   4 // This file is free software, distributed under the MIT License.
   5 //
   6 /// \file uiterator.h
   7 /// \brief Contains various iterator adapters.
   8 //
   9
  10 #ifndef UITERATOR_H_5BCA176C7214A30F2069E2614D2DC226
  11 #define UITERATOR_H_5BCA176C7214A30F2069E2614D2DC226
  12
  13 #include "utypes.h"
  14
  15 namespace ustl {
  16
  17 //----------------------------------------------------------------------
  18
  19 /// \struct iterator_traits uiterator.h ustl.h
  20 /// \brief Contains the type traits of \p Iterator
  21 ///
  22 template <typename Iterator>
  23 struct iterator_traits {
  24     typedef typename Iterator::value_type        value_type;
  25     typedef typename Iterator::difference_type   difference_type;
  26     typedef typename Iterator::pointer           pointer;
  27     typedef typename Iterator::reference         reference;
  28 };
  29
  30 #ifndef DOXYGEN_SHOULD_SKIP_THIS
  31
  32 template <typename T>
  33 struct iterator_traits<T*> {
  34     typedef T           value_type;
  35     typedef ptrdiff_t   difference_type;
  36     typedef const T*    const_pointer;
  37     typedef T*          pointer;
  38     typedef const T&    const_reference;
  39     typedef T&          reference;
  40 };
  41
  42 template <typename T>
  43 struct iterator_traits<const T*> {
  44     typedef T           value_type;
  45     typedef ptrdiff_t   difference_type;
  46     typedef const T*    const_pointer;
  47     typedef const T*    pointer;
  48     typedef const T&    const_reference;
  49     typedef const T&    reference;
  50 };
  51
  52 template <>
  53 struct iterator_traits<void*> {
  54     typedef uint8_t             value_type;
  55     typedef ptrdiff_t           difference_type;
  56     typedef const void*         const_pointer;
  57     typedef void*               pointer;
  58     typedef const value_type&   const_reference;
  59     typedef value_type&         reference;
  60 };
  61
  62 template <>
  63 struct iterator_traits<const void*> {
  64     typedef uint8_t             value_type;
  65     typedef ptrdiff_t           difference_type;
  66     typedef const void*         const_pointer;
  67     typedef const void*         pointer;
  68     typedef const value_type&   const_reference;
  69     typedef const value_type&   reference;
  70 };
  71
  72 #endif
  73
  74 //----------------------------------------------------------------------
  75
  76 /// \class reverse_iterator uiterator.h ustl.h
  77 /// \ingroup IteratorAdaptors
  78 /// \brief Wraps \p Iterator to behave in an exactly opposite manner.
  79 ///
  80 template <class Iterator>
  81 class reverse_iterator {
  82 public:
  83     typedef typename iterator_traits<Iterator>::value_type      value_type;
  84     typedef typename iterator_traits<Iterator>::difference_type difference_type;
  85     typedef typename iterator_traits<Iterator>::pointer         pointer;
  86     typedef typename iterator_traits<Iterator>::reference       reference;
  87 public:
  88                                 reverse_iterator (void) : m_i() {}
  89     explicit                    reverse_iterator (Iterator iter) : m_i (iter) {}
  90     inline bool                 operator== (const reverse_iterator& iter) const { return (m_i == iter.m_i); }
  91     inline bool                 operator< (const reverse_iterator& iter) const { return (iter.m_i < m_i); }
  92     inline Iterator             base (void) const { return (m_i); }
  93     inline reference            operator* (void) const { Iterator prev (m_i); --prev; return (*prev); }
  94     inline pointer              operator-> (void) const { return (&(operator*())); }
  95     inline reverse_iterator&    operator++ (void) { -- m_i; return (*this); }
  96     inline reverse_iterator&    operator-- (void) { ++ m_i; return (*this); }
  97     inline reverse_iterator     operator++ (int) { reverse_iterator prev (*this); -- m_i; return (prev); }
  98     inline reverse_iterator     operator-- (int) { reverse_iterator prev (*this); ++ m_i; return (prev); }
  99     inline reverse_iterator&    operator+= (size_t n) { m_i -= n; return (*this); }
 100     inline reverse_iterator&    operator-= (size_t n) { m_i += n; return (*this); }
 101     inline reverse_iterator     operator+ (size_t n) const { return (reverse_iterator (m_i - n)); }
 102     inline reverse_iterator     operator- (size_t n) const { return (reverse_iterator (m_i + n)); }
 103     inline reference            operator[] (uoff_t n) const { return (*(*this + n)); }
 104     inline difference_type      operator- (const reverse_iterator& i) const { return (distance (m_i, i.m_i)); }
 105 protected:
 106     Iterator            m_i;
 107 };
 108
 109 //----------------------------------------------------------------------
 110
 111 /// \class insert_iterator uiterator.h ustl.h
 112 /// \ingroup IteratorAdaptors
 113 /// \brief Calls insert on bound container for each assignment.
 114 ///
 115 template <class Container>
 116 class insert_iterator {
 117 public:
 118     typedef typename Container::value_type      value_type;
 119     typedef typename Container::difference_type difference_type;
 120     typedef typename Container::pointer         pointer;
 121     typedef typename Container::reference       reference;
 122     typedef typename Container::iterator        iterator;
 123 public:
 124     explicit                    insert_iterator (Container& ctr, iterator ip) : m_rCtr (ctr), m_ip (ip) {}
 125     inline insert_iterator&     operator= (typename Container::const_reference v)
 126                                     { m_ip = m_rCtr.insert (m_ip, v); return (*this); }
 127     inline insert_iterator&     operator* (void)  { return (*this); }
 128     inline insert_iterator&     operator++ (void) { ++ m_ip; return (*this); }
 129     inline insert_iterator      operator++ (int)  { insert_iterator prev (*this); ++ m_ip; return (*this); }
 130 protected:
 131     Container&                  m_rCtr;
 132     iterator                    m_ip;
 133 };
 134
 135 /// Returns the insert_iterator for \p ctr.
 136 template <class Container>
 137 inline insert_iterator<Container> inserter (Container& ctr, typename Container::iterator ip)
 138 {
 139     return (insert_iterator<Container> (ctr, ip));
 140 }
 141
 142 //----------------------------------------------------------------------
 143
 144 /// \class back_insert_iterator uiterator.h ustl.h
 145 /// \ingroup IteratorAdaptors
 146 /// \brief Calls push_back on bound container for each assignment.
 147 ///
 148 template <class Container>
 149 class back_insert_iterator {
 150 public:
 151     typedef typename Container::value_type      value_type;
 152     typedef typename Container::difference_type difference_type;
 153     typedef typename Container::pointer         pointer;
 154     typedef typename Container::reference       reference;
 155 public:
 156     explicit                            back_insert_iterator (Container& ctr) : m_rCtr (ctr) {}
 157     inline back_insert_iterator&        operator= (typename Container::const_reference v)
 158                                             { m_rCtr.push_back (v); return (*this); }
 159     inline back_insert_iterator&        operator* (void)  { return (*this); }
 160     inline back_insert_iterator&        operator++ (void) { return (*this); }
 161     inline back_insert_iterator         operator++ (int)  { return (*this); }
 162 protected:
 163     Container&          m_rCtr;
 164 };
 165
 166 /// Returns the back_insert_iterator for \p ctr.
 167 template <class Container>
 168 inline back_insert_iterator<Container> back_inserter (Container& ctr)
 169 {
 170     return (back_insert_iterator<Container> (ctr));
 171 }
 172
 173 //----------------------------------------------------------------------
 174
 175 /// \class index_iterate uiterator.h ustl.h
 176 /// \ingroup IteratorAdaptors
 177 ///
 178 /// \brief Allows iteration through an index container.
 179 ///
 180 /// Converts an iterator into a container of uoff_t indexes to an
 181 /// iterator of iterators into another container.
 182 ///
 183 template <typename RandomAccessIterator, typename IndexIterator>
 184 class index_iterate {
 185 public:
 186     typedef RandomAccessIterator        value_type;
 187     typedef ptrdiff_t                   difference_type;
 188     typedef RandomAccessIterator*       pointer;
 189     typedef RandomAccessIterator        reference;
 190 public:
 191                                 index_iterate (void) : m_Base(), m_i() {}
 192                                 index_iterate (RandomAccessIterator ibase, IndexIterator iindex) : m_Base (ibase), m_i (iindex) {}
 193     inline bool                 operator== (const index_iterate& i) const { return (m_i == i.m_i); }
 194     inline bool                 operator< (const index_iterate& i) const { return (m_i < i.m_i); }
 195     inline bool                 operator== (const RandomAccessIterator& i) const { return (m_Base == i); }
 196     inline bool                 operator< (const RandomAccessIterator& i) const { return (m_Base < i); }
 197     inline IndexIterator        base (void) const { return (m_i); }
 198     inline reference            operator* (void) const { return (advance(m_Base, *m_i)); }
 199     inline pointer              operator-> (void) const { return (&(operator*())); }
 200     inline index_iterate&       operator++ (void) { ++ m_i; return (*this); }
 201     inline index_iterate&       operator-- (void) { -- m_i; return (*this); }
 202     inline index_iterate        operator++ (int) { index_iterate prev (*this); ++ m_i; return (prev); }
 203     inline index_iterate        operator-- (int) { index_iterate prev (*this); -- m_i; return (prev); }
 204     inline index_iterate&       operator+= (size_t n) { m_i += n; return (*this); }
 205     inline index_iterate&       operator-= (size_t n) { m_i -= n; return (*this); }
 206     inline index_iterate        operator+ (size_t n) const { return (index_iterate (m_Base, m_i + n)); }
 207     inline index_iterate        operator- (size_t n) const { return (index_iterate (m_Base, m_i - n)); }
 208     inline reference            operator[] (uoff_t n) const { return (*(*this + n)); }
 209     inline difference_type      operator- (const index_iterate& i) const { return (distance (m_i, i.m_i)); }
 210 private:
 211     RandomAccessIterator        m_Base;
 212     IndexIterator               m_i;
 213 };
 214
 215 /// Returns an index_iterate for \p ibase over \p iindex.
 216 template <typename RandomAccessIterator, typename IndexIterator>
 217 inline index_iterate<RandomAccessIterator, IndexIterator> index_iterator (RandomAccessIterator ibase, IndexIterator iindex)
 218 {
 219     return (index_iterate<RandomAccessIterator, IndexIterator> (ibase, iindex));
 220 }
 221
 222 /// Converts the indexes in \p xc to iterators in \p ic of base \p ibase.
 223 template <typename IndexContainer, typename IteratorContainer>
 224 inline void indexv_to_iteratorv (typename IteratorContainer::value_type ibase, const IndexContainer& xc, IteratorContainer& ic)
 225 {
 226     ic.resize (xc.size());
 227     copy_n (index_iterator (ibase, xc.begin()), xc.size(), ic.begin());
 228 }
 229
 230 //----------------------------------------------------------------------
 231
 232 /// Converts the given const_iterator into an iterator.
 233 ///
 234 template <typename Container>
 235 inline typename Container::iterator unconst (typename Container::const_iterator i, Container&)
 236     { return (const_cast<typename Container::iterator>(i)); }
 237
 238 #ifndef DOXYGEN_SHOULD_SKIP_THIS
 239
 240 #define IBYI(Iter1, Iter2, Ctr1, Ctr2)  \
 241 template <typename Container1, typename Container2>     \
 242 inline typename Container2::Iter2 ibyi (typename Container1::Iter1 idx, Ctr1& ctr1, Ctr2& ctr2) \
 243 {                                                       \
 244     assert (ctr1.size() == ctr2.size());                \
 245     return (ctr2.begin() + (idx - ctr1.begin()));       \
 246 }
 247
 248 IBYI(const_iterator, const_iterator, const Container1, const Container2)
 249 IBYI(iterator, iterator, Container1, Container2)
 250 IBYI(const_iterator, iterator, const Container1, Container2)
 251 IBYI(iterator, const_iterator, Container1, const Container2)
 252
 253 #else // DOXYGEN
 254
 255 #error This declaration is for doxygen only; it is not compiled.
 256
 257 /// Converts a const_iterator in one container into a const_iterator in another container.
 258 template <typename Container1, typename Container2>
 259 inline typename Container2::iterator ibyi (typename Container1::iterator idx, Container1& ctr1, Container2& ctr2) {}
 260
 261 #endif // DOXYGEN
 262
 263 //----------------------------------------------------------------------
 264
 265 } // namespace ustl
 266
 267 #endif
 268