通用的 LoserTree

项目地址：http://code.google.com/p/febird

 

 - 共有 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 图示如下：
     @code

RandIterOfInput                                          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

 

项目地址：http://code.google.com/p/febird