<commit_before>/* Copyright (C) 2008-2011 <NAME>
   (C) 2015 <NAME>.
   (C) 2016 <NAME>. (generic improvements, auxiliary solutions, subsolutions)
   
   This file is part of fplll. fplll is free software: you
   can redistribute it and/or modify it under the terms of the GNU Lesser
   General Public License as published by the Free Software Foundation,
   either version 2.1 of the License, or (at your option) any later version.

   fplll is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
   GNU Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public License
   along with fplll. If not, see <http://www.gnu.org/licenses/>. */

#include "enumerate_base.h"

FPLLL_BEGIN_NAMESPACE

#ifdef FPLLL_WITH_RECURSIVE_ENUM
template<int kk, int kk_start, bool dualenum, bool findsubsols>
inline void EnumerationBase::enumerate_recursive( EnumerationBase::opts<kk, kk_start, dualenum, findsubsols> )
{
    enumf alphak = x[kk] - center[kk];
    enumf newdist = partdist[kk] + alphak*alphak*rdiag[kk];

    if (!(newdist <= partdistbounds[kk]))
        return;
    ++nodes;
    
    alpha[kk] = alphak;
    if (findsubsols && newdist < subsoldists[kk])
    {
        subsoldists[kk] = newdist;
        process_subsolution(kk, newdist);
    }
    
    if (kk == 0)
    {
        if (newdist > 0.0 /* || !is_svp */)
            process_solution(newdist);
    }
    else
    {
        partdist[kk-1] = newdist;
        if (dualenum)
        {
            for (int j = center_partsum_begin[kk]; j > kk-1; --j)
                center_partsums[kk-1][j] = center_partsums[kk-1][j+1] - alpha[j] * mut[kk-1][j];
        }
        else
        {
            for (int j = center_partsum_begin[kk]; j > kk-1; --j)
                center_partsums[kk-1][j] = center_partsums[kk-1][j+1] - x[j] * mut[kk-1][j];
        }
        if (center_partsum_begin[kk] > center_partsum_begin[kk-1])
            center_partsum_begin[kk-1] = center_partsum_begin[kk];
        center_partsum_begin[kk] = kk;
        center[kk-1] = center_partsums[kk-1][kk];    
        roundto(x[kk-1], center[kk-1]);
        dx[kk-1] = ddx[kk-1] = (((int)(center[kk-1] >= x[kk-1]) & 1) << 1) - 1;
    }

    
    while (true)
    {
        enumerate_recursive( opts<kk-1,kk_start,dualenum,findsubsols>() );

        if (partdist[kk] != 0.0)
        {
            x[kk] += dx[kk];
            ddx[kk] = -ddx[kk];
            dx[kk] = ddx[kk] - dx[kk];

            enumf alphak2 = x[kk] - center[kk];
            enumf newdist2 = partdist[kk] + alphak2*alphak2*rdiag[kk];
            if (!(newdist2 <= partdistbounds[kk]))
                return;
            ++nodes;
            alpha[kk] = alphak2;
            if (kk == 0)
            {
                if (newdist2 > 0.0 /* || !is_svp */)
                    process_solution(newdist2);
            }
            else
            {
                partdist[kk-1] = newdist2;
                if (dualenum)
                    center_partsums[kk-1][kk-1+1] = center_partsums[kk-1][kk-1+1+1] - alpha[kk-1+1] * mut[kk-1][kk-1+1];
                else
                    center_partsums[kk-1][kk-1+1] = center_partsums[kk-1][kk-1+1+1] - x[kk-1+1] * mut[kk-1][kk-1+1];
                if (kk > center_partsum_begin[kk-1])
                    center_partsum_begin[kk-1] = kk;
                center[kk-1] = center_partsums[kk-1][kk-1+1];    
                roundto(x[kk-1], center[kk-1]);
                dx[kk-1] = ddx[kk-1] = (((int)(center[kk-1] >= x[kk-1]) & 1) << 1) - 1;
            }
        }
        else
        {
            ++x[kk];

            enumf alphak2 = x[kk] - center[kk];
            enumf newdist2 = partdist[kk] + alphak2*alphak2*rdiag[kk];
            if (!(newdist2 <= partdistbounds[kk]))
                return;
            ++nodes;
            alpha[kk] = alphak2;
            if (kk == 0)
            {
                if (newdist2 > 0.0 /* || !is_svp */)
                    process_solution(newdist2);
            }
            else
            {
                partdist[kk-1] = newdist2;
                if (dualenum)
                    center_partsums[kk-1][kk-1+1] = center_partsums[kk-1][kk-1+1+1] - alpha[kk-1+1] * mut[kk-1][kk-1+1];
                else
                    center_partsums[kk-1][kk-1+1] = center_partsums[kk-1][kk-1+1+1] - x[kk-1+1] * mut[kk-1][kk-1+1];
                if (kk > center_partsum_begin[kk-1])
                    center_partsum_begin[kk-1] = kk;
                center[kk-1] = center_partsums[kk-1][kk-1+1];    
                roundto(x[kk-1], center[kk-1]);
                dx[kk-1] = ddx[kk-1] = (((int)(center[kk-1] >= x[kk-1]) & 1) << 1) - 1;
            }
        }
    }
}

