<tt.rantala@gmail.com>
namespace rantala {
static inline unsigned log2(unsigned n)
{ return 8*sizeof(unsigned)-1-__builtin_clz(n); }
template <typename T>
struct loser_tree
{
typedef struct { T* stream; size_t n; } Stream;
unsigned* restrict _nodes;
Stream* restrict _streams;
unsigned _nonempty_streams;
const unsigned _stream_offset;
template <typename Iterator>
loser_tree(Iterator begin, Iterator end)
: _nodes(0), _streams(0), _nonempty_streams(end-begin),
_stream_offset(1 << (log2(_nonempty_streams-1)+1))
{
assert(_nonempty_streams>1);
void* raw = malloc(_stream_offset*sizeof(unsigned) +
_stream_offset*sizeof(Stream));
_nodes = static_cast<unsigned*>(raw);
_streams = reinterpret_cast<Stream*>(
static_cast<char*>(raw) +
_stream_offset*sizeof(unsigned));
for (unsigned i=0; i < _nonempty_streams; ++i) {
_streams[i].stream = begin[i].first;
_streams[i].n = begin[i].second;
}
(void) memset(_streams+_nonempty_streams, 0,
(_stream_offset-_nonempty_streams)*sizeof(Stream));
_nodes[0] = init_min(1);
}
~loser_tree()
{
assert(_nodes); assert(_streams);
free(static_cast<void*>(_nodes));
}
Stream& node2stream(unsigned pos)
{
assert(pos < _stream_offset);
assert(_nodes[pos] < _stream_offset);
return _streams[_nodes[pos]];
}
bool stream_empty(Stream& pos) const { return pos.n == size_t(0); }
unsigned init_min(unsigned root)
{
if (root >= _stream_offset) { return root-_stream_offset; }
const unsigned l = init_min(root << 1);
const unsigned r = init_min((root << 1) + 1);
if (stream_empty(_streams[r])) {
_nodes[root] = r;
return l;
}
if (stream_empty(_streams[l])) {
_nodes[root] = l;
return r;
}
if (cmp(*(_streams[l].stream), *(_streams[r].stream)) <= 0) {
_nodes[root] = r;
return l;
}
_nodes[root] = l;
return r;
}
bool empty() const { return _nonempty_streams == 0; }
void update()
{
unsigned new_min = _nodes[0];
for (unsigned i=(_stream_offset+new_min) >> 1; i!=0; i >>= 1) {
if (stream_empty(_streams[new_min]) or
(not stream_empty(node2stream(i)) and
cmp(*node2stream(i).stream,
*_streams[new_min].stream) < 0)) {
std::swap(new_min, _nodes[i]);
}
}
_nodes[0] = new_min;
}
T min()
{
assert(_nonempty_streams);
assert(not stream_empty(node2stream(0)));
T ret = *(node2stream(0).stream++);
if (--node2stream(0).n == size_t(0)) { --_nonempty_streams; }
update();
return ret;
}
};
#ifndef NDEBUG
#include <ostream>
template <typename T>
std::ostream& operator<<(std::ostream& strm, const loser_tree<T>& tree)
{
strm<<"/-------------------\n";
for(unsigned i=0;i<tree._stream_offset;++i){
if(i==1)strm<<"--------------------\n";
strm<<i<<": "<<tree._nodes[i]<<"\n";
}
strm<<"--------------------\n";
for(unsigned i=0;i<tree._stream_offset;++i)
strm<<i<<": "<<tree._streams[i].stream
<<", n="<<tree._streams[i].n<<"\n";
strm<<"-------------------/\n";
return strm;
}
#endif
}