include/oned/rec_bisect_minmax.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".

#ifndef __REC_BISECT_MINMAX_H__
#define __REC_BISECT_MINMAX_H__
#include <util/prefix_sum_tools.hpp>
#include <assert.h>
#include <cstdlib>
#include <util/tools.hpp>
namespace oned
{
template <typename T, typename Pr>
class RecursiveBisectionMinMax
{
  //For debug purpose only
  static int linsrch(const Pr prefixSum, int low, int high, int leftProc, int rightProc);

  static double pointDiff(const Pr prefixSum, int low, int high, int leftProc, int rightProc, int point);
  static int slopeAt(const Pr prefixSum, int low, int high, int leftProc, int rightProc, int point);
  static int bimonsearch(const Pr prefixSum, int low, int high, int leftProc, int rightProc);
  /*Returns the recursive bisection cuts in sorted order in
   *cutPoints. low and high included.*/
  static T rec_bisection_internal(int numProc, int low, int high,
                                  const Pr prefixSum, int *cutPoints);
  

public:
  /*Calculates the abstract weight difference of two partitions which
    are seperated by the index "candidate". candidate remains in the
    left processor. prefixsum[i] is the sum of first i elements in a
    given array. prefixsum[0] = 0. low and high values are included
    while calculating the difference. rightProc is the number of
    processors on the right and leftProc is the number of processors on
    the left*/
  static double calculateDiff(const Pr prefixSum, int low, int high,
                              int leftProc, int rightProc, int candidate);




  static int findEvenCut(const Pr prefixSum, int low, int high,
                         int leftProc, int rightProc);  
  static T rec_bisection(int procCount, const Pr prefixSumArray,
                         int length, int *cutIndexes, T);
};
}
#include <oned/rec_bisect_minmax_impl.hpp>

#endif