include/oned/greedy_bisect_impl.hpp

Go to the documentation of this file.

// This file is part of SPart, Spatially Located Workload Partitioner.

// Copyright (C) 2011, The Ohio State University
// SPart developed by Erdeniz O. Bas, Erik Saule and Umit V. Catalyurek 

// For questions, comments, suggestions, bugs please send e-mail to: 
// Umit V. Catalyurek   catalyurek.1@osu.edu

// SPart 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 2 or (at your option) any later
// version.

// SPart 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 SPart; if not, write to the Free Software Foundation, Inc.,
// 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

// As a special exception, if other files instantiate templates or use
// macros or inline functions from this file, or you compile this file
// and link it with other works to produce a work based on this file,
// this file does not by itself cause the resulting work to be covered by
// the GNU General Public License. However the source code for this file
// must still be made available in accordance with section (3) of the GNU
// General Public License.

// This exception does not invalidate any other reasons why a work based
// on this file might be covered by the GNU General Public License.

// The full text of the GPL license version 2 is available in "gpl.txt".

#include <oned/greedy_bisect.hpp>

template <typename T, typename Pr>
T oned::GreedyBisection<T,Pr>::greedy_bisection(int procCount,
                                          const Pr& prefixSumArray,
                                          int length, int *cutIndexes,
                                          T )
{
  T v = greedy_bisect_internal(procCount, prefixSumArray, length, cutIndexes);
  return v;
}


template <typename T, typename Pr>
T oned::GreedyBisection<T,Pr>::greedy_bisect_internal(int procCount, 
                                                const Pr& prefixSumArray,
                                                int length, int *cutIndexes)
{
  std::priority_queue<HeapElement, std::vector<HeapElement>,
    HeapElementCompare> heap;

  HeapElement model;
  int hsize = 1;
  T bottleneck = -1;

  model.weight = prefixSumArray[length - 1];
  model.low = 1;
  model.high = length - 1;

  heap.push(model);

  while(hsize != procCount)
    {
      int cutPoint=0;
     
      HeapElement out = heap.top();
      heap.pop();


      assert (out.low > 0);
      assert (out.high <= length - 1);

      cutPoint = RecursiveBisection<T,Pr>::findEvenCut(prefixSumArray, out.low, out.high, 1, 1);
      assert (cutPoint >= out.low);
      assert (cutPoint <= out.high);

      model.weight = prefixSumArray[cutPoint] - prefixSumArray[out.low-1];
      model.low = out.low;
      model.high = cutPoint;


      heap.push(model);

      out.weight = prefixSumArray[out.high] - prefixSumArray[cutPoint];
      out.low = cutPoint + 1;
      //out.high = out.high;
      heap.push(out);

      hsize++;
    }

  {
    int i = 0;
    int remove=0;

    while (!heap.empty())
      {
        HeapElement out;

        out=heap.top();
        heap.pop();

        assert (out.high <= length-1);
        assert (out.high >= 0);
        assert (out.low <= length-1);
        assert (out.low >= 0);
        assert (out.low <= out.high);

        if(out.weight > bottleneck)
          bottleneck = out.weight;
        if (!remove && out.high == length-1)
          {
            remove = 1;
          }
        else
          {
            cutIndexes[i] = out.high;
            i++;
          }
      }
  }

  std::sort(cutIndexes, cutIndexes+procCount-1);

 
  return bottleneck;
}