/* Copyright (c) 1997-2005
   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_CASCADED_CONTAINER_H
#define _POLYMAKE_CASCADED_CONTAINER_H "$Project: polymake $$Id: CascadedContainer.h,v 1.20 2005/09/28 11:15:35 gawrilow Exp $"

#ifndef _POLYMAKE_ITERATORS_H
#  include <iterators.h>
#endif

namespace pm {

template <typename Iterator, typename ExpectedFeatures, int depth> class cascaded_iterator;

template <typename Iterator, typename ExpectedFeatures, int depth>
struct cascaded_iterator_traits {
   static const bool
      accumulate_offset= depth==2 && (check_container_feature<typename iterator_traits<Iterator>::value_type, sparse>::answer ||
				      list_search<ExpectedFeatures, indexed, absorbing_feature>::answer);

   typedef typename ensure_features<typename attrib<typename iterator_traits<Iterator>::reference>::minus_ref,
				    ExpectedFeatures>::iterator
      down_iterator;
   typedef cascaded_iterator<down_iterator,
			     typename if_else<accumulate_offset, typename mix_features<ExpectedFeatures,indexed>::result,
				                                 ExpectedFeatures>::result,
			     depth-1>
      super;
};

template <typename Iterator, typename ExpectedFeatures, int depth>
class cascaded_iterator
   : public cascaded_iterator_traits<Iterator,ExpectedFeatures,depth>::super {
   typedef cascaded_iterator_traits<Iterator,ExpectedFeatures,depth> traits;
public:
   typedef cascaded_iterator<typename iterator_traits<Iterator>::iterator, ExpectedFeatures, depth>
      iterator;
   typedef cascaded_iterator<typename iterator_traits<Iterator>::const_iterator, ExpectedFeatures, depth>
      const_iterator;
   typedef typename traits::super super;
protected:
   template <typename,typename,int> friend class cascaded_iterator;
   typedef Iterator cur_it_type;
   Iterator cur;

   Iterator* get_cur() { return &cur; }

   bool init()
   {
      while (!cur.at_end()) {
	 typename Iterator::reference c=*cur;
	 typedef typename super::cur_it_type s_cur_it_type;
	 s_cur_it_type *s_cur=super::get_cur();
	 s_cur->~s_cur_it_type();
	 new(s_cur) s_cur_it_type(ensure(c,(ExpectedFeatures*)0).begin());
	 if (depth==2) this->store_dim(c);
	 if (super::init()) return true;
	 if (depth==2) this->adjust_offset();
	 ++cur;
      }
      return false;
   }

   bool incr()
   {
      if (super::incr()) return true;
      if (depth==2) this->adjust_offset();
      ++cur;
      return init();
   }

public:
   cascaded_iterator() { }
   cascaded_iterator(const Iterator& cur_arg)
      : cur(cur_arg) { init(); }
   cascaded_iterator(typename alt_constructor<Iterator>::arg_type& cur_arg)
      : cur(cur_arg) { init(); }

   cascaded_iterator(const iterator& it)
      : super(it), cur(it.cur) { }

   cascaded_iterator& operator= (const iterator& it)
   {
      cur=it.cur;
      super::operator=(it);
      return *this;
   }

   cascaded_iterator& operator++ () { incr(); return *this; }
   const cascaded_iterator operator++ (int) { cascaded_iterator copy=*this; operator++(); return copy; }

   bool operator== (const iterator& it) const
   {
      return cur==it.cur && super::operator==(it);
   }
   bool operator== (typename assign_const<const_iterator, !identical<iterator,const_iterator>::answer>::type& it)
   {
      return cur==it.cur && super::operator==(it);
   }

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

   bool at_end() const { return cur.at_end(); }

   void reset()
   {
      typedef typename enable_if<void, check_iterator_feature<Iterator,resettable>::answer>::type error_if_unimplemented;
      cur.reset(); init();
   }
};

template <bool _need_index>
class cascaded_iterator_index_store {
protected:
   template <typename Container>
   void store_dim(const Container&) { }
   void adjust_offset() { }
};

template <>
class cascaded_iterator_index_store<true> {
protected:
   int offset, dim;

   cascaded_iterator_index_store() : offset(0) { }

   template <typename Container>
   void store_dim(const Container& c) { dim=get_dim(c); }
   void adjust_offset() { offset+=dim; }
};

template <typename Iterator, typename ExpectedFeatures>
class cascaded_iterator<Iterator, ExpectedFeatures, 1>
   : public Iterator,
     protected cascaded_iterator_index_store<list_search_all<ExpectedFeatures, indexed, absorbing_feature>::answer> {
public:
   typedef Iterator super;
protected:
   typedef cascaded_iterator_index_store<list_search_all<ExpectedFeatures, indexed, absorbing_feature>::answer> index_store;
   template <typename,typename,int> friend class cascaded_iterator;

   typedef Iterator cur_it_type;
   Iterator* get_cur() { return this; }

   bool init() { return !this->at_end(); }

   bool incr()
   {
      super::operator++();
      return !this->at_end();
   }
public:
   typedef forward_iterator_tag iterator_category;

   cascaded_iterator() { }
   cascaded_iterator(const cascaded_iterator<typename iterator_traits<Iterator>::iterator, ExpectedFeatures, 1>& it)
      : super(it), index_store(it) { }

   cascaded_iterator& operator= (const cascaded_iterator<typename iterator_traits<Iterator>::iterator, ExpectedFeatures, 1>& it)
   {
      super::operator=(it);
      index_store::operator=(it);
      return *this;
   }

   int index() const { return super::index()+this->offset; }
};

template <typename Iterator, typename ExpectedFeatures, int depth, typename Feature>
struct check_iterator_feature<cascaded_iterator<Iterator, ExpectedFeatures, depth>, Feature>
   : check_iterator_feature<typename cascaded_iterator<Iterator, ExpectedFeatures, depth>::super, Feature> { };

template <typename Iterator, typename ExpectedFeatures, int depth>
struct check_iterator_feature<cascaded_iterator<Iterator, ExpectedFeatures, depth>, resettable>
   : check_iterator_feature<Iterator, resettable> { };

template <typename> class CascadeDepth { };

template <typename Container, int depth>
struct cascade_traits : cascade_traits<typename container_traits<Container>::value_type, depth-1> {
   typedef typename least_derived< cons<typename container_traits<Container>::category,
					typename cascade_traits<typename container_traits<Container>::value_type, depth-1>::category> >::type
      category;
};

template <typename Container>
struct cascade_traits<Container, 1> : container_traits<Container> {
   typedef typename least_derived< cons<typename container_traits<Container>::category,
					bidirectional_iterator_tag> >::type
      category;
   typedef Container base_container;
};

template <typename Top, typename Traits>
class cascade_typebase : public manip_container_top<Top, Traits> {
   typedef manip_container_top<Top, Traits> _super;
public:
   typedef typename deref<typename extract_type_param<Traits,Container,typename _super::hidden_type>::result>::minus_ref container;
   static const int depth=extract_int_param<Traits, CascadeDepth>::result;
   typedef dense can_enforce_features;
   typedef typename mix_features<typename _super::expected_features, end_sensitive>::result needed_features;
   typedef typename list_search_all<needed_features, resettable, identical>::negative needed_down_features;
   typedef cascaded_iterator<typename ensure_features<container,needed_features>::iterator, needed_down_features, depth>
      iterator;
   typedef cascaded_iterator<typename ensure_features<container,needed_features>::const_iterator, needed_down_features, depth>
      const_iterator;
   typedef typename iterator::reference reference;
   typedef typename const_iterator::reference const_reference;
   typedef typename iterator::value_type value_type;

   typedef cascade_traits<container,depth> base_traits;
   typedef typename base_traits::category category;
};

template <typename Top, typename Traits=typename Top::manipulator_traits,
          typename Category=typename cascade_typebase<Top,Traits>::category>
class cascade_impl
   : public cascade_typebase<Top,Traits> {
   typedef cascade_typebase<Top,Traits> _super;
public:
   typedef Traits manipulator_traits;
   typedef cascade_impl<Top,Traits> manipulator_impl;
   typedef typename _super::iterator iterator;
   typedef typename _super::const_iterator const_iterator;

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

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

   int size() const
   {
      return cascade_size(this->top().get_container(), (int2type<_super::depth>*)0);
   }
   bool empty() const
   {
      return cascade_empty(this->top().get_container(), (int2type<_super::depth>*)0);
   }
   int dim() const
   {
      return cascade_dim(this->top().get_container(), (int2type<_super::depth>*)0);
   }
};

template <typename Top, typename Traits>
class cascade_impl<Top, Traits, forward_iterator_tag>
   : public cascade_impl<Top, Traits, input_iterator_tag> {
   typedef cascade_impl<Top, Traits, input_iterator_tag> _super;
public:
   typename _super::reference front() { return *this->begin(); }
   typename _super::const_reference front() const { return *this->begin(); }
};

template <typename Top, typename Traits>
class cascade_impl<Top, Traits, bidirectional_iterator_tag>
   : public cascade_impl<Top, Traits, forward_iterator_tag> {
   typedef cascade_impl<Top, Traits, forward_iterator_tag> _super;
public:
   typedef typename toggle_features<typename _super::needed_features, _reversed>::result
      needed_reverse_features;
   typedef typename toggle_features<typename _super::needed_down_features, _reversed>::result
      needed_reverse_down_features;
   typedef cascaded_iterator<typename ensure_features<typename _super::container, needed_reverse_features>::iterator,
			     needed_reverse_down_features, cascade_typebase<Top,Traits>::depth>
      reverse_iterator;
   typedef cascaded_iterator<typename ensure_features<typename _super::container, needed_reverse_features>::const_iterator,
                             needed_reverse_down_features, cascade_typebase<Top,Traits>::depth>
      const_reverse_iterator;

   reverse_iterator rbegin()
   {
      return reverse_iterator(ensure(this->top().get_container(), (needed_reverse_features*)0).begin());
   }
   reverse_iterator rend()
   {
      return reverse_iterator(ensure(this->top().get_container(), (needed_reverse_features*)0).end());
   }
   const_reverse_iterator rbegin() const
   {
      return const_reverse_iterator(ensure(this->top().get_container(), (needed_reverse_features*)0).begin());
   }
   const_reverse_iterator rend() const
   {
      return const_reverse_iterator(ensure(this->top().get_container(), (needed_reverse_features*)0).end());
   }

   typename _super::reference back() { return *rbegin(); }
   typename _super::const_reference back() const { return *rbegin(); }
};

template <typename Container, int depth> inline
int cascade_size(const Container& c, int2type<depth>*)
{
   int size=0;
   for (typename Entire<Container>::const_iterator i=entire(c); !i.at_end(); ++i)
      size+=cascade_size(*i, (int2type<depth-1>*)0);
   return size;
}

template <typename Container> inline
int cascade_size(const Container& c, int2type<1>*)
{
   return c.size();
}

template <typename Container, int depth> inline
int cascade_dim(const Container& c, int2type<depth>*)
{
   int d=0;
   for (typename Entire<Container>::const_iterator i=entire(c); !i.at_end(); ++i)
      d+=cascade_dim(*i, (int2type<depth-1>*)0);
   return d;
}

template <typename Container> inline
int cascade_dim(const Container& c, int2type<1>*)
{
   return get_dim(c);
}

template <typename Container, int depth> inline
bool cascade_empty(const Container& c, int2type<depth>*)
{
   for (typename Entire<Container>::const_iterator i=entire(c); !i.at_end(); ++i)
      if (!cascade_empty(*i, (int2type<depth-1>*)0)) return false;
   return true;
}

template <typename Container> inline
bool cascade_empty(const Container& c, int2type<1>*)
{
   return c.empty();
}

template <typename ContainerRef, int depth=object_traits<typename deref<ContainerRef>::type>::nesting_level>
class CascadedContainer
   : public cascade_impl< CascadedContainer<ContainerRef,depth>,
	       cons< Container< ContainerRef >,
		     CascadeDepth< int2type<depth> > >
            > {
protected:
   typedef typename alias<ContainerRef>::arg_type arg_type;
   alias<ContainerRef> src;
public:
   CascadedContainer(arg_type src_arg) : src(src_arg) { }

   typename deref<ContainerRef>::plus_ref get_container() { return src; }
   typename deref<ContainerRef>::plus_const_ref get_container() const { return src; }
};

template <typename ContainerRef, int depth>
struct check_container_feature<CascadedContainer<ContainerRef, depth>, sparse>
   : check_container_feature<typename CascadedContainer<ContainerRef,depth>::base_traits::base_container, sparse> { };

template <typename ContainerRef, int depth>
struct check_container_feature<CascadedContainer<ContainerRef, depth>, pure_sparse>
   : check_container_feature<typename CascadedContainer<ContainerRef,depth>::base_traits::base_container, pure_sparse> { };

template <typename ContainerRef, int depth>
struct spec_object_traits< CascadedContainer<ContainerRef, depth> >
   : spec_object_traits<is_container> {
   static const bool is_temporary=true;
};

template <typename Container> inline
CascadedContainer<Container&>
cascade(Container& c) { return c; }

template <typename Container> inline
CascadedContainer<const Container&>
cascade(const Container& c) { return c; }

template <int depth, typename Container> inline
CascadedContainer<Container&, depth>
cascade(Container& c, int2type<depth>*) { return c; }

template <int depth, typename Container> inline
CascadedContainer<const Container&, depth>
cascade(const Container& c, int2type<depth>*) { return c; }

template <typename Iterator, typename Value, typename ExpectedFeatures=void,
	  typename Model=typename object_traits<typename iterator_traits<Iterator>::value_type>::model,
	  bool _match=isomorphic<typename iterator_traits<Iterator>::value_type, Value>::answer>
struct construct_cascade_helper {
   static const int depth=1;
   typedef Iterator& result_type;
};

template <typename Iterator, typename Value, typename ExpectedFeatures>
struct construct_cascade_helper<Iterator, Value, ExpectedFeatures, is_container, false> {
   static const int depth=construct_cascade_helper<typename iterator_traits<Iterator>::value_type::iterator, Value, ExpectedFeatures>::depth+1;
   typedef cascaded_iterator<Iterator, typename mix_features<ExpectedFeatures, end_sensitive>::result, depth> result_type;
};

template <typename Value, typename Iterator> inline
typename construct_cascade_helper<Iterator,Value>::result_type
construct_matching_iterator(Iterator& src) { return src; }

template <typename Value, typename Iterator, typename ExpectedFeatures> inline
typename construct_cascade_helper<Iterator,Value,ExpectedFeatures>::result_type
construct_matching_iterator(Iterator& src, ExpectedFeatures*) { return src; }

} // end namespace pm

namespace polymake {
   using pm::cascade;
   using pm::construct_matching_iterator;
} // end namespace polymake

#endif // _POLYMAKE_CASCADED_CONTAINER_H

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