text:
#include "IndriPruneIndex.h"

#include <algorithm>
#include <string>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include <boost/algorithm/string.hpp>
#include <boost/bind.hpp>
#include <boost/dynamic_bitset.hpp>
#include <boost/foreach.hpp>
#include <boost/format.hpp>
#include <boost/function.hpp>

// FIXME: check if this quick fix is appropriate
#define __atomic_add __gnu_cxx::__atomic_add

#include "indri/CompressedCollection.hpp"
#include "indri/DeletedDocumentList.hpp"
#include "indri/DiskIndex.hpp"
#include "indri/IndexWriter.hpp"
#include "indri/Parameters.hpp"
#include "indri/Path.hpp"
#include "indri/Repository.hpp"
#include "indri/TermScoreFunctionFactory.hpp"

#include "BinnedFilter.h"
#include "DocumentCentricTermScoreFunction.h"
#include "FilteredIndex.h"
#include "GainFunction.h"
#include "QuantileSampler.h"
#include "RunningStat.h"

indri_contrib::DocumentCentricTermScoreFunction*
getDocumentCentricTermScoreFunction(const std::string& stringSpec,
				    double documentLength, double collectionLength, int documentCount)
{
    // Notation:
    //   collectionLength    := N  (collection length, in # of words)
    //   documentCount       := D  (total # of documents)
    //   documentLength      := DL (document length, in # of words)
    //
    // When invoked, pass 3 parameters:
    //   termCount           := TF (term frequency in some document)
    //   collectionTermCount := CF (collection term frequency)
    //   documentFrequency   := DF (document frequency, in # of docs)
    indri::api::Parameters spec;
    parseSpec(spec, stringSpec);
    std::string method = spec.get("method", "dirichlet");

    if (method == "dirichlet" || method == "d" || method == "dir") {
	// dirichlet -- takes parameter "mu"
	double mu = spec.get("mu", 2500);
	return new indri_contrib::DirichletDocumentCentricTermScoreFunction(
	    mu, documentLength, collectionLength);
    }
    else if (method == "linear" || method == "jm" || method == "jelinek-mercer") {
	// jelinek-mercer -- can take parameters collectionLambda (or just lambda) and documentLambda
	double collectionLambda = spec.exists("collectionLambda")?
	    spec.get("collectionLambda", 0.4): spec.get("lambda", 0.4);
	return new indri_contrib::JelinekMercerDocumentCentricTermScoreFunction(
	    collectionLambda, documentLength, collectionLength);
    }
    else if (method == "tfidf" || method == "okapi") {
	double k1 = spec.get("k1", 1.2);
	double b = spec.get("b", 0.75);
	double k3 = spec.get("k3", 7);
	int qtf = spec.get("qtf", 1);

	return new indri_contrib::TFIDFDocumentCentricTermScoreFunction(
	    qtf, k1, b, k3, (method == "okapi"), documentLength, collectionLength, documentCount);
    }
    else if (method == "kld") {
	double collectionLambda = spec.exists("collectionLambda")?
	    spec.get("collectionLambda", 0.0): spec.get("lambda", 0.0);
	return new indri_contrib::KLDivergenceDocumentCentricTermScoreFunction(
	    collectionLambda, documentLength, collectionLength);
    }
    else die(boost::format("No support for method '%s'") % method);
}

// Weight
//
typedef std::vector<double> Weight;

// LazyVectorLoader
//
class LazyVectorLoader {
    std::ifstream _in;
    std::string _buf;
    std::istringstream _linein;

public:
    LazyVectorLoader(std::string guardPath): _in(guardPath) { }

    bool hasNext() const { return static_cast<bool>(_in); }

    void next(std::unordered_set<int>& v) {
	v.clear();

	if (getline(_in, _buf)) {
	    _linein.str(_buf);
	    _linein.clear();

	    int n;
	    while (_linein >> n) v.insert(n);
	}
    }
};

// Generalized uniform pruning
//
template<class GainFunction>
void generalized_uniform_pruning(indri::index::Index& index,
				 indri::api::Parameters& parameters,
				 Weight& weight,
				 indri_contrib::QuantileSampler* sampler,
				 indri_contrib::BinnedFilter* filter)
{
    string rule = parameters.get("rule", "method:dir");
    double epsilon = parameters.get("epsilon", 0.0);
    double scale = parameters.get("scale", 1.0);
    bool softmax = parameters.get("softmax", 0);

    string partial_gain = parameters.get("partialGain", "");
    bool point_eval_exclusive = (partial_gain == "exclusive");
    bool point_eval_inclusive = (partial_gain == "inclusive");

    string rank_transform = parameters.get("rankTransform", "");
    bool step_transform = (rank_transform == "step");
    bool uniform_transform = (rank_transform == "uniform");

    unique_ptr<LazyVectorLoader> guardLoader;
    if (parameters.exists("guard")) {
	string guardPath = parameters["guard"];
	guardLoader = unique_ptr<LazyVectorLoader>(new LazyVectorLoader(guardPath));
    }

    // Initialize the gain function
    GainFunction gain;
    gain.loadParameters(parameters);

    // There are totally N term occurrences in D documents
    long N = index.termCount();
    int D = index.documentCount();

    vector<int> CF_cache;
    CF_cache.push_back(0);
    vector<int> DF_cache;
    DF_cache.push_back(0);

    int T = index.uniqueTermCount();
    vector<int> term2seq(T + 1); // map termID to seq # in inverted list
    term2seq[0] = 0;
    // unordered_map<string, int> pos;

    // Pass 1: Term-based scan, for setting up (empty) bitmaps
    {
	unique_ptr<indri::index::DocListFileIterator>
	    docListFileIterator(index.docListFileIterator());
	int seqID = 0;

	for (docListFileIterator->startIteration();
	     !docListFileIterator->finished();
	     docListFileIterator->nextEntry())
	{
	    indri::index::DocListFileIterator::DocListData* docListData = docListFileIterator->currentEntry();
	    assert(docListData);

	    indri::index::TermData* termData = docListData->termData;
	    assert(termData);

	    indri::index::DocListIterator* docListIterator = docListData->iterator;
	    assert(docListIterator);

	    ++seqID;
	    term2seq[index.term(termData->term)] = seqID;

	    int CF = termData->corpus.totalCount; // collection term frequency
	    CF_cache.push_back(CF);

	    int DF = termData->corpus.documentCount; // document frequency
	    DF_cache.push_back(DF);

	    while (!docListIterator->finished())
		docListIterator->nextEntry(D + 1);

	    if (filter) {
		boost::dynamic_bitset<unsigned long> bitmap;
		filter->add(bitmap);
	    }
	}
    }

    // Pass 2: Document-based scan, to compute scores
    {
	unique_ptr<indri::index::TermListFileIterator>
	    termListFileIterator(index.termListFileIterator());

	unordered_map<lemur::api::TERMID_T, int> bag;
	vector<pair<lemur::api::TERMID_T, double>> prob;
	lemur::api::DOCID_T docID = 0;

	unordered_set<int> guards;

	for (termListFileIterator->startIteration();
	     !termListFileIterator->finished();
	     termListFileIterator->nextEntry())
	{
	    ++docID;

	    indri::index::TermList* termList = termListFileIterator->currentEntry();
	    assert(termList);

	    bag.clear();
	    const indri::utility::greedy_vector<lemur::api::TERMID_T>& vec = termList->terms();
	    for (size_t i = 0; i < vec.size(); ++i) ++bag[vec[i]];

	    int DL = vec.size();
	    unique_ptr<indri_contrib::DocumentCentricTermScoreFunction> scoreFunction(
		getDocumentCentricTermScoreFunction(rule, DL, N, D));

	    prob.clear();
	    for (unordered_map<lemur::api::TERMID_T, int>::const_iterator iter =
		 bag.begin(); iter != bag.end(); ++iter)
	    {
		lemur::api::TERMID_T seqID = term2seq[iter->first];
		if (seqID == 0) continue; // FIXME: a quick hack for removing OOVs

		int TF = iter->second;
		double probScore = scoreFunction->compute(TF, CF_cache[seqID], DF_cache[seqID]);
		prob.push_back(make_pair(seqID, probScore));
	    }

	    if (!scoreFunction->isProbability()) {
		double sum = 0.0;
		for (size_t i = 0; i < prob.size(); ++i) {
		    if (prob[i].second < 0) prob[i].second = 0;
		    sum += prob[i].second;
		}

		for (size_t i = 0; i < prob.size(); ++i)
		    prob[i].second = scale * prob[i].second / sum;

		if (softmax) {
		    sum = 0.0;
		    for (size_t i = 0; i < prob.size(); ++i) {
			prob[i].second = std::exp(prob[i].second);
			sum += prob[i].second;
		    }

		    for (size_t i = 0; i < prob.size(); ++i)
			prob[i].second /= sum;
		}
	    }

	    if (guardLoader)
		guardLoader->next(guards);

	    if (!prob.empty()) {
		double cumprob = 0.0;
		int offset = 0;

		if (!guards.empty()) {
		    for (size_t i = 0; i < prob.size(); ++i) {
			if (guards.find(prob[i].first) != guards.end()) {
			    swap(prob[offset], prob[i]);
			    cumprob += prob[offset++].second;
			}
		    }
		}

		stable_sort(prob.begin() + offset, prob.end(),
			    greater_value<lemur::api::TERMID_T, double>());

		if (step_transform) {
		    double step = 1.0 / prob.size();
		    double sum = 0.5 * (prob.size() + 1);
		    for (size_t i = 0; i < prob.size(); ++i)
			prob[i].second = (1.0 - i * step) / sum;
		    cumprob = 0.0;
		    offset = 0;
		}
		else if (uniform_transform) {
		    double step = 1.0 / prob.size();
		    for (size_t i = 0; i < prob.size(); ++i)
			prob[i].second = step;
		    cumprob = 0.0;
		    offset = 0;
		}

		double docWeight = weight[docID];
		double cumgain0 = docWeight * gain(0.0);
		double cumgain = docWeight * gain(cumprob); // save for later

		for (size_t i = offset; i < prob.size(); ++i) {
		    cumprob += prob[i].second;
		    prob[i].second = docWeight * gain(cumprob);
		}

		if (point_eval_inclusive) {
		    double shift = gain(1.0);
		    for (size_t i = 0; i < prob.size(); ++i)
			prob[i].second = shift - prob[i].second;
		}
		else if (point_eval_exclusive) {
		    double shift = gain(1.0);
		    for (size_t i = prob.size() - 1; i > offset; --i)
			prob[i].second = shift - prob[i - 1].second;
		    prob[offset].second = shift - cumgain;
		}
		else {
		    for (size_t i = prob.size() - 1; i > offset; --i)
			prob[i].second -= prob[i - 1].second;
		    prob[offset].second -= cumgain;
		}

		if (sampler)
		    for (size_t i = 0; i < prob.size(); ++i)
			sampler->add(prob[i].second);

		if (filter) {
		    for (size_t i = 0; i < offset; ++i) {
			lemur::api::TERMID_T seqID = prob[i].first;
			filter->operator[](seqID - 1).push_back(false);
		    }

		    for (size_t i = offset; i < prob.size(); ++i) {
			lemur::api::TERMID_T seqID = prob[i].first;
			double weighted_gain = prob[i].second;

			if (seqID)
			    filter->operator[](seqID - 1).push_back(weighted_gain < epsilon);
		    }
		}
	    }
	}
    }
}

