/* Copyright (c) 1997-2006
   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_GENERIC_SET_H
#define _POLYMAKE_GENERIC_SET_H "$Project: polymake $$Id: GenericSet.h 7402 2006-07-27 23:44:14Z gawrilow $"

#ifndef _POLYMAKE_SERIES_H
#  include <Series.h>
#endif
#ifndef _POLYMAKE_COMPARATORS_H
#  include <comparators.h>
#endif
#ifndef _POLYMAKE_GENERIC_IO_H
#  include <GenericIO.h>
#endif

namespace pm {

/* ------------
 *  Complement
 * ------------ */

template <typename _Set, typename E=typename _Set::element_type, typename Comparator=typename _Set::element_comparator>
class Complement : public operators::base {
protected:
   Complement();
   ~Complement();
public:
   typedef E element_type;
   typedef Comparator element_comparator;
   typedef E value_type;
   typedef GenericSet<_Set,E,Comparator> generic_type;
   typedef Set<E,Comparator> persistent_type;
   typedef _Set base_type;
   const _Set& base() const { return reinterpret_cast<const _Set&>(*this); }
   bool contains(typename function_argument<E>::type k) const { return !base().contains(k); }
};

template <typename _Set, typename E, typename Comparator>
struct container_traits< Complement<_Set,E,Comparator> > {
   typedef typename container_traits<_Set>::value_type value_type;
   typedef typename container_traits<_Set>::const_reference const_reference;
   typedef const_reference reference;
   typedef forward_iterator_tag category;
};

template <typename _Set, typename E, typename Comparator>
struct container_traits< const Complement<_Set,E,Comparator> >
   : container_traits< Complement<_Set,E,Comparator> > { };

template <typename _Set, typename E, typename Comparator>
struct redirect_object_traits< Complement<_Set,E,Comparator> >
   : spec_object_traits<is_container> {
   typedef Set<E,Comparator> persistent_type;
   typedef GenericSet<_Set,E,Comparator> generic_type;
   typedef is_set generic_tag;
};

/* ------------------
 *  SingleElementSet
 * ------------------ */
template <typename E, typename Comparator>
class SingleElementSetCmp;

template <typename E, typename Comparator>
class SingleElementSetContains {
public:
   bool contains(typename function_argument<E>::const_type x) const
   {
      typename binary_op_builder<Comparator, void, void,
	                         typename function_argument<E>::const_type, typename function_argument<E>::const_type>::operation
	 cmp;
      return cmp(x, static_cast<const SingleElementSetCmp<E,Comparator>*>(this)->front())==cmp_eq;
   }
};

template <typename E, typename Comparator>
class SingleElementSetCmp
   : public single_elem_container<E>,
     public GenericSet<SingleElementSetCmp<E,Comparator>, E, Comparator>,
     public SingleElementSetContains<E, Comparator> {
public:
   SingleElementSetCmp(typename function_argument<E>::type arg)
      : single_elem_container<E>(arg) { }
};

template <typename E, typename Comparator>
class SingleElementSetCmp<const E&, Comparator>
   : public single_elem_container<const E&>,
     public GenericSet<SingleElementSetCmp<const E&,Comparator>, E, Comparator>,
     public SingleElementSetContains<const E&, Comparator> {
protected:
   ~SingleElementSetCmp();
};

template <typename E>
class SingleElementSet : public SingleElementSetCmp<E, operations::cmp<> > {
public:
   SingleElementSet(typename function_argument<E>::type arg)
      : SingleElementSetCmp<E, operations::cmp<> >(arg) { }
};

template <typename E>
class SingleElementSet<const E&> : public SingleElementSetCmp<const E&, operations::cmp<> > {
protected:
   ~SingleElementSet();
};

template <typename Comparator, typename E> inline
const SingleElementSetCmp<const E&, Comparator>&
scalar2set(const E& x)
{
   return reinterpret_cast<const SingleElementSetCmp<const E&, Comparator>&>(x);
}

