1/* 2 * Copyright 2007-2014 Haiku, Inc. All rights reserved. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * Niels Sascha Reedijk, niels.reedijk@gmail.com 7 * John Scipione, jscipione@gmail.com 8 * 9 * Proofreading: 10 * David Weizades, ddewbofh@hotmail.com 11 * Thom Holwerda, slakje@quicknet.nl 12 * John Drinkwater, jdrinkwater@gmail.com 13 * 14 * Corresponds to: 15 * headers/os/support/List.h hrev47422 16 * src/kits/support/List.cpp hrev47422 17 */ 18 19 20/*! 21 \file List.h 22 \ingroup support 23 \ingroup libbe 24 \brief Defines the BList class. 25*/ 26 27 28/*! 29 \class BList 30 \ingroup support 31 \ingroup libbe 32 \brief An ordered container that is designed to hold generic \c void* 33 objects. 34 35 This class is designed to be used for a variety of tasks. Unlike similar 36 implementations in other libraries, this class is not based on templates 37 and as such is inherently not typed. So it will be the job of the programmer 38 to make sure proper data is entered since the compiler cannot check this by 39 itself. 40 41 BList contains a list of items that will grow and shrink depending on how 42 many items are in it. So you will not have to do any of the memory 43 management nor any ordering. These properties makes it useful in a whole 44 range of situations such as the interface kit within the BListView class. 45 46 A note on the ownership of the objects might come in handy. BList never 47 assumes ownership of the objects. As such, removing items from the list will 48 only remove the entries from the list; it will not delete the items 49 themselves. Similarly, you should also make sure that before you might 50 delete an object that is in a list, you will have to remove it from the list 51 first. 52 53 \warning This class is not thread-safe. 54 55 The class implements methods to add, remove, reorder, retrieve, and query 56 items as well as some advanced methods which let you perform a task on all 57 the items in the list. 58 59 \see BObjectList for a templated version of BList that adds type safety, 60 optional object ownership, search, and insert operations. 61 62 \since BeOS R3 63*/ 64 65 66/*! 67 \fn BList::BList(int32 count = 20) 68 \brief Create a new list with a number of empty slots. 69 70 The memory management of this class allocates new memory per block. The 71 \c count parameter can be tweaked to determine the size of these blocks. 72 In general, if you know your list is only going to contain a certain number 73 of items at most, you can pass that value. If you expect your list to have 74 very few items, it is safe to choose a low number. This is to prevent the 75 list from taking up unneeded memory. If you expect the list to contain a 76 large number of items, choose a higher value. Every time the memory is full, 77 all the items have to be copied into a new piece of allocated memory, which 78 is an expensive operation. 79 80 If you are unsure, you do not have to worry too much. Just make sure you do 81 not use a lot of lists, and as long as the list is not used in one of the 82 performance critical parts of the code, you are safe to go with the default 83 values. 84 85 \param count The size of the blocks allocated in memory. 86 87 \since BeOS R3 88*/ 89 90 91/*! 92 \fn BList::BList(const BList& other) 93 \brief Copy constructor. Copy a complete list into this one. 94 95 \param other The list to copy from. 96 97 \since BeOS R3 98*/ 99 100 101/*! 102 \fn BList::~BList() 103 \brief Destroy the list. 104 105 Please note that as BList does not assume ownership of the objects, 106 only the list will be freed, not the objects that are held in it. 107 108 \since BeOS R3 109*/ 110 111 112/*! 113 \name Operators 114*/ 115 116 117//! @{ 118 119 120/*! 121 \fn BList& BList::operator=(const BList &other) 122 \brief Copy another list into this object. 123 124 \since BeOS R3 125*/ 126 127 128/*! 129 \fn bool BList::operator==(const BList& other) const 130 \brief Returns whether or not the BList and \a other are equal. 131 132 Equal means that they are the same object or their contents are the same. 133 134 \return \c true if the lists are equal, \c false if they are NOT equal. 135 136 \since Haiku R1 137*/ 138 139 140/*! 141 \fn bool BList::operator!=(const BList& other) const 142 \brief Returns whether or not the BList and \a other are NOT equal. 143 144 \return \c true if the lists are NOT equal, \c false if they are equal. 145 146 \since Haiku R1 147*/ 148 149 150//! @} 151 152 153/*! 154 \name Adding and Removing Items 155*/ 156 157 158//! @{ 159 160 161/*! 162 \fn bool BList::AddItem(void* item, int32 index) 163 \brief Add \a item at the specified \a index. 164 165 \param item The \a item to add. 166 \param index The place in the list to add the \a item. 167 168 \return Whether or not the item was added. 169 \retval true The item was added. 170 \retval false Item was not added. Either the index is negative or invalid, 171 or resizing the list failed. 172 173 \see AddItem(void*) 174 175 \since BeOS R3 176*/ 177 178 179/*! 180 \fn bool BList::AddItem(void* item) 181 \brief Append the \a item to the end of the list. 182 183 \param item The item to append. 184 185 \return Whether or not the \a item was appended. 186 \retval true The \a item was appended. 187 \retval false \a item was not appended, since resizing the BList failed. 188 189 \see AddItem(void*, int32) 190 191 \since BeOS R3 192*/ 193 194 195/*! 196 \fn bool BList::AddList(const BList* list, int32 index) 197 \brief Add a \a list of items to this list at the specified \a index. 198 199 Note that the \a list parameter is \c const, so the original list will not 200 be altered. 201 202 \param list The \a list to be added. 203 \param index The position in the current \a list where the new item(s) 204 are added. 205 206 \return Whether or not the \a list was added. 207 \retval true The \a list was added. 208 \retval false Failed to insert the \a list resizing failed. 209 210 \see AddList(const BList*) 211 212 \since BeOS R3 213*/ 214 215 216/*! 217 \fn bool BList::AddList(const BList* list) 218 \brief Append a \a list of items to this list. 219 220 Note that the \a list parameter is a \c const, so the original list will not 221 be altered. 222 223 \param list The \a list to be added. 224 225 \return Whether or not the \a list was added. 226 \retval true The \a list was appended. 227 \retval false Failed to append the list, resizing failed. 228 229 \see AddList(const BList*, int32) 230 231 \since BeOS R3 232*/ 233 234 235/*! 236 \fn bool BList::RemoveItem(void* item) 237 \brief Remove \a item from the list. 238 239 \param item The \a item to be removed. 240 241 \return Whether or not the \a item was removed. 242 \retval true The \a item was found and removed. 243 \retval false The \a item was not in this list and thus not removed. 244 245 \see RemoveItem(int32) 246 247 \since BeOS R3 248*/ 249 250 251/*! 252 \fn void* BList::RemoveItem(int32 index) 253 \brief Remove the item at \a index from the list. 254 255 \param index The \a index of the item to be removed. 256 257 \return The pointer to the item that was removed, or \c NULL if the 258 \a index was invalid. 259 260 \see RemoveItem(void*) 261 262 \since BeOS R3 263*/ 264 265 266/*! 267 \fn bool BList::RemoveItems(int32 index, int32 count) 268 \brief Remove a number of items starting at a certain position. 269 270 If the count parameter is larger than the number of items in the list, 271 all the items from the offset to the end will be removed. 272 273 \param index The offset in the list where removal should start. 274 \param count The number of items to remove. 275 276 \return Whether or not the items were removed. 277 \retval true Removal succeeded. 278 \retval false Failed to remove the items because the index was invalid. 279 280 \since BeOS R3 281*/ 282 283 284/*! 285 \fn bool BList::ReplaceItem(int32 index, void* item) 286 \brief Replace an item with another one. 287 288 \param index The offset in the list where to put the \a item. 289 \param item The new \a item to put in the list. 290 291 \return Whether or not the item was replaced. 292 \retval true The item was replaced. 293 \retval false The \a index was invalid. 294 295 \since Haiku R1 296*/ 297 298 299/*! 300 \fn void BList::MakeEmpty() 301 \brief Clear all the items from the list. 302 303 \note This does not free the items. 304 305 \since BeOS R3 306*/ 307 308 309//! @} 310 311 312/*! 313 \name Reordering Items 314*/ 315 316 317//! @{ 318 319 320/*! 321 \fn void BList::SortItems(int (*compareFunc)(const void*, const void*)) 322 \brief Sort the items with the use of a supplied comparison function. 323 324 The function should take two \c const pointers as arguments and should 325 return an integer. 326 327 For an example, see the Compare(const BString *, const BString *) function. 328 329 \since BeOS R3 330*/ 331 332 333/*! 334 \fn bool BList::SwapItems(int32 indexA, int32 indexB) 335 \brief Swap the items at \a indexA and \a indexB. 336 337 \param indexA The first item. 338 \param indexB The second item. 339 340 \return Whether or not the items were swapped. 341 \retval true Swap succeeded. 342 \retval false Swap failed because one of the indexes was invalid. 343 344 \since Haiku R1 345*/ 346 347 348/*! 349 \fn bool BList::MoveItem(int32 fromIndex, int32 toIndex) 350 \brief Move the item at \a fromIndex to the position of \a toIndex. 351 352 This moves a list item from position A to position B, moving the appropriate 353 block of list elements to make up for the move. For example, in the array: 354\verbatim 355A B C D E F G H I J 356\endverbatim 357 358 Moving 1(B)->6(G) would result in this: 359\verbatim 360A C D E F G B H I J 361\endverbatim 362 363 \param fromIndex The original location. 364 \param toIndex The new location. 365 366 \return Whether or not the items were moved. 367 \retval true Move succeeded. 368 \retval false Move failed due to the indexes being invalid. 369 370 \since Haiku R1 371*/ 372 373 374//! @} 375 376 377/*! 378 \name Retrieving Items 379*/ 380 381 382//! @{ 383 384 385/*! 386 \fn void* BList::ItemAt(int32 index) const 387 \brief Return a pointer to the item at the given \a index. 388 389 \param index The item to retrieve. 390 391 \return A pointer to the item in that position, or \c NULL if the 392 \a index is out of bounds. 393 394 \see ItemAtFast(int32 index) const 395 396 \since BeOS R3 397*/ 398 399 400/*! 401 \fn void* BList::FirstItem() const 402 \brief Return a pointer to the first item in the list. 403 404 \return A pointer to the first item or \c NULL if the list is empty. 405 406 \see LastItem() const 407 408 \since BeOS R3 409*/ 410 411 412/*! 413 \fn void* BList::ItemAtFast(int32 index) const 414 \brief Return a pointer to the item at \a index. 415 416 This method does not perform any boundary checks when it retrieves an item. 417 Use this method in a performance critical area of your program where you are 418 sure you will not get an invalid item. 419 420 \return A pointer to the item. 421 422 \since Haiku R1 423*/ 424 425 426/*! 427 \fn void* BList::LastItem() const 428 \brief Return a pointer to the last item in the list. 429 430 \return A pointer to the last item or \c NULL if the list is empty. 431 432 \see FirstItem() const 433 434 \since BeOS R3 435*/ 436 437 438/*! 439 \fn void* BList::Items() const 440 \brief Return the internal list of objects. 441 442 This method will return a pointer to the internal pointer list. This means 443 that you should be careful what you are doing, since you are working with 444 the internals of the class directly. 445 446 It is not a good idea to make any changes to the list, since that will mess 447 up the internal consistency. 448 449 \warning If there is anything you want, for which you need the list of 450 objects, please realize that that probably means that what you 451 want to do is a bad idea to begin with and that you should avoid 452 this method. The list of objects does not belong to you. 453 454 \return The internal list of pointers. 455 456 \sa DoForEach() for an alternate method. 457 458 \since BeOS R3 459*/ 460 461 462//! @} 463 464 465/*! 466 \name Querying Items 467*/ 468 469 470//! @{ 471 472 473/*! 474 \fn bool BList::HasItem(void* item) const 475 \brief Return whether or not \a item is in the list. 476 477 \return \c true if the \a item was in the list, \c false otherwise. 478 479 \since BeOS R3 480*/ 481 482 483/*! 484 \fn bool BList::HasItem(const void *item) const 485 \brief Return whether or not \a item is in the list. 486 487 \return \c true if the \a item was in the list, \c false otherwise. 488 489 \since Haiku R1 490*/ 491 492 493/*! 494 \fn int32 BList::IndexOf(void* item) const 495 \brief Return the index of \a item. 496 497 \return The index of the item, or -1 when the item is not in the list. 498 499 \since BeOS R3 500*/ 501 502 503/*! 504 \fn int32 BList::IndexOf(const void *item) const 505 \brief Return the index of \a item. 506 507 \return The index of the item, or -1 when the item is not in the list. 508 509 \since Haiku R1 510*/ 511 512 513/*! 514 \fn int32 BList::CountItems() const 515 \brief Returns the number of items in the list. 516 517 \return The number of items in the list as an int32. 518 519 \since BeOS R3 520*/ 521 522 523/*! 524 \fn bool BList::IsEmpty() const 525 \brief Return whether or not there are items in the list. 526 527 \return \c true if the list was empty, \c false otherwise. 528 529 \since BeOS R3 530*/ 531 532 533//! @} 534 535 536/*! 537 \name Iterating Over Items 538*/ 539 540 541//! @{ 542 543 544/*! 545 \fn void BList::DoForEach(bool (*func)(void* item)) 546 \brief Perform an action on every item in the list. 547 548 Iterates over all items in the list, and calls the \a func function on each of them, 549 until the function returns \c true. 550 551 \param func A pointer to a function that takes a \c void* list item, and 552 returns a bool indicating if the iteration should stop. 553 554 \see DoForEach(bool (*func)(void*, void*), void*) 555 556 \since BeOS R3 557*/ 558 559 560/*! 561 \fn void BList::DoForEach(bool (*func)(void* item, void* arg2), void* arg2) 562 \brief Perform an action on every item in the list with an argument. 563 564 The iteration stops when the \a func function returns \c true. 565 This can be used to implement a linear search of the list, for example: 566 567 \code{.cpp} 568 bool compareFunc(void* _item, void* arg2) { 569 Item* item = (Item*)_item; 570 Args* args = (Args*)arg2; 571 if (item->Matches(args->pattern)) { 572 args->result = item; 573 return true; 574 } 575 return false; 576 } 577 578 Args args = {0}; 579 list.DoForEach(compareFunc, &args); 580 if (args->result != NULL) { 581 // Found it! 582 } 583 \endcode 584 585 \param func A function with the first \c void* argument being the item 586 and the second \c void* being the argument that you supply. 587 \param arg2 An argument to supply to \a func. 588 589 \see DoForEach(bool (*func)(void*)) 590 591 \since BeOS R3 592*/ 593 594 595//! @} 596