#define ENUM_TABLE_FILL8(a) \
            & EnumerationBase::enumerate_recursive_wrapper< a+0,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+1,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+2,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+3,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+4,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+5,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+6,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+7,dualenum,findsubsols>
#define ENUM_TABLE_FILL64(a) \
            ENUM_TABLE_FILL8(a), ENUM_TABLE_FILL8(a+8), ENUM_TABLE_FILL8(a+16), ENUM_TABLE_FILL8(a+24), \
            ENUM_TABLE_FILL8(a+32), ENUM_TABLE_FILL8(a+40), ENUM_TABLE_FILL8(a+48), ENUM_TABLE_FILL8(a+56)
#define ENUM_TABLE_FILL256(a) \
            ENUM_TABLE_FILL64(a), ENUM_TABLE_FILL64(a+64), ENUM_TABLE_FILL64(a+128), ENUM_TABLE_FILL64(a+192)
            
template<bool dualenum, bool findsubsols>
inline void EnumerationBase::enumerate_recursive_dispatch(int kk)
{
    typedef void (EnumerationBase::*enum_recur_type)();
    static const enum_recur_type lookup[] = {
        ENUM_TABLE_FILL256(0),
        ENUM_TABLE_FILL256(256),
        ENUM_TABLE_FILL256(512),
        ENUM_TABLE_FILL256(768),
        ENUM_TABLE_FILL256(1024),
        ENUM_TABLE_FILL256(1280),
        ENUM_TABLE_FILL256(1536),
        ENUM_TABLE_FILL256(1792),
    };
    (this->*lookup[kk])();
}

#endif

