iterator.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_ITERATOR_HPP
#define ADOBE_ITERATOR_HPP
 
#include <adobe/config.hpp>
 
/*
    NOTE (sparent) : GCC 3.1 defines std::distance in <algorithm> instead of <iterator> so we go
    ahead and include both here to work around the issue.
*/
 
#include <algorithm>
#include <cassert>
#include <iterator>
#include <utility>
 
#include <boost/range.hpp>
 
#include <boost/iterator/iterator_facade.hpp>
#include <boost/iterator/iterator_traits.hpp>
 
#include <adobe/empty.hpp>
#include <adobe/typeinfo.hpp>
 
#include <adobe/implementation/swap.hpp>
 
namespace adobe {
 
/**************************************************************************************************/
 
/*
    Just counts the number of outputs; doesn't copy anything. More efficient than a
    back_insert_iterator into a container if all you're interested in is the size of
    the result.
*/
 
/**************************************************************************************************/

class counting_output_iterator {
public:
    typedef std::output_iterator_tag iterator_category;
    typedef counting_output_iterator value_type;
    typedef counting_output_iterator& reference;
    typedef std::size_t size_type;
 
    counting_output_iterator() : count_m(0) {}
 
    counting_output_iterator(const counting_output_iterator& x) : count_m(x.count_m) {}
 
    size_type count() const { return count_m; }
 
    template <typename T>
    reference operator=(const T&) {
        return *this;
    }
 
    reference operator*() { return *this; }
 
    bool operator==(counting_output_iterator const& rhs) const { return this == &rhs; }
 
    counting_output_iterator operator++(int) {
        ++count_m;
        return *this;
    }
 
