include/util/prefix_sum_tools_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 "assert.h"
#include <stdlib.h>
#include "tools.hpp"
#include <iostream>
#include "prefix_sum_tools.hpp"

template <typename T, typename Pr>
int util::extractXDim(const util::RectList<T,Pr>& currentP, int *cuts, std::vector<int> procs[])
{
  using namespace std;
  using namespace util;
  rectangle r;
  //To force initialization inside loop
  int lastCut = -1;
  int i = 0;
  cuts[0]=1;
  
  for (vector<rectangle>::const_iterator list_iter1 = currentP.rectangles.begin();list_iter1 != currentP.rectangles.end(); list_iter1++)
    {
      
      r = *list_iter1;
      if(r.x_bot_r != lastCut)
        {
          lastCut=r.x_bot_r;
          i++;
          cuts[i] = r.x_bot_r;
          procs[i-1].push_back(1);
        }
      procs[i-1].push_back(r.y_bot_r);
    }
  return i;
}
template <typename T, typename Pr>
int util::extractXDim(const util::RectList<T,Pr>& currentP, int *cuts)
{
  using namespace std;
  using namespace util;
  rectangle r;
  //To force initialization inside loop
  int lastCut = -1;
  int i = 0;
  cuts[0]=1;
  
  for (vector<rectangle>::const_iterator list_iter1 = currentP.rectangles.begin();list_iter1 != currentP.rectangles.end(); list_iter1++)
    {
      
      r = *list_iter1;
      if(r.x_bot_r != lastCut)
        {
          lastCut=r.x_bot_r;
          i++;
          cuts[i] = r.x_bot_r;
        }
    }
  return i;
}
template <typename T, typename Pr>
int util::binarySearch (const Pr& prefixSumArray, int l, int h, T prefixSumBottleneck)
{
  int mid, oldMid = -1;

  assert (l <= h);
  //  assert (prefixSumArray != NULL);

  int low=l;
  int high=h;

  if (prefixSumBottleneck < prefixSumArray[low]) return -1;

  while (low <= high)
    {
      mid = (low + high) / 2;
      assert (low <= high);
      assert (mid >= 0);
      assert (mid <= high);
      if (prefixSumArray[mid] > prefixSumBottleneck)
        {
          high = mid - 1;
        }
      else if (prefixSumArray[mid] < prefixSumBottleneck)
        {
          oldMid = mid;
          low = mid + 1;
        }
      else
        {
          low = mid + 1;
          oldMid = mid;
        }
    }

  assert (prefixSumArray[oldMid] <= prefixSumBottleneck);
  assert (oldMid == h || prefixSumArray[oldMid+1] > prefixSumBottleneck);

  return oldMid;
}



template <typename T, typename Pr>
int util::binarySearch_interval (const Pr& prefixSumArray, int l, int h, T prefixSumBottleneck, int base)
{
  int mid, oldMid = -1;

  int high=h;
  int low = l;

  assert (low <= high);
  //  assert (prefixSumArray != NULL);

  if (prefixSumBottleneck < prefixSumArray.interval(base,low)) return -1;

  while (low <= high)
    {
      mid = (low + high) / 2;
      assert (low <= high);
      assert (mid >= 0);
      assert (mid <= high);
      if (prefixSumArray.interval(base,mid) > prefixSumBottleneck)
        {
          high = mid - 1;
        }
      else if (prefixSumArray.interval(base,mid) < prefixSumBottleneck)
        {
          oldMid = mid;
          low = mid + 1;
        }
      else
        {
          low = mid + 1;
          oldMid = mid;
        }
    }

  assert (prefixSumArray.interval(base, oldMid) <= prefixSumBottleneck);
  assert (oldMid == h || prefixSumArray.interval(base, oldMid+1) > prefixSumBottleneck);


  return oldMid;
}


//result[i] = \sum_{i' < i} array[i']
//For array[0:length-1]. Therefore result[0:length]
template <typename T>
void util::prefixsum(const T *array, T *result, int length)
{
  int i;

  assert (array != NULL);
  assert (result != NULL);
  assert (length >= 0);

  result[0] = 0;
  for(i = 1; i < length + 1; i++)
    result[i] = result[i - 1] + array[i - 1];
}


//look for the first index of value greater or equal than/to prefixsumbottleneck in [low:high]
template <typename T, typename Pr>
int util::binarySearchLeft(const Pr& prefixSumArray, int low, int high, T prefixSumBottleneck)
{
  int mid, oldMid = high;
  assert (low <= high);
  //  assert (prefixSumArray != NULL);

  while (low < high)
    {
      mid = (low + high) / 2;
      assert (low <= high);
      assert (mid >= 0);
      assert (mid <= high);
      if (prefixSumArray[mid] > prefixSumBottleneck)
        {
          oldMid = mid;
          high = mid ;
        }
      else if (prefixSumArray[mid] < prefixSumBottleneck)
        {
          low = mid + 1;
        }
      else
        return mid;
    }
  assert (low == high);
  return oldMid;
}