// PowerFunction
//
struct NegativeExponentPower: std::unary_function<double, double> {
    int minusN;
    NegativeExponentPower(int n): minusN(-n) {}
    double operator()(double p) { return std::pow(p, minusN); }
};

struct NegativeOnePower: std::unary_function<double, double> {
    double operator()(double p) { return 1.0 / p; }
};

// Renyi divergence of infinite order
//
void renyi_divergence_infinite_order(indri::index::Index& index,
				     indri::api::Parameters& parameters,
				     Weight& weight,
				     indri_contrib::QuantileSampler* sampler,
				     indri_contrib::BinnedFilter* filter)
{
    string rule = parameters.get("rule", "method:dir");
    double epsilon = parameters.get("epsilon", 0.0);
    double scale = parameters.get("scale", 1.0);
    bool softmax = parameters.get("softmax", 0);
    int cardinality = parameters.get("cardinality", 1);

    boost::function<double(double)> power_function;
    if (cardinality == 1)
	power_function = NegativeOnePower();
    else
	power_function = NegativeExponentPower(cardinality);

    // string partial_gain = parameters.get("partialGain", "");
    // bool point_eval_exclusive = (partial_gain == "exclusive");
    // bool point_eval_inclusive = (partial_gain == "inclusive");

    string rank_transform = parameters.get("rankTransform", "");
    bool step_transform = (rank_transform == "step");
    bool uniform_transform = (rank_transform == "uniform");

    unique_ptr<LazyVectorLoader> guardLoader;
    if (parameters.exists("guard")) {
	string guardPath = parameters["guard"];
	guardLoader = unique_ptr<LazyVectorLoader>(new LazyVectorLoader(guardPath));
    }

    // There are totally N term occurrences in D documents
    long N = index.termCount();
    int D = index.documentCount();

    vector<int> CF_cache;
    CF_cache.push_back(0);
    vector<int> DF_cache;
    DF_cache.push_back(0);

    int T = index.uniqueTermCount();
    vector<int> term2seq(T + 1); // map termID to seq # in inverted list
    term2seq[0] = 0;
    // unordered_map<string, int> pos;

    // Pass 1: Term-based scan, for setting up (empty) bitmaps
    {
	unique_ptr<indri::index::DocListFileIterator>
	    docListFileIterator(index.docListFileIterator());
	int seqID = 0;

	for (docListFileIterator->startIteration();
	     !docListFileIterator->finished();
	     docListFileIterator->nextEntry())
	{
	    indri::index::DocListFileIterator::DocListData* docListData = docListFileIterator->currentEntry();
	    assert(docListData);

	    indri::index::TermData* termData = docListData->termData;
	    assert(termData);

	    indri::index::DocListIterator* docListIterator = docListData->iterator;
	    assert(docListIterator);

	    ++seqID;
	    term2seq[index.term(termData->term)] = seqID;

	    int CF = termData->corpus.totalCount; // collection term frequency
	    CF_cache.push_back(CF);

	    int DF = termData->corpus.documentCount; // document frequency
	    DF_cache.push_back(DF);

	    while (!docListIterator->finished())
		docListIterator->nextEntry(D + 1);

	    if (filter) {
		boost::dynamic_bitset<unsigned long> bitmap;
		filter->add(bitmap);
	    }
	}
    }

    // Pass 2: Document-based scan, to compute scores
    {
	unique_ptr<indri::index::TermListFileIterator>
	    termListFileIterator(index.termListFileIterator());

	unordered_map<lemur::api::TERMID_T, int> bag;
	vector<pair<lemur::api::TERMID_T, double>> prob;
	lemur::api::DOCID_T docID = 0;

	unordered_set<int> guards;

	for (termListFileIterator->startIteration();
	     !termListFileIterator->finished();
	     termListFileIterator->nextEntry())
	{
	    ++docID;

	    indri::index::TermList* termList = termListFileIterator->currentEntry();
	    assert(termList);

	    bag.clear();
	    const indri::utility::greedy_vector<lemur::api::TERMID_T>& vec = termList->terms();
	    for (size_t i = 0; i < vec.size(); ++i) ++bag[vec[i]];

	    int DL = vec.size();
	    unique_ptr<indri_contrib::DocumentCentricTermScoreFunction> scoreFunction(
		getDocumentCentricTermScoreFunction(rule, DL, N, D));

	    prob.clear();
	    for (unordered_map<lemur::api::TERMID_T, int>::const_iterator iter =
		 bag.begin(); iter != bag.end(); ++iter)
	    {
		lemur::api::TERMID_T seqID = term2seq[iter->first];
		if (seqID == 0) continue; // FIXME: a quick hack for removing OOVs

		int TF = iter->second;
		double probScore = scoreFunction->compute(TF, CF_cache[seqID], DF_cache[seqID]);
		prob.push_back(make_pair(seqID, probScore));
	    }

	    if (!scoreFunction->isProbability()) {
		double sum = 0.0;
		for (size_t i = 0; i < prob.size(); ++i) {
		    if (prob[i].second < 0) prob[i].second = 0;
		    sum += prob[i].second;
		}

		for (size_t i = 0; i < prob.size(); ++i)
		    prob[i].second = scale * prob[i].second / sum;

		if (softmax) {
		    sum = 0.0;
		    for (size_t i = 0; i < prob.size(); ++i) {
			prob[i].second = std::exp(prob[i].second);
			sum += prob[i].second;
		    }

		    for (size_t i = 0; i < prob.size(); ++i)
			prob[i].second /= sum;
		}
	    }

	    if (guardLoader)
		guardLoader->next(guards);

	    if (!prob.empty()) {
		double cumprob = 0.0;
		int offset = 0;

		if (!guards.empty()) {
		    for (size_t i = 0; i < prob.size(); ++i) {
			if (guards.find(prob[i].first) != guards.end()) {
			    swap(prob[offset], prob[i]);
			    cumprob += prob[offset++].second;
			}
		    }
		}

		stable_sort(prob.begin() + offset, prob.end(),
			    greater_value<lemur::api::TERMID_T, double>());

		if (step_transform) {
		    double step = 1.0 / prob.size();
		    double sum = 0.5 * (prob.size() + 1);
		    for (size_t i = 0; i < prob.size(); ++i)
			prob[i].second = (1.0 - i * step) / sum;
		    cumprob = 0.0;
		    offset = 0;
		}
		else if (uniform_transform) {
		    double step = 1.0 / prob.size();
		    for (size_t i = 0; i < prob.size(); ++i)
			prob[i].second = step;
		    cumprob = 0.0;
		    offset = 0;
		}

		for (size_t i = offset; i < prob.size(); ++i) {
		    cumprob += prob[i].second;
		    // prob[i].second = float(1.0) / cumprob;
		    prob[i].second = power_function(cumprob);
		}

		if (sampler)
		    for (size_t i = 0; i < prob.size(); ++i)  // FIXME: better go from offset instead of 0?
			sampler->add(prob[i].second);

		if (filter) {
		    for (size_t i = 0; i < offset; ++i) {
			lemur::api::TERMID_T seqID = prob[i].first;
			filter->operator[](seqID - 1).push_back(false);
		    }

		    for (size_t i = offset; i < prob.size(); ++i) {
			lemur::api::TERMID_T seqID = prob[i].first;
			double weighted_gain = prob[i].second;

			if (seqID)
			    filter->operator[](seqID - 1).push_back(weighted_gain < epsilon);
		    }
		}
	    }
	}
    }
}

// Document-centric pruning
//
void document_centric_pruning(indri::index::Index& index,
			      indri::api::Parameters& parameters,
			      Weight& weight,
			      indri_contrib::QuantileSampler* sampler,
			      indri_contrib::BinnedFilter* filter)
{
    string rule = parameters.get("rule", "method:tfidf");
    double lambda = parameters.get("epsilon", 0.0); // NOTE: lambda <=> epsilon

    // There are totally N term occurrences in D documents
    long N = index.termCount();
    int D = index.documentCount();

    vector<int> CF_cache;
    CF_cache.push_back(0);
    vector<int> DF_cache;
    DF_cache.push_back(0);

    int T = index.uniqueTermCount();
    vector<int> term2seq(T + 1); // map termID to seq # in inverted list
    term2seq[0] = 0;
    // unordered_map<string, int> pos;

    // Pass 1: Term-based scan, for setting up (empty) bitmaps
    {
	unique_ptr<indri::index::DocListFileIterator>
	    docListFileIterator(index.docListFileIterator());
	int seqID = 0;

	for (docListFileIterator->startIteration();
	     !docListFileIterator->finished();
	     docListFileIterator->nextEntry())
	{
	    indri::index::DocListFileIterator::DocListData* docListData = docListFileIterator->currentEntry();
	    assert(docListData);

	    indri::index::TermData* termData = docListData->termData;
	    assert(termData);

	    indri::index::DocListIterator* docListIterator = docListData->iterator;
	    assert(docListIterator);

	    ++seqID;
	    term2seq[index.term(termData->term)] = seqID;

	    int CF = termData->corpus.totalCount; // collection term frequency
	    CF_cache.push_back(CF);

	    int DF = termData->corpus.documentCount; // document frequency
	    DF_cache.push_back(DF);

	    while (!docListIterator->finished())
		docListIterator->nextEntry(D + 1);

	    if (filter) {
		boost::dynamic_bitset<unsigned long> bitmap;
		filter->add(bitmap);
	    }
	}
    }

    // Pass 2: Document-based scan, to compute scores
    {
	unique_ptr<indri::index::TermListFileIterator>
	    termListFileIterator(index.termListFileIterator());

	unordered_map<lemur::api::TERMID_T, int> bag;
	vector<pair<lemur::api::TERMID_T, double>> prob;
	lemur::api::DOCID_T docID = 0;

	for (termListFileIterator->startIteration();
	     !termListFileIterator->finished();
	     termListFileIterator->nextEntry())
	{
	    ++docID;

	    indri::index::TermList* termList = termListFileIterator->currentEntry();
	    assert(termList);

	    bag.clear();
	    const indri::utility::greedy_vector<lemur::api::TERMID_T>& vec = termList->terms();
	    for (size_t i = 0; i < vec.size(); ++i) ++bag[vec[i]];

	    int DL = vec.size();
	    unique_ptr<indri_contrib::DocumentCentricTermScoreFunction> scoreFunction(
		getDocumentCentricTermScoreFunction(rule, DL, N, D));

	    prob.clear();
	    for (unordered_map<lemur::api::TERMID_T, int>::const_iterator iter =
		 bag.begin(); iter != bag.end(); ++iter)
	    {
		lemur::api::TERMID_T seqID = term2seq[iter->first];
		if (seqID == 0) continue; // FIXME: a quick hack for removing OOVs

		int TF = iter->second;
		double probScore = scoreFunction->compute(TF, CF_cache[seqID], DF_cache[seqID]);
		prob.push_back(make_pair(seqID, probScore));
	    }

	    if (!prob.empty()) {
		stable_sort(prob.begin(), prob.end(),
			    greater_value<lemur::api::TERMID_T, double>());

		double step = 1.0 / prob.size();
		for (size_t i = 0; i < prob.size(); ++i)
		    prob[i].second = 1.0 - i * step; // comparable to lambda

		if (sampler) {
		    for (size_t i = 0; i < prob.size(); ++i)
			sampler->add(prob[i].second);
		}

		if (filter) {
		    for (size_t i = 0; i < prob.size(); ++i) {
			lemur::api::TERMID_T seqID = prob[i].first;
			double l = prob[i].second;
			filter->operator[](seqID - 1).push_back(l <= lambda); // note the ``equality''
		    }
		}
	    }
	}
    }
}

