/* Copyright (c) 1997-2004
   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.14 2004/06/22 16:22:46 gawrilow Exp $"

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

namespace pm {

template <typename ChainTypebase, typename Iterator, typename ExpectedFeatures>
struct iterator_chain_functions {
   typedef typename ChainTypebase::container_list container_list;
   static const bool is_reverse=list_contains<ExpectedFeatures,_reversed>::answer;
   static const int length=list_length<container_list>::answer, last_index=length-1;

   template <int index> struct common {
      static const int container_index= is_reverse ? last_index-index : index;
      typedef int2type<container_index> discr;
   };
   struct length_def {
      static const int length=iterator_chain_functions::length;
   };
   struct init : length_def {
      template <int index> struct defs {
	 static void _do(ChainTypebase& c, Iterator& it) {
	    it=ensure(c.get_container((typename common<index>::discr*)0), (ExpectedFeatures*)0).begin();
	 }
      };
      typedef void (*fpointer) (ChainTypebase&, Iterator&);
   };
   struct dim : length_def {
      template <int index> struct defs : common<index> {
	 static int _do(const ChainTypebase& c) {
	    return get_dim(c.get_container((typename common<index>::discr*)0));
	 }
	 static const int next_index= index+(index<last_index);
	 static int accumulate(const ChainTypebase& c) {
	    int d=_do(c);
	    if (index<last_index) d+=defs<next_index>::accumulate(c);
	    return d;
	 }
      };
      typedef int (*fpointer) (const ChainTypebase&);
   };
};

template <typename ChainTypebase, typename Iterator, typename ExpectedFeatures>
class iterator_chain : public iterator_traits<Iterator>::derivable_type {
protected:
   typedef typename iterator_traits<Iterator>::derivable_type super;
   ChainTypebase *owner;
   int chain_index, offset;

   typedef iterator_chain_functions<ChainTypebase, Iterator, ExpectedFeatures> Functions;

   static const bool
      is_reverse=list_contains<ExpectedFeatures, _reversed>::answer,
      is_indexed=check_iterator_feature<Iterator,indexed>::answer;

   void _init_offset(False*) { }
   void _init_offset(True*) {
      offset= is_reverse ? Functions::dim::template defs<1>::accumulate(*owner) : 0;
   }
   void _incr_offset(False*) { }
   void _incr_offset(True*) {
      offset += virtuals::table<typename Functions::dim>::call(chain_index)(*owner);
   }
   void _decr_offset(False*) { }
   void _decr_offset(True*) {
      offset -= virtuals::table<typename Functions::dim>::call(chain_index)(*owner);
   }

   void _init() {
      chain_index=0;
      Functions::init::template defs<0>::_do(*owner, *this);
      _init_offset((bool2type<is_indexed>*)0);
      if (super::at_end()) valid_position();
   }

   void valid_position() {
      do {
	 if (!is_reverse) _incr_offset((bool2type<is_indexed>*)0);
	 if (++chain_index == Functions::length) return;
	 if (is_reverse) _decr_offset((bool2type<is_indexed>*)0);
	 virtuals::table<typename Functions::init>::call(chain_index)(*owner, *this);
      } while (super::at_end());
   }

   template <typename,typename> friend class iterator_union;
   template <typename,typename,typename> friend class iterator_chain;
public:
   typedef forward_iterator_tag iterator_category;
   typedef iterator_chain<typename deref<ChainTypebase>::type, typename iterator_traits<Iterator>::iterator, ExpectedFeatures>
      iterator;
   typedef iterator_chain<const ChainTypebase, typename iterator_traits<Iterator>::const_iterator, ExpectedFeatures>
      const_iterator;

   iterator_chain(ChainTypebase *owner_arg=0)
      : owner(owner_arg) {
      if (owner) _init(); else chain_index=Functions::length;
   }

   iterator_chain(const iterator& it)
      : super(static_cast<const typename iterator::super&>(it)),
	owner(it.owner), chain_index(it.chain_index), offset(it.offset) { }

   iterator_chain& operator++ () {
      super::operator++();
      if (super::at_end()) valid_position();
      return *this;
   }
   const iterator_chain operator++ (int) { iterator_chain copy=*this; operator++(); return copy; }

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

   bool at_end() const { return chain_index == Functions::length; }
   void reset() { _init(); }
   int index() const { return super::index()+offset; }
};

template <typename ChainTypebase, typename Iterator, typename ExpectedFeatures, typename Feature>
struct check_iterator_feature<iterator_chain<ChainTypebase, Iterator, ExpectedFeatures>, Feature>
   : check_iterator_feature<Iterator, Feature> { };

template <typename ChainTypebase, typename Iterator, typename ExpectedFeatures>
struct check_iterator_feature<iterator_chain<ChainTypebase, Iterator, ExpectedFeatures>, resettable> : True { };

template <typename Container,
	  bool _descend=is_instance3_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 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 union_container_traits<container_list, needed_features> ctraits;

   typedef typename ctraits::reference reference;
   typedef typename ctraits::const_reference const_reference;
   typedef typename deref<reference>::type value_type;
   typedef typename ctraits::category category;

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

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

   template <int pos>
   typename n_th<container_list, pos>::car&
   get_container(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(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(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(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>*)
   {
      const int side= pos >= list_length<typename helper1::container_list>::answer,
	        discr= (side ? helper2::descend : helper1::descend)*2+side;
      return get_container((int2type<pos>*)0, (int2type<discr>*)0);
   }
   template <int pos>
   typename n_th<const_container_list, pos>::car&
   get_container(int2type<pos>*) const
   {
      const int side= pos >= list_length<typename helper1::container_list>::answer,
	        discr= (side ? helper2::descend : helper1::descend)*2+side;
      return get_container((int2type<pos>*)0, (int2type<discr>*)0);
   }
};

template <class Top, class Traits=typename Top::manipulator_traits,
	  class 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;

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

   typedef iterator_chain<_base, typename _base::ctraits::iterator, typename _base::needed_features> iterator;
   typedef iterator_chain<const _base, typename _base::ctraits::const_iterator, typename _base::needed_features> const_iterator;

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

   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_typebase<Top, Traits> _base;
   typedef container_chain_impl<Top, Traits, forward_iterator_tag> _super;
protected:
   typedef typename toggle_features<typename _super::needed_features, _reversed>::result needed_reverse_features;
public:
   typedef iterator_chain<_base, typename _base::ctraits::reverse_iterator, needed_reverse_features>
      reverse_iterator;
   typedef iterator_chain<const _base, typename _base::ctraits::const_reverse_iterator, needed_reverse_features>
      const_reverse_iterator;

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

   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:
