From patchwork Wed Oct 12 15:26:40 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 681350 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3svHlq3VyFz9sBr for ; Thu, 13 Oct 2016 02:27:03 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=Fm48aW2M; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=o5ipAnenOok12rhr0Bq5+LJ6bYDT8L5NSPo6zcAbxmx+KO9R2O1wI obQtMFk6Az3x5QtLSa7bPXoSLN+rzZDpOH/QGyCTZXygso4XlSHMODN++FuZMwe6 rBnWvOtlK7nWC1JmQqHImFdAznqbFZ4biyMQfkAi96XJTxxixaGAt8= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=JiorxVWc/SYGSDovJdy/sohNkrA=; b=Fm48aW2MZHFNH2SaGWDb Lbu+SHvbt9z50IjszI0DDwmo026RExJLtP8UKzxDcXA6jKk1d2sO6+UFqhk6Iv9F CeV+OMTq5788Vg+ulIB63zaCpF1kMgav45+PC/09vUInu97qrY0AClItynPPS/Hf xGdCjQRm/Juj1vF65ZwYEHk= Received: (qmail 119424 invoked by alias); 12 Oct 2016 15:26:53 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 119370 invoked by uid 89); 12 Oct 2016 15:26:53 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.3 required=5.0 tests=BAYES_20, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=rng, Components, test04, __n X-Spam-User: qpsmtpd, 2 recipients X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Wed, 12 Oct 2016 15:26:43 +0000 Received: from int-mx14.intmail.prod.int.phx2.redhat.com (int-mx14.intmail.prod.int.phx2.redhat.com [10.5.11.27]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id E8069C0921B0; Wed, 12 Oct 2016 15:26:41 +0000 (UTC) Received: from localhost (ovpn-116-39.ams2.redhat.com [10.36.116.39]) by int-mx14.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id u9CFQeRS003976; Wed, 12 Oct 2016 11:26:41 -0400 Date: Wed, 12 Oct 2016 16:26:40 +0100 From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [PATCH] Define std::sample for C++17 Message-ID: <20161012152640.GA11799@redhat.com> MIME-Version: 1.0 Content-Disposition: inline X-Clacks-Overhead: GNU Terry Pratchett User-Agent: Mutt/1.7.0 (2016-08-17) I forgot that std::sample() was added to C++17, so it wasn't in our status table. It is now. I changed the testcase to use our iterator wrappers instead of containers, which found some bugs. I intend to go through other tests where I've used std::forward_list to get forward iterators, or stream iterators for input/output iterators, and make them use the wrappers too. * doc/xml/manual/status_cxx2017.xml: Add std::sample status. * doc/html/*: Regenerate. * include/experimental/algorithm (__sample): Move to bits/stl_algo.h and into namespace std. * include/bits/stl_algo.h (__sample): Define here. Fix invalid use of input iterator. Defend against overloaded comma operator. (sample): Define for C++17. * testsuite/25_algorithms/sample/1.cc: New test. Tested powerpc64le-linux, committed to trunk. commit d727fe4bd81e5c79d4f37df66fad53503e01ccec Author: Jonathan Wakely Date: Wed Oct 12 15:02:59 2016 +0100 Define std::sample for C++17 * doc/xml/manual/status_cxx2017.xml: Add std::sample status. * doc/html/*: Regenerate. * include/experimental/algorithm (__sample): Move to bits/stl_algo.h and into namespace std. * include/bits/stl_algo.h (__sample): Define here. Fix invalid use of input iterator. Defend against overloaded comma operator. (sample): Define for C++17. * testsuite/25_algorithms/sample/1.cc: New test. diff --git a/libstdc++-v3/doc/xml/manual/status_cxx2017.xml b/libstdc++-v3/doc/xml/manual/status_cxx2017.xml index c6b8440..ae8dfa9 100644 --- a/libstdc++-v3/doc/xml/manual/status_cxx2017.xml +++ b/libstdc++-v3/doc/xml/manual/status_cxx2017.xml @@ -182,6 +182,17 @@ Feature-testing recommendations for C++. + Library Fundamentals V1 TS Components: Sampling + + + P0220R1 + + + 7 + __cpp_lib_sample >= 201603 + + + Constant View: A proposal for a std::as_const helper function template diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index ea0b56c..0538a79 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -5615,6 +5615,86 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO __gnu_cxx::__ops::__iter_comp_iter(__comp)); } +#if __cplusplus >= 201402L + /// Reservoir sampling algorithm. + template + _RandomAccessIterator + __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, + _RandomAccessIterator __out, random_access_iterator_tag, + _Size __n, _UniformRandomBitGenerator&& __g) + { + using __distrib_type = uniform_int_distribution<_Size>; + using __param_type = typename __distrib_type::param_type; + __distrib_type __d{}; + _Size __sample_sz = 0; + while (__first != __last && __sample_sz != __n) + { + __out[__sample_sz++] = *__first; + ++__first; + } + for (auto __pop_sz = __sample_sz; __first != __last; + ++__first, (void) ++__pop_sz) + { + const auto __k = __d(__g, __param_type{0, __pop_sz}); + if (__k < __n) + __out[__k] = *__first; + } + return __out + __sample_sz; + } + + /// Selection sampling algorithm. + template + _OutputIterator + __sample(_ForwardIterator __first, _ForwardIterator __last, + forward_iterator_tag, + _OutputIterator __out, _Cat, + _Size __n, _UniformRandomBitGenerator&& __g) + { + using __distrib_type = uniform_int_distribution<_Size>; + using __param_type = typename __distrib_type::param_type; + __distrib_type __d{}; + _Size __unsampled_sz = std::distance(__first, __last); + for (__n = std::min(__n, __unsampled_sz); __n != 0; ++__first) + if (__d(__g, __param_type{0, --__unsampled_sz}) < __n) + { + *__out++ = *__first; + --__n; + } + return __out; + } + +#if __cplusplus > 201402L +#define __cpp_lib_sample 201603 + /// Take a random sample from a population. + template + _SampleIterator + sample(_PopulationIterator __first, _PopulationIterator __last, + _SampleIterator __out, _Distance __n, + _UniformRandomBitGenerator&& __g) + { + using __pop_cat = typename + std::iterator_traits<_PopulationIterator>::iterator_category; + using __samp_cat = typename + std::iterator_traits<_SampleIterator>::iterator_category; + + static_assert( + __or_, + is_convertible<__samp_cat, random_access_iterator_tag>>::value, + "output range must use a RandomAccessIterator when input range" + " does not meet the ForwardIterator requirements"); + + static_assert(is_integral<_Distance>::value, + "sample size must be an integer type"); + + return std::__sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, + __n, std::forward<_UniformRandomBitGenerator>(__g)); + } +#endif // C++17 +#endif // C++14 + _GLIBCXX_END_NAMESPACE_ALGO } // namespace std diff --git a/libstdc++-v3/include/experimental/algorithm b/libstdc++-v3/include/experimental/algorithm index 0ba6311..eb18dde 100644 --- a/libstdc++-v3/include/experimental/algorithm +++ b/libstdc++-v3/include/experimental/algorithm @@ -36,7 +36,6 @@ #else #include -#include #include namespace std _GLIBCXX_VISIBILITY(default) @@ -55,52 +54,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION #define __cpp_lib_experimental_sample 201402 - /// Reservoir sampling algorithm. - template - _RandomAccessIterator - __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, - _RandomAccessIterator __out, random_access_iterator_tag, - _Size __n, _UniformRandomNumberGenerator&& __g) - { - using __distrib_type = std::uniform_int_distribution<_Size>; - using __param_type = typename __distrib_type::param_type; - __distrib_type __d{}; - _Size __sample_sz = 0; - while (__first != __last && __sample_sz != __n) - __out[__sample_sz++] = *__first++; - for (auto __pop_sz = __sample_sz; __first != __last; - ++__first, ++__pop_sz) - { - const auto __k = __d(__g, __param_type{0, __pop_sz}); - if (__k < __n) - __out[__k] = *__first; - } - return __out + __sample_sz; - } - - /// Selection sampling algorithm. - template - _OutputIterator - __sample(_ForwardIterator __first, _ForwardIterator __last, - forward_iterator_tag, - _OutputIterator __out, _Cat, - _Size __n, _UniformRandomNumberGenerator&& __g) - { - using __distrib_type = std::uniform_int_distribution<_Size>; - using __param_type = typename __distrib_type::param_type; - __distrib_type __d{}; - _Size __unsampled_sz = std::distance(__first, __last); - for (__n = std::min(__n, __unsampled_sz); __n != 0; ++__first) - if (__d(__g, __param_type{0, --__unsampled_sz}) < __n) - { - *__out++ = *__first; - --__n; - } - return __out; - } - /// Take a random sample from a population. template @@ -123,9 +76,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION static_assert(is_integral<_Distance>::value, "sample size must be an integer type"); - return std::experimental::__sample( - __first, __last, __pop_cat{}, __out, __samp_cat{}, - __n, std::forward<_UniformRandomNumberGenerator>(__g)); + return std::__sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, + __n, + std::forward<_UniformRandomNumberGenerator>(__g)); } _GLIBCXX_END_NAMESPACE_VERSION diff --git a/libstdc++-v3/testsuite/25_algorithms/sample/1.cc b/libstdc++-v3/testsuite/25_algorithms/sample/1.cc new file mode 100644 index 0000000..10376e2 --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/sample/1.cc @@ -0,0 +1,110 @@ +// Copyright (C) 2014-2016 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++17" } +// { dg-do run { target c++1z } } + +#include +#include +#include +#include + +std::mt19937 rng; + +using std::sample; +using __gnu_test::test_container; +using __gnu_test::input_iterator_wrapper; +using __gnu_test::output_iterator_wrapper; +using __gnu_test::forward_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; + +void +test01() +{ + const int in[] = { 1, 2 }; + test_container pop(in); + const int sample_size = 10; + int samp[sample_size] = { }; + + // population smaller than desired sample size + auto it = sample(pop.begin(), pop.end(), samp, sample_size, rng); + VERIFY( it == samp + std::distance(pop.begin(), pop.end()) ); + const auto sum = std::accumulate(pop.begin(), pop.end(), 0); + VERIFY( std::accumulate(samp, samp + sample_size, 0) == sum ); +} + +void +test02() +{ + const int in[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; + test_container pop(in); + const int sample_size = 10; + int samp[sample_size] = { }; + + auto it = sample(pop.begin(), pop.end(), samp, sample_size, rng); + VERIFY( it == samp + sample_size ); + + // verify no duplicates + std::sort(samp, it); + auto it2 = std::unique(samp, it); + VERIFY( it2 == it ); +} + +void +test03() +{ + const int in[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; + test_container pop(in); + const int sample_size = 5; + int samp[sample_size] = { }; + + // input iterator for population + auto it = sample(pop.begin(), pop.end(), samp, sample_size, rng); + VERIFY( it == samp + sample_size ); + + // verify no duplicates + std::sort(samp, it); + auto it2 = std::unique(samp, it); + VERIFY( it2 == it ); +} + +void +test04() +{ + const int in[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; + test_container pop(in); + const int sample_size = 5; + int out[sample_size]; + test_container samp(out); + + // forward iterator for population and output iterator for result + auto res = sample(pop.begin(), pop.end(), samp.begin(), sample_size, rng); + + // verify no duplicates + std::sort(std::begin(out), std::end(out)); + auto it = std::unique(std::begin(out), std::end(out)); + VERIFY( it == std::end(out) ); +} + +int +main() +{ + test01(); + test02(); + test03(); + test04(); +}