/* Copyright (c) 1997-2006
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
*/

#ifndef _POLYMAKE_ITERATORS_H
#define _POLYMAKE_ITERATORS_H "$Project: polymake $$Id: iterators.h 7459 2006-11-09 11:34:48Z gawrilow $"

#include <functional>
#include <iterator>
#include <limits>

#ifndef _POLYMAKE_TYPE_MANIP_H
#  include <type_manip.h>
#endif
#ifndef _POLYMAKE_PPAIR_H
#  include <ppair.h>
#endif

namespace std {

/** Specialization for inserters.
    Although an XXX_insert_iterator can't be dereferenced,
    it's useful to know in some algorithms what for data it accepts.
    The standard iterator_traits would not provide this information.
*/
template <typename Container>
struct iterator_traits< back_insert_iterator<Container> > {
  typedef output_iterator_tag iterator_category;
  typedef typename Container::value_type value_type;
  typedef void difference_type;
  typedef void pointer;
  typedef void reference;
};

template <typename Container>
struct iterator_traits< front_insert_iterator<Container> > {
  typedef output_iterator_tag iterator_category;
  typedef typename Container::value_type value_type;
  typedef void difference_type;
  typedef void pointer;
  typedef void reference;
};

template <typename Container>
struct iterator_traits< insert_iterator<Container> > {
  typedef output_iterator_tag iterator_category;
  typedef typename Container::value_type value_type;
  typedef void difference_type;
  typedef void pointer;
  typedef void reference;
};
} // end namespace std

namespace pm {

using std::input_iterator_tag;
using std::output_iterator_tag;
using std::forward_iterator_tag;
using std::bidirectional_iterator_tag;
using std::random_access_iterator_tag;

template <typename Iterator,
	  bool _seems_std=
#if _POLYMAKE_ICC_ONLY
             derived_from_instance4<Iterator, std::_Bidit>::value || derived_from_instance4<Iterator, std::_Ranit>::value,
#else
             false,
#endif
	  bool _seems_persistent=
	     derived_from<typename std::iterator_traits<Iterator>::iterator_category, forward_iterator_tag>::value>
struct iterator_cross_const_helper {
   typedef typename Iterator::iterator iterator;
   typedef typename Iterator::const_iterator const_iterator;
};

template <typename Iterator, bool _seems_std>
struct iterator_cross_const_helper<Iterator, _seems_std, false> {
   typedef Iterator iterator;
   typedef Iterator const_iterator;
};

template <typename Iterator>
struct iterator_category_booleans {
   static const bool
      is_forward=
         derived_from<typename std::iterator_traits<Iterator>::iterator_category, forward_iterator_tag>::value,
      is_bidirectional=
         derived_from<typename std::iterator_traits<Iterator>::iterator_category, bidirectional_iterator_tag>::value,
      is_random=
         derived_from<typename std::iterator_traits<Iterator>::iterator_category, random_access_iterator_tag>::value;
};

template <typename Iterator>
struct iterator_traits
   : public std::iterator_traits<Iterator>,
     public iterator_cross_const_helper<Iterator>,
     public iterator_category_booleans<Iterator> {
   typedef Iterator derivable_type;
};

template <typename Iterator, bool _is_rev=iterator_category_booleans<Iterator>::is_bidirectional>
struct default_iterator_reversed {
   typedef void type;
};

template <typename Iterator>
struct default_iterator_reversed<Iterator, true> {
   typedef std::reverse_iterator<Iterator> type;
   static Iterator revert(const type& it) { return it.base(); }
};

template <typename Iterator>
struct iterator_reversed : default_iterator_reversed<Iterator> { };

template <typename Iterator>
struct iterator_reversed< std::reverse_iterator<Iterator> > {
   typedef Iterator type;
   static std::reverse_iterator<Iterator> revert(const type& it) { return std::reverse_iterator<Iterator>(it); }
};

template <typename Iterator1, typename Iterator2>
struct iterator_pair_traits {
   static const bool
      is_forward=
         iterator_traits<Iterator1>::is_forward && iterator_traits<Iterator2>::is_forward,
      is_bidirectional=
         iterator_traits<Iterator1>::is_bidirectional && iterator_traits<Iterator2>::is_bidirectional,
      is_random=
         iterator_traits<Iterator1>::is_random && iterator_traits<Iterator2>::is_random;
};

template <typename Iterator>
struct iterator_traits<Iterator&> : iterator_traits<typename deref<Iterator>::type> { };

template <typename Iterator>
struct iterator_cross_const_helper<std::reverse_iterator<Iterator>, false, true> {
   typedef std::reverse_iterator<typename iterator_traits<Iterator>::iterator> iterator;
   typedef std::reverse_iterator<typename iterator_traits<Iterator>::const_iterator> const_iterator;
};

#if _POLYMAKE_ICC_ONLY
namespace std_nested_iterators {
   enum { unmatched=1 };

   namespace _impl {
      struct bait { };
      size_discriminant<unmatched>::type analyzer_f(...);
   }
   typedef _impl::bait *bait;

   template <typename Iterator, typename Value, int _kind>
   struct extractor
      : iterator_cross_const_helper<Iterator, false, true> { };

   template <typename Iterator, typename Value>
   struct detector
      : extractor<Iterator, Value, sizeof(analyzer_f((Iterator*)0, (Value*)0, (Iterator*)0, bait(0)))> { };
}

template <typename Iterator>
struct iterator_cross_const_helper<Iterator, true, true>
   : std_nested_iterators::detector<Iterator, typename std::iterator_traits<Iterator>::value_type> { };

#endif // _POLYMAKE_ICC_ONLY

template <typename Iterator>
struct alt_constructor {
   typedef typename if_else<identical<Iterator, typename iterator_traits<Iterator>::iterator>::value,
			    Iterator, const typename iterator_traits<Iterator>::iterator>::type
      arg_type;
};

#ifdef __GNUC__

template <typename Iterator, typename Container>
struct iterator_cross_const_helper<__gnu_cxx::__normal_iterator<Iterator, Container>, false, true> {
   typedef __gnu_cxx::__normal_iterator<typename iterator_traits<Iterator>::iterator, Container> iterator;
   typedef __gnu_cxx::__normal_iterator<typename iterator_traits<Iterator>::const_iterator, Container> const_iterator;
};

#endif // __GNUC__

} // end namespace pm

#if defined(__GNUC__) || defined(__COMO__)
namespace std {
   class _Bit_iterator;
   class _Bit_const_iterator;
}

namespace pm {
template <>
struct iterator_cross_const_helper<std::_Bit_iterator, false, true> {
   typedef std::_Bit_iterator iterator;
   typedef std::_Bit_const_iterator const_iterator;
};

template <>
struct iterator_cross_const_helper<std::_Bit_const_iterator, false, true> {
   typedef std::_Bit_iterator iterator;
   typedef std::_Bit_const_iterator const_iterator;
};
} // end namespace pm
#endif

namespace pm {

template <typename Iterator1, typename Iterator2>
struct matching_iterator {
   static const bool value= identical<Iterator1, Iterator2>::value ||
                            identical<typename iterator_traits<Iterator1>::iterator, Iterator2>::value;
};

template <typename Iterator1, typename Iterator2>
struct comparable_iterator {
   static const bool value= identical<typename iterator_traits<Iterator1>::iterator, Iterator2>::value ||
                            identical<typename iterator_traits<Iterator1>::const_iterator, Iterator2>::value;
};

template <typename IteratorList1, typename IteratorList2>
struct matching_iterator_list
   : list_accumulate_binary<list_and, matching_iterator, IteratorList1, IteratorList2> { };

template <typename IteratorList1, typename IteratorList2>
struct comparable_iterator_list
   : list_accumulate_binary<list_and, comparable_iterator, IteratorList1, IteratorList2> { };

/** Wrapper for a pointer used as an iterator.

    Several iterator modifiers defined later derive itself from the corresponding basis iterator.
    A built-in pointer is a valid iterator; however, the C++ syntax rules don't allow inheritance
    from a pointer, since it's not a class.

    This wrapper solves this problem: it behaves exactly the same as a pointer, and is a valid
    base class to be derived from.
*/
template <typename T>
class ptr_wrapper {
public:
   typedef random_access_iterator_tag iterator_category;
   typedef T& reference;
   typedef T* pointer;
   typedef typename deref<T>::type value_type;	// T may have 'const' attribute
   typedef ptrdiff_t difference_type;
   typedef ptr_wrapper<value_type> iterator;
   typedef ptr_wrapper<const value_type> const_iterator;

   ptr_wrapper(pointer cur_arg=0) : cur(cur_arg) { }
   ptr_wrapper(const iterator& it) : cur(it.operator->()) { }

   ptr_wrapper& operator= (pointer cur_arg) { cur=cur_arg; return *this; }
   ptr_wrapper& operator= (const iterator& it) { cur=it.operator->(); return *this; }

   reference operator* () const { return *cur; }
   pointer operator-> () const { return cur; }
   reference operator[] (int i) const { return cur[i]; }

   ptr_wrapper& operator++ () { ++cur; return *this; }
   ptr_wrapper& operator-- () { --cur; return *this; }
   const ptr_wrapper operator++ (int) { ptr_wrapper copy=*this; operator++(); return copy; }
   const ptr_wrapper operator-- (int) { ptr_wrapper copy=*this; operator--(); return copy; }
   ptr_wrapper& operator+= (int i) { cur+=i; return *this; }
   ptr_wrapper& operator-= (int i) { cur-=i; return *this; }
   const ptr_wrapper operator+ (int i) const { return ptr_wrapper(cur+i); }
   const ptr_wrapper operator- (int i) const { return ptr_wrapper(cur-i); }
   friend const ptr_wrapper operator+ (int i, const ptr_wrapper& p) { return ptr_wrapper(p.cur+i); }
   ptrdiff_t operator- (const ptr_wrapper& p) const { return cur-p.cur; }
   ptrdiff_t operator- (const T* x) const { return cur-x; }

   bool operator== (const iterator& p)       const { return cur==p.cur; }
   bool operator!= (const iterator& p)       const { return cur!=p.cur; }
   bool operator<  (const iterator& p)       const { return cur<p.cur; }
   bool operator>  (const iterator& p)       const { return cur>p.cur; }
   bool operator<= (const iterator& p)       const { return cur<=p.cur; }
   bool operator>= (const iterator& p)       const { return cur>=p.cur; }
   bool operator== (const const_iterator& p) const { return cur==p.cur; }
   bool operator!= (const const_iterator& p) const { return cur!=p.cur; }
   bool operator<  (const const_iterator& p) const { return cur<p.cur; }
   bool operator>  (const const_iterator& p) const { return cur>p.cur; }
   bool operator<= (const const_iterator& p) const { return cur<=p.cur; }
   bool operator>= (const const_iterator& p) const { return cur>=p.cur; }

private:
   pointer cur;
};

template <typename T>
struct iterator_traits<T*> : public std::iterator_traits<T*>, public iterator_category_booleans<T*> {
   typedef ptr_wrapper<T> derivable_type;
   typedef typename deref<T>::type* iterator;
   typedef const typename deref<T>::type* const_iterator;
};

template <typename T>
struct alt_constructor<T*> {
   typedef const ptr_wrapper<T> arg_type;
};


template <typename T>
class black_hole {
public:
   typedef output_iterator_tag iterator_category;
   typedef T value_type;
   typedef void reference;
   typedef void pointer;
   typedef void difference_type;

   black_hole& operator++ () { return *this; }
   black_hole& operator++ (int) { return *this; }
   black_hole& operator* () { return *this; }
   black_hole& operator= (typename function_argument<T>::type) { return *this; }
};

template <typename T, typename Counter>
class counting_black_hole : public black_hole<T> {
public:
   counting_black_hole() { }
   counting_black_hole(Counter *counter_arg) : counter(counter_arg) { }

   black_hole<T>& operator++ () { ++(*counter); return *this; }
   black_hole<T>& operator++ (int) { ++(*counter); return *this; }
protected:
   Counter* counter;
};

template <typename Container>
class insert_iterator {
protected:
   Container* container;
public:
   typedef output_iterator_tag iterator_category;
   typedef typename Container::value_type value_type;
   typedef void pointer;
   typedef void reference;
   typedef void difference_type;

   insert_iterator(Container& container_arg) : container(&container_arg) { }

   insert_iterator& operator= (typename function_argument<typename Container::value_type>::type x)
   {
      container->insert(x);
      return *this;
   }

   insert_iterator& operator* () { return *this; }
   insert_iterator& operator++ () { return *this; }
   insert_iterator& operator++ (int) { return *this; }
};

template <typename Container> inline
insert_iterator<Container> inserter(Container& c) { return c; }

struct end_sensitive { };
struct contractable { };
struct rewindable { };
struct indexed { };
struct dense { };
struct sparse_compatible : end_sensitive, indexed { };
struct sparse : sparse_compatible { };
struct pure_sparse : sparse { };

/** Feature of an iterator
    Is true if the data sequence doesn't have any natural limit whatever kind
*/
struct unlimited { };

template <typename Iterator, typename Feature>
struct default_check_iterator_feature : identical<Feature,void> { };

template <typename Iterator>
struct default_check_iterator_feature<Iterator, unlimited> {
   static const bool value=!iterator_traits<Iterator>::is_forward;
};

template <typename Iterator, typename Feature>
struct check_iterator_feature : default_check_iterator_feature<Iterator, Feature> { };

template <typename Iterator, typename Feature>
struct enable_if_iterator : enable_if<void*, check_iterator_feature<Iterator, Feature>::value> { };

template <typename Feature_before, typename Feature_after>
struct feature_allow_order : True { };

template <typename Feature, bool on_top=true> struct provide_construction { };

template <typename Feature_before, bool on_top, typename Feature_after>
struct feature_allow_order< provide_construction<Feature_before, on_top>, Feature_after >
   : feature_allow_order<Feature_before, Feature_after> { };

template <typename Feature_before, typename Feature_after, bool on_top>
struct feature_allow_order< Feature_before, provide_construction<Feature_after, on_top> >
   : feature_allow_order<Feature_before, Feature_after> { };

template <typename Feature_before, bool on_top_before, typename Feature_after, bool on_top_after>
struct feature_allow_order< provide_construction<Feature_before, on_top_before>, provide_construction<Feature_after, on_top_after> >
   : feature_allow_order<Feature_before, Feature_after> { };

template <typename Feature1, typename Feature2>
struct absorbing_feature : derived_from<Feature1,Feature2> { };

template <typename Feature1, bool on_top1, typename Feature2>
struct absorbing_feature< provide_construction<Feature1, on_top1>, Feature2>
   : absorbing_feature<Feature1,Feature2> { };

template <typename Feature1, bool on_top1, typename Feature2, bool on_top2>
struct absorbing_feature< provide_construction<Feature1,on_top1>, provide_construction<Feature2,on_top2> > {
   static const bool value= on_top1>=on_top2 && derived_from<Feature1,Feature2>::value;
};

template <typename Feature, bool on_top>
struct identical< provide_construction<Feature,on_top>, Feature > : True {
   typedef provide_construction<Feature,on_top> type;
};

template <typename Feature, bool on_top>
struct identical< Feature, provide_construction<Feature,on_top> > : True {
   typedef provide_construction<Feature> type;
};

template <typename Iterator>
struct accompanying_iterator {
   typedef typename iterator_traits<Iterator>::derivable_type type;

   static void assign(type& it, const type& other) { it=other;}

   static void advance(type& it, const type&, int n) { std::advance(it, n); }
};

template <typename Iterator>
class rewindable_iterator : public iterator_traits<Iterator>::derivable_type {
protected:
   typedef typename iterator_traits<Iterator>::derivable_type super;
   typename accompanying_iterator<Iterator>::type _begin;

   template <typename> friend class rewindable_iterator;
public:
   typedef rewindable_iterator<typename iterator_traits<Iterator>::iterator> iterator;
   typedef rewindable_iterator<typename iterator_traits<Iterator>::const_iterator> const_iterator;

   rewindable_iterator() { }
   rewindable_iterator(const Iterator& cur_arg)
      : super(cur_arg), _begin(cur_arg) { }
   rewindable_iterator(typename alt_constructor<Iterator>::arg_type& cur_arg)
      : super(cur_arg), _begin(cur_arg) { }

   rewindable_iterator(const iterator& it)
      : super(static_cast<const typename iterator::super&>(it)), _begin(it._begin) { }

   rewindable_iterator& operator= (const iterator& it)
   {
      static_cast<super&>(*this)=it;
      _begin=it._begin;
      return *this;
   }

   rewindable_iterator& operator= (const Iterator& cur)
   {
      static_cast<super&>(*this)=cur;
      return *this;
   }
   rewindable_iterator& operator= (typename alt_constructor<Iterator>::arg_type& cur)
   {
      static_cast<super&>(*this)=cur;
      return *this;
   }

   void rewind()
   {
      accompanying_iterator<Iterator>::assign(static_cast<super&>(*this), _begin);
   }
private:
   void contract1(bool, int distance_front, int, False)
   {
      std::advance(static_cast<super&>(*this), distance_front);
   }
   void contract1(bool renumber, int distance_front, int distance_back, True)
   {
      super::contract(renumber, distance_front, distance_back);
   }
public:
   void contract(bool renumber, int distance_front, int distance_back=0)
   {
      contract1(renumber, distance_front, distance_back, bool2type<check_iterator_feature<super, contractable>::value>());
      _begin=static_cast<const super&>(*this);
   }
};

template <typename Iterator, typename Feature>
struct check_iterator_feature<rewindable_iterator<Iterator>, Feature>
   : check_iterator_feature<Iterator,Feature> { };

template <typename Iterator>
struct check_iterator_feature<rewindable_iterator<Iterator>, rewindable> : True { };

template <typename Iterator>
struct check_iterator_feature<rewindable_iterator<Iterator>, contractable> : True { };

template <typename Iterator>
struct accompanying_iterator< rewindable_iterator<Iterator> > : accompanying_iterator<Iterator> { };

template <typename Iterator>
class iterator_range : public iterator_traits<Iterator>::derivable_type {
protected:
   typedef typename iterator_traits<Iterator>::derivable_type super;
   typedef typename accompanying_iterator<Iterator>::type end_type;

   end_type _end;
   template <typename> friend class iterator_range;
public:
   typedef iterator_range<typename iterator_traits<Iterator>::iterator> iterator;
   typedef iterator_range<typename iterator_traits<Iterator>::const_iterator> const_iterator;

   iterator_range() { }
   iterator_range(const Iterator& cur_arg)
      : super(cur_arg), _end(cur_arg) { }
   iterator_range(const Iterator& cur_arg, const end_type& end_arg)
      : super(cur_arg), _end(end_arg) { }

   iterator_range(typename alt_constructor<Iterator>::arg_type& cur_arg)
      : super(cur_arg), _end(cur_arg) { }
   iterator_range(typename alt_constructor<Iterator>::arg_type& cur_arg, const end_type& end_arg)
      : super(cur_arg), _end(cur_arg) { }
   iterator_range(typename alt_constructor<Iterator>::arg_type& cur_arg, typename alt_constructor<end_type>::arg_type& end_arg)
      : super(cur_arg), _end(end_arg) { }

   iterator_range(const iterator& it)
      : super(static_cast<const typename iterator::super&>(it)), _end(it._end) { }

   iterator_range& operator= (const iterator& it)
   {
      static_cast<super&>(*this)=it;
      _end=it._end;
      return *this;
   }

   iterator_range& operator= (const Iterator& cur)
   {
      static_cast<super&>(*this)=cur;
      return *this;
   }
   iterator_range& operator= (typename alt_constructor<Iterator>::arg_type& cur)
   {
      static_cast<super&>(*this)=cur;
      return *this;
   }

   bool at_end() const { return static_cast<const super&>(*this)==_end; }

   iterator_range& operator++()
   {
      super::operator++(); return *this;
   }
   const iterator_range operator++ (int)
   {
      iterator_range copy=*this; operator++(); return copy;
   }

   iterator_range& operator--()
   {
      typedef typename enable_if<super, iterator_traits<Iterator>::is_bidirectional>::type error_if_unimplemented;
      error_if_unimplemented::operator--(); return *this;
   }
   const iterator_range operator-- (int)
   {
      iterator_range copy=*this; operator--(); return copy;
   }

