1 /* DB_Matrix class declaration. 2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it> 3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com) 4 5 This file is part of the Parma Polyhedra Library (PPL). 6 7 The PPL is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by the 9 Free Software Foundation; either version 3 of the License, or (at your 10 option) any later version. 11 12 The PPL is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with this program; if not, write to the Free Software Foundation, 19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA. 20 21 For the most up-to-date information see the Parma Polyhedra Library 22 site: http://bugseng.com/products/ppl/ . */ 23 24 #ifndef PPL_DB_Matrix_defs_hh 25 #define PPL_DB_Matrix_defs_hh 1 26 27 #include "DB_Matrix_types.hh" 28 #include "globals_defs.hh" 29 #include "DB_Row_defs.hh" 30 #include "Checked_Number_types.hh" 31 #include "Rounding_Dir_defs.hh" 32 #include <vector> 33 #include <cstddef> 34 #include <iosfwd> 35 36 namespace Parma_Polyhedra_Library { 37 38 namespace IO_Operators { 39 40 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 41 //! Output operator. 42 /*! \relates Parma_Polyhedra_Library::DB_Matrix */ 43 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 44 template <typename T> 45 std::ostream& 46 operator<<(std::ostream& s, const DB_Matrix<T>& c); 47 48 } // namespace IO_Operators 49 50 } // namespace Parma_Polyhedra_Library 51 52 53 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 54 //! The base class for the square matrices. 55 /*! \ingroup PPL_CXX_interface 56 The template class DB_Matrix<T> allows for the representation of 57 a square matrix of T objects. 58 Each DB_Matrix<T> object can be viewed as a multiset of DB_Row<T>. 59 */ 60 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 61 template <typename T> 62 class Parma_Polyhedra_Library::DB_Matrix { 63 public: 64 //! Returns the maximum number of rows a DB_Matrix can handle. 65 static dimension_type max_num_rows(); 66 67 //! Returns the maximum number of columns a DB_Matrix can handle. 68 static dimension_type max_num_columns(); 69 70 //! Builds an empty matrix. 71 /*! 72 DB_Rows' size and capacity are initialized to \f$0\f$. 73 */ 74 DB_Matrix(); 75 76 //! Builds a square matrix having the specified dimension. 77 explicit DB_Matrix(dimension_type n_rows); 78 79 //! Copy constructor. 80 DB_Matrix(const DB_Matrix& y); 81 82 //! Constructs a conservative approximation of \p y. 83 template <typename U> 84 explicit DB_Matrix(const DB_Matrix<U>& y); 85 86 //! Destructor. 87 ~DB_Matrix(); 88 89 //! Assignment operator. 90 DB_Matrix& operator=(const DB_Matrix& y); 91 92 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 93 //! A read-only iterator over the rows of the matrix. 94 /*! \ingroup PPL_CXX_interface */ 95 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 96 class const_iterator { 97 private: 98 typedef typename std::vector<DB_Row<T> >::const_iterator Iter; 99 //! The const iterator on the rows' vector \p rows. 100 Iter i; 101 102 public: 103 typedef std::forward_iterator_tag iterator_category; 104 typedef typename std::iterator_traits<Iter>::value_type value_type; 105 typedef typename std::iterator_traits<Iter>::difference_type 106 difference_type; 107 typedef typename std::iterator_traits<Iter>::pointer pointer; 108 typedef typename std::iterator_traits<Iter>::reference reference; 109 110 //! Default constructor. 111 const_iterator(); 112 113 /*! \brief 114 Builds a const iterator on the matrix starting from 115 an iterator \p b on the elements of the vector \p rows. 116 */ 117 explicit const_iterator(const Iter& b); 118 119 //! Ordinary copy constructor. 120 const_iterator(const const_iterator& y); 121 122 //! Assignment operator. 123 const_iterator& operator=(const const_iterator& y); 124 125 //! Dereference operator. 126 reference operator*() const; 127 128 //! Indirect member selector. 129 pointer operator->() const; 130 131 //! Prefix increment operator. 132 const_iterator& operator++(); 133 134 //! Postfix increment operator. 135 const_iterator operator++(int); 136 137 /*! \brief 138 Returns <CODE>true</CODE> if and only if 139 \p *this and \p y are identical. 140 */ 141 bool operator==(const const_iterator& y) const; 142 143 /*! \brief 144 Returns <CODE>true</CODE> if and only if 145 \p *this and \p y are different. 146 */ 147 bool operator!=(const const_iterator& y) const; 148 }; 149 150 /*! \brief 151 Returns the const_iterator pointing to the first row, 152 if \p *this is not empty; 153 otherwise, returns the past-the-end const_iterator. 154 */ 155 const_iterator begin() const; 156 157 //! Returns the past-the-end const_iterator. 158 const_iterator end() const; 159 160 private: 161 template <typename U> friend class DB_Matrix; 162 163 //! The rows of the matrix. 164 std::vector<DB_Row<T> > rows; 165 166 //! Size of the initialized part of each row. 167 dimension_type row_size; 168 169 /*! \brief 170 Capacity allocated for each row, i.e., number of 171 <CODE>long</CODE> objects that each row can contain. 172 */ 173 dimension_type row_capacity; 174 175 public: 176 //! Swaps \p *this with \p y. 177 void m_swap(DB_Matrix& y); 178 179 //! Makes the matrix grow by adding more rows and more columns. 180 /*! 181 \param new_n_rows 182 The number of rows and columns of the resized matrix. 183 184 A new matrix, with the specified dimension, is created. 185 The contents of the old matrix are copied in the upper, left-hand 186 corner of the new matrix, which is then assigned to \p *this. 187 */ 188 void grow(dimension_type new_n_rows); 189 190 //! Resizes the matrix without worrying about the old contents. 191 /*! 192 \param new_n_rows 193 The number of rows and columns of the resized matrix. 194 195 A new matrix, with the specified dimension, is created without copying 196 the content of the old matrix and assigned to \p *this. 197 */ 198 void resize_no_copy(dimension_type new_n_rows); 199 200 //! Returns the number of rows in the matrix. 201 dimension_type num_rows() const; 202 203 //! \name Subscript operators. 204 //@{ 205 //! Returns a reference to the \p k-th row of the matrix. 206 DB_Row<T>& operator[](dimension_type k); 207 208 //! Returns a constant reference to the \p k-th row of the matrix. 209 const DB_Row<T>& operator[](dimension_type k) const; 210 //@} 211 212 PPL_OUTPUT_DECLARATIONS 213 214 /*! \brief 215 Loads from \p s an ASCII representation (as produced by 216 ascii_dump(std::ostream&) const) and sets \p *this accordingly. 217 Returns <CODE>true</CODE> if successful, <CODE>false</CODE> otherwise. 218 */ 219 bool ascii_load(std::istream& s); 220 221 //! Returns the total size in bytes of the memory occupied by \p *this. 222 memory_size_type total_memory_in_bytes() const; 223 224 //! Returns the size in bytes of the memory managed by \p *this. 225 memory_size_type external_memory_in_bytes() const; 226 227 //! Checks if all the invariants are satisfied. 228 bool OK() const; 229 }; 230 231 namespace Parma_Polyhedra_Library { 232 233 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 234 //! Swaps \p x with \p y. 235 /*! \relates DB_Matrix */ 236 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 237 template <typename T> 238 void swap(DB_Matrix<T>& x, DB_Matrix<T>& y); 239 240 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 241 //! Returns <CODE>true</CODE> if and only if \p x and \p y are identical. 242 /*! \relates DB_Matrix */ 243 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 244 template <typename T> 245 bool operator==(const DB_Matrix<T>& x, const DB_Matrix<T>& y); 246 247 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 248 //! Returns <CODE>true</CODE> if and only if \p x and \p y are different. 249 /*! \relates DB_Matrix */ 250 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 251 template <typename T> 252 bool operator!=(const DB_Matrix<T>& x, const DB_Matrix<T>& y); 253 254 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 255 //! Computes the rectilinear (or Manhattan) distance between \p x and \p y. 256 /*! \relates DB_Matrix 257 If the rectilinear distance between \p x and \p y is defined, 258 stores an approximation of it into to \p r 259 and returns <CODE>true</CODE>; returns <CODE>false</CODE> otherwise. 260 261 The direction of the approximation is specified by \p dir. 262 263 All computations are performed using the temporary variables 264 \p tmp0, \p tmp1 and \p tmp2. 265 */ 266 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 267 template <typename Temp, typename To, typename T> 268 bool rectilinear_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 269 const DB_Matrix<T>& x, 270 const DB_Matrix<T>& y, 271 Rounding_Dir dir, 272 Temp& tmp0, 273 Temp& tmp1, 274 Temp& tmp2); 275 276 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 277 //! Computes the euclidean distance between \p x and \p y. 278 /*! \relates DB_Matrix 279 If the Euclidean distance between \p x and \p y is defined, 280 stores an approximation of it into to \p r 281 and returns <CODE>true</CODE>; returns <CODE>false</CODE> otherwise. 282 283 The direction of the approximation is specified by \p dir. 284 285 All computations are performed using the temporary variables 286 \p tmp0, \p tmp1 and \p tmp2. 287 */ 288 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 289 template <typename Temp, typename To, typename T> 290 bool euclidean_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 291 const DB_Matrix<T>& x, 292 const DB_Matrix<T>& y, 293 Rounding_Dir dir, 294 Temp& tmp0, 295 Temp& tmp1, 296 Temp& tmp2); 297 298 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 299 //! Computes the \f$L_\infty\f$ distance between \p x and \p y. 300 /*! \relates DB_Matrix 301 If the \f$L_\infty\f$ distance between \p x and \p y is defined, 302 stores an approximation of it into to \p r 303 and returns <CODE>true</CODE>; returns <CODE>false</CODE> otherwise. 304 305 The direction of the approximation is specified by \p dir. 306 307 All computations are performed using the temporary variables 308 \p tmp0, \p tmp1 and \p tmp2. 309 */ 310 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 311 template <typename Temp, typename To, typename T> 312 bool l_infinity_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 313 const DB_Matrix<T>& x, 314 const DB_Matrix<T>& y, 315 Rounding_Dir dir, 316 Temp& tmp0, 317 Temp& tmp1, 318 Temp& tmp2); 319 320 } // namespace Parma_Polyhedra_Library 321 322 #include "DB_Matrix_inlines.hh" 323 #include "DB_Matrix_templates.hh" 324 325 #endif // !defined(PPL_DB_Matrix_defs_hh) 326