/* 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_TRANSFORMED_CONTAINER_H
#define _POLYMAKE_TRANSFORMED_CONTAINER_H "$Project: polymake $$Id: TransformedContainer.h,v 1.17 2006/03/07 18:06:42 gawrilow Exp $"

#ifndef _POLYMAKE_SPARSE_H
#  include <sparse.h>
#endif

namespace pm {
/* ----------------------
 *  TransformedContainer
 * ---------------------- */

template <typename ContainerRef, typename Operation>
class TransformedContainer
   : public modified_container_base<ContainerRef, Operation>,
     public modified_container_impl< TransformedContainer<ContainerRef,Operation>,
               cons< Container< ContainerRef >,
		     Accessor< Operation > >
            > {
   typedef modified_container_base<ContainerRef, Operation> _base;
public:
   TransformedContainer(typename _base::arg_type src_arg,
			const typename _base::operation_type& op_arg=typename _base::operation_type())
      : _base(src_arg, op_arg) { }

   using _base::get_accessor;
};

template <typename ContainerRef, typename Operation>
struct check_container_feature<TransformedContainer<ContainerRef,Operation>, sparse>
   : check_container_ref_feature<ContainerRef, sparse> { };

template <typename ContainerRef, typename Operation>
struct check_container_feature<TransformedContainer<ContainerRef,Operation>, pure_sparse>
   : check_container_ref_feature<ContainerRef, pure_sparse> { };

template <typename ContainerRef, typename Operation>
struct spec_object_traits< TransformedContainer<ContainerRef, Operation> >
   : spec_object_traits<is_container> {
   static const bool is_temporary=true,
                     is_always_const=identical_raw<typename TransformedContainer<ContainerRef, Operation>::reference,
						   typename TransformedContainer<ContainerRef, Operation>::const_reference>::answer;
};

template <typename Container, typename Operation> inline
TransformedContainer<Container&, Operation>
attach_operation(Container& src, const Operation& op)
{
   return TransformedContainer<Container&, Operation> (src,op);
}

template <typename Container, typename Operation> inline
TransformedContainer<const Container&, Operation>
attach_operation(const Container& src, const Operation& op)
{
   return TransformedContainer<const Container&, Operation> (src,op);
}

template <typename Container, typename Class, typename Member> inline
TransformedContainer<Container&, operations::var_member<Class&,Member> >
attach_member_accessor(Container& c, Member Class::*ptr)
{
   return TransformedContainer<Container&, operations::var_member<Class&,Member> > (c,ptr);
}

template <typename Container, typename Class, typename Member> inline
TransformedContainer<const Container&, operations::var_member<const Class&,Member> >
attach_member_accessor(const Container& c, Member Class::*ptr)
{
   return TransformedContainer<const Container&, operations::var_member<const Class&,Member> > (c,ptr);
}

template <typename Container, typename Class, typename Member, Member Class::*Ptr> inline
TransformedContainer<Container&, operations::member<Class,Member,Ptr> >
attach_member_accessor(Container& c, ptr2type<Class, Member, Ptr>*)
{
   return c;
}

template <typename Container, typename Class, typename Member, Member Class::*Ptr> inline
TransformedContainer<const Container&, operations::member<Class,Member,Ptr> >
attach_member_accessor(const Container& c, ptr2type<Class, Member, Ptr>*)
{
   return c;
}

/* --------------------------
 *  TransformedContainerPair
 * -------------------------- */

template <typename ContainerRef1, typename ContainerRef2>
struct TransformedContainerPair_helper1 {
   typedef typename deref<ContainerRef1>::type container1;
   typedef typename deref<ContainerRef2>::type container2;
   static const bool
      sparse1=check_container_feature<container1, sparse>::answer,
      sparse2=check_container_feature<container2, sparse>::answer,
      constant1= object_classifier::what_is<container1>::answer == object_classifier::is_constant,
      constant2= object_classifier::what_is<container2>::answer == object_classifier::is_constant,
      use_sparse_coupler= (sparse1 || sparse2) && !constant1 && !constant2,
      dense_result= (!sparse1 && !constant1) || (!sparse2 && !constant2),
      sparse_result= (sparse1 && sparse2) || (sparse1 && constant2) || (constant1 && sparse2);
};

