<commit_before>#ifndef ALEPH_DISTANCES_DETAIL_MUNKRES_HH__
#define ALEPH_DISTANCES_DETAIL_MUNKRES_HH__

#include "Matrix.hh"

#include <algorithm>
#include <limits>
#include <vector>

namespace aleph
{

namespace distances
{

namespace detail
{

template <class T> class Munkres
{
public:

  void solve( Matrix<T>& matrix )
  {
    auto n = matrix.n();

    // Copy input matrix
    this->matrix = m;

    _rowMask = std::vector<bool>( size, false );
    _colMask = std::vector<bool>( size, false );

    subtractRowMinimum( matrix );

    unsigned short step = 1;

    while( step )
    {
      std::size_t row = 0;
      std::size_t col = 0;

      switch ( step ) {
        case 1:
          step = step1( matrix );
          break;
        case 2:
          step = step2( matrix );
          break;
        case 3:
          step = step3( matrix, row, col );
          break;
        case 4:
          step = step4( matrix );
          break;
        case 5:
          step = step5( matrix );
          break;
      }
    }

    for( std::size_t row = 0; row < n; row++ )
    {
      for( std::size_t col = 0; col < n; col++ )
      {
        if( _stars( row, col ) )
          matrix( row, col ) = T( 0 );
        else
          matrix( row, col ) = std::numeric_limits<T>::max();
      }
    }
  }

private:

  // Modifies matrix in-place by subtracting the minimum value in each
  // row. The function assumes that matrix is not empty.
  void subtractRowMinimum( Matrix<T>& matrix )
  {
    auto n = matrix.n();

    for( std::size_t row = 0; row < n; row++ )
    {
      auto min = matrix( row, 0 );

      for( std::size_t col = 0; col < n; col++ )
        min = std::min( min, matrix( row, col ) );

      for( std::size_t col = 0; col < n; col++ )
        matrix( row, col ) -= min;
    }
  }

  bool findUncoveredZeroInMatrix( const Matrix<T>& matrix, std::size_t& row, std::size_t& column ) const
  {
    auto n = matrix.n();

    for( row = 0; row < n; row++ )
    {
      if( !_rowMask[row] )
      {
        for( col = 0; col < n; col++ )
        {
          if( !_colMask[col] )
          {
            if( matrix( row, col ) == T( 0 ) )
              return true;
          }
        }
      }
    }

    return false;
  }

  // Find zeroes in the current matrix. If there is no starred zero in
  // the row or column, star the current value.
  unsigned short step1( Matrix<T>& matrix )
  {
    auto n = matrix.n();

    for( std::size_t row = 0; row < n; row++ )
    {
      for( std::size_t col = 0; col < n; col++ )
      {
        if( matrix( row, col ) == T( 0 ) )
        {
          // Check whether another zero in the same _column_ is already
          // starred.
          for( std::size_t r = 0; r < n; r++ )
          {
            if( _stars( r, col ) )
              goto skipCurrentColumn;
          }

          // Check whether another zero in the same _row_ is already
          // starred.
          for( std::size_t c = 0; c < n; c++ )
          {
            if( _stars( row, c ) )
              goto skipCurrentRow;
          }

          _stars( row, col ) = true;
        }
        skipCurrentColumn:
          ;
      }

      skipCurrentRow:
        ;
    }

    return 2;
  }

  // Cover each column that contains a starred zero. If enough columns
  // have been covered, the starred zeroes give us the complete set of
  // assignments.
  unsigned short step2( Matrix<T>& matrix )
  {
    auto n                     = matrix.n();
    std::size_t coveredColumns = 0;

    for( std::size_t row = 0; row < n; row++ )
    {
      for( std::size_t col = 0; col < n; col++ )
      {
        if( _stars( row, col ) )
        {
          _colMask[col] = true;
          ++coveredColumns;
        }
      }
    }

    if( coveredColumns >= n )
      return 0;

    return 3;
  }

  // Find an uncovered zero and prime it. If there is no starred zero in
  // the row containing this primed zero, go to step 5. Otherwise, cover
  // this row and uncover the column that contains the starred zero.
  unsigned short step3( Matrix<T>& matrix, std::size_t& row, std::size_t& col )
  {
    if( findUncoveredZeroInMatrix( matrix, row, col ) )
      _primes( row, col ) = true;
    else
      return 5;

    auto n = matrix.n();

    for( std::size_t c = 0; c < n; c++ )
    {
      if( _stars( row, c ) )
      {
        _rowMask[row] = true;
        _colMask[col] = false;

        return 3;
      }
    }

    return 4;
  }

  unsigned short step4( Matrix<T>& matrix, std::size_t row, std::size_t col )
  {
    auto n = matrix.n();

    using Pair     = std::pair<std::size_t, std::size_t>;
    using Sequence = std::vector<Pair>;

    Sequence sequence;

    sequence.push_back( std::make_pair( row, col ) );<commit_msg>Resetting stars and primes in mask matrices<commit_after>#ifndef ALEPH_DISTANCES_DETAIL_MUNKRES_HH__
#define ALEPH_DISTANCES_DETAIL_MUNKRES_HH__

#include "Matrix.hh"

#include <algorithm>
#include <limits>
#include <vector>

namespace aleph
{

namespace distances
{

namespace detail
{

template <class T> class Munkres
{
public:

  void solve( Matrix<T>& matrix )
  {
    auto n = matrix.n();

    // Copy input matrix
    this->matrix = m;

    _rowMask = std::vector<bool>( size, false );
    _colMask = std::vector<bool>( size, false );

    subtractRowMinimum( matrix );

    unsigned short step = 1;

    while( step )
    {
      std::size_t row = 0;
      std::size_t col = 0;

      switch ( step ) {
        case 1:
          step = step1( matrix );
          break;
        case 2:
          step = step2( matrix );
          break;
        case 3:
          step = step3( matrix, row, col );
          break;
        case 4:
          step = step4( matrix );
          break;
        case 5:
          step = step5( matrix );
          break;
      }
    }

    for( std::size_t row = 0; row < n; row++ )
    {
      for( std::size_t col = 0; col < n; col++ )
      {
        if( _stars( row, col ) )
          matrix( row, col ) = T( 0 );
        else
          matrix( row, col ) = std::numeric_limits<T>::max();
      }
    }
  }

private:

  // Modifies matrix in-place by subtracting the minimum value in each
  // row. The function assumes that matrix is not empty.
  void subtractRowMinimum( Matrix<T>& matrix )
  {
    auto n = matrix.n();

    for( std::size_t row = 0; row < n; row++ )
    {
      auto min = matrix( row, 0 );

      for( std::size_t col = 0; col < n; col++ )
        min = std::min( min, matrix( row, col ) );

      for( std::size_t col = 0; col < n; col++ )
        matrix( row, col ) -= min;
    }
  }

  bool findUncoveredZeroInMatrix( const Matrix<T>& matrix, std::size_t& row, std::size_t& column ) const
  {
    auto n = matrix.n();

    for( row = 0; row < n; row++ )
    {
      if( !_rowMask[row] )
      {
        for( col = 0; col < n; col++ )
        {
          if( !_colMask[col] )
          {
            if( matrix( row, col ) == T( 0 ) )
              return true;
          }
        }
      }
    }

    return false;
  }

  // Find zeroes in the current matrix. If there is no starred zero in
  // the row or column, star the current value.
  unsigned short step1( Matrix<T>& matrix )
  {
    auto n = matrix.n();

    for( std::size_t row = 0; row < n; row++ )
    {
      for( std::size_t col = 0; col < n; col++ )
      {
        if( matrix( row, col ) == T( 0 ) )
        {
          // Check whether another zero in the same _column_ is already
          // starred.
          for( std::size_t r = 0; r < n; r++ )
          {
            if( _stars( r, col ) )
              goto skipCurrentColumn;
          }

          // Check whether another zero in the same _row_ is already
          // starred.
          for( std::size_t c = 0; c < n; c++ )
          {
            if( _stars( row, c ) )
              goto skipCurrentRow;
          }

          _stars( row, col )  = true;
          _primes( row, col ) = false;
        }
        skipCurrentColumn:
          ;
      }

      skipCurrentRow:
        ;
    }

    return 2;
  }

  // Cover each column that contains a starred zero. If enough columns
  // have been covered, the starred zeroes give us the complete set of
  // assignments.
  unsigned short step2( Matrix<T>& matrix )
  {
    auto n                     = matrix.n();
    std::size_t coveredColumns = 0;

    for( std::size_t row = 0; row < n; row++ )
    {
      for( std::size_t col = 0; col < n; col++ )
      {
        if( _stars( row, col ) )
        {
          _colMask[col] = true;
          ++coveredColumns;
        }
      }
    }

    if( coveredColumns >= n )
      return 0;

    return 3;
  }

  // Find an uncovered zero and prime it. If there is no starred zero in
  // the row containing this primed zero, go to step 5. Otherwise, cover
  // this row and uncover the column that contains the starred zero.
  unsigned short step3( Matrix<T>& matrix, std::size_t& row, std::size_t& col )
  {
    if( findUncoveredZeroInMatrix( matrix, row, col ) )
    {
      _primes( row, col ) = true;
      _stars( row, col )  = false;
    }
    else
      return 5;

    auto n = matrix.n();

    for( std::size_t c = 0; c < n; c++ )
    {
      if( _stars( row, c ) )
      {
        _rowMask[row] = true;
        _colMask[col] = false;

        return 3;
      }
    }

    return 4;
  }

  unsigned short step4( Matrix<T>& matrix, std::size_t row, std::size_t col )
  {
    auto n = matrix.n();

    using Pair     = std::pair<std::size_t, std::size_t>;
    using Sequence = std::vector<Pair>;

    Sequence sequence;

    sequence.push_back( std::make_pair( row, col ) );
{'fraction_non_alphanumeric': 0.12514291653674253, 'fraction_numerical': 0.008938779752624467, 'mean_word_length': 1.6944833380005602, 'pattern_counts': {'":': 0, '<': 63, '<?xml version=': 0, '>': 39, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3597605', 'n_tokens_mistral': 3329, 'n_tokens_neox': 3134, 'n_words': 1004}