path: root/libcilkrts/include/cilk/reducer_list.h

/*  reducer_list.h                  -*- C++ -*-
 *
 *  @copyright
 *  Copyright (C) 2009-2013, Intel Corporation
 *  All rights reserved.
 *  
 *  @copyright
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions
 *  are met:
 *  
 *    * Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *    * Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in
 *      the documentation and/or other materials provided with the
 *      distribution.
 *    * Neither the name of Intel Corporation nor the names of its
 *      contributors may be used to endorse or promote products derived
 *      from this software without specific prior written permission.
 *  
 *  @copyright
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 *  HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
 *  OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 *  AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
 *  WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 *  POSSIBILITY OF SUCH DAMAGE.
 */

/** @file reducer_list.h
 *
 *  @brief Defines classes for doing parallel list creation by appending or
 *  prepending.
 *
 *  @ingroup ReducersList
 *
 *  @see ReducersList
 */

#ifndef REDUCER_LIST_H_INCLUDED
#define REDUCER_LIST_H_INCLUDED

#include <cilk/reducer.h>
#include <list>

/** @defgroup ReducersList List Reducers
 *
 *  List append and prepend reducers allow the creation of a standard list by
 *  concatenating a set of lists or values in parallel.
 *
 *  @ingroup Reducers
 *
 *  You should be familiar with @ref pagereducers "Cilk reducers", described in
 *  file `reducers.md`, and particularly with @ref reducers_using, before trying
 *  to use the information in this file.
 *
 *  @section redlist_usage Usage Example
 *
 *      // Create a list containing the labels of the nodes of a tree in
 *      // “inorder” (left subtree, root, right subtree).
 *
 *      struct Tree { Tree* left; Tree* right; string label; ... };
 *
 *      list<string> x;
 *      cilk::reducer< cilk::op_list_append<string> > xr(cilk::move_in(x));
 *      collect_labels(tree, xr);
 *      xr.move_out(x);
 *      
 *      void collect_labels(Tree* node, 
 *                          cilk::reducer< cilk::op_list_append<string> >& xr)
 *      {
 *          if (node) {
 *              cilk_spawn collect_labels(node->left, xr);
 *              xr->push_back(node->label);
 *              collect_labels(node->right, xr);
 *              cilk_sync;
 *          }
 *      }
 *
 *  @section redlist_monoid The Monoid
 *
 *  @subsection redlist_monoid_values Value Set
 *
 *  The value set of a list reducer is the set of values of the class 
 *  `std::list<Type, Allocator>`, which we refer to as “the reducer’s list 
 *  type”.
 *
 *  @subsection redlist_monoid_operator Operator
 *
 *  The operator of a list append reducer is defined as
 *
 *      x CAT y == (every element of x, followed by every element of y)
 *
 *  The operator of a list prepend reducer is defined as
 *
 *      x RCAT y == (every element of y, followed by every element of x)
 *
 *  @subsection redlist_monoid_identity Identity
 *
 *  The identity value of a list reducer is the empty list, which is the value 
 *  of the expression `std::list<Type, Allocator>([allocator])`.
 *
 *  @section redlist_operations Operations
 *
 *  In the operation descriptions below, the type name `List` refers to the 
 *  reducer’s string type, `std::list<Type, Allocator>`.
 *
 *  @subsection redlist_constructors Constructors
 *
 *  Any argument list which is valid for a `std::list` constructor is valid for 
 *  a list reducer constructor. The usual move-in constructor is also provided:
 *
 *      reducer(move_in(List& variable))
 *
 *  A list reducer with no constructor arguments, or with only an allocator 
 *  argument, will initially contain the identity value, an empty list. 
 *
 *  @subsection redlist_get_set Set and Get
 *
 *      r.set_value(const List& value)
 *      const List& = r.get_value() const
 *      r.move_in(List& variable)
 *      r.move_out(List& variable)
 *
 *  @subsection redlist_view_ops View Operations
 *
 *  The view of a list append reducer provides the following member functions:
 *
 *      void push_back(const Type& element) 
 *      void insert_back(List::size_type n, const Type& element) 
 *      template <typename Iter> void insert_back(Iter first, Iter last)
 *      void splice_back(List& x)
 *      void splice_back(List& x, List::iterator i)
 *      void splice_back(List& x, List::iterator first, List::iterator last)
 *  
 *  The view of a list prepend reducer provides the following member functions:
 *
 *      void push_front(const Type& element) 
 *      void insert_front(List::size_type n, const Type& element) 
 *      template <typename Iter> void insert_front(Iter first, Iter last)
 *      void splice_front(List& x)
 *      void splice_front(List& x, List::iterator i)
 *      void splice_front(List& x, List::iterator first, List::iterator last)
 *
 *  The `push_back` and `push_front` functions are the same as the
 *  corresponding `std::list` functions. The `insert_back`, `splice_back`,
 *  `insert_front`, and `splice_front` functions are the same as the 
 *  `std::list` `insert` and `splice` functions, with the first parameter
 *  fixed to the end or beginning of the list, respectively.
 *
 *  @section redlist_performance Performance Considerations
 *
 *  An efficient reducer requires that combining the values of two views (using 
 *  the view `reduce()` function) be a constant-time operations. Two lists can
 *  be merged in constant time using the `splice()` function if they have the
 *  same allocator. Therefore, the lists for new views are created (by the view
 *  identity constructor) using the same allocator as the list that was created
 *  when the reducer was constructed.
 *
 *  The performance of adding elements to a list reducer depends on the view 
 *  operations that are used:
 *
 *  *   The `push` functions add a single element to the list, and therefore
 *      take constant time.
 *  *   An `insert` function that inserts _N_ elements adds each of them
 *      individually, and therefore takes _O(N)_ time. 
 *  *   A `splice` function that inserts _N_ elements just adjusts a couple of
 *      pointers, and therefore takes constant time, _if the splice is from a
 *      list with the same allocator as the reducer_. Otherwise, it is
 *      equivalent to an `insert`, and takes _O(N)_ time.
 *
 *  This means that for best performance, if you will be adding elements to a
 *  list reducer in batches, you should `splice` them from a list having the
 *  same allocator as the reducer.
 *
 *  The reducer `move_in` and `move_out` functions do a constant-time `swap` if
 *  the variable has the same allocator as the reducer, and a linear-time copy
 *  otherwise.
 *  
 *  Note that the allocator of a list reducer is determined when the reducer is
 *  constructed. The following two examples may have very different behavior:
 *
 *      list<Element, Allocator> a_list;
 *
 *      reducer< list_append<Element, Allocator> reducer1(move_in(a_list));
 *      ... parallel computation ...
 *      reducer1.move_out(a_list);
 *
 *      reducer< list_append<Element, Allocator> reducer2;
 *      reducer2.move_in(a_list);
 *      ... parallel computation ...
 *      reducer2.move_out(a_list);
 *
 *  *   `reducer1` will be constructed with the same allocator as `a_list`,
 *      because the list was was specified in the constructor. The `move_in`
 *      and`move_out` can therefore be done with a `swap` in constant time.
 *  *   `reducer2` will be constructed with a _default_ allocator,
 *      “`Allocator()`”, which may or may not be the same as the allocator of
 *      `a_list`. Therefore, the `move_in` and `move_out` may have to be done
 *      with a copy in _O(N)_ time.
 *  
 *  (All instances of an allocator type with no internal state (like
 *  `std::allocator`) are “the same”. You only need to worry about the “same
 *  allocator” issue when you create list reducers with custom allocator types.)
 *
 *  @section redlist_types Type and Operator Requirements
 *
 *  `std::list<Type, Allocator>` must be a valid type.
 */


