mstl_algorithm_compare.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_COMPARE_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_ALGORITHM_COMPARE_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "../mstl_iterator.hpp"
#include "../mstl_pair.hpp"
#include "../string/mstl_char_function.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

//*****************************************************************************
//*****************************************************************************
//                               比较算法
//
//             equal  lexicographical_compare  mismatch  matching
//*****************************************************************************
//*****************************************************************************

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename InputIterator1, typename InputIterator2 >
inline bool equal( InputIterator1 first1, InputIterator1 last1,
                   InputIterator2 first2 )
{
    typedef  typename iterator_traits<InputIterator1>::iterator_category  cate;
    return equal_aux( first1, last1, first2, cate() );
}

template< typename InputIterator1, typename InputIterator2 >
bool equal_aux( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, input_iterator_tag )
{
    for( ; first1 != last1; ++first1,++first2 )
    {
        if( !(*first1 == *first2) )
            return false;
    }
    return true;
}

template< typename InputIterator1, typename InputIterator2 >
bool equal_aux( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, random_access_iterator_tag )
{
    typedef  typename iterator_traits<InputIterator1>::difference_type  diff_t1;

    for( diff_t1 n = last1 - first1; n > 0; --n,++first1,++first2 )
    {
        if( !(*first1 == *first2) )
            return false;
    }
    return true;
}



template< typename InputIterator1, typename InputIterator2,
          typename BinaryPredicate >
inline bool equal( InputIterator1 first1, InputIterator1 last1,
                   InputIterator2 first2, BinaryPredicate bin_pred )
{
    typedef  typename iterator_traits<InputIterator1>::iterator_category  cate;
    return equal_aux( first1, last1, first2, bin_pred, cate() );
}

template< typename InputIterator1, typename InputIterator2,
          typename BinaryPredicate >
bool equal_aux( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, BinaryPredicate bin_pred,
                input_iterator_tag )
{
    for( ; first1 != last1; ++first1,++first2 )
    {
        if( !bin_pred(*first1, *first2) )
            return false;
    }
    return true;
}

template< typename InputIterator1, typename InputIterator2,
          typename BinaryPredicate >
bool equal_aux( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, BinaryPredicate bin_pred,
                random_access_iterator_tag )
{
    typedef  typename iterator_traits<InputIterator1>::difference_type  diff_t1;

    for( diff_t1 n = last1 - first1; n > 0; --n,++first1,++first2 )
    {
        if( !bin_pred(*first1, *first2) )
            return false;
    }
    return true;
}



inline bool equal( const char* first1, const char* last1, const char* first2 )
{
    return ( memcmp( first1, first2, last1 - first1 ) == 0 );
}

inline bool equal( const unsigned char* first1, const unsigned char* last1,
                   const unsigned char* first2 )
{
    return ( memcmp( first1, first2, last1 - first1 ) == 0 );
}

inline bool equal( const wchar_t* first1, const wchar_t* last1,
                   const wchar_t* first2 )
{
    return ( wmemcmp( first1, first2, last1 - first1 ) == 0 );
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename InputIterator1, typename InputIterator2 >
inline
bool lexicographical_compare( InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2 )
{
    typedef  typename iterator_traits<InputIterator1>::iterator_category  cate1;
    typedef  typename iterator_traits<InputIterator2>::iterator_category  cate2;
    return lexic_cmp( first1, last1, first2, last2, cate1(), cate2() );
}

template< typename InputIterator1, typename InputIterator2 >
bool lexic_cmp( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, InputIterator2 last2,
                input_iterator_tag, input_iterator_tag )
{
    for( ; (first1 != last1) && (first2 != last2); ++first1,++first2 )
    {
    	if( *first1 < *first2 )
    	    return true;
    	if( *first2 < *first1 )
    	    return false;
    }
    return ( first1 == last1 && first2 != last2 );
}

template< typename InputIterator1, typename InputIterator2 >
bool lexic_cmp( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, InputIterator2 last2,
                random_access_iterator_tag, random_access_iterator_tag )
{
    typedef  typename iterator_traits<InputIterator1>::difference_type  diff_t1;
    typedef  typename iterator_traits<InputIterator2>::difference_type  diff_t2;

    diff_t1 len1 = last1 - first1;
    diff_t2 len2 = last2 - first2;
    def_ptrdiff_t len = len1 < len2 ? len1 : len2;

    for( ; len > 0; --len,++first1,++first2 )
    {
    	if( *first1 < *first2 )
    	    return true;
    	if( *first2 < *first1 )
    	    return false;
    }
    return ( len1 < len2 );
}



template< typename InputIterator1, typename InputIterator2,
          typename StrictWeakOrdering >
inline
bool lexicographical_compare( InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              StrictWeakOrdering comp )
{
    typedef  typename iterator_traits<InputIterator1>::iterator_category  cate1;
    typedef  typename iterator_traits<InputIterator2>::iterator_category  cate2;
    return lexic_cmp( first1, last1, first2, last2, comp, cate1(), cate2() );
}

template< typename InputIterator1, typename InputIterator2,
          typename StrictWeakOrdering >
bool lexic_cmp( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, InputIterator2 last2,
                StrictWeakOrdering comp,
                input_iterator_tag, input_iterator_tag )
{
    for( ; (first1 != last1) && (first2 != last2); ++first1,++first2 )
    {
    	if( comp(*first1, *first2) )
    	    return true;
    	if( comp(*first2, *first1) )
    	    return false;
    }
    return ( first1 == last1 && first2 != last2 );
}

template< typename InputIterator1, typename InputIterator2,
          typename StrictWeakOrdering >
bool lexic_cmp( InputIterator1 first1, InputIterator1 last1,