    reference operator++() {
        ++count_m;
        return *this;
    }
 
private:
    std::size_t count_m;
};
 
/**************************************************************************************************/
 
/*
    top iterator            bottom iterator
 
    random access           random access           bidirectional
    bidirectional           random access           bidirectional
    forward                 random access           forward
    input                   random access           forward
    output                  random access           ???
 
    random access           bidirectional           bidirectional
    bidirectional           bidirectional           bidirectional
    forward                 bidirectional           forward
    input                   bidirectional           forward
    output                  bidirectional           ???
 
    random access           forward                 forward
    bidirectional           forward                 forward
    forward                 forward                 forward
    input                   forward                 forward
    output                  forward                 ???
 
    random access           input                   input
    bidirectional           input                   input
    forward                 input                   input
    input                   input                   input
    output                  input                   ???
 
    random access           output                  output
    bidirectional           output                  output
    forward                 output                  output
    input                   output                  output
    output                  output                  ???
 
 
    if (catgory(bottom) == bidirectional && catgory(top) == bidirectional) return bidirectional
    else if (catgory(bottom) == forward) return forward
    else return category(bottom)
*/
 
template <typename I> // I models an InputIterator where value_type(I) models Range
class segmented_iterator
    : public boost::iterator_facade<
          segmented_iterator<I>,
          typename boost::range_value<typename boost::iterator_value<I>::type>::type,
          std::bidirectional_iterator_tag,
          typename boost::iterator_reference<
              typename boost::range_iterator<typename boost::iterator_value<I>::type>::type>::type,
          typename boost::iterator_difference<typename boost::range_iterator<
              typename boost::iterator_value<I>::type>::type>::type> {
public:
    segmented_iterator() : bucket_m(), end_m(), current_m() {}
    segmented_iterator(I first, I last) : bucket_m(first), end_m(last) {
        while (bucket_m != end_m && boost::empty(*bucket_m)) {
            ++bucket_m;
        }
        if (bucket_m != end_m)
            current_m = boost::begin(*bucket_m);
    }
 
    segmented_iterator(const segmented_iterator& x)
        : bucket_m(x.bucket_m), end_m(x.end_m), current_m(x.current_m) {}
 
    segmented_iterator& operator=(segmented_iterator x) {
        swap(*this, x);
        return *this;
    }
 
    friend inline void swap(segmented_iterator& x, segmented_iterator& y) {
        swap(x.bucket_m, y.bucket_m);
        swap(x.end_m, y.end_m);
        swap(x.curent_m, y.curent_m);
    }
 
private:
    typedef typename boost::iterator_reference<
        typename boost::range_iterator<typename boost::iterator_value<I>::type>::type>::type
        reference_t;
    typedef I top_iterator_t;
    typedef typename boost::range_iterator<typename boost::iterator_value<I>::type>::type
        bottom_iterator_t;
 
    top_iterator_t bucket_m;
    top_iterator_t end_m;
    bottom_iterator_t current_m;
 
    // boost iterator_facade access functions
 
    friend class boost::iterator_core_access;
 
    reference_t dereference() const { return *current_m; }
 
    bool equal(const segmented_iterator& x) const {
        /*
        If the end of the top sequences are the same and we are in the same bucket then if we are
        at the very end or we are at the same local position then we are equal.
        */
 
        return end_m == x.end_m && bucket_m == x.bucket_m &&
               (bucket_m == end_m || current_m == x.current_m);
    }
 
    void increment() {
        ++current_m;
 
        while (current_m == boost::end(*bucket_m)) {
            ++bucket_m;
            if (bucket_m == end_m)
                break;
            current_m = boost::begin(*bucket_m);
        }
    }
    void decrement() {
        while (bucket_m == end_m || current_m == boost::begin(*bucket_m)) {
            --bucket_m;
            current_m = boost::end(*bucket_m);
        }
 
        --current_m;
    }
};
 
 
template <typename R> // R models ConvertibleToRange
inline boost::iterator_range<segmented_iterator<typename boost::range_iterator<R>::type>>
make_segmented_range(R& r) {
    typedef segmented_iterator<typename boost::range_iterator<R>::type> iterator;
 
    return boost::make_iterator_range(iterator(boost::begin(r), boost::end(r)),
                                      iterator(boost::end(r), boost::end(r)));
}
 
 
template <typename R> // R models ConvertibleToRange
inline segmented_iterator<typename boost::range_iterator<R>::type> make_segmented_iterator(R& r) {
    typedef segmented_iterator<typename boost::range_iterator<R>::type> iterator;
 
    return iterator(boost::begin(r), boost::end(r));
}
 
/**************************************************************************************************/
 
/*
    NOTE (sparent) : The asserts are comment only because we don't require that our function
    object be equality comparable.
*/
 
 
template <typename F,                 // F models Unary Function object
          typename T,                 // T models Regular Type
          typename R = T&,            // R models Reference Type of T
          typename I = std::size_t,   // I models Unsigned Integer
          typename D = std::ptrdiff_t // D models Signed Integer
          >
// I is convertible to argument[1] of F
// result of F is R
// D is the difference type of I (must be signed)
class index_iterator : public boost::iterator_facade<index_iterator<F, T, R, I, D>, T,
                                                     std::random_access_iterator_tag, R, D> {
public:
    index_iterator() : index_m(0) {}
    index_iterator(F f, I i) : dereference_m(f), index_m(i) {}
 
    index_iterator(const index_iterator& x) : dereference_m(x.dereference_m), index_m(x.index_m) {}
 
    index_iterator& operator=(const index_iterator& x) {
        index_iterator temp(x);
        swap(temp, *this);
        return *this;
    }
 
    friend inline void swap(index_iterator& x, index_iterator& y) {
        swap(x.dereference_m, y.dereference_m);
        swap(x.index_m, y.index_m);
    }
 
    I base() const { return index_m; }
 
private:
    F dereference_m;
    I index_m;
 
    // boost iterator_facade access functions
 
    friend class boost::iterator_core_access;
 
    R dereference() const { return dereference_m(this->index_m); }
 
    bool equal(const index_iterator& x) const {
        // assert(dereference_m == x.dereference_m);
 
        return index_m == x.index_m;
    }
 
    void increment() { ++index_m; }
    void decrement() { --index_m; }
    void advance(D x) { index_m += x; }
 
    D distance_to(const index_iterator& x) const {
        // assert(dereference_m == x.dereference_m);
 
        /*
            REVISIT (sparent) : There isn't a difference type for unsigned integers - because an
            index is usually denoted by an unsigned type, but a difference is signed we should
            have some mechanism to peform the subtraction and guarantee a valid result. We don't
            currently have said mechanism, so we simply cast from (possibly)unsigned to signed.
 
            This limits the range within which we can perform this operation, but practically it
            shouldn't be an issue.
        */
        return D(x.index_m) - D(index_m);
    }
};

//                  STEP ITERATOR ADAPTOR
 
 
template <typename DERIVED, // type of the derived class
          typename IT,      // Models Iterator
          typename S_FN>
// A policy object that can compute the distance between two iterators of type IT
// and can advance an iterator of type IT a given number of IT's units
class step_iterator_adaptor
    : public boost::iterator_adaptor<DERIVED, IT, boost::use_default, boost::use_default,
                                     boost::use_default, typename S_FN::difference_type> {
public:
    typedef boost::iterator_adaptor<DERIVED, IT, boost::use_default, boost::use_default,
                                    boost::use_default, typename S_FN::difference_type>
        parent_type;
    typedef typename std::iterator_traits<IT>::difference_type base_difference_type;
    typedef typename S_FN::difference_type difference_type;
    typedef typename std::iterator_traits<IT>::reference reference;
 
    step_iterator_adaptor() {}
    step_iterator_adaptor(const IT& it, S_FN step_fn = S_FN())
        : parent_type(it), _step_fn(step_fn) {}
 
    difference_type step() const { return _step_fn.step(); }
 
protected:
    S_FN _step_fn;
 
private:
    friend class boost::iterator_core_access;
 
    void increment() { _step_fn.advance(this->base_reference(), 1); }
    void decrement() { _step_fn.advance(this->base_reference(), -1); }
    void advance(base_difference_type d) { _step_fn.advance(this->base_reference(), d); }
    difference_type distance_to(const step_iterator_adaptor& it) const {
        return _step_fn.difference(this->base_reference(), it.base_reference());
    }
};
 
// although boost::iterator_adaptor defines these, the default implementation computes distance and
// compares for zero.
// it is often faster to just apply the relation operator to the base
template <typename D, typename IT, typename S_FN>
inline bool operator>(const step_iterator_adaptor<D, IT, S_FN>& p1,
                      const step_iterator_adaptor<D, IT, S_FN>& p2) {
    return p1.step() > 0 ? p1.base() > p2.base() : p1.base() < p2.base();
}
 
 
template <typename D, typename IT, typename S_FN>
inline bool operator<(const step_iterator_adaptor<D, IT, S_FN>& p1,
                      const step_iterator_adaptor<D, IT, S_FN>& p2) {
    return p1.step() > 0 ? p1.base() < p2.base() : p1.base() > p2.base();
}
 
template <typename D, typename IT, typename S_FN>
inline bool operator>=(const step_iterator_adaptor<D, IT, S_FN>& p1,
                       const step_iterator_adaptor<D, IT, S_FN>& p2) {
    return p1.step() > 0 ? p1.base() >= p2.base() : p1.base() <= p2.base();
}
 
 
template <typename D, typename IT, typename S_FN>
inline bool operator<=(const step_iterator_adaptor<D, IT, S_FN>& p1,
                       const step_iterator_adaptor<D, IT, S_FN>& p2) {
    return p1.step() > 0 ? p1.base() <= p2.base() : p1.base() >= p2.base();
}
 
 
template <typename D, typename IT, typename S_FN>
inline bool operator==(const step_iterator_adaptor<D, IT, S_FN>& p1,
                       const step_iterator_adaptor<D, IT, S_FN>& p2) {
    return p1.base() == p2.base();
}
 
 
template <typename D, typename IT, typename S_FN>
inline bool operator!=(const step_iterator_adaptor<D, IT, S_FN>& p1,
                       const step_iterator_adaptor<D, IT, S_FN>& p2) {
    return p1.base() != p2.base();
}
 
/**************************************************************************************************/

struct null_output_iterator_t {
    typedef std::output_iterator_tag iterator_category;
    typedef null_output_iterator_t value_type;
    typedef std::ptrdiff_t difference_type;
    typedef value_type* pointer;
    typedef value_type& reference;
 
    null_output_iterator_t& operator++(int) { return *this; }
    null_output_iterator_t& operator++() { return *this; }
    reference operator*() { return *this; }
 
    template <typename T>
    null_output_iterator_t& operator=(const T&) {
        return *this;
    }
};

 
/**************************************************************************************************/
 
} // namespace adobe
 
/**************************************************************************************************/
 
#endif
 
/**************************************************************************************************/