namespace cilk {

namespace internal {

/** @ingroup ReducersList */
//@{

/** Base class for list append and prepend view classes.
 *
 *  @note   This class provides the definitions that are required for a class
 *          that will be used as the parameter of a @ref list_monoid_base
 *          specialization. 
 *
 *  @tparam Type        The list element type (not the list type).
 *  @tparam Allocator   The list's allocator class.
 *
 *  @see ReducersList
 *  @see list_monoid_base
 */
template <typename Type, typename Allocator>
class list_view_base
{
protected:
    /// The type of the contained list.
    typedef std::list<Type, Allocator>  list_type;

    /// The list accumulator variable.
    list_type m_value;

public:

    /** @name Monoid support.
     */
    //@{
    
    /// Required by @ref monoid_with_view
    typedef list_type   value_type;

    /// Required by @ref list_monoid_base
    Allocator get_allocator() const
    { 
        return m_value.get_allocator(); 
    }
    
    //@}
    
    
    /** @name Constructors.
     */
    //@{
    
    /// Standard list constructor.
    explicit list_view_base(const Allocator& a = Allocator()) : m_value(a) {}
    explicit list_view_base(
        typename list_type::size_type n, 
        const Type& value = Type(), 
        const Allocator& a = Allocator() ) : m_value(n, value, a) {}
    template <typename Iter> 
    list_view_base(Iter first, Iter last, const Allocator& a = Allocator()) : 
        m_value(first, last, a) {}
    list_view_base(const list_type& list) : m_value(list) {}

    /// Move-in constructor.
    explicit list_view_base(move_in_wrapper<value_type> w)
        : m_value(w.value().get_allocator())
    {
        m_value.swap(w.value());
    }
    
