losertree.h

Go to the documentation of this file.

/***************************************************************************
 *  include/stxxl/bits/parallel/losertree.h
 *
 *  Many generic loser tree variants.
 *  Extracted from MCSTL - http://algo2.iti.uni-karlsruhe.de/singler/mcstl/
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright (C) 2007 Johannes Singler <[email protected]>
 *  Copyright (C) 2014-2015 Timo Bingmann <[email protected]>
 *
 *  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 STXXL_PARALLEL_LOSERTREE_HEADER
#define STXXL_PARALLEL_LOSERTREE_HEADER

#include <stxxl/bits/namespace.h>
#include <stxxl/bits/noncopyable.h>
#include <stxxl/bits/common/utils.h>
#include <stxxl/bits/parallel/base.h>
#include <functional>

STXXL_BEGIN_NAMESPACE

namespace parallel {

/**
 * Guarded loser tree/tournament tree, either copying the whole element into
 * the tree structure, or looking up the element via the index.
 *
 * This is a base class for the LoserTreeCopy<true> and <false> classes.
 *
 * Guarding is done explicitly through one flag sup per element, inf is not
 * needed due to a better initialization routine.  This is a well-performing
 * variant.
 *
 * \tparam ValueType the element type
 * \tparam Comparator comparator to use for binary comparisons.
 */
template <typename ValueType, typename Comparator = std::less<ValueType> >
class LoserTreeCopyBase
{
public:
    //! size of counters and array indexes
    typedef unsigned int size_type;
    //! type of the source field
    typedef int source_type;

protected:
    //! Internal representation of a loser tree player/node
    struct Loser
    {
        //! flag, true iff is a virtual maximum sentinel
        bool sup;
        //! index of source
        source_type source;
        //! copy of key value of the element in this node
        ValueType key;
    };

    //! number of nodes
    const size_type ik;
    //! log_2(ik) next greater power of 2
    const size_type k;
    //! array containing loser tree nodes
    Loser* losers;
    //! the comparator object
    Comparator comp;
    //! still have to construct keys
    bool first_insert;

public:
    LoserTreeCopyBase(size_type _k,
                      Comparator _comp = std::less<ValueType>())
        : ik(_k),
          k(round_up_to_power_of_two(ik)),
          comp(_comp),
          first_insert(true)
    {
        // avoid default-constructing losers[].key
        losers = static_cast<Loser*>(operator new (2 * k * sizeof(Loser)));

        for (size_type i = ik - 1; i < k; ++i)
        {
            losers[i + k].sup = true;
            losers[i + k].source = (source_type)(-1);
        }
    }

    ~LoserTreeCopyBase()
    {
        for (size_type i = 0; i < (2 * k); ++i)
            losers[i].~Loser();

        delete losers;
    }

    void print(std::ostream& os)
    {
        for (size_type i = 0; i < (k * 2); i++)
            os << i << "    " << losers[i].key << " from " << losers[i].source << ",  " << losers[i].sup << "\n";
    }

    //! return the index of the player with the smallest element.
    source_type get_min_source()
    {
        return losers[0].source;
    }

    /**
     * Initializes the player source with the element key.
     *
     * \param key the element to insert
     * \param source index of the player
     * \param sup flag that determines whether the value to insert is an
     *   explicit supremum sentinel.
     */
    void insert_start(const ValueType& key, source_type source, bool sup)
    {
        size_type pos = k + source;

        losers[pos].sup = sup;
        losers[pos].source = source;

        if (UNLIKELY(first_insert))
        {
            // copy construct all keys from this first key
            for (size_type i = 0; i < (2 * k); ++i)
                new (&(losers[i].key))ValueType(key);
            first_insert = false;
        }
        else
            losers[pos].key = key;
    }

    /**
     * Computes the winner of the competition at player root.  Called
     * recursively (starting at 0) to build the initial tree.
     *
     * \param root index of the game to start.
     */
    size_type init_winner(size_type root)
    {
        if (root >= k)
        {
            return root;
        }
        else
        {
            size_type left = init_winner(2 * root);
            size_type right = init_winner(2 * root + 1);
            if (losers[right].sup ||
                (!losers[left].sup && !comp(losers[right].key, losers[left].key)))
            {                   //left one is less or equal
                losers[root] = losers[right];
                return left;
            }
            else
            {                   //right one is less
                losers[root] = losers[left];
                return right;
            }
        }
    }

    void init()
    {
        losers[0] = losers[init_winner(1)];
    }
};

/**
 * Guarded loser tree/tournament tree, either copying the whole element into
 * the tree structure, or looking up the element via the index.
 *
 * Unstable specialization of LoserTreeCopyBase.
 *
 * Guarding is done explicitly through one flag sup per element, inf is not
 * needed due to a better initialization routine.  This is a well-performing
 * variant.
 *
 * \tparam ValueType the element type
 * \tparam Comparator comparator to use for binary comparisons.
 */
template <bool Stable /* == false */,
          typename ValueType, typename Comparator = std::less<ValueType> >
class LoserTreeCopy : public LoserTreeCopyBase<ValueType, Comparator>
{
public:
    typedef LoserTreeCopyBase<ValueType, Comparator> base_type;

    typedef typename base_type::size_type size_type;
    typedef typename base_type::source_type source_type;
    using base_type::k;
    using base_type::losers;
    using base_type::comp;

    LoserTreeCopy(size_type _k, Comparator _comp = std::less<ValueType>())
        : base_type(_k, _comp)
    { }

    // do not pass const reference since key will be used as local variable
    void delete_min_insert(ValueType key, bool sup)
    {
        using std::swap;

        source_type source = losers[0].source;
        for (size_type pos = (k + source) / 2; pos > 0; pos /= 2)
        {
            // the smaller one gets promoted
            if (sup ||
                (!losers[pos].sup && comp(losers[pos].key, key)))
            {
                // the other one is smaller
                swap(losers[pos].sup, sup);
                swap(losers[pos].source, source);
                swap(losers[pos].key, key);
            }
        }

        losers[0].sup = sup;
        losers[0].source = source;
        losers[0].key = key;
    }
};

/**
 * Guarded loser tree/tournament tree, either copying the whole element into
 * the tree structure, or looking up the element via the index.
 *
 * Stable specialization of LoserTreeCopyBase.
 *
 * Guarding is done explicitly through one flag sup per element, inf is not
 * needed due to a better initialization routine.  This is a well-performing
 * variant.
 *
 * \tparam ValueType the element type
 * \tparam Comparator comparator to use for binary comparisons.
 */
template <typename ValueType, typename Comparator>
class LoserTreeCopy</* Stable == */ true, ValueType, Comparator>
    : public LoserTreeCopyBase<ValueType, Comparator>
{
public:
    typedef LoserTreeCopyBase<ValueType, Comparator> base_type;

    typedef typename base_type::size_type size_type;
    typedef typename base_type::source_type source_type;
    using base_type::k;
    using base_type::losers;
    using base_type::comp;

    LoserTreeCopy(size_type _k, Comparator _comp = std::less<ValueType>())
        : base_type(_k, _comp)
    { }

    // do not pass const reference since key will be used as local variable
    void delete_min_insert(ValueType key, bool sup)
    {
        using std::swap;

        source_type source = losers[0].source;
        for (size_type pos = (k + source) / 2; pos > 0; pos /= 2)
        {
            if ((sup && (!losers[pos].sup || losers[pos].source < source)) ||
                (!sup && !losers[pos].sup &&
                 ((comp(losers[pos].key, key)) ||
                  (!comp(key, losers[pos].key) && losers[pos].source < source))))
            {
                // the other one is smaller
                swap(losers[pos].sup, sup);
                swap(losers[pos].source, source);
                swap(losers[pos].key, key);
            }
        }

        losers[0].sup = sup;
        losers[0].source = source;
        losers[0].key = key;
    }
};

/** Guarded loser tree, either copying the whole element into the tree structure, or looking up the element via the index.
 *
 *  Guarding is done explicitly through one flag sup per element, inf is not needed due to a better initialization routine.
 *  This is a well-performing variant.
 */
template <typename T, typename Comparator = std::less<T> >
class LoserTreeReference
{
#undef COPY
#ifdef COPY
        #define KEY(i) losers[i].key
        #define KEY_SOURCE(i) key
#else
        #define KEY(i) keys[losers[i].source]
        #define KEY_SOURCE(i) keys[i]
#endif

private:
    struct Loser
    {
        bool sup;
        int source;
#ifdef COPY
        T key;
#endif
    };

    unsigned int ik, k;
    Loser* losers;
#ifndef COPY
    T* keys;
#endif
    Comparator comp;

public:
    LoserTreeReference(unsigned int _k, Comparator _comp = std::less<T>()) : comp(_comp)
    {
        ik = _k;
        k = round_up_to_power_of_two(ik);
        losers = new Loser[k * 2];
#ifndef COPY
        keys = new T[ik];
#endif
        for (unsigned int i = ik - 1; i < k; i++)
            losers[i + k].sup = true;
    }

    ~LoserTreeReference()
    {
        delete[] losers;
#ifndef COPY
        delete[] keys;
#endif
    }

    void print(std::ostream& os)
    {
        for (unsigned int i = 0; i < (k * 2); i++)
            os << i << "    " << KEY(i) << " from " << losers[i].source << ",  " << losers[i].sup << "\n";
    }

    int get_min_source()
    {
        return losers[0].source;
    }

    void insert_start(T key, int source, bool sup)
    {
        unsigned int pos = k + source;

        losers[pos].sup = sup;
        losers[pos].source = source;
        KEY(pos) = key;
    }

    unsigned int init_winner(unsigned int root)
    {
        if (root >= k)
        {
            return root;
        }
        else
        {
            unsigned int left = init_winner(2 * root);
            unsigned int right = init_winner(2 * root + 1);
            if (losers[right].sup ||
                (!losers[left].sup && !comp(KEY(right), KEY(left))))
            {                   //left one is less or equal
                losers[root] = losers[right];
                return left;
            }
            else
            {                   //right one is less
                losers[root] = losers[left];
                return right;
            }
        }
    }

    void init()
    {
        losers[0] = losers[init_winner(1)];
    }

    void delete_min_insert(T /* key */, bool sup)
    {
        using std::swap;

        int source = losers[0].source;
        for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
        {
            //the smaller one gets promoted
            if (sup ||
                (!losers[pos].sup && comp(KEY(pos), KEY_SOURCE(source))))
            {                   //the other one is smaller
                swap(losers[pos].sup, sup);
                swap(losers[pos].source, source);
#ifdef COPY
                swap(KEY(pos), KEY_SOURCE(source));
#endif
            }
        }

        losers[0].sup = sup;
        losers[0].source = source;
#ifdef COPY
        KEY(0) = KEY_SOURCE(source);
#endif
    }

    void insert_start_stable(T key, int source, bool sup)
    {
        return insert_start(key, source, sup);
    }

    unsigned int init_winner_stable(unsigned int root)
    {
        if (root >= k)
        {
            return root;
        }
        else
        {
            unsigned int left = init_winner(2 * root);
            unsigned int right = init_winner(2 * root + 1);
            if (losers[right].sup ||
                (!losers[left].sup && !comp(KEY(right), KEY(left))))
            {                   //left one is less or equal
                losers[root] = losers[right];
                return left;
            }
            else
            {                   //right one is less
                losers[root] = losers[left];
                return right;
            }
        }
    }

    void init_stable()
    {
        losers[0] = losers[init_winner_stable(1)];
    }

    void delete_min_insert_stable(T /* key */, bool sup)
    {
        using std::swap;

        int source = losers[0].source;
        for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
        {
            //the smaller one gets promoted, ties are broken by source
            if ((sup && (!losers[pos].sup || losers[pos].source < source)) ||
                (!sup && !losers[pos].sup &&
                 ((comp(KEY(pos), KEY_SOURCE(source))) ||
                  (!comp(KEY_SOURCE(source), KEY(pos)) && losers[pos].source < source))))
            {                   //the other one is smaller
                swap(losers[pos].sup, sup);
                swap(losers[pos].source, source);
#ifdef COPY
                swap(KEY(pos), KEY_SOURCE(source));
#endif
            }
        }

        losers[0].sup = sup;
        losers[0].source = source;
#ifdef COPY
        KEY(0) = KEY_SOURCE(source);
#endif
    }
};
#undef KEY
#undef KEY_SOURCE

