1 /* Bit_Row 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_Bit_Row_defs_hh 25 #define PPL_Bit_Row_defs_hh 1 26 27 #include "Bit_Row_types.hh" 28 #include "globals_types.hh" 29 #include <iosfwd> 30 #include <gmpxx.h> 31 #include <vector> 32 33 namespace Parma_Polyhedra_Library { 34 35 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 36 //! Swaps \p x with \p y. 37 /*! \relates Bit_Row */ 38 void swap(Bit_Row& x, Bit_Row& y); 39 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 40 41 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 42 //! Swaps objects referred by \p x and \p y. 43 /*! \relates Bit_Row */ 44 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 45 void 46 iter_swap(std::vector<Bit_Row>::iterator x, 47 std::vector<Bit_Row>::iterator y); 48 49 // Put them in the namespace here to declare them friends later. 50 51 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 52 //! Returns <CODE>true</CODE> if and only if \p x and \p y are equal. 53 /*! \relates Bit_Row */ 54 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 55 bool operator==(const Bit_Row& x, const Bit_Row& y); 56 57 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 58 //! Returns <CODE>true</CODE> if and only if \p x and \p y are not equal. 59 /*! \relates Bit_Row */ 60 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 61 bool operator!=(const Bit_Row& x, const Bit_Row& y); 62 63 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 64 //! The basic comparison function. 65 /*! \relates Bit_Row 66 Compares \p x with \p y starting from the least significant bits. 67 The ordering is total and has the following property: if \p x and \p y 68 are two rows seen as sets of naturals, if \p x is a strict subset 69 of \p y, then \p x comes before \p y. 70 71 Returns 72 - -1 if \p x comes before \p y in the ordering; 73 - 0 if \p x and \p y are equal; 74 - 1 if \p x comes after \p y in the ordering. 75 */ 76 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 77 int compare(const Bit_Row& x, const Bit_Row& y); 78 79 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 80 //! Set-theoretic inclusion test. 81 /*! \relates Bit_Row */ 82 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 83 bool subset_or_equal(const Bit_Row& x, const Bit_Row& y); 84 85 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 86 /*! \brief 87 Set-theoretic inclusion test: sets \p strict_subset to a Boolean 88 indicating whether the inclusion is strict or not. 89 90 \relates Bit_Row 91 */ 92 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 93 bool subset_or_equal(const Bit_Row& x, const Bit_Row& y, 94 bool& strict_subset); 95 96 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 97 //! Set-theoretic strict inclusion test. 98 /*! \relates Bit_Row */ 99 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 100 bool strict_subset(const Bit_Row& x, const Bit_Row& y); 101 102 } // namespace Parma_Polyhedra_Library 103 104 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 105 //! A row in a matrix of bits. 106 /*! \ingroup PPL_CXX_interface */ 107 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 108 class Parma_Polyhedra_Library::Bit_Row { 109 public: 110 //! Default constructor. 111 Bit_Row(); 112 113 //! Copy constructor. 114 Bit_Row(const Bit_Row& y); 115 116 //! Set-union constructor. 117 /*! 118 Constructs an object containing the set-union of \p y and \p z. 119 */ 120 Bit_Row(const Bit_Row& y, const Bit_Row& z); 121 122 //! Destructor. 123 ~Bit_Row(); 124 125 //! Assignment operator. 126 Bit_Row& operator=(const Bit_Row& y); 127 128 //! Swaps \p *this with \p y. 129 void m_swap(Bit_Row& y); 130 131 //! Returns the truth value corresponding to the bit in position \p k. 132 bool operator[](unsigned long k) const; 133 134 //! Sets the bit in position \p k. 135 void set(unsigned long k); 136 137 //! Sets bits up to position \p k (excluded). 138 void set_until(unsigned long k); 139 140 //! Clears the bit in position \p k. 141 void clear(unsigned long k); 142 143 //! Clears bits from position \p k (included) onward. 144 void clear_from(unsigned long k); 145 146 //! Clears all the bits of the row. 147 void clear(); 148 149 //! Assigns to \p *this the set-theoretic union of \p x and \p y. 150 void union_assign(const Bit_Row& x, const Bit_Row& y); 151 152 //! Assigns to \p *this the set-theoretic intersection of \p x and \p y. 153 void intersection_assign(const Bit_Row& x, const Bit_Row& y); 154 155 //! Assigns to \p *this the set-theoretic difference of \p x and \p y. 156 void difference_assign(const Bit_Row& x, const Bit_Row& y); 157 158 159 friend int compare(const Bit_Row& x, const Bit_Row& y); 160 friend bool operator==(const Bit_Row& x, const Bit_Row& y); 161 friend bool operator!=(const Bit_Row& x, const Bit_Row& y); 162 friend bool subset_or_equal(const Bit_Row& x, const Bit_Row& y); 163 friend bool subset_or_equal(const Bit_Row& x, const Bit_Row& y, 164 bool& strict_subset); 165 friend bool strict_subset(const Bit_Row& x, const Bit_Row& y); 166 167 //! Returns the index of the first set bit or ULONG_MAX if no bit is set. 168 unsigned long first() const; 169 170 /*! \brief 171 Returns the index of the first set bit after \p position 172 or ULONG_MAX if no bit after \p position is set. 173 */ 174 unsigned long next(unsigned long position) const; 175 176 //! Returns the index of the last set bit or ULONG_MAX if no bit is set. 177 unsigned long last() const; 178 179 /*! \brief 180 Returns the index of the first set bit before \p position 181 or ULONG_MAX if no bits before \p position is set. 182 */ 183 unsigned long prev(unsigned long position) const; 184 185 //! Returns the number of set bits in the row. 186 unsigned long count_ones() const; 187 188 //! Returns <CODE>true</CODE> if no bit is set in the row. 189 bool empty() const; 190 191 //! Returns the total size in bytes of the memory occupied by \p *this. 192 memory_size_type total_memory_in_bytes() const; 193 194 //! Returns the size in bytes of the memory managed by \p *this. 195 memory_size_type external_memory_in_bytes() const; 196 197 //! Checks if all the invariants are satisfied 198 bool OK() const; 199 200 private: 201 //! Bit-vector representing the row. 202 mpz_t vec; 203 204 //! Assigns to \p *this the union of \p y and \p z. 205 /*! 206 The size of \p y must be be less than or equal to the size of \p z. 207 Upon entry, \p vec must have allocated enough space to contain the result. 208 */ 209 void union_helper(const Bit_Row& y, const Bit_Row& z); 210 }; 211 212 #include "Bit_Row_inlines.hh" 213 214 #endif // !defined(PPL_Bit_Row_defs_hh) 215