/* 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_SELECTED_SUBSET_H
#define _POLYMAKE_SELECTED_SUBSET_H "$Project: polymake $$Id: SelectedSubset.h,v 1.14 2004/06/22 16:22:44 gawrilow Exp $"

#ifndef _POLYMAKE_SERIES_H
#  include <Series.h>
#endif

namespace pm {

/** Selecting filtered iterator
    This iterator hides the data items for which the given predicate evaluates to \\false\\.
*/
template <typename Iterator, typename Predicate,
          typename Category=typename least_derived< cons<typename iterator_traits<Iterator>::iterator_category,
						      bidirectional_iterator_tag> >::type>
class unary_predicate_selector : public Iterator {
protected:
   typedef Iterator super;
   typedef unary_helper<Iterator,Predicate> helper;
   typedef typename helper::star star;
   typename helper::operation pred;

   void skip_masked()
   {
      while (!this->at_end() && !pred(star::get(*this))) super::operator++();
   }

   template <typename,typename,typename> friend class unary_predicate_selector;
public:
   typedef typename least_derived< cons<typename iterator_traits<Iterator>::iterator_category,
					bidirectional_iterator_tag> >::type
      iterator_category;
   typedef unary_predicate_selector<typename iterator_traits<Iterator>::iterator, Predicate> iterator;
   typedef unary_predicate_selector<typename iterator_traits<Iterator>::const_iterator, Predicate> const_iterator;

   unary_predicate_selector() { }
   unary_predicate_selector(const iterator& it)
      : super(static_cast<const typename iterator::super&>(it)), pred(helper::create(it.pred)) { }

   unary_predicate_selector(const Iterator& cur_arg,
			    const Predicate& pred_arg=Predicate())
      : super(cur_arg), pred(helper::create(pred_arg))
   {
      skip_masked();
   }
   unary_predicate_selector(typename alt_constructor<Iterator>::arg_type& cur_arg,
			    const Predicate& pred_arg=Predicate())
      : super(cur_arg), pred(helper::create(pred_arg))
   {
      skip_masked();
   }

   unary_predicate_selector& operator++ ()
   {
      super::operator++();
      skip_masked();
      return *this;
   }

   const unary_predicate_selector operator++ (int) { unary_predicate_selector copy=*this; operator++(); return copy; }

   void reset() { super::reset(); skip_masked(); }
};

template <typename Iterator, typename Predicate>
class unary_predicate_selector<Iterator, Predicate, bidirectional_iterator_tag>
   : public unary_predicate_selector<Iterator, Predicate, forward_iterator_tag> {
   typedef unary_predicate_selector<Iterator, Predicate, forward_iterator_tag> _super;
public:
   unary_predicate_selector() { }
   unary_predicate_selector(const typename _super::iterator& it)
      : _super(it) { }

   unary_predicate_selector(const Iterator& cur_arg,
			    const Predicate& pred_arg=Predicate())
      : _super(cur_arg,pred_arg) { }
   unary_predicate_selector(typename alt_constructor<Iterator>::arg_type& cur_arg,
			    const Predicate& pred_arg=Predicate())
      : _super(cur_arg,pred_arg) { }

   // it's the applications' responsibility not to call this at the first position
   unary_predicate_selector& operator-- ()
   {
      typedef typename _super::super super;
      typedef typename _super::star _star;
      do
	 super::operator--();
      while (!pred(_star::get(*this)));
      return *this;
   }

   const unary_predicate_selector operator-- (int) { unary_predicate_selector copy=*this; operator--(); return copy; }
private:
   // make them undefined for the case of random_access Iterator
   void operator+=(int);
   void operator-=(int);
   void operator+(int);
   void operator-(int);
   void operator[](int);
};

template <typename Iterator, typename Predicate, typename Category, typename Feature>
struct check_iterator_feature<unary_predicate_selector<Iterator, Predicate, Category>, Feature> {
   static const bool answer=check_iterator_feature<Iterator, Feature>::answer ||
                            identical<Feature, reference_relaxed>::answer;	// can't enforce it anyway
};

struct unary_predicate_selector_modifier {
   template <typename Iterator, typename Predicate, typename ExpectedFeatures>
   struct defs {
      typedef typename mix_features< typename list_search_all<ExpectedFeatures,reference_relaxed,identical>::negative,
				     end_sensitive>::result
         needed_features;
      typedef unary_predicate_selector<Iterator,Predicate> iterator;
   };
};