/**
 * Guarded loser tree, using pointers to the elements instead of copying them
 * into the tree nodes.
 *
 * This is a base class for the LoserTreePointer<true> and <false> classes.
 *
 * Guarding is done explicitly through one flag sup per element, inf is not
 * needed due to a better initialization routine.  This is a well-performing
 * variant.
 */
template <typename ValueType, typename Comparator = std::less<ValueType> >
class LoserTreePointerBase
{
public:
    //! size of counters and array indexes
    typedef typename LoserTreeCopyBase<ValueType, Comparator>
        ::size_type size_type;
    //! type of the source field
    typedef typename LoserTreeCopyBase<ValueType, Comparator>
        ::source_type source_type;

protected:
    //! Internal representation of a loser tree player/node
    struct Loser
    {
        //! flag, true iff is a virtual maximum sentinel
        bool sup;
        //! index of source
        source_type source;
        //! pointer to key value of the element in this node
        const ValueType* keyp;
    };

    //! number of nodes
    const size_type ik;
    //! log_2(ik) next greater power of 2
    const size_type k;
    //! array containing loser tree nodes
    Loser* losers;
    //! the comparator object
    Comparator comp;

public:
    LoserTreePointerBase(size_type _k,
                         Comparator _comp = std::less<ValueType>())
        : ik(_k),
          k(round_up_to_power_of_two(ik)),
          losers(new Loser[k * 2]),
          comp(_comp)
    {
        for (size_type i = ik - 1; i < k; i++)
        {
            losers[i + k].sup = true;
            losers[i + k].source = (source_type)(-1);
        }
    }

    ~LoserTreePointerBase()
    {
        delete[] losers;
    }

    void print(std::ostream& os)
    {
        for (size_type i = 0; i < (k * 2); i++)
            os << i << "    " << losers[i].keyp << " from " << losers[i].source << ",  " << losers[i].sup << "\n";
    }

    //! return the index of the player with the smallest element.
    source_type get_min_source()
    {
        return losers[0].source;
    }

    /**
     * Initializes the player source with the element key.
     *
     * \param key the element to insert
     * \param source index of the player
     * \param sup flag that determines whether the value to insert is an
     *   explicit supremum sentinel.
     */
    void insert_start(const ValueType& key, source_type source, bool sup)
    {
        size_type pos = k + source;

        losers[pos].sup = sup;
        losers[pos].source = source;
        losers[pos].keyp = &key;
    }

    /**
     * Computes the winner of the competition at player root.  Called
     * recursively (starting at 0) to build the initial tree.
     *
     * \param root index of the game to start.
     */
    size_type init_winner(size_type root)
    {
        if (root >= k)
        {
            return root;
        }
        else
        {
            size_type left = init_winner(2 * root);
            size_type right = init_winner(2 * root + 1);
            if (losers[right].sup ||
                (!losers[left].sup && !comp(*losers[right].keyp, *losers[left].keyp)))
            {                   //left one is less or equal
                losers[root] = losers[right];
                return left;
            }
            else
            {                   //right one is less
                losers[root] = losers[left];
                return right;
            }
        }
    }

    void init()
    {
        losers[0] = losers[init_winner(1)];
    }
};

/**
 * Guarded loser tree, using pointers to the elements instead of copying them
 * into the tree nodes.
 *
 * Unstable specialization of LoserTreeCopyBase.
 *
 * Guarding is done explicitly through one flag sup per element, inf is not
 * needed due to a better initialization routine.  This is a well-performing
 * variant.
 */
template <bool Stable /* == false */,
          typename ValueType, typename Comparator = std::less<ValueType> >
