winner_tree.h

Go to the documentation of this file.

/***************************************************************************
 *  include/stxxl/bits/common/winner_tree.h
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright (C) 2014 Thomas Keh <[email protected]>
 *  Copyright (C) 2014 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_COMMON_WINNER_TREE_HEADER
#define STXXL_COMMON_WINNER_TREE_HEADER

#include <vector>
#include <limits>

#include <stxxl/bits/common/timer.h>
#include <stxxl/bits/common/utils.h>
#include <stxxl/bits/verbose.h>

STXXL_BEGIN_NAMESPACE

/*!
 * The class winner_tree is a binary tournament tree. There are n=2^k so
 * called players which compete for the winning position. The winner is the
 * smallest one regarding the comparator m_less. Each player is identified with
 * it's index. The comparator should use this index in order to compare the
 * actual values.
 *
 * A change of one players value results in O(log n) operations.  The winner
 * can be determined in O(1) operations.
 *
 * There is a number of fixed players which remain at the same index forever,
 * even if they were deactivated in between. Additionally any number of players
 * can be added dynamically. They are assigned to a free slot and if one gets
 * removed the slot will be marked free again.
 */
template <typename Comparator>
class winner_tree
{
protected:
    //! the binary tree of size 2^(k+1)-1
    std::vector<unsigned_type> m_tree;

    //! the comparator object of this tree
    Comparator& m_less;

    //! number of slots for the players (2^k)
    unsigned_type m_num_slots;

    //! Defines if statistics are gathered: fake_timer or timer
    typedef fake_timer stats_timer;

    //! Collection of stats from the winner_tree
    struct stats_type
    {
        stats_timer replay_time;
        stats_timer double_num_slots_time;
        stats_timer remove_player_time;

        friend std::ostream& operator << (std::ostream& os, const stats_type& o)
        {
            return os << "replay_time=" << o.replay_time << std::endl
                      << "double_num_slots_time=" << o.double_num_slots_time << std::endl
                      << "remove_player_time=" << o.remove_player_time << std::endl;
        }
    };

    //! Collection of stats from the winner_tree
    stats_type m_stats;

    const unsigned_type invalid_key = std::numeric_limits<unsigned_type>::max();

public:
    /**
     * Constructor. Reserves space, registers free slots. No games are played
     * here! All players and slots are deactivated in the beginning.
     *
     * \param num_players Number of fixed players. Fixed players remain at the
     * same index forever, even if they were deactivated in between.
     *
     * \param less The comparator. It should use two given indices, compare the
     * corresponding values and return the index of one with the smaller value.
     */
    winner_tree(unsigned_type num_players, Comparator& less)
        : m_less(less)
    {
        STXXL_ASSERT(num_players > 0 && num_players <= invalid_key);

        m_num_slots = (1 << ilog2_ceil(num_players));
        unsigned_type treesize = (m_num_slots << 1) - 1;
        m_tree.resize(treesize, invalid_key);
    }

    //! activate one of the static players or add a new one and replay
    inline void activate_player(unsigned_type index)
    {
        STXXL_ASSERT(index != invalid_key);
        while (index >= m_num_slots)
            double_num_slots();
        replay_on_change(index);
    }

    //! activate a player and resize if necessary
    inline void activate_without_replay(unsigned_type index)
    {
        STXXL_ASSERT(index != invalid_key);
        while (index >= m_num_slots)
            double_num_slots();
        m_tree[((m_tree.size() / 2) + index)] = index;
    }

    //! deactivate a player
    inline void deactivate_without_replay(unsigned_type index)
    {
        STXXL_ASSERT(index != invalid_key);
        STXXL_ASSERT(index < m_num_slots);
        m_tree[((m_tree.size() / 2) + index)] = invalid_key;
    }

    //! deactivate a player and replay.
    inline void deactivate_player(unsigned_type index)
    {
        STXXL_ASSERT(index != invalid_key);
        STXXL_ASSERT(index < m_num_slots);
        replay_on_change(index, true);
    }

    /**
     * deactivate one player in a batch of deactivations run
     * replay_on_deactivation() afterwards. If there are multiple consecutive
     * removes you should run deactivate_player_step() for all of them first and
     * afterwards run replay_on_deactivation() for each one of them.
     */
    inline void deactivate_player_step(unsigned_type index)
    {
        STXXL_ASSERT(index != invalid_key);
        STXXL_ASSERT(index < m_num_slots);

        m_stats.remove_player_time.start();
        unsigned_type p = (m_tree.size() / 2) + index;

        // Needed for following deactivations...
        while (p > 0 && m_tree[p] == index) {
            m_tree[p] = invalid_key;
            p -= (p + 1) % 2; // move to left sibling if necessary
            p /= 2;           // move to parent
        }

        if (m_tree[0] == index)
            m_tree[0] = invalid_key;

        m_stats.remove_player_time.stop();
    }

    //! Replay after the player at index has been deactivated.
    inline void replay_on_deactivations(unsigned_type index)
    {
        STXXL_ASSERT(index != invalid_key);
        STXXL_ASSERT(index < m_num_slots);
        replay_on_change(index, true);
    }

    //! Notify that the value of the player at index has changed.
    inline void notify_change(unsigned_type index)
    {
        STXXL_ASSERT(index != invalid_key);
        replay_on_change(index);
    }