template <typename Iterator, typename Predicate> inline
unary_predicate_selector<Iterator, Predicate>
make_unary_predicate_selector(Iterator it, const Predicate& pred)
{
   return unary_predicate_selector<Iterator, Predicate>(it,pred);
}

template <typename Iterator, typename Predicate>
class input_truncator : public Iterator {
protected:
   typedef Iterator super;
   typedef unary_helper<Iterator,Predicate> helper;
   typedef typename helper::star star;
   typename helper::operation pred;

   template <typename,typename> friend class input_truncator;
public:
   typedef forward_iterator_tag iterator_category;
   typedef input_truncator<typename iterator_traits<Iterator>::iterator, Predicate> iterator;
   typedef input_truncator<typename iterator_traits<Iterator>::const_iterator, Predicate> const_iterator;

   input_truncator() { }
   input_truncator(const iterator& it)
      : super(static_cast<const typename iterator::super&>(it)), pred(helper::create(it.pred)) { }

   input_truncator(const Iterator& cur_arg, const Predicate& pred_arg=Predicate())
      : super(cur_arg), pred(helper::create(pred_arg)) { }
   input_truncator(typename alt_constructor<Iterator>::arg_type& cur_arg, const Predicate& pred_arg=Predicate())
      : super(cur_arg), pred(helper::create(pred_arg)) { }

   input_truncator& operator++ () { super::operator++(); return *this; }
   const input_truncator operator++ (int) { input_truncator copy=*this; operator++(); return copy; }

   bool at_end() const
   {
      return super::at_end() || !pred(star::get(*this));
   }

   bool operator== (const input_truncator& it) const
   {
      return at_end() ? it.at_end() : static_cast<const Iterator&>(*this)==static_cast<const Iterator&>(it);
   }
   bool operator!= (const input_truncator& it) const
   {
      return !operator==(it);
   }
private:
   // make them undefined for the case of bidirectional or random_access Iterator
   void operator--();
   void operator--(int);
   void operator+=(int);
   void operator-=(int);
   void operator+(int);
   void operator-(int);
   void operator[](int);
};

template <typename Iterator, typename Predicate, typename Feature>
struct check_iterator_feature<input_truncator<Iterator, Predicate>, Feature> {
   static const bool answer=check_iterator_feature<Iterator, Feature>::answer ||
                            identical<Feature, reference_relaxed>::answer;	// can't enforce it anyway
};

struct input_truncator_modifier {
   template <typename Iterator, typename Predicate, typename ExpectedFeatures>
   struct defs : public unary_predicate_selector_modifier::defs<Iterator, Predicate, ExpectedFeatures> {
      typedef input_truncator<Iterator,Predicate> iterator;
   };
};

template <typename ContainerRef, typename Predicate>
class SelectedSubset
   : public modified_container_base<ContainerRef, Predicate>,
     public modified_container_impl< SelectedSubset<ContainerRef,Predicate>,
               cons< Container< ContainerRef >,
               cons< Accessor< Predicate >,
                     Modifier< unary_predicate_selector_modifier > > >
            >,
     public generic_of_subset< SelectedSubset<ContainerRef,Predicate>,
			       typename deref<ContainerRef>::type> {
   typedef modified_container_base<ContainerRef, Predicate> _base;
   typedef modified_container_impl<SelectedSubset> _super;
public:
   SelectedSubset(typename _base::arg_type src_arg, const Predicate& pred_arg=Predicate())
      : _base(src_arg,pred_arg) { }

   using _base::get_accessor;
};

template <typename ContainerRef, typename Predicate>
class TruncatedContainer
   : public modified_container_base<ContainerRef, Predicate>,
     public modified_container_impl< TruncatedContainer<ContainerRef,Predicate>,
               cons< Container< ContainerRef >,
               cons< Accessor< Predicate >,
                     Modifier< input_truncator_modifier > > >
            >,
     public generic_of_subset< TruncatedContainer<ContainerRef,Predicate>,
			       typename deref<ContainerRef>::type> {
   typedef modified_container_base<ContainerRef, Predicate> _base;
   typedef modified_container_impl<TruncatedContainer> _super;
public:
   typedef forward_iterator_tag category;

   TruncatedContainer(typename _base::arg_type src_arg, const Predicate& pred_arg=Predicate())
      : _base(src_arg,pred_arg) { }

   using _base::get_accessor;

   typename _super::reference front()
   {
      return this->get_container().front();
   }
   typename _super::const_reference front() const
   {
      return this->get_container().front();
   }
};