class LoserTreePointer : public LoserTreePointerBase<ValueType, Comparator>
{
public:
    typedef LoserTreePointerBase<ValueType, Comparator> base_type;

    typedef typename base_type::size_type size_type;
    typedef typename base_type::source_type source_type;
    using base_type::k;
    using base_type::losers;
    using base_type::comp;

    LoserTreePointer(size_type _k, Comparator _comp = std::less<ValueType>())
        : base_type(_k, _comp)
    { }

    void delete_min_insert(const ValueType& key, bool sup)
    {
        using std::swap;

        const ValueType* keyp = &key;
        source_type source = losers[0].source;
        for (size_type pos = (k + source) / 2; pos > 0; pos /= 2)
        {
            //the smaller one gets promoted
            if (sup ||
                (!losers[pos].sup && comp(*losers[pos].keyp, *keyp)))
            {                   //the other one is smaller
                swap(losers[pos].sup, sup);
                swap(losers[pos].source, source);
                swap(losers[pos].keyp, keyp);
            }
        }

        losers[0].sup = sup;
        losers[0].source = source;
        losers[0].keyp = keyp;
    }
};

/**
 * Guarded loser tree, using pointers to the elements instead of copying them
 * into the tree nodes.
 *
 * Unstable specialization of LoserTreeCopyBase.
 *
 * Guarding is done explicitly through one flag sup per element, inf is not
 * needed due to a better initialization routine.  This is a well-performing
 * variant.
 */
template <typename ValueType, typename Comparator>
class LoserTreePointer</* Stable == */ true, ValueType, Comparator>
    : public LoserTreePointerBase<ValueType, Comparator>
{
public:
    typedef LoserTreePointerBase<ValueType, Comparator> base_type;

    typedef typename base_type::size_type size_type;
    typedef typename base_type::source_type source_type;
    using base_type::k;
    using base_type::losers;
    using base_type::comp;

    LoserTreePointer(size_type _k, Comparator _comp = std::less<ValueType>())
        : base_type(_k, _comp)
    { }

    void delete_min_insert(const ValueType& key, bool sup)
    {
        using std::swap;

        const ValueType* keyp = &key;
        source_type source = losers[0].source;
        for (size_type pos = (k + source) / 2; pos > 0; pos /= 2)
        {
            //the smaller one gets promoted, ties are broken by source
            if ((sup && (!losers[pos].sup || losers[pos].source < source)) ||
                (!sup && !losers[pos].sup &&
                 ((comp(*losers[pos].keyp, *keyp)) ||
                  (!comp(*keyp, *losers[pos].keyp) && losers[pos].source < source))))
            {                   //the other one is smaller
                swap(losers[pos].sup, sup);
                swap(losers[pos].source, source);
                swap(losers[pos].keyp, keyp);
            }
        }

        losers[0].sup = sup;
        losers[0].source = source;
        losers[0].keyp = keyp;
    }
};

/**
 * Unguarded loser tree, copying the whole element into the tree structure.
 *
 * This is a base class for the LoserTreeCopyUnguarded<true> and <false>
 * classes.
 *
 * No guarding is done, therefore not a single input sequence must run empty.
 * This is a very fast variant.
 */
template <typename ValueType, typename Comparator = std::less<ValueType> >
class LoserTreeCopyUnguardedBase : private noncopyable
{
protected:
    //! Internal representation of a loser tree player/node
    struct Loser
    {
        //! index of source
        int source;
        //! copy of key value of the element in this node
        ValueType key;
    };

    //! number of nodes
    unsigned int ik;
    //! log_2(ik) next greater power of 2
    unsigned int k;
    //! array containing loser tree nodes
    Loser* losers;
    //! the comparator object
    Comparator comp;

public:
    LoserTreeCopyUnguardedBase(unsigned int _k, const ValueType& _sentinel,
                               Comparator _comp = std::less<ValueType>())
        : ik(_k),
          k(round_up_to_power_of_two(ik)),
          losers(new Loser[k * 2]),
          comp(_comp)
    {
        for (unsigned int i = 0; i < 2 * k; i++)
        {
            losers[i].source = -1;
            losers[i].key = _sentinel;
        }
    }