template <typename Operation, bool use_sparse_coupler, bool _partially_defined>
struct TransformedContainerPair_helper2 {
   typedef Operation accessor;
   typedef Accessor< Operation > traits2;
};

template <typename Operation, bool _partially_defined>
struct TransformedContainerPair_helper2<Operation, true, _partially_defined> {
   typedef typename if_else<_partially_defined, set_union_zipper, set_intersection_zipper>::result controller;
   typedef typename if_else<_partially_defined,
			    pair< Operation, BuildBinaryIt<operations::zipper_index> >,
			    Operation>::result
      accessor;

   typedef cons< Coupler< sparse_coupler<controller, false> >,
	   cons< Modifier< binary_transform_modifier< cons< Bijective< False >,
							    PartiallyDefined< bool2type<_partially_defined> > > > >,
		 Accessor< accessor > > >
      traits2;
};

template <typename ContainerRef1, typename ContainerRef2, typename Operation>
struct TransformedContainerPair_helper
   : TransformedContainerPair_helper1<ContainerRef1, ContainerRef2> {
   typedef TransformedContainerPair_helper1<ContainerRef1, ContainerRef2> _super;
   typedef typename if_else<!_super::sparse1 && !_super::constant1 && _super::sparse2,
			    masquerade_add_features<ContainerRef1,sparse_compatible>, ContainerRef1>::result
      first_type;
   typedef typename if_else<!_super::sparse2 && !_super::constant2 && _super::sparse1,
			    masquerade_add_features<ContainerRef2,sparse_compatible>, ContainerRef2>::result
      second_type;

   typedef typename binary_op_builder<Operation, typename container_traits<ContainerRef1>::iterator,
				                 typename container_traits<ContainerRef2>::iterator>::operation
      operation;
   static const bool partially_defined=operations::is_partially_defined<operation>::answer;

   typedef TransformedContainerPair_helper2<Operation, _super::use_sparse_coupler, partially_defined> helper2;
   typedef cons< Container1< first_type >,
           cons< Container2< second_type >,
		 typename helper2::traits2 > >
      traits;
   typedef typename helper2::accessor accessor;
   typedef modified_container_pair_base<first_type, second_type, accessor> base;
   typedef typename is_identity_transform<Operation>::type op_arg_type;

   static const op_arg_type& get_accessor(const op_arg_type& op_arg, True*)
   {
      return op_arg;
   }
   static accessor get_accessor(const Operation& op_arg, False*)
   {
      return accessor(op_arg, typename accessor::second_type());
   }
};

template <typename ContainerRef1, typename ContainerRef2, typename Operation>
class TransformedContainerPair
   : public TransformedContainerPair_helper<ContainerRef1,ContainerRef2,Operation>::base,
     public modified_container_pair_impl< TransformedContainerPair<ContainerRef1,ContainerRef2,Operation>,
               typename TransformedContainerPair_helper<ContainerRef1,ContainerRef2,Operation>::traits
            > {
   typedef modified_container_pair_impl<TransformedContainerPair> _super;
   typedef TransformedContainerPair_helper<ContainerRef1,ContainerRef2,Operation> helper;
   typedef typename helper::base _base;
   static const bool simple_accessor=identical<Operation, typename helper::accessor>::answer;
protected:
   int size(False*, False*) const { return _super::size(); }
   int size(True*, False*) const { return this->get_container1().size(); }
   int size(False*, True*) const { return this->get_container2().size(); }
public:
   TransformedContainerPair(typename _base::first_arg_type src1_arg, typename _base::second_arg_type src2_arg,
			    const typename helper::op_arg_type& op_arg=typename helper::op_arg_type())
      : _base(src1_arg, src2_arg, helper::get_accessor(op_arg, (bool2type<simple_accessor>*)0)) { }

   using _base::get_accessor;

   int size() const
   {
      return size((bool2type<helper::use_sparse_coupler && (helper::partially_defined ? !helper::sparse1 : !helper::sparse2)>*)0,
		  (bool2type<helper::use_sparse_coupler && (helper::partially_defined ? !helper::sparse2 : !helper::sparse1)>*)0);
   }
};

