1/* 2 * Copyright 2007, 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 * 8 * Proofreading: 9 * David Weizades, ddewbofh@hotmail.com 10 * Thom Holwerda, slakje@quicknet.nl 11 * John Drinkwater, jdrinkwater@gmail.com 12 * 13 * Corresponds to: 14 * /trunk/headers/os/support/List.h rev 19972 15 * /trunk/src/kits/support/List.cpp rev 18649 16 */ 17 18 19/*! 20 \file List.h 21 \brief Defines the BList class. 22*/ 23 24 25/*! 26 \class BList 27 \ingroup support 28 \ingroup libbe 29 \brief An ordered container that is designed to hold generic \c void* 30 objects. 31 32 This class is designed to be used for a variety of tasks. Unlike similar 33 implementations in other libraries, this class is not based on templates 34 and as such is inherently not typed. So it will be the job of the programmer 35 to make sure proper data is entered since the compiler cannot check this by 36 itself. 37 38 BList contains a list of items that will grow and shrink depending on how 39 many items are in it. So you will not have to do any of the memory 40 management nor any ordering. These properties makes it useful in a whole 41 range of situations such as the interface kit within the BListView class. 42 43 A note on the ownership of the objects might come in handy. BList never 44 assumes ownership of the objects. As such, removing items from the list will 45 only remove the entries from the list; it will not delete the items 46 themselves. Similarly, you should also make sure that before you might 47 delete an object that is in a list, you will have to remove it from the list 48 first. 49 50 \warning This class is not thread-safe. 51 52 The class implements methods to add, remove, reorder, retrieve, and query 53 items as well as some advanced methods which let you perform a task on all 54 the items in the list. 55*/ 56 57 58/*! 59 \fn BList::BList(int32 count = 20) 60 \brief Create a new list with a number of empty slots. 61 62 The memory management of this class allocates new memory per block. The 63 \c count parameter can be tweaked to determine the size of these blocks. 64 In general, if you know your list is only going to contain a certain number 65 of items at most, you can pass that value. If you expect your list to have 66 very few items, it is safe to choose a low number. This is to prevent the 67 list from taking up unneeded memory. If you expect the list to contain a 68 large number of items, choose a higher value. Every time the memory is full, 69 all the items have to be copied into a new piece of allocated memory, which 70 is an expensive operation. 71 72 If you are unsure, you do not have to worry too much. Just make sure you do 73 not use a lot of lists, and as long as the list is not used in one of the 74 performance critical parts of the code, you are safe to go with the default 75 values. 76 77 \param count The size of the blocks allocated in memory. 78*/ 79 80 81/*! 82 \fn BList::BList(const BList& anotherList) 83 \brief Copy constructor. Copy a complete list into this one. 84*/ 85 86 87/*! 88 \fn BList::~BList() 89 \brief Destroy the list. 90 91 Please note that as BList does not assume ownership of the objects, 92 only the list will be freed, not the objects that are held in it. 93*/ 94 95 96/*! 97 \fn BList& BList::operator=(const BList &list) 98 \brief Copy another list into this object. 99*/ 100 101 102/*! 103 \name Adding and Removing Items 104*/ 105 106 107//! @{ 108 109 110/*! 111 \fn bool BList::AddItem(void *item, int32 index) 112 \brief Add an item at a certain position. 113 114 \param item The item to add. 115 \param index The place in the list. 116 \retval true The item was added. 117 \retval false Item was not added. Either the index is negative or invalid, 118 or resizing the list failed. 119 \see AddItem(void *item) 120*/ 121 122 123/*! 124 \fn bool BList::AddItem(void *item) 125 \brief Append an item to the list. 126 127 \param item The item to add. 128 \retval true The item was appended. 129 \retval false Item was not appended, since resizing the list failed. 130 \see AddItem(void *item, int32 index) 131*/ 132 133 134/*! 135 \fn bool BList::AddList(const BList *list, int32 index) 136 \brief Add items from another list to this list at a certain position. 137 138 Note that the \a list parameter is \c const, so the original list will not 139 be altered. 140 141 \param list The list to be added. 142 \param index The position in the current list where the new item(s) should 143 be put. 144 \retval true The list was added. 145 \retval false Failed to insert the list, due to the fact that resizing our 146 list failed. 147 \see AddList(const BList *list) 148*/ 149 150 151/*! 152 \fn bool BList::AddList(const BList *list) 153 \brief Append a list to this list. 154 155 Note that the \a list parameter is a \c const, so the original list will not 156 be altered. 157 158 \param list The list to be appended. 159 \retval true The list was appended. 160 \retval false Failed to append the list, due to the fact that resizing of 161 our list failed. 162 \see AddList(const BList *list, int32 index) 163*/ 164 165 166/*! 167 \fn bool BList::RemoveItem(void *item) 168 \brief Remove an item from the list. 169 170 \param item The item that should be removed. 171 \retval true The item was found and removed. 172 \retval false The item was not in this list and thus not removed. 173 \see RemoveItem(int32 index) 174*/ 175 176 177/*! 178 \fn void * BList::RemoveItem(int32 index) 179 \brief Remove the item at \a index from the list. 180 181 \param index The item that should be removed. 182 \return The pointer to the item that was removed, or \c NULL in case the 183 index was invalid. 184 \see RemoveItem(void *item) 185*/ 186 187 188/*! 189 \fn bool BList::RemoveItems(int32 index, int32 count) 190 \brief Remove a number of items starting at a certain position. 191 192 If the count parameter is larger than the number of items in the list, 193 all the items from the offset to the end will be removed. 194 195 \param index The offset in the list where removal should start. 196 \param count The number of items to remove. 197 \retval true Removal succeeded. 198 \retval false Failed to remove the items because the index was invalid. 199*/ 200 201 202/*! 203 \fn bool BList::ReplaceItem(int32 index, void *newItem) 204 \brief Replace an item with another one. 205 206 \param index The offset in the list where to put the item. 207 \param newItem The new item to put in the list. 208 \retval true Item replaced. 209 \retval false The index was invalid. 210*/ 211 212 213/*! 214 \fn void BList::MakeEmpty() 215 \brief Clear all the items from the list. 216 217 Please note that this does not free the items. 218*/ 219 220 221//! @} 222 223 224/*! 225 \name Reordering Items 226*/ 227 228 229//! @{ 230 231 232/*! 233 \fn void BList::SortItems(int (*compareFunc)(const void *, const void *)) 234 \brief Sort the items with the use of a supplied comparison function. 235 236 The function should take two \c const pointers as arguments and should 237 return an integer. 238 239 For an example, see the Compare(const BString *, const BString *) function. 240*/ 241 242 243/*! 244 \fn bool BList::SwapItems(int32 indexA, int32 indexB) 245 \brief Swap two items. 246 247 \param indexA The first item. 248 \param indexB The second item. 249 \retval true Swap succeeded. 250 \retval false Swap failed because one of the indexes was invalid. 251*/ 252 253 254/*! 255 \fn bool BList::MoveItem(int32 fromIndex, int32 toIndex) 256 \brief Move an item to a new place 257 258 This moves a list item from position A to position B, moving the appropriate 259 block of list elements to make up for the move. For example, in the array: 260 \verbatim 261A B C D E F G H I J 262 \endverbatim 263 264 Moving 1(B)->6(G) would result in this: 265 \verbatim 266A C D E F G B H I J 267 \endverbatim 268 269 \param fromIndex The original location. 270 \param toIndex The new location. 271 \retval true Move succeeded. 272 \retval false Move failed due to the indexes being invalid. 273*/ 274 275 276//! @} 277 278 279/*! 280 \name Retrieving Items 281*/ 282 283 284//! @{ 285 286 287/*! 288 \fn void *BList::ItemAt(int32 index) const 289 \brief Get an item. 290 291 \param index The item to retrieve. 292 \return A pointer to the item in that position, or \c NULL if the index is 293 out of bounds. 294 \see ItemAtFast(int32 index) const 295*/ 296 297 298/*! 299 \fn void *BList::FirstItem() const 300 \brief Get the first item. 301 302 \return A pointer to the first item or \c NULL if the list is empty. 303 \see LastItem() const 304*/ 305 306 307/*! 308 \fn void *BList::ItemAtFast(int32 index) const 309 \brief Get an item. 310 311 This method does not perform any boundary checks when it retrieves an item. 312 Use this method in a performance critical area of your program where you are 313 sure you will not get an invalid item. 314 315 \return A pointer to the item. 316*/ 317 318 319/*! 320 \fn void *BList::LastItem() const 321 \brief Get the last item. 322 \return A pointer to the last item or \c NULL if the list is empty. 323 \see FirstItem() const 324*/ 325 326 327/*! 328 \fn void *BList::Items() const 329 \brief Return the internal list of objects. 330 331 This method will return a pointer to the internal pointer list. This means 332 that you should be careful what you are doing, since you are working with 333 the internals of the class directly. 334 335 It is not a good idea to make any changes to the list, since that will mess 336 up the internal consistency. 337 338 \warning If there is anything you want, for which you need the list of 339 objects, please realize that that probably means that what you want to 340 do is a bad idea to begin with and that you should avoid this method. 341 The list of objects does not belong to you. See also DoForEach() for an 342 alternate method. 343 \return The internal list of pointers. 344*/ 345 346 347//! @} 348 349 350/*! 351 \name Querying for Items 352*/ 353 354 355//! @{ 356 357 358/*! 359 \fn bool BList::HasItem(void *item) const 360 \brief Check if an item is in the list. 361*/ 362 363 364/*! 365 \fn int32 BList::IndexOf(void *item) const 366 \brief Get the index of an item. 367 368 \return The index of the item, or -1 when the item is not in the list. 369*/ 370 371 372/*! 373 \fn int32 BList::CountItems() const 374 \brief Get the number of items in the list. 375*/ 376 377 378/*! 379 \fn bool BList::IsEmpty() const 380 \brief Check if there are items in the list. 381*/ 382 383 384//! @} 385 386 387/*! 388 \name Iterating over the List 389*/ 390 391 392//! @{ 393 394 395/*! 396 \fn void BList::DoForEach(bool (*func)(void* item)) 397 \brief Perform an action on every item in the list. 398 399 If one of the actions on the items fails it means that the \a func function 400 returned \c false and the processing of the list will be stopped. 401 402 \param func A function that takes a \c void* argument and returns a 403 boolean. 404 \see DoForEach(bool (*func)(void* item, void* arg2), void *arg2) 405*/ 406 407 408/*! 409 \fn void BList::DoForEach(bool (*func)(void* item, void* arg2), void *arg2) 410 \brief Perform an action on every item in the list with an argument. 411 412 If one of the actions on the items fails it means that the \a func function 413 returned \c false and the processing of the list will be stopped. 414 415 \param func A function with the first \c void* argument being the item 416 and the second \c void* being the argument that you supply. It should 417 return a boolean value on whether it succeeded or not. 418 \param arg2 An argument to supply to \a func. 419 \see DoForEach(bool (*func)(void* item)) 420*/ 421 422 423//! @} 424