template<typename T> void _loadVectorFile(std::vector<T>& v, std::string path)
{
    std::ifstream in(path);
    T val;
    while (in >> val)
	v.push_back(val);
}

// Popularity-based pruning
//
void popularity_based_pruning(indri::index::Index& index,
			      indri::api::Parameters& parameters,
			      Weight& weight,
			      indri_contrib::QuantileSampler* sampler,
			      indri_contrib::BinnedFilter* filter)
{
    double epsilon = parameters.get("epsilon", 0.0);

    if (!parameters.exists("termGain"))
	die("Need to specify the path to term gain file (-termGain=PATH)");

    string termGainPath = parameters["termGain"];
    vector<double> termGain;
    termGain.push_back(0); // Orz...

    _loadVectorFile<double>(termGain, termGainPath);

    // long N = index.termCount();
    // int D = index.documentCount();

    unique_ptr<indri::index::DocListFileIterator>
	docListFileIterator(index.docListFileIterator());

    int seqID = 0;

    for (docListFileIterator->startIteration();
	 !docListFileIterator->finished();
	 docListFileIterator->nextEntry())
    {
	indri::index::DocListFileIterator::DocListData* docListData = docListFileIterator->currentEntry();
	assert(docListData);

	indri::index::TermData* termData = docListData->termData;
	assert(termData);

	indri::index::DocListIterator* docListIterator = docListData->iterator;
	assert(docListIterator);

	++seqID;

	// int CF = termData->corpus.totalCount; // collection term frequency
	int DF = termData->corpus.documentCount; // document frequency

	vector<double> scores;

	for (; !docListIterator->finished(); docListIterator->nextEntry()) {
	    indri::index::DocListIterator::DocumentData* documentData =
		docListIterator->currentEntry();

	    int docID = documentData->document;
	    scores.push_back(termGain[seqID]);
	}

	if (sampler)
	    sampler->add(scores.begin(), scores.end());

	if (filter) {
	    int offset = 0;
	    boost::dynamic_bitset<unsigned long> bitmap(DF); // allocate enough space first

	    BOOST_FOREACH (double score, scores) {
		if (score < epsilon)
		    bitmap.set(offset);
		++offset;
	    }

	    bitmap.resize(offset);
	    filter->add(bitmap);
	}
    }
}

// Two-sample two-proportion test (2N2P)
//
void two_proportion_test(indri::index::Index& index,
			 indri::api::Parameters& parameters,
			 Weight& weight,
			 indri_contrib::QuantileSampler* sampler,
			 indri_contrib::BinnedFilter* filter)
{
    if (parameters.exists("rule"))
	die("Argument -rule has no effect in prp_based_pruning");

    double epsilon = parameters.get("epsilon", 0.0);
    double h = parameters.get("h", 0.0);

    // There are totally N term occurrences in D documents
    long N = index.termCount();
    int D = index.documentCount();

    unique_ptr<indri::index::DocListFileIterator>
	docListFileIterator(index.docListFileIterator());

    for (docListFileIterator->startIteration();
	 !docListFileIterator->finished();
	 docListFileIterator->nextEntry())
    {
	indri::index::DocListFileIterator::DocListData* docListData = docListFileIterator->currentEntry();
	assert(docListData);

	indri::index::TermData* termData = docListData->termData;
	assert(termData);

	indri::index::DocListIterator* docListIterator = docListData->iterator;
	assert(docListIterator);

	int CF = termData->corpus.totalCount; // collection term frequency
	int DF = termData->corpus.documentCount; // document frequency

	double p_c = double(CF) / N;

	vector<double> scores;

	for (; !docListIterator->finished(); docListIterator->nextEntry()) {
	    indri::index::DocListIterator::DocumentData* documentData =
		docListIterator->currentEntry();

	    int docID = documentData->document;
	    int TF = documentData->positions.size(); // term frequency (in this document)
	    int DL = index.documentLength(docID);

	    double p_d = double(TF) / DL;
	    double P = double(TF + CF) / (DL + N);
	    double scale = (1.0 / DL) + (1.0 / N);

	    double score = (p_d + p_c) /
		std::sqrt(P * (1 - P) * scale);
	    if (h > 0.0)
		score -= h * std::sqrt(scale);

	    scores.push_back(score);
	}

	if (sampler)
	    sampler->add(scores.begin(), scores.end());

	if (filter) {
	    int offset = 0;
	    boost::dynamic_bitset<unsigned long> bitmap(DF); // allocate enough space first

	    BOOST_FOREACH (double score, scores) {
		if (score < epsilon)
		    bitmap.set(offset);
		++offset;
	    }

	    bitmap.resize(offset);
	    filter->add(bitmap);
	}
    }
}

// Probability-ranking principle
//
void prp_based_pruning(indri::index::Index& index,
		       indri::api::Parameters& parameters,
		       Weight& weight,
		       indri_contrib::QuantileSampler* sampler,
		       indri_contrib::BinnedFilter* filter)
{
    if (parameters.exists("rule"))
	die("Argument -rule has no effect in prp_based_pruning");

    double epsilon = parameters.get("epsilon", 0.0);

    // There are totally N term occurrences in D documents
    long N = index.termCount();
    int D = index.documentCount();

    RunningStat stat;
    for (int i = 1; i <= D; ++i)
	stat.push(index.documentLength(i));

    double dlMu = stat.mean();
    double dlSigma = stat.standardDeviation();

    unique_ptr<indri::index::DocListFileIterator>
	docListFileIterator(index.docListFileIterator());

    for (docListFileIterator->startIteration();
	 !docListFileIterator->finished();
	 docListFileIterator->nextEntry())
    {
	indri::index::DocListFileIterator::DocListData* docListData = docListFileIterator->currentEntry();
	assert(docListData);

	indri::index::TermData* termData = docListData->termData;
	assert(termData);

	indri::index::DocListIterator* docListIterator = docListData->iterator;
	assert(docListIterator);

	int CF = termData->corpus.totalCount; // collection term frequency
	int DF = termData->corpus.documentCount; // document frequency

	// probability of term given nonrelevance p_q = p(q|C)
	double p_q = static_cast<double>(CF) / N;

	vector<double> scores;

	for (; !docListIterator->finished(); docListIterator->nextEntry()) {
	    indri::index::DocListIterator::DocumentData* documentData =
		docListIterator->currentEntry();

	    int docID = documentData->document;
	    int TF = documentData->positions.size(); // term frequency (in this document)
	    int DL = index.documentLength(docID);

	    // document prior p_d = p(r|D)
	    double p_d = 0.5 + 0.1 * std::tanh(double(DL - dlMu) / dlSigma);

	    // query likelihood p_r = p(q|D,r)
	    double p_r = 0.4 * double(TF) / DL + 0.6 * p_q;

	    double score = (p_r / p_q) * (p_d / (1.0 - p_d));
	    scores.push_back(score);
	}

	if (sampler)
	    sampler->add(scores.begin(), scores.end());

	if (filter) {
	    int offset = 0;
	    boost::dynamic_bitset<unsigned long> bitmap(DF); // allocate enough space first

	    BOOST_FOREACH (double score, scores) {
		if (score < epsilon)
		    bitmap.set(offset);
		++offset;
	    }

	    bitmap.resize(offset);
	    filter->add(bitmap);
	}
    }
}

// Uniform pruning
//
void uniform_pruning(indri::index::Index& index,
		     indri::api::Parameters& parameters,
		     Weight& weight,
		     indri_contrib::QuantileSampler* sampler,
		     indri_contrib::BinnedFilter* filter)
{
    string rule = parameters.get("rule", "method:tfidf");
    double epsilon = parameters.get("epsilon", 0.0);

    // There are totally N term occurrences in D documents
    long N = index.termCount();
    int D = index.documentCount();

    unique_ptr<indri::index::DocListFileIterator>
	docListFileIterator(index.docListFileIterator());

    for (docListFileIterator->startIteration();
	 !docListFileIterator->finished();
	 docListFileIterator->nextEntry())
    {
	indri::index::DocListFileIterator::DocListData* docListData = docListFileIterator->currentEntry();
	assert(docListData);

	indri::index::TermData* termData = docListData->termData;
	assert(termData);

	indri::index::DocListIterator* docListIterator = docListData->iterator;
	assert(docListIterator);

	int CF = termData->corpus.totalCount; // collection term frequency
	int DF = termData->corpus.documentCount; // document frequency

	unique_ptr<indri::query::TermScoreFunction> scoreFunction(
	    indri::query::TermScoreFunctionFactory::get(rule, CF, N, DF, D));
	vector<double> scores;

	for (; !docListIterator->finished(); docListIterator->nextEntry()) {
	    indri::index::DocListIterator::DocumentData* documentData =
		docListIterator->currentEntry();

	    int docID = documentData->document;
	    int TF = documentData->positions.size(); // term frequency (in this document)
	    int DL = index.documentLength(docID);

	    double logWeight = std::log(weight[docID]); // always a catch!
	    scores.push_back(logWeight + scoreFunction->scoreOccurrence(TF, DL));
	}

	if (sampler)
	    sampler->add(scores.begin(), scores.end());

	if (filter) {
	    int offset = 0;
	    boost::dynamic_bitset<unsigned long> bitmap(DF); // allocate enough space first

	    BOOST_FOREACH (double score, scores) {
		if (score < epsilon)
		    bitmap.set(offset);
		++offset;
	    }

	    bitmap.resize(offset);
	    filter->add(bitmap);
	}
    }
}

