mstl_algorithm_lower_bound.hpp

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

/*
The young Library
Copyright (c) 2005 by 杨桓

Permission to use, copy, modify, distribute and sell this software for any
purpose is hereby granted without fee, provided that the above copyright
notice appear in all copies and that both that copyright notice and this
permission notice appear in supporting documentation.
The author make no representations about the suitability of this software
for any purpose. It is provided "as is" without express or implied warranty.
*/

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_MINI_STL_ALGORITHM_LOWER_BOUND_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_ALGORITHM_LOWER_BOUND_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "../mstl_iterator.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename ForwardIterator, typename T >
inline
ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last,
                             const T& value )
{
    typedef  typename iterator_traits<ForwardIterator>::iterator_category  cate;

    if( first == last )
        return first;
    else
        return lower_b_aux( first, last, value, cate() );
}

template< typename ForwardIterator, typename T >
ForwardIterator lower_b_aux( ForwardIterator first, ForwardIterator last,
                             const T& value, forward_iterator_tag )
{
    typedef  typename iterator_traits<ForwardIterator>::difference_type  diff_t;
    diff_t len = distance( first, last );
    diff_t half;
    ForwardIterator middle;

    while( len > 0 )
    {
        half = len / 2;
        middle = first;
        advance( middle, half );
        if( *middle < value )  //要查找的值在后半部分
        {
            first = middle;
            ++first;
            len = len - half - 1;
        }
        else  //要查找的值在前半部分
            len = half;
    }

    return first;
}

template< typename ForwardIterator, typename T >
ForwardIterator lower_b_aux( ForwardIterator first, ForwardIterator last,
                             const T& value, random_access_iterator_tag )
{
    typedef  typename iterator_traits<ForwardIterator>::difference_type  diff_t;
    diff_t len = last - first;
    diff_t half;
    ForwardIterator middle;

    while( len > 0 )
    {
        half = len / 2;
        middle = first + half;
        if( *middle < value )  //要查找的值在后半部分
        {
            first = middle + 1;
            len = len - half - 1;
        }
        else  //要查找的值在前半部分
            len = half;
    }

    return first;
}



template< typename ForwardIterator, typename T, typename StrictWeakOrdering >
inline
ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last,
                             const T& value, StrictWeakOrdering comp )
{
    typedef  typename iterator_traits<ForwardIterator>::iterator_category  cate;

    if( first == last )
        return first;
    else
        return lower_b_aux( first, last, value, comp, cate() );
}

template< typename ForwardIterator, typename T, typename StrictWeakOrdering >
ForwardIterator lower_b_aux( ForwardIterator first, ForwardIterator last,
                             const T& value, StrictWeakOrdering comp,
                             forward_iterator_tag )
{
    typedef  typename iterator_traits<ForwardIterator>::difference_type  diff_t;
    diff_t len = distance( first, last );
    diff_t half;
    ForwardIterator middle;

    while( len > 0 )
    {
        half = len / 2;
        middle = first;
        advance( middle, half );
        if( comp(*middle, value) )  //要查找的值在后半部分
        {
            first = middle;
            ++first;
            len = len - half - 1;
        }
        else  //要查找的值在前半部分
            len = half;
    }

    return first;
}

template< typename ForwardIterator, typename T, typename StrictWeakOrdering >
ForwardIterator lower_b_aux( ForwardIterator first, ForwardIterator last,
                             const T& value, StrictWeakOrdering comp,
                             random_access_iterator_tag )
{
    typedef  typename iterator_traits<ForwardIterator>::difference_type  diff_t;
    diff_t len = last - first;
    diff_t half;
    ForwardIterator middle;

    while( len > 0 )
    {
        half = len / 2;
        middle = first + half;
        if( comp(*middle, value) )  //要查找的值在后半部分
        {
            first = middle + 1;
            len = len - half - 1;
        }
        else  //要查找的值在前半部分
            len = half;
    }

    return first;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_END_NAMESPACE__
#endif
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------