    //! Returns the winner.
    //! Remember running replay_on_pop() if the value of the winner changes.
    inline unsigned_type top() const
    {
        return m_tree[0];
    }

    //! Returns if all players are deactivated.
    inline bool empty() const
    {
        return (m_tree[0] == invalid_key);
    }

    //! Return the current number of slots
    size_t num_slots() const
    {
        return m_num_slots;
    }

    //! Replay after the value of the winning player has changed.
    inline void replay_on_pop()
    {
        STXXL_ASSERT(!empty());
        replay_on_change(m_tree[0]);
    }

    /**
     * Replays all games the player with the given index is involved in.  This
     * corresponds to the path from leaf [index] to root.  If only the value of
     * player [index] has changed the result is a valid winner tree.
     *
     * \param index     The player whose value has changed.
     *
     * \param done      Set done to true if the player has been deactivated
     *                  or removed. All games will be lost then.
     */
    inline void replay_on_change(unsigned_type index, bool done = false)
    {
        STXXL_ASSERT(index != invalid_key);
        m_stats.replay_time.start();

        unsigned_type top;
        unsigned_type p = (m_tree.size() / 2) + index;

        if (!done)
            top = index;
        else
            top = invalid_key;

        while (p > 0) {
            m_tree[p] = top;
            p -= (p + 1) % 2; // round down to left node position

            if (m_tree[p] == invalid_key)
                top = m_tree[p + 1];
            else if (m_tree[p + 1] == invalid_key)
                top = m_tree[p];
            else if (m_less(m_tree[p], m_tree[p + 1]))
                top = m_tree[p];
            else
                top = m_tree[p + 1];

            p /= 2;
        }

        m_tree[p] = top;
        m_stats.replay_time.stop();
    }

    //! Doubles the number of slots and adapts the tree so it's a valid winner
    //! tree again.
    inline void double_num_slots()
    {
        m_stats.double_num_slots_time.start();

        m_num_slots = m_num_slots << 1;
        size_t old_tree_size = m_tree.size();
        size_t tree_size = (m_num_slots << 1) - 1;
        m_tree.resize(tree_size, invalid_key);

        for (unsigned_type i = old_tree_size - 1; i >= 0; --i) {
            size_t old_index = i;
            size_t old_level = ilog2_floor(old_index + 1);
            size_t new_index = old_index + (1 << old_level);
            m_tree[new_index] = m_tree[old_index];
        }

        size_t step_size = (1 << ilog2_floor(old_tree_size));
        size_t index = tree_size - 1;

        while (step_size > 0) {
            for (size_t i = 0; i < step_size; ++i) {
                m_tree[index] = invalid_key;
                --index;
            }
            index -= step_size;
            step_size /= 2;
        }

        m_stats.double_num_slots_time.stop();
    }

    //! Deactivate all players
    inline void clear()
    {
        std::fill(m_tree.begin(), m_tree.end(), invalid_key);
    }

    inline void resize(unsigned_type num_players)
    {
        m_num_slots = (1 << ilog2_ceil(num_players));
        unsigned_type treesize = (m_num_slots << 1) - 1;
        m_tree.resize(treesize, invalid_key);
    }

    //! Deactivate all players and resize the tree.
    inline void resize_and_clear(unsigned_type num_players)
    {
        resize(num_players);
        clear();
    }

    inline void resize_and_rebuild(unsigned_type num_players)
    {
        //resize(num_players);
        STXXL_ASSERT(num_players > 0);
        resize_and_clear(num_players);
        for (unsigned_type i = 0; i < num_players; ++i)
            activate_without_replay(i);
        //for (unsigned_type i=num_players; i<m_num_slots; ++i)
        //    deactivate_without_replay(i);
        rebuild();
    }

    //! Build from winner tree from scratch.
    inline void rebuild()
    {
        unsigned_type i = (m_tree.size() / 2);

        if (i == 0)
            return;

        do {
            --i;
            const unsigned_type lc = i * 2 + 1; // m_tree.size() is uneven -> index OK
            const unsigned_type rc = i * 2 + 2;
            unsigned_type winner;

            if (m_tree[lc] == invalid_key)
                winner = m_tree[rc];
            else if (m_tree[rc] == invalid_key)
                winner = m_tree[lc];
            else if (m_less(m_tree[lc], m_tree[rc]))
                winner = m_tree[lc];
            else
                winner = m_tree[rc];

            m_tree[i] = winner;
        } while (i > 0);
    }

    //! Returns a readable representation of the winner tree as string.
    std::string to_string() const
    {
        std::ostringstream ss;
        unsigned_type levelsize = 1;
        unsigned_type j = 0;
        for (unsigned_type i = 0; i < m_tree.size(); ++i) {
            if (i >= j + levelsize) {
                ss << "\n";
                j = i;
                levelsize *= 2;
            }
            if (m_tree[i] != invalid_key)
                ss << m_tree[i] << " ";
            else
                ss << "~ ";
        }
        ss << "\n";
        return ss.str();
    }

    //! Print statistical data.
    void print_stats() const
    {
        STXXL_VARDUMP(m_num_slots);
        STXXL_MSG(m_stats);
    }
};

STXXL_END_NAMESPACE

#endif // !STXXL_COMMON_WINNER_TREE_HEADER