template <typename T, typename Pr, bool row>
util::Aggreg2Dto1D<T,Pr,row>::Aggreg2Dto1D(const Pr& p, int xl, int xh, int yl, int yh)
  :pr(p),xlow(xl), xhigh(xh), ylow(yl), yhigh(yh)
{
  assert (xl<=xh);
  assert (yl<=yh);
  if (row)
    precomp = pr[xlow-1][ylow-1] - pr[xlow-1][yhigh] ;
  else
    precomp = pr[xlow-1][ylow-1] - pr[xhigh][ylow-1];
  assert(precomp<=0);
}

template <typename T, typename Pr, bool row>
util::Aggreg2Dto1D<T,Pr,row>::Aggreg2Dto1D(const Aggreg2Dto1D<T,Pr,row>& o)
  :pr(o.pr),xlow(o.xlow), xhigh(o.xhigh), ylow(o.ylow), yhigh(o.yhigh), precomp(o.precomp)
{
  assert (xlow<=xhigh);
  assert (ylow<=yhigh);
  
  assert (ylow == o.ylow);
  assert (yhigh == o.yhigh);
}

template <typename T, typename Pr, bool row>
const T util::Aggreg2Dto1D<T,Pr,row>::operator[] (int x) const
{
  if (row)
    {
      assert (x>=0);
      assert (x <= xhigh-xlow+1);
      //All non-negative values
      assert(precomp + pr[x+xlow-1][yhigh] - pr[x+xlow-1][ylow-1]>=0);
      return precomp + pr[x+xlow-1][yhigh] - pr[x+xlow-1][ylow-1];
    }
  else
    {
      int y=x;

      assert (y>= 0);
      assert (y <= yhigh-ylow+1);
      //All non-negative values
      assert(precomp + pr[xhigh][y+ylow-1] - pr[xlow-1][y+ylow-1]>=0);
      return precomp + pr[xhigh][y+ylow-1] - pr[xlow-1][y+ylow-1];
    }
}

template <typename T, typename Pr, bool row>
T util::Aggreg2Dto1D<T,Pr,row>::interval(int i1, int i2) const
{
  return (*this)[i2] - (*this)[i1];
}



template <typename T, typename Pr, bool row>
util::AggregMax2Dto1D<T,Pr,row>::AggregMax2Dto1D(const AggregMax2Dto1D& a)
    :lineCount(a.lineCount), lineSet(new Aggreg2Dto1D<T,Pr,row>*[lineCount])
{
  for (int i=0; i<lineCount; i++)
    {
      if (a.lineSet[i] != NULL)
        lineSet[i] = new Aggreg2Dto1D<T,Pr,row>(*(a.lineSet[i]));
      else
        lineSet[i] = NULL;
    }
}

template <typename T, typename Pr, bool row>
util::AggregMax2Dto1D<T,Pr,row>::~AggregMax2Dto1D()
{
  for (int i=0; i<lineCount; i++)
    if (lineSet[i] != NULL)
      delete lineSet[i];
  delete[] lineSet;
}

template <typename T, typename Pr, bool row>
util::AggregMax2Dto1D<T,Pr,row>::AggregMax2Dto1D(const Pr& psum, int procY, int *ycuts)
  :lineCount(procY), lineSet(new Aggreg2Dto1D<T,Pr,row>*[lineCount])
{
  if (row == true)
    {
      int lastY = 1;
      for(int i = 0;i < procY-1; i++)
        {
          assert (ycuts[i] != 0);
          if (lastY <= ycuts[i])
            lineSet[i] = new Aggreg2Dto1D<T, Pr, row> (psum, 1, psum.prefixsizeX() - 1, lastY, ycuts[i]);
          else
            lineSet[i] = NULL;
          lastY = ycuts[i] + 1;
        }
      if (lastY <= psum.prefixsizeY() - 1)
        lineSet[procY-1] = new Aggreg2Dto1D<T, Pr, row> (psum, 1, psum.prefixsizeX() - 1, lastY, psum.prefixsizeY() - 1);
      else
        lineSet[procY-1] = NULL;
    }
  else //row == false
    {
      int procX = procY;
      int* xcuts = ycuts;
      
      int lastX = 1;
      for(int i = 0;i < procX-1; i++)
        {
          assert (xcuts[i] != 0);
          if (lastX <= xcuts[i])
            lineSet[i] = new Aggreg2Dto1D<T, Pr, row> (psum, lastX, xcuts[i], 1, psum.prefixsizeY() - 1 );
          else
            lineSet[i] = NULL;
          lastX = xcuts[i] + 1;
        }
      if (lastX <= psum.prefixsizeX() - 1)
        lineSet[procX-1] = new Aggreg2Dto1D<T, Pr, row> (psum, lastX, psum.prefixsizeX() - 1, 1, psum.prefixsizeY() - 1);
      else
        lineSet[procX-1] = NULL;
    }
}
template <typename T, typename Pr, bool row>
T util::AggregMax2Dto1D<T,Pr,row>::interval(int left, int right) const
{
  T maxVal;
  int i = 0;
  while (lineSet[i] == NULL)
    {
      assert (i < lineCount);
      i++;
    }
  maxVal = lineSet[i]->interval(left,right);
  
  for(; i < lineCount; i++)
    {
      if (lineSet[i] != NULL)
        maxVal = std::max(lineSet[i]->interval(left,right), maxVal);
    }
  return maxVal;
}
template <typename T, typename Pr, bool row>
int util::AggregMax2Dto1D<T,Pr,row>::getLineCount()
{
  return lineCount;
}