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