通用的 LoserTree
– 共有 n 个内部结点，n 个外部结点
– winner 只用于初始化时计算败者树，算完后即丢弃
– winner/loser 的第 0 个单元都不是内部结点，不属于树中的一员
– winner 的第 0 个单元未用
– m_tree 的第 0 个单元用于保存最终的赢者, 其它单元保存败者
– 该初始化需要的 n-1 次比较，总的时间复杂度是 O(n)
– 严蔚敏&吴伟民 的 LoserTree 初始化复杂度是 O(n*log(n))，并且还需要一个 min_key,
但是他们的初始化不需要额外的 winner 数组
– 并且，这个实现比 严蔚敏&吴伟民 的 LoserTree 初始化更强壮
其中引用的一些代码比较长，故未贴出
#define LT_iiter_traits typename std::iterator_traits<typename std::iterator_traits<RandIterOfInput>::value_type>template< class RandIterOfInput , class KeyType = LT_iiter_traits::value_type , bool StableSort = false //!< same Key in various way will output by way order , class Compare = std::less<KeyType> , class KeyExtractor = typename boost::mpl::if_c< boost::is_same<KeyType, LT_iiter_traits::value_type >::value, boost::multi_index::identity<KeyType>, MustProvideKeyExtractor >::type , CacheLevel HowCache = cache_default >class LoserTree : public CacheStrategy< typename std::iterator_traits<RandIterOfInput>::value_type , KeyType , KeyExtractor , HowCache >, public MultiWay_SetOP< LT_iiter_traits::value_type , KeyType , LoserTree<RandIterOfInput, KeyType, StableSort, Compare, KeyExtractor, HowCache> >
…{
DECLARE_NONE_COPYABLE_CLASS(LoserTree) typedef CacheStrategy< typename std::iterator_traits<RandIterOfInput>::value_type , KeyType , KeyExtractor , HowCache > super; friend class MultiWay_SetOP< LT_iiter_traits::value_type , KeyType , LoserTree<RandIterOfInput, KeyType, StableSort, Compare, KeyExtractor, HowCache> >;public: typedef typename std::iterator_traits<RandIterOfInput>::value_type way_iter_t; typedef typename std::iterator_traits<way_iter_t >::value_type value_type; typedef KeyType key_type; typedef KeyExtractor key_extractor; typedef boost::integral_constant<bool, StableSort> is_stable_sort; typedef typename super::cache_category cache_category; typedef typename super::cache_item_type cache_item_type;public:
/**//** @brief construct @par 图示如下： @codeRandIterOfInput this is guard value || || || || / / first–> 0 way_iter_t [min_value…………………….max_value] / 1 way_iter_t [min_value…………………….max_value] <— 每个序列均已 | 2 way_iter_t [min_value…………………….max_value] 按 comp 排序 | 3 way_iter_t [min_value…………………….max_value] < 4 way_iter_t [min_value…………………….max_value] | 5 way_iter_t [min_value…………………….max_value] | 7 way_iter_t [min_value…………………….max_value] 8 way_iter_t [min_value…………………….max_value] last—> end @endcode @param comp value 的比较器 @note 每个序列最后必须要有一个 max_value 作为序列结束标志，否则会导致未定义行为
*/ LoserTree(RandIterOfInput first, RandIterOfInput last, const KeyType& max_key, const Compare& comp = Compare(), const KeyExtractor& keyExtractor = KeyExtractor()) …{ init(first, last, max_key, comp, keyExtractor); } LoserTree(RandIterOfInput first, int length, const KeyType& max_key, const Compare& comp = Compare(), const KeyExtractor& keyExtractor = KeyExtractor()) …{ init(first, first + length, max_key, comp, keyExtractor); }// LoserTree(RandIterOfInput first, RandIterOfInput last,// const cache_item_type& min_item,// const cache_item_type& max_item,// const KeyType& max_key,// const Compare& comp = Compare(),// const KeyExtractor& keyExtractor = KeyExtractor())// {// init_yan_wu(first, last, min_item, max_item, comp, keyExtractor);// }// LoserTree(RandIterOfInput first, int length,// const cache_item_type& min_item, // yan_wu init need// const cache_item_type& max_item,// const KeyType& max_key,// const Compare& comp = Compare(),// const KeyExtractor& keyExtractor = KeyExtractor())// {// init_yan_wu(first, first + length, min_item, max_item, comp, keyExtractor);// } LoserTree() …{ } /**//** @brief 初始化 – 共有 n 个内部结点，n 个外部结点 – winner 只用于初始化时计算败者树，算完后即丢弃 – winner/loser 的第 0 个单元都不是内部结点，不属于树中的一员 – winner 的第 0 个单元未用 – m_tree 的第 0 个单元用于保存最终的赢者, 其它单元保存败者 – 该初始化需要的 n-1 次比较，总的时间复杂度是 O(n) – 严蔚敏&吴伟民 的 LoserTree 初始化复杂度是 O(n*log(n))，并且还需要一个 min_key, 但是他们的初始化不需要额外的 winner 数组 – 并且，这个实现比 严蔚敏&吴伟民 的 LoserTree 初始化更强壮 */ void init(RandIterOfInput first, RandIterOfInput last, const KeyType& max_key, const Compare& comp = Compare(), const KeyExtractor& keyExtractor = KeyExtractor()) …{ m_comp = comp; m_key_extractor = keyExtractor; m_beg = first; m_end = last; m_max_key = max_key; int len = int(last – first); if (0 == len) …{ throw std::logic_error("LoserTree: way sequence must not be empty"); } m_tree.resize(len); this->resize_cache(len); int i; for (i = 0; i != len; ++i) …{ // read first value from every sequence this->input_cache_item(i, *(first+i)); } if (1 == len) …{ m_tree[0] = 0; return; } int minInnerToEx = len / 2; std::vector<int> winner(len); for (i = len – 1; i > minInnerToEx; —i) …{ exter_loser_winner(m_tree[i], winner[i], i, len); } int left, right; if (len & 1) // odd …{ // left child is last inner node, right child is first external node left = winner[len–1]; right = 0; } else …{ left = 0; right = 1; } get_loser_winner(m_tree[minInnerToEx], winner[minInnerToEx], left, right); for (i = minInnerToEx; i > 0; i /= 2) …{ for (int j = i–1; j >= i/2; —j) …{ inner_loser_winner(m_tree[j], winner[j], j, winner); } } m_tree[0] = winner[1]; } //! 严蔚敏&吴伟民 的 LoserTree 初始化 //! 复杂度是 O(n*log(n))，并且还需要一个 min_key void init_yan_wu(RandIterOfInput first, RandIterOfInput last, const cache_item_type& min_item, const cache_item_type& max_item, const Compare& comp = Compare(), const KeyExtractor& keyExtractor = KeyExtractor()) …{ //! this function do not support cache_none BOOST_STATIC_ASSERT(HowCache != cache_none); assert(first < last); // ensure that will not construct empty loser tree m_comp = comp; m_key_extractor = keyExtractor; m_beg = first; m_end = last; m_max_key = this->key_from_cache_item(max_item); int len = int(last – first); m_tree.resize(len); this->resize_cache(len+1); this->set_cache_item(len, min_item); int i; for (i = 0; i != len; ++i) …{ m_tree[i] = len; // read first value from every sequence this->input_cache_item(i, *(first+i)); } for (i = len–1; i >= 0; —i) ajust(i); // 防止 cache 的最后一个成员上升到 top ??….. // this->set_cache_item(len, max_item); // assert(!m_tree.empty()); // if (m_tree[0] == len) // ajust(len); // 会导致在 ajust 中 m_tree[parent] 越界 } const value_type& current_value() const …{ assert(!m_tree.empty()); // assert(!is_end()); // 允许访问末尾的 guardValue, 便于简化 app return current_value_aux(cache_category()); } /**//** @brief return current way NO. */ int current_way() const …{ assert(!m_tree.empty()); assert(!is_end()); return m_tree[0]; } size_t total_ways() const …{ return m_tree.size(); } bool is_any_way_end() const …{ return is_end(); } bool is_end() const …{ assert(!m_tree.empty()); const KeyType& cur_key = get_cache_key(m_tree[0], cache_category()); return !m_comp(cur_key, m_max_key); // cur_key >= max_value } void increment() …{ assert(!m_tree.empty()); assert(!is_end()); int top = m_tree[0]; input_cache_item(top, ++*(m_beg + top)); ajust(top); } void ajust_for_update_top() …{ assert(!m_tree.empty()); int top = m_tree[0]; input_cache_item(top, *(m_beg + top)); ajust(top); } way_iter_t& top() …{ assert(!m_tree.empty()); return *(m_beg + m_tree[0]); } void reserve(int maxTreeSize) …{ m_tree.reserve(maxTreeSize); resize_cache(maxTreeSize); }protected: void ajust(int s) …{ int parent = int(s + m_tree.size()) >> 1; while (parent > 0) …{ if (comp_cache_item(m_tree[parent], s, cache_category(), is_stable_sort())) …{ std::swap(s, m_tree[parent]); } parent >>= 1; } m_tree[0] = s; } void exter_loser_winner(int& loser, int& winner, int parent, int len) const …{ int left = 2 * parent – len; int right = left + 1; get_loser_winner(loser, winner, left, right); } void inner_loser_winner(int& loser, int& winner, int parent, const std::vector<int>& winner_vec) const …{ int left = 2 * parent; int right = 2 * parent + 1; left = winner_vec[left]; right = winner_vec[right]; get_loser_winner(loser, winner, left, right); } void get_loser_winner(int& loser, int& winner, int left, int right) const …{ if (comp_cache_item(left, right, cache_category(), is_stable_sort())) …{ loser = right; winner = left; } else …{ loser = left; winner = right; } } const value_type& current_value_aux(tag_cache_none) const …{ assert(m_tree[0] < int(m_tree.size())); return **(m_beg + m_tree[0]); } const value_type& current_value_aux(tag_cache_key) const …{ assert(m_tree[0] < int(m_tree.size())); return **(m_beg + m_tree[0]); } const value_type& current_value_aux(tag_cache_value) const …{ assert(m_tree[0] < int(m_tree.size())); return this->m_cache[m_tree[0]]; } using super::get_cache_key; inline const KeyType get_cache_key(int nth, tag_cache_none) const …{ return this->m_key_extractor(**(m_beg + nth)); } template<class CacheCategory> inline bool comp_cache_item(int x, int y, CacheCategory cache_tag, boost::true_type isStableSort) const …{ return comp_key_stable(x, y, get_cache_key(x, cache_tag), get_cache_key(y, cache_tag), typename HasTriCompare<Compare>::type()); } bool comp_key_stable(int x, int y, const KeyType& kx, const KeyType& ky, boost::true_type hasTriCompare) const …{ int ret = m_comp.compare(kx, ky); if (ret < 0) return true; if (ret > 0) return false; ret = m_comp.compare(kx, m_max_key); assert(ret <= 0); if (0 == ret) return false; else return x < y; } bool comp_key_stable(int x, int y, const KeyType& kx, const KeyType& ky, boost::false_type hasTriCompare) const …{ if (m_comp(kx, ky)) return true; if (m_comp(ky, kx)) return false; if (!m_comp(kx, m_max_key)) // kx >= max_key –> kx == max_key …{ // max_key is the max, so must assert this: assert(!m_comp(m_max_key, kx)); return false; } else return x < y; } template<class CacheCategory> inline bool comp_cache_item(int x, int y, CacheCategory cache_tag, boost::false_type isStableSort) const …{ return m_comp(get_cache_key(x, cache_tag), get_cache_key(y, cache_tag)); }protected: KeyType m_max_key; std::vector<int> m_tree; RandIterOfInput m_beg; RandIterOfInput m_end; Compare m_comp;
};使用示例：
// test_multi_way.cpp : Defines the entry point for the console application.//#include "stdafx.h"using namespace std;using namespace febird;//using namespace febird::prefix_zip;using namespace febird::multi_way;template<class _Cont>void printResult(const char* title, const _Cont& result)…{ cout << title << ": "; for (typename _Cont::const_iterator i = result.begin(); i != result.end(); ++i) cout << *i << ","; cout << endl;}template<class _Cont>void printKeyValue(const char* title, const _Cont& result)…{ cout << title << ": "; for (typename _Cont::const_iterator i = result.begin(); i != result.end(); ++i) cout << "(" << result.key(i) << "," << *i << "),"; cout << endl;}template<class _Cont>void printPairCont(const char* title, const _Cont& result)…{ cout << title << ": "; for (typename _Cont::const_iterator i = result.begin(); i != result.end(); ++i) cout << "(" << i->first << "," << i->second << "),"; cout << endl;}int main(int argc, char* argv[])…{// cout << setw(5) << setiosflags(ios::right) << 100 << setw(20) << setiosflags(ios::left) << "abcd" << endl;// cout << setw(5) << setiosflags(ios::right) << 100 << setw(20) << left << "abcd" << endl; int ivals[][11] = …{ …{1, 8, 20, 31, 47, 54, 75, 82, 93, 99, INT_MAX}, …{1, 7, 20, 30, 48, 53, 76, 81, 95, 98, INT_MAX}, …{3, 6, 17, 20, 35, 42, 49, 73, 90, 91, INT_MAX}, …{2, 4, 19, 20, 46, 51, 73, 88, 96, 97, INT_MAX}, …{2, 4, 15, 20, 46, 51, 73, 88, 96, 97, INT_MAX}, }; vector<int> intersect; vector<int> unionvec; vector<int*> ilower, iupper; for (int i = 0; i < 5; ++i) ilower.push_back(ivals[i]); for (int i = 0; i < 5; ++i) iupper.push_back(ivals[i] + 10); LoserTree<vector<int*>::iterator> loserTree(ilower.begin(), ilower.end(), INT_MAX); loserTree.intersection(back_inserter(intersect)); for (int i = 0; i < 5; ++i) ilower.push_back(ivals[i]); loserTree.init(ilower.begin(), ilower.end(), INT_MAX); loserTree.union_set(back_inserter(unionvec)); vector<int> v1; copy(&ivals[0][0], &ivals[5][0], back_inserter(v1)); printResult("all_values", v1); printResult("intersection_result", intersect); printResult("union_result", unionvec); vector<pair<int*, int*> > range, range2; for (int i = 0; i < 5; ++i) …{ range.push_back(make_pair(ivals[i], ivals[i] + 10)); } intersect.clear(); range2 = range; HeapMultiWay<vector<pair<int*, int*> >::iterator> heap(range.begin(), range.end()); heap.intersection(back_inserter(intersect)); printResult("intersection_result2", intersect); range = range2; …{ vector<int> copyset; heap.init(range.begin(), range.end()); heap.copy_if2(back_inserter(copyset), MultiWay_CopyAtLeastDup(3)); printResult("MultiWay_CopyAtLeastDup(3)", copyset); } range = range2; …{ map<int, int> counting; heap.init(range.begin(), range.end()); heap.copy_if2((int*)(0), MultiWay_GetCountTable(counting, 2)); printPairCont("MultiWay_GetCountMap", counting); } range = range2; …{ vector<pair<int, int> > counting; heap.init(range.begin(), range.end()); heap.copy_if2((int*)(0), MultiWay_GetCountSequence(counting, 2)); printPairCont("MultiWay_GetCountSequence", counting); } range = range2; …{ // MultiWayTable<int, int> counting(16); map<int, int> counting; heap.init(range.begin(), range.end()); heap.copy_if2((int*)(0), MultiWay_GetCountTable(counting, 2)); // printKeyValue("MultiWay_GetCountTable", counting); printPairCont("MultiWay_GetCountTable", counting); } range = range2; …{ // PackedTable<int, int> counting; map<int, int> counting; heap.init(range.begin(), range.end()); heap.copy_if2((int*)(0), MultiWay_GetCountTable(counting, 2)); // printKeyValue("MultiWay_GetCountTable", counting); printPairCont("MultiWay_GetCountTable", counting); } return 0;}