// Term-based pruning
//
void term_based_pruning(indri::index::Index& index,
			indri::api::Parameters& parameters,
			Weight& weight,
			indri_contrib::QuantileSampler* sampler,
			indri_contrib::BinnedFilter* filter)
{
    string rule = parameters.get("rule", "method:tfidf");
    int k = parameters.get("k", 10);
    double epsilon = parameters.get("epsilon", 0.0);

    // There are totally N term occurrences in D documents
    long N = index.termCount();
    int D = index.documentCount();

    unique_ptr<indri::index::DocListFileIterator>
	docListFileIterator(index.docListFileIterator());

    for (docListFileIterator->startIteration();
	 !docListFileIterator->finished();
	 docListFileIterator->nextEntry())
    {
	indri::index::DocListFileIterator::DocListData* docListData =
	    docListFileIterator->currentEntry();
	indri::index::TermData* termData = docListData->termData;
	indri::index::DocListIterator* docListIterator = docListData->iterator;

	int CF = termData->corpus.totalCount; // collection term frequency
	int DF = termData->corpus.documentCount; // document frequency

	unique_ptr<indri::query::TermScoreFunction> scoreFunction(
	    indri::query::TermScoreFunctionFactory::get(rule, CF, N, DF, D));
	vector<double> scores;

	for (; !docListIterator->finished(); docListIterator->nextEntry()) {
	    indri::index::DocListIterator::DocumentData* documentData =
		docListIterator->currentEntry();

	    int TF = documentData->positions.size(); // term frequency (in this document)
	    int DL = index.documentLength(documentData->document);
	    scores.push_back(scoreFunction->scoreOccurrence(TF, DL));
	}

	if (sampler) {
	    if (scores.size() > k) {
		vector<double> sorter(scores.begin(), scores.end());
		nth_element(sorter.begin(), sorter.begin() + k - 1, sorter.end(), greater<double>());

		// NOTE: This is just a hack for skipping negative scores
		//       (only works for okapi)
		double denom = sorter[k - 1];
		if (denom > 0) {
		    transform(sorter.begin(), sorter.end(), sorter.begin(),
			      boost::bind(divides<double>(), _1, denom));

		    sampler->add(sorter.begin(), sorter.end());
		}
	    }
	    else {
		double fake_score = 1.0 + 1.0 / k;
		sampler->add(scores.size(), fake_score);
	    }
	}

	if (filter) {
	    int offset = 0;
	    boost::dynamic_bitset<unsigned long> bitmap(DF); // allocate enough space first

	    if (scores.size() > k) {
		vector<double> sorter(scores.begin(), scores.end());
		nth_element(sorter.begin(), sorter.begin() + k - 1, sorter.end(), greater<double>());

		double z = sorter[k - 1] * epsilon;
		BOOST_FOREACH (double score, scores) {
		    if (score < z)
			bitmap.set(offset);
		    ++offset;
		}
	    }
	    else
		offset += scores.size();

	    bitmap.resize(offset);
	    filter->add(bitmap);
	}
    }
}

//--------------------------------------------------
// Handlers
//--------------------------------------------------
void compile_guard(indri::api::Parameters& parameters)
{
    using indri::file::Path;

    std::vector<std::string> requiredKeys = { "index", "output", "rule", "k" };
    requires(parameters, requiredKeys);

    std::string sourcePath = parameters["index"];
    std::string outputPath = parameters["output"];
    std::string rule = parameters.get("rule", "method:tfidf");
    int k = parameters.get("k", 10);

    indri::collection::Repository repo;
    repo.openRead(sourcePath);
    indri::index::Index& index = *((*repo.indexes())[0]);

    // There are totally N term occurrences in D documents
    long N = index.termCount();
    int D = index.documentCount();

    std::vector<std::vector<int>> inv(D + 1, std::vector<int>());
    int seqID = 0;

    unique_ptr<indri::index::DocListFileIterator>
	docListFileIterator(index.docListFileIterator());

    for (docListFileIterator->startIteration();
	 !docListFileIterator->finished();
	 docListFileIterator->nextEntry())
    {
	++seqID;

	indri::index::DocListFileIterator::DocListData* docListData =
	    docListFileIterator->currentEntry();
	indri::index::TermData* termData = docListData->termData;
	indri::index::DocListIterator* docListIterator = docListData->iterator;

	int CF = termData->corpus.totalCount; // collection term frequency
	int DF = termData->corpus.documentCount; // document frequency

	unique_ptr<indri::query::TermScoreFunction> scoreFunction(
	    indri::query::TermScoreFunctionFactory::get(rule, CF, N, DF, D));
	vector<double> scores;
	vector<lemur::api::DOCID_T> docids;

	for (; !docListIterator->finished(); docListIterator->nextEntry()) {
	    indri::index::DocListIterator::DocumentData* documentData =
		docListIterator->currentEntry();

	    int TF = documentData->positions.size(); // term frequency (in this document)
	    int DL = index.documentLength(documentData->document);
	    scores.push_back(scoreFunction->scoreOccurrence(TF, DL));
	    docids.push_back(documentData->document);
	}

	if (scores.size() > k) {
	    vector<double> sorter(scores.begin(), scores.end());
	    nth_element(sorter.begin(), sorter.begin() + k - 1, sorter.end(), greater<double>());

	    double z = sorter[k - 1];
	    for (size_t i = 0; i < scores.size(); ++i)
		if (scores[i] >= z)
		    inv[docids[i]].push_back(seqID);
	}
	else
	    for (size_t i = 0; i < docids.size(); ++i)
		inv[docids[i]].push_back(seqID);
    }

    std::ofstream out(outputPath.c_str());

    for (size_t i = 0; i < inv.size(); ++i) {
	for (size_t j = 0; j < inv[i].size(); ++j)
	    out << inv[i][j] << ' ';
	out << '\n';
    }
}

void compile_access(indri::api::Parameters& parameters) {
    using indri::file::Path;

    std::vector<std::string> requiredKeys = { "index", "viewFile", "output" };
    requires(parameters, requiredKeys);

    std::string sourcePath = parameters["index"];
    std::string viewPath = parameters["viewFile"];
    std::string outputPath = parameters["output"];

    indri::collection::Repository repo;
    repo.openRead(sourcePath);
    indri::collection::CompressedCollection& collection = *repo.collection();

    std::unordered_map<std::string, int> access;

    {
	std::ifstream vin(viewPath.c_str());
	std::string docno;

	while (vin >> docno) ++access[docno];
    }

    {
	std::ofstream out(outputPath.c_str());

	int D = (*repo.indexes())[0]->documentCount();
	for (size_t docID = 1; docID <= D; ++docID) {
	    std::string docno = collection.retrieveMetadatum(docID, "docno");

	    if (access.find(docno) != access.end())
		out << access[docno] << '\n';
	    else
		out << 0 << '\n';
	}
    }
}

void compile_term_gain(indri::api::Parameters& parameters) {
    using indri::file::Path;

    std::vector<std::string> requiredKeys = { "index", "queryFile", "hasCounts", "output" };
    requires(parameters, requiredKeys);

    std::string sourcePath = parameters["index"];
    std::string queryPath = parameters["queryFile"];
    std::string outputPath = parameters["output"];
    bool hasCounts = parameters.get("hasCounts", false);
    bool debug = parameters.get("debug", false);

    indri::collection::Repository repo;
    repo.openRead(sourcePath);
    indri::index::Index& index = *((*repo.indexes())[0]);

    // Step 1: accumulate stem counts
    std::unordered_map<std::string, int> stemPop;

    {
	std::unordered_map<std::string, int> bag;
	std::string term;

	std::ifstream in(queryPath.c_str());

	if (hasCounts) {
	    int queryCount;
	    std::string line;
	    std::istringstream line_in;

	    while (std::getline(in, line)) {
		line_in.str(line);
		line_in.clear();

		line_in >> queryCount;
		while (line_in >> term)
		    bag[term] += queryCount;
	    }
	}
	else
	    while (in >> term) ++bag[term];

	for (std::unordered_map<std::string, int>::iterator iter = bag.begin();
	     iter != bag.end(); ++iter)
	{
	    std::string stem = repo.processTerm(iter->first);
	    stemPop[stem] += iter->second;
	}
    }

    std::vector<double> termGain;
    std::vector<std::string> stems;
    std::vector<int> stemCounts;

    termGain.push_back(0);
    stems.push_back("");
    stemCounts.push_back(0);

    int D = index.documentCount();

    // Step 2: Term-based scan, for setting up (empty) bitmaps
    {
	unique_ptr<indri::index::DocListFileIterator>
	    docListFileIterator(index.docListFileIterator());

	for (docListFileIterator->startIteration();
	     !docListFileIterator->finished();
	     docListFileIterator->nextEntry())
	{
	    indri::index::DocListFileIterator::DocListData* docListData = docListFileIterator->currentEntry();
	    assert(docListData);

	    indri::index::TermData* termData = docListData->termData;
	    assert(termData);

	    int DF = termData->corpus.documentCount; // document frequency

	    std::unordered_map<std::string, int>::iterator match =
		stemPop.find(termData->term);

	    stems.push_back(termData->term);

	    if (match == stemPop.end()) {
		termGain.push_back(0);
		stemCounts.push_back(0);
	    }
	    else {
		termGain.push_back(static_cast<double>(match->second) / DF);
		stemCounts.push_back(match->second);
	    }

	    // Still needs to traverse to the end
	    indri::index::DocListIterator* docListIterator = docListData->iterator;
	    assert(docListIterator);

	    while (!docListIterator->finished())
		docListIterator->nextEntry(D + 1);
	}
    }

    // Step 3: Output
    {
	std::ofstream out(outputPath.c_str());

	if (debug)
	    for (size_t i = 1; i < termGain.size(); ++i)
		out << boost::format("%3.17f\t%d\t%s") % termGain[i] % stemCounts.at(i) % stems.at(i) << '\n';
	else
	    for (size_t i = 1; i < termGain.size(); ++i)
		out << boost::format("%3.17f") % termGain[i] << '\n';
    }
}