   iterator_range& operator+= (int i)
   {
      typedef typename enable_if<super, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      error_if_unimplemented::operator+=(i);
      return *this;
   }
   iterator_range& operator-= (int i)
   {
      typedef typename enable_if<super, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      error_if_unimplemented::operator-=(i);
      return *this;
   }

   const iterator_range operator+ (int i) const
   {
      typedef typename enable_if<super, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      return iterator_range(static_cast<const error_if_unimplemented&>(*this)+i, _end);
   }
   const iterator_range operator- (int i) const
   {
      typedef typename enable_if<super, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      return iterator_range(static_cast<const error_if_unimplemented&>(*this)-i, _end);
   }
   friend const iterator_range operator+ (int i, const iterator_range& me)
   {
      typedef typename enable_if<super, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      return iterator_range(static_cast<const error_if_unimplemented&>(me)+i, me._end);
   }

   typename super::difference_type operator- (const super& it) const
   {
      typedef typename enable_if<super, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      return static_cast<const error_if_unimplemented&>(*this)-it;
   }
   typename super::difference_type
   operator- (typename if_else<identical<super,Iterator>::value, super, const Iterator>::type& it) const
   {
      typedef typename enable_if<super, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      return static_cast<const error_if_unimplemented&>(*this)-it;
   }
private:
   void contract1(bool, int distance_front, int, False)
   {
      std::advance(static_cast<super&>(*this), distance_front);
   }
   void contract1(bool renumber, int distance_front, int distance_back, True)
   {
      super::contract(renumber, distance_front, distance_back);
   }
public:
   void contract(bool renumber, int distance_front, int distance_back=0)
   {
      contract1(renumber, distance_front, distance_back, bool2type<check_iterator_feature<super, contractable>::value>());
      accompanying_iterator<Iterator>::advance(_end, static_cast<const super&>(*this), -distance_back);
   }
};

template <typename Iterator, typename Feature>
struct check_iterator_feature<iterator_range<Iterator>, Feature>
   : check_iterator_feature<Iterator,Feature> { };

template <typename Iterator>
struct check_iterator_feature<iterator_range<Iterator>, end_sensitive> : True { };

template <typename Iterator>
struct check_iterator_feature<iterator_range<Iterator>, contractable> : True { };

template <> struct feature_allow_order<end_sensitive,rewindable> : False { };

template <typename Iterator>
struct accompanying_iterator< iterator_range<Iterator> > : accompanying_iterator<Iterator> { };

template <typename Iterator> inline
iterator_range<Iterator>
make_iterator_range(Iterator first, Iterator last)
{
   return iterator_range<Iterator>(first,last);
}

struct manip_container_base { };
template <typename Top, typename Value=typename Top::value_type, bool _is_masquerade_ref=true>
struct constant_container;

namespace object_classifier {
   enum { is_manip=unspecified+1, is_constant };

   namespace _impl {
      size_discriminant<is_manip>::type analyzer_f(const manip_container_base*, bait*);

      template <typename Top, typename Value, bool _is_masquerade_ref>
      size_discriminant<is_constant>::type analyzer_f(const constant_container<Top,Value,_is_masquerade_ref>*, bait*);
   }

   template <typename Container,
             bool _iterator_preserved=identical<typename Container::const_iterator,
					        typename Container::manipulator_impl::const_iterator>::value>
   struct check_begin_end {
      static const int value= _iterator_preserved ? int(is_manip) : int(unspecified);
   };

   template <typename Container>
   struct what_is<Container, is_manip> : check_begin_end<Container> { };

} // end namespace object_classifier

template <>
struct spec_object_traits< int2type<object_classifier::is_manip> >
   : spec_object_traits<is_container> { };

template <>
struct spec_object_traits< int2type<object_classifier::is_constant> >
   : spec_object_traits<is_container> { };

template <typename Container, typename ProvidedFeatures> class manip_feature_collector;

template <typename Container, bool is_const>
struct default_container_elem_traits {
   typedef typename Container::const_reference const_reference;
   typedef typename if_else<is_const, const_reference, typename Container::reference>::type reference;
   typedef typename deref<reference>::type value_type;
};

template <typename Container, bool is_const,
          bool _reversible=iterator_traits<typename Container::iterator>::is_bidirectional>
struct default_container_it_traits : default_container_elem_traits<Container, is_const> {
   typedef typename Container::const_iterator const_iterator;
   typedef typename if_else<is_const, const_iterator, typename Container::iterator>::type iterator;
   typedef typename iterator_traits<iterator>::iterator_category category;
};

template <typename Container, bool is_const>
struct default_container_it_traits<Container, is_const, true>
   : default_container_it_traits<Container, is_const, false> {
   typedef typename Container::const_reverse_iterator const_reverse_iterator;
   typedef typename if_else<is_const, const_reverse_iterator, typename Container::reverse_iterator>::type reverse_iterator;
};

DeclTypedefCHECK(container_category);

template <typename Container, bool is_const,
	  bool _has_category=has_container_category<Container>::value>
struct default_container_traits : default_container_it_traits<Container, is_const> { };

template <typename Container, bool is_const>
struct default_container_traits<Container, is_const, true>
   : default_container_it_traits<Container, is_const,
				 derived_from<typename Container::container_category, bidirectional_iterator_tag>::value> {
   typedef typename Container::container_category category;
};

template <typename ContainerRef>
struct container_traits
   : default_container_traits<typename deref<ContainerRef>::type, attrib<ContainerRef>::is_const>
{
   typedef default_container_traits<typename deref<ContainerRef>::type, attrib<ContainerRef>::is_const> _super;
   static const bool
      is_forward       = derived_from<typename _super::category, forward_iterator_tag>::value,
      is_bidirectional = derived_from<typename _super::category, bidirectional_iterator_tag>::value,
      is_random        = derived_from<typename _super::category, random_access_iterator_tag>::value;
};

template <typename ContainerRef>
struct container_elem_traits
   : default_container_elem_traits<typename deref<ContainerRef>::type, attrib<ContainerRef>::is_const> { };

/* --------------
 *  plain arrays
 * -------------- */

template <typename T>
struct array_traits {
   typedef T& reference;
   typedef const T& const_reference;
   typedef T value_type;
   typedef T* iterator;
   typedef const T* const_iterator;
   typedef std::reverse_iterator<iterator> reverse_iterator;
   typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
   typedef random_access_iterator_tag container_category;
};

template <typename Top, typename E=typename container_traits<Top>::value_type>
class plain_array : public array_traits<E> {
   typedef array_traits<E> _super;
public:
   typename _super::iterator begin()
   {
      return &(static_cast<Top*>(this)->get_data());
   }
   typename _super::iterator end()
   {
      return begin()+static_cast<const Top*>(this)->size();
   }
   typename _super::const_iterator begin() const
   {
      return &(static_cast<const Top*>(this)->get_data());
   }
   typename _super::const_iterator end() const
   {
      return begin()+static_cast<const Top*>(this)->size();
   }

   typename _super::reverse_iterator rbegin()
   {
      return typename _super::reverse_iterator(end());
   }
   typename _super::reverse_iterator rend()
   {
      return typename _super::reverse_iterator(begin());
   }
   typename _super::const_reverse_iterator rbegin() const
   {
      return typename _super::const_reverse_iterator(end());
   }
   typename _super::const_reverse_iterator rend() const
   {
      return typename _super::const_reverse_iterator(begin());
   }

   typename _super::reference front()
   {
      return *begin();
   }
   typename _super::reference back()
   {
      return end()[-1];
   }
   typename _super::reference operator[] (int i)
   {
      return begin()[i];
   }
   typename _super::const_reference front() const
   {
      return *begin();
   }
   typename _super::const_reference back() const
   {
      return end()[-1];
   }
   typename _super::const_reference operator[] (int i) const
   {
      return begin()[i];
   }

   bool empty() const
   {
      return static_cast<const Top*>(this)->size()==0;
   }
};

template <typename T, int _size>
class array_as_container : public plain_array< array_as_container<T,_size>, T> {
protected:
   array_as_container();
   ~array_as_container();
public:
   T& get_data() { return *reinterpret_cast<T*>(this); }
   const T& get_data() const { return *reinterpret_cast<const T*>(this); }
   int size() const { return _size; }
   int max_size() const { return _size; }
};

template <typename T, int _size>
class fixed_array : public plain_array< fixed_array<T,_size>, T> {
   T data[_size];
public:
   T& get_data() { return data[0]; }
   const T& get_data() const { return data[0]; }
   int size() const { return _size; }
   int max_size() const { return _size; }
};

template <typename T>
class dyn_array_as_container : public plain_array< dyn_array_as_container<T>, T> {
protected:
   T* start;
   int _size;
public:
   dyn_array_as_container(T* start_arg, int size_arg) : start(start_arg), _size(size_arg) {}
   dyn_array_as_container(T* start_arg, T* end_arg) : start(start_arg), _size(end_arg-start_arg) {}

   T& get_data() { return *start; }
   const T& get_data() const { return *start; }
   int size() const { return _size; }
   int max_size() const { return _size; }
};

template <typename T, int size> inline
array_as_container<T,size>& array2container(T (&a)[size])
{
   return reinterpret_cast<array_as_container<T,size>&>(a);
}
template <typename T, int size> inline
const array_as_container<T,size>& array2container(const T (&a)[size])
{
   return reinterpret_cast<const array_as_container<T,size>&>(a);
}
template <typename T> inline
dyn_array_as_container<T> array2container(T* start, int size)
{
   return dyn_array_as_container<T>(start,size);
}
template <typename T> inline
dyn_array_as_container<T> array2container(T* start, T* end)
{
   return dyn_array_as_container<T>(start,end);
}

template <typename T>
struct spec_object_traits< array_traits<T> >
   : spec_object_traits<is_container> { };

template <typename T, int size>
struct spec_object_traits< array_as_container<T,size> >
   : spec_object_traits<is_container> { };

template <typename T, int size>
struct spec_object_traits< fixed_array<T,size> >
   : spec_object_traits<is_container> { };

template <typename T>
struct spec_object_traits< dyn_array_as_container<T> >
   : spec_object_traits<is_container> { };

template <typename FeatureList1, typename FeatureList2>
struct mix_features {
   typedef typename concat_list< typename list_search_all<FeatureList1, FeatureList2, absorbing_feature>::negative2,
	   typename concat_list< typename list_search_all<FeatureList2, FeatureList1, absorbing_feature>::negative2,
				 typename list_search_all<FeatureList1, FeatureList2, identical>::positive >::type >::type
      type;
};

template <typename List, typename Feature>
struct min_feature
   : list_logical_or< typename list_search_all<List, Feature, absorbing_feature>::positive, Feature > { };

template <typename FeatureList1, typename FeatureList2>
struct toggle_features {
   typedef typename concat_list< typename list_search_all<FeatureList1, FeatureList2, identical>::negative,
				 typename list_search_all<FeatureList1, FeatureList2, identical>::negative2 >::type
      type;
};

template <typename Container, int kind=object_classifier::what_is<Container>::value>
struct enforce_feature_helper {
   typedef void must_enforce_features;
   typedef void can_enforce_features;
   typedef void cannot_enforce_features;
};

template <typename Container>
struct enforce_feature_helper<Container, object_classifier::is_manip> {
   typedef typename list_search_all<typename Container::expected_features,
				    typename Container::must_enforce_features, absorbing_feature>::negative2
      must_enforce_features;
   typedef typename Container::can_enforce_features can_enforce_features;
   typedef typename Container::cannot_enforce_features cannot_enforce_features;
};

struct checked_via_iterator { };

// to be specialized on the second parameter only
template <typename Container, typename Feature>
struct default_check_container_feature : checked_via_iterator {
   static const bool value=
      check_iterator_feature<typename container_traits<Container>::iterator, Feature>::value &&
      !list_search_all<Feature, typename enforce_feature_helper<Container>::must_enforce_features, absorbing_feature>::value;
};

// can be specialized either on the first parameter or on both
template <typename Container, typename Feature>
struct check_container_feature : default_check_container_feature<Container,Feature> { };

template <typename ContainerRef, typename Feature>
struct check_container_ref_feature : check_container_feature<typename deref<ContainerRef>::type, Feature> { };

template <typename Container, typename Features>
struct check_container_features : check_container_feature<Container, Features> { };

template <typename Container>
struct check_container_features<Container, void> : True { };

template <typename Container, typename Head, typename Tail>
struct check_container_features<Container, cons<Head,Tail> > {
   static const bool value=check_container_features<Container, Head>::value &&
                           check_container_features<Container, Tail>::value;
};

template <typename Feature, typename Container>
struct filter_iterator_features_helper
   : derived_from<default_check_container_feature<Container,Feature>, checked_via_iterator> { };

template <typename Feature, typename Container>
struct filter_iterator_features_helper<provide_construction<Feature,false>, Container> 
   : filter_iterator_features_helper<Feature, Container> { };

template <typename Feature>
struct filter_iterator_features 
   : list_search_all<Feature, array_as_container<int,1>, filter_iterator_features_helper> { };

template <typename Feature>
struct reorder_features_helper {
   typedef Feature type;
};

template <typename Head, typename Tail,
	  typename before=typename list_search_all<Head,Tail,feature_allow_order>::negative2,
	  typename after=typename list_search_all<Head,Tail,feature_allow_order>::positive2>
struct reorder_features_helper2
   : reorder_features_helper< typename concat_list<before, typename concat_list<Head,after>::type >::type > { };

template <typename Head, typename Tail, typename after>
struct reorder_features_helper2<Head, Tail, void, after> {
   typedef cons<Head, typename reorder_features_helper<Tail>::type> type;
};

template <typename Head, typename Tail>
struct reorder_features_helper< cons<Head,Tail> >
   : reorder_features_helper2<Head, Tail> { };

template <typename Features>
struct reorder_features {
   // 'int' here serves just as some inexisting feature
   typedef typename list_search_all<Features,int,feature_allow_order>::positive normal;
   typedef typename list_search_all<Features,int,feature_allow_order>::negative last;
   typedef typename concat_list< typename filter_iterator_features<normal>::negative,
				 typename filter_iterator_features<normal>::positive >::type
      normal_list;
   typedef typename concat_list< typename reorder_features_helper<normal_list>::type, last >::type type;
};

/* Provides a construction (masquerading Container) that will have a desired feature.
   Must be specialized for each enforcible feature. */
template <typename Container, typename Feature>
struct default_enforce_feature;

// Can be specialized for some container classes. Handles exactly one missing feature.
template <typename Container, typename Feature>
struct enforce_feature {
   typedef typename default_enforce_feature<Container,Feature>::container container;
};

// Can be specialized for various container families (according to object_classifier::what_is).
template <typename Container, typename Features, int kind>
struct default_enforce_features
   : enforce_feature<Container,Features> { };

// Can be specialized for some container classes. Handles a list of missing features
template <typename Container, typename Features>
struct enforce_features
   : default_enforce_features<Container, Features, object_classifier::what_is<Container>::value> { };

template <typename Container>
struct default_enforce_feature<Container, void> {
   typedef Container container;
};

template <typename Container, typename Feature, bool on_top>
struct default_enforce_feature<Container, provide_construction<Feature,on_top> >
   : enforce_feature<Container, Feature> { };

template <typename Container, typename Features, typename Lacking>
struct enforce_lacking_features_helper
   : enforce_features<Container,Lacking> { };

template <typename Container, typename Features>
struct enforce_lacking_features_helper<Container, Features, void> {
   typedef Container container;
};

template <typename Container, typename Features>
struct enforce_lacking_features {
   typedef typename list_search_all<Container,Features,check_container_feature>::negative2 lacking;
   typedef typename enforce_lacking_features_helper<Container, Features, lacking>::container container;
};

template <typename Container, typename Head, typename Tail>
struct default_enforce_features<Container, cons<Head,Tail>, object_classifier::unspecified> {
   typedef typename reorder_features< cons<Head,Tail> >::type needed_features;
   typedef typename enforce_feature<Container, typename needed_features::head>::container enforced_head;
   typedef typename enforce_lacking_features<enforced_head, typename needed_features::tail>::container container;
};

template <typename Container, typename Features>
class feature_collector : public enforce_lacking_features<Container, Features>::container {
protected:
   feature_collector();
   ~feature_collector();
};

template <typename Container, typename Features>
struct redirect_object_traits< feature_collector<Container, Features> > : object_traits<Container> { };

template <typename Container, typename ProvidedFeatures, typename Feature>
struct check_container_feature<feature_collector<Container, ProvidedFeatures>, Feature> {
   static const bool value=check_container_feature<Container,Feature>::value ||
                           list_search<ProvidedFeatures, Feature, absorbing_feature>::value;
};

template <typename Container, typename Features>
struct ensure_features_helper {
   typedef typename inherit_const<feature_collector<typename deref<Container>::type, Features>, Container>::type
      container;
};

template <typename Container, typename ProvidedFeatures, typename Features>
struct ensure_features_helper<feature_collector<Container, ProvidedFeatures>, Features>
   : ensure_features_helper<Container, typename mix_features<ProvidedFeatures,Features>::type> { };

template <typename Container, typename ProvidedFeatures, typename Features>
struct ensure_features_helper<const feature_collector<Container, ProvidedFeatures>, Features>
   : ensure_features_helper<const Container, typename mix_features<ProvidedFeatures,Features>::type> { };

template <typename Container, typename Features>
struct ensure_features
   : ensure_features_helper<Container, Features>,
     container_traits<typename ensure_features_helper<Container, Features>::container> { };

template <typename Container, typename Features, bool _reversed=false>
struct ensure_const_helper {
   static const bool preserve_const=
      effectively_const<const Container>::value ||
      identical<typename Container::iterator, typename Container::const_iterator>::value;
   typedef typename assign_const<Container, preserve_const>::type src_container;
   typedef typename assign_const<typename ensure_features<Container, Features>::container, preserve_const>::type container;
   typedef typename if_else< preserve_const,
			     typename ensure_features<Container, Features>::const_iterator,
			     typename ensure_features<Container, Features>::iterator >::type
      iterator;
};

template <typename Container, typename Features>
struct ensure_const_helper<Container, Features, true> : ensure_const_helper<Container, Features, false> {
   typedef ensure_const_helper<Container, Features, false> _super;
   typedef typename if_else< _super::preserve_const,
			     typename ensure_features<Container, Features>::const_reverse_iterator,
			     typename ensure_features<Container, Features>::reverse_iterator >::type
      reverse_iterator;
};

template <typename Container, typename Features> inline
typename ensure_features<Container, Features>::container&
ensure(Container& c, Features*)
{
   return reinterpret_cast<typename ensure_features<Container, Features>::container&>(c);
}

template <typename Container, typename Features> inline
typename ensure_const_helper<Container, Features>::container&
ensure(const Container& c, Features*)
{
   typedef ensure_const_helper<Container, Features> helper;
   return reinterpret_cast<typename helper::container&>(const_cast<typename helper::src_container&>(c));
}

template <typename ContainerRef, typename Features>
struct masquerade_add_features {
   typedef ContainerRef orig_ref;
   typedef typename inherit_ref<typename ensure_features<typename deref<ContainerRef>::minus_ref, Features>::container, ContainerRef>::type type;
};

template <typename ContainerRef, typename Features>
struct deref< masquerade_add_features<ContainerRef, Features> >
   : deref< typename masquerade_add_features<ContainerRef, Features>::type > { };

namespace operations {
struct incomplete {
   typedef void argument_type;
   typedef void first_argument_type;
   typedef void second_argument_type;
   typedef void result_type;
   void operator() () const;
};
}

template <template <typename> class Operation>
struct BuildUnary : operations::incomplete { };

template <template <typename> class Operation>
struct BuildUnaryIt : operations::incomplete { };

template <template <typename,typename> class Operation>
struct BuildBinary : operations::incomplete { };

template <template <typename,typename> class Operation>
struct BuildBinaryIt : operations::incomplete { };

template <typename Operation, typename Iterator, typename Reference=typename iterator_traits<Iterator>::reference>
struct unary_op_builder {
   typedef Operation operation;
   static const operation& create(const Operation& op) { return op; }
};

template <typename Operation>
struct empty_op_builder {
   typedef Operation operation;
   template <typename X>
   static operation create(const X&) { return operation(); }
};

template <template <typename> class Operation, typename Iterator, typename Reference>
struct unary_op_builder<BuildUnary<Operation>, Iterator, Reference>
   : empty_op_builder< Operation<Reference> > { };

template <template <typename> class Operation, typename Iterator, typename Reference>
struct unary_op_builder<BuildUnaryIt<Operation>, Iterator, Reference>
   : empty_op_builder< Operation<const Iterator&> > { };

template <typename Operation, typename Iterator1, typename Iterator2,
	  typename LeftRef=typename iterator_traits<Iterator1>::reference,
	  typename RightRef=typename iterator_traits<Iterator2>::reference>
struct binary_op_builder {
   typedef Operation operation;
   static const operation& create(const Operation& op) { return op; }
};

template <template <typename,typename> class Operation, typename Iterator1, typename Iterator2, typename LeftRef, typename RightRef>
struct binary_op_builder<BuildBinary<Operation>, Iterator1, Iterator2, LeftRef, RightRef>
   : empty_op_builder< Operation<LeftRef, RightRef> > { };

template <template <typename,typename> class Operation, typename Iterator1, typename Iterator2, typename LeftRef, typename RightRef>
struct binary_op_builder<BuildBinaryIt<Operation>, Iterator1, Iterator2, LeftRef, RightRef >
   : empty_op_builder< Operation<const Iterator1&, const Iterator2&> > { };

template <typename T, typename Iterator>
struct value_type_match {
   static const bool value=compatible<typename iterator_traits<Iterator>::reference, T>::value ||
	                   identical<typename object_traits<typename iterator_traits<Iterator>::value_type>::persistent_type,
				     typename object_traits<typename deref<T>::type>::persistent_type
                                    >::value;
};

template <typename Iterator, typename arg_type,
	  bool _not_deref=identical<arg_type,void>::value || derived_from<Iterator, typename deref<arg_type>::type>::value>
struct star_helper {
   typedef const Iterator& result_type;
   static const bool data_arg=true;
   static result_type get(const Iterator& it) { return it; }
};

template <typename Iterator, typename arg_type>
struct star_helper<Iterator, arg_type, true> {
   typedef const Iterator* result_type;
   static const bool data_arg=false;
   static result_type get(const Iterator& it) { return &it; }
};

template <typename Iterator, typename Operation>
struct unary_helper
   : unary_op_builder<Operation, typename iterator_traits<Iterator>::derivable_type> {
   typedef typename iterator_traits<Iterator>::derivable_type it_super;
   typedef star_helper<it_super, typename unary_helper::operation::argument_type> star;
   static const bool data_arg=star::data_arg;
   static typename star::result_type get(const it_super& it) { return star::get(it); }
};

template <typename IteratorPair, typename Operation>
struct binary_helper
   : binary_op_builder<Operation, typename IteratorPair::super, typename IteratorPair::second_type> {
   typedef typename IteratorPair::super it_super;
   typedef typename IteratorPair::second_type it_second;
   typedef binary_op_builder<Operation, it_super, it_second> _super;
   typedef star_helper<it_super, typename _super::operation::first_argument_type> star1;
   typedef star_helper<it_second, typename _super::operation::second_argument_type> star2;
   static const bool first_data_arg=star1::data_arg, second_data_arg=star2::data_arg;
   static typename star1::result_type get1(const it_super& it) { return star1::get(it); }
   static typename star2::result_type get2(const it_second& it) { return star2::get(it); }
};

template <typename Operation, typename IndexOperation, typename Iterator, typename Reference>
struct unary_op_builder<pair<Operation,IndexOperation>, Iterator, Reference>
   : unary_op_builder<Operation, Iterator, Reference> { };

template <typename Iterator, typename Operation, typename IndexOperation>
struct unary_helper<Iterator, pair<Operation,IndexOperation> >
   : unary_helper<Iterator,Operation> { };

template <typename Operation, typename IndexOperation, typename Iterator1, typename Iterator2, 
	  typename Reference1, typename Reference2>
struct binary_op_builder<pair<Operation,IndexOperation>, Iterator1, Iterator2, Reference1, Reference2>
   : binary_op_builder<Operation, Iterator1, Iterator2, Reference1, Reference2> { };

template <typename IteratorPair, typename Operation, typename IndexOperation>
struct binary_helper<IteratorPair, pair<Operation,IndexOperation> >
   : binary_helper<IteratorPair, Operation> { };

template <typename> class Container;
template <typename> class Container1;
template <typename> class Container2;
template <typename> class Operation;
template <typename> class IteratorConstructor;
template <typename> class IteratorCoupler;
template <typename> class Hidden;
typedef Hidden<True> MasqueradedTop;
template <typename> class ExpectedFeatures;
template <typename> class FeaturesViaSecond;
template <typename> class Bijective;
template <typename> class PartiallyDefined;

struct pair_coupler;
template <typename Params=void> struct unary_transform_constructor;
template <typename Params=void> struct binary_transform_constructor;

template <typename IteratorConstructor,
	  bool _try=(derived_from_instance<IteratorConstructor, unary_transform_constructor>::value ||
		     derived_from_instance<IteratorConstructor, binary_transform_constructor>::value)>
struct is_bijective : False { };

template <typename Operation>
struct is_identity_transform : False {
   typedef Operation type;
};

template <typename IteratorConstructor>
struct is_bijective<IteratorConstructor, true> : extract_bool_param<typename IteratorConstructor::params, Bijective, true> { };

template <typename Operation>
struct is_identity_transform< pair<nothing,Operation> > : True {
   typedef Operation type;
};

template <typename Top, typename Params, bool _has_hidden=extract_type_param<Params,Hidden>::specified>
class manip_container_top : public manip_container_base {
public:
   typedef void hidden_type;
   typedef typename extract_type_param<Params, ExpectedFeatures>::type expected_features;
   typedef Top manip_top_type;
   typedef void must_enforce_features;
   typedef void can_enforce_features;
   typedef void cannot_enforce_features;

