<commit_before>/*******************************************************************************
 * benchmarks/prefix_doubling/prefix_doubling.cpp
 *
 * Part of Project Thrill - http://project-thrill.org
 *
 * Copyright (C) 2016 <NAME> <<EMAIL>>
 *
 * All rights reserved. Published under the BSD-2 license in the LICENSE file.
 ******************************************************************************/

#include <thrill/api/allgather.hpp>
#include <thrill/api/cache.hpp>
#include <thrill/api/dia.hpp>
#include <thrill/api/distribute.hpp>
#include <thrill/api/distribute_from.hpp>
#include <thrill/api/gather.hpp>
#include <thrill/api/generate.hpp>
#include <thrill/api/groupby.hpp>
#include <thrill/api/merge.hpp>
#include <thrill/api/prefixsum.hpp>
#include <thrill/api/read_binary.hpp>
#include <thrill/api/size.hpp>
#include <thrill/api/sort.hpp>
#include <thrill/api/sum.hpp>
#include <thrill/api/window.hpp>
#include <thrill/api/write_binary.hpp>
#include <thrill/api/zip.hpp>
#include <thrill/common/cmdline_parser.hpp>
#include <thrill/common/logger.hpp>
#include <thrill/core/multiway_merge.hpp>

#include <algorithm>
#include <limits>
#include <random>
#include <stdexcept>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

bool debug_print = false;
bool debug = true;

using namespace thrill; // NOLINT
using thrill::common::RingBuffer;

//! A pair (index, t=T[index]).
template <typename AlphabetType>  
struct IndexOneMer {
    size_t index;
    AlphabetType t;

    friend std::ostream& operator << (std::ostream& os, const IndexOneMer& iom) {
        return os << '[' << iom.index << ',' << iom.t << ']';
    }
} THRILL_ATTRIBUTE_PACKED;

//! A pair (rank, index)
struct IndexRank {
    size_t index;
    size_t rank;

    friend std::ostream& operator << (std::ostream& os, const IndexRank& ri) {
        return os << '(' << ri.index << '|' << ri.rank << ')';
    }
} THRILL_ATTRIBUTE_PACKED;

//! A triple (rank_1, rank_2, index)
struct IndexRankRank {
    size_t index;
    size_t rank1;
    size_t rank2;

    friend std::ostream& operator << (std::ostream& os, const IndexRankRank& rri) {
        return os << "( i: " << rri.index << "| r1: " << rri.rank1 << "| r2: " << rri.rank2 << ")";
    }
} THRILL_ATTRIBUTE_PACKED;

