MRUnionFindParallel.h

Go to the documentation of this file.

#pragma once
 
#include "MRUnionFind.h"
#include "MRBitSetParallelFor.h"
#include "MRParallelFor.h"
#include "MRTimer.h"
 
namespace MR
{
 

template <typename I>
[[nodiscard]] TypedBitSet<I> findRootsBitSet( const BaseUnionFind<I> & uf, const TypedBitSet<I> * region = nullptr )
{
    MR_TIMER;
    TypedBitSet<I> res( uf.size() );
    BitSetParallelForAll( res, [&]( I i )
    {
        if ( region && !region->test( i ) )
            return;
        if ( uf.isRoot( i ) )
            res.set( i );
    } );
    return res;
}

template <typename I>
[[nodiscard]] TypedBitSet<I> findComponentBitSet( BaseUnionFind<I> & uf, I a, const TypedBitSet<I> * region = nullptr )
{
    MR_TIMER;
    TypedBitSet<I> res( uf.size() );
    a = uf.find( a );
    BitSetParallelForAllRanged( res, [&]( I i, const auto & range )
    {
        if ( region && !region->test( i ) )
            return;
        if ( a == uf.findUpdateRange( i, range.beg, range.end ) )
            res.set( i );
    } );
    return res;
}

template <typename I>
[[nodiscard]] bool isSubdivision( const BaseUnionFind<I> & uf, const TypedBitSet<I> & region )
{
    MR_TIMER;
    tbb::task_group_context ctx;
    ParallelFor( I( 0 ), I( uf.size() ), [&]( I i )
    {
        if ( region.test( uf.parent( i ) ) != region.test( i ) )
            ctx.cancel_group_execution();
    }, ctx );
    return !ctx.is_group_execution_cancelled();
}

template <typename I>
const Vector<I, I> & updateRootsParallel( BaseUnionFind<I> & uf )
{
    MR_TIMER;
    tbb::parallel_for( tbb::blocked_range<I>( I( 0 ), I( uf.size() ) ),
        [&] ( const tbb::blocked_range<I> & range )
    {
        for ( I i = range.begin(); i < range.end(); ++i )
            uf.findUpdateRange( i, range.begin(), range.end() );
    } );
    return uf.parents();
}
}