template <typename E> inline
const SingleElementSet<const E&>&
scalar2set(const E& x)
{
   return reinterpret_cast<const SingleElementSet<const E&>&>(x);
}

/* ----------
 *  LazySet2
 * ---------- */

template <typename SetRef1, typename SetRef2, typename Controller>
class LazySet2
   : public container_pair_base<SetRef1, SetRef2>,
     public modified_container_pair_impl< LazySet2<SetRef1,SetRef2,Controller>,
					  list( Container1< SetRef1 >,
						Container2< SetRef2 >,
						IteratorCoupler< zipping_coupler<typename deref<SetRef1>::type::element_comparator, Controller> >,
						Operation< BuildBinaryIt<operations::zipper> >,
						IteratorConstructor< binary_transform_constructor< Bijective<False> > > ) >,
     public GenericSet< LazySet2<SetRef1,SetRef2,Controller>,
                        typename identical<typename deref<SetRef1>::type::element_type,
					   typename deref<SetRef2>::type::element_type>::type,
                        typename identical<typename deref<SetRef1>::type::element_comparator,
					   typename deref<SetRef2>::type::element_comparator>::type
                      > {
   typedef container_pair_base<SetRef1, SetRef2> _base;
   typedef modified_container_pair_impl<LazySet2> _super;
public:
   LazySet2(typename _base::first_arg_type src1_arg, typename _base::second_arg_type src2_arg,
	    Controller=Controller())
      : _base(src1_arg,src2_arg) { }

   const typename deref<SetRef1>::type::element_comparator& get_comparator_object() const
   {
      return this->get_container1().get_comparator_object();
   }

   bool contains(typename function_argument<typename deref<SetRef1>::type::element_type>::type x) const
   {
      return Controller::contains(this->get_container1().contains(x), this->get_container2().contains(x));
   }
};

template <typename SetRef1, typename SetRef2, typename Controller>
struct spec_object_traits< LazySet2<SetRef1, SetRef2, Controller> >
   : spec_object_traits<is_container> {
   static const bool is_lazy=true, is_temporary=true, is_always_const=true;
};

/* -----------------------------
 *  Set with assigned dimension
 * ----------------------------- */

template <typename SetRef,
	  bool _is_complement=derived_from_instance3<typename deref<SetRef>::type,Complement>::value>
struct complement_helper : False {
   typedef typename deref<SetRef>::type container;
   typedef container base_type;
   typedef const container& container_ref;
   static bool dimension_check(container_ref c, int d)
   {
      return c.empty() || (c.front()>=0 && c.back()<d);
   }
};

template <typename SetRef>
struct complement_helper<SetRef, true> : True {
   typedef typename deref<SetRef>::type::base_type base_type;
   typedef LazySet2<sequence, const base_type&, set_difference_zipper> container;
   typedef container container_ref;
   static bool dimension_check(SetRef c, int d)
   {
      return c.base().empty() || (c.base().front()>=0 && c.base().back()<d);
   }
};

template <typename SetRef>
class Set_with_dim
   : public modified_container_impl< Set_with_dim<SetRef>,
				     list( Container< typename complement_helper<SetRef>::container >,
					   Operation< pair<nothing, operations::identity<int> > >,
					   ExpectedFeatures<end_sensitive> ) >,
     public GenericSet< Set_with_dim<SetRef>, typename deref<SetRef>::type::element_type,
			typename deref<SetRef>::type::element_comparator> {
protected:
   alias<SetRef> set;
   int _dim;
public:
   typedef typename alias<SetRef>::arg_type arg_type;

   Set_with_dim(arg_type set_arg, int dim_arg)
      : set(set_arg), _dim(dim_arg) { }

   const typename complement_helper<SetRef>::base_type& get_set() const
   {
      return _get_set(complement_helper<SetRef>());
   }
   typename complement_helper<SetRef>::container_ref get_container() const
   {
      return _get_container(complement_helper<SetRef>());
   }
   int size() const
   {
      return _size(complement_helper<SetRef>());
   }
   int max_size() const
   {
      return _dim;
   }
   int dim() const
   {
      return _dim;
   }
   bool contains(typename function_argument<typename deref<SetRef>::type::element_type>::type x) const
   {
      return get_set().contains(x);
   }
   const typename deref<SetRef>::type::element_comparator& get_comparator_object() const
   {
      return get_set().get_comparator_object();
   }

private:
   const typename complement_helper<SetRef>::base_type& _get_set(False) const
   {
      return set;
   }
   const typename complement_helper<SetRef>::base_type& _get_set(True) const
   {
      return static_cast<SetRef>(set).base();
   }
   typename complement_helper<SetRef>::container_ref _get_container(False) const
   {
      return _get_set(False());
   }
   typename complement_helper<SetRef>::container_ref _get_container(True) const
   {
      return typename complement_helper<SetRef>::container(sequence(0,_dim), _get_set(True()));
   }
   int _size(False) const
   {
      return _get_set(False()).size();
   }
   int _size(True) const
   {
      return _dim-_get_set(True()).size();
   }
};

