/home/palakars/workspace-inprogress/code-in-progress/aitools3/aitools3-aq-invertedindex-cpp/src/core/InternalIntroSort.hpp

Go to the documentation of this file.

/* Copyright (C) 2010 webis.de
 * All rights reserved.
 */
#ifndef AITOOLS_INVERTEDINDEX_INTERNAL_INTRO_SORT_HPP
#define AITOOLS_INVERTEDINDEX_INTERNAL_INTRO_SORT_HPP

#include "IndexMessages.pb.h"
#include "PostlistBuilder.hpp"
#include "Postlist.hpp"
#include "Quantile.hpp"
#include <functional>
#include <algorithm>
#include <vector>

namespace aitools {
namespace invertedindex {

class InternalIntroSort {

private: // nested types

        typedef Configuration::Sorting Sorting;

private: // disallow instantiation

        InternalIntroSort();

public: // class methods

        template<typename Value>
        static void
        sort(Postlist<Value>& postlist, Quantile& quantile, Sorting mode);

        template<typename Value>
        static void
        sort(std::vector<Value>& values, Quantile& quantile, Sorting mode);

private: // class methods

        template<typename Value>
        static void
        comp_quantile(const std::vector<Value>& values, Quantile& quantile);

};

// IMPLEMENTATION

template<typename Value>
void InternalIntroSort::sort
(Postlist<Value>& postlist, Quantile& quantile, Sorting mode)
{
        if (mode == Configuration::DISABLED) return;

        // Copy all values to a vector.
        Value value;
        std::vector<Value> values;
        values.reserve(postlist.length());
        while (postlist.next(value))
        {
                values.push_back(value);
        }
        // Sort all values and compute quantile.
        sort(values, quantile, mode);
        // Build a new sorted postlist.
        ByteBuffer buffer;
        PostlistBuilder builder;
        builder.set_checksum(postlist.iterator()->header().checksum);
        typename std::vector<Value>::const_iterator end(values.end());
        typename std::vector<Value>::const_iterator it(values.begin());
        for (; it != end; ++it)
        {
                it->to_bytes(buffer);
                builder.append(buffer);
        }
        postlist = builder.build();
}

template<typename Value>
void InternalIntroSort::sort
(std::vector<Value>& values, Quantile& quantile, Sorting mode)
{
        if (mode == Configuration::ASCENDING)
        {
                std::sort(values.begin(), values.end(), std::less<Value>());
        }
        else if (mode == Configuration::DESCENDING)
        {
                std::sort(values.begin(), values.end(), std::greater<Value>());
        }
        else
        {
                return;
        }
        comp_quantile(values, quantile);
}

template<typename Value>
void InternalIntroSort::comp_quantile
(const std::vector<Value>& values, Quantile& quantile)
{
        // Compute entire integral
        double score(0);
        double integrals[Quantile::COUNT] = {0};
        typename std::vector<Value>::const_iterator end(values.end());
        typename std::vector<Value>::const_iterator it(values.begin());
        for (; it != end; ++it)
        {
                score += it->score();
        }
        integrals[Quantile::P100] = score;
        // Compute partial integrals (P10, P20, P30, ..., PX0)
        for (unsigned q(Quantile::P10); q != Quantile::P91; ++q)
        {
                integrals[q] = (q+1) * 0.1 * score;
        }
        // Compute partial integrals (P91, P92, P93, ..., P99)
        for (unsigned q(Quantile::P91); q != Quantile::P100; ++q)
        {
                integrals[q] = (0.9 + (q-Quantile::P91+1) * (0.01)) * score;
        }
        // Find quantile boundaries
        quantile.clear();
        double integral(0);
        Quantile::Order order(Quantile::P10);
        for (unsigned i(0); i != values.size(); ++i)
        {
                integral += values[i].score();
                if (integral >= integrals[order])
                {
                        quantile.at(order) = i+1;
                        if (order < Quantile::P100)
                        {
                                order = Quantile::Order(order+1);
                        }
                }
        }
        // Set remaining quantile boundaries
        for (unsigned q(order); q <= Quantile::P100; ++q)
        {
                quantile.at((Quantile::Order)q) = values.size();
        }
}

} // namespace invertedindex
} // namespace aitools

#endif // AITOOLS_INVERTEDINDEX_INTERNAL_INTRO_SORT_HPP

---