   Top& top()             { return *static_cast<Top*>(this); }
   const Top& top() const { return *static_cast<const Top*>(this); }
};

template <typename Container, typename ProvidedFeatures, typename Params>
class manip_container_top<manip_feature_collector<Container, ProvidedFeatures>, Params, false>
   : public manip_container_base {
public:
   typedef void hidden_type;
   typedef typename mix_features<typename extract_type_param<Params, ExpectedFeatures>::type, ProvidedFeatures>::type
      expected_features;
   typedef typename Container::manip_top_type manip_top_type;
   typedef void must_enforce_features;
   typedef typename Container::can_enforce_features can_enforce_features;
   typedef typename Container::cannot_enforce_features cannot_enforce_features;

   manip_top_type& top()
   {
      return *static_cast<manip_top_type*>(reinterpret_cast<Container*>(this));
   }
   const manip_top_type& top() const
   {
      return *static_cast<const manip_top_type*>(reinterpret_cast<const Container*>(this));
   }
};

template <typename Top, typename hidden>
struct manip_container_hidden_helper {
   typedef hidden type;
};

template <typename Top>
struct manip_container_hidden_helper<Top, True>
   : extract_template_type_param<Top,0> { };

template <typename Top, typename Params,
	  bool _binary=extract_type_param<Params, Container1>::specified || extract_type_param<Params, Container2>::specified>
class manip_container_hidden_defaults {
public:
   typedef typename manip_container_hidden_helper<Top, typename extract_type_param<Params,Hidden>::type>::type hidden_type;
   typedef typename attrib<typename extract_type_param<Params,Container,hidden_type>::type>::minus_ref container;

   container& get_container()
   {
      return reinterpret_cast<container&>(static_cast<manip_container_top<Top, Params, true>*>(this)->top());
   }
   const container& get_container() const
   {
      return reinterpret_cast<const container&>(static_cast<const manip_container_top<Top, Params, true>*>(this)->top());
   }
};

template <typename Top, typename Params>
class manip_container_hidden_defaults<Top, Params, true> {
public:
   typedef typename manip_container_hidden_helper<Top, typename extract_type_param<Params,Hidden>::type>::type hidden_type;
   typedef typename attrib<typename extract_type_param<Params,Container1,hidden_type>::type>::minus_ref container1;
   typedef typename attrib<typename extract_type_param<Params,Container2,hidden_type>::type>::minus_ref container2;

   container1& get_container1()
   {
      return reinterpret_cast<container1&>(static_cast<manip_container_top<Top, Params, true>*>(this)->top());
   };
   const container1& get_container1() const
   {
      return reinterpret_cast<const container1&>(static_cast<const manip_container_top<Top, Params, true>*>(this)->top());
   }
   container2& get_container2()
   {
      return reinterpret_cast<container2&>(static_cast<manip_container_top<Top, Params, true>*>(this)->top());
   }
   const container2& get_container2() const
   {
      return reinterpret_cast<const container2&>(static_cast<const manip_container_top<Top, Params, true>*>(this)->top());
   }
};

template <typename Top, typename Params>
class manip_container_top<Top, Params, true>
   : public manip_container_top<Top, Params, false>,
     public manip_container_hidden_defaults<Top, Params> {
protected:
   manip_container_top();
   ~manip_container_top();
public:
   typedef typename manip_container_hidden_defaults<Top,Params>::hidden_type hidden_type;

   hidden_type& hidden()
   {
      return reinterpret_cast<hidden_type&>(this->top());
   }
   const hidden_type& hidden() const
   {
      return reinterpret_cast<const hidden_type&>(this->top());
   }
};

template <typename Top, typename Params>
class redirected_container_typebase : public manip_container_top<Top,Params> {
   typedef manip_container_top<Top,Params> _super;
public:
   typedef typename deref<typename extract_type_param<Params, Container, typename _super::hidden_type>::type>::minus_ref container;
   typedef typename _super::expected_features needed_features;
   typedef typename ensure_features<container,needed_features>::iterator iterator;
   typedef typename ensure_features<container,needed_features>::const_iterator const_iterator;
   typedef typename enforce_feature_helper<container>::must_enforce_features must_enforce_features;
   typedef typename enforce_feature_helper<container>::can_enforce_features can_enforce_features;
   typedef typename enforce_feature_helper<container>::cannot_enforce_features cannot_enforce_features;
   typedef typename container_traits<container>::category container_category;
   typedef typename container_traits<container>::value_type value_type;
   typedef typename container_traits<container>::reference reference;
   typedef typename container_traits<container>::const_reference const_reference;
};

template <typename Top, typename Params=typename Top::manipulator_params,
          typename Category=typename redirected_container_typebase<Top,Params>::container_category>
class redirected_container 
   : public redirected_container_typebase<Top,Params> {
   typedef redirected_container_typebase<Top,Params> _super;
public:
   typedef redirected_container<Top,Params> manipulator_impl;
   typedef Params manipulator_params;

   template <typename FeatureCollector>
   struct rebind_feature_collector {
      typedef redirected_container<FeatureCollector,Params> type;
   };

   typename _super::iterator begin()
   {
      const typename _super::container& c=this->top().get_container();
      return ensure(const_cast<typename _super::container&>(c), (typename _super::needed_features*)0).begin();
   }
   typename _super::iterator end()
   {
      const typename _super::container& c=this->top().get_container();
      return ensure(const_cast<typename _super::container&>(c), (typename _super::needed_features*)0).end();
   }
   typename _super::const_iterator begin() const
   {
      return ensure(this->top().get_container(), (typename _super::needed_features*)0).begin();
   }
   typename _super::const_iterator end() const
   {
      return ensure(this->top().get_container(), (typename _super::needed_features*)0).end();
   }

   int size() const { return this->top().get_container().size(); }
   bool empty() const { return this->top().get_container().empty(); }
};

template <typename Top, typename Params>
class redirected_container<Top, Params, forward_iterator_tag>
   : public redirected_container<Top, Params, input_iterator_tag> {
   typedef redirected_container<Top, Params, input_iterator_tag> _super;
public:
   typename _super::reference front()
   {
      return this->top().get_container().front();
   }
   typename _super::const_reference front() const
   {
      return this->top().get_container().front();
   }
};

template <typename Top, typename Params>
class redirected_container<Top, Params, bidirectional_iterator_tag>
   : public redirected_container<Top, Params, forward_iterator_tag> {
   typedef redirected_container<Top, Params, forward_iterator_tag> _super;
public:
   typedef typename ensure_features<typename _super::container, typename _super::needed_features>::reverse_iterator
      reverse_iterator;
   typedef typename ensure_features<typename _super::container, typename _super::needed_features>::const_reverse_iterator
      const_reverse_iterator;

   reverse_iterator rbegin()
   {
      const typename _super::container& c=this->top().get_container();
      return ensure(const_cast<typename _super::container&>(c), (typename _super::needed_features*)0).rbegin();
   }
   reverse_iterator rend()
   {
      const typename _super::container& c=this->top().get_container();
      return ensure(const_cast<typename _super::container&>(c), (typename _super::needed_features*)0).rend();
   }
   const_reverse_iterator rbegin() const
   {
      return ensure(this->top().get_container(), (typename _super::needed_features*)0).rbegin();
   }
   const_reverse_iterator rend() const
   {
      return ensure(this->top().get_container(), (typename _super::needed_features*)0).rend();
   }

   typename _super::reference back()
   {
      return this->top().get_container().back();
   }
   typename _super::const_reference back() const
   {
      return this->top().get_container().back();
   }
};

template <typename Top, typename Params>
class redirected_container<Top, Params, random_access_iterator_tag>
   : public redirected_container<Top, Params, bidirectional_iterator_tag> {
   typedef redirected_container<Top, Params, bidirectional_iterator_tag> _super;
public:
   typename _super::reference operator[] (int i)
   {
      return this->top().get_container()[i];
   }
   typename _super::const_reference operator[] (int i) const
   {
      return this->top().get_container()[i];
   }
};

template <typename Iterator> inline
int count_it(Iterator src)
{
   typename iterator_traits<Iterator>::difference_type cnt=0;
   while (!src.at_end()) {
      ++cnt, ++src;
   }
   return cnt;
}

template <typename Top, typename Typebase, bool _reversible>
class modified_container_non_bijective_elem_access {
public:
   typename Typebase::reference front()
   {
      return *static_cast<Top&>(*this).begin();
   }
   typename Typebase::const_reference front() const
   {
      return *static_cast<const Top&>(*this).begin();
   }

   int size() const
   {
      return count_it(static_cast<const Top&>(*this).begin());
   }
   bool empty() const
   {
      return static_cast<const Top&>(*this).begin().at_end();
   }
};

template <typename Top, typename Typebase>
class modified_container_non_bijective_elem_access<Top, Typebase, true>
   : public modified_container_non_bijective_elem_access<Top, Typebase, false> {
public:
   typename Typebase::reference back()
   {
      return *static_cast<Top&>(*this).rbegin();
   }
   typename Typebase::const_reference back() const
   {
      return *static_cast<const Top&>(*this).rbegin();
   }
};

template <typename Top, typename Params>
class modified_container_typebase
   : public manip_container_top<Top, Params> {
   typedef manip_container_top<Top, Params> _super;
public:
   typedef typename deref<typename extract_type_param<Params, Container, typename _super::hidden_type>::type>::minus_ref
      container;
   typedef typename extract_type_param<Params, Operation>::type operation;
   typedef typename extract_type_param<Params, IteratorConstructor, unary_transform_constructor<> >::type it_constructor;

   typedef typename it_constructor::template defs<typename container_traits<container>::iterator,
						  operation, typename _super::expected_features>::needed_features
      needed_features;
   typedef typename it_constructor::template defs<typename ensure_features<container,needed_features>::iterator,
						  operation, typename _super::expected_features>::iterator
      iterator;
   typedef typename it_constructor::template defs<typename ensure_features<container,needed_features>::const_iterator,
						  operation, typename _super::expected_features>::iterator
      const_iterator;

   typedef typename container_traits<container>::category container_category;
   typedef typename enforce_feature_helper<typename deref<container>::type>::must_enforce_features must_enforce_features;

   typedef typename iterator_traits<iterator>::value_type value_type;
   typedef typename iterator_traits<iterator>::reference reference;
   typedef typename iterator_traits<const_iterator>::reference const_reference;
};

template <typename Top, typename Params>
class reverse_modified_container_typebase {
   typedef modified_container_typebase<Top, Params> _base;
public:
   typedef typename _base::it_constructor::template defs<typename ensure_features<typename _base::container,
										  typename _base::needed_features>::reverse_iterator,
							 typename _base::operation, typename _base::expected_features>::iterator
      reverse_iterator;
   typedef typename _base::it_constructor::template defs<typename ensure_features<typename _base::container,
										  typename _base::needed_features>::const_reverse_iterator,
							 typename _base::operation, typename _base::expected_features>::iterator
      const_reverse_iterator;
};

template <typename Top, typename Params,
          typename Category=typename modified_container_typebase<Top,Params>::container_category,
          bool _bijective=is_bijective<typename modified_container_typebase<Top,Params>::it_constructor>::value,
	  bool _identity=is_identity_transform<typename modified_container_typebase<Top,Params>::operation>::value>
class modified_container_elem_access;

template <typename Top, typename Params=typename Top::manipulator_params,
	  bool _reversible=derived_from<typename modified_container_typebase<Top,Params>::container_category,
					bidirectional_iterator_tag>::value>
class modified_container_impl
   : public modified_container_typebase<Top,Params>,
     public modified_container_elem_access<Top,Params> {
   typedef modified_container_typebase<Top,Params> _super;
public:
   typedef modified_container_impl<Top,Params> manipulator_impl;
   typedef Params manipulator_params;
   typedef typename _super::iterator iterator;
   typedef typename _super::const_iterator const_iterator;

   template <typename FeatureCollector>
   struct rebind_feature_collector {
      typedef modified_container_impl<FeatureCollector,Params> type;
   };

   typename is_identity_transform<typename _super::operation>::type get_operation() const
   {
      return typename is_identity_transform<typename _super::operation>::type();
   }

   iterator begin()
   {
      const typename _super::container& c=this->top().get_container();
      return iterator(ensure(const_cast<typename _super::container&>(c), (typename _super::needed_features*)0).begin(),
		      this->top().get_operation());
   }
   iterator end()
   {
      const typename _super::container& c=this->top().get_container();
      return iterator(ensure(const_cast<typename _super::container&>(c), (typename _super::needed_features*)0).end(),
		      this->top().get_operation());
   }
   const_iterator begin() const
   {
      return const_iterator(ensure(this->top().get_container(), (typename _super::needed_features*)0).begin(),
			    this->top().get_operation());
   }
   const_iterator end() const
   {
      return const_iterator(ensure(this->top().get_container(), (typename _super::needed_features*)0).end(),
			    this->top().get_operation());
   }
};

template <typename Top, typename Params>
class modified_container_impl<Top, Params, true>
   : public modified_container_impl<Top, Params, false>,
     public reverse_modified_container_typebase<Top, Params> {
   typedef modified_container_impl<Top,Params,false> _super;
   typedef reverse_modified_container_typebase<Top, Params> _rbase;
public:
   typename _rbase::reverse_iterator rbegin()
   {
      const typename _super::container& c=this->top().get_container();
      return typename _rbase::reverse_iterator(ensure(const_cast<typename _super::container&>(c),
						      (typename _super::needed_features*)0).rbegin(),
					       this->top().get_operation());
   }
   typename _rbase::reverse_iterator rend()
   {
      const typename _super::container& c=this->top().get_container();
      return typename _rbase::reverse_iterator(ensure(const_cast<typename _super::container&>(c),
						      (typename _super::needed_features*)0).rend(),
					       this->top().get_operation());
   }
   typename _rbase::const_reverse_iterator rbegin() const
   {
      return typename _rbase::const_reverse_iterator(ensure(this->top().get_container(),
							    (typename _super::needed_features*)0).rbegin(),
						     this->top().get_operation());
   }
   typename _rbase::const_reverse_iterator rend() const
   {
      return typename _rbase::const_reverse_iterator(ensure(this->top().get_container(),
							    (typename _super::needed_features*)0).rend(),
						     this->top().get_operation());
   }
};

template <typename Top, typename Params, typename Category, bool _bijective, bool _identity>
class modified_container_elem_access {
   typedef modified_container_typebase<Top,Params> _base;
protected:
   typename _base::manip_top_type& _top()
   {
      return static_cast<modified_container_impl<Top,Params>*>(this)->top();
   }
   const typename _base::manip_top_type& _top() const
   {
      return static_cast<const modified_container_impl<Top,Params>*>(this)->top();
   }
public:
   int size() const
   {
      return _top().get_container().size();
   }
   int dim() const
   {
      return get_dim(_top().get_container());
   }
   bool empty() const
   {
      return _top().get_container().empty();
   }
};

template <typename Top, typename Params>
class modified_container_elem_access<Top, Params, forward_iterator_tag, true, false>
   : public modified_container_elem_access<Top, Params, input_iterator_tag, true, false> {
   typedef modified_container_typebase<Top,Params> _base;

   typename _base::reference _front(const typename _base::iterator::operation& op, True)
   {
      return op(this->_top().get_container().front());
   }
   typename _base::const_reference _front(const typename _base::const_iterator::operation& op, True) const
   {
      return op(this->_top().get_container().front());
   }
   typename _base::reference _front(const typename _base::iterator::operation& op, False)
   {
      return op(this->_top().get_container().begin());
   }
   typename _base::const_reference _front(const typename _base::const_iterator::operation& op, False) const
   {
      return op(this->_top().get_container().begin());
   }
public:
   typename _base::reference front()
   {
      typedef typename _base::iterator::helper opb;
      return _front(opb::create(this->_top().get_operation()), bool2type<opb::data_arg>());
   }
   typename _base::const_reference front() const
   {
      typedef typename _base::const_iterator::helper opb;
      return _front(opb::create(this->_top().get_operation()), bool2type<opb::data_arg>());
   }
};

template <typename Top, typename Params>
class modified_container_elem_access<Top, Params, forward_iterator_tag, true, true>
   : public modified_container_elem_access<Top, Params, input_iterator_tag, true, true> {
   typedef modified_container_typebase<Top,Params> _base;
public:
   typename _base::reference front()
   {
      return this->_top().get_container().front();
   }
   typename _base::const_reference front() const
   {
      return this->_top().get_container().front();
   }
};

template <typename Top, typename Params>
class modified_container_elem_access<Top, Params, bidirectional_iterator_tag, true, false>
   : public modified_container_elem_access<Top, Params, forward_iterator_tag, true, false> {
   typedef modified_container_typebase<Top,Params> _base;
   typedef reverse_modified_container_typebase<Top,Params> _rbase;

   typename _base::reference _back(const typename _rbase::reverse_iterator::operation& op, True)
   {
      return op(this->_top().get_container().back());
   }
   typename _base::const_reference _back(const typename _rbase::const_reverse_iterator::operation& op, True) const
   {
      return op(this->_top().get_container().back());
   }
   typename _base::reference _back(const typename _rbase::reverse_iterator::operation& op, False)
   {
      return op(this->_top().get_container().rbegin());
   }
   typename _base::const_reference _back(const typename _rbase::const_reverse_iterator::operation& op, False) const
   {
      return op(this->_top().get_container().rbegin());
   }
public:
   typename _base::reference back()
   {
      typedef typename _rbase::reverse_iterator::helper opb;
      return _back(opb::create(this->_top().get_operation()), bool2type<opb::data_arg>());
   }
   typename _base::const_reference back() const
   {
      typedef typename _rbase::const_reverse_iterator::helper opb;
      return _back(opb::create(this->_top().get_operation()), bool2type<opb::data_arg>());
   }
};

template <typename Top, typename Params>
class modified_container_elem_access<Top, Params, bidirectional_iterator_tag, true, true>
   : public modified_container_elem_access<Top, Params, forward_iterator_tag, true, true> {
   typedef modified_container_typebase<Top,Params> _base;
public:
   typename _base::reference back()
   {
      return this->_top().get_container().back();
   }
   typename _base::const_reference back() const
   {
      return this->_top().get_container().back();
   }
};

template <typename Top, typename Params>
class modified_container_elem_access<Top, Params, random_access_iterator_tag, true, false>
   : public modified_container_elem_access<Top, Params, bidirectional_iterator_tag, true, false> {
   typedef modified_container_typebase<Top,Params> _base;

   typename _base::reference _random(int i, const typename _base::iterator::operation& op, True)
   {
      return op(this->_top().get_container()[i]);
   }
   typename _base::const_reference _random(int i, const typename _base::const_iterator::operation& op, True) const
   {
      return op(this->_top().get_container()[i]);
   }
   typename _base::reference _random(int i, const typename _base::iterator::operation& op, False)
   {
      return op(this->_top().get_container().begin() + i);
   }
   typename _base::const_reference _random(int i, const typename _base::const_iterator::operation& op, False) const
   {
      return op(this->_top().get_container().begin() + i);
   }
public:
   typename _base::reference operator[] (int i)
   {
      typedef typename _base::iterator::helper opb;
      return _random(i, opb::create(this->_top().get_operation()), bool2type<opb::data_arg>());
   }
   typename _base::const_reference operator[] (int i) const
   {
      typedef typename _base::const_iterator::helper opb;
      return _random(i, opb::create(this->_top().get_operation()), bool2type<opb::data_arg>());
   }
};

template <typename Top, typename Params>
class modified_container_elem_access<Top, Params, random_access_iterator_tag, true, true>
   : public modified_container_elem_access<Top, Params, bidirectional_iterator_tag, true, true> {
   typedef modified_container_typebase<Top,Params> _base;
public:
   typename _base::reference operator[] (int i)
   {
      return this->_top().get_container()[i];
   }
   typename _base::const_reference operator[] (int i) const
   {
      return this->_top().get_container()[i];
   }
};

template <typename Top, typename Params, typename Category>
class modified_container_elem_access<Top, Params, Category, false, false>
   : public modified_container_non_bijective_elem_access<Top, modified_container_typebase<Top,Params>,
							 derived_from<Category, bidirectional_iterator_tag>::value> { };

template <typename Top, typename Params>
class container_pair_typebase : public manip_container_top<Top, Params> {
   typedef manip_container_top<Top, Params> _super;
public:
   typedef typename extract_type_param<Params,Container1>::type container1_ref;
   typedef typename extract_type_param<Params,Container2>::type container2_ref;
   typedef typename deref<container1_ref>::minus_ref container1;
   typedef typename deref<container2_ref>::minus_ref container2;

