Source/Contrib/ComplexSceneManager/External/boost/circular_buffer/details.hpp

   1 // Helper classes and functions for the circular buffer.
   2
   3 // Copyright (c) 2003-2008 Jan Gaspar
   4
   5 // Use, modification, and distribution is subject to the Boost Software
   6 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #if !defined(BOOST_CIRCULAR_BUFFER_DETAILS_HPP)
  10 #define BOOST_CIRCULAR_BUFFER_DETAILS_HPP
  11
  12 #if defined(_MSC_VER) && _MSC_VER >= 1200
  13     #pragma once
  14 #endif
  15
  16 #include <boost/iterator.hpp>
  17 #include <boost/throw_exception.hpp>
  18 #include <boost/detail/no_exceptions_support.hpp>
  19 #include <iterator>
  20
  21 namespace boost {
  22
  23 namespace cb_details {
  24
  25 template <class Traits> struct nonconst_traits;
  26
  27 template<class ForwardIterator, class Diff, class T, class Alloc>
  28 void uninitialized_fill_n_with_alloc(
  29     ForwardIterator first, Diff n, const T& item, Alloc& alloc);
  30
  31 template<class InputIterator, class ForwardIterator, class Alloc>
  32 ForwardIterator uninitialized_copy_with_alloc(
  33     InputIterator first, InputIterator last, ForwardIterator dest, Alloc& alloc);
  34
  35 /*!
  36     \struct const_traits
  37     \brief Defines the data types for a const iterator.
  38 */
  39 template <class Traits>
  40 struct const_traits {
  41     // Basic types
  42     typedef typename Traits::value_type value_type;
  43     typedef typename Traits::const_pointer pointer;
  44     typedef typename Traits::const_reference reference;
  45     typedef typename Traits::size_type size_type;
  46     typedef typename Traits::difference_type difference_type;
  47
  48     // Non-const traits
  49     typedef nonconst_traits<Traits> nonconst_self;
  50 };
  51
  52 /*!
  53     \struct nonconst_traits
  54     \brief Defines the data types for a non-const iterator.
  55 */
  56 template <class Traits>
  57 struct nonconst_traits {
  58     // Basic types
  59     typedef typename Traits::value_type value_type;
  60     typedef typename Traits::pointer pointer;
  61     typedef typename Traits::reference reference;
  62     typedef typename Traits::size_type size_type;
  63     typedef typename Traits::difference_type difference_type;
  64
  65     // Non-const traits
  66     typedef nonconst_traits<Traits> nonconst_self;
  67 };
  68
  69 /*!
  70     \struct iterator_wrapper
  71     \brief Helper iterator dereference wrapper.
  72 */
  73 template <class Iterator>
  74 struct iterator_wrapper {
  75     mutable Iterator m_it;
  76     explicit iterator_wrapper(Iterator it) : m_it(it) {}
  77     Iterator operator () () const { return m_it++; }
  78 private:
  79     iterator_wrapper<Iterator>& operator = (const iterator_wrapper<Iterator>&); // do not generate
  80 };
  81
  82 /*!
  83     \struct item_wrapper
  84     \brief Helper item dereference wrapper.
  85 */
  86 template <class Pointer, class Value>
  87 struct item_wrapper {
  88     Value m_item;
  89     explicit item_wrapper(Value item) : m_item(item) {}
  90     Pointer operator () () const { return &m_item; }
  91 private:
  92     item_wrapper<Pointer, Value>& operator = (const item_wrapper<Pointer, Value>&); // do not generate
  93 };
  94
  95 /*!
  96     \struct assign_n
  97     \brief Helper functor for assigning n items.
  98 */
  99 template <class Value, class Alloc>
 100 struct assign_n {
 101     typedef typename Alloc::size_type size_type;
 102     size_type m_n;
 103     Value m_item;
 104     Alloc& m_alloc;
 105     assign_n(size_type n, Value item, Alloc& alloc) : m_n(n), m_item(item), m_alloc(alloc) {}
 106     template <class Pointer>
 107     void operator () (Pointer p) const {
 108         uninitialized_fill_n_with_alloc(p, m_n, m_item, m_alloc);
 109     }
 110 private:
 111     assign_n<Value, Alloc>& operator = (const assign_n<Value, Alloc>&); // do not generate
 112 };
 113
 114 /*!
 115     \struct assign_range
 116     \brief Helper functor for assigning range of items.
 117 */
 118 template <class Iterator, class Alloc>
 119 struct assign_range {
 120     const Iterator& m_first;
 121     const Iterator& m_last;
 122     Alloc& m_alloc;
 123     assign_range(const Iterator& first, const Iterator& last, Alloc& alloc)
 124     : m_first(first), m_last(last), m_alloc(alloc) {}
 125     template <class Pointer>
 126     void operator () (Pointer p) const {
 127         uninitialized_copy_with_alloc(m_first, m_last, p, m_alloc);
 128     }
 129 private:
 130     assign_range<Iterator, Alloc>& operator = (const assign_range<Iterator, Alloc>&); // do not generate
 131 };
 132
 133 /*!
 134     \class capacity_control
 135     \brief Capacity controller of the space optimized circular buffer.
 136 */
 137 template <class Size>
 138 class capacity_control {
 139
 140     //! The capacity of the space optimized circular buffer.
 141     Size m_capacity;
 142
 143     //! The lowest guaranteed capacity of the adapted circular buffer.
 144     Size m_min_capacity;
 145
 146 public:
 147
 148     //! Constructor.
 149     capacity_control(Size capacity, Size min_capacity = 0)
 150     : m_capacity(capacity), m_min_capacity(min_capacity) {
 151         BOOST_CB_ASSERT(capacity >= min_capacity); // check for capacity lower than min_capacity
 152     }
 153
 154     // Default copy constructor.
 155
 156     // Default assign operator.
 157
 158     //! Get the capacity of the space optimized circular buffer.
 159     Size capacity() const { return m_capacity; }
 160
 161     //! Get the minimal capacity of the space optimized circular buffer.
 162     Size min_capacity() const { return m_min_capacity; }
 163
 164     //! Size operator - returns the capacity of the space optimized circular buffer.
 165     operator Size() const { return m_capacity; }
 166 };
 167
 168 /*!
 169     \struct iterator
 170     \brief Random access iterator for the circular buffer.
 171     \param Buff The type of the underlying circular buffer.
 172     \param Traits Basic iterator types.
 173     \note This iterator is not circular. It was designed
 174           for iterating from begin() to end() of the circular buffer.
 175 */
 176 template <class Buff, class Traits>
 177 struct iterator :
 178     public boost::iterator<
 179     std::random_access_iterator_tag,
 180     typename Traits::value_type,
 181     typename Traits::difference_type,
 182     typename Traits::pointer,
 183     typename Traits::reference>
 184 #if BOOST_CB_ENABLE_DEBUG
 185     , public debug_iterator_base
 186 #endif // #if BOOST_CB_ENABLE_DEBUG
 187 {
 188 // Helper types
 189
 190     //! Base iterator.
 191     typedef boost::iterator<
 192         std::random_access_iterator_tag,
 193         typename Traits::value_type,
 194         typename Traits::difference_type,
 195         typename Traits::pointer,
 196         typename Traits::reference> base_iterator;
 197
 198     //! Non-const iterator.
 199     typedef iterator<Buff, typename Traits::nonconst_self> nonconst_self;
 200
 201 // Basic types
 202
 203     //! The type of the elements stored in the circular buffer.
 204     typedef typename base_iterator::value_type value_type;
 205
 206     //! Pointer to the element.
 207     typedef typename base_iterator::pointer pointer;
 208
 209     //! Reference to the element.
 210     typedef typename base_iterator::reference reference;
 211
 212     //! Size type.
 213     typedef typename Traits::size_type size_type;
 214
 215     //! Difference type.
 216     typedef typename base_iterator::difference_type difference_type;
 217
 218 // Member variables
 219
 220     //! The circular buffer where the iterator points to.
 221     const Buff* m_buff;
 222
 223     //! An internal iterator.
 224     pointer m_it;
 225
 226 // Construction & assignment
 227
 228     // Default copy constructor.
 229
 230     //! Default constructor.
 231     iterator() : m_buff(0), m_it(0) {}
 232
 233 #if BOOST_CB_ENABLE_DEBUG
 234
 235     //! Copy constructor (used for converting from a non-const to a const iterator).
 236     iterator(const nonconst_self& it) : debug_iterator_base(it), m_buff(it.m_buff), m_it(it.m_it) {}
 237
 238     //! Internal constructor.
 239     /*!
 240         \note This constructor is not intended to be used directly by the user.
 241     */
 242     iterator(const Buff* cb, const pointer p) : debug_iterator_base(cb), m_buff(cb), m_it(p) {}
 243
 244 #else
 245
 246     iterator(const nonconst_self& it) : m_buff(it.m_buff), m_it(it.m_it) {}
 247
 248     iterator(const Buff* cb, const pointer p) : m_buff(cb), m_it(p) {}
 249
 250 #endif // #if BOOST_CB_ENABLE_DEBUG
 251
 252     //! Assign operator.
 253     iterator& operator = (const iterator& it) {
 254         if (this == &it)
 255             return *this;
 256 #if BOOST_CB_ENABLE_DEBUG
 257         debug_iterator_base::operator =(it);
 258 #endif // #if BOOST_CB_ENABLE_DEBUG
 259         m_buff = it.m_buff;
 260         m_it = it.m_it;
 261         return *this;
 262     }
 263
 264 // Random access iterator methods
 265
 266     //! Dereferencing operator.
 267     reference operator * () const {
 268         BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
 269         BOOST_CB_ASSERT(m_it != 0);        // check for iterator pointing to end()
 270         return *m_it;
 271     }
 272
 273     //! Dereferencing operator.
 274     pointer operator -> () const { return &(operator*()); }
 275
 276     //! Difference operator.
 277     template <class Traits0>
 278     difference_type operator - (const iterator<Buff, Traits0>& it) const {
 279         BOOST_CB_ASSERT(is_valid(m_buff));    // check for uninitialized or invalidated iterator
 280         BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator
 281         return linearize_pointer(*this) - linearize_pointer(it);
 282     }
 283
 284     //! Increment operator (prefix).
 285     iterator& operator ++ () {
 286         BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
 287         BOOST_CB_ASSERT(m_it != 0);        // check for iterator pointing to end()
 288         m_buff->increment(m_it);
 289         if (m_it == m_buff->m_last)
 290             m_it = 0;
 291         return *this;
 292     }
 293
 294     //! Increment operator (postfix).
 295     iterator operator ++ (int) {
 296         iterator<Buff, Traits> tmp = *this;
 297         ++*this;
 298         return tmp;
 299     }
 300
 301     //! Decrement operator (prefix).
 302     iterator& operator -- () {
 303         BOOST_CB_ASSERT(is_valid(m_buff));        // check for uninitialized or invalidated iterator
 304         BOOST_CB_ASSERT(m_it != m_buff->m_first); // check for iterator pointing to begin()
 305         if (m_it == 0)
 306             m_it = m_buff->m_last;
 307         m_buff->decrement(m_it);
 308         return *this;
 309     }
 310
 311     //! Decrement operator (postfix).
 312     iterator operator -- (int) {
 313         iterator<Buff, Traits> tmp = *this;
 314         --*this;
 315         return tmp;
 316     }
 317
 318     //! Iterator addition.
 319     iterator& operator += (difference_type n) {
 320         BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
 321         if (n > 0) {
 322             BOOST_CB_ASSERT(m_buff->end() - *this >= n); // check for too large n
 323             m_it = m_buff->add(m_it, n);
 324             if (m_it == m_buff->m_last)
 325                 m_it = 0;
 326         } else if (n < 0) {
 327             *this -= -n;
 328         }
 329         return *this;
 330     }
 331
 332     //! Iterator addition.
 333     iterator operator + (difference_type n) const { return iterator<Buff, Traits>(*this) += n; }
 334
 335     //! Iterator subtraction.
 336     iterator& operator -= (difference_type n) {
 337         BOOST_CB_ASSERT(is_valid(m_buff)); // check for uninitialized or invalidated iterator
 338         if (n > 0) {
 339             BOOST_CB_ASSERT(*this - m_buff->begin() >= n); // check for too large n
 340             m_it = m_buff->sub(m_it == 0 ? m_buff->m_last : m_it, n);
 341         } else if (n < 0) {
 342             *this += -n;
 343         }
 344         return *this;
 345     }
 346
 347     //! Iterator subtraction.
 348     iterator operator - (difference_type n) const { return iterator<Buff, Traits>(*this) -= n; }
 349
 350     //! Element access operator.
 351     reference operator [] (difference_type n) const { return *(*this + n); }
 352
 353 // Equality & comparison
 354
 355     //! Equality.
 356     template <class Traits0>
 357     bool operator == (const iterator<Buff, Traits0>& it) const {
 358         BOOST_CB_ASSERT(is_valid(m_buff));    // check for uninitialized or invalidated iterator
 359         BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator
 360         return m_it == it.m_it;
 361     }
 362
 363     //! Inequality.
 364     template <class Traits0>
 365     bool operator != (const iterator<Buff, Traits0>& it) const {
 366         BOOST_CB_ASSERT(is_valid(m_buff));    // check for uninitialized or invalidated iterator
 367         BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator
 368         return m_it != it.m_it;
 369     }
 370
 371     //! Less.
 372     template <class Traits0>
 373     bool operator < (const iterator<Buff, Traits0>& it) const {
 374         BOOST_CB_ASSERT(is_valid(m_buff));    // check for uninitialized or invalidated iterator
 375         BOOST_CB_ASSERT(it.is_valid(m_buff)); // check for uninitialized or invalidated iterator
 376         return linearize_pointer(*this) < linearize_pointer(it);
 377     }
 378
 379     //! Greater.
 380     template <class Traits0>
 381     bool operator > (const iterator<Buff, Traits0>& it) const { return it < *this; }
 382
 383     //! Less or equal.
 384     template <class Traits0>
 385     bool operator <= (const iterator<Buff, Traits0>& it) const { return !(it < *this); }
 386
 387     //! Greater or equal.
 388     template <class Traits0>
 389     bool operator >= (const iterator<Buff, Traits0>& it) const { return !(*this < it); }
 390
 391 // Helpers
 392
 393     //! Get a pointer which would point to the same element as the iterator in case the circular buffer is linearized.
 394     template <class Traits0>
 395     typename Traits0::pointer linearize_pointer(const iterator<Buff, Traits0>& it) const {
 396         return it.m_it == 0 ? m_buff->m_buff + m_buff->size() :
 397             (it.m_it < m_buff->m_first ? it.m_it + (m_buff->m_end - m_buff->m_first)
 398                 : m_buff->m_buff + (it.m_it - m_buff->m_first));
 399     }
 400 };
 401
 402 //! Iterator addition.
 403 template <class Buff, class Traits>
 404 inline iterator<Buff, Traits>
 405 operator + (typename Traits::difference_type n, const iterator<Buff, Traits>& it) {
 406     return it + n;
 407 }
 408
 409 #if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) && !defined(BOOST_MSVC_STD_ITERATOR)
 410
 411 //! Iterator category.
 412 template <class Buff, class Traits>
 413 inline std::random_access_iterator_tag iterator_category(const iterator<Buff, Traits>&) {
 414     return std::random_access_iterator_tag();
 415 }
 416
 417 //! The type of the elements stored in the circular buffer.
 418 template <class Buff, class Traits>
 419 inline typename Traits::value_type* value_type(const iterator<Buff, Traits>&) { return 0; }
 420
 421 //! Distance type.
 422 template <class Buff, class Traits>
 423 inline typename Traits::difference_type* distance_type(const iterator<Buff, Traits>&) { return 0; }
 424
 425 #endif // #if defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) && !defined(BOOST_MSVC_STD_ITERATOR)
 426
 427 /*!
 428     \fn ForwardIterator uninitialized_copy_with_alloc(InputIterator first, InputIterator last, ForwardIterator dest,
 429             Alloc& alloc)
 430     \brief Equivalent of <code>std::uninitialized_copy</code> with allocator.
 431 */
 432 template<class InputIterator, class ForwardIterator, class Alloc>
 433 inline ForwardIterator uninitialized_copy_with_alloc(InputIterator first, InputIterator last, ForwardIterator dest,
 434     Alloc& alloc) {
 435     ForwardIterator next = dest;
 436     BOOST_TRY {
 437         for (; first != last; ++first, ++dest)
 438             alloc.construct(dest, *first);
 439     } BOOST_CATCH(...) {
 440         for (; next != dest; ++next)
 441             alloc.destroy(next);
 442         BOOST_RETHROW
 443     }
 444     BOOST_CATCH_END
 445     return dest;
 446 }
 447
 448 /*!
 449     \fn void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, const T& item, Alloc& alloc)
 450     \brief Equivalent of <code>std::uninitialized_fill_n</code> with allocator.
 451 */
 452 template<class ForwardIterator, class Diff, class T, class Alloc>
 453 inline void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, const T& item, Alloc& alloc) {
 454     ForwardIterator next = first;
 455     BOOST_TRY {
 456         for (; n > 0; ++first, --n)
 457             alloc.construct(first, item);
 458     } BOOST_CATCH(...) {
 459         for (; next != first; ++next)
 460             alloc.destroy(next);
 461         BOOST_RETHROW
 462     }
 463     BOOST_CATCH_END
 464 }
 465
 466 } // namespace cb_details
 467
 468 } // namespace boost
 469
 470 #endif // #if !defined(BOOST_CIRCULAR_BUFFER_DETAILS_HPP)