    //@}
    
    /** @name Reducer support.
     */
    //@{
    
    /// Required by reducer::move_in()
    void view_move_in(value_type& v)
    {
        if (m_value.get_allocator() == v.get_allocator())
            // Equal allocators. Do a (fast) swap.
            m_value.swap(v);
        else
            // Unequal allocators. Do a (slow) copy.
            m_value = v;
        v.clear();
    }
    
    /// Required by reducer::move_out()
    void view_move_out(value_type& v)
    {
        if (m_value.get_allocator() == v.get_allocator())
            // Equal allocators.  Do a (fast) swap.
            m_value.swap(v);
        else
            // Unequal allocators.  Do a (slow) copy.
            v = m_value;
        m_value.clear();
    }
    
    /// Required by reducer::set_value()
    void view_set_value(const value_type& v) { m_value = v; }

    /// Required by reducer::get_value()
    value_type const& view_get_value()     const { return m_value; }
    
    // Required by legacy wrapper get_reference()
    value_type      & view_get_reference()       { return m_value; }
    value_type const& view_get_reference() const { return m_value; }
    
    //@}
};


/** Base class for list append and prepend monoid classes.
 *
 *  The key to efficient reducers is that the `identity` operation, which
 * creates a new per-strand view, and the `reduce` operation, which combines
 *  two per-strand views, must be constant-time operations. Two lists can be
 *  concatenated in constant time only if they have the same allocator.
 *  Therefore, all the per-strand list accumulator variables must be created
 *   with the same allocator as the leftmost view list. 
 *
 *  This means that a list reduction monoid must have a copy of the allocator
 *  of the leftmost view’s list, so that it can use it in the `identity`
 *  operation. This, in turn, requires that list reduction monoids have a
 *  specialized `construct()` function, which constructs the leftmost view
 *  before the monoid, and then passes the leftmost view’s allocator to the
 *  monoid constructor.
 *
 *  @tparam View    The list append or prepend view class.
 *  @tparam Align   If `false` (the default), reducers instantiated on this
 *                  monoid will be naturally aligned (the Cilk library 1.0
 *                  behavior). If `true`, reducers instantiated on this monoid
 *                  will be cache-aligned for binary compatibility with 
 *                  reducers in Cilk library version 0.9.
 *
 *  @see ReducersList
 *  @see list_view_base
 */
template <typename View, bool Align>
class list_monoid_base : public monoid_with_view<View, Align>
{
    typedef typename View::value_type           list_type;
    typedef typename list_type::allocator_type  allocator_type;
    allocator_type                              m_allocator;
    
    using monoid_base<list_type, View>::provisional;
    
public:

    /** Constructor.
     *
     *  There is no default constructor for list monoids, because the allocator 
     *  must always be specified.
     *
     *  @param  allocator   The list allocator to be used when
     *                      identity-constructing new views.
     */
    list_monoid_base(const allocator_type& allocator = allocator_type()) :
        m_allocator(allocator) {}

    /** Create an identity view.
     *
     *  List view identity constructors take the list allocator as an argument.
     *
     *  @param v    The address of the uninitialized memory in which the view
     *              will be constructed.
     */
    void identity(View *v) const { ::new((void*) v) View(m_allocator); }
    
    /** @name construct functions
     *
     *  All `construct()` functions first construct the leftmost view, using 
     *  the optional @a x1, @a x2, and @a x3 arguments that were passed in from
     *  the reducer constructor. They then call the view’s `get_allocator()`
     *  function to get the list allocator from its contained list, and pass it
     *  to the monoid constructor.
     */
    //@{

    template <typename Monoid>
    static void construct(Monoid* monoid, View* view)
        { provisional( new ((void*)view) View() ).confirm_if( 
            new ((void*)monoid) Monoid(view->get_allocator()) ); }

    template <typename Monoid, typename T1>
    static void construct(Monoid* monoid, View* view, const T1& x1)
        { provisional( new ((void*)view) View(x1) ).confirm_if( 
            new ((void*)monoid) Monoid(view->get_allocator()) ); }

    template <typename Monoid, typename T1, typename T2>
    static void construct(Monoid* monoid, View* view, const T1& x1, const T2& x2)
        { provisional( new ((void*)view) View(x1, x2) ).confirm_if( 
            new ((void*)monoid) Monoid(view->get_allocator()) ); }

    template <typename Monoid, typename T1, typename T2, typename T3>
    static void construct(Monoid* monoid, View* view, const T1& x1, const T2& x2, 
                            const T3& x3)
        { provisional( new ((void*)view) View(x1, x2, x3) ).confirm_if( 
            new ((void*)monoid) Monoid(view->get_allocator()) ); }

