include/util/prefix_sum_tools.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 __PREFIX_SUM_TOOLS_H__
#define __PREFIX_SUM_TOOLS_H__

#include "prefix2d.hpp"
#include "rect_list.hpp"
namespace util
{
template <typename T, typename Pr>
int extractXDim(const util::RectList<T,Pr>& currentP, int *cuts, std::vector<int> procs[]);
template <typename T, typename Pr>
int extractXDim(const util::RectList<T,Pr>& currentP, int *cuts);
template<typename T>
void prefixsum(const T *array, T *result, int length);



template <typename T, typename Pr, bool row>
class Aggreg2Dto1D
{
  const Pr& pr;
  const int xlow;
  const int xhigh;
  const int ylow;
  const int yhigh;
  T precomp;

private:
  Aggreg2Dto1D<T,Pr,row>& operator=(const Aggreg2Dto1D<T,Pr,row>& rhs);
  Aggreg2Dto1D();

public:

  Aggreg2Dto1D(const Pr& p, int xl, int xh, int yl, int yh);
  Aggreg2Dto1D(const Aggreg2Dto1D<T,Pr,row>& o);
  const T operator[] (int x) const;
  T interval(int i1, int i2) const;
};




template <typename T, bool>
class Prefix2D;
template <typename T, typename Pr, bool row>
class Aggreg2Dto1D;

template <typename T, typename Pr, bool row>
class AggregMax2Dto1D
{
  int lineCount;
  Aggreg2Dto1D<T,Pr,row> **lineSet;
  
  AggregMax2Dto1D();
  const AggregMax2Dto1D& operator=(const AggregMax2Dto1D& a);

public:
  AggregMax2Dto1D(const AggregMax2Dto1D& a);
  ~AggregMax2Dto1D();
  AggregMax2Dto1D(const Pr& psum, int procY, int *ycuts);
  T interval(int left, int right) const;
  int getLineCount();

};

template <typename T, typename Pr>
int binarySearch(const Pr & prefixSumArray, int low, int high, T prefixSumBottleneck);

template <typename T, typename Pr>
int binarySearch_interval(const Pr& prefixSumArray, int low, int high, T prefixSumBottleneck, int base);

// returns -1 for impossible; or the first i such that prefixSumArray[i]>= prefixSumBottleneck
template <typename T, typename Pr>
int binarySearchLeft(const Pr & prefixSumArray, int low,
                            int high, T prefixSumBottleneck);

}
#include "prefix_sum_tools_impl.hpp"

#endif