From patchwork Fri Jan 14 01:24:50 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Carlini X-Patchwork-Id: 78857 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]) by ozlabs.org (Postfix) with SMTP id 26C94B7088 for ; Fri, 14 Jan 2011 12:25:05 +1100 (EST) Received: (qmail 27172 invoked by alias); 14 Jan 2011 01:25:03 -0000 Received: (qmail 27086 invoked by uid 22791); 14 Jan 2011 01:25:01 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_NONE X-Spam-Check-By: sourceware.org Received: from vsmtp4.tin.it (HELO vsmtp4.tin.it) (212.216.176.224) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 14 Jan 2011 01:24:54 +0000 Received: from [192.168.0.4] (79.33.220.126) by vsmtp4.tin.it (8.5.132) id 4CFCBB2A02A5170D; Fri, 14 Jan 2011 02:24:50 +0100 Message-ID: <4D2FA5E2.2020509@oracle.com> Date: Fri, 14 Jan 2011 02:24:50 +0100 From: Paolo Carlini User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.1.16) Gecko/20101125 SUSE/3.0.11 Thunderbird/3.0.11 MIME-Version: 1.0 To: "gcc-patches@gcc.gnu.org" CC: libstdc++ Subject: [v3] Add std::is_permutation (in C++0x mode) X-IsSubscribed: yes 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 Hi, this just completes the work started back in 2010. Tested x86_64-linux multilib, committed. Paolo. ///////////////////////////////// 2011-01-13 Paolo Carlini * testsuite/25_algorithms/is_permutation/check_type.cc: New. * testsuite/25_algorithms/is_permutation/requirements/ explicit_instantiation/2.cc: Likewise. * testsuite/25_algorithms/is_permutation/requirements/ explicit_instantiation/pod.cc: Likewise. * testsuite/25_algorithms/is_permutation/1.cc: Likewise. 2011-01-13 John Lakos Pablo Halpern Paolo Carlini * include/bits/stl_algo.h (is_permutation): Add, per N3068. * include/bits/algorithmfwd.h: Add. Index: include/bits/stl_algo.h =================================================================== --- include/bits/stl_algo.h (revision 168743) +++ include/bits/stl_algo.h (working copy) @@ -1,6 +1,7 @@ // Algorithm implementation -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, +// 2010, 2011 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -63,7 +64,8 @@ #include // for _Temporary_buffer #ifdef __GXX_EXPERIMENTAL_CXX0X__ -#include // for std::uniform_int_distribution +#include // for std::uniform_int_distribution +#include // for std::bind #endif // See concept_check.h for the __glibcxx_*_requires macros. @@ -4109,6 +4111,99 @@ return std::make_pair(*__p.first, *__p.second); } + /** + * @brief Checks whether a permutaion of the second sequence is equal + * to the first sequence. + * @ingroup non_mutating_algorithms + * @param first1 Start of first range. + * @param last1 End of first range. + * @param first2 Start of second range. + * @return true if there exists a permutation of the elements in the range + * [first2, first2 + (last1 - first1)), beginning with + * ForwardIterator2 begin, such that equal(first1, last1, begin) + * returns true; otherwise, returns false. + */ + template + bool + is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2) + { + // Efficiently compare identical prefixes: O(N) if sequences + // have the same elements in the same order. + for (; __first1 != __last1; ++__first1, ++__first2) + if (!(*__first1 == *__first2)) + break; + + if (__first1 == __last1) + return true; + + // Establish __last2 assuming equal ranges by iterating over the + // rest of the list. + _ForwardIterator2 __last2 = __first2; + std::advance(__last2, std::distance(__first1, __last1)); + for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) + { + if (__scan != _GLIBCXX_STD_P::find(__first1, __scan, *__scan)) + continue; // We've seen this one before. + + auto __matches = std::count(__first2, __last2, *__scan); + if (0 == __matches + || std::count(__scan, __last1, *__scan) != __matches) + return false; + } + return true; + } + + /** + * @brief Checks whether a permutation of the second sequence is equal + * to the first sequence. + * @ingroup non_mutating_algorithms + * @param first1 Start of first range. + * @param last1 End of first range. + * @param first2 Start of second range. + * @param pred A binary predicate. + * @return true if there exists a permutation of the elements in the range + * [first2, first2 + (last1 - first1)), beginning with + * ForwardIterator2 begin, such that equal(first1, last1, begin, + * pred) returns true; otherwise, returns false. + */ + template + bool + is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _BinaryPredicate __pred) + { + // Efficiently compare identical prefixes: O(N) if sequences + // have the same elements in the same order. + for (; __first1 != __last1; ++__first1, ++__first2) + if (!bool(__pred(*__first1, *__first2))) + break; + + if (__first1 == __last1) + return true; + + // Establish __last2 assuming equal ranges by iterating over the + // rest of the list. + _ForwardIterator2 __last2 = __first2; + std::advance(__last2, std::distance(__first1, __last1)); + for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) + { + using std::placeholders::_1; + + if (__scan != _GLIBCXX_STD_P::find_if(__first1, __scan, + std::bind(__pred, _1, *__scan))) + continue; // We've seen this one before. + + auto __matches = std::count_if(__first2, __last2, + std::bind(__pred, _1, *__scan)); + if (0 == __matches + || std::count_if(__scan, __last1, + std::bind(__pred, _1, *__scan)) != __matches) + return false; + } + return true; + } + #ifdef _GLIBCXX_USE_C99_STDINT_TR1 /** * @brief Shuffle the elements of a sequence using a uniform random Index: include/bits/algorithmfwd.h =================================================================== --- include/bits/algorithmfwd.h (revision 168743) +++ include/bits/algorithmfwd.h (working copy) @@ -1,6 +1,6 @@ // declarations -*- C++ -*- -// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010, 2011 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 @@ -301,6 +301,15 @@ bool is_partitioned(_IIter, _IIter, _Predicate); + template + bool + is_permutation(_FIter1, _FIter1, _FIter2); + + template + bool + is_permutation(_FIter1, _FIter1, _FIter2, _BinaryPredicate); + template bool is_sorted(_FIter, _FIter); Index: testsuite/25_algorithms/is_permutation/check_type.cc =================================================================== --- testsuite/25_algorithms/is_permutation/check_type.cc (revision 0) +++ testsuite/25_algorithms/is_permutation/check_type.cc (revision 0) @@ -0,0 +1,48 @@ +// { dg-options "-std=gnu++0x" } + +// 2011-01-13 Paolo Carlini +// +// Copyright (C) 2011 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 +// . + +// 25.2.12 [alg.is_permutation] Is permutation + +// { dg-do compile } + +#include +#include + +using __gnu_test::forward_iterator_wrapper; + +struct X { }; + +bool operator==(const X&, const X) { return true; } +bool predicate(const X&, const X&) { return true; } + +bool +test1(forward_iterator_wrapper& lhs1, + forward_iterator_wrapper& rhs1) +{ + return std::is_permutation(lhs1, lhs1, rhs1); +} + +bool +test2(forward_iterator_wrapper& x1, + forward_iterator_wrapper& x2) +{ + return std::is_permutation(x1, x1, x2, predicate); +} Index: testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/2.cc =================================================================== --- testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/2.cc (revision 0) +++ testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/2.cc (revision 0) @@ -0,0 +1,41 @@ +// { dg-options "-std=gnu++0x" } +// { dg-do compile } + +// 2011-01-13 Paolo Carlini +// +// Copyright (C) 2011 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 +// . + +#include +#include +#include + +namespace std +{ + using __gnu_test::NonDefaultConstructible; + + typedef NonDefaultConstructible value_type; + typedef value_type* iterator_type; + typedef std::pointer_to_binary_function + predicate_type; + + template bool is_permutation(iterator_type, iterator_type, + iterator_type); + + template bool is_permutation(iterator_type, iterator_type, + iterator_type, predicate_type); +} Index: testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/pod.cc =================================================================== --- testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/pod.cc (revision 0) +++ testsuite/25_algorithms/is_permutation/requirements/explicit_instantiation/pod.cc (revision 0) @@ -0,0 +1,40 @@ +// { dg-options "-std=gnu++0x" } +// { dg-do compile } + +// 2011-01-13 Paolo Carlini +// +// Copyright (C) 2011 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 +// . + +#include +#include + +namespace std +{ + using __gnu_test::pod_int; + + typedef pod_int value_type; + typedef value_type* iterator_type; + typedef std::pointer_to_binary_function + predicate_type; + + template bool is_permutation(iterator_type, iterator_type, + iterator_type); + + template bool is_permutation(iterator_type, iterator_type, + iterator_type, predicate_type); +} Index: testsuite/25_algorithms/is_permutation/1.cc =================================================================== --- testsuite/25_algorithms/is_permutation/1.cc (revision 0) +++ testsuite/25_algorithms/is_permutation/1.cc (revision 0) @@ -0,0 +1,104 @@ +// { dg-options "-std=gnu++0x" } + +// 2011-01-13 Paolo Carlini +// +// Copyright (C) 2011 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 +// . + +// 25.2.12 [alg.is_permutation] Is permutation + +#include +#include +#include + +struct my_equal_to +{ + bool + operator()(int __x, int __y) const + { return __x % 10 == __y % 10; } +}; + +const int arr0[] = { 11, 22, 33, 44, 55 }; + +void +do_test(int arr1[5], bool np = true) +{ + bool test __attribute__((unused)) = true; + + do + VERIFY( std::is_permutation(arr1, arr1 + 5, arr0) == np ); + while (std::next_permutation(arr1, arr1 + 5)); +} + +template + void + do_test(int arr1[5], Predicate pred, bool np = true) + { + bool test __attribute__((unused)) = true; + + do + VERIFY( std::is_permutation(arr1, arr1 + 5, arr0, pred) == np ); + while (std::next_permutation(arr1, arr1 + 5)); + } + +void test01() +{ + int arr1[] = { 11, 22, 33, 44, 55 }; + do_test(arr1); + + int arr2[] = { 11, 33, 33, 44, 55 }; + do_test(arr2, false); + + int arr3[] = { 33, 33, 33, 44, 44 }; + do_test(arr3, false); + + int arr4[] = { 11, 22, 33, 44, 55 }; + do_test(arr4, std::equal_to()); + + int arr5[] = { 11, 33, 33, 44, 55 }; + do_test(arr5, std::equal_to(), false); + + int arr6[] = { 33, 33, 33, 44, 44 }; + do_test(arr6, std::equal_to(), false); + + int arr7[] = { 1, 2, 3, 4, 5 }; + do_test(arr7, my_equal_to()); + + int arr8[] = { 1, 3, 3, 4, 5 }; + do_test(arr8, my_equal_to(), false); + + int arr9[] = { 3, 3, 3, 4, 4 }; + do_test(arr9, my_equal_to(), false); + + int arr10[] = { 111, 222, 333, 444, 555 }; + do_test(arr10, my_equal_to()); + + int arr11[] = { 1, 222, 33, 4, 55 }; + do_test(arr11, my_equal_to()); + + int arr12[] = { 111, 333, 333, 444, 555 }; + do_test(arr12, my_equal_to(), false); + + int arr13[] = { 333, 333, 333, 444, 444 }; + do_test(arr13, my_equal_to(), false); +} + +int main() +{ + test01(); + return 0; +}