template <typename ContainerRef, typename Predicate>
struct spec_object_traits< SelectedSubset<ContainerRef, Predicate> >
   : spec_object_traits<is_container> {
   static const bool is_temporary=true,
                     is_always_const=effectively_const<ContainerRef>::answer;
};

template <typename ContainerRef, typename Predicate>
struct spec_object_traits< TruncatedContainer<ContainerRef, Predicate> >
   : spec_object_traits<is_container> {
   static const bool is_temporary=true,
                     is_always_const=effectively_const<ContainerRef>::answer;
};

template <typename Container, typename Predicate> inline
SelectedSubset<Container&, Predicate>
attach_selector(Container& c, const Predicate& pred)
{
   return SelectedSubset<Container&, Predicate> (c,pred);
}

template <typename Container, typename Predicate> inline
SelectedSubset<const Container&, Predicate>
attach_selector(const Container& c, const Predicate& pred)
{
   return SelectedSubset<const Container&, Predicate> (c,pred);
}

template <typename Container, typename Predicate> inline
TruncatedContainer<Container&, Predicate>
attach_truncator(Container& c, const Predicate& pred)
{
   return TruncatedContainer<Container&, Predicate> (c,pred);
}

template <typename Container, typename Predicate> inline
TruncatedContainer<const Container&, Predicate>
attach_truncator(const Container& c, const Predicate& pred)
{
   return TruncatedContainer<const Container&, Predicate> (c,pred);
}

/** Selecting output iterator

    This is a combination of an output iterator (called below `basis iterator') and a predicate.

    When a data item is assigned to the output iterator, it is first evaluated by the predicate object.
    Only items mapped to \\true\\ are passed through to the assignment method of the basis iterator.
*/
template <typename Iterator, typename Predicate>
class output_predicate_selector : public iterator_traits<Iterator>::derivable_type {
protected:
   Predicate pred;

   typedef typename iterator_traits<Iterator>::derivable_type super;
public:
   typedef output_iterator_tag iterator_category;
   typedef typename iterator_traits<Iterator>::value_type value_type;

   output_predicate_selector() { }

   output_predicate_selector(const Iterator& cur_arg, const Predicate& pred_arg=Predicate())
      : super(cur_arg), pred(pred_arg) { }

   output_predicate_selector& operator= (typename function_argument<value_type>::type arg)
   {
      if (pred(arg))
	 *static_cast<super*>(this)=arg;
      return *this;
   }

   template <class Arg>
   output_predicate_selector& operator= (const Arg& arg)
   {
      if (pred(arg))
	 *static_cast<super*>(this)=arg;
      return *this;
   }

   output_predicate_selector& operator* () { return *this; }
   output_predicate_selector& operator++ () { return *this; }
   output_predicate_selector& operator++ (int) { return *this; }
};

template <typename Iterator, typename Predicate> inline
output_predicate_selector<Iterator,Predicate>
make_output_predicate_selector(Iterator it, Predicate pred)
{
   return output_predicate_selector<Iterator,Predicate>(it,pred);
}

struct output_predicate_selector_modifier {
   template <typename Iterator, typename Predicate, typename ExpectedFeatures>
   struct defs {
      typedef ExpectedFeatures needed_features;
      typedef output_predicate_selector<Iterator,Predicate> iterator;
   };
};

template <typename IteratorPair, typename Predicate,
          typename Category=typename least_derived< cons<typename IteratorPair::iterator_category,
							 bidirectional_iterator_tag> >::type>
class binary_predicate_selector : public IteratorPair {
protected:
   typedef IteratorPair super;
   typedef binary_helper<IteratorPair,Predicate> helper;
   typedef typename helper::star1 star1;
   typedef typename helper::star2 star2;
   typename helper::operation pred;

   void skip_masked()
   {
      while (!this->at_end() && !pred(star1::get(*this), star2::get(this->second)))
	 super::operator++();
   }