template <typename SetRef>
struct check_container_feature<Set_with_dim<SetRef>, sparse_compatible> : True { };

template <typename SetRef,
	  bool _has_dim=check_container_feature<typename complement_helper<SetRef>::container, sparse_compatible>::value>
struct Set_with_dim_helper {
   typedef SetRef container;
   typedef typename attrib<SetRef>::plus_const_ref container_ref;
   typedef alias<SetRef> alias_type;

   static container_ref create(container_ref c, int)
   {
      return c;
   }
   static container_ref get_set(container_ref c)
   {
      return c;
   }
   static bool check(container_ref c, int d)
   {
      return c.dim()==d;
   }
};

template <typename SetRef>
struct Set_with_dim_helper<SetRef, false> {
   typedef Set_with_dim<SetRef> alias_type;
   typedef const alias_type container;

   static alias_type create(typename alias_type::arg_type c, int d)
   {
      return container(c,d);
   }
   static const typename complement_helper<SetRef>::base_type& get_set(container& c)
   {
      return c.get_set();
   }
   static bool check(typename attrib<SetRef>::plus_const_ref c, int d)
   {
      return complement_helper<SetRef>::dimension_check(c,d);
   }
};

/* -----------------------------------------
 *  Functors for set-theoretical operations
 * ----------------------------------------- */

namespace operations {

template <typename OpRef>
struct bitwise_inv_impl<OpRef, is_set> {
   typedef OpRef argument_type;
   typedef const Complement<typename deref<OpRef>::type>& result_type;

   result_type operator() (typename function_argument<OpRef>::const_type x) const
   {
      return reinterpret_cast<result_type>(x);
   }
};

template <typename Set>
struct bitwise_inv_impl<const Complement<Set>&, is_set> {
   typedef const Complement<Set>& argument_type;
   typedef const Set& result_type;

   result_type operator() (argument_type x) const
   {
      return x.base();
   }
};

template <typename LeftRef, typename RightRef, bool check>
struct add_impl<LeftRef, RightRef, check, cons<is_set, is_set> > {
   typedef LeftRef first_argument_type;
   typedef RightRef second_argument_type;
   typedef LazySet2<typename attrib<LeftRef>::plus_const, typename attrib<RightRef>::plus_const, set_union_zipper> result_set;
   typedef const result_set result_type;

   result_type operator() (typename function_argument<LeftRef>::const_type l,
			   typename function_argument<RightRef>::const_type r) const
   {
      return result_set(l,r);
   }

   template <typename Iterator2>
   typename function_argument<LeftRef>::const_type
   operator() (partial_left, typename function_argument<LeftRef>::const_type l, const Iterator2&) const
   {
      return l;
   }

   template <typename Iterator1>
   typename function_argument<RightRef>::const_type
   operator() (partial_right, const Iterator1&, typename function_argument<RightRef>::const_type r) const
   {
      return r;
   }