void compile_query_view(indri::api::Parameters& parameters) {
    using indri::file::Path;

    std::vector<std::string> requiredKeys = { "index", "queryFile", "viewFile", "output" };
    requires(parameters, requiredKeys);

    std::string sourcePath = parameters["index"];
    std::string queryPath = parameters["queryFile"];
    std::string viewPath = parameters["viewFile"];
    std::string outputPath = parameters["output"];

    indri::collection::Repository repo;
    repo.openRead(sourcePath);
    indri::index::Index& index = *((*repo.indexes())[0]);
    indri::collection::CompressedCollection& collection = *repo.collection();

    std::unordered_map<std::string, std::vector<lemur::api::DOCID_T>> post;

    {
	std::unordered_map<std::string, std::string> term2stem;

	std::ifstream qin(queryPath.c_str()), vin(viewPath.c_str());
	std::string line;
	std::istringstream iss;
	std::vector<std::string> stems;
	std::vector<std::string> docnos;
	std::vector<lemur::api::DOCID_T> docids;

	while (true) {

	    // first let us retrieve the stems
	    if (!getline(qin, line)) break;

	    boost::trim(line);

	    stems.clear();
	    boost::split(stems, line, boost::is_any_of(" "));
	    for (size_t i = 0; i < stems.size(); ++i) {
		if (term2stem.find(stems[i]) == term2stem.end())
		    term2stem[stems[i]] = repo.processTerm(stems[i]);
		stems[i] = term2stem[stems[i]];
	    }

	    // then we look at the document views
	    if (!getline(vin, line)) break;

	    boost::trim(line);

	    docnos.clear();
	    docids.clear();
	    boost::split(docnos, line, boost::is_any_of(" "));
	    for (size_t i = 0; i < docnos.size(); ++i) {
		std::vector<lemur::api::DOCID_T> ids =
		    collection.retrieveIDByMetadatum("docno", docnos[i]);
		docids.push_back(ids[0]);
	    }

	    // save this to the hashtable
	    for (size_t i = 0; i < stems.size(); ++i)
		for (size_t j = 0; j < docids.size(); ++j)
		    post[stems[i]].push_back(docids[j]);
	}
    }

    std::ofstream out(outputPath.c_str());

    for (std::unordered_map<std::string, std::vector<lemur::api::DOCID_T>>::iterator iter = post.begin();
	 iter != post.end(); ++iter)
    {
	std::vector<lemur::api::DOCID_T>& l = iter->second;
	std::sort(l.begin(), l.end());
	std::vector<lemur::api::DOCID_T>::iterator last = std::unique(l.begin(), l.end());
	l.erase(last, l.end());
    }

    int D = index.documentCount();

    {
	unique_ptr<indri::index::DocListFileIterator>
	    docListFileIterator(index.docListFileIterator());

	for (docListFileIterator->startIteration();
	     !docListFileIterator->finished();
	     docListFileIterator->nextEntry())
	{
	    indri::index::DocListFileIterator::DocListData* docListData = docListFileIterator->currentEntry();
	    assert(docListData);

	    indri::index::TermData* termData = docListData->termData;
	    assert(termData);

	    int DF = termData->corpus.documentCount; // document frequency

	    indri::index::DocListIterator* docListIterator = docListData->iterator;
	    assert(docListIterator);

	    if (post.find(termData->term) != post.end()) {
		std::vector<lemur::api::DOCID_T>& l = post[termData->term];
		std::vector<lemur::api::DOCID_T>::iterator curr = l.begin();

		size_t offset = 0;
		while (!docListIterator->finished() && curr != l.end()) {
		    ++offset;

		    indri::index::DocListIterator::DocumentData* docData = docListIterator->currentEntry();
		    lemur::api::DOCID_T docID = docData->document;

		    if (*curr == docID) {
			out << ' ' << offset;
			++curr;
		    }

		    docListIterator->nextEntry();
		}
	    }

	    out << '\n';

	    while (!docListIterator->finished())
		docListIterator->nextEntry(D + 1);
	}
    }
}

void prune_index(indri::api::Parameters& parameters) {
    using indri::file::Path;

    std::vector<std::string> requiredKeys = { "index", "method" };
    requires(parameters, requiredKeys);

    std::string sourcePath = parameters["index"];
    std::string method = parameters["method"];

    struct PruneMethod {
	typedef void (*Handler)(indri::index::Index&,
				indri::api::Parameters&,
				Weight&,
				indri_contrib::QuantileSampler*,
				indri_contrib::BinnedFilter*);

	std::string name;
	Handler handler;
    };

    std::vector<PruneMethod> listOfPruneMethods = {
	{ "gup_kl", generalized_uniform_pruning<LogarithmGain> },
	{ "gup_var", generalized_uniform_pruning<IdentityGain> },
	{ "gup_hellinger", generalized_uniform_pruning<SquareRootGain> },
	{ "gup_x2", generalized_uniform_pruning<MinusReciprocalGain> },
	{ "gup_renyi", generalized_uniform_pruning<MinusExponentialGain> },

	// { "guarded_x2", generalized_uniform_pruning<MinusReciprocalGain> },

	// { "mix_kl_x2", generalized_uniform_pruning<MixtureGain<LogarithmGain, MinusReciprocalGain>> },
	// { "mix_hellinger_x2", generalized_uniform_pruning<MixtureGain<SquareRootGain, MinusReciprocalGain>> },
	// { "mix_renyi_x2", generalized_uniform_pruning<MixtureGain<MinusExponentialGain, MinusReciprocalGain>> },

	{ "dcp", document_centric_pruning },
	{ "pp", popularity_based_pruning },
	{ "up", uniform_pruning },
	{ "tcp", term_based_pruning },
	{ "prp", prp_based_pruning },
	{ "2n2p", two_proportion_test },

	{ "infinite_renyi", renyi_divergence_infinite_order }
    };

    PruneMethod::Handler handler = 0;
    BOOST_FOREACH (const PruneMethod& pruneMethod, listOfPruneMethods) {
	if (method == pruneMethod.name) {
	    handler = pruneMethod.handler;
	    break;
	}
    }

    if (!handler)
	die(boost::format("No such method '%s'") % method);

    // Load up the old index
    indri::index::DiskIndex diskIndex;

    {
	indri::api::Parameters manifest;
	manifest.loadFile(Path::combine(sourcePath, "manifest"));
	diskIndex.open(Path::combine(sourcePath, "index"),
		       i64_to_string((INT64)manifest["indexes.index"]));
    }

    indri_contrib::BinnedFilter filter;

    int documentCount = diskIndex.documentCount();
    Weight weight(documentCount + 1, 1.0); // uniform weight

    if (parameters.exists("prior")) {
	std::string priorPath = parameters["prior"];
	double beta = parameters.get("beta", 0.0);

	indri::collection::Repository repo;
	repo.openRead(sourcePath);
	indri::collection::CompressedCollection* collection = repo.collection();
	weight.assign(documentCount + 1, 0.0);

	{
	    std::ifstream in(priorPath.c_str());
	    std::vector<lemur::api::DOCID_T> result;
	    double cumsum = 0.0;

	    std::string docno;
	    double prob;
	    while (in >> docno >> prob) {
		result = collection->retrieveIDByMetadatum("docno", docno);
		assert(result.size() == 1);
		weight[result.front()] = prob;
		cumsum += prob;
	    }

	    for (int i = 1; i <= documentCount; ++i) {
		if (weight[i] == 0.0) weight[i] = 1.0;
		else weight[i] = 1.0 + weight[i] / (1.0 - cumsum + beta) * documentCount;
	    }
	}
    }

    if (parameters.exists("estimate")) {
	indri::api::Parameters estimateSpec;
	parseSpec(estimateSpec, parameters.get("estimate"));

	std::string method = estimateSpec.get("method", "p2"); // default using p-square algorithm
	std::vector<double> poi = {
	    0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9,
	    0.91, 0.92, 0.93, 0.94, 0.95, 0.96, 0.97, 0.98, 0.99 };

	// for (double f = 0.1; f <= 0.9; f += 0.1) poi.push_back(f);
	// for (double f = 0.91; f <= 0.99; f += 0.01) poi.push_back(f);

	// Method 1: Bisection
	if (method == "bisection") {
	    double lb = estimateSpec.get("lb", 0.0);
	    double ub = estimateSpec.get("ub", 1.0);

	    std::unordered_map<double, double> estimates;

	    struct Bracket {
		double a, b;
		double f_a, f_b;
		std::vector<double> val;
	    };

	    Bracket root;
	    root.a = lb;
	    root.b = ub;
	    root.f_a = 0;
	    root.f_b = 1;
	    root.val = poi;

	    std::queue<Bracket> q;
	    q.push(root);

	    while (!q.empty()) {
		Bracket r = q.front();
		q.pop();

		std::cerr << boost::format("(%3.17f, %3.17f) -> (%3.17f, %3.17f): ") % r.a % r.b % r.f_a % r.f_b;
		BOOST_FOREACH (double v, r.val) {
		    std::cerr << v << ' ';
		}
		std::cerr << '\n';

		double p = (r.a + r.b) / 2;
		parameters.set("epsilon", p);
		handler(diskIndex, parameters, weight, 0, &filter);

		double f_p = filter.ratio();
		filter.clear();

		std::cerr << boost::format("  epsilon = %3.17f, rho = %3.17f") % p % f_p << '\n';

		const double SIGMA = 0.000000001; // change in x
		const double DELTA = 0.000001; // change in f(x)

		if (r.b - r.a <= SIGMA) {
		    estimates[p] = f_p;
		    BOOST_FOREACH (double v, r.val) {
			std::cerr << boost::format("  DONE %f") % v << '\n';
		    }
		}
		else {
		    Bracket r_ap, r_pb;
		    r_ap.a = r.a; r_ap.f_a = r.f_a;
		    r_ap.b = p; r_ap.f_b = f_p;
		    r_pb.a = p; r_pb.f_a = f_p;
		    r_pb.b = r.b; r_pb.f_b = r.f_b;

		    BOOST_FOREACH (double v, r.val) {
			if (v >= f_p - DELTA && v <= f_p + DELTA) {
			    estimates[p] = f_p;
			    std::cerr << boost::format("  DONE %f") % v << '\n';
			}
			else if (v < f_p - DELTA)
			    r_ap.val.push_back(v);
			else if (v > f_p + DELTA)
			    r_pb.val.push_back(v);
		    }

		    if (!r_ap.val.empty()) q.push(r_ap);
		    if (!r_pb.val.empty()) q.push(r_pb);
		}
	    }

	    std::vector<double> keys;
	    for (std::unordered_map<double, double>::iterator iter =
		 estimates.begin(); iter != estimates.end(); ++iter)
		keys.push_back(iter->first);

	    std::sort(keys.begin(), keys.end());
	    BOOST_FOREACH (double key, keys) {
		std::cout << boost::format("%3.17f\t%3.17f") % key % estimates[key] << '\n';
	    }
	}
	// Case 2: P-square algorithm
	else if (method == "p_square" || method == "p2") {
	    double step = estimateSpec.get("step", 0.1);
	    double window = estimateSpec.get("window", 0.0);

	    std::vector<double> points;

	    if (step > 0)
		for (double q = step; q < 1.0; q += step) {
		    if (window > 0) points.push_back(q - window);

		    points.push_back(q);

		    if (window > 0) points.push_back(q + window);
		}

	    std::stable_sort(points.begin(), points.end());

	    indri_contrib::PSquareQuantileSampler sampler(points);
	    handler(diskIndex, parameters, weight, &sampler, 0);

	    std::vector<double> estimates = sampler.query(poi);
	    for (size_t i = 0; i < poi.size(); ++i)
		std::cout << boost::format("%3.17f\t%3.17f") % estimates[i] % poi[i] << '\n';
	}
	// Case 3: Reservoir sampling
	else if (method == "reservoir") {
	    size_t reservoirSize = estimateSpec.get("size", 1000000);

	    indri_contrib::ReservoirQuantileSampler sampler(reservoirSize);
	    handler(diskIndex, parameters, weight, &sampler, 0);

	    std::vector<double> estimates = sampler.query(poi);
	    for (size_t i = 0; i < poi.size(); ++i)
		std::cout << boost::format("%3.17f\t%3.17f") % estimates[i] % poi[i] << '\n';
	}
	else
	    die(boost::format("No such estimation method '%s'") % method);
    }
    else {
	// The pruning method returns a prune (filter)
	handler(diskIndex, parameters, weight, 0, &filter);
	cout << filter.ratio() << '\n';

	indri_contrib::FilteredIndex<indri_contrib::BinnedFilter>
	    filteredIndex(diskIndex, filter);

	// Apply and produce a new index ONLY when the name is given
	if (parameters.exists("newindex")) {
	    string path = parameters["newindex"];
	    if (!Path::exists(path))
		Path::create(path);

	    // Load up the manifest
	    indri::api::Parameters manifest;
	    manifest.loadFile(Path::combine(sourcePath, "manifest"));

	    if (manifest["indexes.index"].size() > 1)
		die("Source contains more than one index (run 'dump-index compact' first)");

	    // Load up the deletedList
	    indri::index::DeletedDocumentList deletedList;
	    deletedList.read(Path::combine(sourcePath, "deleted"));

	    if (deletedList.deletedCount() > 0)
		die("Source has non-empty deleted list (run 'dump-index compact' first)");

	    // Write out the index
	    try {
		indri::index::IndexWriter writer;
		string indexPath = Path::combine(path, "index");
		if (!Path::exists(indexPath)) Path::create(indexPath);

		vector<indri::index::Index::FieldDescription> fieldDescriptions;
		writer.write(filteredIndex, fieldDescriptions, deletedList, Path::combine(indexPath, "0"));
	    }
	    catch (lemur::api::Exception& e) {
		// LEMUR_RETHROW(e, "sip");
		std::cout << e.what() << std::endl;
	    }

	    // Copy the compressed collection
	    {
		indri::collection::CompressedCollection sourceCollection, collection;
		sourceCollection.openRead(Path::combine(sourcePath, "collection"));

		string collectionPath = Path::combine(path, "collection");
		Path::create(collectionPath);
		collection.create(collectionPath,
				  sourceCollection.forwardFields(),
				  sourceCollection.reverseFields());
		collection.append(sourceCollection, deletedList, 0);
	    }

	    // Write out the deleted list
	    deletedList.write(Path::combine(path, "deleted"));

	    // Write out the manifest
	    manifest["indexes"].set("index", 0);
	    manifest.writeFile(Path::combine(path, "manifest"));
	}
    }
}

