/******************************************************************************
* src/tools/losertree.h
*
* Loser tree implementation with improved caching of equality.
*
******************************************************************************
* Copyright (C) 2012 Timo Bingmann
*
* This program is free software: you can redistribute it and/or modify it
* under the terms of the GNU General Public License as published by the Free
* Software Foundation, either version 3 of the License, or (at your option)
* any later version.
*
* This program is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
* more details.
*
* You should have received a copy of the GNU General Public License along with
* this program. If not, see .
*****************************************************************************/
template
class LoserTree3Way
{
private:
/// marker inside loser tree to save equality comparisons
static const uint32_t EqualMark = 0x80000000;
/// marker inside loser tree for finished players
static const uint32_t DoneMark = 0x7FFFFFFF;
/// the comparator object of this tree
const Comparator& m_cmp;
/// number of players
unsigned int m_size;
/// the tree of size n-1
std::vector m_tree;
/// saves the equality mark of top after extraction
bool m_top_equal;
/// all players are done
bool m_done;
public:
/// Initialize loser tree and play initial games.
LoserTree3Way(const Comparator& cmp)
: m_cmp(cmp)
{
}
/// Play initial round of comparison games.
bool play_initial(unsigned int size)
{
m_size = size;
m_top_equal = false;
m_done = false;
// initialize loser tree of appropriate size (round up to power of two)
unsigned int treesize = (1 << (int)(log2(size - 1) + 2)) - 1;
if (treesize == 0) treesize = 1;
m_tree.resize(treesize, DoneMark);
// fill in lowest level: all ascending player numbers
int levelput = m_tree.size() / 2;
for (unsigned int i = 0; i < m_size; ++i)
{
m_tree[levelput + i] = m_cmp.exists(i) ? i : DoneMark;
}
unsigned int levelsize = levelput + 1;
// construct higher levels iteratively from bottom up
while ( levelsize > 1 )
{
levelsize = levelsize / 2;
int levelget = levelput;
levelput /= 2;
for (unsigned int i = 0; i < levelsize; ++i)
{
if ( m_tree[levelget + 2*i + 1] == DoneMark )
m_tree[levelput + i] = m_tree[levelget + 2*i] & ~EqualMark;
else if ( m_tree[levelget + 2*i] == DoneMark )
m_tree[levelput + i] = m_tree[levelget + 2*i + 1] & ~EqualMark;
else
{
int cmp = m_cmp( m_tree[levelget + 2*i] & ~EqualMark, m_tree[levelget + 2*i + 1] & ~EqualMark );
if (cmp < 0)
m_tree[levelput + i] = m_tree[levelget + 2*i] & ~EqualMark;
else if (cmp == 0)
m_tree[levelput + i] = m_tree[levelget + 2*i] | EqualMark;
else
m_tree[levelput + i] = m_tree[levelget + 2*i + 1] & ~EqualMark;
}
}
}
m_top_equal = false;
return (m_done = (m_tree[0] == DoneMark));
}
/// Get the top element of the tree: index of the losing player.
unsigned int top() const
{
return m_tree[0] & ~EqualMark;
}
/// Get flag whether the current losing player's key is equal to the previous one's. If this returns true,
/// the previous key is _always_ equal to this one. However, this flag _need_not_ be set if the previous
/// keys are equal. Due to optimization in the comparison tree, it might not have been necessary to
/// compare the two player's keys directly.
bool top_equal() const
{
return m_top_equal;
}
/// Extract the currently losing player and replay the tree with the new updated values for the losing
/// player. (The updates are performed outside of the tree implementation.)
bool replay()
{
m_top_equal = (m_tree[0] & EqualMark); // save equality marker for query
int top = m_tree[0] & ~EqualMark;
int p = (m_tree.size() / 2) + top;
if (!m_cmp.exists(top)) top = DoneMark; // mark player as done
while( p > 0 )
{
m_tree[p] = top;
p -= (p+1) % 2; // round down to left node position
if (m_tree[p] == DoneMark)
top = m_tree[p+1] & ~EqualMark;
else if (m_tree[p+1] == DoneMark)
top = m_tree[p] & ~EqualMark;
else
if (m_tree[p/2] & EqualMark)
{
// do nothing, the previous comparison of the parent key was equal -> this key can only be
// greater-equal than that one.
top = m_tree[p+1] & ~EqualMark;
}
else
{
int cmp = m_cmp( m_tree[p] & ~EqualMark, m_tree[p+1] & ~EqualMark );
if ( cmp < 0 )
top = m_tree[p] & ~EqualMark;
else if (cmp == 0)
top = m_tree[p] | EqualMark;
else
top = m_tree[p+1] & ~EqualMark;
}
p /= 2;
}
assert(p == 0);
m_tree[0] = top;
return (m_done = (m_tree[0] == DoneMark));
}
/// Return true if all players are done
bool done() const
{
return m_done;
}
void print() const
{
unsigned int levelsize = 1;
unsigned int j = 0;
for (unsigned int i = 0; i < m_tree.size(); ++i)
{
if (i >= j + levelsize) {
std::cout << "\n";
j = i; levelsize *= 2;
}
std::cout << (m_tree[i] & ~EqualMark) << ((m_tree[i] & EqualMark) ? 'e' : ' ') << " ";
}
std::cout << "\n";
}
};