   typedef typename extract_type_param<Params, IteratorCoupler, pair_coupler>::type it_coupler;
   typedef typename it_coupler::template defs<typename container_traits<container1>::iterator,
					      typename container_traits<container2>::iterator,
					      typename _super::expected_features>::needed_features1
      needed_features1;
   typedef typename it_coupler::template defs<typename container_traits<container1>::iterator,
					      typename container_traits<container2>::iterator,
					      typename _super::expected_features>::needed_features2
      needed_features2;
   typedef typename it_coupler::template defs<typename ensure_features<container1,needed_features1>::iterator,
					      typename ensure_features<container2,needed_features2>::iterator,
					      typename _super::expected_features>::iterator
      iterator;
   typedef typename it_coupler:: template defs<typename ensure_features<container1,needed_features1>::const_iterator,
					       typename ensure_features<container2,needed_features2>::const_iterator,
					       typename _super::expected_features>::iterator
      const_iterator;

   typedef typename least_derived< cons<typename container_traits<container1>::category,
					typename container_traits<container2>::category> >::type
      container_category;
   typedef typename mix_features<typename enforce_feature_helper<typename deref<container1>::type>::must_enforce_features,
				 typename enforce_feature_helper<typename deref<container2>::type>::must_enforce_features>::type
      must_enforce_features;

   typedef typename iterator_traits<iterator>::value_type value_type;
   typedef typename iterator_traits<iterator>::reference reference;
   typedef typename iterator_traits<const_iterator>::reference const_reference;
};

template <typename IteratorCoupler> struct reverse_coupler {
   typedef IteratorCoupler type;
};

template <typename Top, typename Params>
class reverse_container_pair_typebase {
   typedef container_pair_typebase<Top, Params> _base;
   typedef typename reverse_coupler<typename _base::it_coupler>::type rev_it_coupler;
public:
   typedef typename rev_it_coupler::template defs<typename ensure_features<typename _base::container1,
									   typename _base::needed_features1>::reverse_iterator,
						  typename ensure_features<typename _base::container2,
									   typename _base::needed_features2>::reverse_iterator,
						  typename _base::expected_features>::iterator
      reverse_iterator;
   typedef typename rev_it_coupler::template defs<typename ensure_features<typename _base::container1,
									   typename _base::needed_features1>::const_reverse_iterator,
						  typename ensure_features<typename _base::container2,
									   typename _base::needed_features2>::const_reverse_iterator,
						  typename _base::expected_features>::iterator
      const_reverse_iterator;
};

template <typename Top, typename Params=typename Top::manipulator_params,
          typename Category=typename container_pair_typebase<Top,Params>::container_category>
class container_pair_impl
   : public container_pair_typebase<Top,Params> {
   typedef container_pair_typebase<Top,Params> _super;
   int _size(False) const { return this->top().get_container1().size(); }
   int _size(True) const { return this->top().get_container2().size(); }
   int _dim(False) const { return get_dim(this->top().get_container1()); }
   int _dim(True) const { return get_dim(this->top().get_container2()); }
   bool _empty(False) const { return this->top().get_container1().empty(); }
   bool _empty(True) const { return this->top().get_container2().empty(); }

   typedef bool2type<object_classifier::what_is<typename deref<typename _super::container1>::type>::value
                     == object_classifier::is_constant>
      discr;
public:
   typedef container_pair_impl<Top,Params> manipulator_impl;
   typedef Params manipulator_params;
   typedef typename _super::iterator iterator;
   typedef typename _super::const_iterator const_iterator;

   template <typename FeatureCollector>
   struct rebind_feature_collector {
      typedef container_pair_impl<FeatureCollector,Params> type;
   };

   iterator begin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      const typename _super::container2& c2=this->top().get_container2();
      return iterator(ensure(const_cast<typename _super::container1&>(c1), (typename _super::needed_features1*)0).begin(),
		      ensure(const_cast<typename _super::container2&>(c2), (typename _super::needed_features2*)0).begin());
   }
   iterator end()
   {
      const typename _super::container1& c1=this->top().get_container1();
      const typename _super::container2& c2=this->top().get_container2();
      return iterator(ensure(const_cast<typename _super::container1&>(c1), (typename _super::needed_features1*)0).end(),
		      ensure(const_cast<typename _super::container2&>(c2), (typename _super::needed_features2*)0).end());
   }
   const_iterator begin() const
   {
      return const_iterator(ensure(this->top().get_container1(), (typename _super::needed_features1*)0).begin(),
			    ensure(this->top().get_container2(), (typename _super::needed_features2*)0).begin());
   }
   const_iterator end() const
   {
      return const_iterator(ensure(this->top().get_container1(), (typename _super::needed_features1*)0).end(),
			    ensure(this->top().get_container2(), (typename _super::needed_features2*)0).end());
   }

   int size() const { return _size(discr()); }
   int dim() const { return _dim(discr()); }
   bool empty() const { return _empty(discr()); }
};

template <typename Top, typename Params>
class container_pair_impl<Top, Params, forward_iterator_tag>
   : public container_pair_impl<Top, Params, input_iterator_tag> {
   typedef container_pair_impl<Top, Params, input_iterator_tag> _super;
public:
   typename _super::reference front()
   {
      return this->top().get_container1().front();
   }
   typename _super::const_reference front() const
   {
      return this->top().get_container1().front();
   }
};

template <typename Top, typename Params>
class container_pair_impl<Top, Params, bidirectional_iterator_tag>
   : public container_pair_impl<Top, Params, forward_iterator_tag>,
     public reverse_container_pair_typebase<Top, Params> {
   typedef container_pair_impl<Top, Params, forward_iterator_tag> _super;
   typedef reverse_container_pair_typebase<Top, Params> _rbase;
public:
   typename _rbase::reverse_iterator rbegin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      const typename _super::container2& c2=this->top().get_container2();
      return typename _rbase::reverse_iterator(ensure(const_cast<typename _super::container1&>(c1),
						      (typename _super::needed_features1*)0).rbegin(),
					       ensure(const_cast<typename _super::container2&>(c2),
						      (typename _super::needed_features2*)0).rbegin());
   }
   typename _rbase::reverse_iterator rend()
   {
      const typename _super::container1& c1=this->top().get_container1();
      const typename _super::container2& c2=this->top().get_container2();
      return typename _rbase::reverse_iterator(ensure(const_cast<typename _super::container1&>(c1),
						      (typename _super::needed_features1*)0).rend(),
					       ensure(const_cast<typename _super::container2&>(c2),
						      (typename _super::needed_features2*)0).rend());
   }
   typename _rbase::const_reverse_iterator rbegin() const
   {
      return typename _rbase::const_reverse_iterator(ensure(this->top().get_container1(),
							    (typename _super::needed_features1*)0).rbegin(),
						     ensure(this->top().get_container2(),
							    (typename _super::needed_features2*)0).rbegin());
   }
   typename _rbase::const_reverse_iterator rend() const
   {
      return typename _rbase::const_reverse_iterator(ensure(this->top().get_container1(),
							    (typename _super::needed_features1*)0).rend(),
						     ensure(this->top().get_container2(),
							    (typename _super::needed_features2*)0).rend());
   }

   typename _super::reference back()
   {
      return this->top().get_container1().back();
   }
   typename _super::const_reference back() const
   {
      return this->top().get_container1().back();
   }
};

template <typename Top, typename Params>
class container_pair_impl<Top, Params, random_access_iterator_tag>
   : public container_pair_impl<Top, Params, bidirectional_iterator_tag> {
   typedef container_pair_impl<Top, Params, bidirectional_iterator_tag> _super;
public:
   typename _super::reference operator[] (int i)
   {
      return this->top().get_container1()[i];
   }
   typename _super::const_reference operator[] (int i) const
   {
      return this->top().get_container1()[i];
   }
};

template <typename Top, typename Params>
class modified_container_pair_typebase
   : public manip_container_top<Top, Params> {
   typedef manip_container_top<Top, Params> _super;
public:
   typedef typename deref<typename extract_type_param<Params, Container1>::type>::minus_ref container1;
   typedef typename deref<typename extract_type_param<Params, Container2>::type>::minus_ref container2;

   typedef typename extract_type_param<Params, Operation>::type operation;
   typedef typename extract_type_param<Params, IteratorCoupler, pair_coupler>::type it_coupler;
   typedef typename it_coupler::template defs<typename container_traits<container1>::iterator,
					      typename container_traits<container2>::iterator, void>
      coupler_defs;
   typedef typename extract_type_param<Params, IteratorConstructor, binary_transform_constructor<> >::type it_constructor;

   typedef typename it_constructor::template defs<typename coupler_defs::iterator, operation, typename _super::expected_features>
      first_try_defs;
   typedef typename first_try_defs::needed_pair_features needed_pair_features;

   typedef typename mix_features<typename it_coupler::template defs<typename container_traits<container1>::iterator,
								    typename container_traits<container2>::iterator,
								    needed_pair_features>::needed_features1,
				 typename first_try_defs::needed_features1>::type
      needed_features1;
   typedef typename mix_features<typename it_coupler::template defs<typename container_traits<container1>::iterator,
								    typename container_traits<container2>::iterator,
								    needed_pair_features>::needed_features2,
				 typename first_try_defs::needed_features2>::type
      needed_features2;
   typedef typename it_coupler::template defs<typename ensure_features<container1,needed_features1>::iterator,
					      typename ensure_features<container2,needed_features2>::iterator,
					      needed_pair_features>::iterator
      it_pair;
   typedef typename it_coupler::template defs<typename ensure_features<container1,needed_features1>::const_iterator,
					      typename ensure_features<container2,needed_features2>::const_iterator,
					      needed_pair_features>::iterator
      const_it_pair;
   typedef typename it_constructor::template defs<it_pair, operation, typename _super::expected_features>::iterator
      iterator;
   typedef typename it_constructor::template defs<const_it_pair, operation, typename _super::expected_features>::iterator
      const_iterator;

   typedef typename least_derived< cons<typename container_traits<container1>::category,
					typename container_traits<container2>::category> >::type
      container_category;
   typedef typename mix_features<typename enforce_feature_helper<typename deref<container1>::type>::must_enforce_features,
				 typename enforce_feature_helper<typename deref<container2>::type>::must_enforce_features>::type
      must_enforce_features;

   typedef typename iterator_traits<iterator>::value_type value_type;
   typedef typename iterator_traits<iterator>::reference reference;
   typedef typename iterator_traits<const_iterator>::reference const_reference;
};

template <typename Top, typename Params>
class reverse_modified_container_pair_typebase {
   typedef modified_container_pair_typebase<Top, Params> _base;
   typedef typename reverse_coupler<typename _base::it_coupler>::type rev_it_coupler;
public:
   typedef typename rev_it_coupler::template defs<typename ensure_features<typename _base::container1,
									   typename _base::needed_features1>::reverse_iterator,
						  typename ensure_features<typename _base::container2,
									   typename _base::needed_features2>::reverse_iterator,
						  typename _base::needed_pair_features>::iterator
      reverse_it_pair;
   typedef typename rev_it_coupler::template defs<typename ensure_features<typename _base::container1,
									   typename _base::needed_features1>::const_reverse_iterator,
						  typename ensure_features<typename _base::container2,
									   typename _base::needed_features2>::const_reverse_iterator,
						  typename _base::needed_pair_features>::iterator
      const_reverse_it_pair;
   typedef typename _base::it_constructor::template defs<reverse_it_pair, typename _base::operation,
							 typename _base::expected_features>::iterator
      reverse_iterator;
   typedef typename _base::it_constructor::template defs<const_reverse_it_pair, typename _base::operation,
							 typename _base::expected_features>::iterator
      const_reverse_iterator;
};

template <typename Top, typename Params,
          typename Category=typename modified_container_pair_typebase<Top,Params>::container_category,
          bool _bijective=is_bijective<typename modified_container_pair_typebase<Top,Params>::it_constructor>::value,
	  bool _identity=is_identity_transform<typename modified_container_pair_typebase<Top,Params>::operation>::value>
class modified_container_pair_elem_access;

template <typename Top, typename Params=typename Top::manipulator_params,
          bool _reversible=derived_from<typename modified_container_pair_typebase<Top,Params>::container_category,
					bidirectional_iterator_tag>::value>
class modified_container_pair_impl
   : public modified_container_pair_typebase<Top,Params>,
     public modified_container_pair_elem_access<Top,Params> {
   typedef modified_container_pair_typebase<Top,Params> _super;
public:
   typedef modified_container_pair_impl<Top,Params> manipulator_impl;
   typedef Params manipulator_params;
   typedef typename _super::iterator iterator;
   typedef typename _super::const_iterator const_iterator;

   template <typename FeatureCollector>
   struct rebind_feature_collector {
      typedef modified_container_pair_impl<FeatureCollector,Params> type;
   };

   typename is_identity_transform<typename _super::operation>::type get_operation() const
   {
      return typename is_identity_transform<typename _super::operation>::type();
   }

   iterator begin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      const typename _super::container2& c2=this->top().get_container2();
      return iterator(ensure(const_cast<typename _super::container1&>(c1), (typename _super::needed_features1*)0).begin(),
		      ensure(const_cast<typename _super::container2&>(c2), (typename _super::needed_features2*)0).begin(),
		      this->top().get_operation());
   }
   iterator end()
   {
      const typename _super::container1& c1=this->top().get_container1();
      const typename _super::container2& c2=this->top().get_container2();
      return iterator(ensure(const_cast<typename _super::container1&>(c1), (typename _super::needed_features1*)0).end(),
		      ensure(const_cast<typename _super::container2&>(c2), (typename _super::needed_features2*)0).end(),
		      this->top().get_operation());
   }
   const_iterator begin() const
   {
      return const_iterator(ensure(this->top().get_container1(), (typename _super::needed_features1*)0).begin(),
			    ensure(this->top().get_container2(), (typename _super::needed_features2*)0).begin(),
			    this->top().get_operation());
   }
   const_iterator end() const
   {
      return const_iterator(ensure(this->top().get_container1(), (typename _super::needed_features1*)0).end(),
			    ensure(this->top().get_container2(), (typename _super::needed_features2*)0).end(),
			    this->top().get_operation());
   }
};

