reduce.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

/*
    Copyright 2005-2007 Adobe Systems Incorporated
   
    Use, modification and distribution are subject to 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).

    See http://opensource.adobe.com/gil for most recent version including documentation.
*/
/*************************************************************************************************/

#ifndef GIL_REDUCE_HPP
#define GIL_REDUCE_HPP

#include <boost/mpl/insert_range.hpp>
#include <boost/mpl/range_c.hpp>
#include <boost/mpl/vector_c.hpp>
#include <boost/mpl/back.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/long.hpp>
#include <boost/mpl/logical.hpp>
#include <boost/mpl/transform.hpp>
#include <boost/mpl/insert.hpp>
#include <boost/mpl/transform.hpp>

#include "../../metafunctions.hpp"
#include "../../typedefs.hpp"
#include "dynamic_at_c.hpp"

////////////////////////////////////////////////////////////////////////////////////////
/// \file               
/// \brief Constructs for static-to-dynamic integer convesion
/// \author Lubomir Bourdev and Hailin Jin \n
///         Adobe Systems Incorporated
/// \date 2005-2007 \n Last updated on May 4, 2006
///
////////////////////////////////////////////////////////////////////////////////////////


#ifdef GIL_REDUCE_CODE_BLOAT


// Max number of cases in the cross-expension of binary operation for it to be reduced as unary
#define GIL_BINARY_REDUCE_LIMIT 226

namespace boost { namespace mpl {

///////////////////////////////////////////////////////
/// Mapping vector - represents the mapping of one type vector to another
///  It is not a full-blown MPL Random Access Type sequence; just has at_c and size implemented
///
/// SrcTypes, DstTypes: MPL Random Access Type Sequences
///
/// Implements size and at_c to behave as if this is an MPL vector of integers
///////////////////////////////////////////////////////

template <typename SrcTypes, typename DstTypes>
struct mapping_vector {};

template <typename SrcTypes, typename DstTypes, long K>
struct at_c<mapping_vector<SrcTypes,DstTypes>, K> {
    static const std::size_t value=size<DstTypes>::value - order<DstTypes, typename at_c<SrcTypes,K>::type>::type::value +1;
    typedef size_t<value> type;
};

template <typename SrcTypes, typename DstTypes>
struct size<mapping_vector<SrcTypes,DstTypes> > {
    typedef typename size<SrcTypes>::type type;
    static const std::size_t value=type::value;
};

///////////////////////////////////////////////////////
/// copy_to_vector - copies a sequence (mpl::set) to vector.
///
/// Temporary solution because I couldn't get mpl::copy to do this.
/// This is what I tried:
/// mpl::copy<SET, mpl::back_inserter<mpl::vector<> > >::type;
/// It works when SET is mpl::vector, but not when SET is mpl::set...
///////////////////////////////////////////////////////

namespace detail {
    template <typename SFirst, std::size_t NLeft>
    struct copy_to_vector_impl {
    private:
        typedef typename deref<SFirst>::type T;
        typedef typename next<SFirst>::type next;
        typedef typename copy_to_vector_impl<next, NLeft-1>::type rest;
    public:
        typedef typename push_front<rest, T>::type type;
    };

    template <typename SFirst> 
    struct copy_to_vector_impl<SFirst,1> {
        typedef vector<typename deref<SFirst>::type> type;
    };
}

template <typename Src>
struct copy_to_vector {
    typedef typename detail::copy_to_vector_impl<typename begin<Src>::type, size<Src>::value>::type type;
};

template <>
struct copy_to_vector<set<> > {
    typedef vector0<> type;
};

} } // boost::mpl

namespace boost { namespace gil {


///////////////////////////////////////////////////////
/// 
/// unary_reduce, binary_reduce - given an MPL Random Access Sequence,
/// dynamically specified index to that container, the bits of an instance of the corresponding type and
/// a generic operation, invokes the operation on the given type
///
///////////////////////////////////////////////////////




///////////////////////////////////////////////////////
/// 
/// \brief Unary reduce.
///
/// Given a set of types and an operation, reduces each type in the set (to reduced_t), then removes duplicates (to unique_t)
/// To apply the operation, first constructs a lookup table that maps each element from Types to its place in unique_t and uses it to map
/// the index to anther index (in map_index). Then invokes apply_operation_base on the unique types with the new index.
///
///////////////////////////////////////////////////////

template <typename Types, typename Op>
struct unary_reduce_impl {
    typedef typename mpl::transform<Types, detail::reduce<Op, mpl::_1> >::type reduced_t;
    typedef typename mpl::copy<reduced_t, mpl::inserter<mpl::set<>, mpl::insert<mpl::_1,mpl::_2> > >::type unique_t;
    static const bool is_single=mpl::size<unique_t>::value==1;
};

template <typename Types, typename Op, bool IsSingle=unary_reduce_impl<Types,Op>::is_single>
struct unary_reduce : public unary_reduce_impl<Types,Op> {
    typedef typename unary_reduce_impl<Types,Op>::reduced_t reduced_t;
    typedef typename unary_reduce_impl<Types,Op>::unique_t unique_t;

    static unsigned short inline map_index(std::size_t index) {
        typedef typename mpl::mapping_vector<reduced_t, unique_t> indices_t;
        return gil::at_c<indices_t, unsigned short>(index);
    }
    template <typename Bits> GIL_FORCEINLINE static typename Op::result_type applyc(const Bits& bits, std::size_t index, Op op) {
        return apply_operation_basec<unique_t>(bits,map_index(index),op);
    }