//--------------------------------------------------
// Main program
//--------------------------------------------------
int main(int argc, char** argv) {
    indri::api::Parameters parameters;

    try {
	parameters.loadCommandLine(argc, argv);
    }
    catch (lemur::api::Exception& e) {
	LEMUR_ABORT(e);
    }

    struct Command {
	typedef void (*Handler)(indri::api::Parameters&);

	std::string name;
	Handler handler;
    };

    std::vector<Command> listOfCommands = {
	{ "pruneIndex", prune_index },
	{ "printInvertedList", print_inverted_list },
	{ "printDirectFile", print_direct_file },
	{ "copyRepository", copy_repository },
	{ "checkIndexHealth", check_index_health },
	{ "checkDocumentPrior", check_document_prior },
	{ "compileGuard", compile_guard },
	{ "compileAccess", compile_access },
	{ "compileTermGain", compile_term_gain },
	{ "compileQueryView", compile_query_view }
    };

    Command::Handler handler = 0;
    BOOST_FOREACH (const Command& cmd, listOfCommands) {
	if (parameters.exists(cmd.name)) {
	    handler = cmd.handler;
	    break;
	}
    }

    if (handler)
	handler(parameters);
    else {
	std::string padding = "  ";
	std::cout << "Available commands:" << '\n';
	BOOST_FOREACH (const Command& cmd, listOfCommands) {
	    std::cout << padding << '-' << cmd.name << '\n';
	}
    }

    return 0;
}

max_stars_repo_name: rueycheng/Indri-PruningToolkit

max_issues_repo_name: rueycheng/Indri-PruningToolkit

max_forks_repo_name: rueycheng/Indri-PruningToolkit


text:
#pragma once
#include <Eigen/Dense>

namespace mdk {
    using VRef = Eigen::Vector3d const&;

    inline double angle(VRef v1, VRef v2, VRef v3) {
        auto u1 = v2 - v1, u2 = v2 - v3;
        return acos(u1.dot(u2) / (u1.norm() * u2.norm()));
    }

    inline double dihedral(VRef v1, VRef v2, VRef v3, VRef v4) {
        auto u1 = v2 - v1, u2 = v3 - v2, u3 = v4 - v3;
        auto d1 = u1.cross(u2), d2 = u2.cross(u3);

        if (d1.isZero() || d2.isZero()) return 0.0;
        double phi = acos(d1.dot(d2) / (d1.norm() * d2.norm()));
        if (d1.dot(u3) < 0.) phi = -phi;
        return phi;
    }

    double asphericity(Vectors const& v) {
        Vector mean = v.vectorwise().mean();

        Eigen::Matrix3d mit;
        double crg;
        for (size_t i = 0; i < v.size(); ++i) {
            Vector diff = v.col(i) - mean;
            crg += diff.squaredNorm();

            Vector sq_diff = diff.array() * diff.array();
            mit(0,0) += sq_diff(1) + sq_diff(2);
            mit(1,1) += sq_diff(2) + sq_diff(0);
            mit(2,2) += sq_diff(0) + sq_diff(1);
            mit(0,1) -= diff(0) * diff(1);
            mit(1,2) -= diff(1) * diff(2);
            mit(0,2) -= diff(0) * diff(2);
        }
        mit(1,0) = mit(0,1);
        mit(2,1) = mit(1,2);
        mit(2,0) = mit(0,2);
        crg = sqrt(crg / v.size());

        auto eigenvaluesC = mit.eigenvalues();
        double eigenvalues[3] = {
            sqrt(eigenvaluesC(0).real() / v.size()),
            sqrt(eigenvaluesC(1).real() / v.size()),
            sqrt(eigenvaluesC(2).real() / v.size())
        };

        std::sort(eigenvalues, eigenvalues + 3);
        return eigenvalues[1] - 0.5 * (eigenvalues[0] + eigenvalues[2]);
    }
}

ext: hpp

max_stars_repo_name: if-pan-zpp/mdk

max_issues_repo_name: if-pan-zpp/mdk

max_forks_repo_name: if-pan-zpp/mdk


text:
#ifndef LIBSOCKS5_TESTS_FAKES_SOCKET_HPP
#define LIBSOCKS5_TESTS_FAKES_SOCKET_HPP

#include "socks5/tests/util/random.hpp"

#include <boost/asio/buffer.hpp>
#include <boost/asio/ip/tcp.hpp>
#include <boost/process/async_pipe.hpp>
#include <boost/system/system_error.hpp>

#include <cassert>

namespace socks5::tests::fakes {

struct socket final {
    using executor_type = boost::asio::io_context::executor_type;

    inline auto get_executor() -> executor_type {
        return io_.get_executor();
    }

    socket(boost::asio::io_context &io, bool connected = false)
        : io_ {io},
          input_pipe_ {io_},
          output_pipe_ {io_},
          connected_ {false},
          fails_ {false} {

        if (connected) {
            connected_ = true;
            ep_        = socks5::tests::util::random_endpoint();
        }
    }

    inline void connect(const boost::asio::ip::tcp::endpoint &ep,
                        boost::system::error_code &           ec) {
        if (fails_) {
            ec = boost::asio::error::fault;
            return;
        }

        connected_ = true;
        ep_        = ep;
        ec         = {};
    }

    inline void close() {
        assert(connected_);

        if (fails_) {
            throw std::logic_error {"Cannot close socket"};
        }

        input_pipe_.close();
        output_pipe_.close();

        connected_ = false;
    }

    inline auto read_some(const boost::asio::mutable_buffer &buf,
                          boost::system::error_code &ec) -> std::size_t {
        if (fails_) {
            ec = boost::asio::error::fault;
            return 0;
        }

        return input_pipe_.read_some(buf, ec);
    }

    inline auto write_some(const boost::asio::const_buffer &buf,
                           boost::system::error_code &      ec) -> std::size_t {
        if (fails_) {
            ec = boost::asio::error::fault;
            return 0;
        }

        return output_pipe_.write_some(buf, ec);
    }

    [[nodiscard]] inline auto always_fails() const noexcept -> bool {
        return fails_;
    }

    inline void always_fails(bool value) noexcept {
        fails_ = value;
    }

    [[nodiscard]] inline auto is_open() const noexcept -> bool {
        return connected_;
    }

