/* 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_INDEXED_SUBSET_H
#define _POLYMAKE_INDEXED_SUBSET_H "$Project: polymake $$Id: IndexedSubset.h,v 1.17 2004/06/22 16:22:45 gawrilow Exp $"

#ifndef _POLYMAKE_GENERIC_SET_H
#  include <GenericSet.h>
#endif

namespace pm {

template <typename Iterator1, typename Iterator2, bool renumber,
          typename Category=typename least_derived< cons<typename iterator_traits<Iterator1>::iterator_category,
							 typename iterator_traits<Iterator2>::iterator_category> >::type>
class indexed_selector
   : public iterator_traits<Iterator1>::derivable_type {
public:
   typedef Iterator1 first_type;
   typedef Iterator2 second_type;

   typedef typename iterator_traits<Iterator1>::derivable_type super;
   Iterator2 second;
protected:
   typedef indexed_selector<Iterator1,Iterator2,renumber> me;
   typedef bool2type<(derived_from<Iterator2, series::iterator>::answer &&
		      identical<typename comparable_iterator<Iterator2>::type, sequence::iterator>::answer)> *step_discr;
private:
   int _index(False*) const { return super::index(); }
   int _index(True*) const { return second.index(); }

   int _step(False*)
   {
      int pos=*second;
      ++second;
      return at_end() ? 0 : *second-pos;
   }
   int _step(True*)
   {
      ++second;
      return second.step();
   }
   int _step()
   {
      return _step((step_discr)0);
   }

public:
   typedef typename least_derived< cons<typename iterator_traits<Iterator1>::iterator_category,
					typename iterator_traits<Iterator2>::iterator_category> >::type
      iterator_category;
   typedef typename iterator_traits<Iterator2>::difference_type difference_type;
   typedef indexed_selector<typename iterator_traits<Iterator1>::iterator, Iterator2, renumber> iterator;
   typedef indexed_selector<typename iterator_traits<Iterator1>::const_iterator, Iterator2, renumber> const_iterator;

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

   indexed_selector(const Iterator1& first_arg, const Iterator2& second_arg, bool adjust=false)
      : super(first_arg), second(second_arg)
   {
      if (adjust && !at_end()) std::advance(static_cast<super&>(*this), *second);
   }

   indexed_selector(typename alt_constructor<Iterator1>::arg_type& first_arg,
		    typename alt_constructor<Iterator2>::arg_type& second_arg, bool adjust=false)
      : super(first_arg), second(second_arg)
   {
      if (adjust && !at_end()) std::advance(static_cast<super&>(*this), *second);
   }

   me& operator++ ()
   {
      std::advance(static_cast<super&>(*this), _step() );
      return static_cast<me&>(*this);
   }
   const me operator++ (int) { me copy=static_cast<me&>(*this); operator++(); return copy; }

   bool operator== (const me& it) const { return second==it.second; }
   bool operator!= (const me& it) const { return !operator==(it); }

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

   int index() const
   {
      return _index((bool2type<renumber>*)0);
   }
   void reset()
   {
      super::reset(); second.reset();
   }
   void narrow_range(int distance_front, int distance_back, bool _renumber)
   {
      int pos=*second;
      second.narrow_range(distance_front, distance_back, _renumber);
      pm::narrow_range(static_cast<super&>(*this), *second-pos, 0, _renumber);
   }
};

template <typename Iterator1, typename Iterator2, bool renumber>
class indexed_selector<Iterator1, Iterator2, renumber, bidirectional_iterator_tag>
   : public indexed_selector<Iterator1, Iterator2, renumber, forward_iterator_tag> {
   typedef indexed_selector<Iterator1, Iterator2, renumber, forward_iterator_tag> _super;

   int _step(False*)
   {
      if (this->at_end()) {
	 --this->second;
	 return 0;
      }
      int pos=*this->second;
      --this->second;
      return *this->second-pos;
   }
   int _step(True*)
   {
      --this->second;
      return -this->second.step();
   }
   int _step()
   {
      return _step((typename _super::step_discr)0);
   }
public:
   indexed_selector() { }
   indexed_selector(const typename _super::iterator& it)
      : _super(it) { }

   indexed_selector(const Iterator1& first_arg, const Iterator2& second_arg, bool adjust=false)
      : _super(first_arg, second_arg,adjust) { }
   indexed_selector(typename alt_constructor<Iterator1>::arg_type& first_arg,
		    typename alt_constructor<Iterator2>::arg_type& second_arg, bool adjust=false)
      : _super(first_arg, second_arg,adjust) { }

   typename _super::me& operator--()
   {
      std::advance(static_cast<typename _super::super&>(*this), _step());
      return static_cast<typename _super::me&>(*this);
   }
   const typename _super::me operator-- (int)
   {
      typename _super::me copy=static_cast<typename _super::me&>(*this); operator--();
      return copy;
   }
};

template <typename Iterator1, typename Iterator2, bool renumber>
class indexed_selector<Iterator1, Iterator2, renumber, random_access_iterator_tag>
   : public indexed_selector<Iterator1, Iterator2, renumber, bidirectional_iterator_tag> {
   typedef indexed_selector<Iterator1, Iterator2, renumber, bidirectional_iterator_tag> _super;

   int _step(int i, False*)
   {
      int pos=this->at_end() ? this->second[-1] : *this->second;
      this->second+=i;
      return (this->at_end() ? this->second[-1] : *this->second)-pos;
   }
   int _step(int i, True*)
   {
      this->second+=i;
      return this->second.step()*i;
   }
   int _step(int i)
   {
      return _step(i, (typename _super::step_discr)0);
   }
public:
   indexed_selector() { }
   indexed_selector(const typename _super::iterator& it)
      : _super(it) { }

   indexed_selector(const Iterator1& first_arg, const Iterator2& second_arg, bool adjust=false)
      : _super(first_arg,second_arg,adjust) { }
   indexed_selector(typename alt_constructor<Iterator1>::arg_type& first_arg,
		    typename alt_constructor<Iterator2>::arg_type& second_arg, bool adjust=false)
      : _super(first_arg,second_arg,adjust) { }

   indexed_selector& operator+= (int i)
   {
      static_cast<typename indexed_selector::super&>(*this) += _step(i);
      return *this;
   }

   indexed_selector& operator-= (int i)
   {
      static_cast<typename indexed_selector::super&>(*this) += _step(-i);
      return *this;
   }

   const indexed_selector operator+ (int i) const { indexed_selector copy=*this; return copy+=i; }
   const indexed_selector operator- (int i) const { indexed_selector copy=*this; return copy-=i; }
   friend const indexed_selector operator+ (int i, const indexed_selector& it) { return it+i; }

   typename _super::reference operator[] (int i) const
   {
      return static_cast<const typename indexed_selector::super&>(*this)[ this->second[i] - (this->at_end() ? this->second[-1] : *this->second) ];
   }
   typename _super::difference_type operator- (const indexed_selector& it) const
   {
      return this->second - it.second;
   }
};

template <typename Iterator1, typename Iterator2, bool renumber, typename Category, typename Feature>
struct check_iterator_feature<indexed_selector<Iterator1,Iterator2,renumber,Category>, Feature> {
   typedef has_narrow_range yes;
   typedef cons<end_sensitive, range_capable> via_second;
   static const bool answer= list_contains<yes, Feature>::answer ||
                             (list_contains<via_second, Feature>::answer ||
				  check_iterator_feature<Iterator1,Feature>::answer) &&
			         check_iterator_feature<Iterator2,Feature>::answer;
};

template <typename Iterator1, typename Iterator2, bool renumber, typename Category>
struct check_iterator_feature<indexed_selector<Iterator1,Iterator2,renumber,Category>, indexed> {
   static const bool answer= renumber ? check_iterator_feature<Iterator2,indexed>::answer
                                      : check_iterator_feature<Iterator1,indexed>::answer;
};

template <typename Iterator1, typename Iterator2, typename IndexComparator, bool renumber,
          typename Category=typename least_derived< cons<typename iterator_traits<Iterator1>::iterator_category,
							 typename iterator_traits<Iterator2>::iterator_category> >::type>
class sparse_indexed_selector : public Iterator1 {
public:
   typedef Iterator1 first_type;
   typedef Iterator2 second_type;

   typedef Iterator1 super;
   Iterator2 second;
protected:
   typedef sparse_indexed_selector<Iterator1,Iterator2,IndexComparator,renumber> me;
   typedef binary_op_builder<IndexComparator, const int*, Iterator2> cmpb;

   bool _at_end;
   typename cmpb::operation icmp;
private:
   void valid_position()
   {
      if (Iterator1::at_end() || second.at_end()) {
	 _at_end=true;
	 return;
      }
      while (1) {
	 switch (icmp(super::index(),*second)) {
	 case cmp_lt:
	    Iterator1::operator++();
	    if (Iterator1::at_end()) {
	       _at_end=true; return;
	    }
	    break;
	 case cmp_gt:
	    ++second;
	    if (second.at_end()) {
	       _at_end=true; return;
	    }
	    break;
	 case cmp_eq:
	    return;
	 }
      }
   }

   int _index(False*) const { return super::index(); }
   int _index(True*) const { return second.index(); }
public:
   typedef typename least_derived< cons<typename iterator_traits<Iterator1>::iterator_category,
					typename iterator_traits<Iterator2>::iterator_category> >::type
      iterator_category;
   typedef typename iterator_traits<Iterator2>::difference_type difference_type;
   typedef sparse_indexed_selector<typename iterator_traits<Iterator1>::iterator, Iterator2, IndexComparator, renumber>
      iterator;
   typedef sparse_indexed_selector<typename iterator_traits<Iterator1>::const_iterator, Iterator2, IndexComparator, renumber>
      const_iterator;

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

   sparse_indexed_selector(const Iterator1& first_arg, const Iterator2& second_arg)
      : super(first_arg), second(second_arg), _at_end(false)
   {
      valid_position();
   }
   sparse_indexed_selector(typename alt_constructor<Iterator1>::arg_type& first_arg,
			   typename alt_constructor<Iterator2>::arg_type& second_arg)
      : super(first_arg), second(second_arg), _at_end(false)
   {
      valid_position();
   }

   me& operator++ ()
   {
      Iterator1::operator++(); ++second;
      valid_position();
      return static_cast<me&>(*this);
   }
   const me operator++ (int) { me copy=static_cast<me&>(*this); operator++(); return copy; }

   bool operator== (const me& it) const
   {
      return second==it.second;
   }
   bool operator!= (const me& it) const { return !operator==(it); }
   bool at_end() const { return _at_end; }

   void reset()
   {
      Iterator1::reset(); second.reset();
      valid_position();
   }
   int index() const
   {
      return _index((bool2type<renumber>*)0);
   }
};

template <typename Iterator1, typename Iterator2, typename IndexComparator, bool renumber>
class sparse_indexed_selector<Iterator1, Iterator2, IndexComparator, renumber, bidirectional_iterator_tag>
   : public sparse_indexed_selector<Iterator1, Iterator2, IndexComparator, renumber, forward_iterator_tag> {
   typedef sparse_indexed_selector<Iterator1, Iterator2, IndexComparator, renumber, forward_iterator_tag> _super;

   void valid_position()
   {
      this->_at_end=false;
      while (1) {
	 cmp_value idiff;
	 int pos=*this->second;
	 while ((idiff=icmp(Iterator1::index(),pos))==cmp_gt)
	    Iterator1::operator--();
	 if (idiff==cmp_eq) return;
	 --this->second;
      }
   }
public:
   sparse_indexed_selector() { }
   sparse_indexed_selector(const typename _super::iterator& it)
      : _super(it) { }

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

   sparse_indexed_selector& operator--()
   {
      Iterator1::operator--(); --this->second;
      valid_position();
      return *this;
   }
};

template <typename Iterator1, typename Iterator2, typename IndexComparator, bool renumber, typename Category, typename Feature>
struct check_iterator_feature<sparse_indexed_selector<Iterator1,Iterator2,IndexComparator,renumber,Category>, Feature> {
   static const bool answer=check_iterator_feature<Iterator1, Feature>::answer &&
                            check_iterator_feature<Iterator2, Feature>::answer;
};

template <typename Iterator1, typename Iterator2, typename IndexComparator, bool renumber, typename Category>
struct check_iterator_feature<sparse_indexed_selector<Iterator1,Iterator2,IndexComparator,renumber,Category>, indexed> {
   static const bool answer= renumber ? check_iterator_feature<Iterator2,indexed>::answer
                                      : check_iterator_feature<Iterator1,indexed>::answer;
};

template <bool _reverse, bool renumber>
struct sparse_indexed_selector_coupler {
   typedef typename if_else<_reverse, reverse_comparator< BuildBinary<operations::cmp> >, BuildBinary<operations::cmp> >::result
      IndexComparator;
   template <typename Iterator1, typename Iterator2, typename ExpectedFeatures>
   struct defs {
      typedef sparse_indexed_selector<Iterator1, Iterator2, IndexComparator, renumber> iterator;
      typedef ExpectedFeatures needed_features1;  // is already sparse
      typedef typename mix_features<ExpectedFeatures,
				    typename if_else<renumber,
						     cons<enforce_construction<indexed>,
							  cons<reference_relaxed, end_sensitive> >,
						     cons<reference_relaxed, end_sensitive>
                                                    >::result
                                   >::result
         needed_features2;
   };
};

template <typename Iterator1, typename Iterator2, bool renumber>
class contiguous_indexed_selector
   : public iterator_pair<Iterator1, Iterator2, FeaturesViaSecond<end_sensitive> > {
   typedef iterator_pair<Iterator1, Iterator2, FeaturesViaSecond<end_sensitive> > _super;

   int _index(False*) const { return *this->second; }
   int _index(True*) const { return this->second.index(); }
public:
   typedef contiguous_indexed_selector<typename iterator_traits<Iterator1>::iterator, Iterator2, renumber>
      iterator;
   typedef contiguous_indexed_selector<typename iterator_traits<Iterator1>::const_iterator, Iterator2, renumber>
      const_iterator;

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

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

   int index() const
   {
      return _index((bool2type<renumber>*)0);
   }

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

template <typename Iterator1, typename Iterator2, bool renumber, typename Feature>
struct check_iterator_feature<contiguous_indexed_selector<Iterator1,Iterator2,renumber>, Feature>
   : check_iterator_feature<iterator_pair<Iterator1, Iterator2, FeaturesViaSecond<end_sensitive> >, Feature> { };

template <typename Iterator1, typename Iterator2, bool renumber>
struct check_iterator_feature<contiguous_indexed_selector<Iterator1,Iterator2,renumber>, reference_relaxed>
   : check_iterator_feature<Iterator1, reference_relaxed> { };

template <typename Iterator1, typename Iterator2, bool renumber>
struct check_iterator_feature<contiguous_indexed_selector<Iterator1,Iterator2,renumber>, indexed> {
   static const bool answer= renumber ? check_iterator_feature<Iterator2,indexed>::answer
                                      : check_iterator_feature<Iterator1,indexed>::answer;
};

template <bool renumber>
struct contiguous_indexed_selector_coupler {
   template <typename Iterator1, typename Iterator2, typename ExpectedFeatures>
   struct defs {
      typedef contiguous_indexed_selector<Iterator1, Iterator2, renumber> iterator;
      typedef typename if_else<renumber,
			       typename list_search_all<ExpectedFeatures, reference_relaxed, identical>::positive,
			       typename list_search_all<ExpectedFeatures, end_sensitive, identical>::negative
                              >::result
         needed_features1;
      static const bool enforce_indexed=renumber && list_search<ExpectedFeatures,indexed,absorbing_feature>::answer;
      typedef typename if_else<enforce_indexed,
			       typename mix_features<ExpectedFeatures, enforce_construction<indexed> >::result,
			       typename list_search_all<ExpectedFeatures, indexed, derived_from>::negative
                              >::result
         needed_features2;
   };
};

template <typename Top, typename Traits> class indexed_subset_typebase;

namespace subset_classifier {
   enum kind { generic, sparse, contiguous, range };

   template <typename ContainerRef,
	     bool _try=derived_from_instance2<typename deref<ContainerRef>::type,
					      modified_container_typebase>::answer>
   struct detect_modified : False { };

   template <typename ContainerRef>
   struct detect_modified<ContainerRef, true>
      : identical<typename deref<ContainerRef>::type::accessor, BuildUnaryIt<operations::index2element> > { };

   template <typename ContainerRef,
	     bool _try=derived_from_instance2<typename deref<ContainerRef>::type,
					      indexed_subset_typebase>::answer>
   struct detect_indexed_slice : False { };

   template <typename ContainerRef>
   struct detect_indexed_slice<ContainerRef, true>
      : identical<typename deref<ContainerRef>::type::accessor, BuildBinaryIt<operations::second_index2element> > { };

   template <typename ContainerRef,
	     bool _enable=true,
	     class _tag=typename object_traits<typename deref<ContainerRef>::type>::generic_tag,
	     bool _is_modified=_enable && detect_modified<ContainerRef>::answer,
	     bool _is_slice=_enable && detect_indexed_slice<ContainerRef>::answer>
   struct data_helper {
      typedef ContainerRef container_ref;
      typedef typename deref<ContainerRef>::type container;
      static container& get(container& c) { return c; }
      static const container& get(const container& c) { return c; }
      static const bool index_to_ref=false;
   };

   template <typename ContainerRef>
   struct data_helper<ContainerRef, true, is_set, true, false> {
      typedef typename deref<ContainerRef>::type container_in;
      typedef typename inherit_ref<typename container_in::container, ContainerRef>::type container_ref;
      typedef typename deref<container_ref>::type container;
      static container& get(container_in& c) { return c.get_container(); }
      static const container& get(const container_in& c) { return c.get_container(); }
      static const bool index_to_ref=true;
   };

   template <typename ContainerRef>
   struct data_helper<ContainerRef, true, is_set, false, true>
      : data_helper<ContainerRef, true, void, false, false> {
      static const bool index_to_ref=true;
   };

   template <typename ContainerRef1, typename ContainerRef2,
	     bool _enable_data_helper,
             bool _complement=derived_from_instance3<typename deref<ContainerRef2>::type,Complement>::answer>
   struct index_helper {
      static const kind
         answer = check_container_feature<typename deref<ContainerRef1>::type, pm::sparse>::answer ||
                  data_helper<ContainerRef1,_enable_data_helper>::index_to_ref
                  ? sparse : generic;
      static const bool complement=true;
      typedef operations::mul<sequence,ContainerRef2> operation;
      typedef typename deref<typename operation::result_type>::type container;
      typedef const container container_ref;
   };

   template <typename ContainerRef1, typename ContainerRef2, bool _enable_data_helper>
   struct index_helper<ContainerRef1, ContainerRef2, _enable_data_helper, false> {
      static const bool random=identical<typename iterator_traits<typename container_traits<ContainerRef1>::iterator>::iterator_category,
					 random_access_iterator_tag>::answer;
      static const kind
         answer = check_container_feature<typename deref<ContainerRef1>::type, pm::sparse>::answer ||
                  data_helper<ContainerRef1,_enable_data_helper>::index_to_ref
                  ? sparse
                  : identical<typename container_traits<ContainerRef2>::iterator, sequence::iterator>::answer
                    ? (random ? range : contiguous)
	            : generic;
      static const bool complement=false;
      typedef typename deref<ContainerRef2>::type container;
      typedef const container& container_ref;
   };

   template <typename IteratorPair, typename Accessor, bool relaxed_result>
   struct iterator_helper {
      typedef binary_transform_iterator<IteratorPair, Accessor, relaxed_result> iterator;
   };
   template <typename IteratorPair, bool relaxed_result>
   struct iterator_helper<IteratorPair, void, relaxed_result> {
      typedef IteratorPair iterator;
   };
}

template <typename> class Renumber { };

template <typename Top, typename Traits>
class indexed_subset_typebase : public manip_container_top<Top, Traits> {
public:
   typedef typename extract_type_param<Traits,Container1>::result container1_ref;
   typedef typename extract_type_param<Traits,Container2>::result container2_ref;
   static const bool renumber=extract_bool_param<Traits,Renumber>::result;

   typedef typename deref<container1_ref>::minus_ref container1;
   typedef typename deref<container2_ref>::minus_ref container2;
   typedef subset_classifier::data_helper<container1_ref, renumber> data_helper;
   typedef subset_classifier::index_helper<container1_ref, container2_ref, renumber> index_helper;
   typedef typename deref<typename data_helper::container_ref>::minus_ref data_container;
   typedef typename index_helper::container index_container;
   typedef typename container_traits<container1>::reference reference;
   typedef typename container_traits<container1>::const_reference const_reference;
   typedef typename container_traits<container1>::value_type value_type;
   typedef typename least_derived< cons<typename container_traits<data_container>::category,
					typename container_traits<index_container>::category> >::type
      category;
   typedef typename if_else<data_helper::index_to_ref, BuildBinaryIt<operations::second_index2element>, void>::result
      accessor;

   static const subset_classifier::kind kind=index_helper::answer;

   typedef typename if_else<renumber && kind==subset_classifier::contiguous, cons<end_sensitive, indexed>, end_sensitive>::result
      must_enforce_features;
   typedef typename manip_container_top<Top, Traits>::expected_features expected_features;
   static const bool simplify=!list_search_all<expected_features, must_enforce_features, absorbing_feature>::answer;

protected:
   typename index_helper::container_ref
   get_index_container(const container2& c2, True*) const
   {
      typename index_helper::operation op;
      return op(sequence(0, get_dim(this->top().get_container1())), c2);
   }
   typename index_helper::container_ref
   get_index_container(const container2& c2, False*) const
   {
      return c2;
   }
   typename index_helper::container_ref
   get_index_container(const container2& c2) const
   {
      return get_index_container(c2, (bool2type<index_helper::complement>*)0);
   }

   int _size(False*) const
   {
      return this->top().get_container2().size();
   }
   int _size(True*) const
   {
      return this->top().get_container1().size() - this->top().get_container2().base().size();
   }
   bool _empty(False*) const
   {
      return this->top().get_container2().empty();
   }
   bool _empty(True*) const
   {
      return _size((True*)0)==0;
   }
public:
   int size() const { return _size((bool2type<index_helper::complement>*)0); }
   int max_size() const { return size(); }
   bool empty() const { return _empty((bool2type<index_helper::complement>*)0); }
};

template <typename Top, typename Traits,
          subset_classifier::kind _kind=indexed_subset_typebase<Top,Traits>::kind,
          typename Category=typename indexed_subset_typebase<Top,Traits>::category>
class indexed_subset_elem_access
   : public indexed_subset_typebase<Top,Traits> {
   typedef indexed_subset_typebase<Top,Traits> _super;
protected:
   typedef typename list_search_all<typename _super::expected_features,
				    typename if_else<_super::renumber,
						     cons<indexed, cons<range_capable, end_sensitive> >,
						     cons<range_capable, end_sensitive>
                                                    >::result,
				    identical_raw>::negative
      needed_features1;
   typedef typename if_else<
      _super::renumber && list_search<typename _super::expected_features,indexed,absorbing_feature>::answer,
      typename mix_features<typename _super::expected_features,
			    cons<enforce_construction<indexed>, cons<reference_relaxed, end_sensitive> > >::result,
      typename mix_features<typename list_search_all<typename _super::expected_features,indexed,absorbing_feature>::negative,
			    cons<reference_relaxed, end_sensitive> >::result >::result
      needed_features2;

public:
   typedef indexed_selector<typename ensure_features<typename _super::container1, needed_features1>::iterator,
			    typename ensure_features<typename _super::index_container, needed_features2>::const_iterator,
			    _super::renumber>
      iterator;
   typedef indexed_selector<typename ensure_features<typename _super::container1, needed_features1>::const_iterator,
			    typename ensure_features<typename _super::index_container, needed_features2>::const_iterator,
			    _super::renumber>
      const_iterator;

   iterator begin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      return iterator(ensure(const_cast<typename _super::container1&>(c1), (needed_features1*)0).begin(),
		      ensure(get_index_container(this->top().get_container2()), (needed_features2*)0).begin(),
		      true);
   }
   iterator end()
   {
      const typename _super::container1& c1=this->top().get_container1();
      return iterator(ensure(const_cast<typename _super::container1&>(c1), (needed_features1*)0).end(),
		      ensure(get_index_container(this->top().get_container2()), (needed_features2*)0).end());
   }
   const_iterator begin() const
   {
      return const_iterator(ensure(this->top().get_container1(), (needed_features1*)0).begin(),
			    ensure(get_index_container(this->top().get_container2()), (needed_features2*)0).begin(),
			    true);
   }
   const_iterator end() const
   {
      return const_iterator(ensure(this->top().get_container1(), (needed_features1*)0).end(),
			    ensure(get_index_container(this->top().get_container2()), (needed_features2*)0).end());
   }
};

template <typename Top, typename Traits>
class indexed_subset_elem_access<Top, Traits, subset_classifier::generic, forward_iterator_tag>
   : public indexed_subset_elem_access<Top, Traits, subset_classifier::generic, input_iterator_tag> {
   typedef indexed_subset_typebase<Top,Traits> _super;
public:
   typename _super::reference front()
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, reference_relaxed>::iterator
         b1=ensure(const_cast<typename _super::container1&>(c1), (reference_relaxed*)0).begin();
      std::advance(b1, get_index_container(this->top().get_container2()).front());
      return *b1;
   }
   typename _super::const_reference front() const
   {
      typename ensure_features<typename _super::container1, reference_relaxed>::const_iterator
         b1=ensure(this->top().get_container1(), (reference_relaxed*)0).begin();
      std::advance(b1, get_index_container(this->top().get_container2()).front());
      return *b1;
   }
};

template <typename Top, typename Traits>
class indexed_subset_elem_access<Top, Traits, subset_classifier::generic, bidirectional_iterator_tag>
   : public indexed_subset_elem_access<Top, Traits, subset_classifier::generic, forward_iterator_tag> {
   typedef indexed_subset_elem_access<Top, Traits, subset_classifier::generic, forward_iterator_tag> _super;
public:
   typedef typename _super::iterator iterator;
   typedef typename _super::const_iterator const_iterator;

   iterator end()
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, typename _super::needed_features1>::iterator
	 e1=ensure(const_cast<typename _super::container1&>(c1), (typename _super::needed_features1*)0).end();
      const typename _super::container2& c2=this->top().get_container2();
      const typename _super::index_container& indices=get_index_container(c2);
      if (!indices.empty()) std::advance(e1, indices.back()-this->size());
      return iterator(e1, ensure(indices, (typename _super::needed_features2*)0).end());
   }
   const_iterator end() const
   {
      typename ensure_features<typename _super::container1, typename _super::needed_features1>::const_iterator
	 e1=ensure(this->top().get_container1(), (typename _super::needed_features1*)0).end();
      const typename _super::container2& c2=this->top().get_container2();
      const typename _super::index_container& indices=get_index_container(c2);
      if (!indices.empty()) std::advance(e1, indices.back()-this->size());
      return const_iterator(e1, ensure(indices, (typename _super::needed_features2*)0).end());
   }

   typedef indexed_selector<typename ensure_features<typename _super::container1, typename _super::needed_features1>::iterator,
			    typename ensure_features<typename _super::index_container, typename _super::needed_features2>::const_reverse_iterator,
			    _super::renumber>
      reverse_iterator;
   typedef indexed_selector<typename ensure_features<typename _super::container1, typename _super::needed_features1>::const_iterator,
			    typename ensure_features<typename _super::index_container, typename _super::needed_features2>::const_reverse_iterator,
			    _super::renumber>
      const_reverse_iterator;

   reverse_iterator rbegin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, typename _super::needed_features1>::iterator
	 it1=ensure(const_cast<typename _super::container1&>(c1), (typename _super::needed_features1*)0).end();
      typename ensure_features<typename _super::index_container, typename _super::needed_features2>::const_reverse_iterator
	 it2=ensure(get_index_container(this->top().get_container2()), (typename _super::needed_features2*)0).rbegin();
      if (!it2.at_end()) std::advance(it1, *it2-c1.size());
      return reverse_iterator(it1, it2);
   }
   reverse_iterator rend()
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, typename _super::needed_features1>::iterator
	 b1=ensure(const_cast<typename _super::container1&>(c1), (typename _super::needed_features1*)0).begin();
      const typename _super::container2& c2=this->top().get_container2();
      const typename _super::index_container& indices=get_index_container(c2);
      if (!indices.empty()) std::advance(b1, indices.front());
      return reverse_iterator(b1, ensure(indices, (typename _super::needed_features2*)0).rend());
   }
   const_reverse_iterator rbegin() const
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, typename _super::needed_features1>::const_iterator
	 it1=ensure(c1, (typename _super::needed_features1*)0).end();
      typename ensure_features<typename _super::index_container, typename _super::needed_features2>::const_reverse_iterator
	 it2=ensure(get_index_container(this->top().get_container2()), (typename _super::needed_features2*)0).rbegin();
      if (!it2.at_end()) std::advance(it1, *it2-c1.size());
      return const_reverse_iterator(it1, it2);
   }
   const_reverse_iterator rend() const
   {
      typename ensure_features<typename _super::container1, typename _super::needed_features1>::const_iterator
	 b1=ensure(this->top().get_container1(), (typename _super::needed_features1*)0).begin();
      const typename _super::container2& c2=this->top().get_container2();
      const typename _super::index_container& indices=get_index_container(c2);
      if (!indices.empty()) std::advance(b1, indices.front());
      return const_reverse_iterator(b1, ensure(indices, (typename _super::needed_features2*)0).rend());
   }

   typename _super::reference back()
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, reference_relaxed>::reverse_iterator
	 rb1=ensure(const_cast<typename _super::container1&>(c1), (reference_relaxed*)0).rbegin();
      std::advance(rb1, c1.size()-1 - get_index_container(this->top().get_container2()).back());
      return *rb1;
   }
   typename _super::reference back() const
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, reference_relaxed>::const_reverse_iterator
	 rb1=ensure(c1, (reference_relaxed*)0).rbegin();
      std::advance(rb1, c1.size()-1 - get_index_container(this->top().get_container2()).back());
      return *rb1;
   }
};

template <typename Top, typename Traits, bool _reversible,
	  bool _simplified=indexed_subset_typebase<Top,Traits>::simplify>	// primary: !reversible, simplified
class indexed_subset_contiguous_elem_access
   : public indexed_subset_typebase<Top,Traits> {
   typedef indexed_subset_typebase<Top,Traits> _super;
protected:
   typedef typename _super::expected_features needed_features1;
public:
   typedef typename ensure_features<typename _super::container1, needed_features1>::iterator iterator;
   typedef typename ensure_features<typename _super::container1, needed_features1>::const_iterator const_iterator;

   iterator begin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      iterator b=ensure(const_cast<typename _super::container1&>(c1), (needed_features1*)0).begin();
      std::advance(b, this->top().get_container2().front());
      return b;
   }
   iterator end()
   {
      const typename _super::container1& c1=this->top().get_container1();
      iterator b=ensure(const_cast<typename _super::container1&>(c1), (needed_features1*)0).begin();
      std::advance(b, this->top().get_container2().back()+1);
      return b;
   }
   const_iterator begin() const
   {
      const_iterator b=ensure(this->top().get_container1(), (needed_features1*)0).begin();
      std::advance(b, this->top().get_container2().front());
      return b;
   }
   const_iterator end() const
   {
      const_iterator b=ensure(this->top().get_container1(), (needed_features1*)0).begin();
      std::advance(b, this->top().get_container2().back()+1);
      return b;
   }
};

template <typename Top, typename Traits>
class indexed_subset_contiguous_elem_access<Top, Traits, false, false>	// !reversible, !simplified
   : public indexed_subset_typebase<Top,Traits> {
   typedef indexed_subset_typebase<Top,Traits> _super;
protected:
   typedef contiguous_indexed_selector_coupler<_super::renumber> coupler;
   typedef typename coupler::template defs<typename container_traits<typename _super::container1>::iterator,
                                           typename container_traits<typename _super::container2>::const_iterator,
				           typename _super::expected_features>::needed_features1
      needed_features1;
   typedef typename coupler::template defs<typename container_traits<typename _super::container1>::const_iterator,
				           typename container_traits<typename _super::container2>::const_iterator,
                                           typename _super::expected_features>::needed_features2
      needed_features2;
public:
   typedef typename coupler::template defs<typename ensure_features<typename _super::container1, needed_features1>::iterator,
				           typename ensure_features<typename _super::container2, needed_features2>::const_iterator,
                                           typename _super::expected_features>::iterator
      iterator;
   typedef typename coupler::template defs<typename ensure_features<typename _super::container1, needed_features1>::const_iterator,
				           typename ensure_features<typename _super::container2, needed_features2>::const_iterator,
                                           typename _super::expected_features>::iterator
      const_iterator;

   iterator begin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, needed_features1>::iterator
	 b1=ensure(const_cast<typename _super::container1&>(c1), (needed_features1*)0).begin();
      const typename _super::container2& c2=this->top().get_container2();
      std::advance(b1, c2.front());
      return iterator(b1, ensure(c2, (needed_features2*)0).begin());
   }
   iterator end()
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, needed_features1>::iterator
	 b1=ensure(const_cast<typename _super::container1&>(c1), (needed_features1*)0).begin();
      const typename _super::container2& c2=this->top().get_container2();
      std::advance(b1, c2.back()+1);
      return iterator(b1, ensure(c2, (needed_features2*)0).end());
   }
   const_iterator begin() const
   {
      typename ensure_features<typename _super::container1, needed_features1>::const_iterator
	 b1=ensure(this->top().get_container1(), (needed_features1*)0).begin();
      const typename _super::container2& c2=this->top().get_container2();
      std::advance(b1, c2.front());
      return const_iterator(b1, ensure(c2, (needed_features2*)0).begin());
   }
   const_iterator end() const
   {
      typename ensure_features<typename _super::container1, needed_features1>::const_iterator
	 b1=ensure(this->top().get_container1(), (needed_features1*)0).begin();
      const typename _super::container2& c2=this->top().get_container2();
      std::advance(b1, c2.back()+1);
      return iterator(b1, ensure(c2, (needed_features2*)0).end());
   }
};

template <typename Top, typename Traits>
class indexed_subset_elem_access<Top, Traits, subset_classifier::contiguous, forward_iterator_tag>
   : public indexed_subset_contiguous_elem_access<Top, Traits, false> {
   typedef indexed_subset_typebase<Top,Traits> _super;
public:
   typename _super::reference front()
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, reference_relaxed>::iterator
	 b1=ensure(const_cast<typename _super::container1&>(c1), (reference_relaxed*)0).begin();
      std::advance(b1, this->top().get_container2().front());
      return *b1;
   }
   typename _super::const_reference front() const
   {
      typename ensure_features<typename _super::container1, reference_relaxed>::const_iterator
	 b1=ensure(this->top().get_container1(), (reference_relaxed*)0).begin();
      std::advance(b1, this->top().get_container2().front());
      return *b1;
   }
};

template <typename Top, typename Traits>
class indexed_subset_contiguous_elem_access<Top, Traits, true, true>	// reversible, simplified
   : public indexed_subset_elem_access<Top, Traits, subset_classifier::contiguous, forward_iterator_tag> {
   typedef indexed_subset_contiguous_elem_access<Top, Traits, false, true> _super;
public:
   typename _super::iterator end()
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename _super::iterator e=ensure(const_cast<typename _super::container1&>(c1), (typename _super::needed_features1*)0).end();
      std::advance(e, this->top().get_container2().back()+1-c1.size());
      return e;
   }
   typename _super::const_iterator end() const
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename _super::const_iterator e=ensure(c1, (typename _super::needed_features1*)0).end();
      std::advance(e, this->top().get_container2().back()+1-c1.size());
      return e;
   }

   typedef typename ensure_features<typename _super::container1, typename _super::needed_features1>::reverse_iterator
      reverse_iterator;
   typedef typename ensure_features<typename _super::container1, typename _super::needed_features1>::const_reverse_iterator
      const_reverse_iterator;

   reverse_iterator rbegin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      reverse_iterator rb=ensure(const_cast<typename _super::container1&>(c1), (typename _super::needed_features1*)0).rbegin();
      std::advance(rb, c1.size()-1 - this->top().get_container2().back());
      return rb;
   }
   reverse_iterator rend()
   {
      const typename _super::container1& c1=this->top().get_container1();
      reverse_iterator re=ensure(const_cast<typename _super::container1&>(c1), (typename _super::needed_features1*)0).rend();
      std::advance(re, -this->top().get_container2().front());
      return re;
   }
   const_reverse_iterator rbegin() const
   {
      const typename _super::container1& c1=this->top().get_container1();
      const_reverse_iterator rb=ensure(c1, (typename _super::needed_features1*)0).rbegin();
      std::advance(rb, c1.size()-1 - this->top().get_container2().back());
      return rb;
   }
   const_reverse_iterator rend() const
   {
      const_reverse_iterator re=ensure(this->top().get_container1(), (typename _super::needed_features1*)0).rend();
      std::advance(re, -this->top().get_container2().front());
      return re;
   }
};

template <typename Top, typename Traits>
class indexed_subset_contiguous_elem_access<Top, Traits, true, false>	// reversible, !simplified
   : public indexed_subset_elem_access<Top, Traits, subset_classifier::contiguous, forward_iterator_tag> {
   typedef indexed_subset_contiguous_elem_access<Top, Traits, false, false> _super;
public:
   typedef typename _super::iterator iterator;
   typedef typename _super::const_iterator const_iterator;

   iterator end()
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, typename _super::needed_features1>::iterator
	 e1=ensure(const_cast<typename _super::container1&>(c1), (typename _super::needed_features1*)0).end();
      const typename _super::container2& c2=this->top().get_container2();
      std::advance(e1, c2.back()+1-c1.size());
      return iterator(e1, ensure(c2, (typename _super::needed_features2*)0).end());
   }
   const_iterator end() const
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, typename _super::needed_features1>::const_iterator
	 e1=ensure(c1, (typename _super::needed_features1*)0).end();
      const typename _super::container2& c2=this->top().get_container2();
      std::advance(e1, c2.back()+1-c1.size());
      return const_iterator(e1, ensure(c2, (typename _super::needed_features2*)0).end());
   }

   typedef typename _super::coupler::template defs<
         typename ensure_features<typename _super::container1, typename _super::needed_features1>::reverse_iterator,
         typename ensure_features<typename _super::container2, typename _super::needed_features2>::const_reverse_iterator,
         typename _super::expected_features>::iterator
      reverse_iterator;
   typedef typename _super::coupler::template defs<
         typename ensure_features<typename _super::container1, typename _super::needed_features1>::const_reverse_iterator,
         typename ensure_features<typename _super::container2, typename _super::needed_features2>::const_reverse_iterator,
         typename _super::expected_features>::iterator
      const_reverse_iterator;

   reverse_iterator rbegin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, typename _super::needed_features1>::reverse_iterator
	 rb1=ensure(const_cast<typename _super::container1&>(c1), (typename _super::needed_features1*)0).rbegin();
      const typename _super::container2& c2=this->top().get_container2();
      std::advance(rb1, c1.size()-1 - c2.back());
      return reverse_iterator(rb1, ensure(c2, (typename _super::needed_features2*)0).rbegin());
   }
   reverse_iterator rend()
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, typename _super::needed_features1>::reverse_iterator
	 re1=ensure(const_cast<typename _super::container1&>(c1), (typename _super::needed_features1*)0).rend();
      const typename _super::container2& c2=this->top().get_container2();
      std::advance(re1, -c2.front());
      return reverse_iterator(re1, ensure(c2, (typename _super::needed_features2*)0).rend());
   }
   const_reverse_iterator rbegin() const
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, typename _super::needed_features1>::const_reverse_iterator
	 rb1=ensure(c1, (typename _super::needed_features1*)0).rbegin();
      const typename _super::container2& c2=this->top().get_container2();
      std::advance(rb1, c1.size()-1 - c2.back());
      return const_reverse_iterator(rb1, ensure(c2, (typename _super::needed_features2*)0).rbegin());
   }
   const_reverse_iterator rend() const
   {
      typename ensure_features<typename _super::container1, typename _super::needed_features1>::const_reverse_iterator
	 re1=ensure(this->top().get_container1(), (typename _super::needed_features1*)0).rend();
      const typename _super::container2& c2=this->top().get_container2();
      std::advance(re1, -c2.front());
      return const_reverse_iterator(re1, ensure(c2, (typename _super::needed_features2*)0).rend());
   }
};

template <typename Top, typename Traits>
class indexed_subset_elem_access<Top, Traits, subset_classifier::contiguous, bidirectional_iterator_tag>
   : public indexed_subset_contiguous_elem_access<Top, Traits, true> {
   typedef indexed_subset_typebase<Top,Traits> _super;
public:
   typename _super::reference back()
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, reference_relaxed>::reverse_iterator
	 rb1=ensure(const_cast<typename _super::container1&>(c1), (reference_relaxed*)0).rbegin();
      std::advance(rb1, c1.size()-1 - this->top().get_container2().back());
      return *rb1;
   }
   typename _super::const_reference back() const
   {
      const typename _super::container1& c1=this->top().get_container1();
      typename ensure_features<typename _super::container1, reference_relaxed>::const_reverse_iterator
	 rb1=ensure(c1, (reference_relaxed*)0).rbegin();
      std::advance(rb1, c1.size()-1 - this->top().get_container2().back());
      return *rb1;
   }
};

template <typename Top, typename Traits,
	  bool _simplified=indexed_subset_typebase<Top,Traits>::simplify>
class indexed_subset_range_elem_access
   : public indexed_subset_typebase<Top,Traits> {
   typedef indexed_subset_typebase<Top,Traits> _super;
protected:
   typedef typename _super::expected_features needed_features1;
public:
   typedef typename ensure_features<typename _super::container1, needed_features1>::iterator iterator;
   typedef typename ensure_features<typename _super::container1, needed_features1>::const_iterator const_iterator;
   typedef typename ensure_features<typename _super::container1, needed_features1>::reverse_iterator reverse_iterator;
   typedef typename ensure_features<typename _super::container1, needed_features1>::const_reverse_iterator const_reverse_iterator;

   iterator begin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      iterator b=ensure(const_cast<typename _super::container1&>(c1), (needed_features1*)0).begin();
      narrow_range(b, this->top().get_container2().front(), 0, _super::renumber);
      return b;
   }
   iterator end()
   {
      const typename _super::container1& c1=this->top().get_container1();
      iterator b=ensure(const_cast<typename _super::container1&>(c1), (needed_features1*)0).begin();
      narrow_range(b, this->top().get_container2().back()+1, 0, _super::renumber);
      return b;
   }
   const_iterator begin() const
   {
      const_iterator b=ensure(this->top().get_container1(), (needed_features1*)0).begin();
      narrow_range(b, this->top().get_container2().front(), 0, _super::renumber);
      return b;
   }
   const_iterator end() const
   {
      const_iterator b=ensure(this->top().get_container1(), (needed_features1*)0).begin();
      narrow_range(b, this->top().get_container2().back()+1, 0, _super::renumber);
      return b;
   }
   reverse_iterator rbegin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      reverse_iterator re=ensure(const_cast<typename _super::container1&>(c1), (needed_features1*)0).rend();
      narrow_range(re, -this->top().get_container2().back()-1, 0, _super::renumber);
      return re;
   }
   reverse_iterator rend()
   {
      const typename _super::container1& c1=this->top().get_container1();
      reverse_iterator re=ensure(const_cast<typename _super::container1&>(c1), (needed_features1*)0).rend();
      narrow_range(re, -this->top().get_container2().front(), 0, _super::renumber);
      return re;
   }
   const_reverse_iterator rbegin() const
   {
      const_reverse_iterator re=ensure(this->top().get_container1(), (needed_features1*)0).rend();
      narrow_range(re, -this->top().get_container2().back()-1, 0, _super::renumber);
      return re;
   }
   const_reverse_iterator rend() const
   {
      const_reverse_iterator re=ensure(this->top().get_container1(), (needed_features1*)0).rend();
      narrow_range(re, -this->top().get_container2().front(), 0, _super::renumber);
      return re;
   }
};

template <typename Top, typename Traits>
class indexed_subset_range_elem_access<Top, Traits, false>
   : public indexed_subset_typebase<Top,Traits> {
   typedef indexed_subset_typebase<Top,Traits> _super;
protected:
   typedef typename mix_features<typename _super::expected_features, range_capable>::result needed_features1;
public:
   typedef typename ensure_features<typename _super::container1, needed_features1>::iterator iterator;
   typedef typename ensure_features<typename _super::container1, needed_features1>::const_iterator const_iterator;
   typedef typename ensure_features<typename _super::container1, needed_features1>::reverse_iterator reverse_iterator;
   typedef typename ensure_features<typename _super::container1, needed_features1>::const_reverse_iterator const_reverse_iterator;

   iterator begin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      const int n=c1.size();
      const typename _super::container2& indices=this->top().get_container2();
      iterator b=ensure(const_cast<typename _super::container1&>(c1), (needed_features1*)0).begin();
      b.narrow_range(indices.front(), n-1-indices.back(), _super::renumber);
      return b;
   }
   iterator end()
   {
      return begin()+this->size();
   }
   const_iterator begin() const
   {
      const typename _super::container1& c1=this->top().get_container1();
      const int n=c1.size();
      const typename _super::container2& indices=this->top().get_container2();
      const_iterator b=ensure(c1, (needed_features1*)0).begin();
      b.narrow_range(indices.front(), n-1-indices.back(), _super::renumber);
      return b;
   }
   const_iterator end() const
   {
      return begin()+this->size();
   }
   reverse_iterator rbegin()
   {
      const typename _super::container1& c1=this->top().get_container1();
      const int n=c1.size();
      const typename _super::container2& indices=this->top().get_container2();
      reverse_iterator rb=ensure(const_cast<typename _super::container1&>(c1), (needed_features1*)0).rbegin();
      rb.narrow_range(n-indices.back()-1, indices.front(), _super::renumber);
      return rb;
   }
   reverse_iterator rend()
   {
      return rbegin()+this->size();
   }
   const_reverse_iterator rbegin() const
   {
      const typename _super::container1& c1=this->top().get_container1();
      const int n=c1.size();
      const typename _super::container2& indices=this->top().get_container2();
      const_reverse_iterator rb=ensure(c1, (needed_features1*)0).rbegin();
      rb.narrow_range(n-indices.back()-1, indices.front(), _super::renumber);
      return rb;
   }
   const_reverse_iterator rend() const
   {
      return rbegin()+this->size();
   }
};

template <typename Top, typename Traits>
class indexed_subset_elem_access<Top, Traits, subset_classifier::range, bidirectional_iterator_tag>
   : public indexed_subset_range_elem_access<Top, Traits> {
   typedef indexed_subset_typebase<Top,Traits> _super;
public:
   typename _super::reference front()
   {
      return this->top().get_container1()[ this->top().get_container2().front() ];
   }
   typename _super::const_reference front() const
   {
      return this->top().get_container1()[ this->top().get_container2().front() ];
   }
   typename _super::reference back()
   {
      return this->top().get_container1()[ this->top().get_container2().back() ];
   }
   typename _super::const_reference back() const
   {
      return this->top().get_container1()[ this->top().get_container2().back() ];
   }
};

template <typename Top, typename Traits, subset_classifier::kind _kind>
class indexed_subset_elem_access<Top, Traits, _kind, random_access_iterator_tag>
   : public indexed_subset_elem_access<Top, Traits, _kind, bidirectional_iterator_tag> {
   typedef indexed_subset_elem_access<Top, Traits, _kind, bidirectional_iterator_tag> _super;
public:
   typename _super::reference front()
   {
      return this->top().get_container1()[ this->top().get_container2().front() ];
   }
   typename _super::const_reference front() const
   {
      return this->top().get_container1()[ this->top().get_container2().front() ];
   }
   typename _super::reference back()
   {
      return this->top().get_container1()[ this->top().get_container2().back() ];
   }
   typename _super::const_reference back() const
   {
      return this->top().get_container1()[ this->top().get_container2().back() ];
   }
   typename _super::reference operator[] (int i)
   {
      return this->top().get_container1()[ this->top().get_container2()[i] ];
   }
   typename _super::const_reference operator[] (int i) const
   {
      return this->top().get_container1()[ this->top().get_container2()[i] ];
   }
};

template <typename Top, typename Traits, typename Category>
class indexed_subset_elem_access<Top, Traits, subset_classifier::sparse, Category>
   : public indexed_subset_typebase<Top,Traits> {
   typedef indexed_subset_typebase<Top,Traits> _super;
protected:
   static const bool relaxed_result=list_search<typename _super::expected_features, reference_relaxed, absorbing_feature>::answer;

   typedef sparse_indexed_selector_coupler<false, _super::renumber> coupler;
   typedef typename coupler::template defs<typename container_traits<typename _super::data_container>::iterator,
                                           typename container_traits<typename _super::index_container>::const_iterator,
				           typename _super::expected_features>::needed_features1
      needed_features1;
   typedef typename coupler::template defs<typename container_traits<typename _super::data_container>::const_iterator,
				           typename container_traits<typename _super::index_container>::const_iterator,
                                           typename _super::expected_features>::needed_features2
      needed_features2;
public:
   typedef typename coupler::template defs<typename ensure_features<typename _super::data_container, needed_features1>::iterator,
				           typename ensure_features<typename _super::index_container, needed_features2>::const_iterator,
                                           typename _super::expected_features>::iterator
      iterator_pair;
   typedef typename coupler::template defs<typename ensure_features<typename _super::data_container, needed_features1>::const_iterator,
				           typename ensure_features<typename _super::index_container, needed_features2>::const_iterator,
                                           typename _super::expected_features>::iterator
      const_iterator_pair;
   typedef typename subset_classifier::iterator_helper<iterator_pair, typename _super::accessor, relaxed_result>::iterator
      iterator;
   typedef typename subset_classifier::iterator_helper<const_iterator_pair, typename _super::accessor, relaxed_result>::iterator
      const_iterator;

   iterator begin()
   {
      typedef typename _super::data_helper data_helper;
      const typename _super::container1& c1=this->top().get_container1();
      return iterator(ensure(data_helper::get(const_cast<typename _super::container1&>(c1)), (needed_features1*)0).begin(),
		      ensure(get_index_container(this->top().get_container2()), (needed_features2*)0).begin());
   }
   iterator end()
   {
      typedef typename _super::data_helper data_helper;
      const typename _super::container1& c1=this->top().get_container1();
      return iterator(ensure(data_helper::get(const_cast<typename _super::container1&>(c1)), (needed_features1*)0).end(),
		      ensure(get_index_container(this->top().get_container2()), (needed_features2*)0).end());
   }
   const_iterator begin() const
   {
      typedef typename _super::data_helper data_helper;
      return const_iterator(ensure(data_helper::get(this->top().get_container1()), (needed_features1*)0).begin(),
			    ensure(get_index_container(this->top().get_container2()), (needed_features2*)0).begin());
   }
   const_iterator end() const
   {
      typedef typename _super::data_helper data_helper;
      return const_iterator(ensure(data_helper::get(this->top().get_container1()), (needed_features1*)0).end(),
			    ensure(get_index_container(this->top().get_container2()), (needed_features2*)0).end());
   }

protected:
   int _rewind_index(const iterator&, int i, forward_iterator_tag*)
   {
      typename Entire<typename _super::container2>::const_iterator iit=entire(this->top().get_container2());
      while (iit.index() < i) ++iit;
      return *iit;
   }

   int _rewind_index(const iterator& pos, int i, bidirectional_iterator_tag*)
   {
      typename iterator::second_type iit=pos.second;
      std::advance(iit, i-pos.index());
      return *iit;
   }

   int _rewind_index(const iterator& pos, int i) {
      return _rewind_index(pos, i, (typename iterator_traits<typename container_traits<typename _super::container2>::const_iterator>::iterator_category*)0);
   }
public:
   void insert(const iterator& pos, int i)
   {
      this->top().get_container1().insert(_rewind_index(pos, i));
   }

   template <typename Data>
   void insert(const iterator& pos, int i, const Data& d)
   {
      this->top().get_container1().insert(_rewind_index(pos, i), d);
   }

   void erase(const iterator& pos)
   {
      this->top().get_container1().erase(pos);
   }

   int size() const { return count_it(begin()); }
   bool empty() const { return begin().at_end(); }

   typename _super::reference front() { return *begin(); }
   typename _super::const_reference front() const { return *begin(); }
};

template <typename Top, typename Traits>
class indexed_subset_elem_access<Top, Traits, subset_classifier::sparse, bidirectional_iterator_tag>
   : public indexed_subset_elem_access<Top, Traits, subset_classifier::sparse, forward_iterator_tag> {
   typedef indexed_subset_elem_access<Top, Traits, subset_classifier::sparse, forward_iterator_tag> _super;
protected:
   typedef sparse_indexed_selector_coupler<true, _super::renumber> rev_coupler;
public:
   typedef typename rev_coupler::template defs<typename ensure_features<typename _super::data_container, typename _super::needed_features1>::reverse_iterator,
					       typename ensure_features<typename _super::index_container, typename _super::needed_features2>::const_reverse_iterator,
					       typename _super::expected_features>::iterator
      reverse_iterator_pair;
   typedef typename rev_coupler::template defs<typename ensure_features<typename _super::data_container, typename _super::needed_features1>::const_reverse_iterator,
					       typename ensure_features<typename _super::index_container, typename _super::needed_features2>::const_reverse_iterator,
					       typename _super::expected_features>::iterator
      const_reverse_iterator_pair;
   typedef typename subset_classifier::iterator_helper<reverse_iterator_pair,typename _super::accessor,_super::relaxed_result>::iterator
      reverse_iterator;
   typedef typename subset_classifier::iterator_helper<const_reverse_iterator_pair,typename _super::accessor,_super::relaxed_result>::iterator
      const_reverse_iterator;

   reverse_iterator rbegin()
   {
      typedef typename _super::data_helper data_helper;
      const typename _super::container1& c1=this->top().get_container1();
      return reverse_iterator(ensure(data_helper::get(const_cast<typename _super::container1&>(c1)), (typename _super::needed_features1*)0).rbegin(),
			      ensure(get_index_container(this->top().get_container2()), (typename _super::needed_features2*)0).rbegin());
   }
   reverse_iterator rend()
   {
      typedef typename _super::data_helper data_helper;
      const typename _super::container1& c1=this->top().get_container1();
      return reverse_iterator(ensure(data_helper::get(const_cast<typename _super::container1&>(c1)), (typename _super::needed_features1*)0).rend(),
			      ensure(get_index_container(this->top().get_container2()), (typename _super::needed_features2*)0).rend());
   }
   const_reverse_iterator rbegin() const
   {
      typedef typename _super::data_helper data_helper;
      return const_reverse_iterator(ensure(data_helper::get(this->top().get_container1()), (typename _super::needed_features1*)0).rbegin(),
				    ensure(get_index_container(this->top().get_container2()), (typename _super::needed_features2*)0).rbegin());
   }
   const_reverse_iterator rend() const
   {
      typedef typename _super::data_helper data_helper;
      return const_reverse_iterator(ensure(data_helper::get(this->top().get_container1()), (typename _super::needed_features1*)0).rend(),
				    ensure(get_index_container(this->top().get_container2()), (typename _super::needed_features2*)0).rend());
   }

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

template <typename Top, typename Traits=typename Top::manipulator_traits>
class indexed_subset_impl
   : public indexed_subset_elem_access<Top,Traits> {
public:
   typedef indexed_subset_impl<Top,Traits> manipulator_impl;
   typedef Traits manipulator_traits;

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

template <typename ContainerRef1, typename ContainerRef2> class IndexedSubset;

   template <typename ContainerRef1, typename ContainerRef2,
          typename Generic1=typename object_traits<typename deref<ContainerRef1>::type>::generic_type,
          typename Generic2=typename object_traits<typename deref<ContainerRef2>::type>::generic_type>
class generic_of_indexed_subset
   : generic_anything< IndexedSubset<ContainerRef1,ContainerRef2> > { };

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

template <typename ContainerRef1, typename ContainerRef2,
	  typename _Set1, typename E, typename Comparator, typename _Set2>
class generic_of_indexed_subset<ContainerRef1, ContainerRef2,
                                GenericSet<_Set1,E,Comparator>, GenericSet<_Set2, int, BuildBinary<operations::cmp> > >
   : public GenericSet<IndexedSubset<ContainerRef1,ContainerRef2>, E, Comparator> { };

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

template <typename Container, typename IndexSet> inline
IndexedSubset<Container&, const typename Concrete<IndexSet>::type&>
select(Container& c, const IndexSet& indices) {
   INDEX_CHECK(!complement_helper<const typename Concrete<IndexSet>::type&>::
	        dimension_check(Concrete<IndexSet>::get(indices), get_dim(c)),
	       "select - indices out of range");
   return IndexedSubset<Container&, const typename Concrete<IndexSet>::type&> (c, Concrete<IndexSet>::get(indices));
}

template <typename Container, typename IndexSet> inline
IndexedSubset<const Container&, const typename Concrete<IndexSet>::type&>
select(const Container& c, const IndexSet& indices) {
   INDEX_CHECK(!complement_helper<const typename Concrete<IndexSet>::type&>::
	        dimension_check(Concrete<IndexSet>::get(indices), get_dim(c)),
	       "select - indices out of range");
   return IndexedSubset<const Container&, const typename Concrete<IndexSet>::type&> (c, Concrete<IndexSet>::get(indices));
}

template <typename ContainerRef1, typename ContainerRef2>
class IndexedSlice
   : public container_pair_base<ContainerRef1, ContainerRef2>,
     public indexed_subset_impl< IndexedSlice<ContainerRef1,ContainerRef2>,
               cons< Container1< ContainerRef1 >,
               cons< Container2< ContainerRef2 >,
		     Renumber< True > > >
            >,
     public inherit_generic< IndexedSlice<ContainerRef1,ContainerRef2>,
			     typename deref<ContainerRef1>::type>::type {
   typedef container_pair_base<ContainerRef1, ContainerRef2> _base;
public:
   typedef typename inherit_generic<IndexedSlice, typename deref<ContainerRef1>::type>::type
      generic_mutable_type;

   IndexedSlice(typename _base::first_arg_type src1_arg, typename _base::second_arg_type src2_arg)
      : _base(src1_arg,src2_arg) { }

   IndexedSlice& operator= (const IndexedSlice& s) {
      return generic_mutable_type::operator=(s);
   }
   using generic_mutable_type::operator=;
protected:
   int dim(False*) const { return this->get_container2().size(); }
   int dim(True*) const { return get_dim(this->get_container1()) - this->get_container2().base().size(); }
public:
   int dim() const {
      return dim((bool2type<derived_from_instance3<typename deref<ContainerRef2>::type, Complement>::answer>*)0);
   }
};

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

template <typename ContainerRef1, typename ContainerRef2>
struct check_container_feature<IndexedSlice<ContainerRef1,ContainerRef2>, sparse_compatible>
   : check_container_feature<typename deref<ContainerRef1>::type, sparse_compatible> { };

template <typename ContainerRef1, typename ContainerRef2>
struct check_container_feature<IndexedSlice<ContainerRef1,ContainerRef2>, sparse>
   : check_container_feature<typename deref<ContainerRef1>::type, sparse> { };

template <typename ContainerRef1, typename ContainerRef2>
struct check_container_feature<IndexedSlice<ContainerRef1,ContainerRef2>, pure_sparse>
   : check_container_feature<typename deref<ContainerRef1>::type, pure_sparse> { };

namespace operations {

template <typename LeftRef, typename RightRef, bool check=false,
          typename Discr=typename isomorphic<typename deref<LeftRef>::type, typename deref<RightRef>::type>::discriminant>
struct slice_impl {
   typedef typename argument<LeftRef>::type first_argument_type;
   typedef typename argument<RightRef>::type second_argument_type;
   typedef IndexedSlice<LeftRef, RightRef> slice;
   typedef typename assign_const<slice, object_traits<slice>::is_always_const>::type result_type;

   result_type operator() (typename function_argument<LeftRef>::ref l,
			   typename function_argument<RightRef>::ref r) const
   {
      if (check)
	 INDEX_CHECK(!complement_helper<RightRef>::dimension_check(r, get_dim(l)),
		     "slice - indices out of range");
      return slice(l,r);
   }
};

template <typename LeftRef, typename RightRef>
struct slice : slice_impl<LeftRef,RightRef> { };

} // end namespace operations

} // end namespace pm

namespace polymake {
   using pm::select;
#if !(defined(__GNUC__) && __GNUC__==3 || __GNUC_MINOR__<=1)
   namespace operations {
      typedef BuildBinary<pm::operations::slice> slice;
   }
#endif
}

namespace std {
   // due to silly overloading rules
   template <typename ContainerRef1, typename ContainerRef2> inline
   void swap(pm::IndexedSlice<ContainerRef1,ContainerRef2>& s1,
	     pm::IndexedSlice<ContainerRef1,ContainerRef2>& s2) {
      s1.swap(s2);
   }
}

#endif // _POLYMAKE_INDEXED_SUBSET_H

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