template <typename ContainerRef1, typename ContainerRef2, typename Operation>
struct check_container_feature<TransformedContainerPair<ContainerRef1,ContainerRef2,Operation>, sparse> {
   static const bool answer=TransformedContainerPair_helper<ContainerRef1,ContainerRef2,Operation>::sparse_result;
};

template <typename ContainerRef1, typename ContainerRef2, typename Operation>
struct check_container_feature<TransformedContainerPair<ContainerRef1,ContainerRef2,Operation>, sparse_compatible> {
   static const bool answer=check_container_ref_feature<ContainerRef1, sparse_compatible>::answer ||
                            check_container_ref_feature<ContainerRef2, sparse_compatible>::answer;
};

template <typename ContainerRef1, typename ContainerRef2, typename Operation>
struct check_container_feature<TransformedContainerPair<ContainerRef1,ContainerRef2,Operation>, dense> {
   static const bool answer=TransformedContainerPair_helper<ContainerRef1,ContainerRef2,Operation>::dense_result;
};

template <typename ContainerRef1, typename ContainerRef2, typename Operation>
struct spec_object_traits< TransformedContainerPair<ContainerRef1, ContainerRef2, Operation> >
   : spec_object_traits<is_container> {
   static const bool is_temporary=true,
                     is_always_const=identical<typename TransformedContainerPair<ContainerRef1, ContainerRef2, Operation>::reference,
					       typename TransformedContainerPair<ContainerRef1, ContainerRef2, Operation>::const_reference>::answer;
};

template <typename Container1, typename Container2, typename Operation> inline
TransformedContainerPair<Container1&, Container2&, Operation>
attach_operation(Container1& c1, Container2& c2, Operation op)
{
   return TransformedContainerPair<Container1&, Container2&, Operation> (c1,c2,op);
}

template <typename Container1, typename Container2, typename Operation> inline
TransformedContainerPair<const Container1&, Container2&, Operation>
attach_operation(const Container1& c1, Container2& c2, Operation op)
{
   return TransformedContainerPair<const Container1&, Container2&, Operation> (c1,c2,op);
}

template <typename Container1, typename Container2, typename Operation> inline
TransformedContainerPair<Container1&, const Container2&, Operation>
attach_operation(Container1& c1, const Container2& c2, Operation op)
{
   return TransformedContainerPair<Container1&, const Container2&, Operation> (c1,c2,op);
}

template <typename Container1, typename Container2, typename Operation> inline
TransformedContainerPair<const Container1&, const Container2&, Operation>
attach_operation(const Container1& c1, const Container2& c2, Operation op)
{
   return TransformedContainerPair<const Container1&, const Container2&, Operation> (c1,c2,op);
}

template <typename Container, typename Scalar> inline
TransformedContainerPair<const Container&, masquerade_keep_ref<unlimited_constant_container,const Scalar&>, BuildBinary<operations::add> >
translate(const Container& c, const Scalar& x)
{
   return TransformedContainerPair<const Container&, masquerade_keep_ref<unlimited_constant_container,const Scalar&>, BuildBinary<operations::add> >
          (c,x);
}

template <typename Container, typename Scalar> inline
TransformedContainerPair<const Container&, masquerade_keep_ref<unlimited_constant_container,const Scalar&>, BuildBinary<operations::mul> >
scale(const Container& c, const Scalar& x)
{
   return TransformedContainerPair<const Container&, masquerade_keep_ref<unlimited_constant_container,const Scalar&>, BuildBinary<operations::mul> >
          (c,x);
}

/* ------------------
 *  ContainerProduct
 * ------------------ */

/** Common base for iterators over cartesian product of two sequences
    It runs over all possible pairs of data items, with the second component changing first.
*/
template <typename Iterator1, typename Iterator2, bool _partial=false>
class iterator_product : public iterator_traits<Iterator1>::derivable_type {
public:
   typedef typename iterator_traits<Iterator1>::derivable_type super;

   typedef Iterator1 first_type;
   typedef Iterator2 second_type;
   Iterator2 second;

   typedef forward_iterator_tag iterator_category;
   typedef iterator_product<typename iterator_traits<Iterator1>::iterator,
			    typename iterator_traits<Iterator2>::iterator, _partial>
      iterator;
   typedef iterator_product<typename iterator_traits<Iterator1>::const_iterator,
			    typename iterator_traits<Iterator2>::const_iterator, _partial>
      const_iterator;

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

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

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