template <typename Top, typename Params>
class modified_container_pair_impl<Top, Params, true>
   : public modified_container_pair_impl<Top, Params, false>,
     public reverse_modified_container_pair_typebase<Top, Params> {
   typedef modified_container_pair_impl<Top, Params, false> _super;
   typedef reverse_modified_container_pair_typebase<Top, Params> _rbase;
public:
   typename _rbase::reverse_iterator rbegin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      const typename _super::container2& c2=this->top().get_container2();
      return typename _rbase::reverse_iterator(ensure(const_cast<typename _super::container1&>(c1),
						      (typename _super::needed_features1*)0).rbegin(),
					       ensure(const_cast<typename _super::container2&>(c2),
						      (typename _super::needed_features2*)0).rbegin(),
					       this->top().get_operation());
   }
   typename _rbase::reverse_iterator rend()
   {
      const typename _super::container1& c1=this->top().get_container1();
      const typename _super::container2& c2=this->top().get_container2();
      return typename _rbase::reverse_iterator(ensure(const_cast<typename _super::container1&>(c1),
						      (typename _super::needed_features1*)0).rend(),
					       ensure(const_cast<typename _super::container2&>(c2),
						      (typename _super::needed_features2*)0).rend(),
					       this->top().get_operation());
   }
   typename _rbase::const_reverse_iterator rbegin() const
   {
      return typename _rbase::const_reverse_iterator(ensure(this->top().get_container1(),
							    (typename _super::needed_features1*)0).rbegin(),
						     ensure(this->top().get_container2(),
							    (typename _super::needed_features2*)0).rbegin(),
						     this->top().get_operation());
   }
   typename _rbase::const_reverse_iterator rend() const
   {
      return typename _rbase::const_reverse_iterator(ensure(this->top().get_container1(),
							    (typename _super::needed_features1*)0).rend(),
						     ensure(this->top().get_container2(),
							    (typename _super::needed_features2*)0).rend(),
						     this->top().get_operation());
   }
};

template <typename Top, typename Params, typename Category, bool _bijective, bool _identity>
class modified_container_pair_elem_access {
   typedef modified_container_pair_typebase<Top,Params> _base;
protected:
   typename _base::manip_top_type& _top()
   {
      return static_cast<modified_container_pair_impl<Top,Params>*>(this)->top();
   }
   const typename _base::manip_top_type& _top() const
   {
      return static_cast<const modified_container_pair_impl<Top,Params>*>(this)->top();
   }
private:
   int _size(False) const { return _top().get_container1().size(); }
   int _size(True) const { return _top().get_container2().size(); }
   int _dim(False) const { return get_dim(_top().get_container1()); }
   int _dim(True) const { return get_dim(_top().get_container2()); }
   bool _empty(False) const { return _top().get_container1().empty(); }
   bool _empty(True) const { return _top().get_container2().empty(); }

   typedef bool2type<object_classifier::what_is<typename deref<typename _base::container1>::type>::value
                     == object_classifier::is_constant>
      discr;
public:
   int size() const { return _size(discr()); }
   int dim() const { return _dim(discr()); }
   bool empty() const { return _empty(discr()); }
};

template <typename Top, typename Params>
class modified_container_pair_elem_access<Top, Params, forward_iterator_tag, true, false>
   : public modified_container_pair_elem_access<Top, Params, input_iterator_tag, true, false> {
   typedef modified_container_pair_typebase<Top, Params> _base;

   typename _base::reference _front(const typename _base::iterator::operation& op, cons<True, True>)
   {
      return op(this->_top().get_container1().front(),
		this->_top().get_container2().front());
   }
   typename _base::const_reference _front(const typename _base::const_iterator::operation& op, cons<True, True>) const
   {
      return op(this->_top().get_container1().front(),
		this->_top().get_container2().front());
   }
   typename _base::reference _front(const typename _base::iterator::operation& op, cons<False, True>)
   {
      return op(this->_top().get_container1().begin(),
		this->_top().get_container2().front());
   }
   typename _base::const_reference _front(const typename _base::const_iterator::operation& op, cons<False, True>) const
   {
      return op(this->_top().get_container1().begin(),
		this->_top().get_container2().front());
   }
   typename _base::reference _front(const typename _base::iterator::operation& op, cons<True, False>)
   {
      return op(this->_top().get_container1().front(),
		this->_top().get_container2().begin());
   }
   typename _base::const_reference _front(const typename _base::const_iterator::operation& op, cons<True, False>) const
   {
      return op(this->_top().get_container1().front(),
		this->_top().get_container2().begin());
   }
   typename _base::reference _front(const typename _base::iterator::operation& op, cons<False, False>)
   {
      return op(this->_top().get_container1().begin(),
		this->_top().get_container2().begin());
   }
   typename _base::const_reference _front(const typename _base::const_iterator::operation& op, cons<False, False>) const
   {
      return op(this->_top().get_container1().begin(),
		this->_top().get_container2().begin());
   }
public:
   typename _base::reference front()
   {
      typedef typename _base::iterator::helper opb;
      return _front(opb::create(this->_top().get_operation()),
		    cons< bool2type<opb::first_data_arg>, bool2type<opb::second_data_arg> >());
   }
   typename _base::const_reference front() const
   {
      typedef typename _base::const_iterator::helper opb;
      return _front(opb::create(this->_top().get_operation()),
		    cons< bool2type<opb::first_data_arg>, bool2type<opb::second_data_arg> >());
   }
};

template <typename Top, typename Params>
class modified_container_pair_elem_access<Top, Params, forward_iterator_tag, true, true>
   : modified_container_pair_elem_access<Top, Params, input_iterator_tag, true, true> {
   typedef modified_container_pair_typebase<Top, Params> _base;
public:
   typename _base::reference front()
   {
      return this->_top().get_container1().front();
   }
   typename _base::const_reference front() const
   {
      return this->_top().get_container1().front();
   }
};

template <typename Top, typename Params>
class modified_container_pair_elem_access<Top, Params, bidirectional_iterator_tag, true, false>
   : public modified_container_pair_elem_access<Top, Params, forward_iterator_tag, true, false> {
   typedef modified_container_pair_typebase<Top, Params> _base;
   typedef reverse_modified_container_pair_typebase<Top, Params> _rbase;

   typename _base::reference _back(const typename _rbase::reverse_iterator::operation& op, cons<True, True>)
   {
      return op(this->_top().get_container1().back(),
		this->_top().get_container2().back());
   }
   typename _base::const_reference _back(const typename _rbase::const_reverse_iterator::operation& op, cons<True, True>) const
   {
      return op(this->_top().get_container1().back(),
		this->_top().get_container2().back());
   }
   typename _base::reference _back(const typename _rbase::reverse_iterator::operation& op, cons<False, True>)
   {
      return op(this->_top().get_container1().rbegin(),
		this->_top().get_container2().back());
   }
   typename _base::const_reference _back(const typename _rbase::const_reverse_iterator::operation& op, cons<False, True>) const
   {
      return op(this->_top().get_container1().rbegin(),
		this->_top().get_container2().back());
   }
   typename _base::reference _back(const typename _rbase::reverse_iterator::operation& op, cons<True, False>)
   {
      return op(this->_top().get_container1().back(),
		this->_top().get_container2().rbegin());
   }
   typename _base::const_reference _back(const typename _rbase::const_reverse_iterator::operation& op, cons<True, False>) const
   {
      return op(this->_top().get_container1().back(),
		this->_top().get_container2().rbegin());
   }
   typename _base::reference _back(const typename _rbase::reverse_iterator::operation& op, cons<False, False>)
   {
      return op(this->_top().get_container1().rbegin(),
		this->_top().get_container2().rbegin());
   }
   typename _base::const_reference _back(const typename _rbase::const_reverse_iterator::operation& op, cons<False, False>) const
   {
      return op(this->_top().get_container1().rbegin(),
		this->_top().get_container2().rbegin());
   }
public:
   typename _base::reference back()
   {
      typedef typename _rbase::reverse_iterator::helper opb;
      return _back(opb::create(this->_top().get_operation()),
		   cons< bool2type<opb::first_data_arg>, bool2type<opb::second_data_arg> >());
   }
   typename _base::const_reference back() const
   {
      typedef typename _rbase::const_reverse_iterator::helper opb;
      return _back(opb::create(this->_top().get_operation()),
		   cons< bool2type<opb::first_data_arg>, bool2type<opb::second_data_arg> >());
   }
};

template <typename Top, typename Params>
class modified_container_pair_elem_access<Top, Params, bidirectional_iterator_tag, true, true>
   : public modified_container_pair_elem_access<Top, Params, forward_iterator_tag, true, true> {
   typedef modified_container_pair_typebase<Top, Params> _base;
public:
   typename _base::reference back()
   {
      return this->_top().get_container1().back();
   }
   typename _base::const_reference back() const
   {
      return this->_top().get_container1().back();
   }
};

template <typename Top, typename Params>
class modified_container_pair_elem_access<Top, Params, random_access_iterator_tag, true, false>
   : public modified_container_pair_elem_access<Top, Params, bidirectional_iterator_tag, true, false> {
   typedef modified_container_pair_typebase<Top, Params> _base;

   typename _base::reference _random(int i, const typename _base::iterator::operation& op, cons<True, True>)
   {
      return op(this->_top().get_container1()[i],
		this->_top().get_container2()[i]);
   }
   typename _base::const_reference _random(int i, const typename _base::const_iterator::operation& op, cons<True, True>) const
   {
      return op(this->_top().get_container1()[i],
		this->_top().get_container2()[i]);
   }
   typename _base::reference _random(int i, const typename _base::iterator::operation& op, cons<False, True>)
   {
      return op(this->_top().get_container1().begin()+i,
		this->_top().get_container2()[i]);
   }
   typename _base::const_reference _random(int i, const typename _base::const_iterator::operation& op, cons<False, True>) const
   {
      return op(this->_top().get_container1().begin()+i,
		this->_top().get_container2()[i]);
   }
   typename _base::reference _random(int i, const typename _base::iterator::operation& op, cons<True, False>)
   {
      return op(this->_top().get_container1()[i],
		this->_top().get_container2().begin()+i);
   }
   typename _base::const_reference _random(int i, const typename _base::const_iterator::operation& op, cons<True, False>) const
   {
      return op(this->_top().get_container1()[i],
		this->_top().get_container2().begin()+i);
   }
   typename _base::reference _random(int i, const typename _base::iterator::operation& op, cons<False, False>)
   {
      return op(this->_top().get_container1().begin()+i,
		this->_top().get_container2().begin()+i);
   }
   typename _base::const_reference _random(int i, const typename _base::const_iterator::operation& op, cons<False, False>) const
   {
      return op(this->_top().get_container1().begin()+i,
		this->_top().get_container2().begin()+i);
   }
public:
   typename _base::reference operator[] (int i)
   {
      typedef typename _base::iterator::helper opb;
      return _random(i, opb::create(this->_top().get_operation()),
		     cons< bool2type<opb::first_data_arg>, bool2type<opb::second_data_arg> >());
   }
   typename _base::const_reference operator[] (int i) const
   {
      typedef typename _base::const_iterator::helper opb;
      return _random(i, opb::create(this->_top().get_operation()),
		     cons< bool2type<opb::first_data_arg>, bool2type<opb::second_data_arg> >());
   }
};

template <typename Top, typename Params>
class modified_container_pair_elem_access<Top, Params, random_access_iterator_tag, true, true>
   : public modified_container_pair_elem_access<Top, Params, bidirectional_iterator_tag, true, true> {
   typedef modified_container_pair_typebase<Top, Params> _base;
public:
   typename _base::reference operator[] (int i)
   {
      return this->_top().get_container1()[i];
   }
   typename _base::const_reference operator[] (int i) const
   {
      return this->_top().get_container1()[i];
   }
};

template <typename Top, typename Params, typename Category>
class modified_container_pair_elem_access<Top, Params, Category, false, false>
   : public modified_container_non_bijective_elem_access<Top, modified_container_pair_typebase<Top,Params>,
							 derived_from<Category, bidirectional_iterator_tag>::value> { };

template <typename Container, typename ProvidedFeatures>
class manip_feature_collector
   : public Container::template rebind_feature_collector< manip_feature_collector<Container, ProvidedFeatures> >::type {
protected:
   manip_feature_collector();
   ~manip_feature_collector();
};

template <typename Container, typename Features>
struct manip_feature_collector_helper {
   typedef manip_feature_collector<Container, Features> container;
};
template <typename Container, typename PrevFeatures, typename Features>
struct manip_feature_collector_helper<manip_feature_collector<Container,PrevFeatures>, Features> {
   typedef manip_feature_collector<Container, typename concat_list<PrevFeatures,Features>::type> container;
};
template <typename Container>
struct manip_feature_collector_helper<Container,void> {
   typedef Container container;
};
template <typename Container, typename PrevFeatures>	// resolving ambiguity
struct manip_feature_collector_helper<manip_feature_collector<Container,PrevFeatures>, void> {
   typedef manip_feature_collector<Container,PrevFeatures> container;
};

template <typename Container, typename Features>
struct default_enforce_features<Container, Features, object_classifier::is_manip> {
   typedef typename list_search_all<Features, int, feature_allow_order>::negative after1;
   typedef typename list_search_all<Features, int, feature_allow_order>::positive not_last;
   typedef typename list_search_all<not_last, typename Container::cannot_enforce_features, absorbing_feature>::positive
      after2;
   typedef typename list_search_all<not_last, typename Container::cannot_enforce_features, absorbing_feature>::negative
      not_after;
   typedef typename list_search_all<not_after, typename Container::can_enforce_features, identical>::positive
      via_manip1;
   typedef typename filter_iterator_features<typename list_search_all<not_after, typename Container::can_enforce_features, identical>::negative>::positive
      via_manip2;
   typedef typename concat_list<via_manip1,via_manip2>::type via_manip;
   typedef typename list_search_all<not_after, via_manip, identical>::negative before;
   typedef typename concat_list<after2,after1>::type after;

   typedef typename default_enforce_features<Container, before, object_classifier::unspecified>::container
      enforced_before;
   typedef typename manip_feature_collector_helper<enforced_before, via_manip>::container enforced_via_manip;
   typedef typename default_enforce_features<enforced_via_manip, after, object_classifier::unspecified>::container
      container;
};

template <typename Container,
	  bool _reversible=container_traits<Container>::is_bidirectional>
class construct_rewindable
   : public enable_if<Container, container_traits<Container>::is_forward>::type {
protected:
   construct_rewindable();
   ~construct_rewindable();
public:
   typedef rewindable_iterator<typename Container::iterator> iterator;
   typedef rewindable_iterator<typename Container::const_iterator> const_iterator;

   iterator begin() { return Container::begin(); }
   iterator end() { return Container::end(); }
   const_iterator begin() const { return Container::begin(); }
   const_iterator end() const { return Container::end(); }
};

template <typename Container>
class construct_rewindable<Container, true>
   : public construct_rewindable<Container, false> {
public:
   typedef rewindable_iterator<typename Container::reverse_iterator> reverse_iterator;
   typedef rewindable_iterator<typename Container::const_reverse_iterator> const_reverse_iterator;

   reverse_iterator rbegin() { return Container::rbegin(); }
   reverse_iterator rend() { return Container::rend(); }
   const_reverse_iterator rbegin() const { return Container::rbegin(); }
   const_reverse_iterator rend() const { return Container::rend(); }
};

template <typename Container, bool _reversible>
struct redirect_object_traits< construct_rewindable<Container,_reversible> > : object_traits<Container> { };

template <typename Container>
struct end_sensitive_helper {
   typedef Container end_source;
};

template <typename Container, bool _reversible>
struct end_sensitive_helper<construct_rewindable<Container,_reversible> > {
   typedef Container end_source;
};

template <typename Container,
          bool _reversible=container_traits<Container>::is_bidirectional>
class construct_end_sensitive : public Container {
protected:
   construct_end_sensitive();
   ~construct_end_sensitive();

   typedef typename end_sensitive_helper<Container>::end_source end_source;
public:
   typedef iterator_range<typename Container::iterator> iterator;
   typedef iterator_range<typename Container::const_iterator> const_iterator;

   iterator begin() { return iterator(Container::begin(), end_source::end()); }
   iterator end() { return iterator(Container::end()); }
   const_iterator begin() const { return const_iterator(Container::begin(), end_source::end()); }
   const_iterator end() const { return const_iterator(Container::end()); }
};

template <typename Container>
class construct_end_sensitive<Container, true>
   : public construct_end_sensitive<Container, false> {
   typedef construct_end_sensitive<Container, false> _super;
public:
   typedef iterator_range<typename Container::reverse_iterator> reverse_iterator;
   typedef iterator_range<typename Container::const_reverse_iterator> const_reverse_iterator;

   reverse_iterator rbegin()
   {
      typedef typename _super::end_source end_source;
      return reverse_iterator(Container::rbegin(), end_source::rend());
   }
   reverse_iterator rend()
   {
      return reverse_iterator(Container::rend());
   }
   const_reverse_iterator rbegin() const
   {
      typedef typename _super::end_source end_source;
      return const_reverse_iterator(Container::rbegin(), end_source::rend());
   }
   const_reverse_iterator rend() const
   {
      return const_reverse_iterator(Container::rend());
   }
};

template <typename Container, bool _reversible>
struct redirect_object_traits< construct_end_sensitive<Container,_reversible> > : object_traits<Container> { };

template <typename Container>
struct default_enforce_feature<Container, rewindable> {
   typedef construct_rewindable<Container> container;
};

template <typename Container>
struct default_enforce_feature<Container, end_sensitive> {
   typedef construct_end_sensitive<Container> container;
};

template <typename Container, typename Feature, bool on_top>
struct default_check_container_feature<Container, provide_construction<Feature,on_top> > : False { };

template <typename Container>
struct Entire : ensure_features<Container, end_sensitive> { };

template <typename Container> inline
typename Entire<typename Concrete<Container>::type>::iterator
entire(Container& c)
{
   return ensure(Concrete<Container>::get(c), (end_sensitive*)0).begin();
}

template <typename Container> inline
typename ensure_const_helper<typename Concrete<Container>::type, end_sensitive>::iterator
entire(const Container& c)
{
   return ensure(Concrete<Container>::get(c), (end_sensitive*)0).begin();
}

template <typename Container> inline
typename Entire<typename Concrete<Container>::type>::reverse_iterator
rentire(Container& c)
{
   return ensure(Concrete<Container>::get(c), (end_sensitive*)0).rbegin();
}

template <typename Container> inline
typename ensure_const_helper<typename Concrete<Container>::type, end_sensitive, true>::reverse_iterator
rentire(const Container& c)
{
   return ensure(Concrete<Container>::get(c), (end_sensitive*)0).rbegin();
}

template <typename ContainerRef, typename Operation>
class modified_container_base {
protected:
   alias<ContainerRef> src;
   typedef typename is_identity_transform<Operation>::type operation_type;
   operation_type op;
public:
   typedef typename alias<ContainerRef>::arg_type arg_type;

   modified_container_base(arg_type src_arg, const operation_type& op_arg)
      : src(src_arg), op(op_arg) { }

   typename alias<ContainerRef>::reference get_container() { return src; }
   typename alias<ContainerRef>::const_reference get_container() const { return src; }
   const operation_type& get_operation() const { return op; }
};

template <typename ContainerRef1, typename ContainerRef2, bool coherent=false>
class container_pair_base {
protected:
   typedef typename if_else<coherent && effectively_const<ContainerRef2>::value,
			    typename attrib<ContainerRef1>::plus_const, ContainerRef1>::type
      Ref1;
   typedef typename if_else<coherent && effectively_const<ContainerRef1>::value,
			    typename attrib<ContainerRef2>::plus_const, ContainerRef2>::type
      Ref2;
   alias<Ref1> src1;
   alias<Ref2> src2;
public:
   typedef typename alias<Ref1>::arg_type first_arg_type;
   typedef typename alias<Ref2>::arg_type second_arg_type;

   container_pair_base(first_arg_type src1_arg, second_arg_type src2_arg)
      : src1(src1_arg), src2(src2_arg) { }

   typename alias<Ref1>::reference get_container1() { return src1; }
   typename alias<Ref2>::reference get_container2() { return src2; }
   typename alias<Ref1>::const_reference get_container1() const { return src1; }
   typename alias<Ref2>::const_reference get_container2() const { return src2; }
};

template <typename ContainerRef1, typename ContainerRef2, typename Operation>
class modified_container_pair_base
   : public container_pair_base<ContainerRef1, ContainerRef2> {
   typedef container_pair_base<ContainerRef1, ContainerRef2> _super;
protected:
   typedef typename is_identity_transform<Operation>::type operation_type;
   operation_type op;
public:
   modified_container_pair_base(typename _super::first_arg_type src1_arg,
				typename _super::second_arg_type src2_arg,
				const operation_type& op_arg)
      : _super(src1_arg,src2_arg), op(op_arg) { }

   const operation_type& get_operation() const { return op; }
};

