/* 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_POWERSET_H
#define _POLYMAKE_POWERSET_H "$Project: polymake $$Id: PowerSet.h,v 1.27 2004/06/22 16:22:45 gawrilow Exp $"

#include <vector>
#ifdef POLY_DEBUG
#  include <sstream>
#endif

#ifndef _POLYMAKE_SET_H
#  include <Set.h>
#endif
#ifndef _POLYMAKE_SELECTED_SUBSET_H
#  include <SelectedSubset.h>
#endif

namespace pm {

template <typename ContainerRef>
class Subsets_of_1
   : public modified_container_impl< Subsets_of_1<ContainerRef>,
               cons< Container< ContainerRef >,
		     Accessor< operations::masquerade2<SingleElementSetCmp,
				  typename generic_of_subsets< Subsets_of_1<ContainerRef>, typename deref<ContainerRef>::type
                                                             >::subset_element_comparator
                               > > >
            >,
     public generic_of_subsets< Subsets_of_1<ContainerRef>, typename deref<ContainerRef>::type > {
   typedef modified_container_impl<Subsets_of_1> _super;
protected:
   typedef typename alias<ContainerRef>::arg_type arg_type;
   alias<ContainerRef> base;
public:
   Subsets_of_1(arg_type base_arg) : base(base_arg) { }

   const typename _super::container& get_container() const { return base; }
};

template <typename Container> inline
const Subsets_of_1<const Container&>
all_subsets_of_1(const Container& c) {
   return c;
}

template <typename SkipIterator,
	  bool _from_std=derived_from_instance<SkipIterator, std::reverse_iterator>::answer>
class skip_predicate {
public:
   typedef SkipIterator argument_type;
   typedef bool result_type;

   skip_predicate(const SkipIterator& skip_arg) : skip(skip_arg) { }

   template <typename Iterator>
   bool operator() (const Iterator& it) const { return it!=skip; }
private:
   SkipIterator skip;
};

template <typename SkipIterator>
class skip_predicate<SkipIterator, true> {
public:
   typedef typename SkipIterator::iterator_type BaseIterator;
   typedef SkipIterator argument_type;
   typedef bool result_type;

   skip_predicate(const SkipIterator& skip_arg) : skip(skip_arg), skip_base(skip.base()) {
      --skip_base;
   }

   bool operator() (const SkipIterator& it) const { return it!=skip; }
   bool operator() (const BaseIterator& it) const { return it!=skip_base; }

   typedef typename if_else< identical<BaseIterator, typename iterator_traits<BaseIterator>::derivable_type>::answer,
			     BaseIterator, const typename iterator_traits<BaseIterator>::derivable_type>::result
      alt_arg_type;
   bool operator() (alt_arg_type& it) const { return it!=skip_base; }
private:
   SkipIterator skip;
   BaseIterator skip_base;
};

template <typename Container, typename SkipIterator> class Subsets_less_1_iterator;

template <typename Container, typename SkipIterator,
          typename Category=typename least_derived< cons<typename container_traits<Container>::category,
							 bidirectional_iterator_tag> >::type>
class Subset_less_1
   : public generic_of_subset< Subset_less_1<Container,SkipIterator>, Container> {
   friend class Subsets_less_1_iterator<Container,SkipIterator>;
protected:
   const Container* base;
   SkipIterator skip;

public:
   typedef typename Container::value_type value_type;
   typedef typename Container::const_reference const_reference;
   typedef const_reference reference;

   Subset_less_1(const Container& base_arg, const SkipIterator& skip_arg)
      : base(&base_arg), skip(skip_arg) { }

   typedef unary_predicate_selector<typename ensure_features<Container, end_sensitive>::const_iterator,
				    skip_predicate<SkipIterator> >
      const_iterator;
   typedef const_iterator iterator;

   iterator begin() const
   {
      return iterator(ensure(*base,(end_sensitive*)0).begin(), skip);
   }
   iterator end() const
   {
      return iterator(ensure(*base,(end_sensitive*)0).end(), skip);
   }
   reference front() const
   {
      typename Container::const_iterator b=base->begin();
      if (b==skip) ++b;
      return *b;
   }

   int size() const { return base->size()-1; }
   bool empty() const { return base->empty() || base->size()<=1; }

   typename iterator_traits<SkipIterator>::reference skipped_element() const { return *skip; }
};

template <typename Container, typename SkipIterator>
class Subset_less_1<Container, SkipIterator, bidirectional_iterator_tag>
   : public Subset_less_1<Container, SkipIterator, forward_iterator_tag> {
   typedef Subset_less_1<Container, SkipIterator, forward_iterator_tag> _super;
   friend class Subsets_less_1_iterator<Container,SkipIterator>;
public:
   Subset_less_1(const Container& base_arg, const SkipIterator& skip_arg)
      : _super(base_arg, skip_arg) { }

   typedef unary_predicate_selector<typename ensure_features<Container, end_sensitive>::const_reverse_iterator,
				    skip_predicate<SkipIterator> >
      const_reverse_iterator;
   typedef const_reverse_iterator reverse_iterator;

   reverse_iterator rbegin() const
   {
      return reverse_iterator(ensure(*this->base,(end_sensitive*)0).rbegin(), this->skip);
   }
   reverse_iterator rend() const
   {
      return reverse_iterator(ensure(*this->base,(end_sensitive*)0).rend(), this->skip);
   }
};

template <typename Container, typename SkipIterator>
class Subsets_less_1_iterator {
public:
   typedef forward_iterator_tag iterator_category;
   typedef Subset_less_1<Container, SkipIterator> value_type;
   typedef const value_type& reference;
   typedef const value_type* pointer;
   typedef ptrdiff_t difference_type;
   typedef Subsets_less_1_iterator iterator;
   typedef Subsets_less_1_iterator const_iterator;

   Subsets_less_1_iterator(const Container& base_arg, const SkipIterator& skip_arg)
      : value(base_arg,skip_arg) { }

   reference operator* () const { return value; }
   pointer operator-> () const { return &value; }

   iterator& operator++ () { ++value.skip; return *this; }
   const iterator operator++ (int) { iterator copy=*this; operator++(); return copy; }

   bool operator== (const iterator& it) const { return value.skip==it.value.skip; }
   bool operator!= (const iterator& it) const { return !operator==(it); }

   bool at_end() const { return value.skip.at_end(); }
protected:
   value_type value;
};

template <typename ContainerRef>
class Subsets_less_1
   : public generic_of_subsets<Subsets_less_1<ContainerRef>, typename deref<ContainerRef>::type> {
protected:
   typedef typename alias<ContainerRef>::arg_type arg_type;
   alias<ContainerRef> base;

   typedef typename deref<ContainerRef>::type base_type;
   const base_type& get_base() const { return base; }

   typedef cons<_reversed, end_sensitive> req_features;
   typedef typename ensure_features<base_type, req_features>::const_iterator skip_iterator;
public:
   typedef Subsets_less_1_iterator<base_type,skip_iterator> iterator;
   typedef typename iterator::value_type value_type;
   typedef typename iterator::reference reference;
   typedef iterator const_iterator;
   typedef reference const_reference;

   Subsets_less_1(arg_type base_arg) : base(base_arg) { }

   int size() const { return get_base().size(); }
   bool empty() const { return get_base().empty(); }

   iterator begin() const
   {
      return iterator(get_base(), ensure(get_base(), (req_features*)0).begin());
   }
   iterator end() const
   {
      return iterator(get_base(), ensure(get_base(), (req_features*)0).end());
   }
};

template <typename Container, typename SkipIterator>
struct check_iterator_feature<Subsets_less_1_iterator<Container,SkipIterator>, end_sensitive> : True { };

template <typename Container, typename SkipIterator>
struct check_iterator_feature<Subsets_less_1_iterator<Container,SkipIterator>, data_bearing> : True { };

template <typename Container> inline
const Subsets_less_1<const Container&>
all_subsets_less_1(const Container& c)
{
   return c;
}

template <typename Container> class Subsets_of_k_iterator;

template <typename _Container>
class pointed_subset
   : public modified_container_impl< pointed_subset<_Container>,
               cons< Container< std::vector<typename container_traits<_Container>::const_iterator> >,
                     Accessor< BuildUnary<operations::extra_deref> > >
            >,
     public generic_of_subset<pointed_subset<_Container>, _Container> {
   friend class Subsets_of_k_iterator<_Container>;
protected:
   typedef typename _Container::const_iterator elem_iterator;

   const _Container* base;
   std::vector<elem_iterator> ptr;
public:
   const std::vector<elem_iterator>& get_container() const { return ptr; }

   pointed_subset() { }

   pointed_subset(const _Container& base_arg, int k)
      : base(&base_arg), ptr(k)
   {
      typename std::vector<elem_iterator>::iterator ptr_i=ptr.begin(), ptr_last=ptr.end();
      for (elem_iterator e=base->begin(); ptr_i != ptr_last; ++e, ++ptr_i)
	 *ptr_i=e;
   }
};

template <typename Container>
class Subsets_of_k_iterator {
public:
   typedef forward_iterator_tag iterator_category;
   typedef pointed_subset<Container> value_type;
   typedef const value_type& reference;
   typedef const value_type* pointer;
   typedef ptrdiff_t difference_type;
   typedef Subsets_of_k_iterator iterator;
   typedef Subsets_of_k_iterator const_iterator;

   Subsets_of_k_iterator() { }

   Subsets_of_k_iterator(const Container& base_arg, int k_arg, bool at_end_arg=false)
      : value(base_arg,k_arg), _at_end(at_end_arg) { }

   reference operator* () const { return value; }
   pointer operator-> () const { return &value; }

   iterator& operator++()
   {
      typename value_type::elem_iterator stop=value.base->end();
      for (typename std::vector<typename value_type::elem_iterator>::iterator ptr_first=value.ptr.begin(), ptr_last=value.ptr.end(), ptr_i=ptr_last;
	   ptr_i != ptr_first; --ptr_i) {
	 typename value_type::elem_iterator new_stop=(ptr_i[-1])++;
	 if (ptr_i[-1] != stop) {
	    for (; ptr_i != ptr_last; ++ptr_i)
	       ++(*ptr_i=ptr_i[-1]);
	    return *this;
	 }
	 stop=new_stop;
      }
      _at_end=true;
      return *this;
   }

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

   bool operator== (const iterator& it) const
   {
      return _at_end==it._at_end && (_at_end || value.ptr==it.value.ptr);
   }
   bool operator!= (const iterator& it) const { return !operator==(it); }

   bool at_end() const { return _at_end; }
protected:
   value_type value;
   bool _at_end;
};

template <typename ContainerRef>
class Subsets_of_k
   : public generic_of_subsets< Subsets_of_k<ContainerRef>, typename deref<ContainerRef>::type> {
public:
   typedef typename deref<ContainerRef>::type base_type;

   typedef Subsets_of_k_iterator<base_type> iterator;
   typedef typename iterator::value_type value_type;
   typedef typename iterator::reference reference;
   typedef iterator const_iterator;
   typedef reference const_reference;

   Subsets_of_k(typename alias<ContainerRef>::arg_type base_arg, int k_arg)
      : base(base_arg), k(k_arg)
   {
      DIMENSION_CHECK((k<0 || k>get_base().size()), "Subsets_of_k - invalid size");
   }

   int size() const
   {
      // n over k
      int n=get_base().size(), s=1;
      for (int i=0, i_end= k*2<n ? k : n-k; i<i_end; ) {
	 s*=n-i; s/=++i;
      }
      return s;
   }

   bool empty() const { return false; }

   iterator begin() const { return iterator(get_base(),k); }
   iterator end() const { return iterator(get_base(),k,true); }
protected:
   alias<ContainerRef> base;
   int k;

   const base_type& get_base() const { return base; }
};

template <typename Container>
struct check_iterator_feature<Subsets_of_k_iterator<Container>, end_sensitive> : True { };

template <typename Container>
struct check_iterator_feature<Subsets_of_k_iterator<Container>, data_bearing> : True { };

template <typename Container> inline
const Subsets_of_k<const Container&>
all_subsets_of_k(const Container& c, int k)
{
   return Subsets_of_k<const Container&>(c,k);
}

template <typename _PowerSet, typename _ElementSet>
int insertMax(_PowerSet& power_set, const GenericSet<_ElementSet>& _element_set)
{
   typename prevent_lazy<_ElementSet>::result_type element_set=prevent_lazy<_ElementSet>::get(_element_set.top());
   if (element_set.empty()) return -1;
   for (typename Entire<_PowerSet>::iterator e=entire(power_set); !e.at_end(); ) {
      int inc=incl(element_set,*e);
      // found a subset containing or equal to set
      if (inc<=0) return inc;
      // found a subset being contained in set
      if (inc==1) power_set.erase(e++);
      else ++e;
   }
   power_set.insert(element_set);
   return 1;
}

template <typename _PowerSet, typename _ElementSet>
int insertMin(_PowerSet& power_set, const GenericSet<_ElementSet>& _element_set)
{
   typename prevent_lazy<_ElementSet>::result_type element_set=prevent_lazy<_ElementSet>::get(_element_set.top());
   if (element_set.empty()) return -1;
   for (typename Entire<_PowerSet>::iterator e=entire(power_set); !e.at_end(); ) {
      int inc=incl(*e,element_set);
      // found a subset containing or equal to set
      if (inc<=0) return inc;
      // found a subset being contained in set
      if (inc==1) power_set.erase(e++);
      else ++e;
   }
   power_set.insert(element_set);
   return 1;
}

template <typename E, typename Comparator=BuildBinary<operations::cmp> >
class PowerSet : public Set< Set<E,Comparator> > {
   typedef Set< Set<E,Comparator> > super;
public:
   /// Create as empty.
   PowerSet() { }

   template <typename Top>
   PowerSet(const GenericSet<Top, Set<E,Comparator> >& S) : super(S) { }

   template <typename Top>
   PowerSet& operator= (const GenericSet<Top, Set<E,Comparator> >& S)
   {
      super::operator=(S);
      return *this;
   }

   /** Reads subsets from an input sequence.
       They must be sorted in the lexicographical order.
   */
   template <typename Iterator>
   PowerSet(Iterator first, Iterator last)
   {
      copy(first, last, back_inserter(*this));
   }

   template <typename InputIterator>
   PowerSet(InputIterator src, end_sensitive)
   {
      copy(src, back_inserter(*this));
   }

   /** Adds an independent subset.
       The new subset will not be added if there is already another subset that includes the given one.
       All subsets in the \\PowerSet\\ that are included in the new one are removed.
       @returnval  1 new subset inserted, smaller subsets possibly deleted
       @returnval  0 new subset not inserted, because the same subset was already there
       @returnval -1 new subset not inserted, because there already is a bigger one
   */
   template <typename Top>
   int insertMax(const GenericSet<Top,E,Comparator>& s)
   {
      return pm::insertMax(*this,s);
   }

   /** Adds an independent subset.
       The new subset will not be added if there is already another subset that is contained in the given one.
       All subsets in the \\PowerSet\\ that contain in the new one are removed.
       @returnval  1 new subset inserted, larger subsets possibly deleted
       @returnval  0 new subset not inserted, because the same subset was already there
       @returnval -1 new subset not inserted, because there already is a smaller one
   */
   template <typename Top>
   int insertMin(const GenericSet<Top,E,Comparator>& s)
   {
      return pm::insertMin(*this,s);
   }
#ifdef POLY_DEBUG
   void check(const char* label) const
   {
      super::check(label);
      for (typename super::const_iterator e=this->begin(); !e.at_end(); ++e) {
	 std::ostringstream elabel;
	 wrap(elabel) << label << '[' << *e << ']';
	 e->check(elabel.str().c_str());
      }
   }
#endif
};

/// Gather all independent intersections of subsets from the given \\PowerSet\\.
template <typename Iterator>
PowerSet<typename iterator_traits<Iterator>::value_type::element_type,
	 typename iterator_traits<Iterator>::value_type::element_comparator>
ridges(Iterator set)
{
   typedef typename iterator_traits<Iterator>::value_type::element_type element_type;
   typedef typename iterator_traits<Iterator>::value_type::element_comparator element_comparator;
   PowerSet<element_type, element_comparator> R;
   for (; !set.at_end(); ++set) {
      Iterator set2=set;
      for (++set2; !set2.at_end(); ++set2) {
	 Set<int> ridge=(*set) * (*set2);
	 R.insertMax(ridge);
      }
   }
   return R;
}

} // end namespace pm

namespace polymake {
   using pm::PowerSet;
   using pm::ridges;
   using pm::Subsets_of_1;
   using pm::all_subsets_of_1;
   using pm::Subsets_less_1;
   using pm::all_subsets_less_1;
   using pm::Subsets_of_k;
   using pm::all_subsets_of_k;
}

#endif // _POLYMAKE_POWERSET_H

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