    //@}
};

//@}

} // namespace internal


/** @ingroup ReducersList */
//@{

/** The list append reducer view class.
 *
 *  This is the view class for reducers created with 
 *  `cilk::reducer< cilk::op_list_append<Type, Allocator> >`. It holds the
 *  accumulator variable for the reduction, and allows only append operations
 *  to be performed on it.
 *
 *  @note   The reducer “dereference” operation (`reducer::operator *()`) 
 *          yields a reference to the view. Thus, for example, the view class’s
 *          `push_back` operation would be used in an expression like
 *          `r->push_back(a)`, where `r` is a list append reducer variable.
 *
 *  @tparam Type        The list element type (not the list type).
 *  @tparam Allocator   The list allocator type.
 *
 *  @see ReducersList
 *  @see op_list_append
 */
template <class Type, 
          class Allocator = typename std::list<Type>::allocator_type>
class op_list_append_view : public internal::list_view_base<Type, Allocator>
{
    typedef internal::list_view_base<Type, Allocator>   base;
    typedef std::list<Type, Allocator>                  list_type;
    typedef typename list_type::iterator                iterator;
    
    iterator end() { return this->m_value.end(); }

public:

    /** @name Constructors.
     *
     *  All op_list_append_view constructors simply pass their arguments on to
     *  the @ref internal::list_view_base base class constructor.
     *
     *  @ref internal::list_view_base supports all the std::list constructor
     *  forms, as well as the reducer move_in constructor form.
     */
    //@{
    
    op_list_append_view() : base() {}
    
    template <typename T1>
    op_list_append_view(const T1& x1) : base(x1) {}
    
    template <typename T1, typename T2>
    op_list_append_view(const T1& x1, const T2& x2) : base(x1, x2) {}
    
    template <typename T1, typename T2, typename T3>
    op_list_append_view(const T1& x1, const T2& x2, const T3& x3) : 
        base(x1, x2, x3) {}

    //@}    

    /** @name View modifier operations.
     */
    //@{
    
    /** Add an element at the end of the list.
     *
     *  This is equivalent to `list.push_back(element)`
     */
    void push_back(const Type& element) 
        { this->m_value.push_back(element); }

    /** Insert elements at the end of the list.
     *
     *  This is equivalent to `list.insert(list.end(), n, element)`
     */
    void insert_back(typename list_type::size_type n, const Type& element) 
        { this->m_value.insert(end(), n, element); }

    /** Insert elements at the end of the list.
     *
     *  This is equivalent to `list.insert(list.end(), first, last)`
     */
    template <typename Iter>
    void insert_back(Iter first, Iter last)
        { this->m_value.insert(end(), first, last); }

    /** Splice elements at the end of the list.
     *
     *  This is equivalent to `list.splice(list.end(), x)`
     */
    void splice_back(list_type& x) {
        if (x.get_allocator() == this->m_value.get_allocator())
            this->m_value.splice(end(), x);
        else {
            insert_back(x.begin(), x.end());
            x.clear();
        }
    }

    /** Splice elements at the end of the list.
     *
     *  This is equivalent to `list.splice(list.end(), x, i)`
     */
    void splice_back(list_type& x, iterator i) {
        if (x.get_allocator() == this->m_value.get_allocator())
            this->m_value.splice(end(), x, i);
        else {
            push_back(*i);
            x.erase(i);
        }
    }

    /** Splice elements at the end of the list.
     *
     *  This is equivalent to `list.splice(list.end(), x, first, last)`
     */
    void splice_back(list_type& x, iterator first, iterator last) {
        if (x.get_allocator() == this->m_value.get_allocator())
            this->m_value.splice(end(), x, first, last);
        else {
            insert_back(first, last);
            x.erase(first, last);
        }
    }
    
    //@}

    /** Reduction operation.
     *
     *  This function is invoked by the @ref op_list_append monoid to combine
     *  the views of two strands when the right strand merges with the left 
     *  one. It appends the value contained in the right-strand view to the 
     *  value contained in the left-strand view, and leaves the value in the
     *  right-strand view undefined.
     *
     *  @param  right   A pointer to the right-strand view. (`this` points to
     *                  the left-strand view.)
     *
     *  @note   Used only by the @ref op_list_append monoid to implement the
     *          monoid reduce operation.
     */
    void reduce(op_list_append_view* right)
    {
        __CILKRTS_ASSERT(
            this->m_value.get_allocator() == right->m_value.get_allocator());
        this->m_value.splice(end(), right->m_value);
    }
};


/** The list prepend reducer view class.
 *
 *  This is the view class for reducers created with 
 *  `cilk::reducer< cilk::op_list_prepend<Type, Allocator> >`. It holds the
 *  accumulator variable for the reduction, and allows only prepend operations
 *  to be performed on it.
 *
 *  @note   The reducer “dereference” operation (`reducer::operator *()`) 
 *          yields a reference to the view. Thus, for example, the view class’s
 *          `push_front` operation would be used in an expression like
 *          `r->push_front(a)`, where `r` is a list prepend reducer variable.
 *
 *  @tparam Type        The list element type (not the list type).
 *  @tparam Allocator   The list allocator type.
 *
 *  @see ReducersList
 *  @see op_list_prepend
 */
template <class Type, 
          class Allocator = typename std::list<Type>::allocator_type>
class op_list_prepend_view : public internal::list_view_base<Type, Allocator>
{
    typedef internal::list_view_base<Type, Allocator>   base;
    typedef std::list<Type, Allocator>                  list_type;
    typedef typename list_type::iterator                iterator;
    
