/* 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_ITERATOR_ZIPPER_H
#define _POLYMAKE_ITERATOR_ZIPPER_H "$Project: polymake $$Id: iterator_zipper.h,v 1.13 2004/06/22 16:22:43 gawrilow Exp $"

#if defined(__GNUC__) && __GNUC_MINOR__<3 && !defined(__APPLE__) && !defined(__COMO__)
#pragma interface
#endif

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

namespace pm {

enum {
   zipper_lt=1, zipper_eq=2, zipper_gt=4,	// correspond to 1<<cmp_XX+1
   zipper_cmp=zipper_lt+zipper_eq+zipper_gt,	// mask for all of them
   zipper_first= (zipper_lt<<6),		// first iterator is in a dereferenceable position
   zipper_second= (zipper_gt<<3),		// second iterator is ...
   zipper_both= zipper_first+zipper_second	// both are ...
};

struct set_union_zipper {
   static int stable(int) { return true; }
   static const bool end1=false, end2=false;
};

struct set_difference_zipper {
   static int stable(int state) { return state & zipper_lt; }
   static const bool end1=true, end2=false;
};

struct set_intersection_zipper {
   static int stable(int state) { return state & zipper_eq; }
   static const bool end1=true, end2=true;
};

struct set_symdifference_zipper {
   static int stable(int state) { return state & zipper_lt+zipper_gt; }
   static const bool end1=false, end2=false;
};

template <typename Iterator1, typename Iterator2, typename Comparator, typename Controller,
	  bool _use_index1=false, bool _use_index2=false>
class iterator_zipper : public iterator_traits<Iterator1>::derivable_type {
public:
   typedef Iterator1 first_type;
   typedef Iterator2 second_type;
   typedef forward_iterator_tag iterator_category;
   typedef iterator_zipper<typename iterator_traits<Iterator1>::iterator, typename iterator_traits<Iterator2>::iterator,
			   Comparator, Controller, _use_index1, _use_index2>
      iterator;
   typedef iterator_zipper<typename iterator_traits<Iterator1>::const_iterator, typename iterator_traits<Iterator2>::const_iterator,
			   Comparator, Controller, _use_index1, _use_index2>
      const_iterator;

   typedef typename iterator_traits<Iterator1>::derivable_type super;
   Iterator2 second;
protected:
   typedef typename if_else<_use_index1, const int*, Iterator1>::result app_iterator1;
   typedef typename if_else<_use_index2, const int*, Iterator2>::result app_iterator2;
   typedef binary_op_builder<Comparator, app_iterator1, app_iterator2> cmpb;
   typename cmpb::operation cmp;
   Controller ctl;
   int state;

   typename star_helper<app_iterator1, typename cmpb::operation::first_argument_type>::result_type
   get1(False*)
   {
      return star_helper<app_iterator1, typename cmpb::operation::first_argument_type>::get(*this);
   }
   typename star_helper<app_iterator2, typename cmpb::operation::second_argument_type>::result_type
   get2(False*)
   {
      return star_helper<app_iterator2, typename cmpb::operation::second_argument_type>::get(second);
   }
   int get1(True*) { return super::index(); }
   int get2(True*) { return second.index(); }

   void compare()
   {
      state &= ~zipper_cmp;
      state += 1 << cmp(get1((bool2type<_use_index1>*)0), get2((bool2type<_use_index2>*)0))+1;
   }

   void incr()
   {
      int cur_state=state;
      if (cur_state & int(zipper_lt)+int(zipper_eq)) {
	 super::operator++();
	 if (super::at_end()) {
	    if (ctl.end1) {
	       state=0; return;
	    } else {
	       state>>=3;
	    }
	 }
      }
      if (cur_state & int(zipper_gt)+int(zipper_eq)) {
	 ++second;
	 if (second.at_end()) {
	    if (ctl.end2) {
	       state=0;
	    } else {
	       state>>=6;
	    }
	 }
      }
   }

   void init()
   {
      state=zipper_both;
      if (super::at_end()) {
	 if (ctl.end1) {
	    state=0; return;
	 } else {
	    state>>=3;
	 }
      }
      if (second.at_end()) {
	 if (ctl.end2) {
	    state=0;
	 } else {
	    state>>=6;
	 }
	 return;
      }
      while (state>=zipper_both) {
	 compare();
	 if (ctl.stable(state)) break;
	 incr();
      }
   }

   template <typename,typename,typename,typename,bool,bool> friend class iterator_zipper;
   template <typename,typename,bool> friend class iterator_product;
public:
   iterator_zipper() : state(0) { }
   iterator_zipper(const iterator& it)
      : super(static_cast<const typename iterator::super&>(it)), second(it.second), state(it.state) { }

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

   iterator_zipper& operator++ ()
   {
      do {
	 incr();
	 if (state<zipper_both) break;
	 compare();
      } while (!ctl.stable(state));
      return *this;
   }
   const iterator_zipper operator++ (int) { iterator_zipper copy=*this; operator++(); return copy; }

   bool at_end() const { return state==0; }
   void reset() { super::reset(); second.reset(); init(); }
};

template <typename Iterator1, typename Iterator2, typename Comparator, typename Controller,
	  bool _use_index1, bool _use_index2, typename Feature>
struct check_iterator_feature<iterator_zipper<Iterator1, Iterator2, Comparator, Controller, _use_index1, _use_index2>,
			      Feature> {
   static const bool answer=check_iterator_feature<Iterator1, Feature>::answer &&
                            check_iterator_feature<Iterator2, Feature>::answer;
};

template <typename Iterator1, typename Iterator2, typename Comparator, typename Controller,
	  bool _use_index1, bool _use_index2>
struct check_iterator_feature<iterator_zipper<Iterator1, Iterator2, Comparator, Controller, _use_index1, _use_index2>,
			      partially_defined> : True { };

template <typename Comparator, typename Controller, bool _use_index1=false, bool _use_index2=false>
struct zipping_coupler {
   template <typename Iterator1, typename Iterator2, typename ExpectedFeatures>
   struct defs {
      typedef iterator_zipper<Iterator1,Iterator2,Comparator,Controller,_use_index1,_use_index2> iterator;
      typedef typename mix_features<ExpectedFeatures,
				    typename if_else<_use_index1, cons<indexed, end_sensitive>, end_sensitive>::result
                                   >::result
         needed_features1;
      typedef typename mix_features<ExpectedFeatures,
				    typename if_else<_use_index2, cons<indexed, end_sensitive>, end_sensitive>::result
                                   >::result
         needed_features2;
   };
};

namespace operations {

template <typename Iterator1Ref, typename Iterator2Ref>
struct zipper {
   typedef Iterator1Ref first_argument_type;
   typedef Iterator2Ref second_argument_type;
   typedef typename union_reference<typename iterator_traits<typename deref<Iterator1Ref>::type>::reference,
				    typename iterator_traits<typename deref<Iterator2Ref>::type>::reference>::type
      result_type;

   result_type operator() (first_argument_type l, second_argument_type) const { return *l; }
   result_type operator() (partial_left, first_argument_type l, second_argument_type) const { return *l; }
   result_type operator() (partial_right, first_argument_type, second_argument_type r) const { return *r; }
};

template <typename Iterator1Ref, typename Iterator2Ref>
struct zipper_index {
   typedef Iterator1Ref first_argument_type;
   typedef Iterator2Ref second_argument_type;
   typedef const int result_type;

   result_type operator() (first_argument_type l, second_argument_type) const { return l.index(); }
   result_type operator() (partial_left, first_argument_type l, second_argument_type) const { return l.index(); }
   result_type operator() (partial_right, first_argument_type, second_argument_type r) const { return r.index(); }
};
} // end namespace operations

template <typename IteratorPair, typename Operation>
class binary_transform_eval<IteratorPair, Operation, true> : public IteratorPair {
protected:
   typedef IteratorPair super;
   typedef binary_transform_eval<typename iterator_traits<IteratorPair>::iterator, Operation, true>
      alt_constructor_arg_type;

   typedef binary_helper<IteratorPair,Operation> helper;
   typedef typename helper::star1 star1;
   typedef typename helper::star2 star2;
   typedef typename helper::operation operation;
   operation op;

   binary_transform_eval() { }
   binary_transform_eval(const alt_constructor_arg_type& it)
      : super(static_cast<const typename alt_constructor_arg_type::super&>(it)),
	op(helper::create(it.op)) { }

   binary_transform_eval(const IteratorPair& cur_arg,
			 const Operation& op_arg)
      : super(cur_arg), op(helper::create(op_arg)) { }
   binary_transform_eval(typename alt_constructor<IteratorPair>::arg_type& cur_arg,
			 const Operation& 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 Operation& 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 Operation& 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
   {
      if (this->state & zipper_lt)
	 return op(operations::partial_left(), star1::get(*this), this->second);
      if (this->state & zipper_gt)
	 return op(operations::partial_right(), static_cast<const typename IteratorPair::super&>(*this), star2::get(this->second));
      // (this->state & zipper_eq)
      return op(star1::get(*this), star2::get(this->second));
   }
};

template <typename IteratorPair, typename Operation, typename IndexOperation>
class binary_transform_eval<IteratorPair, pair<Operation, IndexOperation>, true>
   : public binary_transform_eval<IteratorPair, Operation, true> {
   typedef binary_transform_eval<IteratorPair, Operation, true> _super;
protected:
   typedef pair<Operation, IndexOperation> op_pair;
   typedef binary_transform_eval<typename iterator_traits<IteratorPair>::iterator, op_pair, true>
      alt_constructor_arg_type;

   typedef binary_helper<IteratorPair,IndexOperation> ihelper;
   typedef typename ihelper::star1 istar1;
   typedef typename ihelper::star2 istar2;
   typename ihelper::operation iop;

   binary_transform_eval() { }
   binary_transform_eval(const alt_constructor_arg_type& it)
      : _super(static_cast<const typename alt_constructor_arg_type::_super&>(it)),
	iop(ihelper::create(it.iop)) { }

   binary_transform_eval(const IteratorPair& cur_arg,
			 const op_pair& 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_pair& 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_pair& 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_pair& 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;

protected:
   int _index(False*) const
   {
      return iop(istar1::get(*this), istar2::get(this->second));
   }

   int _index(True*) const
   {
      if (this->state & zipper_lt)
	 return iop(operations::partial_left(), istar1::get(*this), this->second);
      if (this->state & zipper_gt)
	 return iop(operations::partial_right(), static_cast<const typename IteratorPair::super&>(*this), istar2::get(this->second));
      // (this->state & zipper_eq)
      return _index((False*)0);
   }
public:
   int index() const
   {
      return _index((bool2type<operations::is_partially_defined<typename ihelper::operation>::answer>*)0);
   }
};

} // end namespace pm

#endif // _POLYMAKE_ITERATOR_ZIPPER_H

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