    template <typename Bits> GIL_FORCEINLINE static typename Op::result_type apply(Bits& bits, std::size_t index, Op op) {
        return apply_operation_base<unique_t>(bits,map_index(index),op);
    }
};

template <typename Types, typename Op>
struct unary_reduce<Types,Op,true> : public unary_reduce_impl<Types,Op> {
    typedef typename unary_reduce_impl<Types,Op>::unique_t unique_t;
    static unsigned short inline map_index(std::size_t index) { return 0; }

    template <typename Bits> GIL_FORCEINLINE static typename Op::result_type applyc(const Bits& bits, std::size_t index, Op op) {
        return op(*gil_reinterpret_cast_c<const typename mpl::front<unique_t>::type*>(&bits));
    }

    template <typename Bits> GIL_FORCEINLINE static typename Op::result_type apply(Bits& bits, std::size_t index, Op op) {
        return op(*gil_reinterpret_cast<typename       mpl::front<unique_t>::type*>(&bits));
    }
};


///////////////////////////////////////////////////////
/// 
/// \brief Binary reduce.
///
/// Given two sets of types, Types1 and Types2, first performs unary reduction on each. Then checks if the product of their sizes is above
/// the GIL_BINARY_REDUCE_LIMIT limit. If so, the operation is too complex to be binary-reduced and uses a specialization of binary_reduce_impl
/// to simply call the binary apply_operation_base (which performs two nested 1D apply operations)
/// If the operation is not too complex, uses the other specialization of binary_reduce_impl to create a cross-product of the input types
/// and performs unary reduction on the result (bin_reduced_t). To apply the binary operation, it simply invokes a unary apply_operation_base
/// on the reduced cross-product types
///
///////////////////////////////////////////////////////

namespace detail {
    struct pair_generator {
        template <typename Vec2> struct apply {
            typedef std::pair<const typename mpl::at_c<Vec2,0>::type*, const typename mpl::at_c<Vec2,1>::type*> type;
        };
    };

    // When the types are not too large, applies reduce on their cross product
    template <typename Unary1, typename Unary2, typename Op, bool IsComplex>
    struct binary_reduce_impl {
    //private:
        typedef typename mpl::copy_to_vector<typename Unary1::unique_t>::type vec1_types;
        typedef typename mpl::copy_to_vector<typename Unary2::unique_t>::type vec2_types;

        typedef mpl::cross_vector<mpl::vector2<vec1_types, vec2_types>, pair_generator> BIN_TYPES;
        typedef unary_reduce<BIN_TYPES,Op> bin_reduced_t;
        
        static unsigned short inline map_index(std::size_t index1, std::size_t index2) {
            unsigned short r1=Unary1::map_index(index1);
            unsigned short r2=Unary2::map_index(index2);
            return bin_reduced_t::map_index(r2*mpl::size<vec1_types>::value + r1);
        }
    public:
        typedef typename bin_reduced_t::unique_t unique_t;

        template <typename Bits1, typename Bits2>
        static typename Op::result_type inline apply(const Bits1& bits1, std::size_t index1, const Bits2& bits2, std::size_t index2, Op op) {
            std::pair<const void*,const void*> pr(&bits1, &bits2);
            return apply_operation_basec<unique_t>(pr, map_index(index1,index2),op);
        }
    };

    // When the types are large performs a double-dispatch. Binary reduction is not done.
    template <typename Unary1, typename Unary2, typename Op>
    struct binary_reduce_impl<Unary1,Unary2,Op,true> {
        template <typename Bits1, typename Bits2>
        static typename Op::result_type inline apply(const Bits1& bits1, std::size_t index1, const Bits2& bits2, std::size_t index2, Op op) {
            return apply_operation_base<Unary1::unique_t,Unary2::unique_t>(bits1, index1, bits2, index2, op);
        }
    };
}


template <typename Types1, typename Types2, typename Op>
struct binary_reduce {
//private:
    typedef unary_reduce<Types1,Op> unary1_t;
    typedef unary_reduce<Types2,Op> unary2_t;

    static const std::size_t CROSS_SIZE = mpl::size<typename unary1_t::unique_t>::value * 
                                          mpl::size<typename unary2_t::unique_t>::value;

    typedef detail::binary_reduce_impl<unary1_t,unary2_t,Op, (CROSS_SIZE>GIL_BINARY_REDUCE_LIMIT)> impl;
public:
    template <typename Bits1, typename Bits2>
    static typename Op::result_type inline apply(const Bits1& bits1, std::size_t index1, const Bits2& bits2, std::size_t index2, Op op) {
        return impl::apply(bits1,index1,bits2,index2,op);
    }
};

template <typename Types, typename UnaryOp>
GIL_FORCEINLINE typename UnaryOp::result_type apply_operation(variant<Types>& arg, UnaryOp op) {
    return unary_reduce<Types,UnaryOp>::template apply(arg._bits, arg._index ,op);
}

template <typename Types, typename UnaryOp>
GIL_FORCEINLINE typename UnaryOp::result_type apply_operation(const variant<Types>& arg, UnaryOp op) {
    return unary_reduce<Types,UnaryOp>::template applyc(arg._bits, arg._index ,op);
}

template <typename Types1, typename Types2, typename BinaryOp>
GIL_FORCEINLINE typename BinaryOp::result_type apply_operation(const variant<Types1>& arg1, const variant<Types2>& arg2, BinaryOp op) {    
    return binary_reduce<Types1,Types2,BinaryOp>::template apply(arg1._bits, arg1._index, arg2._bits, arg2._index, op);
}

#undef GIL_BINARY_REDUCE_LIMIT

} }  // namespace gil