    iterator begin() { return this->m_value.begin(); }

public:

    /** @name Constructors.
     *
     *  All op_list_prepend_view constructors simply pass their arguments on to
     *  the @ref internal::list_view_base base class constructor.
     *
     *  @ref internal::list_view_base supports all the std::list constructor
     *  forms, as well as the reducer move_in constructor form.
     *
     */
    //@{
    
    op_list_prepend_view() : base() {}
    
    template <typename T1>
    op_list_prepend_view(const T1& x1) : base(x1) {}
    
    template <typename T1, typename T2>
    op_list_prepend_view(const T1& x1, const T2& x2) : base(x1, x2) {}
    
    template <typename T1, typename T2, typename T3>
    op_list_prepend_view(const T1& x1, const T2& x2, const T3& x3) : 
        base(x1, x2, x3) {}

    //@}    

    /** @name View modifier operations.
     */
    //@{
    
    /** Add an element at the beginning of the list.
     *
     *  This is equivalent to `list.push_front(element)`
     */
    void push_front(const Type& element) 
        { this->m_value.push_front(element); }

    /** Insert elements at the beginning of the list.
     *
     *  This is equivalent to `list.insert(list.begin(), n, element)`
     */
    void insert_front(typename list_type::size_type n, const Type& element) 
        { this->m_value.insert(begin(), n, element); }

    /** Insert elements at the beginning of the list.
     *
     *  This is equivalent to `list.insert(list.begin(), first, last)`
     */
    template <typename Iter>
    void insert_front(Iter first, Iter last)
        { this->m_value.insert(begin(), first, last); }

    /** Splice elements at the beginning of the list.
     *
     *  This is equivalent to `list.splice(list.begin(), x)`
     */
    void splice_front(list_type& x) {
        if (x.get_allocator() == this->m_value.get_allocator())
            this->m_value.splice(begin(), x);
        else {
            insert_front(x.begin(), x.begin());
            x.clear();
        }
    }

    /** Splice elements at the beginning of the list.
     *
     *  This is equivalent to `list.splice(list.begin(), x, i)`
     */
    void splice_front(list_type& x, iterator i) {
        if (x.get_allocator() == this->m_value.get_allocator())
            this->m_value.splice(begin(), x, i);
        else {
            push_front(*i);
            x.erase(i);
        }
    }

    /** Splice elements at the beginning of the list.
     *
     *  This is equivalent to `list.splice(list.begin(), x, first, last)`
     */
    void splice_front(list_type& x, iterator first, iterator last) {
        if (x.get_allocator() == this->m_value.get_allocator())
            this->m_value.splice(begin(), x, first, last);
        else {
            insert_front(first, last);
            x.erase(first, last);
        }
    }
    
    //@}