struct _reversed { };

template <typename Container,
	  bool _random=container_traits<Container>::is_random>
class construct_reversed {
   Container& hidden() { return reinterpret_cast<Container&>(*this); }
   const Container& hidden() const { return reinterpret_cast<const Container&>(*this); }
public:
   typedef typename container_traits<Container>::value_type value_type;
   typedef typename container_traits<Container>::reference reference;
   typedef typename container_traits<Container>::const_reference const_reference;
   typedef typename container_traits<Container>::category container_category;

   typedef typename container_traits<Container>::reverse_iterator iterator;
   typedef typename container_traits<Container>::const_reverse_iterator const_iterator;
   typedef typename container_traits<Container>::iterator reverse_iterator;
   typedef typename container_traits<Container>::const_iterator const_reverse_iterator;

   iterator begin() { return hidden().rbegin(); }
   iterator end() { return hidden().rend(); }
   const_iterator begin() const { return hidden().rbegin(); }
   const_iterator end() const { return hidden().rend(); }
   reverse_iterator rbegin() { return hidden().begin(); }
   reverse_iterator rend() { return hidden().end(); }
   const_reverse_iterator rbegin() const { return hidden().begin(); }
   const_reverse_iterator rend() const { return hidden().end(); }

   reference front() { return hidden().back(); }
   reference back() { return hidden().front(); }
   const_reference front() const { return hidden().back(); }
   const_reference back() const { return hidden().front(); }

   int size() const { return hidden().size(); }
   int dim() const { return get_dim(hidden()); }
   bool empty() const { return hidden().empty(); }
};

template <typename Container>
class construct_reversed<Container, true>
   : public construct_reversed<Container,false> {
   typedef construct_reversed<Container,false> _super;
public:
   typename _super::reference operator[] (int i)
   {
      return (_super::hidden())[this->size()-1-i];
   }

   typename _super::const_reference operator[] (int i) const
   {
      return (_super::hidden())[this->size()-1-i];
   }
};

template <typename Container>
struct default_check_container_feature<Container, _reversed> : False { };

template <typename Container>
struct default_enforce_feature<Container, _reversed> {
   typedef construct_reversed<Container> container;
};

template <typename Feature>
struct feature_allow_order<_reversed,Feature> : False { };

template <typename Container, bool _random>
struct redirect_object_traits< construct_reversed<Container,_random> >
   : spec_object_traits<Container> { };

template <typename Container, bool _random, typename Feature>
struct check_container_feature<construct_reversed<Container,_random>, Feature>
   : check_container_feature<Container,Feature> { };

template <typename Container, bool _random>
struct check_container_feature<construct_reversed<Container,_random>, _reversed> : True { };

template <typename Container, bool _random, typename Features>
struct enforce_features<construct_reversed<Container,_random>, Features> {
   typedef construct_reversed<typename enforce_features<Container,Features>::container> container;
};

template <typename Container> inline
typename ensure_features<Container,_reversed>::container&
reversed(Container& c)
{
   return reinterpret_cast<typename ensure_features<Container,_reversed>::container&>(c);
}

template <typename Container> inline
const typename ensure_features<Container,_reversed>::container&
reversed(const Container& c)
{
   return reinterpret_cast<const typename ensure_features<Container,_reversed>::container&>(c);
}

template <typename Value, bool _assignable=false, bool _simple=is_pod<Value>::value>
class op_value_cache {
   Value *value;
   std::allocator<Value> alloc;

public:
   op_value_cache() : value(0) { }

   op_value_cache(const op_value_cache& op)
   {
      if (_assignable && op.value) {
	 value=alloc.allocate(1);
	 new(value) Value(*op.value);
      } else {
	 value=0;
      }
   }

   op_value_cache(typename function_argument<Value>::type arg)
   {
      value=alloc.allocate(1);
      new(value) Value(arg);
   }

   ~op_value_cache()
   {
      if (value) {
	 alloc.destroy(value);
	 alloc.deallocate(value,1);
      }
   }

   op_value_cache& operator= (const op_value_cache& op)
   {
      if (_assignable) {
	 if (value) {
	    alloc.destroy(value);
	    if (op.value) {
	       new(value) Value(*op.value);
	    } else {
	       alloc.deallocate(value,1);
	       value=0;
	    }
	 } else if (op.value) {
	    value=alloc.allocate(1);
	    new(value) Value(*op.value);
	 }
      }
      return *this;
   }

   Value& operator= (Value arg)
   {
      if (value)
	 alloc.destroy(value);
      else
	 value=alloc.allocate(1);
      new(value) Value(arg);
      return *value;
   }

   Value& get() { return *value; }
   const Value& get() const { return *value; }
};

template <typename Value, bool _assignable>
class op_value_cache<Value, _assignable, true> {
   Value value;
public:
   op_value_cache() { }
   op_value_cache(typename function_argument<Value>::type arg)
      : value(arg) { }

   Value& operator= (Value arg)
   {
      value=arg;
      return value;
   }

   op_value_cache& operator= (const op_value_cache& op)
   {
      if (_assignable) value=op.value;
      return *this;
   }

   Value& get() { return value; }
   const Value& get() const { return value; }
};

template <typename ResultRef, bool _need_proxy=!attrib<ResultRef>::is_reference>
struct arrow_helper {
   typedef typename attrib<ResultRef>::minus_ref *pointer;

   template <typename Iterator>
   static pointer get(const Iterator& it) { return &(*it); }
};

template <typename Result>
struct arrow_helper<Result, true> {
   class pointer {
      template <typename,bool> friend class arrow_helper;
      typedef typename deref<Result>::type value_type;
      value_type value;

      template <typename Iterator>
      pointer(const Iterator& it) : value(*it) { }
   public:
      value_type* operator->() { return &value; }
   };

   template <typename Iterator>
   static pointer get(const Iterator& it) { return it; }
};

template <typename Iterator, typename Operation>
class unary_transform_eval : public iterator_traits<Iterator>::derivable_type {
protected:
   typedef typename iterator_traits<Iterator>::derivable_type super;
public:
   typedef unary_helper<Iterator,Operation> helper;
   typedef typename helper::operation operation;
protected:
   operation op;

   typedef Operation op_arg_type;

   unary_transform_eval() { }

   template <typename Operation2>
   unary_transform_eval(const unary_transform_eval<typename iterator_traits<Iterator>::iterator, Operation2>& it)
      : super(it),
	op(helper::create(it.op)) { }

   template <typename Operation2>
   unary_transform_eval(const unary_transform_eval<typename iterator_reversed<Iterator>::type, Operation2>& it)
      : super(iterator_reversed<Iterator>::revert(it)),
	op(helper::create(it.op)) { }

   unary_transform_eval(const Iterator& cur_arg, const op_arg_type& op_arg)
      : super(cur_arg), op(helper::create(op_arg)) { }
   unary_transform_eval(typename alt_constructor<Iterator>::arg_type& cur_arg, const op_arg_type& op_arg)
      : super(cur_arg), op(helper::create(op_arg)) { }

   template <typename,typename> friend class unary_transform_eval;
public:
   typedef typename operation::result_type reference;

   reference operator* () const
   {
      return op(*helper::get(*this));
   }

   typedef typename arrow_helper<reference>::pointer pointer;
   pointer operator-> () const
   {
      return arrow_helper<reference>::get(*this);
   }
};

template <typename Iterator, typename Operation, typename IndexOperation>
class unary_transform_eval<Iterator, pair<Operation, IndexOperation> >
   : public unary_transform_eval<Iterator, Operation> {
   typedef unary_transform_eval<Iterator, Operation> _super;
protected:
   typedef unary_helper<Iterator,IndexOperation> ihelper;
   typename ihelper::operation iop;

   typedef pair<Operation, IndexOperation> op_arg_type;

   unary_transform_eval() { }

   template <typename Operation2, typename IndexOperation2>
   unary_transform_eval(const unary_transform_eval<typename iterator_traits<Iterator>::iterator,
			                           pair<Operation2, IndexOperation2> >& it)
      : _super(it),
	iop(ihelper::create(it.iop)) { }

   template <typename Operation2, typename IndexOperation2>
   unary_transform_eval(const unary_transform_eval<typename iterator_reversed<Iterator>::type, pair<Operation2, IndexOperation2> >& it)
      : _super(it),
	iop(ihelper::create(it.op)) { }

   unary_transform_eval(const Iterator& cur_arg, const op_arg_type& op_arg)
      : _super(cur_arg, op_arg.first),
	iop(ihelper::create(op_arg.second)) { }
   unary_transform_eval(typename alt_constructor<Iterator>::arg_type& cur_arg, const op_arg_type& op_arg)
      : _super(cur_arg, op_arg.first),
	iop(ihelper::create(op_arg.second)) { }

   template <typename,typename> friend class unary_transform_eval;
public:
   int index() const
   {
      return iop(*ihelper::get(*this));
   }
};

template <typename Iterator, typename IndexOperation>
class unary_transform_eval<Iterator, pair<nothing, IndexOperation> >
   : public iterator_traits<Iterator>::derivable_type {
protected:
   typedef typename iterator_traits<Iterator>::derivable_type super;

   typedef unary_helper<Iterator,IndexOperation> ihelper;
   typename ihelper::operation iop;

   typedef IndexOperation op_arg_type;

   unary_transform_eval() { }

   template <typename IndexOperation2>
   unary_transform_eval(const unary_transform_eval<typename iterator_traits<Iterator>::iterator,
			                           pair<nothing, IndexOperation2> >& it)
      : super(it),
	iop(ihelper::create(it.iop)) { }

   template <typename IndexOperation2>
   unary_transform_eval(const unary_transform_eval<typename iterator_reversed<Iterator>::type, pair<nothing, IndexOperation2> >& it)
      : super(it),
	iop(ihelper::create(it.op)) { }

   unary_transform_eval(const Iterator& cur_arg, const op_arg_type& op_arg)
      : super(cur_arg),
	iop(ihelper::create(op_arg)) { }
   unary_transform_eval(typename alt_constructor<Iterator>::arg_type& cur_arg, const op_arg_type& op_arg)
      : super(cur_arg),
	iop(ihelper::create(op_arg)) { }

   template <typename,typename> friend class unary_transform_eval;
public:
   int index() const
   {
      return iop(*ihelper::get(*this));
   }
};

template <typename Iterator, typename Operation>
class unary_transform_iterator
   : public unary_transform_eval<Iterator, Operation> {
   typedef unary_transform_eval<Iterator, Operation> _super;
protected:
   typedef typename _super::super super;
public:
   typedef typename deref<typename _super::reference>::type value_type;
   typedef unary_transform_iterator<typename iterator_traits<Iterator>::iterator, Operation>
      iterator;
   typedef unary_transform_iterator<typename iterator_traits<Iterator>::const_iterator, Operation>
      const_iterator;

   unary_transform_iterator() { }

   template <typename Operation2>
   unary_transform_iterator(const unary_transform_iterator<typename iterator_traits<Iterator>::iterator, Operation2>& it)
      : _super(it) { }

   template <typename Operation2>
   explicit unary_transform_iterator(const unary_transform_iterator<typename iterator_reversed<Iterator>::type, Operation2>& it)
      : _super(it) { }

   unary_transform_iterator(const Iterator& cur_arg,
			    const typename _super::op_arg_type& op_arg=typename _super::op_arg_type())
      : _super(cur_arg,op_arg) { }

   unary_transform_iterator& operator++ ()
   {
      super::operator++(); return *this;
   }
   const unary_transform_iterator operator++ (int)
   {
      unary_transform_iterator copy=*this;  operator++();  return copy;
   }

   unary_transform_iterator& operator-- ()
   {
      typedef typename enable_if<super, iterator_traits<Iterator>::is_bidirectional>::type error_if_unimplemented;
      error_if_unimplemented::operator--(); return *this;
   }
   const unary_transform_iterator operator-- (int)
   {
      unary_transform_iterator copy=*this;  operator--();  return copy;
   }

   unary_transform_iterator& operator+= (int i)
   {
      typedef typename enable_if<super, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      error_if_unimplemented::operator+=(i);
      return *this;
   }
   unary_transform_iterator& operator-= (int i)
   {
      typedef typename enable_if<super, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      error_if_unimplemented::operator-=(i);
      return *this;
   }
   const unary_transform_iterator operator+ (int i) const
   {
      typedef typename enable_if<unary_transform_iterator, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      error_if_unimplemented copy=*this;  return copy+=i;
   }
   const unary_transform_iterator operator- (int i) const
   {
      typedef typename enable_if<unary_transform_iterator, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      error_if_unimplemented copy=*this; return copy-=i;
   }
   friend const unary_transform_iterator operator+ (int i, const unary_transform_iterator& me)
   {
      return me+i;
   }

   typename super::difference_type
   operator- (const iterator& it) const 
   {
      typedef typename enable_if<super, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      return static_cast<const error_if_unimplemented&>(*this) - it;
   }
   typename super::difference_type
   operator- (typename assign_const<const_iterator, !identical<iterator,const_iterator>::value>::type& it) const
   {
      typedef typename enable_if<super, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      return static_cast<const error_if_unimplemented&>(*this) - it;
   }

protected:
   typename _super::reference _random(int i, True) const
   {
      return this->op(super::operator[](i));
   }
   typename _super::reference _random(int i, False) const
   {
      return this->op(static_cast<const super&>(*this) + i);
   }
public:
   typename _super::reference operator[] (int i) const
   {
      typedef typename enable_if<typename _super::helper, iterator_traits<Iterator>::is_random>::type error_if_unimplemented;
      return _random(i, bool2type<error_if_unimplemented::data_arg>());
   }
};

template <typename Iterator, typename Operation, typename Feature>
struct check_iterator_feature<unary_transform_iterator<Iterator, Operation>, Feature>
   : check_iterator_feature<Iterator, Feature> { };

template <typename Iterator, typename Operation>
struct check_iterator_feature<unary_transform_iterator<Iterator, Operation>, indexed> {
   static const bool value=is_instance2_of<Operation,pair>::value ||
                           check_iterator_feature<Iterator,indexed>::value;
};

template <typename Iterator, typename Operation> inline
unary_transform_iterator<Iterator,Operation>
make_unary_transform_iterator(Iterator it, const Operation& op)
{
   return unary_transform_iterator<Iterator,Operation>(it,op);
}

template <typename Params>
struct unary_transform_constructor {
   typedef Params params;
   template <typename Iterator, typename Operation, typename ExpectedFeatures>
   struct defs {
      typedef typename if_else<is_instance2_of<Operation,pair>::value,
			       typename list_search_all<ExpectedFeatures, indexed, identical>::negative,
			       ExpectedFeatures>::type
         needed_features;
      typedef unary_transform_iterator<Iterator, Operation> iterator;
   };
};

template <typename Container>
struct default_check_container_feature<Container, sparse>
   : check_container_feature<Container, pure_sparse> { };

template <typename Container>
struct default_check_container_feature<Container, sparse_compatible>
   : check_container_feature<Container, sparse> { };

template <typename Container>
struct default_check_container_feature<Container, pure_sparse> : False { };

template <typename Container>
struct default_check_container_feature<Container, dense> {
   static const bool value=!check_container_feature<Container, sparse>::value;
};

template <typename Container>
int get_dim(const Container& c, True)
{
   return c.dim();
}
template <typename Container>
int get_dim(const Container& c, False)
{
   return c.size();
}
template <typename Container>
int get_dim(const Container& c)
{
   return get_dim(c, bool2type<check_container_feature<Container,sparse_compatible>::value>());
}

/* -----------------------------------------------------
 *  unlimited_constant_container, single_elem_container
 * ----------------------------------------------------- */

template <typename T>
class single_value_iterator {
protected:
   op_value_cache<T, true> value;
   bool _at_end;
public:
   typedef random_access_iterator_tag iterator_category;
   typedef T value_type;
   typedef const T& reference;
   typedef const T* pointer;
   typedef ptrdiff_t difference_type;
   typedef single_value_iterator iterator;
   typedef single_value_iterator const_iterator;

   single_value_iterator() : _at_end(true) { }

   single_value_iterator(typename function_argument<T>::type arg, bool end_arg=false)
      : value(arg), _at_end(end_arg) { }

   reference operator* () const { return value.get(); }
   pointer operator-> () const { return &**this; }
   reference operator[] (int) const { return **this; }

   iterator& operator++ () { _at_end^=1; return *this; }
   const iterator operator++ (int) { iterator copy=*this; operator++(); return copy; }
   iterator& operator-- () { return operator++(); }
   const iterator operator-- (int) { iterator copy=*this; operator++(); return copy; }

   iterator& operator+= (int i) { _at_end^=i&1; return *this; }
   iterator& operator-= (int i) { return operator+=(i); }
   const iterator operator+ (int i) const { iterator copy=*this; return copy+=i; }
   friend const iterator operator+ (int i, const iterator& me) { return me+i; }
   const iterator operator- (int i) const { iterator copy=*this; return copy+=i; }
   difference_type operator- (const iterator& it) const { return _at_end-it._at_end; }
   bool operator== (const iterator& it) const { return _at_end==it._at_end; }
   bool operator!= (const iterator& it) const { return !operator==(it); }

   bool at_end() const { return _at_end; }
   int index() const { return 0; }
   void rewind() { _at_end=false; }
};

template <typename T>
class constant_iterator {
protected:
   op_value_cache<T, true> value;
public:
   typedef random_access_iterator_tag iterator_category;
   typedef T value_type;
   typedef const T& reference;
   typedef const T* pointer;
   typedef ptrdiff_t difference_type;
   typedef constant_iterator iterator;
   typedef constant_iterator const_iterator;

   constant_iterator() { }
   constant_iterator(const T *arg) : value(*arg) { }

   reference operator* () const { return value.get(); }
   pointer operator-> () const { return &**this; }
   reference operator[] (int) const { return **this; }

   iterator& operator++ () { return *this; }
   iterator& operator++ (int) { return *this; }
   iterator& operator-- () { return *this; }
   iterator& operator-- (int) { return *this; }
   iterator& operator+= (int) { return *this; }
   iterator& operator-= (int) { return *this; }
   const iterator& operator+ (int) const { return *this; }
   const iterator& operator- (int) const { return *this; }
   friend const iterator& operator+ (int, const iterator& it) { return it; }
   bool operator== (const iterator& it) const { return this==it; }
   bool operator!= (const iterator& it) const { return !operator==(it); }
   bool operator< (const iterator& it) const { return !operator==(it); }
   bool operator> (const iterator& it) const { return !operator==(it); }
   bool operator<= (const iterator& it) const { return true; }
   bool operator>= (const iterator& it) const { return true; }
   difference_type operator- (const iterator& it) const { return this!=it; }

   void rewind() { }
};

template <typename T>
struct constant_iterator<T&> {
protected:
   const T* ptr;
public:
   typedef random_access_iterator_tag iterator_category;
   typedef typename deref<T>::type value_type;
   typedef const T& reference;
   typedef const T* pointer;
   typedef ptrdiff_t difference_type;
   typedef constant_iterator iterator;
   typedef constant_iterator const_iterator;

   constant_iterator(const T* arg=0) : ptr(arg) { }

   reference operator* () const { return *ptr; }
   pointer operator-> () const { return ptr; }
   reference operator[] (int) const { return *ptr; }

   iterator& operator++ () { return *this; }
   iterator& operator++ (int) { return *this; }
   iterator& operator-- () { return *this; }
   iterator& operator-- (int) { return *this; }
   iterator& operator+= (int) { return *this; }
   iterator& operator-= (int) { return *this; }
   const iterator& operator+ (int) const { return *this; }
   const iterator& operator- (int) const { return *this; }
   friend const iterator& operator+ (int, const iterator& it) { return it; }
   bool operator== (const iterator& it) const { return ptr==it.ptr; }
   bool operator!= (const iterator& it) const { return !operator==(it); }
   bool operator< (const iterator& it) const { return !operator==(it); }
   bool operator> (const iterator& it) const { return !operator==(it); }
   bool operator<= (const iterator& it) const { return true; }
   bool operator>= (const iterator& it) const { return true; }
   difference_type operator- (const iterator& it) const { return ptr-it.ptr; }

   void rewind() { }
};

template <typename T>
struct check_iterator_feature<single_value_iterator<T>, end_sensitive> : True { };