    ~LoserTreeCopyUnguardedBase()
    {
        delete[] losers;
    }

    void print(std::ostream& os)
    {
        for (unsigned int i = 0; i < k + ik; i++)
            os << i << "    " << losers[i].key << " from " << losers[i].source << "\n";
    }

    //! return the index of the player with the smallest element.
    int get_min_source()
    {
        assert(losers[0].source != -1 && "Data underrun in unguarded merging.");
        return losers[0].source;
    }

    void insert_start(const ValueType& key, int source)
    {
        unsigned int pos = k + source;

        losers[pos].source = source;
        losers[pos].key = key;
    }

    unsigned int init_winner(unsigned int root)
    {
        if (root >= k)
        {
            return root;
        }
        else
        {
            unsigned int left = init_winner(2 * root);
            unsigned int right = init_winner(2 * root + 1);
            if (!comp(losers[right].key, losers[left].key))
            {                   //left one is less or equal
                losers[root] = losers[right];
                return left;
            }
            else
            {                   //right one is less
                losers[root] = losers[left];
                return right;
            }
        }
    }

    void init()
    {
        losers[0] = losers[init_winner(1)];
    }
};

template <bool Stable /* == false */,
          typename ValueType, typename Comparator = std::less<ValueType> >
class LoserTreeCopyUnguarded : public LoserTreeCopyUnguardedBase<ValueType, Comparator>
{
protected:
    typedef LoserTreeCopyUnguardedBase<ValueType, Comparator> base_type;

    using base_type::k;
    using base_type::losers;
    using base_type::comp;

public:
    LoserTreeCopyUnguarded(unsigned int _k, const ValueType& _sentinel,
                           Comparator _comp = std::less<ValueType>())
        : base_type(_k, _sentinel, _comp)
    { }

    // do not pass const reference since key will be used as local variable
    void delete_min_insert(ValueType key)
    {
        using std::swap;

        int source = losers[0].source;
        for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
        {
            // the smaller one gets promoted
            if (comp(losers[pos].key, key))
            {
                // the other one is smaller
                swap(losers[pos].source, source);
                swap(losers[pos].key, key);
            }
        }

        losers[0].source = source;
        losers[0].key = key;
    }
};

template <typename ValueType, typename Comparator>
class LoserTreeCopyUnguarded</* Stable == */ true, ValueType, Comparator>
    : public LoserTreeCopyUnguardedBase<ValueType, Comparator>
{
protected:
    typedef LoserTreeCopyUnguardedBase<ValueType, Comparator> base_type;

    using base_type::k;
    using base_type::losers;
    using base_type::comp;

public:
    LoserTreeCopyUnguarded(unsigned int _k, const ValueType& _sentinel,
                           Comparator _comp = std::less<ValueType>())
        : base_type(_k, _sentinel, _comp)
    { }

    // do not pass const reference since key will be used as local variable
    void delete_min_insert(ValueType key)
    {
        using std::swap;

        int source = losers[0].source;
        for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
        {
            if (!comp(key, losers[pos].key) && losers[pos].source < source)
            {
                // the other one is smaller
                swap(losers[pos].source, source);
                swap(losers[pos].key, key);
            }
        }

        losers[0].source = source;
        losers[0].key = key;
    }
};

/**
 * Unguarded loser tree, keeping only pointers to the elements in the tree
 * structure.
 *
 * This is a base class for the LoserTreePointerUnguarded<true> and <false>
 * classes.
 *
 * No guarding is done, therefore not a single input sequence must run empty.
 * This is a very fast variant.
 */
template <typename ValueType, typename Comparator = std::less<ValueType> >
class LoserTreePointerUnguardedBase : private noncopyable
{
protected:
    //! Internal representation of a loser tree player/node
    struct Loser
    {
        //! index of source
        int source;
        //! copy of key value of the element in this node
        const ValueType* keyp;
    };

