Program Listing for File MFSet.h

↰ Return to documentation for file (ADS/mfset/MFSet.h)

/*--------------------------------------------------------------------------*/
/*------------------------------ File MFSet.h ------------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_MFSet
 #define __ADS_MFSet
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"
#include "ADS/graph/Graph.h"

#include <stdexcept>
#include <utility>
#include <vector>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

/*--------------------------------------------------------------------------*/
/*------------------------------ CLASS MFSet -------------------------------*/
/*--------------------------------------------------------------------------*/

class MFSet {

/*--------------------------------------------------------------------------*/
 public:

 enum class Union {
  NONE ,
  RANK ,
  SIZE
  };

 explicit MFSet( int n , Union u = Union::RANK , bool compress = true );

 [[nodiscard]] int n( void ) const;

 [[nodiscard]] int count( void ) const;

 int find( int x );

 bool merge( int x , int y );

 bool same( int x , int y );

 [[nodiscard]] int parent( int x ) const;

 [[nodiscard]] int rank( int x ) const;

 [[nodiscard]] int size( int x ) const;

 [[nodiscard]] long steps( void ) const;

/*--------------------------------------------------------------------------*/
 private:

 [[nodiscard]] int root( int x ) const;

 [[nodiscard]] bool forest( void ) const;

 std::vector< int > f_p;
 std::vector< int > f_rank;
 std::vector< int > f_size;
 Union f_union;
 bool f_compress;
 int f_count;
 long f_steps = 0;

 };  // end( class MFSet )

/*--------------------------------------------------------------------------*/

template< Graph G >
MFSet components( const G & g );

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/mfset/impl/MFSet.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* MFSet.h included */

/*--------------------------------------------------------------------------*/
/*---------------------------- End File MFSet.h ----------------------------*/
/*--------------------------------------------------------------------------*/