   template <typename,typename,typename> friend class binary_predicate_selector;
public:
   typedef typename least_derived< cons<typename IteratorPair::iterator_category,
					bidirectional_iterator_tag> >::type
      iterator_category;
   typedef binary_predicate_selector<typename iterator_traits<IteratorPair>::iterator, Predicate> iterator;
   typedef binary_predicate_selector<typename iterator_traits<IteratorPair>::const_iterator, Predicate> const_iterator;

   binary_predicate_selector() { }
   binary_predicate_selector(const iterator& it)
      : super(static_cast<const typename iterator::super&>(it)), pred(helper::create(it.pred)) { }

   binary_predicate_selector(const IteratorPair& cur_arg,
			     const Predicate& pred_arg=Predicate())
      : super(cur_arg), pred(helper::create(pred_arg))
   {
      skip_masked();
   }
   binary_predicate_selector(typename alt_constructor<IteratorPair>::arg_type& cur_arg,
			     const Predicate& pred_arg=Predicate())
      : super(cur_arg), pred(helper::create(pred_arg))
   {
      skip_masked();
   }

   binary_predicate_selector(const typename IteratorPair::first_type& first_arg,
			     const typename IteratorPair::second_type& second_arg,
			     const Predicate& pred_arg=Predicate())
      : super(first_arg,second_arg) , pred(helper::create(pred_arg))
   {
      skip_masked();
   }

   binary_predicate_selector(typename alt_constructor<typename IteratorPair::first_type>::arg_type& first_arg,
			     typename alt_constructor<typename IteratorPair::second_type>::arg_type& second_arg,
			     const Predicate& pred_arg=Predicate())
      : super(first_arg,second_arg) , pred(helper::create(pred_arg))
   {
      skip_masked();
   }

   binary_predicate_selector& operator++ ()
   {
      super::operator++();
      skip_masked();
      return *this;
   }

   const binary_predicate_selector operator++ (int) { binary_predicate_selector copy=*this; operator++(); return copy; }

   void reset() { super::reset();  skip_masked(); }
};

template <typename IteratorPair, typename Predicate>
class binary_predicate_selector<IteratorPair, Predicate, bidirectional_iterator_tag>
   : public binary_predicate_selector<IteratorPair, Predicate, forward_iterator_tag> {
   typedef binary_predicate_selector<IteratorPair, Predicate, forward_iterator_tag> _super;
public:
   binary_predicate_selector() { }
   binary_predicate_selector(const typename _super::iterator& it)
      : _super(it) { }

   binary_predicate_selector(const IteratorPair& cur_arg,
			     const Predicate& pred_arg=Predicate())
      : _super(cur_arg, pred_arg) { }
   binary_predicate_selector(typename alt_constructor<IteratorPair>::arg_type& cur_arg,
			     const Predicate& pred_arg=Predicate())
      : _super(cur_arg, pred_arg) { }

   binary_predicate_selector(const typename IteratorPair::first_type& first_arg,
			     const typename IteratorPair::second_type& second_arg,
			     const Predicate& pred_arg=Predicate())
      : _super(first_arg, second_arg, pred_arg) { }
   binary_predicate_selector(typename alt_constructor<typename IteratorPair::first_type>::arg_type& first_arg,
			     typename alt_constructor<typename IteratorPair::second_type>::arg_type& second_arg,
			     const Predicate& pred_arg=Predicate())
      : _super(first_arg, second_arg, pred_arg) { }

   binary_predicate_selector& operator-- ()
   {
      do
	 IteratorPair::operator--();
      while (!pred(typename _super::star1::get(*this), typename _super::star2::get(this->second)));
      return *this;
   }
private:
   void operator+=(int);
   void operator-=(int);
   void operator+(int);
   void operator-(int);
   void operator[](int);
};

template <typename IteratorPair, typename Predicate, typename Category, typename Feature>
struct check_iterator_feature<binary_predicate_selector<IteratorPair, Predicate, Category>, Feature> {
   static const bool answer=check_iterator_feature<IteratorPair, Feature>::answer ||
                            identical<Feature, reference_relaxed>::answer;	// can't enforce it anyway
};

template <typename Iterator1, typename Iterator2, typename Predicate> inline
binary_predicate_selector<iterator_pair<Iterator1, Iterator2>, Predicate>
make_binary_predicate_selector(Iterator1 first, Iterator2 second, const Predicate& pred)
{
   return binary_predicate_selector<iterator_pair<Iterator1, Iterator2>, Predicate>(first,second,pred);
}