   typename function_argument<LeftRef>::lvalue
   assign(typename function_argument<LeftRef>::lvalue l,
	  typename function_argument<RightRef>::const_type r) const
   {
      return static_cast<typename function_argument<LeftRef>::lvalue> (l+=r);
   }
};

template <typename LeftRef, typename RightRef, bool check>
struct add_impl<LeftRef, RightRef, check, cons<is_set, is_scalar> > {
   typedef LeftRef first_argument_type;
   typedef RightRef second_argument_type;
   typedef typename deref<LeftRef>::type::element_comparator Comparator;
   typedef LazySet2<typename attrib<LeftRef>::plus_const, pm::masquerade2_keep_ref<SingleElementSetCmp, RightRef, Comparator>,
		    set_union_zipper>
      result_set;
   typedef const result_set result_type;

   result_type operator() (typename function_argument<LeftRef>::const_type l,
			   typename function_argument<RightRef>::const_type r) const
   {
      return result_set(l,r);
   }

   typename function_argument<LeftRef>::lvalue
   assign(typename function_argument<LeftRef>::lvalue l,
	  typename function_argument<RightRef>::const_type r) const
   {
      return static_cast<typename function_argument<LeftRef>::lvalue> (l+=r);
   }
};

template <typename LeftRef, typename RightRef, bool check>
struct add_impl<LeftRef, RightRef, check, cons<is_scalar, is_set> > {
   typedef LeftRef first_argument_type;
   typedef RightRef second_argument_type;
   typedef typename deref<RightRef>::type::element_comparator Comparator;
   typedef LazySet2<pm::masquerade2_keep_ref<SingleElementSetCmp, LeftRef, Comparator>, typename attrib<RightRef>::plus_const,
		    set_union_zipper>
      result_set;
   typedef const result_set result_type;

   result_type operator() (typename function_argument<LeftRef>::const_type l,
			   typename function_argument<RightRef>::const_type r) const
   {
      return result_set(l,r);
   }
};

template <typename LeftRef, typename RightRef, bool check>
struct sub_impl<LeftRef, RightRef, check, cons<is_set, is_set> > {
   typedef LeftRef first_argument_type;
   typedef RightRef second_argument_type;
   typedef LazySet2<typename attrib<LeftRef>::plus_const, typename attrib<RightRef>::plus_const, set_difference_zipper>
      result_set;
   typedef const result_set result_type;

   typedef Set<typename identical<typename deref<LeftRef>::type::element_type,
				  typename deref<RightRef>::type::element_type>::type,
	       typename identical<typename deref<LeftRef>::type::element_comparator,
				  typename deref<RightRef>::type::element_comparator>::type>
      _Set;

   result_type operator() (typename function_argument<LeftRef>::const_type l,
			   typename function_argument<RightRef>::const_type r) const {
      return result_set(l,r);
   }

   template <typename Iterator2>
   typename function_argument<LeftRef>::const_type
   operator() (partial_left, typename function_argument<LeftRef>::const_type l, const Iterator2&) const
   {
      return l;
   }

   template <typename Iterator1>
   _Set operator() (partial_right, const Iterator1&, typename function_argument<RightRef>::const_type) const
   {
      return _Set();
   }

   typename function_argument<LeftRef>::lvalue
   assign(typename function_argument<LeftRef>::lvalue l,
	  typename function_argument<RightRef>::const_type r) const
   {
      return static_cast<typename function_argument<LeftRef>::lvalue> (l-=r);
   }
};

template <typename LeftRef, typename RightRef, bool check>
struct sub_impl<LeftRef, RightRef, check, cons<is_set, is_scalar> > {
   typedef LeftRef first_argument_type;
   typedef RightRef second_argument_type;
   typedef typename deref<LeftRef>::type::element_comparator Comparator;
   typedef LazySet2<typename attrib<LeftRef>::plus_const, pm::masquerade2_keep_ref<SingleElementSetCmp, RightRef, Comparator>,
		    set_difference_zipper>
      result_set;

   typedef const result_set result_type;

   result_type operator() (typename function_argument<LeftRef>::const_type l,
			   typename function_argument<RightRef>::const_type r) const
   {
      return result_set(l,r);
   }

