Return-Path: 
 <stdcxx-dev-return-945-apmail-incubator-stdcxx-dev-archive=incubator.apache.org@incubator.apache.org>
Delivered-To: apmail-incubator-stdcxx-dev-archive@www.apache.org
Received: (qmail 84790 invoked from network); 17 Feb 2006 16:24:29 -0000
Received: from hermes.apache.org (HELO mail.apache.org) (209.237.227.199)
  by minotaur.apache.org with SMTP; 17 Feb 2006 16:24:29 -0000
Received: (qmail 78290 invoked by uid 500); 17 Feb 2006 16:24:29 -0000
Delivered-To: apmail-incubator-stdcxx-dev-archive@incubator.apache.org
Received: (qmail 78276 invoked by uid 500); 17 Feb 2006 16:24:28 -0000
Mailing-List: contact stdcxx-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
List-Help: <mailto:stdcxx-dev-help@incubator.apache.org>
List-Unsubscribe: <mailto:stdcxx-dev-unsubscribe@incubator.apache.org>
List-Post: <mailto:stdcxx-dev@incubator.apache.org>
List-Id: <stdcxx-dev.incubator.apache.org>
Reply-To: stdcxx-dev@incubator.apache.org
Delivered-To: mailing list stdcxx-dev@incubator.apache.org
Received: (qmail 78265 invoked by uid 99); 17 Feb 2006 16:24:28 -0000
Received: from asf.osuosl.org (HELO asf.osuosl.org) (140.211.166.49)
    by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 17 Feb 2006 08:24:28 -0800
X-ASF-Spam-Status: No, hits=-0.0 required=10.0
	tests=SPF_PASS
X-Spam-Check-By: apache.org
Received-SPF: pass (asf.osuosl.org: domain of AntonP@moscow.vdiweb.com
 designates 195.210.189.132 as permitted sender)
Received: from [195.210.189.132] (HELO exmsk.moscow.vdiweb.com)
 (195.210.189.132)
    by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 17 Feb 2006 08:24:27 -0800
Received: from [10.11.0.166] ([10.11.0.166]) by exmsk.moscow.vdiweb.com with
 Microsoft SMTPSVC(6.0.3790.1830);
	 Fri, 17 Feb 2006 19:23:45 +0300
Message-ID: <43F5F891.9@moscow.vdiweb.com>
Date: Fri, 17 Feb 2006 19:23:45 +0300
From: Anton Pevtsov <antonp@moscow.vdiweb.com>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US;
 rv:1.7) Gecko/20040514
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: stdcxx-dev@incubator.apache.org
Subject: test for lib.set.symmetric.difference
Content-Type: multipart/mixed;
 boundary="------------010100050504090503090109"
X-OriginalArrivalTime: 17 Feb 2006 16:23:45.0215 (UTC)
 FILETIME=[86188CF0:01C633DE]
X-Virus-Checked: Checked by ClamAV on apache.org
X-Spam-Rating: minotaur.apache.org 1.6.2 0/1000/N

--------------010100050504090503090109
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit

The attached file contains the test for the lib.set.symmetric.difference
algorithm. 

With best wishes,
Anton Pevtsov


--------------010100050504090503090109
Content-Type: text/plain;
 name="25.set.symmetric.difference.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="25.set.symmetric.difference.cpp"

/***************************************************************************
 *
 * set.symmetric.difference.cpp - test exercising 25.3.5.5 
 * [lib.set.symmetric.difference]
 *
 * $Id: $
 *
 ***************************************************************************
 *
 * Copyright (c) 1994-2005 Quovadx,  Inc., acting through its  Rogue Wave
 * Software division. Licensed under the Apache License, Version 2.0 (the
 * "License");  you may  not use this file except  in compliance with the
 * License.    You    may   obtain   a   copy   of    the   License    at
 * http://www.apache.org/licenses/LICENSE-2.0.    Unless   required    by
 * applicable law  or agreed to  in writing,  software  distributed under
 * the License is distributed on an "AS IS" BASIS,  WITHOUT WARRANTIES OR
 * CONDITIONS OF  ANY KIND, either  express or implied.  See  the License
 * for the specific language governing permissions  and limitations under
 * the License.
 * 
 **************************************************************************/