   iterator_product& operator++()
   {
      ++second;
      if (second.at_end()) {
	 super::operator++();
	 second.reset();
      }
      return *this;
   }

   iterator_product operator++(int) { iterator_product copy=*this; operator++(); return copy; }

   bool operator== (const iterator_product& it) const
   {
      return static_cast<const super&>(*this)==static_cast<const super&>(it)  &&  second==it.second;
   }
   bool operator!= (const iterator_product& it) const { return !operator==(it); }

private:
   void operator--();
   void operator+=(int);
   void operator-=(int);
   void operator+(int);
   void operator-(int);
   void operator[](int);

   template <typename,typename,bool> friend class iterator_product;
};

template <typename Iterator1, typename Iterator2>
class iterator_product<Iterator1, Iterator2, true>
   : public iterator_product<Iterator1, Iterator2, false> {
   typedef iterator_product<Iterator1, Iterator2, false> _super;
   template <typename,typename,bool> friend class iterator_product;
protected:
   int state;

   static const bool
      partial1=check_iterator_feature<Iterator1,partially_defined>::answer,
      partial2=check_iterator_feature<Iterator2,partially_defined>::answer;

   void set_state(True*, True*)
   {
      state = this->second.state & zipper_eq
	    ? _super::state :
	      _super::state & zipper_eq
	    ? zipper_lt
	    : zipper_gt;
   }
   void set_state(True*, False*)
   {
      state = _super::state;
   }
   void set_state(False*, True*)
   {
      state = this->second.state & zipper_gt ? zipper_lt : zipper_eq;
   }
   void set_state()
   {
      set_state((bool2type<partial1>*)0, (bool2type<partial2>*)0);
   }

   void incr(True*, True*)
   {
      if (state & zipper_gt) {
	 typedef typename _super::super super;
	 typedef typename Iterator2::super super2;
	 this->second.super2::operator++();
	 if (this->second.super2::at_end()) {
	    super::operator++();
	    this->second.reset();
	    set_state((True*)0, (True*)0);
	 }
      } else {
	 _super::operator++();
	 set_state((True*)0, (True*)0);
      }
   }

   void incr(True*, False*)
   {
      _super::operator++();
      set_state((True*)0, (False*)0);
   }

   void incr(False*, True*) {
      _super::operator++();
      set_state((False*)0, (True*)0);
   }
public:
   typedef iterator_product<typename iterator_traits<Iterator1>::iterator,
			    typename iterator_traits<Iterator2>::iterator, true>
      iterator;
   typedef iterator_product<typename iterator_traits<Iterator1>::const_iterator,
			    typename iterator_traits<Iterator2>::const_iterator, true>
      const_iterator;

   iterator_product() { }
   iterator_product(const iterator& it)
      : _super(static_cast<const typename iterator::_super&>(it)) { }

   iterator_product(const Iterator1& first_arg, const Iterator2& second_arg)
      : _super(first_arg,second_arg) { set_state(); }
   iterator_product(typename alt_constructor<Iterator1>::arg_type& first_arg,
		    typename alt_constructor<Iterator2>::arg_type& second_arg)
      : _super(first_arg,second_arg) { set_state(); }

   iterator_product& operator= (const iterator& it)
   {
      _super::operator=(static_cast<const typename iterator::_super&>(it));
      return *this;
   }

   iterator_product& operator++ ()
   {
      incr((bool2type<partial1>*)0, (bool2type<partial2>*)0);
      return *this;
   }

   iterator_product operator++(int) { iterator_product copy=*this; operator++(); return copy; }

   void reset()
   {
      typedef typename enable_if<_super, check_iterator_feature<Iterator1,resettable>::answer>::type
	 error_if_unimplemented;
      error_if_unimplemented::reset(); set_state();
   }
};

template <typename Iterator1, typename Iterator2, bool _partial, typename Feature>
struct check_iterator_feature<iterator_product<Iterator1,Iterator2,_partial>, Feature>
   : check_iterator_feature<Iterator1,Feature> { };

template <typename Iterator1, typename Iterator2, bool _partial>
struct check_iterator_feature<iterator_product<Iterator1,Iterator2,_partial>, indexed> : False { };