    /** Reduction operation.
     *
     *  This function is invoked by the @ref op_list_prepend monoid to combine
     *  the views of two strands when the right strand merges with the left 
     *  one. It prepends the value contained in the right-strand view to the 
     *  value contained in the left-strand view, and leaves the value in the
     *  right-strand view undefined.
     *
     *  @param  right   A pointer to the right-strand view. (`this` points to
     *                  the left-strand view.)
     *
     *  @note   Used only by the @ref op_list_prepend monoid to implement the
     *          monoid reduce operation.
     */
    /** Reduce operation.
     *
     *  Required by @ref monoid_base.
     */
    void reduce(op_list_prepend_view* right)
    {
        __CILKRTS_ASSERT(
            this->m_value.get_allocator() == right->m_value.get_allocator());
        this->m_value.splice(begin(), right->m_value);
    }
};



/** Monoid class for list append reductions. Instantiate the cilk::reducer
 *  template class with a op_list_append monoid to create a list append reducer
 *  class. For example, to create a list of strings:
 *
 *      cilk::reducer< cilk::op_list_append<std::string> > r;
 *
 *  @tparam Type    The list element type (not the list type).
 *  @tparam Alloc   The list allocator type.
 *  @tparam Align   If `false` (the default), reducers instantiated on this
 *                  monoid will be naturally aligned (the Cilk library 1.0
 *                  behavior). If `true`, reducers instantiated on this monoid
 *                  will be cache-aligned for binary compatibility with 
 *                  reducers in Cilk library version 0.9.
 *
 *  @see ReducersList
 *  @see op_list_append_view
 */
template <typename Type, 
          typename Allocator = typename std::list<Type>::allocator_type,
          bool Align = false>
struct op_list_append : 
    public internal::list_monoid_base<op_list_append_view<Type, Allocator>, Align> 
{
    /// Construct with default allocator.
    op_list_append() {}
    /// Construct with specified allocator.
    op_list_append(const Allocator& alloc) : 
        internal::list_monoid_base<op_list_append_view<Type, Allocator>, Align>(alloc) {}
};

/** Monoid class for list prepend reductions. Instantiate the cilk::reducer
 *  template class with a op_list_prepend monoid to create a list prepend
 *  reducer class. For example, to create a list of strings:
 *
 *      cilk::reducer< cilk::op_list_prepend<std::string> > r;
 *
 *  @tparam Type    The list element type (not the list type).
 *  @tparam Alloc   The list allocator type.
 *  @tparam Align   If `false` (the default), reducers instantiated on this
 *                  monoid will be naturally aligned (the Cilk library 1.0
 *                  behavior). If `true`, reducers instantiated on this monoid
 *                  will be cache-aligned for binary compatibility with 
 *                  reducers in Cilk library version 0.9.
 *
 *  @see ReducersList
 *  @see op_list_prepend_view
 */
template <typename Type, 
          typename Allocator = typename std::list<Type>::allocator_type,
          bool Align = false>
struct op_list_prepend : 
    public internal::list_monoid_base<op_list_prepend_view<Type, Allocator>, Align> 
{
    /// Construct with default allocator.
    op_list_prepend() {}
    /// Construct with specified allocator.
    op_list_prepend(const Allocator& alloc) : 
        internal::list_monoid_base<op_list_prepend_view<Type, Allocator>, Align>(alloc) {}
};


/** Deprecated list append reducer wrapper class.
 *
 *  reducer_list_append is the same as 
 *  @ref reducer<@ref op_list_append>, except that reducer_list_append is a
 *  proxy for the contained view, so that accumulator variable update 
 *  operations can be applied directly to the reducer. For example, an element
 *  is appended to a `reducer<%op_list_append>` with `r->push_back(a)`, but an
 *  element can be appended to a `%reducer_list_append` with `r.push_back(a)`.
 *
 *  @deprecated Users are strongly encouraged to use `reducer<monoid>`
 *              reducers rather than the old wrappers like reducer_list_append. 
 *              The `reducer<monoid>` reducers show the reducer/monoid/view
 *              architecture more clearly, are more consistent in their
 *              implementation, and present a simpler model for new
 *              user-implemented reducers.
 *
 *  @note   Implicit conversions are provided between `%reducer_list_append` 
 *          and `reducer<%op_list_append>`. This allows incremental code
 *          conversion: old code that used `%reducer_list_append` can pass a
 *          `%reducer_list_append` to a converted function that now expects a
 *          pointer or reference to a `reducer<%op_list_append>`, and vice
 *          versa.
 *
 *  @tparam Type        The value type of the list.
 *  @tparam Allocator   The allocator type of the list.
 *
 *  @see op_list_append
 *  @see reducer
 *  @see ReducersList
 */
template <class Type, class Allocator = std::allocator<Type> >
class reducer_list_append : 
    public reducer<op_list_append<Type, Allocator, true> >
{
    typedef reducer<op_list_append<Type, Allocator, true> > base;
    using base::view;
public:

    /// The reducer’s list type.
    typedef typename base::value_type list_type;

    /// The list’s element type.
    typedef Type list_value_type;

    /// The reducer’s primitive component type.
    typedef Type basic_value_type;

    /// The monoid type.
    typedef typename base::monoid_type Monoid;

    /** @name Constructors
     */
    //@{
    
    /** Construct a reducer with an empty list.
     */
    reducer_list_append() {}

    /** Construct a reducer with a specified initial list value.
     */
    reducer_list_append(const std::list<Type, Allocator> &initial_value) : 
        base(initial_value) {}
        
    //@}
        

    /** @name Forwarded functions
     *  @details Functions that update the contained accumulator variable are
     *  simply forwarded to the contained @ref op_and_view. */
    //@{

    /// @copydoc op_list_append_view::push_back(const Type&)
    void push_back(const Type& element) { view().push_back(element); }
    
    //@}

    /** Allow mutable access to the list within the current view.
     * 
     *  @warning    If this method is called before the parallel calculation is
     *              complete, the list returned by this method will be a partial
     *              result.
     * 
     *  @returns    A mutable reference to the list within the current view.
     */
    list_type &get_reference() { return view().view_get_reference(); }

    /** Allow read-only access to the list within the current view.
     * 
     *  @warning    If this method is called before the parallel calculation is
     *              complete, the list returned by this method will be a partial
     *              result.
     * 
     *  @returns    A const reference to the list within the current view.
     */
    list_type const &get_reference() const { return view().view_get_reference(); }

    /// @name Dereference
    //@{
    /** Dereferencing a wrapper is a no-op. It simply returns the wrapper.
     *  Combined with the rule that a wrapper forwards view operations to the
     *  view, this means that view operations can be written the same way on
     *  reducers and wrappers, which is convenient for incrementally
     *  converting code using wrappers to code using reducers. That is:
     *
     *      reducer< op_list_append<int> > r;
     *      r->push_back(a);    // *r returns the view
     *                          // push_back is a view member function
     *
     *      reducer_list_append<int> w;
     *      w->push_back(a);    // *w returns the wrapper
     *                          // push_back is a wrapper member function that
     *                          // calls the corresponding view function
     */
    //@{
    reducer_list_append&       operator*()       { return *this; }
    reducer_list_append const& operator*() const { return *this; }

    reducer_list_append*       operator->()       { return this; }
    reducer_list_append const* operator->() const { return this; }
    //@}
    
    /** @name Upcast
     *  @details In Cilk library 0.9, reducers were always cache-aligned. In
     *  library  1.0, reducer cache alignment is optional. By default, reducers
     *  are unaligned (i.e., just naturally aligned), but legacy wrappers
     *  inherit from cache-aligned reducers for binary compatibility.
     *
     *  This means that a wrapper will automatically be upcast to its aligned
     *  reducer base class. The following conversion operators provide
     *  pseudo-upcasts to the corresponding unaligned reducer class.
     */
    //@{
    operator reducer< op_list_append<Type, Allocator, false> >& ()
    {
        return *reinterpret_cast<
            reducer< op_list_append<Type, Allocator, false> >*
            >(this);
    }
    operator const reducer< op_list_append<Type, Allocator, false> >& () const
    {
        return *reinterpret_cast< 
            const reducer< op_list_append<Type, Allocator, false> >* 
            >(this);
    }
    //@}
    
};


/** Deprecated list prepend reducer wrapper class.
 *
 *  reducer_list_prepend is the same as 
 *  @ref reducer<@ref op_list_prepend>, except that reducer_list_prepend is a
 *  proxy for the contained view, so that accumulator variable update operations
 *  can be applied directly to the reducer. For example, an element is prepended
 *  to a `reducer<op_list_prepend>` with `r->push_back(a)`, but an element is
 *  prepended to a `reducer_list_prepend` with `r.push_back(a)`.
 *
 *  @deprecated Users are strongly encouraged to use `reducer<monoid>`
 *              reducers rather than the old wrappers like reducer_list_prepend. 
 *              The `reducer<monoid>` reducers show the reducer/monoid/view
 *              architecture more clearly, are more consistent in their
 *              implementation, and present a simpler model for new
 *              user-implemented reducers.
 *
 *  @note   Implicit conversions are provided between `%reducer_list_prepend` 
 *          and `reducer<%op_list_prepend>`. This allows incremental code
 *          conversion: old code that used `%reducer_list_prepend` can pass a
 *          `%reducer_list_prepend` to a converted function that now expects a
 *          pointer or reference to a `reducer<%op_list_prepend>`, and vice
 *          versa.
 *
 *  @tparam Type        The value type of the list.
 *  @tparam Allocator   The allocator type of the list.
 *
 *  @see op_list_prepend
 *  @see reducer
 *  @see ReducersList
 */
template <class Type, class Allocator = std::allocator<Type> >
class reducer_list_prepend : 
    public reducer<op_list_prepend<Type, Allocator, true> >
{
    typedef reducer<op_list_prepend<Type, Allocator, true> > base;
    using base::view;
public:

    /** The reducer’s list type.
     */
    typedef typename base::value_type list_type;

    /** The list’s element type.
     */
    typedef Type list_value_type;

    /** The reducer’s primitive component type.
     */
    typedef Type basic_value_type;

    /** The monoid type.
     */
    typedef typename base::monoid_type Monoid;

    /** @name Constructors
     */
    //@{
    
    /** Construct a reducer with an empty list.
     */
    reducer_list_prepend() {}

    /** Construct a reducer with a specified initial list value.
     */
    reducer_list_prepend(const std::list<Type, Allocator> &initial_value) : 
        base(initial_value) {}
        
    //@}

    /** @name Forwarded functions
     *  @details Functions that update the contained accumulator variable are
     *  simply forwarded to the contained @ref op_and_view. 
     */
    //@{

    /// @copydoc op_list_prepend_view::push_front(const Type&)
    void push_front(const Type& element) { view().push_front(element); }
    
    //@}

    /** Allow mutable access to the list within the current view.
     * 
     *  @warning    If this method is called before the parallel calculation is
     *              complete, the list returned by this method will be a partial
     *              result.
     * 
     *  @returns    A mutable reference to the list within the current view.
     */
    list_type &get_reference() { return view().view_get_reference(); }

    /** Allow read-only access to the list within the current view.
     * 
     *  @warning    If this method is called before the parallel calculation is
     *              complete, the list returned by this method will be a partial
     *              result.
     * 
     *  @returns    A const reference to the list within the current view.
     */
    list_type const &get_reference() const { return view().view_get_reference(); }

    /// @name Dereference
    /** Dereferencing a wrapper is a no-op. It simply returns the wrapper.
     *  Combined with the rule that a wrapper forwards view operations to the
     *  view, this means that view operations can be written the same way on
     *  reducers and wrappers, which is convenient for incrementally
     *  converting code using wrappers to code using reducers. That is:
     *
     *      reducer< op_list_prepend<int> > r;
     *      r->push_front(a);    // *r returns the view
     *                           // push_front is a view member function
     *
     *      reducer_list_prepend<int> w;
     *      w->push_front(a);    // *w returns the wrapper
     *                           // push_front is a wrapper member function that
     *                           // calls the corresponding view function
     */
    //@{
    reducer_list_prepend&       operator*()       { return *this; }
    reducer_list_prepend const& operator*() const { return *this; }

    reducer_list_prepend*       operator->()       { return this; }
    reducer_list_prepend const* operator->() const { return this; }
    //@}
    
    /** @name Upcast
     *  @details In Cilk library 0.9, reducers were always cache-aligned. In
     *  library  1.0, reducer cache alignment is optional. By default, reducers
     *  are unaligned (i.e., just naturally aligned), but legacy wrappers
     *  inherit from cache-aligned reducers for binary compatibility.
     *
     *  This means that a wrapper will automatically be upcast to its aligned
     *  reducer base class. The following conversion operators provide
     *  pseudo-upcasts to the corresponding unaligned reducer class.
     */
    //@{
    operator reducer< op_list_prepend<Type, Allocator, false> >& ()
    {
        return *reinterpret_cast<
            reducer< op_list_prepend<Type, Allocator, false> >* 
            >(this);
    }
    operator const reducer< op_list_prepend<Type, Allocator, false> >& () const
    {
        return *reinterpret_cast<
            const reducer< op_list_prepend<Type, Allocator, false> >* 
            >(this);
    }
    //@}
    
};

/// @cond internal

/** Metafunction specialization for reducer conversion.
 *
 *  This specialization of the @ref legacy_reducer_downcast template class
 *  defined in reducer.h causes the `reducer< op_list_append<Type, Allocator> >`
 *  class to have an `operator reducer_list_append<Type, Allocator>& ()`
 *  conversion operator that statically downcasts the `reducer<op_list_append>`
 *  to the corresponding `reducer_list_append` type. (The reverse conversion,
 *  from `reducer_list_append` to `reducer<op_list_append>`, is just an upcast,
 *  which is provided for free by the language.)
 */
template <class Type, class Allocator, bool Align>
struct legacy_reducer_downcast<reducer<op_list_append<Type, Allocator, Align> > >
{
    typedef reducer_list_append<Type, Allocator> type;
};

/** Metafunction specialization for reducer conversion.
 *
 *  This specialization of the @ref legacy_reducer_downcast template class
 *  defined in reducer.h causes the
 *  `reducer< op_list_prepend<Type, Allocator> >` class to have an 
 *  `operator reducer_list_prepend<Type, Allocator>& ()` conversion operator
 *  that statically downcasts the `reducer<op_list_prepend>` to the
 *  corresponding `reducer_list_prepend` type. (The reverse conversion, from
 *  `reducer_list_prepend` to `reducer<op_list_prepend>`, is just an upcast,
 *  which is provided for free by the language.)
 */
template <class Type, class Allocator, bool Align>
struct legacy_reducer_downcast<reducer<op_list_prepend<Type, Allocator, Align> > >
{
    typedef reducer_list_prepend<Type, Allocator> type;
};

/// @endcond

//@}

} // Close namespace cilk

#endif //  REDUCER_LIST_H_INCLUDED