#include <algorithm>    // for set_symmetric_difference 
#include <cstring>      // for strlen, size_t

#include <alg_test.h>
#include <driver.h>     // for rw_test()

_RWSTD_NAMESPACE (std) { 

// disable explicit instantiation for compilers (like MSVC)
// that can't handle it
#ifndef _RWSTD_NO_EXPLICIT_INSTANTIATION

template 
OutputIter<lt_comp<assign<base<cpy_ctor> > > >
set_symmetric_difference (InputIter<lt_comp<assign<base<cpy_ctor> > > >,
                          InputIter<lt_comp<assign<base<cpy_ctor> > > >,
                          InputIter<lt_comp<assign<base<cpy_ctor> > > >,
                          InputIter<lt_comp<assign<base<cpy_ctor> > > >,
                          OutputIter<lt_comp<assign<base<cpy_ctor> > > >);

template 
OutputIter<lt_comp<assign<base<cpy_ctor> > > >
set_symmetric_difference (InputIter<lt_comp<assign<base<cpy_ctor> > > >,
                          InputIter<lt_comp<assign<base<cpy_ctor> > > >,
                          InputIter<lt_comp<assign<base<cpy_ctor> > > >,  
                          InputIter<lt_comp<assign<base<cpy_ctor> > > >,
                          OutputIter<lt_comp<assign<base<cpy_ctor> > > >,
                        binary_predicate<lt_comp<assign<base<cpy_ctor> > > >);

#endif // _RWSTD_NO_EXPLICIT_INSTANTIATION

}   // namespace std

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

struct Less
{
    static std::size_t funcalls_;

    // dummy arguments provided to prevent the class from being
    // default constructible and implicit conversion from int
    Less (int /* dummy */, int /* dummy */) {
        funcalls_ = 0;
    }

    // return a type other than bool but one that is implicitly
    // convertible to bool to detect incorrect assumptions
    conv_to_bool operator() (const X &x, const X &y) /* non-const */ {
        ++funcalls_;
        return conv_to_bool::make (x.val_ < y.val_);
    }

private:
    void operator= (Less&);   // not assignable
};

std::size_t Less::funcalls_;

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

struct SetSymDifferenceBase
{
    virtual ~SetSymDifferenceBase() {}

    const char* iter_names [3];

    // ipure virtual
    virtual X*
    set_sym_difference (const X*, const X*, const X*, const X*, 
                        X*, X*, const Less*) const = 0;
};

template <class InputIterator1, class InputIterator2, class OutputIterator>
struct SetSymDifference: SetSymDifferenceBase
{
    SetSymDifference () {
        iter_names [0] = type_name (InputIterator1 (0, 0, 0), (X*)0);
        iter_names [1] = type_name (InputIterator2 (0, 0, 0), (X*)0);
        iter_names [2] = type_name (OutputIterator (0, 0, 0), (X*)0);
    }

    virtual ~SetSymDifference() {}

    virtual X*
    set_sym_difference (const X    *xsrc1, const X *xsrc1_end,
                        const X    *xsrc2, const X *xsrc2_end,
                        X          *xdst, X *xdst_end,
                        const Less *ppred) const {

        const InputIterator1 first1 (xsrc1,     xsrc1, xsrc1_end);
        const InputIterator1 last1  (xsrc1_end, xsrc1, xsrc1_end);
        const InputIterator2 first2 (xsrc2,     xsrc2, xsrc2_end);
        const InputIterator2 last2  (xsrc2_end, xsrc2, xsrc2_end);

        const OutputIterator result (xdst, xdst, xdst_end);

        const OutputIterator ret = ppred ?
            std::set_symmetric_difference (first1, last1, first2, last2, 
                                           result, *ppred)
          : std::set_symmetric_difference (first1, last1, first2, last2, 
                                           result);

        // silence EDG eccp 3.7 and prior remark #550-D:
        //   variable was set but never used
        _RWSTD_UNUSED (ret);

        return ret.cur_;
    }
};

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