template<bool dualenum, bool findsubsols>
void EnumerationBase::enumerate_loop()
{
    if (k >= k_end)
        return;
    
    for (int i = 0; i < k_end; ++i)
    {
        center_partsum_begin[i+1] = k_end - 1;
        center_partsums[i][k_end] = center_partsum[i];
    }
    
    partdist[k_end] = 0.0; // needed to make next_pos_up() work properly

    nodes -= k_end - k;
    k = k_end - 1;
#ifdef FPLLL_WITH_RECURSIVE_ENUM
    enumerate_recursive_dispatch<dualenum, findsubsols>(k);
    return;
#endif

    finished = false;
    while (!finished)
    {
        enumf alphak = x[k] - center[k];
        enumf newdist = partdist[k] + alphak * alphak * rdiag[k];
        FPLLL_TRACE("Level k=" << k << " dist_k=" << partdist[k] << " x_k=" << x[k] << " newdist=" << newdist << " partdistbounds_k=" << partdistbounds[k]);
        if (newdist <= partdistbounds[k])
        {
            ++nodes;
            alpha[k] = alphak;
            if (findsubsols && newdist < subsoldists[k])
            {
                subsoldists[k] = newdist;
                process_subsolution(k, newdist);
            }
            --k;
            if (k < 0)
            {
                if (newdist > 0.0 /* || !is_svp */)
                    process_solution(newdist);
                finished = !next_pos_up();
                continue;
            }
            if (!_max_indices.empty() && _max_indices[k+1] == k+1)   //in CVP, at max GS vector, we reset the partial distance
            {
                reset(newdist);
                finished = !next_pos_up();
                continue;
            }
            if (dualenum)
            {
                for (int j = center_partsum_begin[k+1]; j > k; --j)
                    center_partsums[k][j] = center_partsums[k][j+1] - alpha[j] * mut[k][j];
            }
            else
            {
                for (int j = center_partsum_begin[k+1]; j > k; --j)
                    center_partsums[k][j] = center_partsums[k][j+1] - x[j] * mut[k][j];
            }
            center_partsum_begin[k] = max(center_partsum_begin[k], center_partsum_begin[k+1]);
            center_partsum_begin[k+1] = k+1;
            
            enumf newcenter =  center_partsums[k][k+1];
            center[k] = newcenter;
            partdist[k] = newdist;
            roundto(x[k], newcenter);
            dx[k] = ddx[k] = (((int)(newcenter >= x[k]) & 1) << 1) - 1;
        }
        else<commit_msg>Very minor stuffs<commit_after>/* Copyright (C) 2008-2011 <NAME>
   (C) 2015 <NAME>.
   (C) 2016 <NAME>. (generic improvements, auxiliary solutions, subsolutions)
   
   This file is part of fplll. fplll is free software: you
   can redistribute it and/or modify it under the terms of the GNU Lesser
   General Public License as published by the Free Software Foundation,
   either version 2.1 of the License, or (at your option) any later version.

   fplll is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
   GNU Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public License
   along with fplll. If not, see <http://www.gnu.org/licenses/>. */

#include "enumerate_base.h"

FPLLL_BEGIN_NAMESPACE

#ifdef FPLLL_WITH_RECURSIVE_ENUM
template<int kk, int kk_start, bool dualenum, bool findsubsols>
inline void EnumerationBase::enumerate_recursive( EnumerationBase::opts<kk, kk_start, dualenum, findsubsols> )
{
    enumf alphak = x[kk] - center[kk];
    enumf newdist = partdist[kk] + alphak*alphak*rdiag[kk];

    if (!(newdist <= partdistbounds[kk]))
        return;
    ++nodes;
    
    alpha[kk] = alphak;
    if (findsubsols && newdist < subsoldists[kk])
    {
        subsoldists[kk] = newdist;
        process_subsolution(kk, newdist);
    }
    
    if (kk == 0)
    {
        if (newdist > 0.0 /* || !is_svp */)
            process_solution(newdist);
    }
    else
    {
        partdist[kk-1] = newdist;
        if (dualenum)
        {
            for (int j = center_partsum_begin[kk]; j > kk-1; --j)
                center_partsums[kk-1][j] = center_partsums[kk-1][j+1] - alpha[j] * mut[kk-1][j];
        }
        else
        {
            for (int j = center_partsum_begin[kk]; j > kk-1; --j)
                center_partsums[kk-1][j] = center_partsums[kk-1][j+1] - x[j] * mut[kk-1][j];
        }
        if (center_partsum_begin[kk] > center_partsum_begin[kk-1])
            center_partsum_begin[kk-1] = center_partsum_begin[kk];
        center_partsum_begin[kk] = kk;
        center[kk-1] = center_partsums[kk-1][kk];    
        roundto(x[kk-1], center[kk-1]);
        dx[kk-1] = ddx[kk-1] = (((int)(center[kk-1] >= x[kk-1]) & 1) << 1) - 1;
    }

    
    while (true)
    {
        enumerate_recursive( opts<kk-1,kk_start,dualenum,findsubsols>() );

        if (partdist[kk] != 0.0)
        {
            x[kk] += dx[kk];
            ddx[kk] = -ddx[kk];
            dx[kk] = ddx[kk] - dx[kk];

            enumf alphak2 = x[kk] - center[kk];
            enumf newdist2 = partdist[kk] + alphak2*alphak2*rdiag[kk];
            if (!(newdist2 <= partdistbounds[kk]))
                return;
            ++nodes;
            alpha[kk] = alphak2;
            if (kk == 0)
            {
                if (newdist2 > 0.0 /* || !is_svp */)
                    process_solution(newdist2);
            }
            else
            {
                partdist[kk-1] = newdist2;
                if (dualenum)
                    center_partsums[kk-1][kk-1+1] = center_partsums[kk-1][kk-1+1+1] - alpha[kk-1+1] * mut[kk-1][kk-1+1];
                else
                    center_partsums[kk-1][kk-1+1] = center_partsums[kk-1][kk-1+1+1] - x[kk-1+1] * mut[kk-1][kk-1+1];
                if (kk > center_partsum_begin[kk-1])
                    center_partsum_begin[kk-1] = kk;
                center[kk-1] = center_partsums[kk-1][kk-1+1];    
                roundto(x[kk-1], center[kk-1]);
                dx[kk-1] = ddx[kk-1] = (((int)(center[kk-1] >= x[kk-1]) & 1) << 1) - 1;
            }
        }
        else
        {
            ++x[kk];

            enumf alphak2 = x[kk] - center[kk];
            enumf newdist2 = partdist[kk] + alphak2*alphak2*rdiag[kk];
            if (!(newdist2 <= partdistbounds[kk]))
                return;
            ++nodes;
            alpha[kk] = alphak2;
            if (kk == 0)
            {
                if (newdist2 > 0.0 /* || !is_svp */)
                    process_solution(newdist2);
            }
            else
            {
                partdist[kk-1] = newdist2;
                if (dualenum)
                    center_partsums[kk-1][kk-1+1] = center_partsums[kk-1][kk-1+1+1] - alpha[kk-1+1] * mut[kk-1][kk-1+1];
                else
                    center_partsums[kk-1][kk-1+1] = center_partsums[kk-1][kk-1+1+1] - x[kk-1+1] * mut[kk-1][kk-1+1];
                if (kk > center_partsum_begin[kk-1])
                    center_partsum_begin[kk-1] = kk;
                center[kk-1] = center_partsums[kk-1][kk-1+1];    
                roundto(x[kk-1], center[kk-1]);
                dx[kk-1] = ddx[kk-1] = (((int)(center[kk-1] >= x[kk-1]) & 1) << 1) - 1;
            }
        }
    }
}

#define ENUM_TABLE_FILL8(a) \
            & EnumerationBase::enumerate_recursive_wrapper< a+0,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+1,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+2,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+3,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+4,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+5,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+6,dualenum,findsubsols>, \
            & EnumerationBase::enumerate_recursive_wrapper< a+7,dualenum,findsubsols>
#define ENUM_TABLE_FILL64(a) \
            ENUM_TABLE_FILL8(a), ENUM_TABLE_FILL8(a+8), ENUM_TABLE_FILL8(a+16), ENUM_TABLE_FILL8(a+24), \
            ENUM_TABLE_FILL8(a+32), ENUM_TABLE_FILL8(a+40), ENUM_TABLE_FILL8(a+48), ENUM_TABLE_FILL8(a+56)
#define ENUM_TABLE_FILL256(a) \
            ENUM_TABLE_FILL64(a), ENUM_TABLE_FILL64(a+64), ENUM_TABLE_FILL64(a+128), ENUM_TABLE_FILL64(a+192)
            
template<bool dualenum, bool findsubsols>
inline void EnumerationBase::enumerate_recursive_dispatch(int kk)
{
    typedef void (EnumerationBase::*enum_recur_type)();
    static const enum_recur_type lookup[] = {
        ENUM_TABLE_FILL256(0),
        ENUM_TABLE_FILL256(256),
        ENUM_TABLE_FILL256(512),
        ENUM_TABLE_FILL256(768),
        ENUM_TABLE_FILL256(1024),
        ENUM_TABLE_FILL256(1280),
        ENUM_TABLE_FILL256(1536),
        ENUM_TABLE_FILL256(1792),
    };
    (this->*lookup[kk])();
}

#endif

template<bool dualenum, bool findsubsols>
void EnumerationBase::enumerate_loop()
{
    if (k >= k_end)
        return;
    
    for (int i = 0; i < k_end; ++i)
    {
        center_partsum_begin[i+1] = k_end - 1;
        center_partsums[i][k_end] = center_partsum[i];
    }
    
    partdist[k_end] = 0.0; // needed to make next_pos_up() work properly

    nodes -= k_end - k;
    k = k_end - 1;

#ifdef FPLLL_WITH_RECURSIVE_ENUM
    enumerate_recursive_dispatch<dualenum, findsubsols>(k);
    return;
#endif

    finished = false;
    while (!finished)
    {
        enumf alphak = x[k] - center[k];
        enumf newdist = partdist[k] + alphak * alphak * rdiag[k];
        FPLLL_TRACE("Level k=" << k << " dist_k=" << partdist[k] << " x_k=" << x[k] << " newdist=" << newdist << " partdistbounds_k=" << partdistbounds[k]);
        if (newdist <= partdistbounds[k])
        {
            ++nodes;
            alpha[k] = alphak;
            if (findsubsols && newdist < subsoldists[k])
            {
                subsoldists[k] = newdist;
                process_subsolution(k, newdist);
            }
            --k;
            if (k < 0)
            {
                if (newdist > 0.0 /* || !is_svp */)
                    process_solution(newdist);
                finished = !next_pos_up();
                continue;
            }
            if (!_max_indices.empty() && _max_indices[k+1] == k+1)   //in CVP, at max GS vector, we reset the partial distance
            {
                reset(newdist);
                finished = !next_pos_up();
                continue;
            }
            if (dualenum)
            {
                for (int j = center_partsum_begin[k+1]; j > k; --j)
                    center_partsums[k][j] = center_partsums[k][j+1] - alpha[j] * mut[k][j];
            }
            else
            {
                for (int j = center_partsum_begin[k+1]; j > k; --j)
                    center_partsums[k][j] = center_partsums[k][j+1] - x[j] * mut[k][j];
            }
            center_partsum_begin[k] = max(center_partsum_begin[k], center_partsum_begin[k+1]);
            center_partsum_begin[k+1] = k+1;
            
            enumf newcenter = center_partsums[k][k+1];
            center[k] = newcenter;
            partdist[k] = newdist;
            roundto(x[k], newcenter);
            dx[k] = ddx[k] = (((int)(newcenter >= x[k]) & 1) << 1) - 1;
        }
        else
{'fraction_non_alphanumeric': 0.13978735310576385, 'fraction_numerical': 0.03077783995523223, 'mean_word_length': 1.9622078567876677, 'pattern_counts': {'":': 0, '<': 107, '<?xml version=': 0, '>': 73, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, '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': '217411', 'n_tokens_mistral': 6674, 'n_tokens_neox': 6323, 'n_words': 1117}