include/util/rect_list_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 "rect_list.hpp"

util::rectangle::rectangle()
{
}

util::rectangle::rectangle(int xl, int xh, int yl, int yh)
  :x_top_l(xl), y_top_l(yl), x_bot_r(xh),y_bot_r(yh)
{}
bool util::rectangle::empty() const
{
  return (x_bot_r < x_top_l || y_bot_r < y_top_l);
}

template<typename Pr>
bool util::rectangle::valid_bound( const Pr & prefixSum) const
{
  if(x_top_l <= 0 ||
     y_top_l <= 0 ||
     x_bot_r >= prefixSum.prefixsizeX() ||
     y_bot_r >= prefixSum.prefixsizeY())
    return false;
  else
    return true;
}

template <typename T, typename Pr>
T util::rectangle::get_load(const Pr& prefixSum) const
{             
  if(empty())
    return 0;
  else
    return prefixSum[x_bot_r][y_bot_r] + prefixSum[x_top_l - 1][y_top_l - 1]
      - prefixSum[x_bot_r][y_top_l-1] - prefixSum[x_top_l-1][y_bot_r];
}

int util::rectangle::get_area() const
{
  return (x_bot_r - x_top_l + 1) * (y_bot_r - y_top_l + 1);
}

std::ostream& util::operator<< (std::ostream& out, const rectangle& r)
{
  out<<"("<<r.x_top_l<<" "<<r.y_top_l<<" "<<r.x_bot_r<<" "<<r.y_bot_r<<")";
  return out;
}


template <typename T, typename Pr>
util::RectList<T,Pr>::RectList(const Pr &ps)
  :prefixSum(ps)
{}

template <typename T, typename Pr>
util::RectList<T,Pr>::RectList(const RectList &rlist)
  :prefixSum(rlist.prefixSum)
{
  copy_into (rlist);
}

template <typename T, typename Pr>
void util::RectList<T,Pr>::add_rect(const rectangle& r)
{  
  if(r.empty())
    return;
  else
    rectangles.push_back(r);
}

template <typename T, typename Pr>
void util::RectList<T,Pr>::copy_into(const  RectList &rlist)
{
  assert (&(prefixSum) == &(rlist.prefixSum));
  
  rectangles.clear();
  
  for (container::const_iterator list_iter1 = rlist.rectangles.begin();
       list_iter1 != rlist.rectangles.end(); list_iter1++)
    add_rect(*list_iter1);
}

template <typename T, typename Pr>
void util::RectList<T,Pr>::add_into(const  RectList &rlist)
{
  assert (&(prefixSum) == &(rlist.prefixSum));
  
  for (container::const_iterator list_iter1 = rlist.rectangles.begin();
       list_iter1 != rlist.rectangles.end(); list_iter1++)
    add_rect(*list_iter1);
}

template <typename T, typename Pr>
void util::RectList<T,Pr>::clear()
{
  rectangles.clear();
}

template <typename T, typename Pr>
T util::RectList<T,Pr>::get_maximum_load() const
{
  assert (valid_part());
  
  T maximum = 0;
  for (container::const_iterator list_iter1 = rectangles.begin();
       list_iter1 != rectangles.end(); list_iter1++)
    maximum = std::max (maximum, list_iter1->get_load<T,Pr> (prefixSum));
  return maximum;
}

template <typename T, typename Pr>
T util::RectList<T,Pr>::get_minimum_load() const
{
  assert (valid_part());
  
  T minimum = prefixSum[prefixSum.prefixsizeX()-1][prefixSum.prefixsizeY()-1];
  for (container::const_iterator list_iter1 = rectangles.begin();
       list_iter1 != rectangles.end(); list_iter1++)
    minimum = std::min (minimum, list_iter1->get_load<T,Pr> (prefixSum));
  return minimum;
} 

template <typename T, typename Pr>
bool util::RectList<T,Pr>::valid_part() const
{
  const bool DEBUG = false;

  //checking that all the rectanlges are valid:
  {
    container::const_iterator list_iter1;
    for (list_iter1 = rectangles.begin(); list_iter1 != rectangles.end(); list_iter1++)
      {
        const rectangle& r = *list_iter1;
        //Check the boundaries are not out of matrix
        if(!r.valid_bound<Pr>(prefixSum))
          {
            if (DEBUG)
              std::cerr<<"bounds of "<<r<<" are wrong"<<std::endl;
            return false;
          }
      }
  }

  //check overlaping
  {
    container::const_iterator list_iter1;
    container::const_iterator list_iter2;

    for (list_iter1 = rectangles.begin(); list_iter1 != rectangles.end(); list_iter1++)
      {
        const rectangle& r1 = *list_iter1;
        for (list_iter2 = rectangles.begin(); list_iter2 != rectangles.end(); list_iter2++)
          {
            const rectangle& r2 = *list_iter2;
            if (list_iter2 == list_iter1)
              continue;

            //Check if any two rectangle overlaps
            if((r1.y_top_l <= r2.y_top_l) && (r2.y_top_l <= r1.y_bot_r) &&
               (r1.x_top_l <= r2.x_top_l) && (r2.x_top_l <= r1.x_bot_r))
              {
                if (DEBUG)
                  std::cerr<<r1<<" and "<<r2<<" overlap"<<std::endl;
                return false;
              }
            //Check if any rectangle resides in another one completely
            if((r1.x_top_l <= r2.x_top_l) &&
               (r2.x_top_l <= r1.x_bot_r) &&
               (r1.x_top_l <= r2.x_bot_r) &&
               (r2.x_bot_r <= r1.x_bot_r) &&
               (r1.y_top_l <= r2.y_top_l) &&
               (r2.y_top_l <= r1.y_bot_r) &&
               (r1.y_top_l <= r2.y_bot_r) &&
               (r2.y_bot_r <= r1.y_bot_r))
              {
                if (DEBUG)
                  std::cerr<<r1<<" is inside "<<r2<<" (or the contrary)"<<std::endl;
                return false;
              }
              
          }
      }      
  }
   
  //checking the coverage
  {
    T tot_load = 0;
    int tot_area = 0;
    container::const_iterator list_iter1;
    for (list_iter1 = rectangles.begin(); list_iter1 != rectangles.end(); list_iter1++)
      {
        const rectangle& r = *list_iter1;
        tot_load += r.get_load<T,Pr>(prefixSum);
        tot_area += r.get_area();
      }

    //The total load of all partitions must be equal to total partition load
    int lastX = prefixSum.prefixsizeX() - 1;
    int lastY = prefixSum.prefixsizeY() - 1;
    if((tot_area != (lastX*lastY)))
      {
        if (DEBUG)
          std::cerr<<"The total area is wrong. The sum is "<<tot_area<<" but should be "<<lastX*lastY<<std::endl;
        return false;
      }
  }

  return true;
}

template <typename T, typename Pr>
std::ostream& util::operator<< (std::ostream& out, const util::RectList<T, Pr>& r)
{
  typedef typename util::RectList<T, Pr>::container::const_iterator container_it;
  container_it list_iter1;
  
  for (list_iter1 = r.rectangles.begin(); 
       list_iter1 != r.rectangles.end();
       list_iter1++)
    out<<*list_iter1<<std::endl;
  
  return out;
}