// exercises set_difference: 25.3.5.5
void test_set_sym_difference (int                             line,
                              const char                     *src1,
                              const char                     *src2,
                              const char                     *res,
                              const std::size_t               nf,
                              bool                            predicate,
                              const SetSymDifferenceBase     &alg)
{
    const char* const it1name = alg.iter_names [0];
    const char* const it2name = alg.iter_names [1];
    const char* const outname = alg.iter_names [2];
    const char* const fname   = "set_symmetric_difference";
    const char* const funname = predicate ? "Less" : 0;

    const std::size_t nsrc1 = std::strlen (src1);
    const std::size_t nsrc2 = std::strlen (src2);
    const std::size_t ndst = std::strlen (res);

    X* const xsrc1 = X::from_char (src1, nsrc1);
    X* const xsrc2 = X::from_char (src2, nsrc2);
    X* const xdst = new X[ndst];

    const int max1_id = nsrc1 > 0 ? xsrc1[nsrc1 - 1].id_ : -1;

    X* const xsrc1_end = xsrc1 + nsrc1;
    X* const xsrc2_end = xsrc2 + nsrc2;
    X* const xdst_end = xdst + ndst;

    const std::size_t last_n_op_lt = X::n_total_op_lt_;

    const Less pred (0, 0);
    const Less* const ppred = predicate ? &pred : 0;

    X* xdst_res = alg.set_sym_difference (xsrc1, xsrc1_end,
                                          xsrc2, xsrc2_end, 
                                          xdst, xdst_end, ppred);

    // check the returned value
    bool success = xdst_res == xdst_end;
    rw_assert (success, 0, line,
               "line %d: %s<%s, %s, %s%{?}, %s%{;}> (\"%s\", \"%s\", ...) "
               "got res + %td, expected res + %zu", 
               __LINE__, fname, it1name, it2name, outname, predicate, 
               funname, src1, src2, xdst_res - xdst, ndst);

    //quit here to avoid the running out of the array boundaries
    if (! success) {    
        delete[] xsrc1;
        delete[] xsrc2;
        delete[] xdst;
        return;
    }

    std::size_t n_ops_lt = ppred ? 
        Less::funcalls_ : X::n_total_op_lt_ - last_n_op_lt;

    // verify the algorithm correctness
    std::size_t i = 0;
    std::size_t n1 = 0;
    std::size_t n2 = 0;
    for ( ; i < ndst; i++) {
        xdst[i].origin_ <= max1_id ? n1++ : n2++;
        success = xdst[i].val_ == res[i];
        if (!success)
            break;
    }

    // to avoid errors in --trace mode
    i = i < ndst ? i : ndst - 1;

    rw_assert (success, 0, line,
               "line %d: %s<%s, %s, %s%{?}, %s%{;}> (\"%s\", \"%s\", ...) "
               " ==> \"%{X=*.*}\", expected \"%s\"", 
               __LINE__, fname, it1name, it2name, outname, predicate, 
               funname, src1, src2, int (ndst), i, xdst, res);

    // verfiy that only elements from first sequence sequence were taken
    success = n1 == nf;
    rw_assert (success, 0, line,
               "line %d: %s<%s, %s, %s%{?}, %s%{;}> (\"%s\", \"%s\", ...) "
               " ==> \"%{X=*.*}\" got %zu elements from first sequence and "
               "%zu from second, expected %zu from first and %zu from second",
               __LINE__, fname, it1name, it2name, outname, predicate, funname, 
               src1, src2, int (ndst), -1, xdst, n1, n2, nf, ndst - nf);

    // verify that the operation is stable : two equal elements
    // should go in the same order
    for (i = 1; i < ndst; i++) {
        if (xdst[i - 1].val_ == xdst[i].val_) {
            success = xdst[i - 1].origin_ < xdst[i].origin_;
            if (!success)
                break;
        }
    }

    // to avoid errors in --trace mode
    if (ndst > 1) {
        i = i < ndst ? i : ndst - 1;

        rw_assert (success, 0, line,
                   "line %d: %s<%s, %s, %s%{?}, %s%{;}> (\"%s\", \"%s\", ...)"
                   " ==> \"%{X=*.*}\" not stable : elements %#c==%#c have "
                   "ids %d >= %d ",
                   __LINE__, fname, it1name, it2name, outname, predicate, 
                   funname, src1, src2, int (ndst), i, xdst, xdst[i - 1].val_, 
                   xdst[i].val_, xdst[i - 1].origin_, xdst[i].origin_);
    }

    // verify the complexity
    std::size_t n_exp_ops = nsrc1 + nsrc2 > 0 ? 2 * (nsrc1 + nsrc2) - 1 : 0;
    rw_assert (n_ops_lt <= n_exp_ops, 0, line,
               "line %d: %s<%s, %s, %s%{?}, %s%{;}> (\"%s\", \"%s\", ...) "
               "complexity: got %zu, expected no more than %zu",
               __LINE__, fname, it1name, it2name, outname, predicate, funname, 
               src1, src2, n_ops_lt, n_exp_ops);

    delete[] xsrc1;
    delete[] xsrc2;
    delete[] xdst;
}

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

