/* 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_CONTAINER_CHAIN_H
#define _POLYMAKE_CONTAINER_CHAIN_H "$Project: polymake $$Id: ContainerChain.h,v 1.20 2006/03/09 16:21:35 gawrilow Exp $"

#ifndef _POLYMAKE_OPERATIONS_H
#  include <operations.h>
#endif
#ifndef _POLYMAKE_CONTAINER_UNION_H
#  include <ContainerUnion.h>
#endif

namespace pm {

template <typename Top, typename Traits> class container_chain_typebase;
template <typename IteratorList, typename _reversed=False> class iterator_chain;

template <typename Iterator>
struct iterator_chain_helper {
   static const bool match=true;
   typedef Iterator type;
   typedef typename iterator_traits<Iterator>::iterator iterator_list;
   typedef typename iterator_traits<Iterator>::const_iterator const_iterator_list;
};

template <typename Iterator1, typename Helper>
struct iterator_chain_helper2 {
   static const bool
      exact_match_here=identical<Iterator1, typename Helper::type>::answer,
      match_here=exact_match_here || identical<typename iterator_traits<Iterator1>::const_iterator,
					       typename iterator_traits<typename Helper::type>::const_iterator>::answer,
      match=Helper::match && match_here;

   typedef typename if_else<exact_match_here, Iterator1, typename iterator_traits<Iterator1>::const_iterator>::result
      type;
};

template <typename Car, typename Cdr>
struct iterator_chain_helper< cons<Car,Cdr> >
   : iterator_chain_helper2<Car, iterator_chain_helper<Cdr> > {
   typedef typename concat_list< typename iterator_chain_helper<Car>::iterator_list, typename iterator_chain_helper<Cdr>::iterator_list >::result
      iterator_list;
   typedef typename concat_list< typename iterator_chain_helper<Car>::const_iterator_list, typename iterator_chain_helper<Cdr>::const_iterator_list >::result
      const_iterator_list;
};

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

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

template <int size>
struct iterator_chain_offset_store {
   int off[size];

   template <typename Container, int discr>
   void init(const Container& c, int2type<discr>*)
   {
      if (discr < size-1)
	 off[discr+1]=off[discr]+get_dim(c);
   }

   template <typename Container>
   void init(const Container& c, int2type<0>*)
   {
      off[0]=0;
      off[1]=get_dim(c);
   }

   int operator[] (int discr) const { return off[discr]; }
};

template <>
struct iterator_chain_offset_store<0> {
   template <typename Container, int discr>
   void init(const Container&, int2type<discr>*) { }
};

template <typename IteratorList,
	  bool _homogeneous=iterator_chain_helper<IteratorList>::match,
	  int pos=0, int n=list_length<IteratorList>::answer>
class iterator_chain_store {
protected:
   typedef typename iterator_chain_helper<IteratorList>::type it_type;
   static const bool _indexed=list_and_binary<check_iterator_feature, IteratorList, same<indexed> >::answer;
   static const int n_offsets=_indexed ? n : 0;
   it_type its[n];
   iterator_chain_offset_store<n_offsets> offsets;

   struct traits {
      typedef typename iterator_traits<it_type>::iterator iterator_list;
      typedef typename iterator_traits<it_type>::const_iterator const_iterator_list;
   };

public:
   typedef typename iterator_traits<it_type>::reference reference;
   typedef typename iterator_traits<it_type>::pointer pointer;
   typedef typename iterator_traits<it_type>::value_type value_type;

protected:
   iterator_chain_store() { }

   template <typename IteratorList2>
   iterator_chain_store(const iterator_chain_store<IteratorList2, _homogeneous, pos, n>& s2)
      : offsets(s2.offsets)
   {
      std::copy(s2.its, s2.its+n, its);
   }

   template <typename IteratorList2>
   void operator= (const iterator_chain_store<IteratorList2, _homogeneous, pos, n>& s2)
   {
      std::copy(s2.its, s2.its+n, its);
      offsets=s2.offsets;
   }

   reference star(int discr) const
   {
      return *its[discr];
   }

   pointer arrow(int discr) const
   {
      return its[discr].operator->();
   }

   int index(int discr) const
   {
      return its[discr].index();
   }

   bool incr(int discr)
   {
      return (++its[discr]).at_end();
   }

   template <typename IteratorList2>
   bool eq(int discr, const iterator_chain_store<IteratorList2, _homogeneous, pos, n>& s2) const
   {
      return its[discr] == s2.its[discr];
   }

   bool at_end(int discr) const
   {
      return its[discr].at_end();
   }

   void reset()
   {
      for (it_type *itp=its, itp_end=itp+n; itp<itp_end; ++itp) itp->reset();
   }

private:
   template <typename Container, typename needed_features, int discr, bool _end>
   void init_step(Container& c, needed_features*, int2type<discr>*, bool2type<_end>*)
   {
      (its+discr)->~it_type();
      if (!_end)
	 new(its+discr) it_type(ensure(c, (needed_features*)0).begin());
      else
         new(its+discr) it_type(ensure(c, (needed_features*)0).end());
      offsets.init(c, (int2type<discr>*)0);
   }

   template <typename Container, typename needed_features, int discr, bool _end>
   void init_step(const Container& c, needed_features*, int2type<discr>*, bool2type<_end>*)
   {
      (its+discr)->~it_type();
      if (!_end)
	 new(its+discr) it_type(ensure(c, (needed_features*)0).begin());
      else
         new(its+discr) it_type(ensure(c, (needed_features*)0).end());
      offsets.init(c, (int2type<discr>*)0);
   }

   template <typename Chain, typename needed_features, int discr, bool _end>
   void init(Chain& c, needed_features*, int2type<discr>*, bool2type<_end>*)
   {
      init_step(c.get_container((int2type<discr>*)0), (needed_features*)0, (int2type<discr>*)0, (bool2type<_end>*)0);
      init(c, (needed_features*)0, (int2type<discr+1>*)0, (bool2type<_end>*)0);
   }

   template <typename Chain, typename needed_features, bool _end>
   void init(Chain& c, needed_features*, int2type<n>*, bool2type<_end>*) { }

protected:
   template <typename Chain, bool _rev, bool _end>
   bool init(Chain& c, bool2type<_rev>*, bool2type<_end>*)
   {
      typedef typename if_else<_rev, typename toggle_features<typename Chain::needed_features, _reversed>::result,
	                             typename Chain::needed_features>::result
	 needed_features;
      init(c, (needed_features*)0, (int2type<0>*)0, (bool2type<_end>*)0);
      return _end || its[0].at_end();
   }

   template <typename, bool, int, int> friend class iterator_chain_store;
};

template <typename IteratorList, int pos, int n>
class iterator_chain_store<IteratorList, false, pos, n>
   : public iterator_chain_store<IteratorList, false, pos+1, n> {
   typedef iterator_chain_store<IteratorList, false, pos+1, n> super;
   typedef typename if_else<pos+1!=n, super, iterator_chain_store>::result next;

   typedef typename n_th<IteratorList, pos>::car it_type;
   it_type it;

protected:
   iterator_chain_store() { }

   template <typename IteratorList2>
   iterator_chain_store(const iterator_chain_store<IteratorList2, false, pos, n>& s2)
      : super(static_cast<const iterator_chain_store<IteratorList2, false, pos+1, n>&>(s2)),
	it(s2.it) { }

   template <typename IteratorList2>
   void operator= (const iterator_chain_store<IteratorList2, false, pos, n>& s2)
   {
      it=s2.it;
      super::operator=(s2);
   }

   typename super::reference star(int discr) const
   {
      switch (discr) {
      case pos:
	 return *it;
      default:
	 return next::star(discr);
      }
   }

   typename super::pointer arrow(int discr) const   {
      switch (discr) {
      case pos:
	 return it.operator->();
      default:
	 return next::arrow(discr);
      }
   }

   int index(int discr) const
   {
      switch (discr) {
      case pos:
	 return it.index();
      default:
	 return next::index(discr);
      }
   }

   bool incr(int discr)
   {
      switch (discr) {
      case pos:
	 return (++it).at_end();
      default:
	 return next::incr(discr);
      }
   }

   template <typename IteratorList2>
   bool eq(int discr, const iterator_chain_store<IteratorList2, false, pos, n>& s2) const
   {
      switch (discr) {
      case pos:
	 return it == s2.it;
      default:
	 return next::eq(discr,s2);
      }
   }

   bool at_end(int discr) const
   {
      switch (discr) {
      case pos:
	 return it.at_end();
      default:
	 return next::at_end(discr);
      }
   }

   void reset()
   {
      it.reset();
      if (pos+1 < n) next::reset();
   }
private:
   template <typename Container, typename needed_features, bool _end>
   void init_step(Container& c, needed_features*, bool2type<_end>*)
   {
      it.~it_type();
      if (!_end)
	 new(&it) it_type(ensure(c, (needed_features*)0).begin());
      else
	 new(&it) it_type(ensure(c, (needed_features*)0).end());
      super::offsets.init(c, (int2type<pos>*)0);
   }

   template <typename Container, typename needed_features, bool _end>
   void init_step(const Container& c, needed_features*, bool2type<_end>*)
   {
      it.~it_type();
      if (!_end)
	 new(&it) it_type(ensure(c, (needed_features*)0).begin());
      else
	 new(&it) it_type(ensure(c, (needed_features*)0).end());
      super::offsets.init(c, (int2type<pos>*)0);
   }

protected:
   template <typename Chain, bool _rev, bool _end>
   bool init(Chain& c, bool2type<_rev>*, bool2type<_end>*)
   {
      typedef typename if_else<_rev, typename toggle_features<typename Chain::needed_features, _reversed>::result,
	                             typename Chain::needed_features>::result
	 needed_features;
      init_step(c.get_container((int2type<pos>*)0), (needed_features*)0, (bool2type<_end>*)0);
      if (pos+1 < n) next::init(c, (bool2type<_rev>*)0, (bool2type<_end>*)0);
      return pos==0 && (_end || it.at_end());
   }

   template <typename, bool, int, int> friend class iterator_chain_store;
};

template <typename IteratorList, int n>
class iterator_chain_store<IteratorList, false, n, n> {
protected:
   static const bool _indexed=list_and_binary<check_iterator_feature, IteratorList, same<indexed> >::answer;
   static const int n_offsets=_indexed ? n : 0;
   iterator_chain_offset_store<n_offsets> offsets;

   typedef union_iterator_traits<IteratorList> traits;

   iterator_chain_store() { }

   template <typename IteratorList2>
   iterator_chain_store(const iterator_chain_store<IteratorList2, false, n, n>& s2)
      : offsets(s2.offsets) { }

   template <typename IteratorList2>
   void operator= (const iterator_chain_store<IteratorList2, false, n, n>& s2)
   {
      offsets=s2.offsets;
   }

public:
   typedef typename traits::reference reference;
   typedef typename traits::pointer pointer;
   typedef typename traits::value_type value_type;
};

template <typename IteratorList, typename _reversed>
class iterator_chain : public iterator_chain_store<IteratorList> {
   typedef iterator_chain_store<IteratorList> super;
protected:
   int discr;
   static const int d_step= _reversed::value ? -1 : 1,
		    d_start= _reversed::value ? list_length<IteratorList>::answer-1 : 0,
		    d_finish= _reversed::value ? -1 : list_length<IteratorList>::answer;

   void valid_position()
   {
      do {
	 discr+=d_step;
      } while (!at_end() && super::at_end(discr));
   }

   template <typename,typename> friend class iterator_chain;
public:
   typedef forward_iterator_tag iterator_category;
   typedef ptrdiff_t difference_type;
   typedef iterator_chain<typename iterator_chain_helper<IteratorList>::iterator_list, _reversed> iterator;
   typedef iterator_chain<typename iterator_chain_helper<IteratorList>::const_iterator_list, _reversed> const_iterator;

   iterator_chain() { }

   template <typename IteratorList2>
   iterator_chain(const iterator_chain<IteratorList2, _reversed>& it,
		  typename enable_if<void, matching_iterator_list<IteratorList,IteratorList2>::answer>::type* =0)
      : super(it), discr(it.discr) { }

   template <typename IteratorList2>
   typename enable_if<iterator_chain, matching_iterator_list<IteratorList,IteratorList2>::answer>::type&
   operator= (const iterator_chain<IteratorList2, _reversed>& it)
   {
      super::operator=(it);  discr=it.discr;
      return *this;
   }

   template <typename Top, typename Traits>
   iterator_chain(container_chain_typebase<Top, Traits>& c)
      : discr(d_start)
   {
      if (this->init(c, (_reversed*)0, (False*)0)) valid_position();
   }

   template <typename Top, typename Traits>
   iterator_chain(const container_chain_typebase<Top, Traits>& c)
      : discr(d_start)
   {
      if (this->init(c, (_reversed*)0, (False*)0)) valid_position();
   }

   template <typename Top, typename Traits>
   iterator_chain(container_chain_typebase<Top, Traits>& c, bool _end)
      : discr(d_finish)
   {
      this->init(c, (_reversed*)0, (True*)0);
   }

   template <typename Top, typename Traits>
   iterator_chain(const container_chain_typebase<Top, Traits>& c, bool _end)
      : discr(d_finish)
   {
      this->init(c, (_reversed*)0, (True*)0);
   }

   typename super::reference operator* () const
   {
      return this->star(discr);
   }

   typename super::pointer operator-> () const
   {
      return this->arrow(discr);
   }

   iterator_chain& operator++ ()
   {
      if (this->incr(discr)) valid_position();
      return *this;
   }
   const iterator_chain operator++ (int) { iterator_chain copy=*this; operator++(); return copy; }

   template <typename IteratorList2>
   bool operator== (const iterator_chain<IteratorList2, _reversed>& it) const
   {
      typedef typename enable_if<bool, matching_iterator_list<IteratorList, IteratorList2>::answer ||
				       matching_iterator_list<IteratorList2, IteratorList>::answer>::type 
	 error_if_unimplemented;
      return discr==it.discr && this->eq(discr,it);
   }

   template <typename IteratorList2>
   bool operator!= (const iterator_chain<IteratorList2, _reversed>& it) const
   {
      typedef typename enable_if<bool, matching_iterator_list<IteratorList, IteratorList2>::answer ||
				       matching_iterator_list<IteratorList2, IteratorList>::answer>::type 
	 error_if_unimplemented;
      return !operator==(it);
   }

   bool at_end() const
   {
      return discr == d_finish;
   }

   void reset()
   {
      typedef typename enable_if<super, check_iterator_feature<iterator_chain, resettable>::answer>::type
	 error_if_unimplemented;
      error_if_unimplemented::reset();
      discr=d_start;
      if (super::at_end(discr)) valid_position();
   }

   int index() const
   {
      typedef typename enable_if<super, check_iterator_feature<iterator_chain, indexed>::answer>::type
	 error_if_unimplemented;
      return error_if_unimplemented::index(discr) + this->offsets[discr];
   }
};

template <typename IteratorList, typename _reversed, typename Feature>
struct check_iterator_feature<iterator_chain<IteratorList, _reversed>, Feature>
   : list_and_binary<check_iterator_feature, IteratorList, same<Feature> > { };

template <typename Container,
	  bool _descend=is_instance2_of<typename container_traits<Container>::iterator, iterator_chain>::answer>
struct container_chain_helper {
   static const bool descend=_descend,  // false
                     is_const=effectively_const<Container>::answer;
   typedef Container container_list;
   typedef const Container const_container_list;
};

template <typename Container>
struct container_chain_helper<Container, true> {
   typedef typename Container::manipulator_impl manip;
   static const bool descend=true, is_const=manip::is_const;
   typedef typename Container::container_list container_list;
   typedef typename Container::const_container_list const_container_list;
};

template <typename Container, typename Features, bool _rev=container_traits<Container>::is_bidirectional>
struct container_chain_traits_helper {
   static const bool reversible=_rev;
   typedef typename ensure_features<Container, Features>::iterator iterator_list;
   typedef typename ensure_features<Container, Features>::const_iterator const_iterator_list;
   typedef typename container_traits<Container>::category category;
};

template <typename Container, typename Features>
struct container_chain_traits_helper<Container, Features, true> : container_chain_traits_helper<Container, Features, false> {
   static const bool reversible=true;
   typedef typename ensure_features<Container, Features>::reverse_iterator reverse_iterator_list;
   typedef typename ensure_features<Container, Features>::const_reverse_iterator const_reverse_iterator_list;
};

template <typename Container, typename Features>
struct container_chain_traits : container_chain_traits_helper<Container, Features> { };

template <typename Traits1, typename Traits2, bool _rev=Traits1::reversible && Traits2::reversible>
struct container_chain_traits_helper2 {
   static const bool reversible=_rev;
   typedef typename concat_list<typename Traits1::iterator_list, typename Traits2::iterator_list>::result iterator_list;
   typedef typename concat_list<typename Traits1::const_iterator_list, typename Traits2::const_iterator_list>::result const_iterator_list;
   typedef typename least_derived< cons<typename Traits1::category, typename Traits2::category> >::type category;
};

template <typename Traits1, typename Traits2>
struct container_chain_traits_helper2<Traits1, Traits2, true> : container_chain_traits_helper2<Traits1, Traits2, false> {
   static const bool reversible=true;
   typedef typename concat_list<typename Traits1::reverse_iterator_list,
				typename Traits2::reverse_iterator_list>::result
      reverse_iterator_list;
   typedef typename concat_list<typename Traits1::const_reverse_iterator_list,
				typename Traits2::const_reverse_iterator_list>::result
      const_reverse_iterator_list;
};

template <typename Car, typename Cdr, typename Features>
struct container_chain_traits<cons<Car, Cdr>, Features>
   : container_chain_traits_helper2< container_chain_traits<Car,Features>, container_chain_traits<Cdr,Features> > { };

template <typename Top, typename Traits>
class container_chain_typebase : public manip_container_top<Top, Traits> {
   typedef manip_container_top<Top, Traits> _super;
public:
   typedef typename extract_type_param<Traits,Container1>::result container1_ref;
   typedef typename extract_type_param<Traits,Container2>::result container2_ref;
   typedef typename deref<container1_ref>::minus_ref container1;
   typedef typename deref<container2_ref>::minus_ref container2;
   typedef container_chain_helper<container1> helper1;
   typedef container_chain_helper<container2> helper2;
   typedef typename concat_list<typename helper1::container_list, typename helper2::container_list>::result
      _container_list;
   typedef typename concat_list<typename helper1::const_container_list, typename helper2::const_container_list>::result
      const_container_list;

   typedef dense can_enforce_features;
   /* either some containers are sparse (then the resulting iterator_chain is automatically indexed),
      or the whole chain should be made indexed (it is cheaper) */
   typedef indexed cannot_enforce_features;

   static const bool
      is_const       = helper1::is_const || helper2::is_const,
      is_sparse      = list_or_binary<check_container_ref_feature, _container_list, same<sparse> >::answer,
      is_pure_sparse = list_and_binary<check_container_ref_feature, _container_list, same<pure_sparse> >::answer;

   typedef typename if_else<is_const, const_container_list, _container_list>::result container_list;
   typedef typename mix_features<typename _super::expected_features,
				 typename if_else<is_sparse,
						  typename if_else<list_search_all<typename _super::expected_features, dense, identical>::answer,
								   cons<indexed, end_sensitive>, sparse_compatible>::result,
						  end_sensitive>::result
                                >::result
      needed_features;

   typedef iterator_chain<typename container_chain_traits<container_list, needed_features>::iterator_list> iterator;
   typedef iterator_chain<typename container_chain_traits<container_list, needed_features>::const_iterator_list> const_iterator;
   typedef typename iterator::reference reference;
   typedef typename const_iterator::reference const_reference;
   typedef typename iterator::value_type value_type;
   typedef typename container_chain_traits<container_list, needed_features>::category category;

   template <int pos> struct pos_helper {
      static const int side= pos >= list_length<typename helper1::container_list>::answer,
	               discr= (side ? helper2::descend : helper1::descend)*2+side;
      typedef cons< int2type<pos>, int2type<discr> > type;
   };

   template <int pos>
   typename n_th<container_list, pos>::car&
   get_container(cons< int2type<pos>, int2type<0> >*)
   {
      return this->top().get_container1();
   }
   template <int pos>
   typename n_th<const_container_list, pos>::car&
   get_container(cons< int2type<pos>, int2type<0> >*) const
   {
      return this->top().get_container1();
   }

   template <int pos>
   typename n_th<container_list, pos>::car&
   get_container(cons< int2type<pos>, int2type<1> >*)
   {
      return this->top().get_container2();
   }
   template <int pos>
   typename n_th<const_container_list, pos>::car&
   get_container(cons< int2type<pos>, int2type<1> >*) const
   {
      return this->top().get_container2();
   }

   template <int pos>
   typename n_th<container_list, pos>::car&
   get_container(cons< int2type<pos>, int2type<2> >*)
   {
      return this->top().get_container1().get_container((int2type<pos>*)0);
   }
   template <int pos>
   typename n_th<const_container_list, pos>::car&
   get_container(cons< int2type<pos>, int2type<2> >*) const
   {
      return this->top().get_container1().get_container((int2type<pos>*)0);
   }

   template <int pos>
   typename n_th<container_list, pos>::car&
   get_container(cons< int2type<pos>, int2type<3> >*)
   {
      return this->top().get_container2().get_container((int2type<(pos-list_length<typename helper1::container_list>::answer)>*)0);
   }
   template <int pos>
   typename n_th<const_container_list, pos>::car&
   get_container(cons< int2type<pos>, int2type<3> >*) const
   {
      return this->top().get_container2().get_container((int2type<(pos-list_length<typename helper1::container_list>::answer)>*)0);
   }

   template <int pos>
   typename n_th<container_list, pos>::car&
   get_container(int2type<pos>*)
   {
      return get_container((typename pos_helper<pos>::type*)0);
   }

   template <int pos>
   typename n_th<const_container_list, pos>::car&
   get_container(int2type<pos>*) const
   {
      return get_container((typename pos_helper<pos>::type*)0);
   }
};