template <typename Iterator1, typename Iterator2, bool _partial>
struct check_iterator_feature<iterator_product<Iterator1,Iterator2,_partial>, partially_defined> {
   static const bool answer=_partial;
};

struct product_index_accessor {
   typedef void first_argument_type;
   typedef void second_argument_type;
   typedef int result_type;

   template <typename Iterator1, typename Iterator2>
   result_type operator() (const Iterator1& it1, const Iterator2& it2) const
   {
      return it1.index()*dim2 + it2.index();
   }
   template <typename Iterator1, typename Iterator2>
   result_type operator() (operations::partial_left, const Iterator1& it1, const Iterator2& it2) const
   {
      return it1.index()*dim2 + *it2.second;
   }
   template <typename Iterator1, typename Iterator2>
   result_type operator() (operations::partial_right, const Iterator1& it1, const Iterator2& it2) const
   {
      return *it1.second*dim2 + it2.index();
   }

   product_index_accessor(int dim2_arg=0) : dim2(dim2_arg) { }
protected:
   int dim2;
};

template <typename Top, typename Traits>
class container_product_typebase : public manip_container_top<Top, Traits> {
   typedef manip_container_top<Top, Traits> _super;
public:
   typedef typename extract_type_param<Traits, Container1>::result src_container1_ref;
   typedef typename extract_type_param<Traits, Container2>::result src_container2_ref;
   typedef typename deref<src_container1_ref>::minus_ref src_container1;
   typedef typename deref<src_container2_ref>::minus_ref src_container2;
   typedef typename container_traits<src_container1>::iterator src_iterator1;
   typedef typename container_traits<src_container2>::iterator src_iterator2;
   typedef typename extract_type_param<Traits, Accessor>::result value_accessor;

   typedef typename binary_op_builder<value_accessor, src_iterator1, src_iterator2>::operation
      operation;
   static const bool
      sparse1=check_container_ref_feature<src_container1, sparse>::answer,
      sparse2=check_container_ref_feature<src_container2, sparse>::answer,
      partially_defined = (sparse1 || sparse2) && operations::is_partially_defined<operation>::answer,
      sparse_result = partially_defined ? sparse1 && sparse2 : sparse1 || sparse2,
      need_index= sparse_result || list_search<typename _super::expected_features, indexed, absorbing_feature>::answer;

   typedef typename if_else<partially_defined && sparse1,
			    masquerade<construct_dense_pair, src_container1_ref>,
			    typename if_else<!partially_defined && !sparse1 && sparse2,
					     masquerade_add_features<src_container1_ref, sparse_compatible>,
					     src_container1_ref>::result
                           >::result
      container1_ref;
   typedef typename if_else<partially_defined && sparse2,
			    masquerade<construct_dense_pair, src_container2_ref>, 
			    typename if_else<!partially_defined && !sparse2 && sparse1,
					     masquerade_add_features<src_container2_ref, sparse_compatible>,
					     src_container2_ref>::result
                           >::result
      container2_ref;
   typedef typename deref<container1_ref>::minus_ref container1;
   typedef typename deref<container2_ref>::minus_ref container2;

   typedef typename if_else<need_index, pair<value_accessor, product_index_accessor>, value_accessor>::result
      accessor;

   typedef typename extract_type_param<Traits, Modifier, binary_transform_modifier<> >::result modifier;

   typedef iterator_product<typename container_traits<container1>::iterator,
			    typename container_traits<container2>::iterator,
			    partially_defined>
      first_try_it_pair;
   typedef typename modifier::template defs<first_try_it_pair, accessor, typename _super::expected_features>
      first_try_defs;
   typedef typename if_else<need_index,
			    typename mix_features<typename first_try_defs::needed_pair_features, indexed>::result,
			    typename first_try_defs::needed_pair_features>::result
      needed_pair_features;
   typedef needed_pair_features needed_features1;
   typedef typename mix_features<needed_pair_features, cons<end_sensitive,resettable> >::result
      needed_features2;
   typedef iterator_product<typename ensure_features<container1,needed_features1>::iterator,
			    typename ensure_features<container2,needed_features2>::iterator,
			    partially_defined>
      it_pair;
   typedef iterator_product<typename ensure_features<container1,needed_features1>::const_iterator,
			    typename ensure_features<container2,needed_features2>::const_iterator,
			    partially_defined>
      const_it_pair;
   typedef typename modifier::template defs<it_pair, accessor, typename _super::expected_features>::iterator
      iterator;
   typedef typename modifier::template defs<const_it_pair, accessor, typename _super::expected_features>::iterator
      const_iterator;