void test_set_sym_difference (const SetSymDifferenceBase &alg, 
                              bool                        predicate)
{
    const char* const it1name = alg.iter_names [0];
    const char* const it2name = alg.iter_names [1];
    const char* const outname = alg.iter_names [2];
    const char* const fname   = "set_symmetric_difference";
    const char* const funname = predicate ? "Less" : 0;

    rw_info (0, 0, 0,
             "%s std::%s(%s, %3$s, %s, %4$s, %1$s%{?}, %s%{;})",
             outname, fname, it1name, it2name, predicate, funname);

#define TEST(src1, src2, res, nf)                                               \
    test_set_sym_difference (__LINE__, src1, src2, res, nf, predicate, alg)  

    TEST ("a", "", "a", 1);
    TEST ("abcde", "", "abcde", 5);

    TEST ("", "a", "a", 0);
    TEST ("", "abcde", "abcde", 0);

    TEST ("a", "b", "ab", 1);
    TEST ("b", "a", "ab", 1);

    TEST ("aa", "aa", "", 0);
    TEST ("ab", "ab", "", 0);

    TEST ("aa", "ab", "ab", 1);
    TEST ("aa", "bb", "aabb", 2);
    TEST ("ab", "bb", "ab", 1);
    TEST ("ac", "bb", "abbc", 2);

    TEST ("ace", "bdf", "abcdef", 3);
    TEST ("acf", "bdf", "abcd", 2);
    TEST ("ade", "bdf", "abef", 2);
    TEST ("bce", "bdf", "cdef", 2);

    TEST ("aacee", "aacee", "", 0);
    TEST ("aacee", "aaace", "ae", 1);
    TEST ("aacee", "aaaae", "aace", 2);
    TEST ("aacee", "aaaaa", "aaacee", 3);
    TEST ("aacee", "aaabd", "abcdee", 3);
    TEST ("aacee", "aabee", "bc", 1);

    TEST ("aaaaa", "aaaaa", "", 0);
    TEST ("aaaaa", "aaaa", "a", 1);
    TEST ("aaaaa", "aaa", "aa", 2);
    TEST ("aaaaa", "aa", "aaa", 3);
    TEST ("aaaaa", "a", "aaaa", 4);
}

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

/* extern */ int rw_opt_no_predicate;           // --no-predicate
/* extern */ int rw_opt_no_input_iter;          // --no-InputIterator
/* extern */ int rw_opt_no_output_iter;         // --no-OutputIterator
/* extern */ int rw_opt_no_fwd_iter;            // --no-ForwardIterator
/* extern */ int rw_opt_no_bidir_iter;          // --no-BidirectionalIterator
/* extern */ int rw_opt_no_rnd_iter;            // --no-RandomAccessIterator

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

template <class InputIterator1, class InputIterator2, class OutputIterator>
void gen_set_sym_difference_test (const InputIterator1&,
                                  const InputIterator2&,
                                  const OutputIterator&,
                                  bool predicate)
{
    const SetSymDifference<
            InputIterator1, InputIterator2, OutputIterator> alg;

    test_set_sym_difference (alg, predicate);
}

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

