1 //------------------------------------------------------------------------------ 2 // Copyright (c) 2003-2005, Haiku, Inc. 3 // 4 // Permission is hereby granted, free of charge, to any person obtaining a 5 // copy of this software and associated documentation files (the "Software"), 6 // to deal in the Software without restriction, including without limitation 7 // the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 // and/or sell copies of the Software, and to permit persons to whom the 9 // Software is furnished to do so, subject to the following conditions: 10 // 11 // The above copyright notice and this permission notice shall be included in 12 // all copies or substantial portions of the Software. 13 // 14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 19 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 20 // DEALINGS IN THE SOFTWARE. 21 // 22 // File Name: Region.cpp 23 // Author: Stefano Ceccherini (burton666@libero.it) 24 // Description: Region class consisting of multiple rectangles 25 // 26 //------------------------------------------------------------------------------ 27 28 // Notes: As now, memory is always allocated and never freed (except on destruction, 29 // or sometimes when a copy is made). 30 // This let us be a bit faster since we don't do many reallocations. 31 // But that means that even an empty region could "waste" much space, if it contained 32 // many rects before being emptied. 33 // I.E: a region which contains 24 rects allocates more than 24 * 4 * sizeof(int32) 34 // = 96 * sizeof(int32) bytes. If we call MakeEmpty(), that region will contain no rects, 35 // but it will still keep the allocated memory. 36 // This shouldnt' be an issue, since usually BRegions are just used for calculations, 37 // and don't last so long. 38 // Anyway, we can change that behaviour if we want, but BeOS's BRegion seems to behave exactly 39 // like this. 40 41 42 #include <cstdlib> 43 #include <cstring> 44 45 #include <Debug.h> 46 #include <Region.h> 47 48 #include <clipping.h> 49 #include <RegionSupport.h> 50 51 52 const static int32 kInitialDataSize = 8; 53 54 55 /*! \brief Initializes a region. The region will have no rects, 56 and its bound will be invalid. 57 */ 58 BRegion::BRegion() 59 : 60 data_size(0), 61 data(NULL) 62 { 63 data = (clipping_rect *)malloc(kInitialDataSize * sizeof(clipping_rect)); 64 if (data != NULL) 65 data_size = kInitialDataSize; 66 67 Support::ZeroRegion(*this); 68 } 69 70 71 /*! \brief Initializes a region to be a copy of another. 72 \param region The region to copy. 73 */ 74 BRegion::BRegion(const BRegion ®ion) 75 : 76 data_size(0), 77 data(NULL) 78 { 79 const int32 size = region.data_size > 0 ? region.data_size : 1; 80 81 data = (clipping_rect *)malloc(size * sizeof(clipping_rect)); 82 if (data != NULL) { 83 data_size = size; 84 bound = region.bound; 85 count = region.count; 86 memcpy(data, region.data, count * sizeof(clipping_rect)); 87 } else 88 Support::ZeroRegion(*this); 89 } 90 91 92 /*! \brief Initializes a region to contain a BRect. 93 \param rect The BRect to set the region to. 94 */ 95 BRegion::BRegion(const BRect rect) 96 : 97 data_size(0), 98 data(NULL) 99 { 100 data = (clipping_rect *)malloc(kInitialDataSize * sizeof(clipping_rect)); 101 if (data != NULL) { 102 data_size = kInitialDataSize; 103 Set(rect); 104 } else 105 Support::ZeroRegion(*this); 106 } 107 108 109 /*! \brief Frees the allocated memory. 110 */ 111 BRegion::~BRegion() 112 { 113 free(data); 114 } 115 116 117 /*! \brief Returns the bounds of the region. 118 \return A BRect which represents the bounds of the region. 119 */ 120 BRect 121 BRegion::Frame() const 122 { 123 return to_BRect(bound); 124 } 125 126 127 /*! \brief Returns the bounds of the region as a clipping_rect (which has integer coordinates). 128 \return A clipping_rect which represents the bounds of the region. 129 */ 130 clipping_rect 131 BRegion::FrameInt() const 132 { 133 return bound; 134 } 135 136 137 /*! \brief Returns the regions's BRect at the given index. 138 \param index The index (zero based) of the wanted rectangle. 139 \return If the given index is valid, it returns the BRect at that index, 140 otherwise, it returns an invalid BRect. 141 */ 142 BRect 143 BRegion::RectAt(int32 index) 144 { 145 if (index >= 0 && index < count) 146 return to_BRect(data[index]); 147 148 return BRect(); //An invalid BRect 149 } 150 151 152 /*! \brief Returns the regions's clipping_rect at the given index. 153 \param index The index (zero based) of the wanted rectangle. 154 \return If the given index is valid, it returns the clipping_rect at that index, 155 otherwise, it returns an invalid clipping_rect. 156 */ 157 clipping_rect 158 BRegion::RectAtInt(int32 index) 159 { 160 if (index >= 0 && index < count) 161 return data[index]; 162 163 clipping_rect rect = { 1, 1, 0, 0 }; 164 return rect; 165 } 166 167 168 /*! \brief Counts the region rects. 169 \return An int32 which is the total number of rects in the region. 170 */ 171 int32 172 BRegion::CountRects() 173 { 174 return count; 175 } 176 177 178 /*! \brief Set the region to contain just the given BRect. 179 \param newBounds A BRect. 180 */ 181 void 182 BRegion::Set(BRect newBounds) 183 { 184 Set(to_clipping_rect(newBounds)); 185 } 186 187 188 /*! \brief Set the region to contain just the given clipping_rect. 189 \param newBounds A clipping_rect. 190 */ 191 void 192 BRegion::Set(clipping_rect newBounds) 193 { 194 ASSERT(data_size > 0); 195 196 if (valid_rect(newBounds)) { 197 count = 1; 198 data[0] = newBounds; 199 bound = newBounds; 200 } else 201 Support::ZeroRegion(*this); 202 } 203 204 205 /*! \brief Check if the region has any area in common with the given BRect. 206 \param rect The BRect to check the region against to. 207 \return \ctrue if the region has any area in common with the BRect, \cfalse if not. 208 */ 209 bool 210 BRegion::Intersects(BRect rect) const 211 { 212 return Intersects(to_clipping_rect(rect)); 213 } 214 215 216 /*! \brief Check if the region has any area in common with the given clipping_rect. 217 \param rect The clipping_rect to check the region against to. 218 \return \ctrue if the region has any area in common with the clipping_rect, \cfalse if not. 219 */ 220 bool 221 BRegion::Intersects(clipping_rect rect) const 222 { 223 if (!rects_intersect(rect, bound)) 224 return false; 225 226 for (long c = 0; c < count; c++) { 227 if (rects_intersect(data[c], rect)) 228 return true; 229 } 230 231 return false; 232 } 233 234 235 /*! \brief Check if the region contains the given BPoint. 236 \param pt The BPoint to be checked. 237 \return \ctrue if the region contains the BPoint, \cfalse if not. 238 */ 239 bool 240 BRegion::Contains(BPoint pt) const 241 { 242 // If the point doesn't lie within the region's bounds, 243 // don't even try it against the region's rects. 244 if (!point_in(bound, pt)) 245 return false; 246 247 for (long c = 0; c < count; c++) { 248 if (point_in(data[c], pt)) 249 return true; 250 } 251 return false; 252 } 253 254 255 /*! \brief Check if the region contains the given coordinates. 256 \param x The \cx coordinate of the point to be checked. 257 \param y The \cy coordinate of the point to be checked. 258 \return \ctrue if the region contains the point, \cfalse if not. 259 */ 260 bool 261 BRegion::Contains(int32 x, int32 y) 262 { 263 // see above 264 if (!point_in(bound, x, y)) 265 return false; 266 267 for (long c = 0; c < count; c++) { 268 if (point_in(data[c], x, y)) 269 return true; 270 } 271 return false; 272 } 273 274 275 /*! \brief Prints the BRegion to stdout. 276 */ 277 void 278 BRegion::PrintToStream() const 279 { 280 Frame().PrintToStream(); 281 282 for (long c = 0; c < count; c++) { 283 clipping_rect *rect = &data[c]; 284 printf("data = BRect(l:%ld.0, t:%ld.0, r:%ld.0, b:%ld.0)\n", 285 rect->left, rect->top, rect->right, rect->bottom); 286 } 287 } 288 289 290 /*! \brief Offsets all region's rects, and bounds by the given values. 291 \param dh The horizontal offset. 292 \param dv The vertical offset. 293 */ 294 void 295 BRegion::OffsetBy(int32 dh, int32 dv) 296 { 297 if (count > 0) { 298 for (long c = 0; c < count; c++) 299 offset_rect(data[c], dh, dv); 300 301 offset_rect(bound, dh, dv); 302 } 303 } 304 305 306 /*! \brief Empties the region, so that it doesn't include any rect, and invalidates its bounds. 307 */ 308 void 309 BRegion::MakeEmpty() 310 { 311 Support::ZeroRegion(*this); 312 } 313 314 315 /*! \brief Modifies the region, so that it includes the given BRect. 316 \param rect The BRect to be included by the region. 317 */ 318 void 319 BRegion::Include(BRect rect) 320 { 321 Include(to_clipping_rect(rect)); 322 } 323 324 325 /*! \brief Modifies the region, so that it includes the given clipping_rect. 326 \param rect The clipping_rect to be included by the region. 327 */ 328 void 329 BRegion::Include(clipping_rect rect) 330 { 331 BRegion region; 332 BRegion newRegion; 333 334 region.Set(rect); 335 336 Support::OrRegion(*this, region, newRegion); 337 Support::CopyRegion(newRegion, *this); 338 } 339 340 341 /*! \brief Modifies the region, so that it includes the area of the given region. 342 \param region The region to be included. 343 */ 344 void 345 BRegion::Include(const BRegion *region) 346 { 347 BRegion newRegion; 348 349 Support::OrRegion(*this, *region, newRegion); 350 Support::CopyRegion(newRegion, *this); 351 } 352 353 354 /*! \brief Modifies the region, excluding the area represented by the given BRect. 355 \param rect The BRect to be excluded. 356 */ 357 void 358 BRegion::Exclude(BRect rect) 359 { 360 Exclude(to_clipping_rect(rect)); 361 } 362 363 364 /*! \brief Modifies the region, excluding the area represented by the given clipping_rect. 365 \param rect The clipping_rect to be excluded. 366 */ 367 void 368 BRegion::Exclude(clipping_rect rect) 369 { 370 BRegion region; 371 BRegion newRegion; 372 373 region.Set(rect); 374 375 Support::SubRegion(*this, region, newRegion); 376 Support::CopyRegion(newRegion, *this); 377 } 378 379 380 /*! \brief Modifies the region, excluding the area contained in the given BRegion. 381 \param region The BRegion to be excluded. 382 */ 383 void 384 BRegion::Exclude(const BRegion *region) 385 { 386 BRegion newRegion; 387 388 Support::SubRegion(*this, *region, newRegion); 389 Support::CopyRegion(newRegion, *this); 390 } 391 392 393 /*! \brief Modifies the region, so that it will contain just the area in common with the given BRegion. 394 \param region the BRegion to intersect to. 395 */ 396 void 397 BRegion::IntersectWith(const BRegion *region) 398 { 399 BRegion newRegion; 400 401 Support::AndRegion(*this, *region, newRegion); 402 Support::CopyRegion(newRegion, *this); 403 } 404 405 406 /*! \brief Modifies the region to be a copy of the given BRegion. 407 \param region the BRegion to copy. 408 \return This function always returns \c *this. 409 */ 410 BRegion & 411 BRegion::operator=(const BRegion ®ion) 412 { 413 if (®ion != this) { 414 free(data); 415 bound = region.bound; 416 count = region.count; 417 data_size = region.data_size; 418 419 if (data_size <= 0) 420 data_size = 1; 421 422 data = (clipping_rect *)malloc(data_size * sizeof(clipping_rect)); 423 424 memcpy(data, region.data, count * sizeof(clipping_rect)); 425 } 426 427 return *this; 428 } 429 430 431 /*! \brief Adds a rect to the region. 432 \param rect The clipping_rect to be added. 433 434 Adds the given rect to the region, merging it with another already contained in the region, 435 if possible. Recalculate the region's bounds if needed. 436 */ 437 void 438 BRegion::_AddRect(clipping_rect rect) 439 { 440 ASSERT(count >= 0); 441 ASSERT(data_size >= 0); 442 ASSERT(valid_rect(rect)); 443 444 // Should we just reallocate the memory and 445 // copy the rect ? 446 bool addRect = true; 447 448 if (count > 0) { 449 // Wait! We could merge the rect with one of the 450 // existing rectangles, if it's adiacent. 451 // We just check it against the last rectangle, since 452 // we are keeping them sorted by their "top" coordinates. 453 long last = count - 1; 454 if (rect.left == data[last].left && rect.right == data[last].right 455 && rect.top == data[last].bottom + 1) { 456 457 data[last].bottom = rect.bottom; 458 addRect = false; 459 460 } else if (rect.top == data[last].top && rect.bottom == data[last].bottom) { 461 if (rect.left == data[last].right + 1) { 462 463 data[last].right = rect.right; 464 addRect = false; 465 466 } else if (rect.right == data[last].left - 1) { 467 468 data[last].left = rect.left; 469 addRect = false; 470 } 471 } 472 } 473 474 // We weren't lucky.... just add the rect as a new one 475 if (addRect) { 476 if (data_size <= count) 477 set_size(count + 16); 478 479 data[count] = rect; 480 481 count++; 482 } 483 484 // Recalculate bounds 485 if (rect.top < bound.top) 486 bound.top = rect.top; 487 488 if (rect.left < bound.left) 489 bound.left = rect.left; 490 491 if (rect.right > bound.right) 492 bound.right = rect.right; 493 494 if (rect.bottom > bound.bottom) 495 bound.bottom = rect.bottom; 496 } 497 498 499 /*! \brief Reallocate the memory in the region. 500 \param new_size The amount of rectangles that the region could contain. 501 */ 502 void 503 BRegion::set_size(long new_size) 504 { 505 if (new_size <= 0) 506 new_size = data_size + 16; 507 508 data = (clipping_rect *)realloc(data, new_size * sizeof(clipping_rect)); 509 510 if (data == NULL) 511 debugger("BRegion::set_size realloc error\n"); 512 513 data_size = new_size; 514 515 ASSERT(count <= data_size); 516 } 517