*
* The smallest element is at the top.
*
- * Guarding is done explicitly through one flag sup per element,
+ * Guarding is done explicitly through one flag _M_sup per element,
* inf is not needed due to a better initialization routine. This
* is a well-performing variant.
*
- * @param T the element type
- * @param Comparator the comparator to use, defaults to std::less<T>
+ * @param _Tp the element _Self
+ * @param _Compare the comparator to use, defaults to std::less<_Tp>
*/
-template<typename T, typename Comparator>
+template<typename _Tp, typename _Compare>
class LoserTreeBase
{
protected:
/** @brief Internal representation of a LoserTree element. */
- struct Loser
- {
- /** @brief flag, true iff this is a "maximum" sentinel. */
- bool sup;
- /** @brief index of the source sequence. */
- int source;
- /** @brief key of the element in the LoserTree. */
- T key;
+ struct _Loser
+ {
+ /** @brief flag, true iff this is a "maximum" __sentinel. */
+ bool _M_sup;
+ /** @brief __index of the _M_source __sequence. */
+ int _M_source;
+ /** @brief _M_key of the element in the LoserTree. */
+ _Tp _M_key;
};
- unsigned int ik, k, offset;
+ unsigned int __ik, __k, __offset;
- /** log_2{k} */
+ /** log_2{__k} */
unsigned int _M_log_k;
- /** @brief LoserTree elements. */
- Loser* losers;
+ /** @brief LoserTree __elements. */
+ _Loser* __losers;
- /** @brief Comparator to use. */
- Comparator comp;
+ /** @brief _Compare to use. */
+ _Compare __comp;
/**
* @brief State flag that determines whether the LoserTree is empty.
*
* Only used for building the LoserTree.
*/
- bool first_insert;
+ bool __first_insert;
public:
/**
* @param _k The number of sequences to merge.
* @param _comp The comparator to use.
*/
- LoserTreeBase(unsigned int _k, Comparator _comp)
- : comp(_comp)
+ LoserTreeBase(unsigned int _k, _Compare _comp)
+ : __comp(_comp)
{
- ik = _k;
+ __ik = _k;
- // Compute log_2{k} for the Loser Tree
- _M_log_k = __log2(ik - 1) + 1;
+ // Compute log_2{__k} for the _Loser Tree
+ _M_log_k = __log2(__ik - 1) + 1;
// Next greater power of 2.
- k = 1 << _M_log_k;
- offset = k;
+ __k = 1 << _M_log_k;
+ __offset = __k;
- // Avoid default-constructing losers[].key
- losers = static_cast<Loser*>(::operator new(2 * k * sizeof(Loser)));
- for (unsigned int i = ik - 1; i < k; ++i)
- losers[i + k].sup = true;
+ // Avoid default-constructing __losers[]._M_key
+ __losers = static_cast<_Loser*>(::operator new(2 * __k * sizeof(_Loser)));
+ for (unsigned int __i = __ik - 1; __i < __k; ++__i)
+ __losers[__i + __k]._M_sup = true;
- first_insert = true;
+ __first_insert = true;
}
/**
* @brief The destructor.
*/
~LoserTreeBase()
- { ::operator delete(losers); }
+ { ::operator delete(__losers); }
/**
- * @brief Initializes the sequence "source" with the element "key".
+ * @brief Initializes the sequence "_M_source" with the element "_M_key".
*
- * @param key the element to insert
- * @param source index of the source sequence
- * @param sup flag that determines whether the value to insert is an
- * explicit supremum.
+ * @param _M_key the element to insert
+ * @param _M_source __index of the _M_source __sequence
+ * @param _M_sup flag that determines whether the value to insert is an
+ * explicit __supremum.
*/
inline void
- insert_start(const T& key, int source, bool sup)
+ __insert_start(const _Tp& _M_key, int _M_source, bool _M_sup)
{
- unsigned int pos = k + source;
+ unsigned int __pos = __k + _M_source;
- if(first_insert)
+ if(__first_insert)
{
// Construct all keys, so we can easily deconstruct them.
- for (unsigned int i = 0; i < (2 * k); ++i)
- new(&(losers[i].key)) T(key);
- first_insert = false;
+ for (unsigned int __i = 0; __i < (2 * __k); ++__i)
+ new(&(__losers[__i]._M_key)) _Tp(_M_key);
+ __first_insert = false;
}
else
- new(&(losers[pos].key)) T(key);
+ new(&(__losers[__pos]._M_key)) _Tp(_M_key);
- losers[pos].sup = sup;
- losers[pos].source = source;
+ __losers[__pos]._M_sup = _M_sup;
+ __losers[__pos]._M_source = _M_source;
}
/**
* @return the index of the sequence with the smallest element.
*/
- int get_min_source()
- { return losers[0].source; }
+ int __get_min_source()
+ { return __losers[0]._M_source; }
};
/**
* @brief Stable LoserTree variant.
*
- * Provides the stable implementations of insert_start, init_winner,
- * init and delete_min_insert.
+ * Provides the stable implementations of insert_start, __init_winner,
+ * __init and __delete_min_insert.
*
* Unstable variant is done using partial specialisation below.
*/
-template<bool stable/* default == true */, typename T, typename Comparator>
-class LoserTree : public LoserTreeBase<T, Comparator>
+template<bool __stable/* default == true */, typename _Tp, typename _Compare>
+class LoserTree : public LoserTreeBase<_Tp, _Compare>
{
- typedef LoserTreeBase<T, Comparator> Base;
- using Base::k;
- using Base::losers;
- using Base::first_insert;
+ typedef LoserTreeBase<_Tp, _Compare> Base;
+ using Base::__k;
+ using Base::__losers;
+ using Base::__first_insert;
public:
- LoserTree(unsigned int _k, Comparator _comp)
+ LoserTree(unsigned int _k, _Compare _comp)
: Base::LoserTreeBase(_k, _comp)
{}
unsigned int
- init_winner(unsigned int root)
+ __init_winner(unsigned int __root)
{
- if (root >= k)
+ if (__root >= __k)
{
- return root;
+ 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(losers[right].key, losers[left].key)))
+ unsigned int __left = __init_winner (2 * __root);
+ unsigned int __right = __init_winner (2 * __root + 1);
+ if (__losers[__right]._M_sup
+ || (!__losers[__left]._M_sup
+ && !__comp(__losers[__right]._M_key, __losers[__left]._M_key)))
{
// Left one is less or equal.
- losers[root] = losers[right];
- return left;
+ __losers[__root] = __losers[__right];
+ return __left;
}
else
{
// Right one is less.
- losers[root] = losers[left];
- return right;
+ __losers[__root] = __losers[__left];
+ return __right;
}
}
}
- void init()
- { losers[0] = losers[init_winner(1)]; }
+ void __init()
+ { __losers[0] = __losers[__init_winner(1)]; }
/**
* @brief Delete the smallest element and insert a new element from
*
* This implementation is stable.
*/
- // Do not pass a const reference since key will be used as local variable.
- void delete_min_insert(T key, bool sup)
+ // Do not pass a const reference since _M_key will be used as local variable.
+ void __delete_min_insert(_Tp _M_key, bool _M_sup)
{
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top!
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
- int source = losers[0].source;
- for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ int _M_source = __losers[0]._M_source;
+ for (unsigned int __pos = (__k + _M_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].key, key))
- || (!comp(key, losers[pos].key)
- && losers[pos].source < source))))
+ // The smaller one gets promoted, ties are broken by _M_source.
+ if ((_M_sup && (!__losers[__pos]._M_sup || __losers[__pos]._M_source < _M_source))
+ || (!_M_sup && !__losers[__pos]._M_sup
+ && ((__comp(__losers[__pos]._M_key, _M_key))
+ || (!__comp(_M_key, __losers[__pos]._M_key)
+ && __losers[__pos]._M_source < _M_source))))
{
// The other one is smaller.
- std::swap(losers[pos].sup, sup);
- std::swap(losers[pos].source, source);
- std::swap(losers[pos].key, key);
+ std::swap(__losers[__pos]._M_sup, _M_sup);
+ std::swap(__losers[__pos]._M_source, _M_source);
+ std::swap(__losers[__pos]._M_key, _M_key);
}
}
- losers[0].sup = sup;
- losers[0].source = source;
- losers[0].key = key;
+ __losers[0]._M_sup = _M_sup;
+ __losers[0]._M_source = _M_source;
+ __losers[0]._M_key = _M_key;
}
};
*
* Stability (non-stable here) is selected with partial specialization.
*/
-template<typename T, typename Comparator>
-class LoserTree</* stable == */false, T, Comparator> :
- public LoserTreeBase<T, Comparator>
+template<typename _Tp, typename _Compare>
+class LoserTree</* __stable == */false, _Tp, _Compare> :
+ public LoserTreeBase<_Tp, _Compare>
{
- typedef LoserTreeBase<T, Comparator> Base;
+ typedef LoserTreeBase<_Tp, _Compare> Base;
using Base::_M_log_k;
- using Base::k;
- using Base::losers;
- using Base::first_insert;
+ using Base::__k;
+ using Base::__losers;
+ using Base::__first_insert;
public:
- LoserTree(unsigned int _k, Comparator _comp)
+ LoserTree(unsigned int _k, _Compare _comp)
: Base::LoserTreeBase(_k, _comp)
{}
/**
- * Computes the winner of the competition at position "root".
+ * Computes the winner of the competition at __position "__root".
*
* Called recursively (starting at 0) to build the initial tree.
*
- * @param root index of the "game" to start.
+ * @param __root __index of the "game" to start.
*/
unsigned int
- init_winner (unsigned int root)
+ __init_winner (unsigned int __root)
{
- if (root >= k)
+ if (__root >= __k)
{
- return root;
+ 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(losers[right].key, losers[left].key)))
+ unsigned int __left = __init_winner (2 * __root);
+ unsigned int __right = __init_winner (2 * __root + 1);
+ if (__losers[__right]._M_sup ||
+ (!__losers[__left]._M_sup
+ && !__comp(__losers[__right]._M_key, __losers[__left]._M_key)))
{
// Left one is less or equal.
- losers[root] = losers[right];
- return left;
+ __losers[__root] = __losers[__right];
+ return __left;
}
else
{
// Right one is less.
- losers[root] = losers[left];
- return right;
+ __losers[__root] = __losers[__left];
+ return __right;
}
}
}
inline void
- init()
- { losers[0] = losers[init_winner(1)]; }
+ __init()
+ { __losers[0] = __losers[__init_winner(1)]; }
/**
- * Delete the key smallest element and insert the element key instead.
+ * Delete the _M_key smallest element and insert the element _M_key instead.
*
- * @param key the key to insert
- * @param sup true iff key is an explicitly marked supremum
+ * @param _M_key the _M_key to insert
+ * @param _M_sup true iff _M_key is an explicitly marked supremum
*/
- // Do not pass a const reference since key will be used as local variable.
+ // Do not pass a const reference since _M_key will be used as local variable.
inline void
- delete_min_insert(T key, bool sup)
+ __delete_min_insert(_Tp _M_key, bool _M_sup)
{
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top!
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
- int source = losers[0].source;
- for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ int _M_source = __losers[0]._M_source;
+ for (unsigned int __pos = (__k + _M_source) / 2; __pos > 0; __pos /= 2)
{
// The smaller one gets promoted.
- if (sup || (!losers[pos].sup && comp(losers[pos].key, key)))
+ if (_M_sup || (!__losers[__pos]._M_sup && __comp(__losers[__pos]._M_key, _M_key)))
{
// The other one is smaller.
- std::swap(losers[pos].sup, sup);
- std::swap(losers[pos].source, source);
- std::swap(losers[pos].key, key);
+ std::swap(__losers[__pos]._M_sup, _M_sup);
+ std::swap(__losers[__pos]._M_source, _M_source);
+ std::swap(__losers[__pos]._M_key, _M_key);
}
}
- losers[0].sup = sup;
- losers[0].source = source;
- losers[0].key = key;
+ __losers[0]._M_sup = _M_sup;
+ __losers[0]._M_source = _M_source;
+ __losers[0]._M_key = _M_key;
}
};
/**
- * @brief Base class of Loser Tree implementation using pointers.
+ * @brief Base class of _Loser Tree implementation using pointers.
*/
-template<typename T, typename Comparator>
-class LoserTreePointerBase
+template<typename _Tp, typename _Compare>
+class _LoserTreePointerBase
{
protected:
- /** @brief Internal representation of LoserTree elements. */
- struct Loser
+ /** @brief Internal representation of LoserTree __elements. */
+ struct _Loser
{
- bool sup;
- int source;
- const T* keyp;
+ bool _M_sup;
+ int _M_source;
+ const _Tp* _M_keyp;
};
- unsigned int ik, k, offset;
- Loser* losers;
- Comparator comp;
+ unsigned int __ik, __k, __offset;
+ _Loser* __losers;
+ _Compare __comp;
public:
- LoserTreePointerBase(unsigned int _k, Comparator _comp = std::less<T>())
- : comp(_comp)
+ _LoserTreePointerBase(unsigned int _k, _Compare _comp = std::less<_Tp>())
+ : __comp(_comp)
{
- ik = _k;
+ __ik = _k;
// Next greater power of 2.
- k = 1 << (__log2(ik - 1) + 1);
- offset = k;
- losers = new Loser[k * 2];
- for (unsigned int i = ik - 1; i < k; i++)
- losers[i + k].sup = true;
+ __k = 1 << (__log2(__ik - 1) + 1);
+ __offset = __k;
+ __losers = new _Loser[__k * 2];
+ for (unsigned int __i = __ik - 1; __i < __k; __i++)
+ __losers[__i + __k]._M_sup = true;
}
- ~LoserTreePointerBase()
- { ::operator delete[](losers); }
+ ~_LoserTreePointerBase()
+ { ::operator delete[](__losers); }
- int get_min_source()
- { return losers[0].source; }
+ int __get_min_source()
+ { return __losers[0]._M_source; }
- void insert_start(const T& key, int source, bool sup)
+ void __insert_start(const _Tp& _M_key, int _M_source, bool _M_sup)
{
- unsigned int pos = k + source;
+ unsigned int __pos = __k + _M_source;
- losers[pos].sup = sup;
- losers[pos].source = source;
- losers[pos].keyp = &key;
+ __losers[__pos]._M_sup = _M_sup;
+ __losers[__pos]._M_source = _M_source;
+ __losers[__pos]._M_keyp = &_M_key;
}
};
*
* The unstable variant is implemented using partial instantiation below.
*/
-template<bool stable/* default == true */, typename T, typename Comparator>
-class LoserTreePointer : public LoserTreePointerBase<T, Comparator>
+template<bool __stable/* default == true */, typename _Tp, typename _Compare>
+class _LoserTreePointer : public _LoserTreePointerBase<_Tp, _Compare>
{
- typedef LoserTreePointerBase<T, Comparator> Base;
- using Base::k;
- using Base::losers;
+ typedef _LoserTreePointerBase<_Tp, _Compare> Base;
+ using Base::__k;
+ using Base::__losers;
public:
- LoserTreePointer(unsigned int _k, Comparator _comp = std::less<T>())
- : Base::LoserTreePointerBase(_k, _comp)
+ _LoserTreePointer(unsigned int _k, _Compare _comp = std::less<_Tp>())
+ : Base::_LoserTreePointerBase(_k, _comp)
{}
unsigned int
- init_winner(unsigned int root)
+ __init_winner(unsigned int __root)
{
- if (root >= k)
+ if (__root >= __k)
{
- return root;
+ 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(*losers[right].keyp,
- *losers[left].keyp)))
+ unsigned int __left = __init_winner (2 * __root);
+ unsigned int __right = __init_winner (2 * __root + 1);
+ if (__losers[__right]._M_sup
+ || (!__losers[__left]._M_sup && !__comp(*__losers[__right]._M_keyp,
+ *__losers[__left]._M_keyp)))
{
// Left one is less or equal.
- losers[root] = losers[right];
- return left;
+ __losers[__root] = __losers[__right];
+ return __left;
}
else
{
// Right one is less.
- losers[root] = losers[left];
- return right;
+ __losers[__root] = __losers[__left];
+ return __right;
}
}
}
- void init()
- { losers[0] = losers[init_winner(1)]; }
+ void __init()
+ { __losers[0] = __losers[__init_winner(1)]; }
- void delete_min_insert(const T& key, bool sup)
+ void __delete_min_insert(const _Tp& _M_key, bool _M_sup)
{
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top!
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
- const T* keyp = &key;
- int source = losers[0].source;
- for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ const _Tp* _M_keyp = &_M_key;
+ int _M_source = __losers[0]._M_source;
+ for (unsigned int __pos = (__k + _M_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 smaller one gets promoted, ties are broken by _M_source.
+ if ((_M_sup && (!__losers[__pos]._M_sup || __losers[__pos]._M_source < _M_source)) ||
+ (!_M_sup && !__losers[__pos]._M_sup &&
+ ((__comp(*__losers[__pos]._M_keyp, *_M_keyp)) ||
+ (!__comp(*_M_keyp, *__losers[__pos]._M_keyp)
+ && __losers[__pos]._M_source < _M_source))))
{
// The other one is smaller.
- std::swap(losers[pos].sup, sup);
- std::swap(losers[pos].source, source);
- std::swap(losers[pos].keyp, keyp);
+ std::swap(__losers[__pos]._M_sup, _M_sup);
+ std::swap(__losers[__pos]._M_source, _M_source);
+ std::swap(__losers[__pos]._M_keyp, _M_keyp);
}
}
- losers[0].sup = sup;
- losers[0].source = source;
- losers[0].keyp = keyp;
+ __losers[0]._M_sup = _M_sup;
+ __losers[0]._M_source = _M_source;
+ __losers[0]._M_keyp = _M_keyp;
}
};
*
* The stable variant is above.
*/
-template<typename T, typename Comparator>
-class LoserTreePointer</* stable == */false, T, Comparator> :
- public LoserTreePointerBase<T, Comparator>
+template<typename _Tp, typename _Compare>
+class _LoserTreePointer</* __stable == */false, _Tp, _Compare> :
+ public _LoserTreePointerBase<_Tp, _Compare>
{
- typedef LoserTreePointerBase<T, Comparator> Base;
- using Base::k;
- using Base::losers;
+ typedef _LoserTreePointerBase<_Tp, _Compare> Base;
+ using Base::__k;
+ using Base::__losers;
public:
- LoserTreePointer(unsigned int _k, Comparator _comp = std::less<T>())
- : Base::LoserTreePointerBase(_k, _comp)
+ _LoserTreePointer(unsigned int _k, _Compare _comp = std::less<_Tp>())
+ : Base::_LoserTreePointerBase(_k, _comp)
{}
unsigned int
- init_winner(unsigned int root)
+ __init_winner(unsigned int __root)
{
- if (root >= k)
+ if (__root >= __k)
{
- return root;
+ 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(*losers[right].keyp, *losers[left].keyp)))
+ unsigned int __left = __init_winner (2 * __root);
+ unsigned int __right = __init_winner (2 * __root + 1);
+ if (__losers[__right]._M_sup
+ || (!__losers[__left]._M_sup
+ && !__comp(*__losers[__right]._M_keyp, *__losers[__left]._M_keyp)))
{
// Left one is less or equal.
- losers[root] = losers[right];
- return left;
+ __losers[__root] = __losers[__right];
+ return __left;
}
else
{
// Right one is less.
- losers[root] = losers[left];
- return right;
+ __losers[__root] = __losers[__left];
+ return __right;
}
}
}
- void init()
- { losers[0] = losers[init_winner(1)]; }
+ void __init()
+ { __losers[0] = __losers[__init_winner(1)]; }
- void delete_min_insert(const T& key, bool sup)
+ void __delete_min_insert(const _Tp& _M_key, bool _M_sup)
{
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top!
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
- const T* keyp = &key;
- int source = losers[0].source;
- for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ const _Tp* _M_keyp = &_M_key;
+ int _M_source = __losers[0]._M_source;
+ for (unsigned int __pos = (__k + _M_source) / 2; __pos > 0; __pos /= 2)
{
// The smaller one gets promoted.
- if (sup || (!losers[pos].sup && comp(*losers[pos].keyp, *keyp)))
+ if (_M_sup || (!__losers[__pos]._M_sup && __comp(*__losers[__pos]._M_keyp, *_M_keyp)))
{
// The other one is smaller.
- std::swap(losers[pos].sup, sup);
- std::swap(losers[pos].source, source);
- std::swap(losers[pos].keyp, keyp);
+ std::swap(__losers[__pos]._M_sup, _M_sup);
+ std::swap(__losers[__pos]._M_source, _M_source);
+ std::swap(__losers[__pos]._M_keyp, _M_keyp);
}
}
- losers[0].sup = sup;
- losers[0].source = source;
- losers[0].keyp = keyp;
+ __losers[0]._M_sup = _M_sup;
+ __losers[0]._M_source = _M_source;
+ __losers[0]._M_keyp = _M_keyp;
}
};
* The whole element is copied into the tree structure.
*
* No guarding is done, therefore not a single input sequence must
- * run empty. Unused sequence heads are marked with a sentinel which
+ * run empty. Unused __sequence heads are marked with a sentinel which
* is > all elements that are to be merged.
*
* This is a very fast variant.
*/
-template<typename T, typename Comparator>
-class LoserTreeUnguardedBase
+template<typename _Tp, typename _Compare>
+class _LoserTreeUnguardedBase
{
protected:
- struct Loser
+ struct _Loser
{
- int source;
- T key;
+ int _M_source;
+ _Tp _M_key;
};
- unsigned int ik, k, offset;
- Loser* losers;
- Comparator comp;
+ unsigned int __ik, __k, __offset;
+ _Loser* __losers;
+ _Compare __comp;
public:
inline
- LoserTreeUnguardedBase(unsigned int _k, const T _sentinel,
- Comparator _comp = std::less<T>())
- : comp(_comp)
+ _LoserTreeUnguardedBase(unsigned int _k, const _Tp _sentinel,
+ _Compare _comp = std::less<_Tp>())
+ : __comp(_comp)
{
- ik = _k;
+ __ik = _k;
// Next greater power of 2.
- k = 1 << (__log2(ik - 1) + 1);
- offset = k;
- // Avoid default-constructing losers[].key
- losers = static_cast<Loser*>(::operator new(2 * k * sizeof(Loser)));
+ __k = 1 << (__log2(__ik - 1) + 1);
+ __offset = __k;
+ // Avoid default-constructing __losers[]._M_key
+ __losers = static_cast<_Loser*>(::operator new(2 * __k * sizeof(_Loser)));
- for (unsigned int i = k + ik - 1; i < (2 * k); ++i)
+ for (unsigned int __i = __k + __ik - 1; __i < (2 * __k); ++__i)
{
- losers[i].key = _sentinel;
- losers[i].source = -1;
+ __losers[__i]._M_key = _sentinel;
+ __losers[__i]._M_source = -1;
}
}
- inline ~LoserTreeUnguardedBase()
- { ::operator delete(losers); }
+ inline ~_LoserTreeUnguardedBase()
+ { ::operator delete(__losers); }
inline int
- get_min_source()
+ __get_min_source()
{
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top!
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
- return losers[0].source;
+ return __losers[0]._M_source;
}
inline void
- insert_start(const T& key, int source, bool)
+ __insert_start(const _Tp& _M_key, int _M_source, bool)
{
- unsigned int pos = k + source;
+ unsigned int __pos = __k + _M_source;
- new(&(losers[pos].key)) T(key);
- losers[pos].source = source;
+ new(&(__losers[__pos]._M_key)) _Tp(_M_key);
+ __losers[__pos]._M_source = _M_source;
}
};
*
* Unstable variant is selected below with partial specialization.
*/
-template<bool stable/* default == true */, typename T, typename Comparator>
-class LoserTreeUnguarded : public LoserTreeUnguardedBase<T, Comparator>
+template<bool __stable/* default == true */, typename _Tp, typename _Compare>
+class _LoserTreeUnguarded : public _LoserTreeUnguardedBase<_Tp, _Compare>
{
- typedef LoserTreeUnguardedBase<T, Comparator> Base;
- using Base::k;
- using Base::losers;
+ typedef _LoserTreeUnguardedBase<_Tp, _Compare> Base;
+ using Base::__k;
+ using Base::__losers;
public:
- LoserTreeUnguarded(unsigned int _k, const T _sentinel,
- Comparator _comp = std::less<T>())
- : Base::LoserTreeUnguardedBase(_k, _sentinel, _comp)
+ _LoserTreeUnguarded(unsigned int _k, const _Tp _sentinel,
+ _Compare _comp = std::less<_Tp>())
+ : Base::_LoserTreeUnguardedBase(_k, _sentinel, _comp)
{}
unsigned int
- init_winner(unsigned int root)
+ __init_winner(unsigned int __root)
{
- if (root >= k)
+ if (__root >= __k)
{
- return root;
+ 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))
+ unsigned int __left = __init_winner (2 * __root);
+ unsigned int __right = __init_winner (2 * __root + 1);
+ if (!__comp(__losers[__right]._M_key, __losers[__left]._M_key))
{
// Left one is less or equal.
- losers[root] = losers[right];
- return left;
+ __losers[__root] = __losers[__right];
+ return __left;
}
else
{
// Right one is less.
- losers[root] = losers[left];
- return right;
+ __losers[__root] = __losers[__left];
+ return __right;
}
}
}
inline void
- init()
+ __init()
{
- losers[0] = losers[init_winner(1)];
+ __losers[0] = __losers[__init_winner(1)];
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top at the beginning (0 sequences!)
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
}
- // Do not pass a const reference since key will be used as local variable.
+ // Do not pass a const reference since _M_key will be used as local variable.
inline void
- delete_min_insert(T key, bool)
+ __delete_min_insert(_Tp _M_key, bool)
{
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top!
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
- int source = losers[0].source;
- for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ int _M_source = __losers[0]._M_source;
+ for (unsigned int __pos = (__k + _M_source) / 2; __pos > 0; __pos /= 2)
{
- // The smaller one gets promoted, ties are broken by source.
- if (comp(losers[pos].key, key)
- || (!comp(key, losers[pos].key) && losers[pos].source < source))
+ // The smaller one gets promoted, ties are broken by _M_source.
+ if (__comp(__losers[__pos]._M_key, _M_key)
+ || (!__comp(_M_key, __losers[__pos]._M_key) && __losers[__pos]._M_source < _M_source))
{
// The other one is smaller.
- std::swap(losers[pos].source, source);
- std::swap(losers[pos].key, key);
+ std::swap(__losers[__pos]._M_source, _M_source);
+ std::swap(__losers[__pos]._M_key, _M_key);
}
}
- losers[0].source = source;
- losers[0].key = key;
+ __losers[0]._M_source = _M_source;
+ __losers[0]._M_key = _M_key;
}
};
*
* Stable implementation is above.
*/
-template<typename T, typename Comparator>
-class LoserTreeUnguarded</* stable == */false, T, Comparator> :
- public LoserTreeUnguardedBase<T, Comparator>
+template<typename _Tp, typename _Compare>
+class _LoserTreeUnguarded</* __stable == */false, _Tp, _Compare> :
+ public _LoserTreeUnguardedBase<_Tp, _Compare>
{
- typedef LoserTreeUnguardedBase<T, Comparator> Base;
- using Base::k;
- using Base::losers;
+ typedef _LoserTreeUnguardedBase<_Tp, _Compare> Base;
+ using Base::__k;
+ using Base::__losers;
public:
- LoserTreeUnguarded(unsigned int _k, const T _sentinel,
- Comparator _comp = std::less<T>())
- : Base::LoserTreeUnguardedBase(_k, _sentinel, _comp)
+ _LoserTreeUnguarded(unsigned int _k, const _Tp _sentinel,
+ _Compare _comp = std::less<_Tp>())
+ : Base::_LoserTreeUnguardedBase(_k, _sentinel, _comp)
{}
unsigned int
- init_winner (unsigned int root)
+ __init_winner (unsigned int __root)
{
- if (root >= k)
+ if (__root >= __k)
{
- return root;
+ return __root;
}
else
{
- unsigned int left = init_winner (2 * root);
- unsigned int right = init_winner (2 * root + 1);
+ unsigned int __left = __init_winner (2 * __root);
+ unsigned int __right = __init_winner (2 * __root + 1);
#if _GLIBCXX_ASSERTIONS
- // If left one is sentinel then right one must be, too.
- if (losers[left].source == -1)
- _GLIBCXX_PARALLEL_ASSERT(losers[right].source == -1);
+ // If __left one is sentinel then __right one must be, too.
+ if (__losers[__left]._M_source == -1)
+ _GLIBCXX_PARALLEL_ASSERT(__losers[__right]._M_source == -1);
#endif
- if (!comp(losers[right].key, losers[left].key))
+ if (!__comp(__losers[__right]._M_key, __losers[__left]._M_key))
{
// Left one is less or equal.
- losers[root] = losers[right];
- return left;
+ __losers[__root] = __losers[__right];
+ return __left;
}
else
{
// Right one is less.
- losers[root] = losers[left];
- return right;
+ __losers[__root] = __losers[__left];
+ return __right;
}
}
}
inline void
- init()
+ __init()
{
- losers[0] = losers[init_winner(1)];
+ __losers[0] = __losers[__init_winner(1)];
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top at the beginning (0 sequences!)
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
}
- // Do not pass a const reference since key will be used as local variable.
+ // Do not pass a const reference since _M_key will be used as local variable.
inline void
- delete_min_insert(T key, bool)
+ __delete_min_insert(_Tp _M_key, bool)
{
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top!
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
- int source = losers[0].source;
- for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ int _M_source = __losers[0]._M_source;
+ for (unsigned int __pos = (__k + _M_source) / 2; __pos > 0; __pos /= 2)
{
// The smaller one gets promoted.
- if (comp(losers[pos].key, key))
+ if (__comp(__losers[__pos]._M_key, _M_key))
{
// The other one is smaller.
- std::swap(losers[pos].source, source);
- std::swap(losers[pos].key, key);
+ std::swap(__losers[__pos]._M_source, _M_source);
+ std::swap(__losers[__pos]._M_key, _M_key);
}
}
- losers[0].source = source;
- losers[0].key = key;
+ __losers[0]._M_source = _M_source;
+ __losers[0]._M_key = _M_key;
}
};
/** @brief Unguarded loser tree, keeping only pointers to the
-* elements in the tree structure.
+* __elements in the tree structure.
*
* No guarding is done, therefore not a single input sequence must
* run empty. This is a very fast variant.
*/
-template<typename T, typename Comparator>
+template<typename _Tp, typename _Compare>
class LoserTreePointerUnguardedBase
{
protected:
- struct Loser
+ struct _Loser
{
- int source;
- const T* keyp;
+ int _M_source;
+ const _Tp* _M_keyp;
};
- unsigned int ik, k, offset;
- Loser* losers;
- Comparator comp;
+ unsigned int __ik, __k, __offset;
+ _Loser* __losers;
+ _Compare __comp;
public:
inline
- LoserTreePointerUnguardedBase(unsigned int _k, const T& _sentinel,
- Comparator _comp = std::less<T>())
- : comp(_comp)
+ LoserTreePointerUnguardedBase(unsigned int _k, const _Tp& _sentinel,
+ _Compare _comp = std::less<_Tp>())
+ : __comp(_comp)
{
- ik = _k;
+ __ik = _k;
// Next greater power of 2.
- k = 1 << (__log2(ik - 1) + 1);
- offset = k;
- // Avoid default-constructing losers[].key
- losers = new Loser[2 * k];
+ __k = 1 << (__log2(__ik - 1) + 1);
+ __offset = __k;
+ // Avoid default-constructing __losers[]._M_key
+ __losers = new _Loser[2 * __k];
- for (unsigned int i = k + ik - 1; i < (2 * k); ++i)
+ for (unsigned int __i = __k + __ik - 1; __i < (2 * __k); ++__i)
{
- losers[i].keyp = &_sentinel;
- losers[i].source = -1;
+ __losers[__i]._M_keyp = &_sentinel;
+ __losers[__i]._M_source = -1;
}
}
inline ~LoserTreePointerUnguardedBase()
- { delete[] losers; }
+ { delete[] __losers; }
inline int
- get_min_source()
+ __get_min_source()
{
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top!
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
- return losers[0].source;
+ return __losers[0]._M_source;
}
inline void
- insert_start(const T& key, int source, bool)
+ __insert_start(const _Tp& _M_key, int _M_source, bool)
{
- unsigned int pos = k + source;
+ unsigned int __pos = __k + _M_source;
- losers[pos].keyp = &key;
- losers[pos].source = source;
+ __losers[__pos]._M_keyp = &_M_key;
+ __losers[__pos]._M_source = _M_source;
}
};
*
* Unstable variant is implemented below using partial specialization.
*/
-template<bool stable/* default == true */, typename T, typename Comparator>
+template<bool __stable/* default == true */, typename _Tp, typename _Compare>
class LoserTreePointerUnguarded :
- public LoserTreePointerUnguardedBase<T, Comparator>
+ public LoserTreePointerUnguardedBase<_Tp, _Compare>
{
- typedef LoserTreePointerUnguardedBase<T, Comparator> Base;
- using Base::k;
- using Base::losers;
+ typedef LoserTreePointerUnguardedBase<_Tp, _Compare> Base;
+ using Base::__k;
+ using Base::__losers;
public:
- LoserTreePointerUnguarded(unsigned int _k, const T& _sentinel,
- Comparator _comp = std::less<T>())
+ LoserTreePointerUnguarded(unsigned int _k, const _Tp& _sentinel,
+ _Compare _comp = std::less<_Tp>())
: Base::LoserTreePointerUnguardedBase(_k, _sentinel, _comp)
{}
unsigned int
- init_winner(unsigned int root)
+ __init_winner(unsigned int __root)
{
- if (root >= k)
+ if (__root >= __k)
{
- return root;
+ 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))
+ unsigned int __left = __init_winner (2 * __root);
+ unsigned int __right = __init_winner (2 * __root + 1);
+ if (!__comp(*__losers[__right]._M_keyp, *__losers[__left]._M_keyp))
{
// Left one is less or equal.
- losers[root] = losers[right];
- return left;
+ __losers[__root] = __losers[__right];
+ return __left;
}
else
{
// Right one is less.
- losers[root] = losers[left];
- return right;
+ __losers[__root] = __losers[__left];
+ return __right;
}
}
}
inline void
- init()
+ __init()
{
- losers[0] = losers[init_winner(1)];
+ __losers[0] = __losers[__init_winner(1)];
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top at the beginning (0 sequences!)
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
}
inline void
- delete_min_insert(const T& key, bool sup)
+ __delete_min_insert(const _Tp& _M_key, bool _M_sup)
{
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top!
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
- const T* keyp = &key;
- int source = losers[0].source;
- for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ const _Tp* _M_keyp = &_M_key;
+ int _M_source = __losers[0]._M_source;
+ for (unsigned int __pos = (__k + _M_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 smaller one gets promoted, ties are broken by _M_source.
+ if (__comp(*__losers[__pos]._M_keyp, *_M_keyp)
+ || (!__comp(*_M_keyp, *__losers[__pos]._M_keyp) && __losers[__pos]._M_source < _M_source))
{
// The other one is smaller.
- std::swap(losers[pos].source, source);
- std::swap(losers[pos].keyp, keyp);
+ std::swap(__losers[__pos]._M_source, _M_source);
+ std::swap(__losers[__pos]._M_keyp, _M_keyp);
}
}
- losers[0].source = source;
- losers[0].keyp = keyp;
+ __losers[0]._M_source = _M_source;
+ __losers[0]._M_keyp = _M_keyp;
}
};
*
* Stable variant is above.
*/
-template<typename T, typename Comparator>
-class LoserTreePointerUnguarded</* stable == */false, T, Comparator> :
- public LoserTreePointerUnguardedBase<T, Comparator>
+template<typename _Tp, typename _Compare>
+class LoserTreePointerUnguarded</* __stable == */false, _Tp, _Compare> :
+ public LoserTreePointerUnguardedBase<_Tp, _Compare>
{
- typedef LoserTreePointerUnguardedBase<T, Comparator> Base;
- using Base::k;
- using Base::losers;
+ typedef LoserTreePointerUnguardedBase<_Tp, _Compare> Base;
+ using Base::__k;
+ using Base::__losers;
public:
- LoserTreePointerUnguarded(unsigned int _k, const T& _sentinel,
- Comparator _comp = std::less<T>())
+ LoserTreePointerUnguarded(unsigned int _k, const _Tp& _sentinel,
+ _Compare _comp = std::less<_Tp>())
: Base::LoserTreePointerUnguardedBase(_k, _sentinel, _comp)
{}
unsigned int
- init_winner(unsigned int root)
+ __init_winner(unsigned int __root)
{
- if (root >= k)
+ if (__root >= __k)
{
- return root;
+ return __root;
}
else
{
- unsigned int left = init_winner (2 * root);
- unsigned int right = init_winner (2 * root + 1);
+ unsigned int __left = __init_winner (2 * __root);
+ unsigned int __right = __init_winner (2 * __root + 1);
#if _GLIBCXX_ASSERTIONS
- // If left one is sentinel then right one must be, too.
- if (losers[left].source == -1)
- _GLIBCXX_PARALLEL_ASSERT(losers[right].source == -1);
+ // If __left one is sentinel then __right one must be, too.
+ if (__losers[__left]._M_source == -1)
+ _GLIBCXX_PARALLEL_ASSERT(__losers[__right]._M_source == -1);
#endif
- if (!comp(*losers[right].keyp, *losers[left].keyp))
+ if (!__comp(*__losers[__right]._M_keyp, *__losers[__left]._M_keyp))
{
// Left one is less or equal.
- losers[root] = losers[right];
- return left;
+ __losers[__root] = __losers[__right];
+ return __left;
}
else
{
// Right one is less.
- losers[root] = losers[left];
- return right;
+ __losers[__root] = __losers[__left];
+ return __right;
}
}
}
inline void
- init()
+ __init()
{
- losers[0] = losers[init_winner(1)];
+ __losers[0] = __losers[__init_winner(1)];
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top at the beginning (0 sequences!)
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
}
inline void
- delete_min_insert(const T& key, bool sup)
+ __delete_min_insert(const _Tp& _M_key, bool _M_sup)
{
#if _GLIBCXX_ASSERTIONS
// no dummy sequence can ever be at the top!
- _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+ _GLIBCXX_PARALLEL_ASSERT(__losers[0]._M_source != -1);
#endif
- const T* keyp = &key;
- int source = losers[0].source;
- for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ const _Tp* _M_keyp = &_M_key;
+ int _M_source = __losers[0]._M_source;
+ for (unsigned int __pos = (__k + _M_source) / 2; __pos > 0; __pos /= 2)
{
// The smaller one gets promoted.
- if (comp(*(losers[pos].keyp), *keyp))
+ if (__comp(*(__losers[__pos]._M_keyp), *_M_keyp))
{
// The other one is smaller.
- std::swap(losers[pos].source, source);
- std::swap(losers[pos].keyp, keyp);
+ std::swap(__losers[__pos]._M_source, _M_source);
+ std::swap(__losers[__pos]._M_keyp, _M_keyp);
}
}
- losers[0].source = source;
- losers[0].keyp = keyp;
+ __losers[0]._M_source = _M_source;
+ __losers[0]._M_keyp = _M_keyp;
}
};
projects / thirdparty / gcc.git / blobdiff