source: lemon-0.x/src/work/athos/union_find.h @ 812:182d3a4d7ddb

// -*- C++ -*- //
/*
Union-Find structure

* Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
* minden szobajovo kulcs ertekre, -1 -es ertekkel!
 
*/
#ifndef UNION_FIND_H
#define UNION_FIND_H

#include <vector>
//#include <map>


namespace hugo {
  
  template <typename KeyType, typename KeyIntMap>
    class UnionFind {
    KeyIntMap& pointmap;
    struct VectorElementType {
      int boss;
      int count;
      VectorElementType(int _boss, int _count){
        boss = _boss;
        count = _count;
      }
    };
    std::vector<VectorElementType> container;
    public:
      
    UnionFind(KeyIntMap& _pointmap): pointmap(_pointmap){
      
    } 
    
    //Give a component of one point to the structure
    int addPoint(KeyType u){
      int _index = container.size();
      VectorElementType buf(_index,1);
      container.push_back(buf);
      return _index;
    }

    
    //Finds the big boss of u
    int find(KeyType u){
      if (pointmap.get(u)==-1){
        int whoami = addPoint(u);
        pointmap.set(u, whoami);
        return whoami;
      }
      else{
        int emp = pointmap.get(u);
        int boss = container[emp].boss;
        while(emp != boss){
          emp = boss;
          boss = container[emp].boss;
        }
        return boss;
      }
    }

    //Finds u and v in the structures and merges the comopnents, if not equal
    bool findAndMerge(KeyType u,KeyType v){
      int bu = find(u);
      int bv = find(v);
      if (bu != bv){
        unio(bu,bv);
        return true;
      }
      else{
        return false;
      }
    }

    //Merges a into b
    void mergeInto(int a, int b){
      container[a].boss = b;
      container[b].count +=  container[a].count;
    }
    
    //Makes the union
    void unio(int b1, int b2){
      if (container[b1].count>container[b2].count){
        mergeInto(b2,b1);
      }
      else{
        mergeInto(b1,b2);
      }
    }//unio
  };
  
}//namespace hugo
#endif