   typename function_argument<LeftRef>::lvalue
   assign(typename function_argument<LeftRef>::lvalue l,
	  typename function_argument<RightRef>::const_type r) const
   {
      return static_cast<typename function_argument<LeftRef>::lvalue> (l-=r);
   }
};

template <typename LeftRef, typename Right, bool check>
struct sub_impl<LeftRef, const Complement<Right>&, check, cons<is_set, is_set> > {
   typedef LeftRef first_argument_type;
   typedef const Complement<Right>& second_argument_type;
   typedef LazySet2<typename attrib<LeftRef>::plus_const, const Right&, set_intersection_zipper> result_set;
   typedef const result_set result_type;

   result_type operator() (typename function_argument<LeftRef>::const_type l,
			   second_argument_type r) const
   {
      return result_set(l,r.base());
   }

   typename function_argument<LeftRef>::lvalue
   assign(typename function_argument<LeftRef>::lvalue l, second_argument_type r) const
   {
      return static_cast<typename function_argument<LeftRef>::lvalue> (l-=r);
   }
};

template <typename LeftRef, typename RightRef, bool check>
struct mul_impl<LeftRef, RightRef, check, cons<is_set, is_set> > {
   typedef LeftRef first_argument_type;
   typedef RightRef second_argument_type;
   typedef LazySet2<typename attrib<LeftRef>::plus_const, typename attrib<RightRef>::plus_const, set_intersection_zipper>
      result_set;
   typedef const result_set result_type;

   result_type operator() (typename function_argument<LeftRef>::const_type l,
			   typename function_argument<RightRef>::const_type r) const
   {
      return result_set(l,r);
   }

   typename function_argument<LeftRef>::lvalue
   assign(typename function_argument<LeftRef>::lvalue l,
	  typename function_argument<RightRef>::const_type r) const
   {
      return static_cast<typename function_argument<LeftRef>::lvalue> (l*=r);
   }
};

template <typename LeftRef, typename RightRef, bool check>
struct mul_impl<LeftRef, RightRef, check, cons<is_set, is_scalar> > {
   typedef LeftRef first_argument_type;
   typedef RightRef second_argument_type;
   typedef typename deref<LeftRef>::type::element_comparator Comparator;
   typedef LazySet2<typename attrib<LeftRef>::plus_const, pm::masquerade2_keep_ref<SingleElementSetCmp, RightRef, Comparator>,
		    set_intersection_zipper>
      result_set;
   typedef const result_set result_type;

   result_type operator() (typename function_argument<LeftRef>::const_type l,
			   typename function_argument<RightRef>::const_type r) const
   {
      return result_set(l,r);
   }
};

template <typename LeftRef, typename RightRef, bool check>
struct mul_impl<LeftRef, RightRef, check, cons<is_scalar, is_set> > {
   typedef LeftRef first_argument_type;
   typedef RightRef second_argument_type;
   typedef typename deref<RightRef>::type::element_comparator Comparator;
   typedef LazySet2<pm::masquerade2_keep_ref<SingleElementSetCmp, LeftRef, Comparator>, typename attrib<RightRef>::plus_const,
		    set_intersection_zipper>
      result_set;
   typedef const result_set result_type;

   result_type operator() (typename function_argument<LeftRef>::const_type l,
			   typename function_argument<RightRef>::const_type r) const
   {
      return result_set(l,r);
   }
};

template <typename LeftRef, typename Right, bool check>
struct mul_impl<LeftRef, const Complement<Right>&, check, cons<is_set, is_set> > {
   typedef LeftRef first_argument_type;
   typedef const Complement<Right>& second_argument_type;
   typedef LazySet2<typename attrib<LeftRef>::plus_const, const Right&, set_difference_zipper> result_set;
   typedef const result_set result_type;

   result_type operator() (typename function_argument<LeftRef>::const_type l, second_argument_type r) const
   {
      return result_set(l,r.base());
   }

