test_insert.h

来自「stl的源码」· C头文件 代码 · 共 553 行 · 第 1/2 页

/***********************************************************************************
  test_insert.h

 * Copyright (c) 1997
 * Mark of the Unicorn, Inc.
 *
 * 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.  Mark of the Unicorn makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.

***********************************************************************************/
#ifndef test_insert_H_
#define test_insert_H_

# include "Prefix.h"
# if defined (EH_NEW_HEADERS)
#  include <utility>
#  include <vector>
#  include <cassert>
#  include <climits>
# else
#  include <vector.h>
#  include <assert.h>
#  include <limits.h>
# endif
#include "random_number.h"
#include "nc_alloc.h"
#include "ThrowCompare.h"

// A classification system for containers, for verification
struct container_tag {};
struct sequence_container_tag  {};
struct associative_container_tag  {};

struct set_tag  {};
struct multiset_tag  {};
struct map_tag {};
struct multimap_tag {};

template <class C, class Iter>
size_t CountNewItems( const C&, const Iter& firstNew,
                      const Iter& lastNew, sequence_container_tag )
{
    size_t dist = 0;
#if 0 //def __SUNPRO_CC
    EH_DISTANCE( firstNew, lastNew, dist );
#else
    EH_DISTANCE( Iter(firstNew), Iter(lastNew), dist );
#endif
    return dist;
}

template <class C, class Iter>
size_t CountNewItems( const C& c, const Iter& firstNew,
                      const Iter& lastNew, multimap_tag )
{
    return CountNewItems( c, firstNew, lastNew, sequence_container_tag() );
}

template <class C, class Iter>
size_t CountNewItems( const C& c, const Iter& firstNew,
                      const Iter& lastNew, multiset_tag )
{
    return CountNewItems( c, firstNew, lastNew, sequence_container_tag() );
}