template <typename Top, typename Traits=typename Top::manipulator_traits,
	  typename Category=typename container_chain_typebase<Top,Traits>::category>
class container_chain_impl
   : public container_chain_typebase<Top,Traits> {
   typedef container_chain_typebase<Top,Traits> _base;
public:
   typedef container_chain_impl<Top,Traits> manipulator_impl;
   typedef Traits manipulator_traits;
   typedef typename _base::iterator iterator;
   typedef typename _base::const_iterator const_iterator;

   template <typename FeatureCollector>
   struct rebind_feature_collector {
      typedef container_chain_impl<FeatureCollector,Traits> type;
   };

   iterator begin()
   {
      return iterator(*this);
   }
   iterator end()
   {
      return iterator(*this, true);
   }
   const_iterator begin() const
   {
      return const_iterator(*this);
   }
   const_iterator end() const
   {
      return const_iterator(*this, true);
   }

   int size() const
   {
      return this->top().get_container1().size() + this->top().get_container2().size();
   }
   bool empty() const
   {
      return this->top().get_container1().empty() && this->top().get_container2().empty();
   }
   int dim() const
   {
      return get_dim(this->top().get_container1()) + get_dim(this->top().get_container2());
   }
};

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

template <typename Top, typename Traits>
class container_chain_impl<Top, Traits, bidirectional_iterator_tag>
   : public container_chain_impl<Top, Traits, forward_iterator_tag> {
   typedef container_chain_impl<Top, Traits, forward_iterator_tag> _super;
public:
   typedef iterator_chain<typename container_chain_traits<typename _super::container_list, typename _super::needed_features>::reverse_iterator_list,
			  True>
      reverse_iterator;
   typedef iterator_chain<typename container_chain_traits<typename _super::container_list, typename _super::needed_features>::const_reverse_iterator_list,
			  True>
      const_reverse_iterator;

   reverse_iterator rbegin()
   {
      return reverse_iterator(*this);
   }
   reverse_iterator rend()
   {
      return reverse_iterator(*this, true);
   }
   const_reverse_iterator rbegin() const
   {
      return const_reverse_iterator(*this);
   }
   const_reverse_iterator rend() const
   {
      return const_reverse_iterator(*this, true);
   }

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

template <typename Top, typename Traits>
class container_chain_impl<Top, Traits, random_access_iterator_tag>
   : public container_chain_impl<Top, Traits, bidirectional_iterator_tag> {
   typedef container_chain_impl<Top, Traits, bidirectional_iterator_tag> _super;
public:
   typename _super::reference operator[] (int i)
   {
      const int d1=get_dim(this->top().get_container1());
      if (i<d1) return this->top().get_container1()[i];
      return this->top().get_container2()[i-d1];
   }
   typename _super::const_reference operator[] (int i) const
   {
      const int d1=get_dim(this->top().get_container1());
      if (i<d1) return this->top().get_container1()[i];
      return this->top().get_container2()[i-d1];
   }
};

template <typename ContainerRef1, typename ContainerRef2>
class ContainerChain
   : public container_pair_base<ContainerRef1, ContainerRef2, true>,
     public container_chain_impl< ContainerChain<ContainerRef1,ContainerRef2>,
	       cons< Container1< ContainerRef1 >,
		     Container2< ContainerRef2 > >
            > {
   typedef container_pair_base<ContainerRef1, ContainerRef2, true> _base;
public:
   ContainerChain(typename _base::first_arg_type src1_arg, typename _base::second_arg_type src2_arg)
      : _base(src1_arg,src2_arg) { }
};

template <typename ContainerRef1, typename ContainerRef2>
struct spec_object_traits< ContainerChain<ContainerRef1, ContainerRef2> >
   : spec_object_traits<is_container> {
   static const bool is_temporary=true,
                     is_always_const=effectively_const<ContainerRef1>::answer || effectively_const<ContainerRef2>::answer;
};

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

template <typename ContainerRef1, typename ContainerRef2>
struct check_container_feature<ContainerChain<ContainerRef1, ContainerRef2>, pure_sparse> {
   static const bool answer=check_container_ref_feature<ContainerRef1, pure_sparse>::answer &&
                            check_container_ref_feature<ContainerRef2, pure_sparse>::answer;
};

template <typename Container1, typename Container2> inline
ContainerChain<Container1&, Container2&>
concatenate(Container1& c1, Container2& c2)
{
   return ContainerChain<Container1&, Container2&> (c1,c2);
}

template <typename Container1, typename Container2> inline
ContainerChain<Container1&, const Container2&>
concatenate(Container1& c1, const Container2& c2)
{
   return ContainerChain<Container1&, const Container2&> (c1,c2);
}

template <typename Container1, typename Container2> inline
ContainerChain<const Container1&, Container2&>
concatenate(const Container1& c1, Container2& c2)
{
   return ContainerChain<const Container1&, Container2&> (c1,c2);
}

template <typename Container1, typename Container2> inline
ContainerChain<const Container1&, const Container2&>
concatenate(const Container1& c1, const Container2& c2)
{
   return ContainerChain<const Container1&, const Container2&> (c1,c2);
}

namespace operations {

template <typename LeftRef, typename RightRef, bool check=false,
          typename Discr=typename isomorphic<typename deref<LeftRef>::type, typename deref<RightRef>::type>::discriminant>
struct concat_impl;

template <typename LeftRef, typename RightRef>
struct concat : concat_impl<LeftRef,RightRef> { };

} // end namespace operations
} // end namespace pm

namespace polymake {
   using pm::concatenate;

   namespace operations {
      typedef BuildBinary<pm::operations::concat> concat;
   }
}

#endif // _POLYMAKE_CONTAINER_CHAIN_H

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