template <typename InputDIA>
DIA<size_t> PrefixDoubling(Context& ctx, const InputDIA& input_dia, size_t input_size) {
    
    using Char = typename InputDIA::ValueType;
    using IndexOneMer = ::IndexOneMer<Char>;

    auto one_mers_sorted = 
        input_dia
        .template FlatWindow<IndexOneMer>(
            2,
            [input_size](size_t index, const RingBuffer<Char>& rb, auto emit) {
                emit(IndexOneMer {index, rb[0]});
                if(index == input_size - 2) emit(IndexOneMer {index + 1, rb[1]});
        })
        .Sort([](const IndexOneMer& a, const IndexOneMer& b) {
            return a.t < b.t;
        }).Keep();

    if(debug_print)
        one_mers_sorted.Print("one_mers_sorted");

    DIA<size_t> sa =
        one_mers_sorted
        .Map([](const IndexOneMer& iom) {
            return iom.index;
        }).Collapse();

    if (debug_print)
        sa.Print("sa");

    DIA<size_t> rebucket =
        one_mers_sorted
        .template FlatWindow<size_t>(
            2,
            [input_size](size_t index, const RingBuffer<IndexOneMer>& rb, auto emit) {
                if (index == 0) emit(0);
                if (rb[0].t == rb[1].t) emit(0);
                else emit(index + 1);
                if (index == input_size - 2) {
                    if (rb[0].t == rb[1].t) emit(0);
                    else emit(index + 2);
                }
        })
        .PrefixSum([](const size_t a, const size_t b) {
            return a > b ? a : b;
        });

    if (debug_print)
        rebucket.Print("rebucket");

    uint8_t shifted_exp = 1;

    while(true) {

        DIA<IndexRank> isa =
            sa
            .Zip(
                rebucket,
                [](size_t sa, size_t rb) {
                    return IndexRank {rb, sa};
            })
            .Sort([](const IndexRank& a, const IndexRank& b) {
                return a.rank < b.rank;   
            });

        if (debug_print)
            isa.Print("isa");
        LOG << "Computed the ISA";

        size_t shift_by = 1 << shifted_exp++;
        LOG << "Shift the ISA by " << shift_by << " positions";

        DIA<IndexRankRank> triple_sorted =
            isa
            .template FlatWindow<IndexRankRank>(
                shift_by,
                [input_size, shift_by](size_t index, const RingBuffer<IndexRank>& rb, auto emit) {
                    emit(IndexRankRank {rb[0].rank, rb[shift_by - 1].index, rb[0].index});
                    if(index == input_size - shift_by)
                        for(size_t i = 1; i < input_size - index; ++i)
                            emit(IndexRankRank {rb[i].rank, 0, rb[i].index});
                }
            )
            .Sort([](const IndexRankRank& a, const IndexRankRank& b) {
                if (a.rank1 == b.rank1) {
                    if (a.rank2 == b.rank2) return a.index < b.index;
                    else return a.rank2 < b.rank2;
                } else return a.rank1 < b.rank1;
            });
        LOG << "Sorted the triples";

        size_t non_singletons =
            triple_sorted
            .template FlatWindow<uint8_t>(
                2,
                [](size_t /*index*/, const RingBuffer<IndexRankRank>& rb, auto emit) {
                    if (rb[0].rank1 == rb[1].rank1 and rb[0].rank2 == rb[1].rank2)
                        emit(0);
                }
            ).Size();

        LOG << "Computed the number of non singletons";

        sa =
            triple_sorted
            .Map([](const IndexRankRank& rri) {
                return rri.index;
        }).Collapse();

        if (debug_print)
            sa.Print("sa");
        // If each suffix is unique regarding their 2h-prefix, we have computed
        // the suffix array and can return it. 
        if (non_singletons == 0)
            return sa;

        rebucket =
            triple_sorted
            .template FlatWindow<size_t>(
                2,
                [input_size](size_t index, const RingBuffer<IndexRankRank>& rb, auto emit) {
                    if (index == 0) emit(0);
                    if (rb[0].rank1 == rb[1].rank1 and rb[0].rank2 == rb[1].rank2)
                        emit(0);
                    else
                        emit(index + 1);
                    if (index == input_size - 2) {
                        if (rb[0].rank1 == rb[1].rank1 and rb[0].rank2 == rb[1].rank2)
                            emit(0);
                        else
                            emit(index + 2);
                    }
            })
            .PrefixSum([](const size_t a, const size_t b) {
                return a > b ? a : b;
            });

        if (debug_print)
            rebucket.Print("rebucket");
        LOG << "Rebucket the partial SA";
    }
}

/*!<commit_msg>Copied SA checker from DC3<commit_after>/*******************************************************************************
 * benchmarks/prefix_doubling/prefix_doubling.cpp
 *
 * Part of Project Thrill - http://project-thrill.org
 *
 * Copyright (C) 2016 <NAME> <<EMAIL>>
 *
 * All rights reserved. Published under the BSD-2 license in the LICENSE file.
 ******************************************************************************/

#include <thrill/api/allgather.hpp>
#include <thrill/api/cache.hpp>
#include <thrill/api/dia.hpp>
#include <thrill/api/distribute.hpp>
#include <thrill/api/distribute_from.hpp>
#include <thrill/api/gather.hpp>
#include <thrill/api/generate.hpp>
#include <thrill/api/groupby.hpp>
#include <thrill/api/merge.hpp>
#include <thrill/api/prefixsum.hpp>
#include <thrill/api/read_binary.hpp>
#include <thrill/api/size.hpp>
#include <thrill/api/sort.hpp>
#include <thrill/api/sum.hpp>
#include <thrill/api/window.hpp>
#include <thrill/api/write_binary.hpp>
#include <thrill/api/zip.hpp>
#include <thrill/common/cmdline_parser.hpp>
#include <thrill/common/logger.hpp>
#include <thrill/core/multiway_merge.hpp>

#include <algorithm>
#include <limits>
#include <random>
#include <stdexcept>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

bool debug_print = false;
bool debug = true;

using namespace thrill; // NOLINT
using thrill::common::RingBuffer;

//! A pair (index, t=T[index]).
template <typename AlphabetType>  
struct IndexOneMer {
    size_t index;
    AlphabetType t;

    friend std::ostream& operator << (std::ostream& os, const IndexOneMer& iom) {
        return os << '[' << iom.index << ',' << iom.t << ']';
    }
} THRILL_ATTRIBUTE_PACKED;

//! A pair (rank, index)
struct IndexRank {
    size_t index;
    size_t rank;

    friend std::ostream& operator << (std::ostream& os, const IndexRank& ri) {
        return os << '(' << ri.index << '|' << ri.rank << ')';
    }
} THRILL_ATTRIBUTE_PACKED;

