/* 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_SET_H
#define _POLYMAKE_SET_H "$Project: polymake $$Id: Set.h,v 1.45 2004/09/20 14:26:39 gawrilow Exp $"

#ifndef _POLYMAKE_AVL_H
#  include <AVL.h>
#endif
#ifndef _POLYMAKE_TREE_CONTAINERS_H
#  include <tree_containers.h>
#endif
#ifndef _POLYMAKE_SHARED_OBJECT_H
#  include <shared_object.h>
#endif
#ifndef _POLYMAKE_CONVERTERS_H
#  include <converters.h>
#endif
#ifndef _POLYMAKE_INDEXED_SUBSET_H
#  include <IndexedSubset.h>
#endif

namespace pm {

template <typename _Set, typename E=typename _Set::element_type, typename Comparator=typename _Set::element_comparator>
class GenericMutableSet : public GenericSet<_Set,E,Comparator> {
protected:
   GenericMutableSet() { }
   GenericMutableSet(const GenericMutableSet&) { }
   typedef GenericMutableSet generic_mutable_type;
protected:
   template <typename Set2, typename E2>
   void _plus_seek(const GenericSet<Set2,E2,Comparator>& s)
   {
      for (typename Entire<Set2>::const_iterator e2=entire(s); !e2.at_end(); ++e2)
	 this->top().insert(*e2);
   }

   template <typename Set2, typename E2>
   void _plus_seq(const GenericSet<Set2,E2,Comparator>& s)
   {
      typedef binary_op_builder<Comparator, typename Entire<_Set>::iterator, typename Entire<Set2>::const_iterator> cmpb;
      const typename cmpb::operation& cmp=cmpb::create(this->top().get_comparator());
      typename Entire<_Set>::iterator e1=entire(this->top());
      typename Entire<Set2>::const_iterator e2=entire(s);
      while (!e1.at_end() && !e2.at_end()) {
	 switch (cmp(*e1,*e2)) {
	 case cmp_eq: ++e2;
	 case cmp_lt: ++e1; break;
	 case cmp_gt: this->top().insert(e1,*e2); ++e2;
	 }
      }
      for (; !e2.at_end(); ++e2) this->top().insert(e1,*e2);
   }

   template <typename Set2, typename E2>
   void _plus(const GenericSet<Set2,E2,Comparator>& s, cons<is_set, is_set>*, True*)
   {
      if (size_estimator<_Set,Set2>::seek_cheaper_than_sequential(this->top(),s.top()))
	 _plus_seek(s);
      else
	 _plus_seq(s);
   }

   template <typename Set2, typename E2>
   void _plus(const GenericSet<Set2,E2,Comparator>& s, cons<is_set, is_set>*, False*)
   {
      _plus_seq(s);
   }

   template <typename Right>
   void _plus(const Right& x, cons<is_set, is_scalar>*, True*)
   {
      this->top().insert(x);
   }

   template <typename Right>
   void _plus(const Right& x, cons<is_set, is_scalar>*, False*)
   {
      _plus_seq(scalar2set(x));
   }

   template <typename Set2, typename E2>
   void _minus_seek(const GenericSet<Set2,E2,Comparator>& s)
   {
      for (typename Entire<Set2>::const_iterator e2=entire(s); !e2.at_end(); ++e2)
	 this->top().erase(*e2);
   }

   template <typename Set2, typename E2>
   void _minus_seq(const GenericSet<Set2,E2,Comparator>& s)
   {
      typedef binary_op_builder<Comparator, typename Entire<_Set>::iterator, typename Entire<Set2>::const_iterator> cmpb;
      const typename cmpb::operation& cmp=cmpb::create(this->top().get_comparator());
      typename Entire<_Set>::iterator e1=entire(this->top());
      typename Entire<Set2>::const_iterator e2=entire(s);
      while (!e1.at_end() && !e2.at_end()) {
	 switch (cmp(*e1,*e2)) {
	 case cmp_lt: ++e1; break;
	 case cmp_eq: this->top().erase(e1++);
	 case cmp_gt: ++e2;
	 }
      }
   }

   template <typename Set2, typename E2>
   void _minus(const GenericSet<Set2,E2,Comparator>& s, cons<is_set, is_set>*, True*)
   {
      if (size_estimator<_Set,Set2>::seek_cheaper_than_sequential(this->top(),s.top()))
	 _minus_seek(s);
      else
	 _minus_seq(s);
   }

   template <typename Set2, typename E2>
   void _minus(const GenericSet<Set2,E2,Comparator>& s, cons<is_set, is_set>*, False*)
   {
      _minus_seq(s);
   }

   template <typename Set2, typename E2>
   void _minus(const Complement<Set2,E2,Comparator>& s,
	       cons<is_set, is_set>*, void*)
   {
      return *this *= s.top();
   }

   template <typename Right>
   void _minus(const Right& x, cons<is_set, is_scalar>*, True*)
   {
      this->top().erase(x);
   }

   template <typename Right>
   void _minus(const Right& x, cons<is_set, is_scalar>*, False*)
   {
      _minus_seq(scalar2set(x));
   }

   template <typename Set2, typename E2>
   void _xor_seek(const GenericSet<Set2,E2,Comparator>& s)
   {
      for (typename Entire<Set2>::const_iterator e2=entire(s); !e2.at_end(); ++e2)
	 this->top().toggle(*e2);
   }

   template <typename Set2, typename E2>
   void _xor_seq(const GenericSet<Set2,E2,Comparator>& s)
   {
      typedef binary_op_builder<Comparator, typename Entire<_Set>::iterator, typename Entire<Set2>::const_iterator> cmpb;
      const typename cmpb::operation& cmp=cmpb::create(this->top().get_comparator());
      typename Entire<_Set>::iterator e1=entire(this->top());
      typename Entire<Set2>::const_iterator e2=entire(s);
      while (!e1.at_end() && !e2.at_end()) {
	 switch (cmp(*e1,*e2)) {
	 case cmp_lt:  ++e1;  break;
	 case cmp_eq: this->top().erase(e1++);  ++e2;  break;
	 case cmp_gt: this->top().insert(e1,*e2);  ++e2;
	 }
      }
      for (; !e2.at_end(); ++e2) this->top().insert(e1,*e2);
   }

   template <typename Set2, typename E2>
   void _xor(const GenericSet<Set2,E2,Comparator>& s, cons<is_set, is_set>*, True*)
   {
      if (size_estimator<_Set,Set2>::seek_cheaper_than_sequential(this->top(),s.top()))
	 _xor_seek(s);
      else
	 _xor_seq(s);
   }

   template <typename Set2, typename E2>
   void _xor(const GenericSet<Set2,E2,Comparator>& s, cons<is_set, is_set>*, False*)
   {
      _xor_seq(s);
   }

   template <typename Right>
   void _xor(const Right& x, cons<is_set, is_scalar>*, True*)
   {
      this->top().toggle(x);
   }

   template <typename Right>
   void _xor(const Right& x, cons<is_set, is_scalar>*, False*)
   {
      _xor_seq(scalar2set(x));
   }

   template <typename Set2, typename E2>
   bool trivial_assignment(const GenericSet<Set2,E2,Comparator>&) const { return false; }

   bool trivial_assignment(const GenericMutableSet& s) const { return this==&s; }

   template <typename Set2, typename E2, typename DiffConsumer>
   void assign(const GenericSet<Set2,E2,Comparator>& s, DiffConsumer diff)
   {
      typedef binary_op_builder<Comparator, typename Entire<_Set>::iterator, typename Entire<Set2>::const_iterator> cmpb;
      const typename cmpb::operation& cmp=cmpb::create(this->top().get_comparator());
      typename Entire<_Set>::iterator dst=entire(this->top());
      typename Entire<Set2>::const_iterator src=entire(s);
      int state=(dst.at_end() ? 0 : zipper_first) + (src.at_end() ? 0 : zipper_second);
      while (state >= zipper_both) {
	 switch (cmp(*dst,*src)) {
	 case cmp_lt:
	    *diff++=*dst;  this->top().erase(dst++);
	    if (dst.at_end()) state -= zipper_first;
	    break;
	 case cmp_eq:
	    ++dst;
	    if (dst.at_end()) state -= zipper_first;
	    ++src;
	    if (src.at_end()) state -= zipper_second;
	    break;
	 case cmp_gt:
	    *diff++=*src;  this->top().insert(dst, *src);  ++src;
	    if (src.at_end()) state -= zipper_second;
	 }
      }
      if (state & zipper_first) {
	 do {
	    *diff++=*dst;  this->top().erase(dst++);
	 }
	 while (!dst.at_end());
      } else if (state) {
	 do {
	    *diff++=*src;  this->top().insert(dst, *src);  ++src;
	 } while (!src.at_end());
      }
   }

   template <typename Set2, typename E2>
   void assign(const GenericSet<Set2,E2,Comparator>& s)
   {
      assign(s, black_hole<E>());
   }

public:
   _Set& operator= (const GenericMutableSet& s)
   {
      if (!this->trivial_assignment(s)) this->top().assign(s);
      return this->top();
   }

   template <typename Set2, typename E2>
   _Set& operator= (const GenericSet<Set2,E2,Comparator>& s)
   {
      this->top().assign(s);
      return this->top();
   }

   template <typename Set2>
   void swap(GenericMutableSet<Set2,E,Comparator>& s)
   {
      if (trivial_assignment(s)) return;
      typedef binary_op_builder<Comparator, typename Entire<_Set>::iterator, typename Entire<Set2>::iterator> cmpb;
      const typename cmpb::operation& cmp=cmpb::create(this->top().get_comparator());
      typename Entire<_Set>::iterator e1=entire(this->top());
      typename Entire<Set2>::iterator e2=entire(s);
      int state=(e1.at_end() ? 0 : zipper_first) + (e2.at_end() ? 0 : zipper_second);
      while (state >= zipper_both) {
	 switch (cmp(*e1,*e2)) {
	 case cmp_lt:
	    s.top().insert(e2, e1.index());
	    this->top().erase(e1++);
	    if (e1.at_end()) state -= zipper_first;
	    break;
	 case cmp_gt:
	    this->top().insert(e1, e2.index());
	    s.top().erase(e2++);
	    if (e2.at_end()) state -= zipper_second;
	    break;
	 case cmp_eq:
	    ++e1;
	    if (e1.at_end()) state -= zipper_first;
	    ++e2;
	    if (e2.at_end()) state -= zipper_second;
	 }
      }
      if (state & zipper_first) {
	 do {
	    s.top().insert(e2, e1.index());
	    this->top().erase(e1++);
	 } while (!e1.at_end());
      } else if (state) {
	 do {
	    this->top().insert(e1, e2.index());
	    s.top().erase(e2++);
	 } while (!e2.at_end());
      }
   }

   template <typename Right>
   _Set& operator+= (const Right& x)
   {
      _plus(x, (typename isomorphic<_Set,Right>::discriminant*)0,
	    (bool2type<derived_from_instance2<_Set,modified_tree>::answer>*)0);
      return this->top();
   }

   template <typename Right>
   _Set& operator-= (const Right& x)
   {
      _minus(x, (typename isomorphic<_Set,Right>::discriminant*)0,
	     (bool2type<derived_from_instance2<_Set,modified_tree>::answer>*)0);
      return this->top();
   }

   /// intersection
   template <typename Set2, typename E2>
   _Set& operator*= (const GenericSet<Set2,E2,Comparator>& s)
   {
      typedef binary_op_builder<Comparator, typename Entire<_Set>::iterator, typename Entire<Set2>::const_iterator> cmpb;
      const typename cmpb::operation& cmp=cmpb::create(this->top().get_comparator());
      typename Entire<_Set>::iterator e1=entire(this->top());
      typename Entire<Set2>::const_iterator e2=entire(s);
      while (!e1.at_end() && !e2.at_end()) {
	 switch (cmp(*e1,*e2)) {
	 case cmp_lt: this->top().erase(e1++); break;
	 case cmp_eq: ++e1;
	 case cmp_gt: ++e2;
	 }
      }
      while (!e1.at_end()) this->top().erase(e1++);
      return this->top();
   }

   template <typename Set2, typename E2>
   _Set& operator *= (const Complement<Set2,E2,Comparator>& s)
   {
      return *this -= s.top();
   }

   /// symmetrical difference
   template <typename Right>
   _Set& operator^= (const Right& x)
   {
      _xor(x, (typename isomorphic<_Set,Right>::discriminant*)0,
	   (bool2type<derived_from_instance2<_Set,modified_tree>::answer>*)0);
      return this->top();
   }

   /// compute the symmetrical difference and make *this equal to s
   template <typename Set2, typename E2>
   Set<E, Comparator> extract_symdif(const GenericSet<Set2,E2,Comparator>& s)
   {
      Set<E, Comparator> result;
      assign(s, std::back_inserter(result));
      return result;
   }

   template <typename Result>
   struct construct_generic {
      typedef GenericMutableSet<Result, E, Comparator> type;
   };

}; // end class GenericMutableSet

template <typename E, typename Comparator>
class Set
   : public modified_tree< Set<E,Comparator>,
               cons< Container< AVL::tree< AVL::traits<E,nothing,Comparator> > >,
                     Accessor< BuildUnary<AVL::node_accessor> > >
            >,
     public GenericMutableSet< Set<E,Comparator>, E, Comparator > {
   typedef modified_tree<Set> _super;
protected:
   typedef AVL::tree< AVL::traits<E,nothing,Comparator> > tree_type;
   shared_object<tree_type> tree;

public:
   tree_type& get_container() { return *tree; }
   const tree_type& get_container() const { return *tree; }
   const Comparator& get_comparator() const { return tree->get_comparator(); }

   /// An empty set.
   Set() { }

   explicit Set(const Comparator& cmp_arg)
      : tree( make_constructor(cmp_arg, (tree_type*)0) ) { }

   template <typename Iterator>
   Set(Iterator src, Iterator end)
      : tree( make_constructor(src, end, (tree_type*)0) ) { }

   template <typename Iterator>
   Set(Iterator src, end_sensitive)
      : tree( make_constructor(src, end_sensitive(), (tree_type*)0) ) { }

   /// Copy of a disguised Set object.
   Set(const GenericSet<Set,E,Comparator>& s)
      : tree(s.top().tree) { }

   /// Copy of an abstract set of the same element type.
   template <typename Set2>
   Set(const GenericSet<Set2,E,Comparator>& s)
      : tree( make_constructor(entire(s), end_sensitive(), (tree_type*)0) ) { }

   /// Copy of an abstract set with element conversion.
   template <typename Set2, typename E2, typename Comparator2>
   explicit Set(const GenericSet<Set2,E2,Comparator2>& s)
      : tree( make_constructor(entire(attach_converter<E>(s)), end_sensitive(), (tree_type*)0) ) { }

   template <int _size>
   explicit Set(const E (&s)[_size])
      : tree( make_constructor(entire(array2container(s)), end_sensitive(), (tree_type*)0) ) { }

   Set& operator= (const Set& s) { assign(s); return *this; }

   /// Assign elements from a disguised Set object.
   Set& operator= (const GenericSet<Set,E,Comparator>& s) { return *this=s.top(); }

   using Set::generic_mutable_type::operator=;

   void clear() { tree.clear(); }

   void swap(Set& s) { tree.swap(s.tree); }

   friend void relocate(Set* from, Set* to)
   {
      pm::relocate(&from->tree, &to->tree);
   }

#ifdef POLY_DEBUG
   void check(const char* label) const { tree->check(label); }
   void dump() const { tree->dump(); }
#endif

   bool contains(typename function_argument<E>::type k) const { return exists(k); }

   template <typename Set2>
   Set& select(const GenericSet<Set2>& selector)
   {
      if (tree.is_shared()) {
	 Set copy(entire(pm::select(const_cast<const Set&>(*this), selector.top())), end_sensitive());
	 *this=copy;
      } else {
	 typename Entire<Set>::iterator e1=entire(*this);
	 typename Set2::element_type cur(0);
	 for (typename Entire<Set2>::const_iterator s=entire(selector); !s.at_end(); ++s) {
	    for (; cur < *s; ++cur) erase(e1++);
	    ++e1; ++cur;
	 }
	 while (!e1.at_end()) erase(e1++);
      }
      return *this;
   }

   template <typename Set2>
   Set& select(const Complement<Set2>& selector)
   {
      if (tree.is_shared()) {
	 Set copy(entire(pm::select(const_cast<const Set&>(*this), selector)), end_sensitive());
	 *this=copy;
      } else {
	 typename Entire<Set>::iterator e1=entire(*this);
	 typename Set2::element_type cur(0);
	 for (typename Entire<Set2>::const_iterator s=entire(selector.top()); !s.at_end(); ++s) {
	    for (; cur < *s; ++cur) ++e1;
	    erase(e1++); ++cur;
	 }
      }
      return *this;
   }

protected:
   friend class alias_to_shared<Set>;
   friend class GenericMutableSet<Set<E,Comparator>, E, Comparator>;

   void assign(const GenericSet<Set>& s) { tree=s.top().tree; }

   template <typename Set2, typename E2>
   void assign(const GenericSet<Set2,E2,Comparator>& s)
   {
      if (tree.is_shared()) {
	 assign(Set(s));
      } else {
	 tree->assign(entire(s));
      }
   }

   const shared_object<tree_type>& data_member() const { return tree; }
};

template <typename E, typename Comparator>
class alias_ptr< Set<E,Comparator> > : public alias_to_shared< Set<E,Comparator> > {
public:
   alias_ptr(const Set<E,Comparator>* ptr_arg) : alias_to_shared< Set<E,Comparator> >(ptr_arg) { }
};

} // end namespace pm

namespace polymake {
   using pm::Set;
}

namespace std {
   template <typename Set1, typename Set2, typename E, typename Comparator> inline
   void swap(pm::GenericMutableSet<Set1,E,Comparator>& s1, pm::GenericMutableSet<Set2,E,Comparator>& s2) {
      s1.top().swap(s2.top());
   }

   template <typename Set1, typename Set2, typename E, typename Comparator> inline
   void swap(const pm::GenericMutableSet<Set1,E,Comparator>& s1, const pm::GenericMutableSet<Set2,E,Comparator>& s2) {
      pm::non_const(s1.top()).swap(pm::non_const(s2.top()));
   }

   template <typename E, typename Comparator> inline
   void swap(pm::Set<E,Comparator>& s1, pm::Set<E,Comparator>& s2) { s1.swap(s2); }
}

#endif // _POLYMAKE_SET_H

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