    [[nodiscard]] inline auto input_pipe() noexcept
        -> boost::process::async_pipe & {
        return input_pipe_;
    }

    [[nodiscard]] inline auto output_pipe() noexcept
        -> boost::process::async_pipe & {
        return output_pipe_;
    }

    [[nodiscard]] inline auto remote_endpoint() noexcept
        -> boost::asio::ip::tcp::endpoint & {
        return ep_;
    }

    inline void clear_input_pipe() {
        input_pipe_ = {io_};
    }

    inline void clear_output_pipe() {
        output_pipe_ = {io_};
    }

  private:
    boost::asio::io_context &  io_;
    boost::process::async_pipe input_pipe_;
    boost::process::async_pipe output_pipe_;

    boost::asio::ip::tcp::endpoint ep_;
    std::atomic_bool               connected_, fails_;
};

} // namespace socks5::tests::fakes

#endif


text:
//  Boost string_algo library find.hpp header file  ---------------------------//

//  Copyright Pavol Droba 2002-2003.
//
// Distributed under the Boost Software License, Version 1.0.
//    (See accompanying file LICENSE_1_0.txt or copy at
//          http://www.boost.org/LICENSE_1_0.txt)

//  See http://www.boost.org/ for updates, documentation, and revision history.

#ifndef BOOST_STRING_FIND_HPP
#define BOOST_STRING_FIND_HPP

#include <boost/algorithm/string/config.hpp>

#include <boost/range/iterator_range_core.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/iterator.hpp>
#include <boost/range/as_literal.hpp>

#include <boost/algorithm/string/finder.hpp>
#include <boost/algorithm/string/compare.hpp>
#include <boost/algorithm/string/constants.hpp>

/*! \file
    Defines a set of find algorithms. The algorithms are searching
    for a substring of the input. The result is given as an \c iterator_range
    delimiting the substring.
*/

namespace network_boost {
    namespace algorithm {

//  Generic find -----------------------------------------------//

        //! Generic find algorithm
        /*!
            Search the input using the given finder.

            \param Input A string which will be searched.
            \param Finder Finder object used for searching.
            \return
                An \c iterator_range delimiting the match.
                Returned iterator is either \c RangeT::iterator or
                \c RangeT::const_iterator, depending on the constness of
                the input parameter.
        */
        template<typename RangeT, typename FinderT>
        inline iterator_range<
            BOOST_STRING_TYPENAME range_iterator<RangeT>::type>
        find(
            RangeT& Input,
            const FinderT& Finder)
        {
            iterator_range<BOOST_STRING_TYPENAME range_iterator<RangeT>::type> lit_input(::network_boost::as_literal(Input));

            return Finder(::network_boost::begin(lit_input),::network_boost::end(lit_input));
        }

//  find_first  -----------------------------------------------//

        //! Find first algorithm
        /*!
            Search for the first occurrence of the substring in the input.

            \param Input A string which will be searched.
            \param Search A substring to be searched for.
            \return
                An \c iterator_range delimiting the match.
                Returned iterator is either \c RangeT::iterator or
                \c RangeT::const_iterator, depending on the constness of
                the input parameter.

              \note This function provides the strong exception-safety guarantee
        */
        template<typename Range1T, typename Range2T>
        inline iterator_range<
            BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
        find_first(
            Range1T& Input,
            const Range2T& Search)
        {
            return ::network_boost::algorithm::find(Input, ::network_boost::algorithm::first_finder(Search));
        }

        //! Find first algorithm ( case insensitive )
        /*!
            Search for the first occurrence of the substring in the input.
            Searching is case insensitive.

            \param Input A string which will be searched.
            \param Search A substring to be searched for.
            \param Loc A locale used for case insensitive comparison
            \return
                An \c iterator_range delimiting the match.
                Returned iterator is either \c Range1T::iterator or
                \c Range1T::const_iterator, depending on the constness of
                the input parameter.

            \note This function provides the strong exception-safety guarantee
        */
        template<typename Range1T, typename Range2T>
        inline iterator_range<
            BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
        ifind_first(
            Range1T& Input,
            const Range2T& Search,
            const std::locale& Loc=std::locale())
        {
            return ::network_boost::algorithm::find(Input, ::network_boost::algorithm::first_finder(Search,is_iequal(Loc)));
        }

//  find_last  -----------------------------------------------//

        //! Find last algorithm
        /*!
            Search for the last occurrence of the substring in the input.

            \param Input A string which will be searched.
            \param Search A substring to be searched for.
            \return
                An \c iterator_range delimiting the match.
                Returned iterator is either \c Range1T::iterator or
                \c Range1T::const_iterator, depending on the constness of
                the input parameter.

            \note This function provides the strong exception-safety guarantee
        */
        template<typename Range1T, typename Range2T>
        inline iterator_range<
            BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
        find_last(
            Range1T& Input,
            const Range2T& Search)
        {
            return ::network_boost::algorithm::find(Input, ::network_boost::algorithm::last_finder(Search));
        }

        //! Find last algorithm ( case insensitive )
        /*!
            Search for the last match a string in the input.
            Searching is case insensitive.

            \param Input A string which will be searched.
            \param Search A substring to be searched for.
            \param Loc A locale used for case insensitive comparison
            \return
                An \c iterator_range delimiting the match.
                Returned iterator is either \c Range1T::iterator or
                \c Range1T::const_iterator, depending on the constness of
                the input parameter.

            \note This function provides the strong exception-safety guarantee
        */
        template<typename Range1T, typename Range2T>
        inline iterator_range<
            BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
        ifind_last(
            Range1T& Input,
            const Range2T& Search,
            const std::locale& Loc=std::locale())
        {
            return ::network_boost::algorithm::find(Input, ::network_boost::algorithm::last_finder(Search, is_iequal(Loc)));
        }

//  find_nth ----------------------------------------------------------------------//

        //! Find n-th algorithm
        /*!
            Search for the n-th (zero-indexed) occurrence of the substring in the
            input.

            \param Input A string which will be searched.
            \param Search A substring to be searched for.
            \param Nth An index (zero-indexed) of the match to be found.
                For negative N, the matches are counted from the end of string.
            \return
                An \c iterator_range delimiting the match.
                Returned iterator is either \c Range1T::iterator or
                \c Range1T::const_iterator, depending on the constness of
                the input parameter.
        */
        template<typename Range1T, typename Range2T>
        inline iterator_range<
            BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
        find_nth(
            Range1T& Input,
            const Range2T& Search,
            int Nth)
        {
            return ::network_boost::algorithm::find(Input, ::network_boost::algorithm::nth_finder(Search,Nth));
        }

        //! Find n-th algorithm ( case insensitive ).
        /*!
            Search for the n-th (zero-indexed) occurrence of the substring in the
            input. Searching is case insensitive.

            \param Input A string which will be searched.
            \param Search A substring to be searched for.
            \param Nth An index (zero-indexed) of the match to be found.
                For negative N, the matches are counted from the end of string.
            \param Loc A locale used for case insensitive comparison
            \return
                An \c iterator_range delimiting the match.
                Returned iterator is either \c Range1T::iterator or
                \c Range1T::const_iterator, depending on the constness of
                the input parameter.

            \note This function provides the strong exception-safety guarantee
        */
        template<typename Range1T, typename Range2T>
        inline iterator_range<
            BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
        ifind_nth(
            Range1T& Input,
            const Range2T& Search,
            int Nth,
            const std::locale& Loc=std::locale())
        {
            return ::network_boost::algorithm::find(Input, ::network_boost::algorithm::nth_finder(Search,Nth,is_iequal(Loc)));
        }

//  find_head ----------------------------------------------------------------------//

        //! Find head algorithm
        /*!
            Get the head of the input. Head is a prefix of the string of the
            given size. If the input is shorter then required, whole input is considered
            to be the head.

            \param Input An input string
            \param N Length of the head
                For N>=0, at most N characters are extracted.
                For N<0, at most size(Input)-|N| characters are extracted.
            \return
                An \c iterator_range delimiting the match.
                Returned iterator is either \c Range1T::iterator or
                \c Range1T::const_iterator, depending on the constness of
                the input parameter.

            \note This function provides the strong exception-safety guarantee
        */
        template<typename RangeT>
        inline iterator_range<
            BOOST_STRING_TYPENAME range_iterator<RangeT>::type>
        find_head(
            RangeT& Input,
            int N)
        {
            return ::network_boost::algorithm::find(Input, ::network_boost::algorithm::head_finder(N));
        }

//  find_tail ----------------------------------------------------------------------//

        //! Find tail algorithm
        /*!
            Get the tail of the input. Tail is a suffix of the string of the
            given size. If the input is shorter then required, whole input is considered
            to be the tail.

            \param Input An input string
            \param N Length of the tail.
                For N>=0, at most N characters are extracted.
                For N<0, at most size(Input)-|N| characters are extracted.
            \return
                An \c iterator_range delimiting the match.
                Returned iterator is either \c RangeT::iterator or
                \c RangeT::const_iterator, depending on the constness of
                the input parameter.

            \note This function provides the strong exception-safety guarantee
        */
        template<typename RangeT>
        inline iterator_range<
            BOOST_STRING_TYPENAME range_iterator<RangeT>::type>
        find_tail(
            RangeT& Input,
            int N)
        {
            return ::network_boost::algorithm::find(Input, ::network_boost::algorithm::tail_finder(N));
        }

//  find_token --------------------------------------------------------------------//

        //! Find token algorithm
        /*!
            Look for a given token in the string. Token is a character that matches the
            given predicate.
            If the "token compress mode" is enabled, adjacent tokens are considered to be one match.

            \param Input A input string.
            \param Pred A unary predicate to identify a token
            \param eCompress Enable/Disable compressing of adjacent tokens
            \return
                An \c iterator_range delimiting the match.
                Returned iterator is either \c RangeT::iterator or
                \c RangeT::const_iterator, depending on the constness of
                the input parameter.

            \note This function provides the strong exception-safety guarantee
        */
        template<typename RangeT, typename PredicateT>
        inline iterator_range<
            BOOST_STRING_TYPENAME range_iterator<RangeT>::type>
        find_token(
            RangeT& Input,
            PredicateT Pred,
            token_compress_mode_type eCompress=token_compress_off)
        {
            return ::network_boost::algorithm::find(Input, ::network_boost::algorithm::token_finder(Pred, eCompress));
        }

    } // namespace algorithm