//! A triple (rank_1, rank_2, index)
struct IndexRankRank {
    size_t index;
    size_t rank1;
    size_t rank2;

    friend std::ostream& operator << (std::ostream& os, const IndexRankRank& rri) {
        return os << "( i: " << rri.index << "| r1: " << rri.rank1 << "| r2: " << rri.rank2 << ")";
    }
} THRILL_ATTRIBUTE_PACKED;

template <typename Char>
struct Index3 {
    size_t index;
    size_t next;
    Char   ch;

    friend std::ostream& operator << (std::ostream& os, const Index3& i) {
        return os << "(index=" << i.index << " next=" << i.next << " ch=" << i.ch << ")";
    }
} THRILL_ATTRIBUTE_PACKED;

template <typename InputDIA, typename SuffixArrayDIA>
bool CheckSA(const InputDIA& input, const SuffixArrayDIA& suffix_array) {

    Context& ctx = input.ctx();

    using Char = typename InputDIA::ValueType;
    using Index3 = ::Index3<Char>;

    size_t input_size = input.Size();

    auto isa_pair =
        suffix_array
        // build tuples with index: (SA[i]) -> (i, SA[i]),
        .Zip(Generate(ctx, input_size),
             [](size_t sa, size_t i) {
                 return IndexRank { sa, i };
             })
        // take (i, SA[i]) and sort to (ISA[i], i)
        .Sort([](const IndexRank& a, const IndexRank& b) {
                  return a.index < b.index;
              });

    // Zip (ISA[i], i) with [0,n) and check that the second component was a
    // permutation of [0,n)
    size_t perm_check =
        isa_pair
        .Zip(Generate(ctx, input_size),
             [](const IndexRank& ir, size_t index) -> size_t {
                 return ir.index == index ? 0 : 1;
             })
        // sum over all boolean values.
        .Sum();

    if (perm_check != 0) {
        LOG1 << "Error: suffix array is not a permutation of 0..n-1.";
        return false;
    }

    using IndexPair = std::pair<size_t, size_t>;

    auto order_check =
        isa_pair
        // extract ISA[i]
        .Map([](const IndexRank& ir) { return ir.rank; })
        // build (ISA[i], ISA[i+1], T[i])
        .template FlatWindow<IndexPair>(
            2, [input_size](size_t index, const RingBuffer<size_t>& rb, auto emit) {
                emit(IndexPair { rb[0], rb[1] });
                if (index == input_size - 2) {
                    // emit sentinel at end
                    emit(IndexPair { rb[1], input_size });
                }
            })
        .Zip(input,
             [](const std::pair<size_t, size_t>& isa_pair, const Char& ch) {
                 return Index3 { isa_pair.first, isa_pair.second, ch };
             })
        // and sort to (i, ISA[SA[i]+1], T[SA[i]])
        .Sort([](const Index3& a, const Index3& b) {
                  return a.index < b.index;
              });

    // order_check.Print("order_check");

    size_t order_check_sum =
        order_check
        // check that no pair violates the order
        .Window(2, [input_size](size_t index, const RingBuffer<Index3>& rb) -> size_t {

                    if (rb[0].ch > rb[1].ch) {
                        // simple check of first character of suffix failed.
                        LOG1 << "Error: suffix array position "
                             << index << " ordered incorrectly.";
                        return 1;
                    }
                    else if (rb[0].ch == rb[1].ch) {
                        if (rb[1].next == input_size) {
                            // last suffix of string must be first among those with
                            // same first character
                            LOG1 << "Error: suffix array position "
                                 << index << " ordered incorrectly.";
                            return 1;
                        }
                        if (rb[0].next != input_size && rb[0].next > rb[1].next) {
                            // positions SA[i] and SA[i-1] has same first character
                            // but their suffixes are ordered incorrectly: the
                            // suffix position of SA[i] is given by ISA[SA[i]]
                            LOG1 << "Error: suffix array position "
                                 << index << " ordered incorrectly.";
                            return 1;
                        }
                    }
                    // else (rb[0].ch < rb[1].ch) -> okay.
                    return 0;
                })
        .Sum();

    return (order_check_sum == 0);
}

