circular_queue.hpp

Go to the documentation of this file.

/*
    Copyright 2013 Adobe
    Distributed under the Boost Software License, Version 1.0.
    (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
*/
/**************************************************************************************************/
 
#ifndef ADOBE_CIRCULAR_QUEUE_HPP
#define ADOBE_CIRCULAR_QUEUE_HPP
 
/**************************************************************************************************/
 
#include <adobe/config.hpp>
 
#include <adobe/algorithm/equal.hpp>
#include <adobe/iterator.hpp>
 
#include <boost/operators.hpp>
 
#include <cassert>
#include <vector>
 
/**************************************************************************************************/
 
namespace adobe {
 


















 
 
/**************************************************************************************************/
 
#if 1 // REVISIT (fbrereto) : Possible compiler optimization?
#define ADOBE_NOTHROW throw()
#else
#define ADOBE_NOTHROW
#endif
 
/**************************************************************************************************/
 
template <typename T>
class circular_queue;
 
template <typename T>
bool operator==(const circular_queue<T>& x, const circular_queue<T>& y);
 
template <typename T>
void swap(circular_queue<T>&, circular_queue<T>&);
 
/**************************************************************************************************/

template <typename T>
class circular_queue : boost::equality_comparable<circular_queue<T>> {
public:
    typedef T value_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef std::size_t size_type;
 
    circular_queue(std::size_t capacity = 0);
 
#if !defined(ADOBE_NO_DOCUMENTATION)
    circular_queue(const circular_queue& rhs);
 
    circular_queue& operator=(circular_queue rhs);
#endif // !defined(ADOBE_NO_DOCUMENTATION)
 
    size_type size() const ADOBE_NOTHROW;
    size_type max_size() const ADOBE_NOTHROW { return container_m.size(); }
    size_type capacity() const ADOBE_NOTHROW { return container_m.size(); }
 
    bool empty() const ADOBE_NOTHROW { return is_empty_m; }
    bool full() const ADOBE_NOTHROW { return !is_empty_m && begin_m == end_m; }
 
    void clear() ADOBE_NOTHROW {
        begin_m = end_m;
        is_empty_m = true;
    }
 
    reference front() ADOBE_NOTHROW;
    const_reference front() const ADOBE_NOTHROW;
 
    void push_back(T x);
 
    void pop_front() ADOBE_NOTHROW;
 
    void putback() ADOBE_NOTHROW;
 
#if !defined(ADOBE_NO_DOCUMENTATION)
private:
    friend inline void swap(circular_queue& x, circular_queue& y) {
        swap(x.container_m, y.container_m);
        std::swap(x.begin_m, y.begin_m);
        std::swap(x.end_m, y.end_m);
        swap(x.is_empty_m, y.is_empty_m);
    }
 
    friend bool operator==<>(const circular_queue& x, const circular_queue& y);
 
    typedef typename std::vector<value_type> container_t;
    typedef typename container_t::iterator iterator;
    typedef typename container_t::const_iterator const_iterator;
 
    /* WARNING (sparent) : Order of members is important to initialization */
    container_t container_m;
    iterator begin_m;
    iterator end_m;
    bool is_empty_m;
    /* WARNING (sparent) : Order of members is important to initialization */
 
    // Note that these ranges assume non-empty.
 
    typedef std::pair<const_iterator, const_iterator> const_range;
 
    const_range first_range() const {
        return const_range(begin_m,
                           begin_m < end_m ? const_iterator(end_m) : boost::end(container_m));
    }
 
    const_range second_range() const {
        return const_range(begin_m < end_m ? const_iterator(end_m) : boost::begin(container_m),
                           end_m);
    }
 
#endif // !defined(ADOBE_NO_DOCUMENTATION)
};
 
/**************************************************************************************************/
 
template <typename T>
circular_queue<T>::circular_queue(std::size_t capacity)
    : container_m(capacity), begin_m(boost::begin(container_m)), end_m(boost::begin(container_m)),
      is_empty_m(true) {}
 
#if !defined(ADOBE_NO_DOCUMENTATION)
 
/**************************************************************************************************/
 
template <typename T>
circular_queue<T>::circular_queue(const circular_queue& rhs)
    : container_m(rhs.capacity()), begin_m(boost::begin(container_m)),
      end_m(boost::begin(container_m)), is_empty_m(rhs.is_empty_m) {
    if (is_empty_m)
        return;
 
    end_m = copy(rhs.first_range(), end_m);
    end_m = copy(rhs.second_range(), end_m);
}
 
/**************************************************************************************************/
 
template <typename T>
inline circular_queue<T>& circular_queue<T>::operator=(circular_queue rhs) {
    swap(*this, rhs);
    return *this;
}
 
#endif // !defined(ADOBE_NO_DOCUMENTATION)
/**************************************************************************************************/
 
template <typename T>
typename circular_queue<T>::reference circular_queue<T>::front() ADOBE_NOTHROW {
    assert(!empty());
    return *begin_m;
}
 
/**************************************************************************************************/
 
template <typename T>
typename circular_queue<T>::const_reference circular_queue<T>::front() const ADOBE_NOTHROW {
    assert(!empty());
    return *begin_m;
}
 
/**************************************************************************************************/
 
template <typename T>
void circular_queue<T>::push_back(T x) {
    *end_m = std::move(x);
 
    bool was_full(full());
 
    if (++end_m == boost::end(container_m))
        end_m = boost::begin(container_m);
    if (was_full)
        begin_m = end_m;
 
    is_empty_m = false;
}
 
/**************************************************************************************************/
 
template <typename T>
void circular_queue<T>::pop_front() ADOBE_NOTHROW {
    assert(!empty());
    if (++begin_m == boost::end(container_m))
        begin_m = boost::begin(container_m);
    is_empty_m = begin_m == end_m;
}
 
/**************************************************************************************************/
 
template <typename T>
void circular_queue<T>::putback() ADOBE_NOTHROW {
    assert(!full());
    if (begin_m == boost::begin(container_m))
        begin_m = boost::end(container_m);
    --begin_m;
    is_empty_m = false;
}
 
/**************************************************************************************************/
 
template <typename T>
typename circular_queue<T>::size_type circular_queue<T>::size() const ADOBE_NOTHROW {
    if (begin_m < end_m)
        return std::distance(begin_m, end_m);
 
    return is_empty_m ? 0 : capacity() - std::distance(end_m, begin_m);
}
 
/**************************************************************************************************/
 
template <typename T>
bool operator==(const circular_queue<T>& x, const circular_queue<T>& y) {
    /*
        REVISIT (sparent) : I'm trying to move the code towards equality of containers to mean "the
        size is the same and all the parts are the same." By making the segmented iterators part of
        a public begin, end interface this would simply be a generic. "equal_containers()" function.
    */
    typedef typename circular_queue<T>::const_range const_range;
 
    if (x.size() != y.size())
        return false;
 
    const_range sequence1[] = {x.first_range(), x.second_range()};
    const_range sequence2[] = {y.first_range(), y.second_range()};
 
    return equal(make_segmented_range(sequence1), make_segmented_iterator(sequence2));
}
 
/**************************************************************************************************/
 
#undef ADOBE_NOTHROW
 
/**************************************************************************************************/
 
} // namespace adobe
 
/**************************************************************************************************/
 
#endif // ADOBE_CIRCULAR_QUEUE_HPP
 
/**************************************************************************************************/