00001 00002 // This file is part of SPart, Spatially Located Workload Partitioner. 00003 00004 // Copyright (C) 2011, The Ohio State University 00005 // SPart developed by Erdeniz O. Bas, Erik Saule and Umit V. Catalyurek 00006 00007 // For questions, comments, suggestions, bugs please send e-mail to: 00008 // Umit V. Catalyurek catalyurek.1@osu.edu 00009 00010 // SPart is free software; you can redistribute it and/or modify it under 00011 // the terms of the GNU General Public License as published by the Free 00012 // Software Foundation; either version 2 or (at your option) any later 00013 // version. 00014 00015 // SPart is distributed in the hope that it will be useful, but WITHOUT 00016 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 00017 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 00018 // for more details. 00019 00020 // You should have received a copy of the GNU General Public License 00021 // along with SPart; if not, write to the Free Software Foundation, Inc., 00022 // 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 00023 00024 // As a special exception, if other files instantiate templates or use 00025 // macros or inline functions from this file, or you compile this file 00026 // and link it with other works to produce a work based on this file, 00027 // this file does not by itself cause the resulting work to be covered by 00028 // the GNU General Public License. However the source code for this file 00029 // must still be made available in accordance with section (3) of the GNU 00030 // General Public License. 00031 00032 // This exception does not invalidate any other reasons why a work based 00033 // on this file might be covered by the GNU General Public License. 00034 00035 // The full text of the GPL license version 2 is available in "gpl.txt". 00036 00047 #ifndef __RECT_LIST_H__ 00048 #define __RECT_LIST_H__ 00049 00050 #include <list> 00051 #include <vector> 00052 #include <iostream> 00053 #include <assert.h> 00054 #include "util/version.hpp" 00055 00056 namespace util 00057 { 00058 00068 struct rectangle 00069 { 00071 int x_top_l; 00073 int y_top_l; 00075 int x_bot_r; 00077 int y_bot_r; 00078 00079 rectangle(); 00080 00081 rectangle(int xl, int xh, int yl, int yh); 00082 00086 bool empty() const; 00087 00094 template<typename Pr> 00095 bool valid_bound( const Pr & prefixSum) const; 00107 template <typename T, typename Pr> 00108 T get_load(const Pr& prefixSum) const; 00109 00115 int get_area() const; 00116 }; 00117 00118 std::ostream& operator<< (std::ostream& out, const rectangle& r); 00119 00126 template <typename T, typename Pr> 00127 class RectList 00128 { 00129 public: 00130 typedef std::vector<rectangle> container; 00131 container rectangles; 00132 const Pr& prefixSum; 00133 00134 RectList(const Pr &ps); 00135 00136 RectList(const RectList &rlist); 00137 00138 00146 void add_rect(const rectangle& r); 00147 00153 void copy_into(const RectList &rlist); 00154 00160 void add_into(const RectList &rlist); 00161 00166 void clear(); 00167 00172 T get_maximum_load() const; 00179 T get_minimum_load() const; 00180 00190 bool valid_part() const; 00191 }; 00192 00193 template <typename T, typename Pr> 00194 std::ostream& operator<< (std::ostream& out, const util::RectList<T, Pr>& r); 00195 } 00196 00197 #include "rect_list_impl.hpp" 00198 #endif