   typedef typename least_derived< cons<typename container_traits<src_container1>::category,
					typename container_traits<src_container2>::category> >::type
      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>::result
      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 Traits>
class reverse_container_product_typebase {
   typedef container_product_typebase<Top, Traits> _base;
   typedef iterator_product<typename ensure_features<typename _base::container1, typename _base::needed_features1>::reverse_iterator,
			    typename ensure_features<typename _base::container2, typename _base::needed_features2>::reverse_iterator,
			    _base::partially_defined>
      reverse_it_pair;
   typedef iterator_product<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,
			    _base::partially_defined>
      const_reverse_it_pair;
public:
   typedef typename _base::modifier::template defs<reverse_it_pair, typename _base::accessor,
						   typename _base::expected_features>::iterator
      reverse_iterator;
   typedef typename _base::modifier::template defs<const_reverse_it_pair, typename _base::accessor,
						   typename _base::expected_features>::iterator
      const_reverse_iterator;
};

template <typename Top, typename Traits=typename Top::manipulator_traits,
	  typename Category=typename container_product_typebase<Top, Traits>::category>
class container_product_impl
   : public container_product_typebase<Top, Traits>,
     public modified_container_non_bijective_elem_access<Top, container_product_typebase<Top, Traits>,
							 derived_from<Category, bidirectional_iterator_tag>::answer>
{
   typedef container_product_typebase<Top, Traits> _super;
public:
   typedef container_product_impl<Top, Traits> manipulator_impl;
   typedef Traits manipulator_traits;
   typedef typename _super::iterator iterator;
   typedef typename _super::const_iterator const_iterator;

   template <typename FeatureCollector>
   struct rebind_feature_collector {
      typedef container_product_impl<FeatureCollector,Traits> 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(),
		      create_accessor());
   }
   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).begin(),
		      create_accessor());
   }
   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(),
			    create_accessor());
   }
   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).begin(),
			    create_accessor());
   }
private:
   template <typename discr2>
   int _size(False*, discr2*) const
   {
      return this->top().get_container1().size() * this->top().get_container2().size();
   }
   int _size(True*, False*) const
   {
      return dim();
   }
   int _size(True*, True*) const
   {
      const int d1=get_dim(this->top().get_container1()), d2=get_dim(this->top().get_container2());
      return d1*d2 - (d1-this->top().get_container1().hidden().size())*(d2-this->top().get_container2().hidden().size());
   }

public:
   int size() const
   {
      return _size((bool2type<_super::partially_defined>*)0,
		   (bool2type<_super::sparse1 && _super::sparse2>*)0);
   }
   int dim() const
   {
      return get_dim(this->top().get_container1()) * get_dim(this->top().get_container2());
   }
   bool empty() const
   {
      return this->top().get_container1().empty() || this->top().get_container2().empty();
   }

private:
   typename _super::value_accessor
   create_accessor(False*) const
   {
      return this->top().get_accessor();
   }

   typename _super::accessor
   create_accessor(True*) const
   {
      return typename _super::accessor(this->top().get_accessor(), get_dim(this->top().get_container2()));
   }
public:
   typename _super::value_accessor get_accessor() const { return typename _super::value_accessor(); }
   typename _super::accessor create_accessor() const { return create_accessor((bool2type<_super::need_index>*)0); }
};

template <typename Top, typename Traits>
class container_product_impl<Top, Traits, bidirectional_iterator_tag>
   : public container_product_impl<Top, Traits, forward_iterator_tag>,
     public reverse_container_product_typebase<Top, Traits> {
   typedef container_product_impl<Top, Traits, forward_iterator_tag> _super;
   typedef reverse_container_product_typebase<Top, Traits> _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->create_accessor());
   }
   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).rbegin(),
					       this->create_accessor());
   }
   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->create_accessor());
   }
   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).rbegin(),
						     this->create_accessor());
   }
};