template <typename T>
struct check_iterator_feature<single_value_iterator<T>, rewindable> : True { };

template <typename T>
struct check_iterator_feature<single_value_iterator<T>, indexed> : True { };

template <typename T>
struct check_iterator_feature<constant_iterator<T>, unlimited> : True { };

template <typename T>
struct check_iterator_feature<constant_iterator<T>, rewindable> : True { };

template <typename T, bool _sparse=false>
class single_elem_container
   : public array_traits<const T> {
protected:
   T elem;
public:
   single_elem_container(typename function_argument<T>::type arg) : elem(arg) { }

   typedef single_value_iterator<T> iterator;
   typedef iterator const_iterator;
   typedef iterator reverse_iterator;
   typedef iterator const_reverse_iterator;

   iterator begin() const { return elem; }
   iterator end() const { return iterator(elem,true); }
   iterator rbegin() const { return elem; }
   iterator rend() const { return iterator(elem,true); }
   const T& front() const { return elem; }
   const T& back() const { return elem; }
   const T& operator[] (int i) const { return elem; }

   bool empty() const { return false; }
   int size() const { return 1; }
   int max_size() const { return 1; }
};

template <typename T>
class single_elem_container<T&, false>
   : public plain_array<single_elem_container<T&>, T> {
protected:
   ~single_elem_container();
public:
   T& get_data() { return reinterpret_cast<T&>(*this); }
   const T& get_data() const { return reinterpret_cast<const T&>(*this); }

   int size() const { return 1; }
   int max_size() const { return 1; }
};

template <typename T>
class single_elem_sparse_container
   : public array_traits<const T> {
protected:
   T elem;
   bool _empty;

   single_elem_sparse_container() : _empty(true) { }
   single_elem_sparse_container(typename function_argument<T>::type arg) : elem(arg), _empty(false) { }

   typedef single_elem_container<T,true> me;
public:
   static me create_empty() { return me(); }
   static me create(typename function_argument<T>::type arg) { return me(arg); }

   typedef single_value_iterator<T> iterator;
   typedef iterator const_iterator;

   iterator begin() const { return iterator(elem,_empty); }
   iterator end() const { return iterator(elem,true); }

   const T& front() const { return elem; }
   bool empty() const { return _empty; }
};

template <typename T>
class single_elem_sparse_container<T&>
   : public array_traits<T> {
protected:
   ~single_elem_sparse_container();
   typedef single_elem_container<T&,true> me;
public:
   static me& create_empty() { return *reinterpret_cast<me*>(1); }
   static typename inherit_const<me,T>::type& create(T& arg) { return reinterpret_cast<typename inherit_const<me,T>::type&>(arg); }

   typedef typename ensure_features<array_as_container<T,1>, sparse_compatible>::iterator iterator;
   typedef typename ensure_features<array_as_container<T,1>, sparse_compatible>::const_iterator const_iterator;

   iterator begin() { return iterator(&front(), &front()+!empty()); }
   const_iterator begin() const { return const_iterator(&front(), &front()+!empty()); }
   iterator end() { return iterator(&front()+!empty()); }
   const_iterator end() const { return const_iterator(&front()+!empty()); }

   T& front() { return reinterpret_cast<T&>(static_cast<me&>(*this)); }
   const T& front() const { return reinterpret_cast<const T&>(static_cast<const me&>(*this)); }

   bool empty() const
   {
      return static_cast<const me*>(this) == reinterpret_cast<const me*>(1);
   }
};

template <typename T>
class single_elem_container<T, true>
   : public single_elem_sparse_container<T> {
   typedef single_elem_sparse_container<T> super;
public:
   single_elem_container() { }
   single_elem_container(typename function_argument<T>::type arg) : super(arg) { }

   typedef typename super::iterator iterator;
   typedef iterator reverse_iterator;
   typedef typename super::const_iterator const_iterator;
   typedef const_iterator const_reverse_iterator;

   iterator rbegin() { return this->begin(); }
   const_iterator rbegin() const { return this->begin(); }
   iterator rend() { return this->end(); }
   const_iterator rend() const { return this->end(); }

   typename super::reference back() { return this->front(); }
   typename super::const_reference back() const { return this->front(); }

   int size() const { return !this->empty(); }
   int max_size() const { return 1; }
   int dim() const { return 1; }
};

template <typename Top, typename Value, bool _is_masquerade_ref>
struct constant_container {
   typedef Value value_type;
   typedef const Value& const_reference;
   typedef const_reference reference;

   typedef constant_iterator<typename if_else<_is_masquerade_ref,const Value&,Value>::type> iterator;
   typedef iterator const_iterator;
   typedef iterator reverse_iterator;
   typedef iterator const_reverse_iterator;

   reference back() const { return static_cast<const Top*>(this)->front(); }
   reference operator[] (int) const { return back(); }

   iterator begin() const { return &back(); }
   iterator end() const { return &back(); }
   iterator rbegin() const { return &back(); }
   iterator rend() const { return &back(); }

   bool empty() const { return true; }
   int size() const { return std::numeric_limits<int>::max(); }
};

template <typename T>
class unlimited_constant_container
   : public constant_container< unlimited_constant_container<T>, T, false> {
protected:
   T value;
public:
   const T& front() const { return value; }
};

template <typename T>
class unlimited_constant_container<const T&>
   : public constant_container< unlimited_constant_container<const T&>, T> {
protected:
   ~unlimited_constant_container();
public:
   const T& front() const { return reinterpret_cast<const T&>(*this); }
};

template <typename Eref>
class repeated_item_container
   : public constant_container<repeated_item_container<Eref>, typename deref<Eref>::type> {
protected:
   alias<Eref> value;
   int d;
public:
   typedef typename alias<Eref>::arg_type arg_type;

   repeated_item_container(arg_type value_arg, int dim_arg)
      : value(value_arg), d(dim_arg) { }

   typename deref<Eref>::plus_const_ref front() const { return value; }
   int size() const { return d; }
   bool empty() const { return d==0; }
};

template <typename T, bool _sparse>
struct spec_object_traits< single_elem_container<T,_sparse> >
   : spec_object_traits<is_container> { };

template <typename E, bool _sparse>
struct check_container_feature<single_elem_container<E,_sparse>, sparse> : bool2type<_sparse> { };

template <typename T> inline
single_elem_container<T&>& item2container(T& x)
{
   return reinterpret_cast<single_elem_container<T&>&>(x);
}
template <typename T> inline
const single_elem_container<const T&>& item2container(const T& x)
{
   return reinterpret_cast<const single_elem_container<const T&>&>(x);
}

template <typename T> inline
const unlimited_constant_container<const typename Concrete<T>::type&>&
constant(const T& x)
{
   return reinterpret_cast<const unlimited_constant_container<const typename Concrete<T>::type&>&>(Concrete<T>::get(x));
}

template <typename E>
class single_elem_composite {
protected:
   ~single_elem_composite();
};

template <typename E>
struct spec_object_traits< single_elem_composite<E> >
   : spec_object_traits<is_composite> {
   typedef E elements;

   template <typename Me, typename Visitor>
   static void visit_elements(Me& me, Visitor& v)
   {
      v << reinterpret_cast<typename inherit_const<E, Me>::type&>(me);
   }
};

template <typename E> inline
single_elem_composite<E>& item2composite(E& x)
{
   return reinterpret_cast<single_elem_composite<E>&>(x);
}

template <typename E> inline
const single_elem_composite<E>& item2composite(const E& x)
{
   return reinterpret_cast<const single_elem_composite<E>&>(x);
}

template <typename Iterator, typename Operation>
class output_transform_iterator : public iterator_traits<Iterator>::derivable_type {
protected:
   Operation op;

   typedef typename iterator_traits<Iterator>::derivable_type super;
public:
   typedef output_iterator_tag iterator_category;
   typedef typename deref<typename Operation::argument_type>::type value_type;

   output_transform_iterator() { }

   output_transform_iterator(const Iterator& cur_arg, const Operation& op_arg=Operation())
      : super(cur_arg), op(op_arg) { }

   output_transform_iterator& operator= (typename Operation::argument_type arg)
   {
      *static_cast<super*>(this)=op(arg);
      return *this;
   }

   template <typename Arg>
   output_transform_iterator& operator= (const Arg& arg)
   {
      *static_cast<super*>(this)=op(arg);
      return *this;
   }

   output_transform_iterator& operator* () { return *this; }
   output_transform_iterator& operator++ () { return *this; }
   output_transform_iterator& operator++ (int) { return *this; }
};

template <typename Iterator, typename Operation> inline
output_transform_iterator<Iterator,Operation>
make_output_transform_iterator(Iterator it, const Operation& op)
{
   return output_transform_iterator<Iterator,Operation>(it,op);
}

struct output_transform_constructor {
   template <typename Iterator, typename Operation, typename ExpectedFeatures>
   struct defs {
      typedef ExpectedFeatures needed_features;
      typedef output_transform_iterator<Iterator,Operation> iterator;
   };
};

template <typename Iterator1, typename Iterator2, typename Params=void>
class iterator_pair
   : public iterator_traits<Iterator1>::derivable_type {
public:
   typedef Iterator1 first_type;
   typedef Iterator2 second_type;

   typedef typename iterator_traits<Iterator1>::derivable_type super;
   Iterator2 second;
protected:
   typedef typename extract_type_param<Params,FeaturesViaSecond>::type features_via_second;

public:
   typedef typename least_derived< cons<typename iterator_traits<Iterator1>::iterator_category,
					typename iterator_traits<Iterator2>::iterator_category> >::type
      iterator_category;
   typedef typename iterator_traits< typename if_else<check_iterator_feature<Iterator1,unlimited>::value,
						      Iterator2, Iterator1>::type >::difference_type
      difference_type;
   typedef iterator_pair<typename iterator_traits<Iterator1>::iterator,
			 typename iterator_traits<Iterator2>::iterator, Params>
      iterator;
   typedef iterator_pair<typename iterator_traits<Iterator1>::const_iterator,
			 typename iterator_traits<Iterator2>::const_iterator, Params>
      const_iterator;

   iterator_pair() { }

   iterator_pair(const Iterator1& first_arg, const Iterator2& second_arg)
      : super(first_arg), second(second_arg) { }
   iterator_pair(const Iterator1& first_arg,
		 typename alt_constructor<Iterator2>::arg_type& second_arg)
      : super(first_arg), second(second_arg) { }
   iterator_pair(typename alt_constructor<Iterator1>::arg_type& first_arg,
		 const Iterator2& second_arg)
      : super(first_arg), second(second_arg) { }
   iterator_pair(typename alt_constructor<Iterator1>::arg_type& first_arg,
		 typename alt_constructor<Iterator2>::arg_type& second_arg)
      : super(first_arg), second(second_arg) { }

   iterator_pair(const iterator& it)
      : super(static_cast<const typename iterator::super&>(it)), second(it.second) { }

   iterator_pair& operator= (const iterator& it)
   {
      super::operator=(static_cast<const typename iterator::super&>(it));
      second=it.second;
      return *this;
   }

   iterator_pair& operator++ ()
   {
      super::operator++(); ++second;
      return *this;
   }
   const iterator_pair
   operator++ (int)
   {
      iterator_pair copy=*this; operator++(); return copy;
   }

   iterator_pair& operator-- ()
   {
      typedef typename enable_if<super, iterator_pair_traits<Iterator1,Iterator2>::is_bidirectional>::type
	 error_if_unimplemented;
      error_if_unimplemented::operator--();  --this->second;
      return *this;
   }
   const iterator_pair operator-- (int)
   {
      iterator_pair copy=*this;  operator--();  return copy;
   }

   iterator_pair& operator+= (int i)
   {
      typedef typename enable_if<super, iterator_pair_traits<Iterator1,Iterator2>::is_bidirectional>::type
	 error_if_unimplemented;
      error_if_unimplemented::operator+=(i);  this->second+=i;
      return *this;
   }
   iterator_pair& operator-= (int i)
   {
      typedef typename enable_if<super, iterator_pair_traits<Iterator1,Iterator2>::is_random>::type
	 error_if_unimplemented;
      error_if_unimplemented::operator-=(i);  this->second-=i;
      return *this;
   }
   const iterator_pair operator+ (int i) const
   {
      iterator_pair copy=*this; return copy+=i;
   }
   const iterator_pair operator- (int i) const
   {
      iterator_pair copy=*this; return copy-=i;
   }
   friend const iterator_pair operator+ (int i, const iterator_pair& it)
   {
      return it+i;
   }

private:
   template <typename IteratorPair>
   difference_type _diff(const IteratorPair& it, False) const
   {
      return static_cast<const super&>(*this)-it;
   }
   template <typename IteratorPair>
   difference_type _diff(const iterator_pair& it, True) const
   {
      return second-it.second;
   }
   template <typename IteratorPair>
   bool _eq(const IteratorPair& it, False) const
   {
      return static_cast<const super&>(*this) == it;
   }
   template <typename IteratorPair>
   bool _eq(const IteratorPair& it, True) const
   {
      return second==it.second;
   }
   static const bool _cmp2=list_search<features_via_second, end_sensitive, absorbing_feature>::value;
public:
   difference_type operator- (const iterator& it) const
   {
      typedef typename enable_if<super, iterator_pair_traits<Iterator1,Iterator2>::is_random>::type
	 error_if_unimplemented;
      return _diff(it, bool2type<_cmp2>());
   }
   difference_type operator- (typename assign_const<const_iterator, !identical<iterator,const_iterator>::value>::type& it) const
   {
      typedef typename enable_if<difference_type, iterator_pair_traits<Iterator1,Iterator2>::is_random>::type
	 error_if_unimplemented;
      return _diff(it, bool2type<_cmp2>());
   }

   bool operator== (const iterator& it) const
   {
      return _eq(it, bool2type<_cmp2>());
   }
   bool operator== (typename assign_const<const_iterator, !identical<iterator,const_iterator>::value>::type& it) const
   {
      return _eq(it, bool2type<_cmp2>());
   }

   bool operator!= (const iterator& it) const
   {
      return !operator==(it);
   }
   bool operator!= (typename assign_const<const_iterator, !identical<iterator,const_iterator>::value>::type& it) const
   {
      return !operator==(it);
   }
private:
   bool _at_end(False) const
   {
      return super::at_end();
   }
   bool _at_end(True) const
   {
      return second.at_end();
   }
   static const bool _at_end2=list_search<features_via_second, end_sensitive, absorbing_feature>::value ||
                              !check_iterator_feature<Iterator1, end_sensitive>::value,
                     _enable_at_end= _at_end2 ? check_iterator_feature<Iterator2, end_sensitive>::value
                                              : check_iterator_feature<Iterator1, end_sensitive>::value;
public:
   bool at_end() const
   {
      typedef typename enable_if<bool, _enable_at_end>::type error_if_unimplemented;
      return _at_end(bool2type<_at_end2>());
   }
private:
   int _index(False) const
   {
      return super::index();
   }
   int _index(True) const
   {
      return second.index();
   }
   static const bool _index2=list_search<features_via_second, indexed, absorbing_feature>::value ||
                             !check_iterator_feature<Iterator1, indexed>::value,
                     _enable_index= _index2 ? check_iterator_feature<Iterator2, indexed>::value
                                            : check_iterator_feature<Iterator1, indexed>::value;
public:
   int index() const
   {
      typedef typename enable_if<int, _enable_index>::type error_if_unimplemented;
      return _index(bool2type<_index2>());
   }
protected:
   static const bool _rewind1 = !list_search<features_via_second, rewindable, absorbing_feature>::value,
                     _enable_rewind= check_iterator_feature<Iterator1, rewindable>::value &&
                                     check_iterator_feature<Iterator2, rewindable>::value;
   void rewind1(True) { super::rewind(); }
   void rewind1(False) { }
public:
   void rewind()
   {
      typedef typename enable_if<void,_enable_rewind>::type error_if_unimplemented;
      rewind1(bool2type<_rewind1>());
      second.rewind();
   }
protected:
   void contract1(bool, int distance_front, int, False)
   {
      std::advance(static_cast<super&>(*this), distance_front);
   }
   void contract1(bool renumber, int distance_front, int distance_back, True)
   {
      super::contract(renumber, distance_front, distance_back);
   }
   void contract2(bool, int distance_front, int, False)
   {
      std::advance(second, distance_front);
   }
   void contract2(bool renumber, int distance_front, int distance_back, True)
   {
      second.contract(renumber, distance_front, distance_back);
   }
public:
   void contract(bool renumber, int distance_front, int distance_back=0)
   {
      if (!list_search<features_via_second, contractable, identical>::value)
	 contract1(renumber, distance_front, distance_back, bool2type<check_iterator_feature<Iterator1, contractable>::value>());
      contract2(renumber, distance_front, distance_back, bool2type<check_iterator_feature<Iterator2, contractable>::value>());
   }
};

template <typename Iterator1, typename Iterator2, typename Params, typename Feature>
struct check_iterator_feature< iterator_pair<Iterator1, Iterator2, Params>, Feature> {
   typedef cons<indexed, cons<end_sensitive, contractable> > one_suffices;

   static const bool
      check1 = check_iterator_feature<Iterator1,Feature>::value,
      check2 = check_iterator_feature<Iterator2,Feature>::value,
      value = list_search<typename extract_type_param<Params,FeaturesViaSecond>::type, Feature, absorbing_feature>::value
	      ? check2 :
	      list_contains<one_suffices, Feature>::value
	      ? check1 || check2
	      : check1 && check2;
};

struct pair_coupler {
   typedef cons<end_sensitive, indexed> usual_or_features;

   template <typename Iterator1, typename Iterator2, typename ExpectedFeatures>
   struct defs {
      typedef typename list_search_all<ExpectedFeatures, usual_or_features, identical>::positive or_features;
      typedef typename list_search_all<ExpectedFeatures, usual_or_features, identical>::negative and_features;
      typedef typename list_search_all<Iterator1, or_features, check_iterator_feature>::positive2 first_can;
      typedef typename list_search_all<Iterator1, or_features, check_iterator_feature>::negative2 first_can_not;
      typedef typename if_else<check_iterator_feature<Iterator2,unlimited>::value, void, first_can_not>::type
         via_second;
      typedef iterator_pair<Iterator1, Iterator2, FeaturesViaSecond<via_second> > iterator;
      typedef typename if_else<check_iterator_feature<Iterator2,unlimited>::value, ExpectedFeatures, and_features>::type
         needed_features1;
      typedef typename if_else<check_iterator_feature<Iterator2,unlimited>::value, and_features,
			       typename list_search_all<ExpectedFeatures, first_can, identical>::negative>::type
	 needed_features2;
   };
};

template <typename IteratorPair, typename Operation, bool _partial>
class binary_transform_eval : public IteratorPair {
protected:
   typedef IteratorPair super;
public:
   typedef binary_helper<IteratorPair,Operation> helper;
   typedef typename helper::operation operation;
protected:
   operation op;

   typedef Operation op_arg_type;

   binary_transform_eval() { }

   template <typename Operation2>
   binary_transform_eval(const binary_transform_eval<typename iterator_traits<super>::iterator, Operation2, _partial>& it)
      : super(it), op(helper::create(it.op)) { }

   binary_transform_eval(const IteratorPair& cur_arg,
			 const op_arg_type& op_arg)
      : super(cur_arg),
	op(helper::create(op_arg)) { }
   binary_transform_eval(typename alt_constructor<IteratorPair>::arg_type& cur_arg,
			 const op_arg_type& op_arg)
      : super(cur_arg),
	op(helper::create(op_arg)) { }

   binary_transform_eval(const typename IteratorPair::first_type& first_arg,
			 const typename IteratorPair::second_type& second_arg,
			 const op_arg_type& op_arg)
      : super(first_arg,second_arg),
	op(helper::create(op_arg)) { }
   binary_transform_eval(const typename IteratorPair::first_type& first_arg,
			 typename alt_constructor<typename IteratorPair::second_type>::arg_type& second_arg,
			 const op_arg_type& op_arg)
      : super(first_arg,second_arg),
	op(helper::create(op_arg)) { }
   binary_transform_eval(typename alt_constructor<typename IteratorPair::first_type>::arg_type& first_arg,
			 const typename IteratorPair::second_type& second_arg,
			 const op_arg_type& op_arg)
      : super(first_arg,second_arg),
	op(helper::create(op_arg)) { }
   binary_transform_eval(typename alt_constructor<typename IteratorPair::first_type>::arg_type& first_arg,
			 typename alt_constructor<typename IteratorPair::second_type>::arg_type& second_arg,
			 const op_arg_type& op_arg)
      : super(first_arg,second_arg),
	op(helper::create(op_arg)) { }