   typename function_argument<LeftRef>::lvalue
   assign(typename function_argument<LeftRef>::lvalue l, second_argument_type r) const
   {
      return static_cast<typename function_argument<LeftRef>::lvalue> (l*=r);
   }
};

template <typename Left, typename RightRef, bool check>
struct mul_impl<const Complement<Left>&, RightRef, check, cons<is_set, is_set> > {
   typedef const Complement<Left>& first_argument_type;
   typedef RightRef second_argument_type;
   typedef LazySet2<const Left&, typename attrib<RightRef>::plus_const, set_difference_zipper> result_set;
   typedef const result_set result_type;

   result_type operator() (first_argument_type l,
			   typename function_argument<RightRef>::const_type r) const
   {
      return result_set(l.base(),r);
   }
};

template <typename LeftRef, typename RightRef, bool check>
struct bitwise_xor_impl<LeftRef, RightRef, check, cons<is_set, is_set> > {
   typedef LeftRef first_argument_type;
   typedef RightRef second_argument_type;
   typedef LazySet2<typename attrib<LeftRef>::plus_const, typename attrib<RightRef>::plus_const,
		    set_symdifference_zipper>
      result_set;
   typedef const result_set result_type;

   result_type operator() (typename function_argument<LeftRef>::const_type l,
			   typename function_argument<RightRef>::const_type r) const
   {
      return result_set(l,r);
   }

   template <typename Iterator2>
   typename function_argument<LeftRef>::const_type
   operator() (partial_left, typename function_argument<LeftRef>::const_type l, const Iterator2&) const
   {
      return l;
   }

   template <typename Iterator1>
   typename function_argument<RightRef>::const_type
   operator() (partial_right, const Iterator1&, typename function_argument<RightRef>::const_type r) const
   {
      return r;
   }

   typename function_argument<LeftRef>::lvalue
   assign(typename function_argument<LeftRef>::lvalue l,
	  typename function_argument<RightRef>::const_type r) const
   {
      return static_cast<typename function_argument<LeftRef>::lvalue> (l^=r);
   }
};

template <typename LeftRef, typename RightRef, bool check>
struct bitwise_xor_impl<LeftRef, RightRef, check, cons<is_set, is_scalar> > {
   typedef LeftRef first_argument_type;
   typedef RightRef second_argument_type;
   typedef typename deref<LeftRef>::type::element_comparator Comparator;
   typedef LazySet2<typename attrib<LeftRef>::plus_const, pm::masquerade2_keep_ref<SingleElementSetCmp, RightRef, Comparator>,
		    set_symdifference_zipper>
      result_set;
   typedef const result_set result_type;

   result_type operator() (typename function_argument<LeftRef>::const_type l,
			   typename function_argument<RightRef>::const_type r) const
   {
      return result_set(l,r);
   }

   typename function_argument<LeftRef>::lvalue
   assign(typename function_argument<LeftRef>::lvalue l,
	  typename function_argument<RightRef>::const_type r) const
   {
      return static_cast<typename function_argument<LeftRef>::lvalue> (l^=r);
   }
};

template <typename LeftRef, typename RightRef, bool check>
struct bitwise_xor_impl<LeftRef, RightRef, check, cons<is_scalar, is_set> > {
   typedef LeftRef first_argument_type;
   typedef RightRef second_argument_type;
   typedef typename deref<RightRef>::type::element_comparator Comparator;
   typedef LazySet2<pm::masquerade2_keep_ref<SingleElementSetCmp, LeftRef, Comparator>, typename attrib<RightRef>::plus_const,
		    set_symdifference_zipper>
      result_set;
   typedef const result_set result_type;

   result_type operator() (typename function_argument<LeftRef>::const_type l,
			   typename function_argument<RightRef>::const_type r) const
   {
      return result_set(l,r);
   }
};

template <typename LeftRef, typename RightRef>
struct includes {
   typedef LeftRef first_argument_type;
   typedef RightRef second_argument_type;
   typedef bool result_type;

