/* Copyright (c) 1997-2005
   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_EQUIVALENCE_RELATION_H
#define _POLYMAKE_EQUIVALENCE_RELATION_H

#include <Array.h>
#include <PowerSet.h>
#include <GenericIO.h>

#include <list>
#include <ext/hash_set>
#include <ext/hash_map>

namespace pm {

class EquivalenceRelation {

protected:
   Array<int> equiv_classes;
   std_ext::hash_set<int> set_rep; 
   Set<int> the_representatives;
   std::list<int> erased_rep;
   mutable bool dirty;

public:
   EquivalenceRelation() { }

   explicit EquivalenceRelation(const int size)
      : equiv_classes(size,sequence(0,size).begin()),
	the_representatives(sequence(0,size)),
	dirty(false) { }

   template <typename Container>
   EquivalenceRelation(const int size, const Container& represent)
      : equiv_classes(size,sequence(0,size).begin()),
	the_representatives(sequence(0,size)),
	dirty(true)
   {
      for (typename Entire<Container>::const_iterator v=entire(represent);
	   !v.at_end(); ++v)
	 set_rep.insert(*v);
   }

protected:
   template <typename Set>
   void add_class(const GenericSet<Set, int>& the_class)
   {
      if (the_class.top().empty()) return;
      const int highest=the_class.top().back();
      if (equiv_classes.size() <= highest)
	 equiv_classes.resize(highest+1, -1);
      const int the_rep=the_class.top().front();
      the_representatives += the_rep;
      for (typename Entire<Set>::const_iterator el=entire(the_class); !el.at_end(); ++el)
	 equiv_classes[*el]=the_rep;
   }

public:
   void clear()
   {
      if (!equiv_classes.empty()) {
	 equiv_classes.clear();
	 set_rep.clear();
	 the_representatives.clear();
	 erased_rep.clear();
	 dirty=false;
      }
   }

   // the representative of the equiv. class of the element e
   int representative(const int e) const
   {
#ifdef POLY_DEBUG
      INDEX_CHECK((e>=equiv_classes.size()), "EquivalenceRelation: Index out of range");
#endif

      if (e == equiv_classes[e])
	 return e;

      int root = e;
      std::list<int> update_root;
      for ( ; equiv_classes[root]!=root; root=equiv_classes[root])
	 update_root.push_back(root);

      while (!update_root.empty()) {
	 const_cast<Array<int>&>(equiv_classes)[update_root.front()] = root;  // keeping the representation neat
	 update_root.pop_front();
      }

      return root;
   }

   // ensures, that the pointer of each element points directly to its representative  
   void squeeze() const
   {
      for (int i=0; i<equiv_classes.size(); ++i)
	 representative(i);
      dirty=false;
   }
   
   // returns for each element the representative of its equiv. class
   const Array<int>& representatives() const
   {
      if (dirty) squeeze();
      return equiv_classes;
   }
   
   // merges two equiv classes each represented by one (arbitrary) of its elements
   void merge_classes(const int c1, const int c2)
   {
      int root1 = representative(c1);
      int root2 = representative(c2);
      if (root1 == root2) return;
      if (root1 > root2) std::swap(root1, root2);

      if (set_rep.find(root2)!=set_rep.end() && set_rep.find(root1)==set_rep.end()) {
	 equiv_classes[root1] = root2;
	 erased_rep.push_back(root1);
      } else {
	 equiv_classes[root2] = root1;
	 erased_rep.push_back(root2);
      }
      dirty=true;
   }
   
   // merges the classes of all the elements contained in classes
   template <typename Container>
   void merge_classes(const Container& classes)
   {
      typename Entire<Container>::const_iterator c=entire(classes);
      if (!c.at_end()) {
	 const int c0=*c;
	 for (++c; !c.at_end(); ++c)
	    merge_classes(c0,*c);
      }
   }

   // lazy: erased representatives are collected and only erased when required
   void update_rep()
   {
      while (!erased_rep.empty()) {
	 the_representatives -= erased_rep.front();
	 erased_rep.pop_front();
      }
   }

   // the set of all representatives
   const Set<int>& set_of_rep() const
   {
      const_cast<EquivalenceRelation*>(this)->update_rep();
      return the_representatives;
   }

   // return the equiv class of the element e
   Set<int> equivalence_class(const int e) const
   {
      Set<int> class_of_e;
      const int rep = representative(e);

      for (int i=0; i<equiv_classes.size(); ++i)
	 if (rep == representative(i))
	    class_of_e += i;

      return class_of_e;
   }

   // returns all equivalence classes
   PowerSet<int> equivalence_classes() const
   {
      PowerSet<int> classes;
      std_ext::hash_map< int,Set<int> > rep_map;

      for (int i=0, n=equiv_classes.size(); i<n; ++i)
	 rep_map[representative(i)] += i;

      for (Entire< std_ext::hash_map< int,Set<int> > >::const_iterator cl=entire(rep_map);
	   !cl.at_end(); ++cl)
	 classes += cl->second;

      dirty=false;
      return classes;
   }

   // returns true iff e1 and e2 are in the same equiv. class
   bool related(const int e1, const int e2) const
   {
      return representative(e1)==representative(e2);
   }
   
   // the element e will be used as representative of it's equiv. class
   void set_representative(const int e)
   {
      set_rep.insert(e);
      const int root = representative(e);

      if (root!=e) {  // adjust representatives
	 equiv_classes[root] = e;
	 equiv_classes[e] = e;
	 update_rep();
	 the_representatives -= root;
	 the_representatives += e;
	 dirty=true;
      }
   }

   template <typename Input>
   friend Input& operator>> (GenericInput<Input>& is, EquivalenceRelation& me)
   {
      PowerSet<int> classes;
      is.top() >> classes;
      me.clear();
      for (Entire< PowerSet<int> >::const_iterator cl=entire(classes); !cl.at_end(); ++cl)
	 me.add_class(*cl);
      return is.top();
   }
};

template <>
struct spec_object_traits< EquivalenceRelation >
   : spec_object_traits<is_container> {
   typedef PowerSet<int> serialized;

   static serialized serialize(const EquivalenceRelation& ER)
   {
      return ER.equivalence_classes();
   }
};

} // end namespace pm

namespace polymake {
   using pm::EquivalenceRelation;
}

#endif // _POLYMAKE_EQUIVALENCE_RELATION_H


// Local Variables:
// mode:C++
// c-basic-offset:3
// End:
