# Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world.

```// Contains get_min_count, the core optimization of the spreadsort algorithm.
// Also has other helper functions commonly useful across variants.

//          Copyright Steven J. Ross 2001 - 2014.
//    (See accompanying file LICENSE_1_0.txt or copy at

/*
Some improvements suggested by:
Phil Endecott and Frank Gennari
*/

#include <algorithm>
#include <vector>
#include <cstring>
#include <limits>
#include <functional>
#include <boost/static_assert.hpp>
#include <boost/sort/pdqsort/pdqsort.hpp>
#include <boost/cstdint.hpp>

namespace boost {
namespace sort {
namespace detail {
//This only works on unsigned data types
template <typename T>
inline unsigned
rough_log_2_size(const T& input)
{
unsigned result = 0;
//The && is necessary on some compilers to avoid infinite loops
//it doesn't significantly impair performance
while ((result < (8*sizeof(T))) && (input >> result)) ++result;
return result;
}

//Gets the minimum size to call spreadsort on to control worst-case runtime.
//This is called for a set of bins, instead of bin-by-bin, to minimize
//This could be replaced by a lookup table of sizeof(Div_type)*8 but this
//function is more general.
template<unsigned log_mean_bin_size,
unsigned log_min_split_count, unsigned log_finishing_count>
inline size_t
get_min_count(unsigned log_range)
{
const size_t typed_one = 1;
const unsigned min_size = log_mean_bin_size + log_min_split_count;
//Assuring that constants have valid settings
BOOST_STATIC_ASSERT(log_min_split_count <= max_splits &&
log_min_split_count > 0);
BOOST_STATIC_ASSERT(max_splits > 1 &&
max_splits < (8 * sizeof(unsigned)));
BOOST_STATIC_ASSERT(max_finishing_splits >= max_splits &&
max_finishing_splits < (8 * sizeof(unsigned)));
BOOST_STATIC_ASSERT(log_mean_bin_size >= 0);
BOOST_STATIC_ASSERT(log_finishing_count >= 0);
//if we can complete in one iteration, do so
//This first check allows the compiler to optimize never-executed code out
if (log_finishing_count < min_size) {
if (log_range <= min_size && log_range <= max_splits) {
//Return no smaller than a certain minimum limit
if (log_range <= log_finishing_count)
return typed_one << log_finishing_count;
return typed_one << log_range;
}
}
const unsigned base_iterations = max_splits - log_min_split_count;
//sum of n to n + x = ((x + 1) * (n + (n + x)))/2 + log_mean_bin_size
const unsigned base_range =
((base_iterations + 1) * (max_splits + log_min_split_count))/2
+ log_mean_bin_size;
//Calculating the required number of iterations, and returning
//1 << (iteration_count + min_size)
if (log_range < base_range) {
unsigned result = log_min_split_count;
for (unsigned offset = min_size; offset < log_range;
offset += ++result);
//Preventing overflow; this situation shouldn't occur
if ((result + log_mean_bin_size) >= (8 * sizeof(size_t)))
return typed_one << ((8 * sizeof(size_t)) - 1);
return typed_one << (result + log_mean_bin_size);
}
//A quick division can calculate the worst-case runtime for larger ranges
unsigned remainder = log_range - base_range;
//the max_splits - 1 is used to calculate the ceiling of the division
unsigned bit_length = ((((max_splits - 1) + remainder)/max_splits)
+ base_iterations + min_size);
//Preventing overflow; this situation shouldn't occur
if (bit_length >= (8 * sizeof(size_t)))
return typed_one << ((8 * sizeof(size_t)) - 1);
//n(log_range)/max_splits + C, optimizing worst-case performance
return typed_one << bit_length;
}

// Resizes the bin cache and bin sizes, and initializes each bin size to 0.
template <class RandomAccessIter>
inline RandomAccessIter *
size_bins(size_t *bin_sizes, std::vector<RandomAccessIter>
&bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
{
// Clear the bin sizes
for (size_t u = 0; u < bin_count; u++)
bin_sizes[u] = 0;
//Make sure there is space for the bins
cache_end = cache_offset + bin_count;
if (cache_end > bin_cache.size())
bin_cache.resize(cache_end);
return &(bin_cache[cache_offset]);
}
}
}
}
}

#endif
```
{"ft_lang_label":"__label__en","ft_lang_prob":0.5762149,"math_prob":0.9696985,"size":4437,"snap":"2022-40-2023-06","text_gpt3_token_len":1070,"char_repetition_ratio":0.1355741,"word_repetition_ratio":0.039076377,"special_character_ratio":0.27834123,"punctuation_ratio":0.1270903,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99205047,"pos_list":[0,1,2],"im_url_duplicate_count":[null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-02-06T12:43:30Z\",\"WARC-Record-ID\":\"<urn:uuid:478315d6-b745-4153-88f4-e79dbc030895>\",\"Content-Length\":\"9040\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:69fd86b5-5e63-4c9c-8432-70393e77cb52>\",\"WARC-Concurrent-To\":\"<urn:uuid:6f1769a3-1fc1-4e6f-b179-e12fe227eea8>\",\"WARC-IP-Address\":\"146.20.110.251\",\"WARC-Target-URI\":\"https://www.boost.org/doc/libs/1_79_0/boost/sort/spreadsort/detail/spreadsort_common.hpp\",\"WARC-Payload-Digest\":\"sha1:MX4I2SFWBFCZFKRURFH5JYY4MZAN72FN\",\"WARC-Block-Digest\":\"sha1:IEDYSUT3XD2HXB4GIQC3JIK6EGMZA357\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-06/CC-MAIN-2023-06_segments_1674764500339.37_warc_CC-MAIN-20230206113934-20230206143934-00655.warc.gz\"}"}