template <class InputIterator1, class InputIterator2>
void gen_set_sym_difference_test (const InputIterator1 &it1,
                                  const InputIterator2 &it2,
                                  bool predicate)
{
    if (0 == rw_opt_no_output_iter)
        gen_set_sym_difference_test (
            it1, it2, OutputIter<X>(0, 0, 0), predicate);
    if (0 == rw_opt_no_fwd_iter)
        gen_set_sym_difference_test (
            it1, it2, FwdIter<X>(0, 0, 0), predicate);
    if (0 == rw_opt_no_bidir_iter)
        gen_set_sym_difference_test (
            it1, it2, BidirIter<X>(0, 0, 0), predicate);
    if (0 == rw_opt_no_rnd_iter)
        gen_set_sym_difference_test (
            it1, it2, RandomAccessIter<X>(0, 0, 0), predicate);
}

template <class InputIterator1>
void gen_set_sym_difference_test (const InputIterator1 &it1, 
                                  bool                  predicate)
{
    if (0 == rw_opt_no_input_iter)
        gen_set_sym_difference_test (
            it1, InputIter<X>(0, 0, 0), predicate);
    if (0 == rw_opt_no_fwd_iter)
        gen_set_sym_difference_test (
            it1, ConstFwdIter<X>(0, 0, 0), predicate);
    if (0 == rw_opt_no_bidir_iter)
        gen_set_sym_difference_test (
            it1, ConstBidirIter<X>(0, 0, 0), predicate);
    if (0 == rw_opt_no_rnd_iter)
        gen_set_sym_difference_test (
            it1, ConstRandomAccessIter<X>(0, 0, 0), predicate);
}

// generates a specialization of the set_union test for each of the required
// iterator categopries
void gen_set_sym_difference_test (bool predicate)
{
    rw_info (0, 0, 0,
             "template <class %s, class %s, class %s%{?}, class %s%{;}> %3$s "
             "set_symmetric_difference (%1$s, %1$s, %2$s, %2$s, "
             "%3$s%{?}, %s%{;})",
             "InputIterator1", "InputIterator2", "OutputIterator",
             predicate, "Compare", predicate, "Compare");

    if (rw_opt_no_output_iter)
        rw_note (0, 0, 0, "OutputIterator test disabled");

    if (rw_opt_no_input_iter)
        rw_note (0, 0, 0, "InputIterator test disabled");
    else
        gen_set_sym_difference_test (InputIter<X>(0, 0, 0), predicate);

    if (rw_opt_no_fwd_iter)
        rw_note (0, 0, 0, "ForwardIterator test disabled");
    else
        gen_set_sym_difference_test (ConstFwdIter<X>(0, 0, 0), predicate);

    if (rw_opt_no_bidir_iter)
        rw_note (0, 0, 0, "BidirectionalIterator test disabled");
    else
        gen_set_sym_difference_test (ConstBidirIter<X>(0, 0, 0), predicate);

    if (rw_opt_no_rnd_iter)
        rw_note (0, 0, 0, "RandomAccessIterator test disabled");
    else
        gen_set_sym_difference_test (
            ConstRandomAccessIter<X>(0, 0, 0), predicate);
}

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

static int run_test (int, char*[])
{
    if (rw_opt_no_predicate)
        rw_note (0, 0, 0, "predicate test disabled");

    const int niters = rw_opt_no_predicate ? 1 : 2;

    //////////////////////////////////////////////////////////////////
    for (int i = 0; i != niters; ++i) {
        gen_set_sym_difference_test (1 == i);
    }

    return 0;
}

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

int main (int argc, char *argv[])
{
    return rw_test (argc, argv, __FILE__,
                    "lib.set.symmetric.difference",
                    0 /* no comment */, run_test,
                    "|-no-predicate#"
                    "|-no-InputIterator# "
                    "|-no-OutputIterator# "
                    "|-no-ForwardIterator# "
                    "|-no-BidirectionalIterator# "
                    "|-no-RandomAccessIterator#",
                    &rw_opt_no_predicate,
                    &rw_opt_no_input_iter,
                    &rw_opt_no_output_iter,
                    &rw_opt_no_fwd_iter,
                    &rw_opt_no_bidir_iter,
                    &rw_opt_no_rnd_iter);
}

--------------010100050504090503090109--