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