   result_type operator() (typename function_argument<LeftRef>::const_type s1,
			   typename function_argument<RightRef>::const_type s2) const
   {
      return incl(s2,s1)<1;
   }
};

template <typename SetRef>
class element_of {
   alias<SetRef> set;
public:
   typedef typename deref<SetRef>::type set_type;
   typedef typename set_type::element_type argument_type;
   typedef bool result_type;

   element_of(typename alias<SetRef>::arg_type set_arg) : set(set_arg) { }

   result_type operator() (typename function_argument<argument_type>::type x) const
   {
      return static_cast<const set_type&>(set).contains(x);
   }
};

} // end namespace operations
namespace operators {

template <typename Set1, typename Set2> inline
typename operations::add_impl<const Set1&, const Set2&, true>::result_type
operator+ (const GenericSet<Set1>& l, const GenericSet<Set2>& r)
{
   operations::add_impl<const Set1&, const Set2&, true> op;
   return op(l.top(), r.top());
}

template <typename Set1, typename E> inline
typename operations::add_impl<const Set1&, const E&, true>::result_type
operator+ (const GenericSet<Set1,E>& l, const E& r)
{
   operations::add_impl<const Set1&, const E&, true> op;
   return op(l.top(), r);
}

template <typename E, typename Set2> inline
typename operations::add_impl<const E&, const Set2&, true>::result_type
operator+ (const E& l, const GenericSet<Set2,E>& r)
{
   operations::add_impl<const E&, const Set2&, true> op;
   return op(l, r.top());
}

template <typename Set1, typename Set2> inline
typename operations::sub_impl<const Set1&, const Set2&, true>::result_type
operator- (const GenericSet<Set1>& l, const GenericSet<Set2>& r)
{
   operations::sub_impl<const Set1&, const Set2&, true> op;
   return op(l.top(), r.top());
}

template <typename Set1, typename E> inline
typename operations::sub_impl<const Set1&, const E&, true>::result_type
operator- (const GenericSet<Set1,E>& l, const E& r)
{
   operations::sub_impl<const Set1&, const E&, true> op;
   return op(l.top(), r);
}

template <typename Set1, typename Set2> inline
typename operations::sub_impl<const Set1&, const Set2&, true>::result_type
operator- (const GenericSet<Set1>& l, const Complement<Set2>& r)
{
   operations::sub_impl<const Set1&, const Set2&, true> op;
   return op(l.top(), r);
}

template <typename Set1, typename Set2> inline
bool operator== (const GenericSet<Set1>& l, const GenericSet<Set2>& r)
{
   operations::eq<const Set1&, const Set2&> cmp_op;
   return cmp_op(l.top(), r.top());
}

template <typename Set1, typename Set2> inline
bool operator< (const GenericSet<Set1>& l, const GenericSet<Set2>& r)
{
   operations::lt<const Set1&, const Set2&> cmp_op;
   return cmp_op(l.top(), r.top());
}

} // end namespace operators

template <typename _Set1, typename _Set2, bool _both_have_size=
          (iterator_traits<typename _Set1::iterator>::is_bidirectional &&
	   iterator_traits<typename _Set2::iterator>::is_bidirectional)>
struct size_estimator {
   /** Estimates how the insertion or removal of a sequence of elements could be made faster.
       Returns true if \\n2*log(n1) < n1+n2\\, which means that seeking for each element of set2
       in set1 would be faster than sequentially comparing element pairs from set1 and set2.
   */
   static bool seek_cheaper_than_sequential(const _Set1& set1, const _Set2& set2) {
      const int n1=set1.size(), n2=set2.size();
      return n2==0 || set1.tree_form() && ( n1/n2>=31 || (1<<(n1/n2))>n1 );
   }

   static int compare(const _Set1& set1, const _Set2& set2) {
      return sign(set1.size()-set2.size());
   }
};

template <typename _Set1, typename _Set2>
struct size_estimator<_Set1,_Set2,false> {
   static bool seek_cheaper_than_sequential(const _Set1&, const _Set2&) { return true; }
   static int compare(const _Set1&, const _Set2&) { return 0; }
};

