1 /* 2 * Copyright 2003, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * All rights reserved. Distributed under the terms of the MIT license. 4 */ 5 #ifndef _VECTOR_SET_H 6 #define _VECTOR_SET_H 7 8 #include <stdlib.h> 9 #include <string.h> 10 11 #include <SupportDefs.h> 12 13 #include <util/kernel_cpp.h> 14 #include <Vector.h> 15 16 // element orders 17 namespace VectorSetOrder { 18 template<typename Value> class Ascending; 19 template<typename Value> class Descending; 20 } 21 22 // for convenience 23 #define _VECTOR_SET_TEMPLATE_LIST template<typename Value, \ 24 typename ElementOrder> 25 #define _VECTOR_SET_CLASS_NAME VectorSet<Value, ElementOrder> 26 #define _VECTOR_SET_CLASS_TYPE typename VectorSet<Value, ElementOrder> 27 28 /*! 29 \class VectorSet 30 \brief A generic vector-based set implementation. 31 32 The elements of the set are ordered according to the supplied 33 compare function object. Default is ascending order. 34 */ 35 template<typename Value, 36 typename ElementOrder = VectorSetOrder::Ascending<Value> > 37 class VectorSet { 38 private: 39 typedef Vector<Value> ElementVector; 40 41 public: 42 typedef typename ElementVector::Iterator Iterator; 43 typedef typename ElementVector::ConstIterator ConstIterator; 44 45 private: 46 static const size_t kDefaultChunkSize = 10; 47 static const size_t kMaximalChunkSize = 1024 * 1024; 48 49 public: 50 VectorSet(size_t chunkSize = kDefaultChunkSize); 51 // TODO: Copy constructor, assignment operator. 52 ~VectorSet(); 53 54 status_t Insert(const Value &value, bool replace = true); 55 56 int32 Remove(const Value &value); 57 Iterator Erase(const Iterator &iterator); 58 59 inline int32 Count() const; 60 inline bool IsEmpty() const; 61 void MakeEmpty(); 62 63 inline Iterator Begin(); 64 inline ConstIterator Begin() const; 65 inline Iterator End(); 66 inline ConstIterator End() const; 67 inline Iterator Null(); 68 inline ConstIterator Null() const; 69 70 Iterator Find(const Value &value); 71 ConstIterator Find(const Value &value) const; 72 Iterator FindClose(const Value &value, bool less); 73 ConstIterator FindClose(const Value &value, bool less) const; 74 75 private: 76 int32 _FindInsertionIndex(const Value &value, bool &exists) const; 77 78 private: 79 ElementVector fElements; 80 ElementOrder fCompare; 81 }; 82 83 84 // VectorSet 85 86 // constructor 87 /*! \brief Creates an empty set. 88 \param chunkSize The granularity for the underlying vector's capacity, 89 i.e. the minimal number of elements the capacity grows or shrinks 90 when necessary. 91 */ 92 _VECTOR_SET_TEMPLATE_LIST 93 _VECTOR_SET_CLASS_NAME::VectorSet(size_t chunkSize) 94 : fElements(chunkSize) 95 { 96 } 97 98 // destructor 99 /*! \brief Frees all resources associated with the object. 100 101 The contained elements are destroyed. Note, that, if the element 102 type is a pointer type, only the pointer is destroyed, not the object 103 it points to. 104 */ 105 _VECTOR_SET_TEMPLATE_LIST 106 _VECTOR_SET_CLASS_NAME::~VectorSet() 107 { 108 } 109 110 // Insert 111 /*! \brief Inserts a copy of the the supplied value. 112 113 If an element with the supplied value is already in the set, the 114 operation will not fail, but return \c B_OK. \a replace specifies 115 whether the element shall be replaced with the supplied in such a case. 116 Otherwise \a replace is ignored. 117 118 \param value The value to be inserted. 119 \param replace If the an element with this value does already exist and 120 \a replace is \c true, the element is replaced, otherwise left 121 untouched. 122 \return 123 - \c B_OK: Everything went fine. 124 - \c B_NO_MEMORY: Insufficient memory for this operation. 125 */ 126 _VECTOR_SET_TEMPLATE_LIST 127 status_t 128 _VECTOR_SET_CLASS_NAME::Insert(const Value &value, bool replace) 129 { 130 bool exists = false; 131 int32 index = _FindInsertionIndex(value, exists); 132 if (exists) { 133 if (replace) 134 fElements[index] = value; 135 return B_OK; 136 } 137 return fElements.Insert(value, index); 138 } 139 140 // Remove 141 /*! \brief Removes the element with the supplied value. 142 \param value The value of the element to be removed. 143 \return The number of removed occurrences, i.e. \c 1, if the set 144 contained an element with the value, \c 0 otherwise. 145 */ 146 _VECTOR_SET_TEMPLATE_LIST 147 int32 148 _VECTOR_SET_CLASS_NAME::Remove(const Value &value) 149 { 150 bool exists = false; 151 int32 index = _FindInsertionIndex(value, exists); 152 if (!exists) 153 return 0; 154 fElements.Erase(index); 155 return 1; 156 } 157 158 // Erase 159 /*! \brief Removes the element at the given position. 160 \param iterator An iterator referring to the element to be removed. 161 \return An iterator referring to the element succeeding the removed 162 one (End(), if it was the last element that has been 163 removed), or Null(), if \a iterator was an invalid iterator 164 (in this case including End()). 165 */ 166 _VECTOR_SET_TEMPLATE_LIST 167 _VECTOR_SET_CLASS_TYPE::Iterator 168 _VECTOR_SET_CLASS_NAME::Erase(const Iterator &iterator) 169 { 170 return fElements.Erase(iterator); 171 } 172 173 // Count 174 /*! \brief Returns the number of elements the set contains. 175 \return The number of elements the set contains. 176 */ 177 _VECTOR_SET_TEMPLATE_LIST 178 inline 179 int32 180 _VECTOR_SET_CLASS_NAME::Count() const 181 { 182 return fElements.Count(); 183 } 184 185 // IsEmpty 186 /*! \brief Returns whether the set is empty. 187 \return \c true, if the set is empty, \c false otherwise. 188 */ 189 _VECTOR_SET_TEMPLATE_LIST 190 inline 191 bool 192 _VECTOR_SET_CLASS_NAME::IsEmpty() const 193 { 194 return fElements.IsEmpty(); 195 } 196 197 // MakeEmpty 198 /*! \brief Removes all elements from the set. 199 */ 200 _VECTOR_SET_TEMPLATE_LIST 201 void 202 _VECTOR_SET_CLASS_NAME::MakeEmpty() 203 { 204 fElements.MakeEmpty(); 205 } 206 207 // Begin 208 /*! \brief Returns an iterator referring to the beginning of the set. 209 210 If the set is not empty, Begin() refers to its first element, 211 otherwise it is equal to End() and must not be dereferenced! 212 213 \return An iterator referring to the beginning of the set. 214 */ 215 _VECTOR_SET_TEMPLATE_LIST 216 inline 217 _VECTOR_SET_CLASS_TYPE::Iterator 218 _VECTOR_SET_CLASS_NAME::Begin() 219 { 220 return fElements.Begin(); 221 } 222 223 // Begin 224 /*! \brief Returns an iterator referring to the beginning of the set. 225 226 If the set is not empty, Begin() refers to its first element, 227 otherwise it is equal to End() and must not be dereferenced! 228 229 \return An iterator referring to the beginning of the set. 230 */ 231 _VECTOR_SET_TEMPLATE_LIST 232 inline 233 _VECTOR_SET_CLASS_TYPE::ConstIterator 234 _VECTOR_SET_CLASS_NAME::Begin() const 235 { 236 return fElements.Begin(); 237 } 238 239 // End 240 /*! \brief Returns an iterator referring to the end of the set. 241 242 The position identified by End() is the one succeeding the last 243 element, i.e. it must not be dereferenced! 244 245 \return An iterator referring to the end of the set. 246 */ 247 _VECTOR_SET_TEMPLATE_LIST 248 inline 249 _VECTOR_SET_CLASS_TYPE::Iterator 250 _VECTOR_SET_CLASS_NAME::End() 251 { 252 return fElements.End(); 253 } 254 255 // End 256 /*! \brief Returns an iterator referring to the end of the set. 257 258 The position identified by End() is the one succeeding the last 259 element, i.e. it must not be dereferenced! 260 261 \return An iterator referring to the end of the set. 262 */ 263 _VECTOR_SET_TEMPLATE_LIST 264 inline 265 _VECTOR_SET_CLASS_TYPE::ConstIterator 266 _VECTOR_SET_CLASS_NAME::End() const 267 { 268 return fElements.End(); 269 } 270 271 // Null 272 /*! \brief Returns an invalid iterator. 273 274 Null() is used as a return value, if something went wrong. It must 275 neither be incremented or decremented nor dereferenced! 276 277 \return An invalid iterator. 278 */ 279 _VECTOR_SET_TEMPLATE_LIST 280 inline 281 _VECTOR_SET_CLASS_TYPE::Iterator 282 _VECTOR_SET_CLASS_NAME::Null() 283 { 284 return fElements.Null(); 285 } 286 287 // Null 288 /*! \brief Returns an invalid iterator. 289 290 Null() is used as a return value, if something went wrong. It must 291 neither be incremented or decremented nor dereferenced! 292 293 \return An invalid iterator. 294 */ 295 _VECTOR_SET_TEMPLATE_LIST 296 inline 297 _VECTOR_SET_CLASS_TYPE::ConstIterator 298 _VECTOR_SET_CLASS_NAME::Null() const 299 { 300 return fElements.Null(); 301 } 302 303 // Find 304 /*! \brief Returns an iterator referring to the element with the 305 specified value. 306 \param value The value of the element to be found. 307 \return An iterator referring to the found element, or End(), if the 308 set doesn't contain any element with the given value. 309 */ 310 _VECTOR_SET_TEMPLATE_LIST 311 _VECTOR_SET_CLASS_TYPE::Iterator 312 _VECTOR_SET_CLASS_NAME::Find(const Value &value) 313 { 314 bool exists = false; 315 int32 index = _FindInsertionIndex(value, exists); 316 if (!exists) 317 return fElements.End(); 318 return fElements.IteratorForIndex(index); 319 } 320 321 // Find 322 /*! \brief Returns an iterator referring to the element with the 323 specified value. 324 \param value The value of the element to be found. 325 \return An iterator referring to the found element, or End(), if the 326 set doesn't contain any element with the given value. 327 */ 328 _VECTOR_SET_TEMPLATE_LIST 329 _VECTOR_SET_CLASS_TYPE::ConstIterator 330 _VECTOR_SET_CLASS_NAME::Find(const Value &value) const 331 { 332 bool exists = false; 333 int32 index = _FindInsertionIndex(value, exists); 334 if (!exists) 335 return fElements.End(); 336 return fElements.IteratorForIndex(index); 337 } 338 339 // FindClose 340 /*! \brief Returns an iterator referring to the element with a value closest 341 to the specified one. 342 343 If the set contains an element with the specified value, an iterator 344 to it is returned. Otherwise \a less indicates whether an iterator to 345 the directly smaller or greater element shall be returned. 346 347 If \a less is \c true and the first element in the set has a greater 348 value than the specified one, End() is returned. Similarly, when \a less 349 is \c false and the last element is smaller. Find() invoked on an empty 350 set always returns End(). 351 352 Note, that the element order used for the set is specified as template 353 argument to the class. Default is ascending order. Descending order 354 inverts the meaning of \a less, i.e. if \c true, greater values will 355 be returned, since they are smaller ones according to the order. 356 357 \param value The value of the element to be found. 358 \return An iterator referring to the found element, or End(), if the 359 set doesn't contain any element with the given value or a close 360 one according to \a less. 361 */ 362 _VECTOR_SET_TEMPLATE_LIST 363 _VECTOR_SET_CLASS_TYPE::Iterator 364 _VECTOR_SET_CLASS_NAME::FindClose(const Value &value, bool less) 365 { 366 bool exists = false; 367 int32 index = _FindInsertionIndex(value, exists); 368 // If not found, the index _FindInsertionIndex() returns will point to 369 // an element with a greater value or to End(). So, no special handling 370 // is needed for !less. 371 if (exists || !less) 372 return fElements.IteratorForIndex(index); 373 // An element with a smaller value is desired. The previous one (if any) 374 // will do. 375 if (index > 0) 376 return fElements.IteratorForIndex(index - 1); 377 return fElements.End(); 378 } 379 380 // FindClose 381 /*! \brief Returns an iterator referring to the element with a value closest 382 to the specified one. 383 384 If the set contains an element with the specified value, an iterator 385 to it is returned. Otherwise \a less indicates whether an iterator to 386 the directly smaller or greater element shall be returned. 387 388 If \a less is \c true and the first element in the set has a greater 389 value than the specified one, End() is returned. Similarly, when \a less 390 is \c false and the last element is smaller. Find() invoked on an empty 391 set always returns End(). 392 393 Note, that the element order used for the set is specified as template 394 argument to the class. Default is ascending order. Descending order 395 inverts the meaning of \a less, i.e. if \c true, greater values will 396 be returned, since they are smaller ones according to the order. 397 398 \param value The value of the element to be found. 399 \return An iterator referring to the found element, or End(), if the 400 set doesn't contain any element with the given value or a close 401 one according to \a less. 402 */ 403 _VECTOR_SET_TEMPLATE_LIST 404 _VECTOR_SET_CLASS_TYPE::ConstIterator 405 _VECTOR_SET_CLASS_NAME::FindClose(const Value &value, bool less) const 406 { 407 bool exists = false; 408 int32 index = _FindInsertionIndex(value, exists); 409 // If not found, the index _FindInsertionIndex() returns will point to 410 // an element with a greater value or to End(). So, no special handling 411 // is needed for !less. 412 if (exists || !less) 413 return fElements.IteratorForIndex(index); 414 // An element with a smaller value is desired. The previous one (if any) 415 // will do. 416 if (index > 0) 417 return fElements.IteratorForIndex(index - 1); 418 return fElements.End(); 419 } 420 421 // _FindInsertionIndex 422 /*! \brief Finds the index at which the element with the supplied value is 423 located or at which it would need to be inserted. 424 \param value The value. 425 \param exists Is set to \c true, if the set does already contain an 426 element with that value. 427 \return The index at which the element with the supplied value is 428 located or at which it would need to be inserted. 429 */ 430 _VECTOR_SET_TEMPLATE_LIST 431 int32 432 _VECTOR_SET_CLASS_NAME::_FindInsertionIndex(const Value &value, 433 bool &exists) const 434 { 435 // binary search 436 int32 lower = 0; 437 int32 upper = Count(); 438 while (lower < upper) { 439 int32 mid = (lower + upper) / 2; 440 int cmp = fCompare(fElements[mid], value); 441 if (cmp < 0) 442 lower = mid + 1; 443 else 444 upper = mid; 445 } 446 exists = (lower < Count() && fCompare(value, fElements[lower]) == 0); 447 return lower; 448 } 449 450 451 // element orders 452 453 namespace VectorSetOrder { 454 455 // Ascending 456 /*! \brief A compare function object implying and ascending order. 457 458 The < operator must be defined on the template argument. 459 */ 460 template<typename Value> 461 class Ascending { 462 public: 463 inline int operator()(const Value &a, const Value &b) const 464 { 465 if (a < b) 466 return -1; 467 else if (b < a) 468 return 1; 469 return 0; 470 } 471 }; 472 473 // Descending 474 /*! \brief A compare function object implying and descending order. 475 476 The < operator must be defined on the template argument. 477 */ 478 template<typename Value> 479 class Descending { 480 public: 481 inline int operator()(const Value &a, const Value &b) const 482 { 483 if (a < b) 484 return -1; 485 else if (b < a) 486 return 1; 487 return 0; 488 } 489 }; 490 491 } // namespace VectorSetOrder 492 493 #endif // _VECTOR_SET_H 494