/***********************************************************************************

  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() );

}

template <class C, class SrcIter>

inline void VerifyInsertion( const C& original, const C& result,

                             const SrcIter& firstNew,

                             const SrcIter& lastNew, size_t insPos )

{

    EH_ASSERT( result.size() == original.size() +

            CountNewItems( original, firstNew, lastNew,

                           container_category(original) ) );

    VerifyInsertion( original, result, firstNew, lastNew, insPos,

                     container_category(original) );

}

template <class C, class Value>

void VerifyInsertN( const C& original, const C& result, size_t insCnt,

                    const Value& val, size_t insPos )

{

    typename C::const_iterator p1 = original.begin();

    typename C::const_iterator p2 = result.begin();

  (void)val;    //*TY 02/06/2000 - to suppress unused variable warning under nondebug build

    for ( size_t n = 0; n < insPos; n++ )

        EH_ASSERT( *p1++ == *p2++ );

    while ( insCnt-- > 0 )

    {

        EH_ASSERT(p2 != result.end());

        EH_ASSERT(*p2 == val );

        ++p2;

    }

    while ( p2 != result.end() ) {

        EH_ASSERT( *p1 == *p2 );

        ++p1; ++p2;

    }

    EH_ASSERT( p1 == original.end() );

}

template <class C>

void prepare_insert_n( C&, size_t ) {}

// Metrowerks 1.8 compiler requires that specializations appear first (!!)

// or it won't call them. Fixed in 1.9, though.

inline void MakeRandomValue(bool& b) { b = bool(random_number(2) != 0); }

template<class T>

inline void MakeRandomValue(T&) {}

template <class C>

struct test_insert_one

{

    test_insert_one( const C& orig, int pos =-1 )

        : original( orig ), fPos( random_number( orig.size() ))

    {

        MakeRandomValue( fInsVal );

        if ( pos != -1 )

        {

            fPos = size_t(pos);

            if ( pos == 0 )

                gTestController.SetCurrentTestName("single insertion at begin()");

            else

                gTestController.SetCurrentTestName("single insertion at end()");

        }

        else

            gTestController.SetCurrentTestName("single insertion at random position");

    }

    void operator()( C& c ) const

    {

        prepare_insert_n( c, (size_t)1 );

        typename C::iterator pos = c.begin();

        EH_STD::advance( pos, size_t(fPos) );

        c.insert( pos, fInsVal );

        // Prevent simulated failures during verification

        gTestController.CancelFailureCountdown();

        // Success. Check results.

        VerifyInsertion( original, c, &fInsVal, 1+&fInsVal, fPos );

    }

private:

    typename C::value_type fInsVal;

    const C& original;

    size_t fPos;

};

template <class C>

struct test_insert_n

{

    test_insert_n( const C& orig, size_t insCnt, int pos =-1 )

        : original( orig ), fPos( random_number( orig.size() )), fInsCnt(insCnt)

    {

        MakeRandomValue( fInsVal );

        if (pos!=-1)

        {

            fPos=size_t(pos);

            if (pos==0)

                gTestController.SetCurrentTestName("n-ary insertion at begin()");

            else

                gTestController.SetCurrentTestName("n-ary insertion at end()");

        }

        else

            gTestController.SetCurrentTestName("n-ary insertion at random position");

    }

    void operator()( C& c ) const

    {

        prepare_insert_n( c, fInsCnt );

        typename C::iterator pos = c.begin();

        EH_STD::advance( pos, fPos );

        c.insert( pos, fInsCnt, fInsVal );

        // Prevent simulated failures during verification

        gTestController.CancelFailureCountdown();

        // Success. Check results.

        VerifyInsertN( original, c, fInsCnt, fInsVal, fPos );

    }

private:

    typename C::value_type fInsVal;

    const C& original;

    size_t fPos;

    size_t fInsCnt;

};

template <class C>

struct test_insert_value

{

    test_insert_value( const C& orig )

        : original( orig )

    {

        MakeRandomValue( fInsVal );

        gTestController.SetCurrentTestName("insertion of random value");

    }

    void operator()( C& c ) const

    {

        c.insert( fInsVal );

        // Prevent simulated failures during verification

        gTestController.CancelFailureCountdown();

        // Success. Check results.

        VerifyInsertion( original, c, &fInsVal, 1+&fInsVal, size_t(0) );

    }

private:

    typename C::value_type fInsVal;

    const C& original;

};

template <class C>

struct test_insert_noresize

{

    test_insert_noresize( const C& orig )

        : original( orig )

    {

        MakeRandomValue( fInsVal );

        gTestController.SetCurrentTestName("insertion of random value without resize");

    }

    void operator()( C& c ) const

    {

        c.insert_noresize( fInsVal );

        // Prevent simulated failures during verification

        gTestController.CancelFailureCountdown();

        // Success. Check results.

        VerifyInsertion( original, c, &fInsVal, 1+&fInsVal, size_t(0) );

    }

private:

    typename C::value_type fInsVal;

    const C& original;

};

template <class C, class Position, class Iter>

void do_insert_range( C& c_inst, Position offset,

                      Iter first, Iter last, sequence_container_tag )

{

    typedef typename C::iterator CIter;

    CIter pos = c_inst.begin();

    EH_STD::advance( pos, offset );

    c_inst.insert( pos, first, last );

}

template <class C, class Position, class Iter>

void do_insert_range( C& c, Position,

                      Iter first, Iter last, associative_container_tag )

{

    c.insert( first, last );

}

template <class C, class Position, class Iter>

void do_insert_range( C& c, Position, Iter first, Iter last, multiset_tag )

{

    c.insert( first, last );

}

template <class C, class Position, class Iter>

void do_insert_range( C& c, Position, Iter first, Iter last, multimap_tag )

{

    c.insert( first, last );

}

template <class C, class Position, class Iter>

void do_insert_range( C& c, Position, Iter first, Iter last, set_tag )

{

    c.insert( first, last );

}

template <class C, class Position, class Iter>

void do_insert_range( C& c, Position, Iter first, Iter last, map_tag )

{

    c.insert( first, last );

}

/*

template <class C, class Iter>

void prepare_insert_range( C&, size_t, Iter, Iter) {}

*/

template <class C, class Iter>

struct test_insert_range

{

    test_insert_range( const C& orig, Iter first, Iter last, int pos=-1 )

        : fFirst( first ),

          fLast( last ),

          original( orig ),

          fPos( random_number( orig.size() ))

    {

        gTestController.SetCurrentTestName("range insertion");

        if ( pos != -1 )

        {

            fPos = size_t(pos);

            if ( pos == 0 )

                gTestController.SetCurrentTestName("range insertion at begin()");

            else

                gTestController.SetCurrentTestName("range insertion at end()");

        }

        else

            gTestController.SetCurrentTestName("range insertion at random position");

    }

    void operator()( C& c ) const

    {

//        prepare_insert_range( c, fPos, fFirst, fLast );

        do_insert_range( c, fPos, fFirst, fLast, container_category(c) );

        // Prevent simulated failures during verification

        gTestController.CancelFailureCountdown();

        // Success. Check results.

        VerifyInsertion( original, c, fFirst, fLast, fPos );

    }

private: