1 /* 2 Open Tracker License 3 4 Terms and Conditions 5 6 Copyright (c) 1991-2000, Be Incorporated. All rights reserved. 7 8 Permission is hereby granted, free of charge, to any person obtaining a copy of 9 this software and associated documentation files (the "Software"), to deal in 10 the Software without restriction, including without limitation the rights to 11 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies 12 of the Software, and to permit persons to whom the Software is furnished to do 13 so, subject to the following conditions: 14 15 The above copyright notice and this permission notice applies to all licensees 16 and shall be included in all copies or substantial portions of the Software. 17 18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF TITLE, MERCHANTABILITY, 20 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 21 BE INCORPORATED BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 22 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF, OR IN CONNECTION 23 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 24 25 Except as contained in this notice, the name of Be Incorporated shall not be 26 used in advertising or otherwise to promote the sale, use or other dealings in 27 this Software without prior written authorization from Be Incorporated. 28 29 Tracker(TM), Be(R), BeOS(R), and BeIA(TM) are trademarks or registered trademarks 30 of Be Incorporated in the United States and other countries. Other brand product 31 names are registered trademarks or trademarks of their respective holders. 32 All rights reserved. 33 */ 34 #ifndef _OBJECT_LIST_H 35 #define _OBJECT_LIST_H 36 37 38 #include <new> 39 40 #include <List.h> 41 #include <SupportDefs.h> 42 43 44 // 45 // ObjectList is a wrapper around BList that adds type safety, 46 // optional object ownership, search, insert operations, etc. 47 // 48 49 template<class T> class BObjectList; 50 51 52 template<class T> 53 struct UnaryPredicate { 54 virtual int operator()(const T *) const 55 // virtual could be avoided here if FindBinaryInsertionIndex, 56 // etc. were member template functions 57 { 58 return 0; 59 } 60 61 private: 62 static int _unary_predicate_glue(const void *item, void *context); 63 64 friend class BObjectList<T>; 65 }; 66 67 68 template<class T> 69 int 70 UnaryPredicate<T>::_unary_predicate_glue(const void *item, void *context) 71 { 72 return ((UnaryPredicate<T> *)context)->operator()((const T *)item); 73 } 74 75 76 class _PointerList_ : public BList { 77 public: 78 _PointerList_(const _PointerList_ &list); 79 _PointerList_(int32 itemsPerBlock = 20, bool owning = false); 80 ~_PointerList_(); 81 82 typedef void *(* GenericEachFunction)(void *, void *); 83 typedef int (* GenericCompareFunction)(const void *, const void *); 84 typedef int (* GenericCompareFunctionWithState)(const void *, const void *, 85 void *); 86 typedef int (* UnaryPredicateGlue)(const void *, void *); 87 88 void *EachElement(GenericEachFunction, void *); 89 void SortItems(GenericCompareFunction); 90 void SortItems(GenericCompareFunctionWithState, void *state); 91 void HSortItems(GenericCompareFunction); 92 void HSortItems(GenericCompareFunctionWithState, void *state); 93 94 void *BinarySearch(const void *, GenericCompareFunction) const; 95 void *BinarySearch(const void *, GenericCompareFunctionWithState, 96 void *state) const; 97 98 int32 BinarySearchIndex(const void *, GenericCompareFunction) const; 99 int32 BinarySearchIndex(const void *, GenericCompareFunctionWithState, 100 void *state) const; 101 int32 BinarySearchIndexByPredicate(const void *, UnaryPredicateGlue) const; 102 103 bool Owning() const; 104 bool ReplaceItem(int32, void *); 105 bool MoveItem(int32 from, int32 to); 106 107 protected: 108 bool owning; 109 110 }; 111 112 113 template<class T> 114 class BObjectList : private _PointerList_ { 115 public: 116 // iteration and sorting 117 typedef T* (*EachFunction)(T*, void*); 118 typedef const T* (*ConstEachFunction)(const T*, void*); 119 typedef int (*CompareFunction)(const T*, const T*); 120 typedef int (*CompareFunctionWithState)(const T*, const T*, 121 void* state); 122 123 BObjectList(int32 itemsPerBlock = 20, 124 bool owning = false); 125 BObjectList(const BObjectList& list); 126 // clones list; if list is owning, makes 127 // copies of all the items 128 129 virtual ~BObjectList(); 130 131 BObjectList& operator=(const BObjectList& list); 132 // clones list; if list is owning, makes 133 // copies of all the items 134 135 // adding and removing 136 bool AddItem(T*); 137 bool AddItem(T*, int32); 138 bool AddList(BObjectList*); 139 bool AddList(BObjectList*, int32); 140 141 bool RemoveItem(T*, bool deleteIfOwning = true); 142 // if owning, deletes the removed item 143 T* RemoveItemAt(int32); 144 // returns the removed item 145 146 void MakeEmpty(bool deleteIfOwning = true); 147 148 // item access 149 T* ItemAt(int32) const; 150 151 bool ReplaceItem(int32 index, T*); 152 // if list is owning, deletes the item 153 // at <index> first 154 T* SwapWithItem(int32 index, T* newItem); 155 // same as ReplaceItem, except does not 156 // delete old item at <index>, returns it 157 // instead 158 bool MoveItem(int32 from, int32 to); 159 160 T* FirstItem() const; 161 T* LastItem() const; 162 163 // misc. getters 164 int32 IndexOf(const T*) const; 165 bool HasItem(const T*) const; 166 bool IsEmpty() const; 167 int32 CountItems() const; 168 169 T* EachElement(EachFunction, void*); 170 const T* EachElement(ConstEachFunction, void*) const; 171 172 void SortItems(CompareFunction); 173 void SortItems(CompareFunctionWithState, 174 void* state); 175 void HSortItems(CompareFunction); 176 void HSortItems(CompareFunctionWithState, 177 void* state); 178 179 // linear search, returns first item that 180 // matches predicate 181 const T* FindIf(const UnaryPredicate<T>&) const; 182 T* FindIf(const UnaryPredicate<T>&); 183 184 // list must be sorted with CompareFunction for 185 // these to work 186 T* BinarySearch(const T&, CompareFunction) const; 187 T* BinarySearch(const T&, CompareFunctionWithState, 188 void* state) const; 189 190 template<typename Key> 191 T* BinarySearchByKey(const Key& key, 192 int (*compare)(const Key*, const T*)) const; 193 194 template<typename Key> 195 T* BinarySearchByKey(const Key& key, 196 int (*compare)(const Key*, const T*, void*), 197 void* state) const; 198 199 int32 BinarySearchIndex(const T&item, 200 CompareFunction compare) const; 201 int32 BinarySearchIndex(const T&item, 202 CompareFunctionWithState compare, 203 void* state) const; 204 205 template<typename Key> 206 int32 BinarySearchIndexByKey(const Key& key, 207 int (*compare)(const Key*, const T*)) const; 208 209 // Binary insertion - list must be sorted with 210 // CompareFunction for these to work 211 212 // simple insert 213 bool BinaryInsert(T*, CompareFunction); 214 bool BinaryInsert(T*, CompareFunctionWithState, 215 void* state); 216 bool BinaryInsert(T*, const UnaryPredicate<T>&); 217 218 // unique insert, returns false if item already 219 // in list 220 bool BinaryInsertUnique(T*, CompareFunction); 221 bool BinaryInsertUnique(T*, CompareFunctionWithState, 222 void* state); 223 bool BinaryInsertUnique(T*, 224 const UnaryPredicate<T>&); 225 226 // insert a copy of the item, returns new 227 // inserted item 228 T* BinaryInsertCopy(const T& copyThis, 229 CompareFunction); 230 T* BinaryInsertCopy(const T& copyThis, 231 CompareFunctionWithState, void* state); 232 233 // insert a copy of the item if not in list 234 // already returns new inserted item or existing 235 // item in case of a conflict 236 T* BinaryInsertCopyUnique(const T& copyThis, 237 CompareFunction); 238 T* BinaryInsertCopyUnique(const T& copyThis, 239 CompareFunctionWithState, void* state); 240 241 int32 FindBinaryInsertionIndex( 242 const UnaryPredicate<T>&, 243 bool* alreadyInList = 0) const; 244 // returns either the index into which a new 245 // item should be inserted or index of an 246 // existing item that matches the predicate 247 248 class Private; 249 private: 250 friend class Private; 251 252 void _SetItem(int32, T*); 253 }; 254 255 256 template<class Item, class Result, class Param1> 257 Result 258 WhileEachListItem(BObjectList<Item>* list, Result (Item::*func)(Param1), 259 Param1 p1) 260 { 261 Result result = 0; 262 int32 count = list->CountItems(); 263 264 for (int32 index = 0; index < count; index++) { 265 if ((result = (list->ItemAt(index)->*func)(p1)) != 0) 266 break; 267 } 268 269 return result; 270 } 271 272 273 template<class Item, class Result, class Param1> 274 Result 275 WhileEachListItem(BObjectList<Item>* list, Result (*func)(Item*, Param1), 276 Param1 p1) 277 { 278 Result result = 0; 279 int32 count = list->CountItems(); 280 281 for (int32 index = 0; index < count; index++) { 282 if ((result = (*func)(list->ItemAt(index), p1)) != 0) 283 break; 284 } 285 286 return result; 287 } 288 289 290 template<class Item, class Result, class Param1, class Param2> 291 Result 292 WhileEachListItem(BObjectList<Item>* list, Result (Item::*func)(Param1, Param2), 293 Param1 p1, Param2 p2) 294 { 295 Result result = 0; 296 int32 count = list->CountItems(); 297 298 for (int32 index = 0; index < count; index++) { 299 if ((result = (list->ItemAt(index)->*func)(p1, p2)) != 0) 300 break; 301 } 302 303 return result; 304 } 305 306 307 template<class Item, class Result, class Param1, class Param2> 308 Result 309 WhileEachListItem(BObjectList<Item>* list, 310 Result (*func)(Item*, Param1, Param2), Param1 p1, Param2 p2) 311 { 312 Result result = 0; 313 int32 count = list->CountItems(); 314 315 for (int32 index = 0; index < count; index++) { 316 if ((result = (*func)(list->ItemAt(index), p1, p2)) != 0) 317 break; 318 } 319 320 return result; 321 } 322 323 324 template<class Item, class Result, class Param1, class Param2, class Param3, 325 class Param4> 326 Result 327 WhileEachListItem(BObjectList<Item>* list, 328 Result (*func)(Item*, Param1, Param2, Param3, Param4), Param1 p1, Param2 p2, 329 Param3 p3, Param4 p4) 330 { 331 Result result = 0; 332 int32 count = list->CountItems(); 333 334 for (int32 index = 0; index < count; index++) { 335 if ((result = (*func)(list->ItemAt(index), p1, p2, p3, p4)) != 0) 336 break; 337 } 338 339 return result; 340 } 341 342 343 template<class Item, class Result> 344 void 345 EachListItemIgnoreResult(BObjectList<Item>* list, Result (Item::*func)()) 346 { 347 int32 count = list->CountItems(); 348 for (int32 index = 0; index < count; index++) 349 (list->ItemAt(index)->*func)(); 350 } 351 352 353 template<class Item, class Param1> 354 void 355 EachListItem(BObjectList<Item>* list, void (*func)(Item*, Param1), Param1 p1) 356 { 357 int32 count = list->CountItems(); 358 for (int32 index = 0; index < count; index++) 359 (func)(list->ItemAt(index), p1); 360 } 361 362 363 template<class Item, class Param1, class Param2> 364 void 365 EachListItem(BObjectList<Item>* list, void (Item::*func)(Param1, Param2), 366 Param1 p1, Param2 p2) 367 { 368 int32 count = list->CountItems(); 369 for (int32 index = 0; index < count; index++) 370 (list->ItemAt(index)->*func)(p1, p2); 371 } 372 373 374 template<class Item, class Param1, class Param2> 375 void 376 EachListItem(BObjectList<Item>* list, void (*func)(Item*,Param1, Param2), 377 Param1 p1, Param2 p2) 378 { 379 int32 count = list->CountItems(); 380 for (int32 index = 0; index < count; index++) 381 (func)(list->ItemAt(index), p1, p2); 382 } 383 384 385 template<class Item, class Param1, class Param2, class Param3> 386 void 387 EachListItem(BObjectList<Item>* list, 388 void (*func)(Item*,Param1, Param2, Param3), Param1 p1, Param2 p2, Param3 p3) 389 { 390 int32 count = list->CountItems(); 391 for (int32 index = 0; index < count; index++) 392 (func)(list->ItemAt(index), p1, p2, p3); 393 } 394 395 396 template<class Item, class Param1, class Param2, class Param3, class Param4> 397 void 398 EachListItem(BObjectList<Item>* list, 399 void (*func)(Item*,Param1, Param2, Param3, Param4), Param1 p1, Param2 p2, 400 Param3 p3, Param4 p4) 401 { 402 int32 count = list->CountItems(); 403 for (int32 index = 0; index < count; index++) 404 (func)(list->ItemAt(index), p1, p2, p3, p4); 405 } 406 407 408 // inline code 409 410 411 inline bool 412 _PointerList_::Owning() const 413 { 414 return owning; 415 } 416 417 418 template<class T> 419 BObjectList<T>::BObjectList(int32 itemsPerBlock, bool owning) 420 : 421 _PointerList_(itemsPerBlock, owning) 422 { 423 } 424 425 426 template<class T> 427 BObjectList<T>::BObjectList(const BObjectList<T>& list) 428 : 429 _PointerList_(list) 430 { 431 owning = list.owning; 432 if (owning) { 433 // make our own copies in an owning list 434 int32 count = list.CountItems(); 435 for (int32 index = 0; index < count; index++) { 436 T* item = list.ItemAt(index); 437 if (item) 438 item = new (std::nothrow) T(*item); 439 _SetItem(index, item); 440 } 441 } 442 } 443 444 445 template<class T> 446 BObjectList<T>::~BObjectList() 447 { 448 if (Owning()) { 449 // have to nuke elements first 450 MakeEmpty(); 451 } 452 } 453 454 455 template<class T> 456 BObjectList<T>& 457 BObjectList<T>::operator=(const BObjectList<T>& list) 458 { 459 owning = list.owning; 460 BObjectList<T> &result = (BObjectList<T>&)_PointerList_::operator=(list); 461 if (owning) { 462 // make our own copies in an owning list 463 int32 count = list.CountItems(); 464 for (int32 index = 0; index < count; index++) { 465 T* item = list.ItemAt(index); 466 if (item) 467 item = new (std::nothrow) T(*item); 468 _SetItem(index, item); 469 } 470 } 471 return result; 472 } 473 474 475 template<class T> 476 bool 477 BObjectList<T>::AddItem(T* item) 478 { 479 // need to cast to void* to make T work for const pointers 480 return _PointerList_::AddItem((void*)item); 481 } 482 483 484 template<class T> 485 bool 486 BObjectList<T>::AddItem(T* item, int32 index) 487 { 488 return _PointerList_::AddItem((void*)item, index); 489 } 490 491 492 template<class T> 493 bool 494 BObjectList<T>::AddList(BObjectList<T>* list) 495 { 496 return _PointerList_::AddList(list); 497 } 498 499 500 template<class T> 501 bool 502 BObjectList<T>::AddList(BObjectList<T>* list, int32 index) 503 { 504 return _PointerList_::AddList(list, index); 505 } 506 507 508 template<class T> 509 bool 510 BObjectList<T>::RemoveItem(T* item, bool deleteIfOwning) 511 { 512 bool result = _PointerList_::RemoveItem((void*)item); 513 514 if (result && Owning() && deleteIfOwning) 515 delete item; 516 517 return result; 518 } 519 520 521 template<class T> 522 T* 523 BObjectList<T>::RemoveItemAt(int32 index) 524 { 525 return (T*)_PointerList_::RemoveItem(index); 526 } 527 528 529 template<class T> 530 inline T* 531 BObjectList<T>::ItemAt(int32 index) const 532 { 533 return (T*)_PointerList_::ItemAt(index); 534 } 535 536 537 template<class T> 538 bool 539 BObjectList<T>::ReplaceItem(int32 index, T* item) 540 { 541 if (owning) 542 delete ItemAt(index); 543 544 return _PointerList_::ReplaceItem(index, (void*)item); 545 } 546 547 548 template<class T> 549 T* 550 BObjectList<T>::SwapWithItem(int32 index, T* item) 551 { 552 T* result = ItemAt(index); 553 _PointerList_::ReplaceItem(index, (void*)item); 554 555 return result; 556 } 557 558 559 template<class T> 560 bool 561 BObjectList<T>::MoveItem(int32 from, int32 to) 562 { 563 return _PointerList_::MoveItem(from, to); 564 } 565 566 567 template<class T> 568 void 569 BObjectList<T>::_SetItem(int32 index, T* newItem) 570 { 571 _PointerList_::ReplaceItem(index, (void*)newItem); 572 } 573 574 575 template<class T> 576 int32 577 BObjectList<T>::IndexOf(const T* item) const 578 { 579 return _PointerList_::IndexOf((void*)item); 580 } 581 582 583 template<class T> 584 T* 585 BObjectList<T>::FirstItem() const 586 { 587 return (T*)_PointerList_::FirstItem(); 588 } 589 590 591 template<class T> 592 T* 593 BObjectList<T>::LastItem() const 594 { 595 return (T*)_PointerList_::LastItem(); 596 } 597 598 599 template<class T> 600 bool 601 BObjectList<T>::HasItem(const T* item) const 602 { 603 return _PointerList_::HasItem((void*)item); 604 } 605 606 607 template<class T> 608 bool 609 BObjectList<T>::IsEmpty() const 610 { 611 return _PointerList_::IsEmpty(); 612 } 613 614 615 template<class T> 616 int32 617 BObjectList<T>::CountItems() const 618 { 619 return _PointerList_::CountItems(); 620 } 621 622 623 template<class T> 624 void 625 BObjectList<T>::MakeEmpty(bool deleteIfOwning) 626 { 627 if (owning && deleteIfOwning) { 628 int32 count = CountItems(); 629 for (int32 index = 0; index < count; index++) 630 delete ItemAt(index); 631 } 632 _PointerList_::MakeEmpty(); 633 } 634 635 636 template<class T> 637 T* 638 BObjectList<T>::EachElement(EachFunction func, void* params) 639 { 640 return (T*)_PointerList_::EachElement((GenericEachFunction)func, params); 641 } 642 643 644 template<class T> 645 const T* 646 BObjectList<T>::EachElement(ConstEachFunction func, void* params) const 647 { 648 return (const T*) 649 const_cast<BObjectList<T>*>(this)->_PointerList_::EachElement( 650 (GenericEachFunction)func, params); 651 } 652 653 template<class T> 654 const T* 655 BObjectList<T>::FindIf(const UnaryPredicate<T>& predicate) const 656 { 657 int32 count = CountItems(); 658 for (int32 index = 0; index < count; index++) { 659 if (predicate.operator()(ItemAt(index)) == 0) 660 return ItemAt(index); 661 } 662 return 0; 663 } 664 665 template<class T> 666 T* 667 BObjectList<T>::FindIf(const UnaryPredicate<T>& predicate) 668 { 669 int32 count = CountItems(); 670 for (int32 index = 0; index < count; index++) { 671 if (predicate.operator()(ItemAt(index)) == 0) 672 return ItemAt(index); 673 } 674 return 0; 675 } 676 677 678 template<class T> 679 void 680 BObjectList<T>::SortItems(CompareFunction function) 681 { 682 _PointerList_::SortItems((GenericCompareFunction)function); 683 } 684 685 686 template<class T> 687 void 688 BObjectList<T>::SortItems(CompareFunctionWithState function, void* state) 689 { 690 _PointerList_::SortItems((GenericCompareFunctionWithState)function, state); 691 } 692 693 694 template<class T> 695 void 696 BObjectList<T>::HSortItems(CompareFunction function) 697 { 698 _PointerList_::HSortItems((GenericCompareFunction)function); 699 } 700 701 702 template<class T> 703 void 704 BObjectList<T>::HSortItems(CompareFunctionWithState function, void* state) 705 { 706 _PointerList_::HSortItems((GenericCompareFunctionWithState)function, state); 707 } 708 709 710 template<class T> 711 T* 712 BObjectList<T>::BinarySearch(const T& key, CompareFunction func) const 713 { 714 return (T*)_PointerList_::BinarySearch(&key, (GenericCompareFunction)func); 715 } 716 717 718 template<class T> 719 T* 720 BObjectList<T>::BinarySearch(const T& key, CompareFunctionWithState func, 721 void* state) const 722 { 723 return (T*)_PointerList_::BinarySearch(&key, 724 (GenericCompareFunctionWithState)func, state); 725 } 726 727 728 template<class T> 729 template<typename Key> 730 T* 731 BObjectList<T>::BinarySearchByKey(const Key& key, 732 int (*compare)(const Key*, const T*)) const 733 { 734 return (T*)_PointerList_::BinarySearch(&key, 735 (GenericCompareFunction)compare); 736 } 737 738 739 template<class T> 740 template<typename Key> 741 T* 742 BObjectList<T>::BinarySearchByKey(const Key &key, 743 int (*compare)(const Key*, const T*, void*), void* state) const 744 { 745 return (T*)_PointerList_::BinarySearch(&key, 746 (GenericCompareFunctionWithState)compare, state); 747 } 748 749 750 template<class T> 751 int32 752 BObjectList<T>::BinarySearchIndex(const T& item, CompareFunction compare) const 753 { 754 return _PointerList_::BinarySearchIndex(&item, 755 (GenericCompareFunction)compare); 756 } 757 758 759 template<class T> 760 int32 761 BObjectList<T>::BinarySearchIndex(const T& item, 762 CompareFunctionWithState compare, void* state) const 763 { 764 return _PointerList_::BinarySearchIndex(&item, 765 (GenericCompareFunctionWithState)compare, state); 766 } 767 768 769 template<class T> 770 template<typename Key> 771 int32 772 BObjectList<T>::BinarySearchIndexByKey(const Key& key, 773 int (*compare)(const Key*, const T*)) const 774 { 775 return _PointerList_::BinarySearchIndex(&key, 776 (GenericCompareFunction)compare); 777 } 778 779 780 template<class T> 781 bool 782 BObjectList<T>::BinaryInsert(T* item, CompareFunction func) 783 { 784 int32 index = _PointerList_::BinarySearchIndex(item, 785 (GenericCompareFunction)func); 786 if (index >= 0) { 787 // already in list, add after existing 788 return AddItem(item, index + 1); 789 } 790 791 return AddItem(item, -index - 1); 792 } 793 794 795 template<class T> 796 bool 797 BObjectList<T>::BinaryInsert(T* item, CompareFunctionWithState func, 798 void* state) 799 { 800 int32 index = _PointerList_::BinarySearchIndex(item, 801 (GenericCompareFunctionWithState)func, state); 802 if (index >= 0) { 803 // already in list, add after existing 804 return AddItem(item, index + 1); 805 } 806 807 return AddItem(item, -index - 1); 808 } 809 810 811 template<class T> 812 bool 813 BObjectList<T>::BinaryInsertUnique(T* item, CompareFunction func) 814 { 815 int32 index = _PointerList_::BinarySearchIndex(item, 816 (GenericCompareFunction)func); 817 if (index >= 0) 818 return false; 819 820 return AddItem(item, -index - 1); 821 } 822 823 824 template<class T> 825 bool 826 BObjectList<T>::BinaryInsertUnique(T* item, CompareFunctionWithState func, 827 void* state) 828 { 829 int32 index = _PointerList_::BinarySearchIndex(item, 830 (GenericCompareFunctionWithState)func, state); 831 if (index >= 0) 832 return false; 833 834 return AddItem(item, -index - 1); 835 } 836 837 838 template<class T> 839 T* 840 BObjectList<T>::BinaryInsertCopy(const T& copyThis, CompareFunction func) 841 { 842 int32 index = _PointerList_::BinarySearchIndex(©This, 843 (GenericCompareFunction)func); 844 845 if (index >= 0) 846 index++; 847 else 848 index = -index - 1; 849 850 T* newItem = new (std::nothrow) T(copyThis); 851 AddItem(newItem, index); 852 return newItem; 853 } 854 855 856 template<class T> 857 T* 858 BObjectList<T>::BinaryInsertCopy(const T& copyThis, 859 CompareFunctionWithState func, void* state) 860 { 861 int32 index = _PointerList_::BinarySearchIndex(©This, 862 (GenericCompareFunctionWithState)func, state); 863 864 if (index >= 0) 865 index++; 866 else 867 index = -index - 1; 868 869 T* newItem = new (std::nothrow) T(copyThis); 870 AddItem(newItem, index); 871 return newItem; 872 } 873 874 875 template<class T> 876 T* 877 BObjectList<T>::BinaryInsertCopyUnique(const T& copyThis, CompareFunction func) 878 { 879 int32 index = _PointerList_::BinarySearchIndex(©This, 880 (GenericCompareFunction)func); 881 if (index >= 0) 882 return ItemAt(index); 883 884 index = -index - 1; 885 T* newItem = new (std::nothrow) T(copyThis); 886 AddItem(newItem, index); 887 return newItem; 888 } 889 890 891 template<class T> 892 T* 893 BObjectList<T>::BinaryInsertCopyUnique(const T& copyThis, 894 CompareFunctionWithState func, void* state) 895 { 896 int32 index = _PointerList_::BinarySearchIndex(©This, 897 (GenericCompareFunctionWithState)func, state); 898 if (index >= 0) 899 return ItemAt(index); 900 901 index = -index - 1; 902 T* newItem = new (std::nothrow) T(copyThis); 903 AddItem(newItem, index); 904 return newItem; 905 } 906 907 908 template<class T> 909 int32 910 BObjectList<T>::FindBinaryInsertionIndex(const UnaryPredicate<T>& pred, 911 bool* alreadyInList) const 912 { 913 int32 index = _PointerList_::BinarySearchIndexByPredicate(&pred, 914 (UnaryPredicateGlue)&UnaryPredicate<T>::_unary_predicate_glue); 915 916 if (alreadyInList) 917 *alreadyInList = index >= 0; 918 919 if (index < 0) 920 index = -index - 1; 921 922 return index; 923 } 924 925 926 template<class T> 927 bool 928 BObjectList<T>::BinaryInsert(T* item, const UnaryPredicate<T>& pred) 929 { 930 return AddItem(item, FindBinaryInsertionIndex(pred)); 931 } 932 933 934 template<class T> 935 bool 936 BObjectList<T>::BinaryInsertUnique(T* item, const UnaryPredicate<T>& pred) 937 { 938 bool alreadyInList; 939 int32 index = FindBinaryInsertionIndex(pred, &alreadyInList); 940 if (alreadyInList) 941 return false; 942 943 AddItem(item, index); 944 return true; 945 } 946 947 948 #endif // _OBJECT_LIST_H 949