template <class C, class Iter, class KeyOfValue>
#ifdef __BORLANDC__
size_t CountUniqueItems_Aux( const C& original, const Iter& firstNew,
#else
size_t CountUniqueItems_Aux( const C& original, Iter firstNew,
#endif
                             Iter lastNew, const KeyOfValue& keyOfValue )
{
  typedef typename C::key_type key;
  typedef typename C::const_iterator const_iter;
  typedef EH_STD::vector<key> key_list;
  typedef typename key_list::iterator key_iterator;
  key_list keys;
  size_t dist = 0;
#ifdef __SUNPRO_CC
  EH_DISTANCE( firstNew, lastNew, dist );
#else
  EH_DISTANCE( Iter(firstNew), Iter(lastNew), dist );
#endif
  keys.reserve( dist );
  for ( Iter x = firstNew; x != lastNew; ++x )
    keys.push_back( keyOfValue(*x) );

  EH_STD::sort( keys.begin(), keys.end() );
  key_iterator last = EH_STD::unique( keys.begin(), keys.end() );

    size_t cnt = 0;
    for ( key_iterator tmp = keys.begin(); tmp != last; ++tmp )
    {
        if ( const_iter(original.find( *tmp )) == const_iter(original.end()) )
            ++cnt;
    }
    return cnt;
}

#if ! defined (__SGI_STL)
EH_BEGIN_NAMESPACE
template <class T>
struct identity
{
  const T& operator()( const T& x ) const { return x; }
};
# if ! defined (__KCC)
template <class _Pair>
struct select1st : public unary_function<_Pair, typename _Pair::first_type> {
  const typename _Pair::first_type& operator()(const _Pair& __x) const {
    return __x.first;
  }
};
# endif
EH_END_NAMESPACE
#endif

template <class C, class Iter>
size_t CountUniqueItems( const C& original, const Iter& firstNew,
                         const Iter& lastNew, set_tag )
{
    typedef typename C::value_type value_type;
    return CountUniqueItems_Aux( original, firstNew, lastNew,
                                 EH_STD::identity<value_type>() );
}

template <class C, class Iter>
size_t CountUniqueItems( const C& original, const Iter& firstNew,
                         const Iter& lastNew, map_tag )
{
#ifdef EH_MULTI_CONST_TEMPLATE_ARG_BUG
    return CountUniqueItems_Aux( original, firstNew, lastNew,
                                 EH_SELECT1ST_HINT<C::value_type, C::key_type>() );
#else
    typedef typename C::value_type value_type;
    return CountUniqueItems_Aux( original, firstNew, lastNew,
                                 EH_STD::select1st<value_type>() );
#endif
}

template <class C, class Iter>
size_t CountNewItems( const C& original, const Iter& firstNew,
                      const Iter& lastNew, map_tag )
{
    return CountUniqueItems( original, firstNew, lastNew,
                             container_category( original ) );
}

template <class C, class Iter>
size_t CountNewItems( const C& original, const Iter& firstNew,
                      const Iter& lastNew, set_tag )
{
    return CountUniqueItems( original, firstNew, lastNew,
                             container_category( original ) );
}

template <class C, class SrcIter>
inline void VerifyInsertion( const C& original, const C& result,
                             const SrcIter& firstNew, const SrcIter& lastNew,
                             size_t, associative_container_tag )
{
    typedef typename C::const_iterator DstIter;
    DstIter first1 = original.begin();
    DstIter first2 = result.begin();

    DstIter* from_orig = new DstIter[original.size()];
    DstIter* last_from_orig = from_orig;

    // fbp : for hashed containers, the following is needed :
    while ( first2 != result.end() )
    {
        EH_STD::pair<DstIter, DstIter> p = EH_STD::mismatch( first1, original.end(), first2 );
        if ( p.second != result.end() )
        {
            SrcIter srcItem = EH_STD::find( SrcIter(firstNew), SrcIter(lastNew), *p.second );

            if (srcItem == lastNew)
            {
                // not found in input range, probably re-ordered from the orig
                DstIter* tmp;
                tmp = EH_STD::find( from_orig, last_from_orig, p.first );

                // if already here, exclude
                if (tmp != last_from_orig)
                {
                    EH_STD::copy(tmp+1, last_from_orig, tmp);
                    last_from_orig--;
                }
                else
                {
                    // register re-ordered element
                    DstIter dstItem;
                    dstItem = EH_STD::find( first1, original.end(), *p.first );
                    EH_ASSERT( dstItem != original.end() );
                    *last_from_orig = dstItem;
                    last_from_orig++;
                    ++p.first;
                }
            }
            ++p.second;
        }
        first1 = p.first;
        first2 = p.second;
    }

    delete [] from_orig;
}

// VC++
template <class C, class SrcIter>
inline void VerifyInsertion(
    const C& original, const C& result, const SrcIter& firstNew,
    const SrcIter& lastNew, size_t, set_tag )
{
    VerifyInsertion( original, result, firstNew, lastNew,
                     size_t(0), associative_container_tag() );
}

template <class C, class SrcIter>
inline void VerifyInsertion(const C& original, const C& result,
                            const SrcIter& firstNew, const SrcIter& lastNew,
                            size_t, multiset_tag )
{
    VerifyInsertion( original, result, firstNew, lastNew,
                     size_t(0), associative_container_tag() );
}

template <class C, class SrcIter>
inline void VerifyInsertion(
    const C& original, const C& result, const SrcIter& firstNew,
    const SrcIter& lastNew, size_t, map_tag )
{
    VerifyInsertion( original, result, firstNew, lastNew,
                     size_t(0), associative_container_tag() );
}

template <class C, class SrcIter>
inline void VerifyInsertion(
    const C& original, const C& result, const SrcIter& firstNew,
    const SrcIter& lastNew, size_t, multimap_tag )
{
    VerifyInsertion( original, result, firstNew, lastNew,
                     size_t(0), associative_container_tag() );
}

template <class C, class SrcIter>
void VerifyInsertion(
# ifdef _MSC_VER
    const C& original, const C& result, SrcIter firstNew,
    SrcIter lastNew, size_t insPos, sequence_container_tag )
# else
    const C& original, const C& result, const SrcIter& firstNew,
    const SrcIter& lastNew, size_t insPos, sequence_container_tag )
# endif
{
    typename C::const_iterator p1 = original.begin();
    typename C::const_iterator p2 = result.begin();
    SrcIter tmp(firstNew);

    for ( size_t n = 0; n < insPos; n++, ++p1, ++p2)
        EH_ASSERT( *p1 == *p2 );

    for (; tmp != lastNew; ++p2, ++tmp ) {
        EH_ASSERT(p2 != result.end());
        EH_ASSERT(*p2 == *tmp);
    }

    for (;  p2 != result.end(); ++p1, ++p2 )
        EH_ASSERT( *p1 == *p2 );
    EH_ASSERT( p1 == original.end() );