    //! number of nodes
    unsigned int ik;
    //! log_2(ik) next greater power of 2
    unsigned int k;
    //! array containing loser tree nodes
    Loser* losers;
    //! the comparator object
    Comparator comp;

public:
    LoserTreePointerUnguardedBase(unsigned int _k, const ValueType& _sentinel,
                                  Comparator _comp = std::less<ValueType>())
        : ik(_k),
          k(round_up_to_power_of_two(ik)),
          losers(new Loser[k * 2]),
          comp(_comp)
    {
        for (unsigned int i = ik - 1; i < k; i++)
        {
            losers[i + k].source = -1;
            losers[i + k].keyp = &_sentinel;
        }
    }

    ~LoserTreePointerUnguardedBase()
    {
        delete[] losers;
    }

    void print(std::ostream& os)
    {
        for (unsigned int i = 0; i < k + ik; i++)
            os << i << "    " << *losers[i].keyp << " from " << losers[i].source << "\n";
    }

    int get_min_source()
    {
        return losers[0].source;
    }

    void insert_start(const ValueType& key, int source)
    {
        unsigned int pos = k + source;

        losers[pos].source = source;
        losers[pos].keyp = &key;
    }

    unsigned int init_winner(unsigned int root)
    {
        if (root >= k)
        {
            return root;
        }
        else
        {
            unsigned int left = init_winner(2 * root);
            unsigned int right = init_winner(2 * root + 1);
            if (!comp(*losers[right].keyp, *losers[left].keyp))
            {                   //left one is less or equal
                losers[root] = losers[right];
                return left;
            }
            else
            {                   //right one is less
                losers[root] = losers[left];
                return right;
            }
        }
    }

    void init()
    {
        losers[0] = losers[init_winner(1)];
    }
};

template <bool Stable /* == false */,
          typename ValueType, typename Comparator = std::less<ValueType> >
class LoserTreePointerUnguarded
    : public LoserTreePointerUnguardedBase<ValueType, Comparator>
{
protected:
    typedef LoserTreePointerUnguardedBase<ValueType, Comparator> base_type;

    using base_type::k;
    using base_type::losers;
    using base_type::comp;

public:
    LoserTreePointerUnguarded(unsigned int _k, const ValueType& _sentinel,
                              Comparator _comp = std::less<ValueType>())
        : base_type(_k, _sentinel, _comp)
    { }

    void delete_min_insert(const ValueType& key)
    {
        using std::swap;

        const ValueType* keyp = &key;
        int source = losers[0].source;
        for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
        {
            //the smaller one gets promoted
            if (comp(*losers[pos].keyp, *keyp))
            {
                //the other one is smaller
                swap(losers[pos].source, source);
                swap(losers[pos].keyp, keyp);
            }
        }

        losers[0].source = source;
        losers[0].keyp = keyp;
    }
};

template <typename ValueType, typename Comparator>
class LoserTreePointerUnguarded</* Stable == */ true, ValueType, Comparator>
    : public LoserTreePointerUnguardedBase<ValueType, Comparator>
{
protected:
    typedef LoserTreePointerUnguardedBase<ValueType, Comparator> base_type;

    using base_type::k;
    using base_type::losers;
    using base_type::comp;

public:
    LoserTreePointerUnguarded(unsigned int _k, const ValueType& _sentinel,
                              Comparator _comp = std::less<ValueType>())
        : base_type(_k, _sentinel, _comp)
    { }

    void delete_min_insert(const ValueType& key)
    {
        using std::swap;

        const ValueType* keyp = &key;
        int source = losers[0].source;
        for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
        {
            //the smaller one gets promoted, ties are broken by source
            if (comp(*losers[pos].keyp, *keyp) ||
                (!comp(*keyp, *losers[pos].keyp) && losers[pos].source < source))
            {
                //the other one is smaller
                swap(losers[pos].source, source);
                swap(losers[pos].keyp, keyp);
            }
        }

        losers[0].source = source;
        losers[0].keyp = keyp;
    }
};

} // namespace parallel

STXXL_END_NAMESPACE

#endif // !STXXL_PARALLEL_LOSERTREE_HEADER