list_partition.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/list_partition.h
00032  *  @brief Functionality to split sequence referenced by only input
00033  *  iterators.
00034  *  This file is a GNU parallel extension to the Standard C++ Library.
00035  */
00036 
00037 // Written by Leonor Frias Moya and Johannes Singler.
00038 
00039 #ifndef _GLIBCXX_PARALLEL_LIST_PARTITION_H
00040 #define _GLIBCXX_PARALLEL_LIST_PARTITION_H 1
00041 
00042 #include <parallel/parallel.h>
00043 #include <vector>
00044 
00045 namespace __gnu_parallel
00046 {
00047   /** @brief Shrinks and doubles the ranges.
00048    *  @param os_starts Start positions worked on (oversampled).
00049    *  @param count_to_two Counts up to 2.
00050    *  @param range_length Current length of a chunk.
00051    *  @param make_twice Whether the @c os_starts is allowed to be
00052    *  grown or not
00053    */
00054   template<typename InputIterator>
00055     void
00056     shrink_and_double(std::vector<InputIterator>& os_starts,
00057               size_t& count_to_two, size_t& range_length,
00058               const bool make_twice)
00059     {
00060       ++count_to_two;
00061       if (not make_twice or count_to_two < 2)
00062     shrink(os_starts, count_to_two, range_length);
00063       else
00064     {
00065       os_starts.resize((os_starts.size() - 1) * 2 + 1);
00066       count_to_two = 0;
00067     }
00068     }
00069 
00070   /** @brief Combines two ranges into one and thus halves the number of ranges.
00071    *  @param os_starts Start positions worked on (oversampled).
00072    *  @param count_to_two Counts up to 2.
00073    *  @param range_length Current length of a chunk. */
00074   template<typename InputIterator>
00075     void
00076     shrink(std::vector<InputIterator>& os_starts, size_t& count_to_two,
00077        size_t& range_length)
00078     {
00079       for (typename std::vector<InputIterator>::size_type i = 0;
00080        i <= (os_starts.size() / 2); ++i)
00081     os_starts[i] = os_starts[i * 2];
00082       range_length *= 2;
00083     }
00084 
00085   /** @brief Splits a sequence given by input iterators into parts of
00086    * almost equal size
00087    *
00088    *  The function needs only one pass over the sequence.
00089    *  @param begin Begin iterator of input sequence.
00090    *  @param end End iterator of input sequence.
00091    *  @param starts Start iterators for the resulting parts, dimension
00092    *  @c num_parts+1. For convenience, @c starts @c [num_parts]
00093    *  contains the end iterator of the sequence.
00094    *  @param lengths Length of the resulting parts.
00095    *  @param num_parts Number of parts to split the sequence into.
00096    *  @param f Functor to be applied to each element by traversing it
00097    *  @param oversampling Oversampling factor. If 0, then the
00098    *  partitions will differ in at most @f$ \sqrt{\mathrm{end} -
00099    *  \mathrm{begin}} @f$ elements. Otherwise, the ratio between the
00100    *  longest and the shortest part is bounded by @f$
00101    *  1/(\mathrm{oversampling} \cdot \mathrm{num\_parts}) @f$.
00102    *  @return Length of the whole sequence.
00103    */
00104   template<typename InputIterator, typename FunctorType>
00105     size_t
00106     list_partition(const InputIterator begin, const InputIterator end,
00107            InputIterator* starts, size_t* lengths, const int num_parts,
00108            FunctorType& f, int oversampling = 0)
00109     {
00110       bool make_twice = false;
00111 
00112       // The resizing algorithm is chosen according to the oversampling factor.
00113       if (oversampling == 0)
00114     {
00115       make_twice = true;
00116       oversampling = 1;
00117     }
00118 
00119       std::vector<InputIterator> os_starts(2 * oversampling * num_parts + 1);
00120 
00121       os_starts[0]= begin;
00122       InputIterator prev = begin, it = begin;
00123       size_t dist_limit = 0, dist = 0;
00124       size_t cur = 1, next = 1;
00125       size_t range_length = 1;
00126       size_t count_to_two = 0;
00127       while (it != end)
00128     {
00129       cur = next;
00130       for (; cur < os_starts.size() and it != end; ++cur)
00131         {
00132           for (dist_limit += range_length;
00133            dist < dist_limit and it != end; ++dist)
00134         {
00135           f(it);
00136           ++it;
00137         }
00138           os_starts[cur] = it;
00139         }
00140 
00141       // Must compare for end and not cur < os_starts.size() , because
00142       // cur could be == os_starts.size() as well
00143       if (it == end)
00144         break;
00145 
00146       shrink_and_double(os_starts, count_to_two, range_length, make_twice);
00147       next = os_starts.size() / 2 + 1;
00148     }
00149 
00150       // Calculation of the parts (one must be extracted from current
00151       // because the partition beginning at end, consists only of
00152       // itself).
00153       size_t size_part = (cur - 1) / num_parts;
00154       int size_greater = static_cast<int>((cur - 1) % num_parts);
00155       starts[0] = os_starts[0];
00156 
00157       size_t index = 0;
00158 
00159       // Smallest partitions.
00160       for (int i = 1; i < (num_parts + 1 - size_greater); ++i)
00161     {
00162       lengths[i - 1] =  size_part * range_length;
00163       index += size_part;
00164       starts[i] = os_starts[index];
00165     }
00166 
00167       // Biggest partitions.
00168       for (int i = num_parts + 1 - size_greater; i <= num_parts; ++i)
00169     {
00170       lengths[i - 1] =  (size_part+1) * range_length;
00171       index += (size_part+1);
00172       starts[i] = os_starts[index];
00173     }
00174 
00175       // Correction of the end size (the end iteration has not finished).
00176       lengths[num_parts - 1] -= (dist_limit - dist);
00177 
00178       return dist;
00179     }
00180 }
00181 
00182 #endif

Generated on Sat Dec 12 09:40:11 2009 for libstdc++ by  doxygen 1.5.6