merge.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 2, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License
00017 // along with this library; see the file COPYING.  If not, write to
00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
00019 // MA 02111-1307, USA.
00020 
00021 // As a special exception, you may use this file as part of a free
00022 // software library without restriction.  Specifically, if other files
00023 // instantiate templates or use macros or inline functions from this
00024 // file, or you compile this file and link it with other files to
00025 // produce an executable, this file does not by itself cause the
00026 // resulting executable to be covered by the GNU General Public
00027 // License.  This exception does not however invalidate any other
00028 // reasons why the executable file might be covered by the GNU General
00029 // Public License.
00030 
00031 /** @file parallel/merge.h
00032  *  @brief Parallel implementation of std::merge().
00033  *  This file is a GNU parallel extension to the Standard C++ Library.
00034  */
00035 
00036 // Written by Johannes Singler.
00037 
00038 #ifndef _GLIBCXX_PARALLEL_MERGE_H
00039 #define _GLIBCXX_PARALLEL_MERGE_H 1
00040 
00041 #include <parallel/basic_iterator.h>
00042 #include <bits/stl_algo.h>
00043 
00044 namespace __gnu_parallel
00045 {
00046   /** @brief Merge routine being able to merge only the @c max_length
00047    * smallest elements.
00048    *
00049    * The @c begin iterators are advanced accordingly, they might not
00050    * reach @c end, in contrast to the usual variant.
00051    * @param begin1 Begin iterator of first sequence.
00052    * @param end1 End iterator of first sequence.
00053    * @param begin2 Begin iterator of second sequence.
00054    * @param end2 End iterator of second sequence.
00055    * @param target Target begin iterator.
00056    * @param max_length Maximum number of elements to merge.
00057    * @param comp Comparator.
00058    * @return Output end iterator. */
00059   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00060        typename OutputIterator, typename _DifferenceTp,
00061        typename Comparator>
00062     OutputIterator
00063     merge_advance_usual(RandomAccessIterator1& begin1,
00064             RandomAccessIterator1 end1,
00065             RandomAccessIterator2& begin2,
00066             RandomAccessIterator2 end2, OutputIterator target,
00067             _DifferenceTp max_length, Comparator comp)
00068     {
00069       typedef _DifferenceTp difference_type;
00070       while (begin1 != end1 && begin2 != end2 && max_length > 0)
00071     {
00072       // array1[i1] < array0[i0]
00073       if (comp(*begin2, *begin1))
00074         *target++ = *begin2++;
00075       else
00076         *target++ = *begin1++;
00077       --max_length;
00078     }
00079 
00080       if (begin1 != end1)
00081     {
00082       target = std::copy(begin1, begin1 + max_length, target);
00083       begin1 += max_length;
00084     }
00085       else
00086     {
00087       target = std::copy(begin2, begin2 + max_length, target);
00088       begin2 += max_length;
00089     }
00090       return target;
00091     }
00092 
00093   /** @brief Merge routine being able to merge only the @c max_length
00094    * smallest elements.
00095    *
00096    * The @c begin iterators are advanced accordingly, they might not
00097    * reach @c end, in contrast to the usual variant.
00098    * Specially designed code should allow the compiler to generate
00099    * conditional moves instead of branches.
00100    * @param begin1 Begin iterator of first sequence.
00101    * @param end1 End iterator of first sequence.
00102    * @param begin2 Begin iterator of second sequence.
00103    * @param end2 End iterator of second sequence.
00104    * @param target Target begin iterator.
00105    * @param max_length Maximum number of elements to merge.
00106    * @param comp Comparator.
00107    * @return Output end iterator. */
00108   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00109        typename OutputIterator, typename _DifferenceTp,
00110        typename Comparator>
00111     OutputIterator
00112     merge_advance_movc(RandomAccessIterator1& begin1,
00113                RandomAccessIterator1 end1,
00114                RandomAccessIterator2& begin2,
00115                RandomAccessIterator2 end2,
00116                OutputIterator target,
00117                _DifferenceTp max_length, Comparator comp)
00118     {
00119       typedef _DifferenceTp difference_type;
00120       typedef typename std::iterator_traits<RandomAccessIterator1>::value_type
00121     value_type1;
00122       typedef typename std::iterator_traits<RandomAccessIterator2>::value_type
00123     value_type2;
00124 
00125 #if _GLIBCXX_ASSERTIONS
00126       _GLIBCXX_PARALLEL_ASSERT(max_length >= 0);
00127 #endif
00128 
00129       while (begin1 != end1 && begin2 != end2 && max_length > 0)
00130     {
00131       RandomAccessIterator1 next1 = begin1 + 1;
00132       RandomAccessIterator2 next2 = begin2 + 1;
00133       value_type1 element1 = *begin1;
00134       value_type2 element2 = *begin2;
00135 
00136       if (comp(element2, element1))
00137         {
00138           element1 = element2;
00139           begin2 = next2;
00140         }
00141       else
00142         begin1 = next1;
00143 
00144       *target = element1;
00145 
00146       ++target;
00147       --max_length;
00148     }
00149       if (begin1 != end1)
00150     {
00151       target = std::copy(begin1, begin1 + max_length, target);
00152       begin1 += max_length;
00153     }
00154       else
00155     {
00156       target = std::copy(begin2, begin2 + max_length, target);
00157       begin2 += max_length;
00158     }
00159       return target;
00160     }
00161 
00162   /** @brief Merge routine being able to merge only the @c max_length
00163    * smallest elements.
00164    *
00165    *  The @c begin iterators are advanced accordingly, they might not
00166    *  reach @c end, in contrast to the usual variant.
00167    *  Static switch on whether to use the conditional-move variant.
00168    *  @param begin1 Begin iterator of first sequence.
00169    *  @param end1 End iterator of first sequence.
00170    *  @param begin2 Begin iterator of second sequence.
00171    *  @param end2 End iterator of second sequence.
00172    *  @param target Target begin iterator.
00173    *  @param max_length Maximum number of elements to merge.
00174    *  @param comp Comparator.
00175    *  @return Output end iterator. */
00176   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00177        typename OutputIterator, typename _DifferenceTp,
00178        typename Comparator>
00179     inline OutputIterator
00180     merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1,
00181           RandomAccessIterator2& begin2, RandomAccessIterator2 end2,
00182           OutputIterator target, _DifferenceTp max_length,
00183           Comparator comp)
00184     {
00185       _GLIBCXX_CALL(max_length)
00186 
00187       return merge_advance_movc(begin1, end1, begin2, end2, target,
00188                 max_length, comp);
00189     }
00190 
00191   /** @brief Merge routine fallback to sequential in case the
00192       iterators of the two input sequences are of different type.
00193       *  @param begin1 Begin iterator of first sequence.
00194       *  @param end1 End iterator of first sequence.
00195       *  @param begin2 Begin iterator of second sequence.
00196       *  @param end2 End iterator of second sequence.
00197       *  @param target Target begin iterator.
00198       *  @param max_length Maximum number of elements to merge.
00199       *  @param comp Comparator.
00200       *  @return Output end iterator. */
00201   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00202        typename RandomAccessIterator3, typename Comparator>
00203     inline RandomAccessIterator3
00204     parallel_merge_advance(RandomAccessIterator1& begin1,
00205                RandomAccessIterator1 end1,
00206                RandomAccessIterator2& begin2,
00207                // different iterators, parallel implementation
00208                // not available            
00209                RandomAccessIterator2 end2,
00210                RandomAccessIterator3 target, typename
00211                std::iterator_traits<RandomAccessIterator1>::
00212                difference_type max_length, Comparator comp)
00213     { return merge_advance(begin1, end1, begin2, end2, target,
00214                max_length, comp); }
00215 
00216   /** @brief Parallel merge routine being able to merge only the @c
00217    * max_length smallest elements.
00218    *
00219    *  The @c begin iterators are advanced accordingly, they might not
00220    *  reach @c end, in contrast to the usual variant.
00221    *  The functionality is projected onto parallel_multiway_merge.
00222    *  @param begin1 Begin iterator of first sequence.
00223    *  @param end1 End iterator of first sequence.
00224    *  @param begin2 Begin iterator of second sequence.
00225    *  @param end2 End iterator of second sequence.
00226    *  @param target Target begin iterator.
00227    *  @param max_length Maximum number of elements to merge.
00228    *  @param comp Comparator.
00229    *  @return Output end iterator.
00230    */
00231   template<typename RandomAccessIterator1, typename RandomAccessIterator3,
00232        typename Comparator>
00233     inline RandomAccessIterator3
00234     parallel_merge_advance(RandomAccessIterator1& begin1,
00235                RandomAccessIterator1 end1,
00236                RandomAccessIterator1& begin2,
00237                RandomAccessIterator1 end2,
00238                RandomAccessIterator3 target, typename
00239                std::iterator_traits<RandomAccessIterator1>::
00240                difference_type max_length, Comparator comp)
00241     {
00242       typedef typename
00243           std::iterator_traits<RandomAccessIterator1>::value_type value_type;
00244       typedef typename std::iterator_traits<RandomAccessIterator1>::
00245     difference_type difference_type1 /* == difference_type2 */;
00246       typedef typename std::iterator_traits<RandomAccessIterator3>::
00247     difference_type difference_type3;
00248       typedef typename std::pair<RandomAccessIterator1, RandomAccessIterator1>
00249         iterator_pair;
00250 
00251       std::pair<RandomAccessIterator1, RandomAccessIterator1>
00252     seqs[2] = { std::make_pair(begin1, end1),
00253             std::make_pair(begin2, end2) };
00254       RandomAccessIterator3
00255         target_end = parallel_multiway_merge
00256           < /* stable = */ true, /* sentinels = */ false>(
00257             seqs, seqs + 2, target, comp,
00258             multiway_merge_exact_splitting
00259               < /* stable = */ true, iterator_pair*,
00260                 Comparator, difference_type1>,
00261             max_length);
00262 
00263       return target_end;
00264     }
00265 }   //namespace __gnu_parallel
00266 
00267 #endif

Generated on Fri Jan 23 20:12:14 2009 for libstdc++ by  doxygen 1.5.6