struct binary_predicate_selector_modifier {
   template <typename IteratorPair, typename Predicate, typename ExpectedFeatures>
   struct defs {
      typedef binary_helper<IteratorPair,Predicate> helper;
      static const bool
	 relaxed_arg2 = !attrib<typename helper::operation::second_argument_type>::is_reference;

      typedef typename mix_features< typename list_search_all<ExpectedFeatures,reference_relaxed,identical>::negative,
				     end_sensitive>::result
         needed_pair_features;
      typedef void needed_features1;
      typedef typename if_else<relaxed_arg2, reference_relaxed, void>::result needed_features2;
      typedef binary_predicate_selector<IteratorPair, Predicate> iterator;
   };
};

template <typename ContainerRef1, typename ContainerRef2, typename Predicate>
class SelectedContainerPairSubset
   : public modified_container_pair_base<ContainerRef1, ContainerRef2, Predicate>,
     public modified_container_pair_impl< SelectedContainerPairSubset<ContainerRef1,ContainerRef2,Predicate>,
               cons< Container1< ContainerRef1 >,
               cons< Container2< ContainerRef2 >,
               cons< Modifier< binary_predicate_selector_modifier >,
		     Accessor< Predicate > > > >
            >,
     public generic_of_subset< SelectedContainerPairSubset<ContainerRef1,ContainerRef2,Predicate>,
			       typename deref<ContainerRef1>::type > {
   typedef modified_container_pair_base<ContainerRef1, ContainerRef2, Predicate> _base;
   typedef modified_container_pair_impl<SelectedContainerPairSubset> _super;
public:
   SelectedContainerPairSubset(typename _base::first_arg_type src1_arg, typename _base::second_arg_type src2_arg,
			       const Predicate& pred_arg=Predicate())
      : _base(src1_arg,src2_arg,pred_arg) { }

   using _base::get_accessor;
};

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

template <typename Container1, typename Container2, typename Predicate> inline
SelectedContainerPairSubset<Container1&, Container2&, Predicate>
attach_selector(Container1& c1, Container2& c2, const Predicate& pred)
{
   return SelectedContainerPairSubset<Container1&, Container2&, Predicate> (c1,c2,pred);
}

template <typename Container1, typename Container2, typename Predicate> inline
SelectedContainerPairSubset<const Container1&, Container2&, Predicate>
attach_selector(const Container1& c1, Container2& c2, Predicate pred)
{
   return SelectedContainerPairSubset<const Container1&, Container2&, Predicate> (c1,c2,pred);
}

template <typename Container1, typename Container2, typename Predicate> inline
SelectedContainerPairSubset<Container1&, const Container2&, Predicate>
attach_selector(Container1& c1, const Container2& c2, Predicate pred)
{
   return SelectedContainerPairSubset<Container1&, const Container2&, Predicate> (c1,c2,pred);
}

template <typename Container1, typename Container2, typename Predicate> inline
SelectedContainerPairSubset<const Container1&, const Container2&, Predicate>
attach_selector(const Container1& c1, const Container2& c2, Predicate pred)
{
   return SelectedContainerPairSubset<const Container1&, const Container2&, Predicate> (c1,c2,pred);
}

template <typename Container1, typename Container2> inline
SelectedContainerPairSubset<Container1&, const Container2&, BuildBinaryIt<operations::second_deref> >
attach_mask(Container1& data, const Container2& boolean)
{
   return SelectedContainerPairSubset<Container1&, const Container2&, BuildBinaryIt<operations::second_deref> >
          (data,boolean);
}

template <typename Container1, typename Container2> inline
SelectedContainerPairSubset<const Container1&, const Container2&, BuildBinaryIt<operations::second_deref> >
attach_mask(const Container1& data, const Container2& boolean)
{
   return SelectedContainerPairSubset<const Container1&, const Container2&, BuildBinaryIt<operations::second_deref> >
          (data,boolean);
}

} // end namespace pm

namespace polymake {
   using pm::make_unary_predicate_selector;
   using pm::make_binary_predicate_selector;
   using pm::make_output_predicate_selector;
   using pm::attach_selector;
   using pm::attach_mask;
} // end namespace polymake

#endif // _POLYMAKE_SELECTED_SUBSET_H

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