    // pull names to the boost namespace
    using algorithm::find;
    using algorithm::find_first;
    using algorithm::ifind_first;
    using algorithm::find_last;
    using algorithm::ifind_last;
    using algorithm::find_nth;
    using algorithm::ifind_nth;
    using algorithm::find_head;
    using algorithm::find_tail;
    using algorithm::find_token;

} // namespace network_boost

#endif  // BOOST_STRING_FIND_HPP

max_stars_repo_name: Liastre/uri

max_issues_repo_name: Liastre/uri

max_forks_repo_name: Liastre/uri


text:
//   Copyright 2015 Patrick Putnam
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.
#include <boost/test/unit_test.hpp>

#include "../unittest_config.h"

#include <vector>
#include <type_traits>

#include "clotho/utility/bit_walker.hpp"
#include "clotho/utility/bit_block_iterator.hpp"

#include "clotho/utility/preprocess_bit_block_iterator.hpp"

typedef unsigned long block_type;
typedef unsigned short sub_block_type;
typedef clotho::utility::block_walker< block_type, sub_block_type > walker_type;

typedef clotho::utility::block_walker< block_type, sub_block_type, clotho::utility::bit_block_walker< sizeof(block_type) * 8> > other_walker_type;

struct set_bit_vector_op {

    set_bit_vector_op() {}

    void operator()( unsigned int idx ) {
        indices.push_back(idx);
    }

    void reset() { indices.clear(); }

    std::vector< unsigned int > indices;
};

BOOST_AUTO_TEST_SUITE( test_utility )

/**
 * Verify bits_per_block are initialized appropriately
 */
BOOST_AUTO_TEST_CASE( test_bit_walker_bit_sizes ) {

    const unsigned int bpb = walker_type::bits_per_block;
    const unsigned int bpsb = walker_type::bits_per_subblock;
    BOOST_REQUIRE_MESSAGE( bpb == sizeof(block_type) * 8, "Unexpected bits_per_block: " << bpb << " (" << (sizeof(block_type) * 8) << ")");
    BOOST_REQUIRE_MESSAGE( bpsb == sizeof(sub_block_type) * 8, "Unexpected bits_per_subblock: " << bpsb << " (" << (sizeof(sub_block_type) * 8) << ")");
}

BOOST_AUTO_TEST_CASE( test_bit_node_init ) {
    // clotho::utility::bit_block_walker< 300 > bw3;    // should not compile because of enable_if in general bit_walker

    walker_type::bit_walker_type bw;

    for( unsigned int i = 1; i < walker_type::bit_walker_type::max_nodes; ++i ) {
        unsigned int s = (i & (1 << bw.getNode()[i].bit_index));
        BOOST_REQUIRE_MESSAGE( s != 0, "Unexpected bit state: " << i << " @ " << bw.getNode()[i].bit_index );

        if( bw.getNode()[i].next ) {
            unsigned int k = (i >> bw.getNode()[i].bit_shift_next);
            BOOST_REQUIRE_MESSAGE( k == bw.getNode()[i].next, "Unexpected next node: " << i << " -> " << k << " (" << bw.getNode()[i].next << ")");
        }
    }
}

/**
 * Initialize a block with every odd bit set, and initialize an expected index vector
 *
 * Apply the set_bit_vector_op
 *
 * Verify that the result vector matches the expected vector
 */
BOOST_AUTO_TEST_CASE( test_bit_walker_set_bits ) {
    std::vector< unsigned int > expected;

    block_type _bits = 0, mask = 1;
    for( unsigned int i = 0; i < walker_type::bits_per_block; ++i ) {
        if( i & 1 ) {
            expected.push_back( i );

            _bits |= mask;
        }
        mask <<= 1;
    }

    set_bit_vector_op sbv;
    walker_type::apply( _bits, sbv );

    BOOST_REQUIRE_MESSAGE( sbv.indices == expected, "Unexpected list of set bits was returned" );
}

/**
 * Initialize a block with every odd bit set, and initialize an expected index vector
 *
 * Apply the set_bit_vector_op
 *
 * Verify that the result vector matches the expected vector
 */
BOOST_AUTO_TEST_CASE( test_other_bit_walker_set_bits ) {
    BOOST_REQUIRE_MESSAGE( (std::is_same< other_walker_type::bit_walker_type, clotho::utility::bit_block_walker< sizeof(block_type) * 8 > >::value), "Unexpected bit block walker (test 1)" );
    BOOST_REQUIRE_MESSAGE( (!std::is_same< other_walker_type::bit_walker_type, clotho::utility::bit_block_walker< 16 > >::value), "Unexpected bit block walker (test 2)" );

    std::vector< unsigned int > expected;

    block_type _bits = 0, mask = 1;
    for( unsigned int i = 0; i < walker_type::bits_per_block; ++i ) {
        if( i & 1 ) {
            expected.push_back( i );

            _bits |= mask;
        }
        mask <<= 1;
    }

    set_bit_vector_op sbv;
    other_walker_type::apply( _bits, sbv );

    BOOST_REQUIRE_MESSAGE( sbv.indices == expected, "Unexpected list of set bits was returned" );
}

/**
 *
 */
BOOST_AUTO_TEST_CASE( test_bit_block_iterator_walk ) {
    typedef clotho::utility::bit_block_iterator< block_type, clotho::utility::tag::walk_iterator_tag > bit_iterator;

    block_type val = (block_type)0x10A10000;
    unsigned int e_bit_count = 4;

    bit_iterator it(val);

    std::vector< unsigned int > set_bits;

    while( !it.done() ) {
        set_bits.push_back( *it );
        ++it;
    }

    BOOST_REQUIRE_MESSAGE( set_bits.size() == e_bit_count, "Unexpected number of set bits in " << val << ". " << set_bits.size() << " != " << e_bit_count );

    std::vector< unsigned int >::iterator bit_it = set_bits.begin();
    while( bit_it != set_bits.end() ) {
        BOOST_REQUIRE_MESSAGE( (val & ((block_type)1 << *bit_it)), "Bit " << *bit_it << " was not set in " << val << " but should be");
        ++bit_it;
    }
}

BOOST_AUTO_TEST_CASE( test_bit_block_iterator_preprocess ) {
    typedef clotho::utility::bit_block_iterator< block_type, clotho::utility::tag::preprocess_iterator_tag > bit_iterator;

    block_type val = (block_type)0x10A10000;
    unsigned int e_bit_count = 4;

    bit_iterator it(val);

    std::vector< unsigned int > set_bits;

    while( !it.done()  ) {
        set_bits.push_back( *it );
        ++it;
    }

    BOOST_REQUIRE_MESSAGE( set_bits.size() == e_bit_count, "Unexpected number of set bits in " << val << ". " << set_bits.size() << " != " << e_bit_count );

    std::vector< unsigned int >::iterator bit_it = set_bits.begin();
    while( bit_it != set_bits.end() ) {
        BOOST_REQUIRE_MESSAGE( (val & ((block_type)1 << *bit_it)), "Bit " << *bit_it << " was not set in " << val << " but should be");
        ++bit_it;
    }
}
BOOST_AUTO_TEST_SUITE_END()

ext: cpp

max_stars_repo_name: putnampp/clotho

max_issues_repo_name: putnampp/clotho

max_forks_repo_name: putnampp/clotho


text:
#ifndef BOOST_TEXT_STRING_UTILITY_HPP
#define BOOST_TEXT_STRING_UTILITY_HPP

#include <boost/text/string.hpp>
#include <boost/text/utility.hpp>
#include <boost/text/detail/sentinel_tag.hpp>

namespace boost { namespace text {

#ifdef BOOST_TEXT_DOXYGEN

    /** Returns a UTF-8-encoded string constructed from [first, last).

        This function only participates in overload resolution if
        CPIter models the CPIter concept. */
    template<typename CPIter, typename Sentinel>
    string to_string(CPIter first, Sentinel last);

    /** Returns a UTF-8-encoded string constructed from range.

        This function only participates in overload resolution if
        CPRange models the CPRange concept. */
    template<typename CPRange>
    string to_string(CPRange & range);

#else

    template<typename CPIter, typename Sentinel>
    auto to_string(CPIter first, Sentinel last)
        -> detail::cp_iter_ret_t<string, CPIter>
    {
        cp_range<CPIter, Sentinel> cps{first, last};
        auto const r = make_from_utf32_range(cps);
        return string(r.begin(), r.end());
    }

    template<typename CPRange>
    auto to_string(CPRange & range) -> detail::cp_rng_alg_ret_t<string, CPRange>
    {
        auto const r = make_from_utf32_range(range);
        return string(std::begin(r), std::end(r));
    }

#endif

}}

#endif

max_stars_repo_name: jan-moeller/text

max_issues_repo_name: jan-moeller/text

max_forks_repo_name: jan-moeller/text


text:
//
// Copyright (c) 2021 Kasper Laudrup (laudrup at stacktrace dot dk)
//
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//

#ifndef BOOST_WINTLS_TEST_ASYNC_ECHO_CLIENT_HPP
#define BOOST_WINTLS_TEST_ASYNC_ECHO_CLIENT_HPP

#include "unittest.hpp"

#include <boost/asio.hpp>

template<typename Stream>
struct async_echo_client : public Stream {
public:
  using Stream::stream;

  async_echo_client(net::io_context& context, const std::string& message)
    : Stream(context)
    , message_(message) {
  }

  void run() {
    do_handshake();
  }

  std::string received_message() const {
    return std::string(net::buffers_begin(recv_buffer_.data()),
                       net::buffers_begin(recv_buffer_.data()) + recv_buffer_.size());
  }

private:
  void do_handshake() {
    stream.async_handshake(Stream::handshake_type::client,
                           [this](const boost::system::error_code& ec) {
                             REQUIRE_FALSE(ec);
                             do_write();
                           });
  }

  void do_write() {
    net::async_write(stream, net::buffer(message_),
                     [this](const boost::system::error_code& ec, std::size_t) {
                       REQUIRE_FALSE(ec);
                       do_read();
                     });
  }

  void do_read() {
    net::async_read_until(stream, recv_buffer_, '\0',
                          [this](const boost::system::error_code& ec, std::size_t) {
                            REQUIRE_FALSE(ec);
                            do_shutdown();
                          });
  }

  void do_shutdown() {
    stream.async_shutdown([](const boost::system::error_code& ec) {
      REQUIRE_FALSE(ec);
    });
  }

  std::string message_;
  net::streambuf recv_buffer_;
};

#endif // BOOST_WINTLS_TEST_ASYNC_ECHO_CLIENT_HPP

max_stars_repo_name: Larsjep/boost-wintls

max_issues_repo_name: Larsjep/boost-wintls

max_forks_repo_name: Larsjep/boost-wintls