template <typename Top, typename Traits>
class container_product_impl<Top, Traits, random_access_iterator_tag>
   : public container_product_impl<Top, Traits, bidirectional_iterator_tag> {
   typedef container_product_impl<Top, Traits, bidirectional_iterator_tag> _super;
public:
   // TO BE DONE LATER
};

template <typename ContainerRef1, typename ContainerRef2, typename Operation>
class ContainerProduct;

template <typename ContainerRef1, typename ContainerRef2, typename Operation>
struct ContainerProduct_helper {
   typedef cons< Container1< ContainerRef1 >,
           cons< Container2< ContainerRef2 >,
		 Accessor< Operation > > >
      traits;

   typedef container_product_impl< ContainerProduct<ContainerRef1,ContainerRef2,Operation>, traits>
      impl;
   typedef modified_container_pair_base<typename impl::container1_ref, typename impl::container2_ref, Operation>
      base;
};

template <typename ContainerRef1, typename ContainerRef2, typename Operation>
class ContainerProduct
   : public ContainerProduct_helper<ContainerRef1,ContainerRef2,Operation>::base,
     public ContainerProduct_helper<ContainerRef1,ContainerRef2,Operation>::impl {
   typedef ContainerProduct_helper<ContainerRef1,ContainerRef2,Operation> helper;
   typedef typename helper::base _base;
   typedef typename helper::impl _super;

public:
   ContainerProduct(typename _base::first_arg_type src1_arg, typename _base::second_arg_type src2_arg,
		    const typename _base::operation_type& op_arg=typename _base::operation_type())
      : _base(src1_arg, src2_arg, op_arg) { }

   using _base::get_accessor;
};

template <typename ContainerRef1, typename ContainerRef2, typename Operation>
struct check_container_feature<ContainerProduct<ContainerRef1,ContainerRef2,Operation>, sparse> {
   typedef typename ContainerProduct_helper<ContainerRef1,ContainerRef2,Operation>::impl impl;
   static const bool answer=impl::sparse_result;
};

template <typename ContainerRef1, typename ContainerRef2, typename Operation>
struct spec_object_traits< ContainerProduct<ContainerRef1, ContainerRef2, Operation> >
   : spec_object_traits<is_container> {
   static const bool is_temporary=true,
                     is_always_const=identical<typename ContainerProduct<ContainerRef1, ContainerRef2, Operation>::reference,
					       typename ContainerProduct<ContainerRef1, ContainerRef2, Operation>::const_reference>::answer;
};

template <typename Container1, typename Container2, typename Operation> inline
ContainerProduct<Container1&, Container2&, Operation>
product(Container1& c1, Container2& c2, Operation op)
{
   return ContainerProduct<Container1&, Container2&, Operation> (c1,c2,op);
}

template <typename Container1, typename Container2, typename Operation> inline
ContainerProduct<const Container1&, Container2&, Operation>
product(const Container1& c1, Container2& c2, Operation op)
{
   return ContainerProduct<const Container1&, Container2&, Operation> (c1,c2,op);
}

template <typename Container1, typename Container2, typename Operation> inline
ContainerProduct<Container1&, const Container2&, Operation>
product(Container1& c1, const Container2& c2, Operation op)
{
   return ContainerProduct<Container1&, const Container2&, Operation> (c1,c2,op);
}

template <typename Container1, typename Container2, typename Operation> inline
ContainerProduct<const Container1&, const Container2&, Operation>
product(const Container1& c1, const Container2& c2, Operation op)
{
   return ContainerProduct<const Container1&, const Container2&, Operation> (c1,c2,op);
}

template <typename Container> inline
const ContainerProduct<count_down, const Container&, BuildBinaryIt<operations::second_deref> >
repeat(const Container& c, int n)
{
   return ContainerProduct<count_down, const Container&, BuildBinaryIt<operations::second_deref> >(count_down(n),c);
}

} // end namespace pm

namespace polymake {
   using pm::attach_operation;
   using pm::attach_member_accessor;
   using pm::translate;
   using pm::scale;
   using pm::product;
   using pm::repeat;
}

#endif // _POLYMAKE_TRANSFORMED_CONTAINER_H

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