/** Analyze the inclusion relation of two sets.
    @returnval  0 $s1$ and $s2$ are equal
    @returnval -1 $s1$ is included in $s2$
    @returnval  1 $s2$ is included in $s1$
    @returnval  2 $s1$ and $s2$ are independent
*/
template <typename _Set1, typename _Set2, typename E1, typename E2, class Comparator>
int incl(const GenericSet<_Set1,E1,Comparator>& s1, const GenericSet<_Set2,E2,Comparator>& s2)
{
   typename _Set1::template comparator_for_pair<_Set2>::type
      cmp_op=s2.get_comparator_for(s2);
   typename Entire<_Set1>::const_iterator e1=entire(s1);
   typename Entire<_Set2>::const_iterator e2=entire(s2);
   int result = size_estimator<_Set1,_Set2>::compare(s1.top(),s2.top());
   while (!e1.at_end() && !e2.at_end()) {
      switch (cmp_op(*e2,*e1)) {
      case cmp_eq: ++e1; ++e2; break;
      case cmp_lt:
	 if (result>0) return 2;
	 result=-1;
	 ++e2;
	 break;
      case cmp_gt:
	 if (result<0) return 2;
	 result=1;
	 ++e1;
	 break;
      }
   }
   if ((!e1.at_end() && result<0) || (!e2.at_end() && result>0)) return 2;
   return result;
}

template <typename Container, typename Comparator=operations::cmp<>, typename ProvidedFeatures=void>
class OrderedContainer
   : public redirected_container< OrderedContainer<Container,Comparator,ProvidedFeatures>,
				  list( Hidden< Container >,
					ExpectedFeatures< ProvidedFeatures > ) >,
     public GenericSet< OrderedContainer<Container,Comparator,ProvidedFeatures>,
                        typename object_traits<typename Container::value_type>::persistent_type,
		        Comparator > { };

template <typename Container, typename Comparator, typename ProvidedFeatures, typename Feature>
struct enforce_features<OrderedContainer<Container, Comparator, ProvidedFeatures>, Feature> {
   typedef OrderedContainer<Container, Comparator, typename mix_features<ProvidedFeatures, Feature>::type> container;
};

template <typename Container> inline
const OrderedContainer<Container>&
assure_ordered(const Container& c)
{
   return reinterpret_cast<const OrderedContainer<Container>&>(c);
}

template <typename Comparator, typename Container> inline
const OrderedContainer<Container, Comparator>&
assure_ordered(const Container& c)
{
   return reinterpret_cast<const OrderedContainer<Container, Comparator>&>(c);
}

template <typename Container>
class Indices
   : public modified_container_impl< Indices<Container>,
				     list( Hidden< typename deref<Container>::minus_ref >,
					   Operation< BuildUnaryIt<operations::index2element> >,
					   ExpectedFeatures< indexed > ) >,
     public GenericSet< Indices<Container>, int, operations::cmp<> > {
protected:
   ~Indices();
};

template <typename Container> inline
const Indices<Container>&
indices(const Container& c)
{
   return reinterpret_cast<const Indices<Container>&>(c);
}

} // end namespace pm

namespace polymake {
   using pm::GenericSet;
   using pm::scalar2set;
   using pm::assure_ordered;
   using pm::Indices;
   using pm::indices;

   namespace operations {
      typedef BuildBinary<pm::operations::includes> includes;

      template <typename _Set> inline
      pm::operations::element_of<const _Set&> element_of(const _Set& s) { return s; }
   }
}

namespace std_ext {
   template <typename T> struct hash;

   template <typename E, typename Comparator>
   struct hash< pm::Set<E,Comparator> > {
      template <typename _Set>
      size_t operator() (const pm::GenericSet<_Set,E,Comparator>& s) const {
	 hash<E> element_hasher;
	 size_t a=1, b=0;
	 for (typename pm::Entire<_Set>::const_iterator e=entire(s); !e.at_end(); ++e)
	    a=a*element_hasher(*e)+b;
	 return a;
      }
   };
}

#endif // _POLYMAKE_GENERIC_SET_H

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