111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// -*- C++ -*- 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2007-2014 Free Software Foundation, Inc. 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is part of the GNU ISO C++ Library. This library is free 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// software; you can redistribute it and/or modify it under the terms 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the GNU General Public License as published by the Free Software 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Foundation; either version 3, or (at your option) any later 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// version. 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This library is distributed in the hope that it will be useful, but 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// WITHOUT ANY WARRANTY; without even the implied warranty of 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// General Public License for more details. 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Under Section 7 of GPL version 3, you are granted additional 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// permissions described in the GCC Runtime Library Exception, version 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 3.1, as published by the Free Software Foundation. 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// You should have received a copy of the GNU General Public License and 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// a copy of the GCC Runtime Library Exception along with this program; 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <http://www.gnu.org/licenses/>. 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/** @file parallel/find_selectors.h 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief _Function objects representing different tasks to be plugged 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * into the parallel find algorithm. 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This file is a GNU parallel extension to the Standard C++ Library. 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Written by Felix Putze. 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef _GLIBCXX_PARALLEL_FIND_SELECTORS_H 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define _GLIBCXX_PARALLEL_FIND_SELECTORS_H 1 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <parallel/tags.h> 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <parallel/basic_iterator.h> 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <bits/stl_pair.h> 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace __gnu_parallel 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Base class of all __gnu_parallel::__find_template selectors. */ 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct __generic_find_selector 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { }; 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Test predicate on a single element, used for std::find() 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * and std::find_if (). 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct __find_if_selector : public __generic_find_selector 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Test on one position. 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __i1 _Iterator on first sequence. 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __i2 _Iterator on second sequence (unused). 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __pred Find predicate. 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, typename _RAIter2, 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Pred> 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator()(_RAIter1 __i1, _RAIter2 __i2, _Pred __pred) 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return __pred(*__i1); } 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Corresponding sequential algorithm on a sequence. 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin1 Begin iterator of first sequence. 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end1 End iterator of first sequence. 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin2 Begin iterator of second sequence. 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __pred Find predicate. 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, typename _RAIter2, 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Pred> 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<_RAIter1, _RAIter2> 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_sequential_algorithm(_RAIter1 __begin1, 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter1 __end1, 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2 __begin2, _Pred __pred) 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return std::make_pair(find_if(__begin1, __end1, __pred, 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert sequential_tag()), __begin2); } 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Test predicate on two adjacent elements. */ 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct __adjacent_find_selector : public __generic_find_selector 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Test on one position. 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __i1 _Iterator on first sequence. 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __i2 _Iterator on second sequence (unused). 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __pred Find predicate. 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, typename _RAIter2, 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Pred> 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator()(_RAIter1 __i1, _RAIter2 __i2, _Pred __pred) 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Passed end iterator is one short. 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __pred(*__i1, *(__i1 + 1)); 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Corresponding sequential algorithm on a sequence. 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin1 Begin iterator of first sequence. 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end1 End iterator of first sequence. 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin2 Begin iterator of second sequence. 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __pred Find predicate. 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, typename _RAIter2, 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Pred> 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<_RAIter1, _RAIter2> 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_sequential_algorithm(_RAIter1 __begin1, 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter1 __end1, 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2 __begin2, _Pred __pred) 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Passed end iterator is one short. 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter1 __spot = adjacent_find(__begin1, __end1 + 1, 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pred, sequential_tag()); 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__spot == (__end1 + 1)) 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __spot = __end1; 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return std::make_pair(__spot, __begin2); 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Test inverted predicate on a single element. */ 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct __mismatch_selector : public __generic_find_selector 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Test on one position. 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __i1 _Iterator on first sequence. 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __i2 _Iterator on second sequence (unused). 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __pred Find predicate. 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, typename _RAIter2, 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Pred> 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator()(_RAIter1 __i1, _RAIter2 __i2, _Pred __pred) 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return !__pred(*__i1, *__i2); } 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Corresponding sequential algorithm on a sequence. 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin1 Begin iterator of first sequence. 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end1 End iterator of first sequence. 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin2 Begin iterator of second sequence. 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __pred Find predicate. 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, typename _RAIter2, 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Pred> 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<_RAIter1, _RAIter2> 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_sequential_algorithm(_RAIter1 __begin1, 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter1 __end1, 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2 __begin2, _Pred __pred) 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return mismatch(__begin1, __end1, __begin2, 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pred, sequential_tag()); } 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Test predicate on several elements. */ 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _FIterator> 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert struct __find_first_of_selector : public __generic_find_selector 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _FIterator _M_begin; 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _FIterator _M_end; 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert explicit __find_first_of_selector(_FIterator __begin, 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _FIterator __end) 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_begin(__begin), _M_end(__end) { } 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Test on one position. 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __i1 _Iterator on first sequence. 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __i2 _Iterator on second sequence (unused). 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __pred Find predicate. */ 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, typename _RAIter2, 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Pred> 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator()(_RAIter1 __i1, _RAIter2 __i2, _Pred __pred) 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (_FIterator __pos_in_candidates = _M_begin; 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pos_in_candidates != _M_end; ++__pos_in_candidates) 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__pred(*__i1, *__pos_in_candidates)) 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return true; 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return false; 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Corresponding sequential algorithm on a sequence. 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin1 Begin iterator of first sequence. 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end1 End iterator of first sequence. 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin2 Begin iterator of second sequence. 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __pred Find predicate. */ 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, typename _RAIter2, 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Pred> 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::pair<_RAIter1, _RAIter2> 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_sequential_algorithm(_RAIter1 __begin1, 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter1 __end1, 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2 __begin2, _Pred __pred) 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return std::make_pair(find_first_of(__begin1, __end1, 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_begin, _M_end, __pred, 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert sequential_tag()), __begin2); 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif /* _GLIBCXX_PARALLEL_FIND_SELECTORS_H */ 198