template <typename InputDIA>
DIA<size_t> PrefixDoubling(Context& ctx, const InputDIA& input_dia, size_t input_size) {
    
    using Char = typename InputDIA::ValueType;
    using IndexOneMer = ::IndexOneMer<Char>;

    auto one_mers_sorted = 
        input_dia
        .template FlatWindow<IndexOneMer>(
            2,
            [input_size](size_t index, const RingBuffer<Char>& rb, auto emit) {
                emit(IndexOneMer {index, rb[0]});
                if(index == input_size - 2) emit(IndexOneMer {index + 1, rb[1]});
        })
        .Sort([](const IndexOneMer& a, const IndexOneMer& b) {
            return a.t < b.t;
        }).Keep();

    if(debug_print)
        one_mers_sorted.Print("one_mers_sorted");

    DIA<size_t> sa =
        one_mers_sorted
        .Map([](const IndexOneMer& iom) {
            return iom.index;
        }).Collapse();

    if (debug_print)
        sa.Print("sa");

    DIA<size_t> rebucket =
        one_mers_sorted
        .template FlatWindow<size_t>(
            2,
            [input_size](size_t index, const RingBuffer<IndexOneMer>& rb, auto emit) {
                if (index == 0) emit(0);
                if (rb[0].t == rb[1].t) emit(0);
                else emit(index + 1);
                if (index == input_size - 2) {
                    if (rb[0].t == rb[1].t) emit(0);
                    else emit(index + 2);
                }
        })
        .PrefixSum([](const size_t a, const size_t b) {
            return a > b ? a : b;
        });

    if (debug_print)
        rebucket.Print("rebucket");

    uint8_t shifted_exp = 1;

    while(true) {

        DIA<IndexRank> isa =
            sa
            .Zip(
                rebucket,
                [](size_t sa, size_t rb) {
                    return IndexRank {rb, sa};
            })
            .Sort([](const IndexRank& a, const IndexRank& b) {
                return a.rank < b.rank;   
            });

        if (debug_print)
            isa.Print("isa");
        LOG << "Computed the ISA";

        size_t shift_by = 1 << shifted_exp++;
        LOG << "Shift the ISA by " << shift_by << " positions";

        DIA<IndexRankRank> triple_sorted =
            isa
            .template FlatWindow<IndexRankRank>(
                shift_by,
                [input_size, shift_by](size_t index, const RingBuffer<IndexRank>& rb, auto emit) {
                    emit(IndexRankRank {rb[0].rank, rb[shift_by - 1].index, rb[0].index});
                    if(index == input_size - shift_by)
                        for(size_t i = 1; i < input_size - index; ++i)
                            emit(IndexRankRank {rb[i].rank, 0, rb[i].index});
                }
            )
            .Sort([](const IndexRankRank& a, const IndexRankRank& b) {
                if (a.rank1 == b.rank1) {
                    if (a.rank2 == b.rank2) return a.index < b.index;
                    else return a.rank2 < b.rank2;
                } else return a.rank1 < b.rank1;
            });
        LOG << "Sorted the triples";

        size_t non_singletons =
            triple_sorted
            .template FlatWindow<uint8_t>(
                2,
                [](size_t /*index*/, const RingBuffer<IndexRankRank>& rb, auto emit) {
                    if (rb[0].rank1 == rb[1].rank1 and rb[0].rank2 == rb[1].rank2)
                        emit(0);
                }
            ).Size();

        LOG << "Computed the number of non singletons";

        sa =
            triple_sorted
            .Map([](const IndexRankRank& rri) {
                return rri.index;
        }).Collapse();

        if (debug_print)
            sa.Print("sa");
        // If each suffix is unique regarding their 2h-prefix, we have computed
        // the suffix array and can return it. 
        if (non_singletons == 0) {
            die_unless(CheckSA(input_dia, sa));
            return sa;
        }

        rebucket =
            triple_sorted
            .template FlatWindow<size_t>(
                2,
                [input_size](size_t index, const RingBuffer<IndexRankRank>& rb, auto emit) {
                    if (index == 0) emit(0);
                    if (rb[0].rank1 == rb[1].rank1 and rb[0].rank2 == rb[1].rank2)
                        emit(0);
                    else
                        emit(index + 1);
                    if (index == input_size - 2) {
                        if (rb[0].rank1 == rb[1].rank1 and rb[0].rank2 == rb[1].rank2)
                            emit(0);
                        else
                            emit(index + 2);
                    }
            })
            .PrefixSum([](const size_t a, const size_t b) {
                return a > b ? a : b;
            });

        if (debug_print)
            rebucket.Print("rebucket");
        LOG << "Rebucket the partial SA";
    }
}

/*!
{'fraction_non_alphanumeric': 0.14823310939974876, 'fraction_numerical': 0.011469768966082254, 'mean_word_length': 1.7005899705014749, 'pattern_counts': {'":': 0, '<': 272, '<?xml version=': 0, '>': 119, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1451686', 'n_tokens_mistral': 5847, 'n_tokens_neox': 5538, 'n_words': 1356}