   template <typename,typename,bool> friend class binary_transform_eval;
public:
   typedef typename operation::result_type reference;

   reference operator* () const
   {
      return op(*helper::get1(*this), *helper::get2(this->second));
   }

   typedef typename arrow_helper<reference>::pointer pointer;
   pointer operator-> () const { return arrow_helper<reference>::get(*this); }
};

template <typename IteratorPair, typename Operation, typename IndexOperation, bool _partial>
class binary_transform_eval<IteratorPair, pair<Operation, IndexOperation>, _partial>
   : public binary_transform_eval<IteratorPair, Operation, _partial> {
   typedef binary_transform_eval<IteratorPair, Operation, _partial> _super;
protected:
   typedef binary_helper<IteratorPair,IndexOperation> ihelper;
   typename ihelper::operation iop;

   typedef pair<Operation, IndexOperation> op_arg_type;

   binary_transform_eval() { }

   template <typename Operation2, typename IndexOperation2>
   binary_transform_eval(const binary_transform_eval<typename iterator_traits<IteratorPair>::iterator,
			                             pair<Operation2, IndexOperation2>, _partial>& it)
      : _super(it),
	iop(ihelper::create(it.iop)) { }

   binary_transform_eval(const IteratorPair& cur_arg,
			 const op_arg_type& op_arg)
      : _super(cur_arg,op_arg.first),
	iop(ihelper::create(op_arg.second)) { }
   binary_transform_eval(typename alt_constructor<IteratorPair>::arg_type& cur_arg,
			 const op_arg_type& op_arg)
      : _super(cur_arg,op_arg.first),
	iop(ihelper::create(op_arg.second)) { }

   binary_transform_eval(const typename IteratorPair::first_type& first_arg,
			 const typename IteratorPair::second_type& second_arg,
			 const op_arg_type& op_arg)
      : _super(first_arg,second_arg,op_arg.first),
	iop(ihelper::create(op_arg.second)) { }
   binary_transform_eval(const typename IteratorPair::first_type& first_arg,
			 typename alt_constructor<typename IteratorPair::second_type>::arg_type& second_arg,
			 const op_arg_type& op_arg)
      : _super(first_arg,second_arg,op_arg.first),
	iop(ihelper::create(op_arg.second)) { }
   binary_transform_eval(typename alt_constructor<typename IteratorPair::first_type>::arg_type& first_arg,
			 const typename IteratorPair::second_type& second_arg,
			 const op_arg_type& op_arg)
      : _super(first_arg,second_arg,op_arg.first),
	iop(ihelper::create(op_arg.second)) { }
   binary_transform_eval(typename alt_constructor<typename IteratorPair::first_type>::arg_type& first_arg,
			 typename alt_constructor<typename IteratorPair::second_type>::arg_type& second_arg,
			 const op_arg_type& op_arg)
      : _super(first_arg,second_arg,op_arg.first),
	iop(ihelper::create(op_arg.second)) { }

   template <typename,typename,bool> friend class binary_transform_eval;
public:
   int index() const
   {
      return iop(*ihelper::get1(*this), *ihelper::get2(this->second));
   }
};

template <typename IteratorPair, typename IndexOperation, bool _partial>
class binary_transform_eval<IteratorPair, pair<nothing, IndexOperation>, _partial>
   : public IteratorPair {
protected:
   typedef IteratorPair super;

   typedef binary_helper<IteratorPair,IndexOperation> ihelper;
   typename ihelper::operation iop;

   typedef IndexOperation op_arg_type;

   binary_transform_eval() { }

   template <typename IndexOperation2>
   binary_transform_eval(const binary_transform_eval<typename iterator_traits<IteratorPair>::iterator,
			                             pair<nothing, IndexOperation2>, _partial>& it)
      : super(it),
	iop(ihelper::create(it.iop)) { }

   binary_transform_eval(const IteratorPair& cur_arg,
			 const op_arg_type& op_arg)
      : super(cur_arg),
	iop(ihelper::create(op_arg)) { }
   binary_transform_eval(typename alt_constructor<IteratorPair>::arg_type& cur_arg,
			 const op_arg_type& op_arg)
      : super(cur_arg),
	iop(ihelper::create(op_arg)) { }

   binary_transform_eval(const typename IteratorPair::first_type& first_arg,
			 const typename IteratorPair::second_type& second_arg,
			 const op_arg_type& op_arg)
      : super(first_arg,second_arg),
	iop(ihelper::create(op_arg)) { }
   binary_transform_eval(const typename IteratorPair::first_type& first_arg,
			 typename alt_constructor<typename IteratorPair::second_type>::arg_type& second_arg,
			 const op_arg_type& op_arg)
      : super(first_arg,second_arg),
	iop(ihelper::create(op_arg)) { }
   binary_transform_eval(typename alt_constructor<typename IteratorPair::first_type>::arg_type& first_arg,
			 const typename IteratorPair::second_type& second_arg,
			 const op_arg_type& op_arg)
      : super(first_arg,second_arg),
	iop(ihelper::create(op_arg)) { }
   binary_transform_eval(typename alt_constructor<typename IteratorPair::first_type>::arg_type& first_arg,
			 typename alt_constructor<typename IteratorPair::second_type>::arg_type& second_arg,
			 const op_arg_type& op_arg)
      : super(first_arg,second_arg),
	iop(ihelper::create(op_arg)) { }

   template <typename,typename,bool> friend class binary_transform_eval;
public:
   int index() const
   {
      return iop(*ihelper::get1(*this), *ihelper::get2(this->second));
   }
};

template <typename IteratorPair, typename Operation, bool _partial=false>
class binary_transform_iterator
   : public binary_transform_eval<IteratorPair, Operation, _partial> {
   typedef binary_transform_eval<IteratorPair, Operation, _partial> _super;
protected:
   typedef IteratorPair super;
public:
   typedef typename deref<typename _super::reference>::type value_type;
   typedef binary_transform_iterator<typename iterator_traits<IteratorPair>::iterator, Operation, _partial>
      iterator;
   typedef binary_transform_iterator<typename iterator_traits<IteratorPair>::const_iterator, Operation, _partial>
      const_iterator;

   binary_transform_iterator() { }

   template <typename Operation2>
   binary_transform_iterator(const binary_transform_iterator<typename iterator_traits<super>::iterator, Operation2, _partial>& it)
      : _super(it) { }

   binary_transform_iterator(const IteratorPair& cur_arg,
			     const typename _super::op_arg_type& op_arg=typename _super::op_arg_type())
      : _super(cur_arg,op_arg) { }

   binary_transform_iterator(const typename IteratorPair::first_type& first_arg,
			     const typename IteratorPair::second_type& second_arg,
			     const typename _super::op_arg_type& op_arg=typename _super::op_arg_type())
      : _super(first_arg,second_arg,op_arg) { }
   binary_transform_iterator(const typename IteratorPair::first_type& first_arg,
			     typename alt_constructor<typename IteratorPair::second_type>::arg_type& second_arg,
			     const typename _super::op_arg_type& op_arg=typename _super::op_arg_type())
      : _super(first_arg,second_arg,op_arg) { }
   binary_transform_iterator(typename alt_constructor<typename IteratorPair::first_type>::arg_type& first_arg,
			     const typename IteratorPair::second_type& second_arg,
			     const typename _super::op_arg_type& op_arg=typename _super::op_arg_type())
      : _super(first_arg,second_arg,op_arg) { }
   binary_transform_iterator(typename alt_constructor<typename IteratorPair::first_type>::arg_type& first_arg,
			     typename alt_constructor<typename IteratorPair::second_type>::arg_type& second_arg,
			     const typename _super::op_arg_type& op_arg=typename _super::op_arg_type())
      : _super(first_arg,second_arg,op_arg) { }

   binary_transform_iterator& operator++ ()
   {
      super::operator++(); return *this;
   }
   const binary_transform_iterator operator++ (int)
   {
      binary_transform_iterator copy=*this;  operator++();  return copy;
   }

   binary_transform_iterator& operator-- ()
   {
      typedef typename enable_if<super, iterator_traits<super>::is_bidirectional>::type error_if_unimplemented;
      error_if_unimplemented::operator--();
      return *this;
   }
   const binary_transform_iterator operator-- (int)
   {
      binary_transform_iterator copy=*this;  operator--();  return copy;
   }

   binary_transform_iterator& operator+= (int i)
   {
      typedef typename enable_if<super, iterator_traits<super>::is_bidirectional>::type error_if_unimplemented;
      error_if_unimplemented::operator+=(i);
      return *this;
   }
   binary_transform_iterator&
   operator-= (int i)
   {
      typedef typename enable_if<super, iterator_traits<super>::is_random>::type error_if_unimplemented;
      error_if_unimplemented::operator-=(i);
      return *this;
   }
   const binary_transform_iterator operator+ (int i) const
   {
      binary_transform_iterator copy=*this;  return copy+=i;
   }
   const binary_transform_iterator operator- (int i) const
   {
      binary_transform_iterator copy=*this;  return copy-=i;
   }
   friend const binary_transform_iterator operator+ (int i, const binary_transform_iterator& it)
   {
      return it+i;
   }

   typename super::difference_type
   operator- (const iterator& it) const
   {
      typedef typename enable_if<super, iterator_traits<super>::is_random>::type error_if_unimplemented;
      return static_cast<const error_if_unimplemented&>(*this) - it;
   }
   typename super::difference_type
   operator- (typename assign_const<const_iterator, !identical<iterator,const_iterator>::value>::type& it) const
   {
      typedef typename enable_if<super, iterator_traits<super>::is_random>::type error_if_unimplemented;
      return static_cast<const error_if_unimplemented&>(*this) - it;
   }

protected:
   typename _super::reference _random(int i, cons<True, True>) const
   {
      return this->op(super::operator[](i), this->second[i]);
   }
   typename _super::reference _random(int i, cons<True, False>) const
   {
      return this->op(super::operator[](i), this->second+i);
   }
   typename _super::reference _random(int i, cons<False, True>) const
   {
      return this->op(static_cast<const typename IteratorPair::super&>(*this)+i, this->second[i]);
   }
   typename _super::reference _random(int i, cons<False, False>) const
   {
      return this->op(static_cast<const typename IteratorPair::super&>(*this)+i, this->second+i);
   }
public:
   typename super::reference operator[] (int i) const
   {
      typedef typename enable_if<typename _super::helper, iterator_traits<super>::is_random>::type error_if_unimplemented;
      return _random(i, cons< bool2type<error_if_unimplemented::first_data_arg>, bool2type<error_if_unimplemented::second_data_arg> >());
   }
};

template <typename IteratorPair, typename Operation, bool _partial, typename Feature>
struct check_iterator_feature<binary_transform_iterator<IteratorPair, Operation, _partial>,
			      Feature>
   : check_iterator_feature<IteratorPair,Feature> { };

template <typename IteratorPair, typename Operation, bool _partial>
struct check_iterator_feature<binary_transform_iterator<IteratorPair, Operation, _partial>, indexed> {
   static const bool value=is_instance2_of<Operation,pair>::value ||
                           check_iterator_feature<IteratorPair, indexed>::value;
};

template <typename Iterator>
struct has_partial_state : False { };

template <typename Params>
struct binary_transform_constructor {
   typedef Params params;
   template <typename IteratorPair, typename Operation, typename ExpectedFeatures>
   struct defs {
      static const bool
	 _partial = extract_bool_param<Params, PartiallyDefined, has_partial_state<IteratorPair>::value>::value;

      typedef typename if_else<is_instance2_of<Operation,pair>::value,
			       typename list_search_all<ExpectedFeatures, indexed, identical>::negative,
			       ExpectedFeatures >::type
         needed_pair_features;
      typedef void needed_features1;
      typedef void needed_features2;
      typedef binary_transform_iterator<IteratorPair, Operation, _partial> iterator;
   };
};

namespace operations {

template <typename IteratorRef>
struct index2element {
   typedef IteratorRef argument_type;
   typedef const int result_type;
   result_type operator() (argument_type it) const { return it.index(); }
};

template <typename IteratorRef>
struct extra_deref {
   typedef IteratorRef argument_type;
   typedef typename iterator_traits<typename deref<IteratorRef>::type>::reference ref;
   typedef typename if_else<attrib<IteratorRef>::is_const, typename attrib<ref>::plus_const, ref>::type result_type;
   result_type operator() (argument_type it) const { return *it; }
};

template <typename Ref>
struct identity {
   typedef Ref argument_type;
   typedef Ref result_type;
   Ref operator() (Ref x) const { return x; }
   typename function_argument<Ref>::lvalue
   assign(typename function_argument<Ref>::lvalue x) const { return x; }
};

template <typename Ref>
struct ref2pointer {
   typedef Ref argument_type;
   typedef typename deref<Ref>::minus_ref* result_type;
   result_type operator() (Ref x) const { return &x; }
};

template <typename Iterator1Ref, typename Iterator2Ref>
struct second_deref {
   typedef Iterator1Ref first_argument_type;
   typedef Iterator2Ref second_argument_type;
   typedef typename iterator_traits<typename deref<Iterator2Ref>::type>::reference result_type;
   result_type operator() (first_argument_type, second_argument_type it2) const
   {
      return *it2;
   }
};

template <typename Iterator1Ref, typename Iterator2Ref>
struct second_index2element {
   typedef Iterator1Ref first_argument_type;
   typedef Iterator2Ref second_argument_type;
   typedef const int result_type;
   result_type operator() (first_argument_type, second_argument_type it2) const
   {
      return it2.index();
   }
};

template <typename OrigRef, typename ApparentRef, bool _need_cache=!attrib<OrigRef>::is_reference>
struct reinterpret_impl {
   typedef OrigRef argument_type;
   typedef ApparentRef result_type;
   result_type operator() (OrigRef x) const
   {
      return reinterpret_cast<result_type>(x);
   }
};

template <typename Orig, typename ApparentRef>
struct reinterpret_impl<Orig, ApparentRef, true> {
   typedef Orig argument_type;
   typedef typename attrib<ApparentRef>::plus_ref result_type;
private:
   mutable op_value_cache<typename deref<Orig>::type> cache;
public:
   result_type operator() (argument_type x) const
   {
      cache=x;
      return reinterpret_cast<result_type>(cache.get());
   }
};

template <typename OrigRef, typename ApparentRef, bool _keep_const>
struct reinterpret_impl_nonconst {
   typedef OrigRef argument_type;
   typedef typename assign_const<ApparentRef,_keep_const>::type result_type;
   result_type operator() (OrigRef x) const
   {
      return reinterpret_cast<result_type>(const_cast<typename assign_const<OrigRef, _keep_const>::type>(x));
   }
};

template <typename OrigRef, typename ApparentRef, bool _do_reinterpret=attrib<OrigRef>::is_reference>
struct construct_or_reinterpret_impl
   : reinterpret_impl<OrigRef, ApparentRef, false> { };

template <typename Orig, typename Apparent>
struct construct_or_reinterpret_impl<Orig, Apparent, false> {
   typedef Orig argument_type;
   typedef Apparent result_type;
   result_type operator() (argument_type x) const { return result_type(x); }
};

template <typename Apparent> struct reinterpret : incomplete { };
template <template <typename> class Masquerade> struct masquerade : incomplete { };
template <template <typename,typename> class Masquerade, typename Second> struct masquerade2 : incomplete { };
template <template <typename> class Masquerade> struct construct_or_masquerade : incomplete { };
template <template <typename,typename> class Masquerade, typename Second> struct construct_or_masquerade2 : incomplete { };
template <typename Apparent> struct reinterpret_it : incomplete { };
template <typename Apparent> struct reinterpret_it_nonconst : incomplete { };
template <template <typename> class Masquerade> struct masquerade_it : incomplete { };
template <template <typename> class Masquerade> struct masquerade_it_nonconst : incomplete { };
template <template <typename,typename> class Masquerade, typename Second> struct masquerade2_it : incomplete { };
template <template <typename,typename> class Masquerade, typename Second> struct masquerade2_it_nonconst : incomplete { };

} // end namespace operations

template <typename Apparent, typename Iterator, typename Reference>
struct unary_op_builder<operations::reinterpret<Apparent>, Iterator, Reference>
   : empty_op_builder< operations::reinterpret_impl<Reference, typename inherit_ref<Apparent,Reference>::type> > { };

template <template <typename> class Masquerade, typename Iterator, typename Reference>
struct unary_op_builder<operations::masquerade<Masquerade>, Iterator, Reference>
   : empty_op_builder< operations::reinterpret_impl<Reference, typename masquerade<Masquerade,Reference>::type> > { };

template <template <typename> class Masquerade, typename Iterator, typename Reference>
struct unary_op_builder<operations::construct_or_masquerade<Masquerade>, Iterator, Reference>
   : empty_op_builder< operations::construct_or_reinterpret_impl<Reference, typename masquerade_keep_ref<Masquerade,Reference>::type> > { };

template <template <typename,typename> class Masquerade, typename Second, typename Iterator, typename Reference>
struct unary_op_builder<operations::masquerade2<Masquerade,Second>, Iterator, Reference>
   : empty_op_builder< operations::reinterpret_impl<Reference, typename masquerade2<Masquerade,Reference,Second>::type> > { };

template <template <typename,typename> class Masquerade, typename Second, typename Iterator, typename Reference>
struct unary_op_builder<operations::construct_or_masquerade2<Masquerade,Second>, Iterator, Reference>
   : empty_op_builder< operations::reinterpret_impl<Reference, typename masquerade2_keep_ref<Masquerade,Reference,Second>::type> > { };

template <typename Apparent, typename Iterator, typename Reference>
struct unary_op_builder<operations::reinterpret_it<Apparent>, Iterator, Reference>
   : empty_op_builder< operations::reinterpret_impl<const Iterator&, typename attrib<Apparent>::plus_const_ref> > { };

template <typename Apparent, typename Iterator, typename Reference>
struct unary_op_builder<operations::reinterpret_it_nonconst<Apparent>, Iterator, Reference>
   : empty_op_builder< operations::reinterpret_impl_nonconst<const Iterator&, typename attrib<Apparent>::plus_ref,
							     attrib<typename iterator_traits<Iterator>::reference>::is_const> > { };

template <template <typename> class Masquerade, typename Iterator, typename Reference>
struct unary_op_builder<operations::masquerade_it<Masquerade>, Iterator, Reference>
   : empty_op_builder< operations::reinterpret_impl<const Iterator&, const Masquerade<Iterator>&> > { };

template <template <typename> class Masquerade, typename Iterator, typename Reference>
struct unary_op_builder<operations::masquerade_it_nonconst<Masquerade>, Iterator, Reference>
   : empty_op_builder< operations::reinterpret_impl_nonconst<const Iterator&, Masquerade<Iterator>&,
							     attrib<typename iterator_traits<Iterator>::reference>::is_const> > { };

template <template <typename,typename> class Masquerade, typename Second, typename Iterator, typename Reference>
struct unary_op_builder<operations::masquerade2_it<Masquerade,Second>, Iterator, Reference>
   : empty_op_builder< operations::reinterpret_impl<const Iterator&, const Masquerade<Iterator,Second>&> > { };

template <template <typename,typename> class Masquerade, typename Second, typename Iterator, typename Reference>
struct unary_op_builder<operations::masquerade2_it_nonconst<Masquerade,Second>, Iterator, Reference>
   : empty_op_builder< operations::reinterpret_impl_nonconst<const Iterator&, Masquerade<Iterator,Second>&,
							     attrib<typename iterator_traits<Iterator>::reference>::is_const> > { };

} // end namespace pm

namespace polymake {
   using pm::array2container;
   using pm::item2container;
   using pm::item2composite;
   using pm::Entire;
   using pm::entire;
   using pm::BuildUnary;
   using pm::BuildBinary;
   using pm::BuildUnaryIt;
   using pm::BuildBinaryIt;
   using pm::make_unary_transform_iterator;
   using pm::make_output_transform_iterator;
   using pm::rewindable;
   using pm::reversed;
   using pm::constant;
   using pm::black_hole;
   using pm::inserter;
} // end namespace polymake

#endif // _POLYMAKE_ITERATORS_H

// Local Variables:
// mode:C++
// End:
