Program Listing for File UnionFind.h

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

/*--------------------------------------------------------------------------*/
/*---------------------------- File UnionFind.h ----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

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

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

#include "ADS/Contract.h"

#include <algorithm>
#include <cstddef>
#include <utility>
#include <vector>

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

namespace ADS {

/*--------------------------------------------------------------------------*/
/*--------------------------- CLASS DisjointSets ---------------------------*/
/*--------------------------------------------------------------------------*/

enum class Union { SIZE , RANK };

enum class Compression { HALVING , FULL };

template< Union L = Union::SIZE , Compression C = Compression::HALVING >
class DisjointSets {

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

 explicit DisjointSets( int n = 0 );

 void reset( int n );

 [[nodiscard]] int n( void ) const { return( int( f_p.size() ) ); }

 [[nodiscard]] int count( void ) const { return( f_count ); }

 int find( int x );

 bool merge( int x , int y );

 bool same( int x , int y );

 int size( int x ) requires( L == Union::SIZE );

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

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

 std::vector< int > f_p;
 int f_count = 0;

 };  // end( class DisjointSets )

using UnionFind = DisjointSets<>;

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

}  // end( namespace ADS )

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

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

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

#endif  /* UnionFind.h included */

/*--------------------------------------------------------------------------*/
/*-------------------------- End File UnionFind.h --------------------------*/
/*--------------------------------------------------------------------------*/