1/* 2Open Tracker License 3 4Terms and Conditions 5 6Copyright (c) 1991-2000, Be Incorporated. All rights reserved. 7 8Permission is hereby granted, free of charge, to any person obtaining a copy of 9this software and associated documentation files (the "Software"), to deal in 10the Software without restriction, including without limitation the rights to 11use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies 12of the Software, and to permit persons to whom the Software is furnished to do 13so, subject to the following conditions: 14 15The above copyright notice and this permission notice applies to all licensees 16and shall be included in all copies or substantial portions of the Software. 17 18THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 19IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF TITLE, MERCHANTABILITY, 20FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 21BE INCORPORATED BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 22AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF, OR IN CONNECTION 23WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 24 25Except as contained in this notice, the name of Be Incorporated shall not be 26used in advertising or otherwise to promote the sale, use or other dealings in 27this Software without prior written authorization from Be Incorporated. 28 29Tracker(TM), Be(R), BeOS(R), and BeIA(TM) are trademarks or registered trademarks 30of Be Incorporated in the United States and other countries. Other brand product 31names are registered trademarks or trademarks of their respective holders. 32All 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 49template<class T> class BObjectList; 50 51 52template<class T> 53struct 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 60private: 61 static int _unary_predicate_glue(const void *item, void *context); 62 63 friend class BObjectList<T>; 64}; 65 66 67template<class T> 68int 69UnaryPredicate<T>::_unary_predicate_glue(const void *item, void *context) 70{ 71 return ((UnaryPredicate<T> *)context)->operator()((const T *)item); 72} 73 74 75class _PointerList_ : public BList { 76public: 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 bool MoveItem(int32 from, int32 to); 105 106protected: 107 bool owning; 108 109}; 110 111 112template<class T> 113class BObjectList : private _PointerList_ { 114public: 115 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; 249private: 250 friend class Private; 251 252 void _SetItem(int32, T*); 253}; 254 255 256template<class Item, class Result, class Param1> 257Result 258WhileEachListItem(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 273template<class Item, class Result, class Param1> 274Result 275WhileEachListItem(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 290template<class Item, class Result, class Param1, class Param2> 291Result 292WhileEachListItem(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 307template<class Item, class Result, class Param1, class Param2> 308Result 309WhileEachListItem(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 324template<class Item, class Result, class Param1, class Param2, class Param3, 325 class Param4> 326Result 327WhileEachListItem(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 343template<class Item, class Result> 344void 345EachListItemIgnoreResult(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 353template<class Item, class Param1> 354void 355EachListItem(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 363template<class Item, class Param1, class Param2> 364void 365EachListItem(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 374template<class Item, class Param1, class Param2> 375void 376EachListItem(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 385template<class Item, class Param1, class Param2, class Param3> 386void 387EachListItem(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 396template<class Item, class Param1, class Param2, class Param3, class Param4> 397void 398EachListItem(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 411inline bool 412_PointerList_::Owning() const 413{ 414 return owning; 415} 416 417 418template<class T> 419BObjectList<T>::BObjectList(int32 itemsPerBlock, bool owning) 420 : 421 _PointerList_(itemsPerBlock, owning) 422{ 423} 424 425 426template<class T> 427BObjectList<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 445template<class T> 446BObjectList<T>::~BObjectList() 447{ 448 if (Owning()) { 449 // have to nuke elements first 450 MakeEmpty(); 451 } 452} 453 454 455template<class T> 456BObjectList<T>& 457BObjectList<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 475template<class T> 476bool 477BObjectList<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 484template<class T> 485bool 486BObjectList<T>::AddItem(T* item, int32 atIndex) 487{ 488 return _PointerList_::AddItem((void*)item, atIndex); 489} 490 491 492template<class T> 493bool 494BObjectList<T>::AddList(BObjectList<T>* newItems) 495{ 496 return _PointerList_::AddList(newItems); 497} 498 499 500template<class T> 501bool 502BObjectList<T>::AddList(BObjectList<T>* newItems, int32 atIndex) 503{ 504 return _PointerList_::AddList(newItems, atIndex); 505} 506 507 508template<class T> 509bool 510BObjectList<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 521template<class T> 522T* 523BObjectList<T>::RemoveItemAt(int32 index) 524{ 525 return (T*)_PointerList_::RemoveItem(index); 526} 527 528 529template<class T> 530inline T* 531BObjectList<T>::ItemAt(int32 index) const 532{ 533 return (T*)_PointerList_::ItemAt(index); 534} 535 536 537template<class T> 538bool 539BObjectList<T>::ReplaceItem(int32 index, T* item) 540{ 541 if (owning) 542 delete ItemAt(index); 543 return _PointerList_::ReplaceItem(index, (void*)item); 544} 545 546 547template<class T> 548T* 549BObjectList<T>::SwapWithItem(int32 index, T* newItem) 550{ 551 T* result = ItemAt(index); 552 _PointerList_::ReplaceItem(index, (void*)newItem); 553 return result; 554} 555 556 557template<class T> 558bool 559BObjectList<T>::MoveItem(int32 from, int32 to) 560{ 561 return _PointerList_::MoveItem(from, to); 562} 563 564 565template<class T> 566void 567BObjectList<T>::_SetItem(int32 index, T* newItem) 568{ 569 _PointerList_::ReplaceItem(index, (void*)newItem); 570} 571 572 573template<class T> 574int32 575BObjectList<T>::IndexOf(const T* item) const 576{ 577 return _PointerList_::IndexOf((void*)item); 578} 579 580 581template<class T> 582T* 583BObjectList<T>::FirstItem() const 584{ 585 return (T*)_PointerList_::FirstItem(); 586} 587 588 589template<class T> 590T* 591BObjectList<T>::LastItem() const 592{ 593 return (T*)_PointerList_::LastItem(); 594} 595 596 597template<class T> 598bool 599BObjectList<T>::HasItem(const T* item) const 600{ 601 return _PointerList_::HasItem((void*)item); 602} 603 604 605template<class T> 606bool 607BObjectList<T>::IsEmpty() const 608{ 609 return _PointerList_::IsEmpty(); 610} 611 612 613template<class T> 614int32 615BObjectList<T>::CountItems() const 616{ 617 return _PointerList_::CountItems(); 618} 619 620 621template<class T> 622void 623BObjectList<T>::MakeEmpty(bool deleteIfOwning) 624{ 625 if (owning && deleteIfOwning) { 626 int32 count = CountItems(); 627 for (int32 index = 0; index < count; index++) 628 delete ItemAt(index); 629 } 630 _PointerList_::MakeEmpty(); 631} 632 633 634template<class T> 635T* 636BObjectList<T>::EachElement(EachFunction func, void* params) 637{ 638 return (T*)_PointerList_::EachElement((GenericEachFunction)func, params); 639} 640 641 642template<class T> 643const T* 644BObjectList<T>::EachElement(ConstEachFunction func, void* params) const 645{ 646 return (const T*) 647 const_cast<BObjectList<T>*>(this)->_PointerList_::EachElement( 648 (GenericEachFunction)func, params); 649} 650 651template<class T> 652const T* 653BObjectList<T>::FindIf(const UnaryPredicate<T>& predicate) const 654{ 655 int32 count = CountItems(); 656 for (int32 index = 0; index < count; index++) { 657 if (predicate.operator()(ItemAt(index)) == 0) 658 return ItemAt(index); 659 } 660 return 0; 661} 662 663template<class T> 664T* 665BObjectList<T>::FindIf(const UnaryPredicate<T>& predicate) 666{ 667 int32 count = CountItems(); 668 for (int32 index = 0; index < count; index++) { 669 if (predicate.operator()(ItemAt(index)) == 0) 670 return ItemAt(index); 671 } 672 return 0; 673} 674 675 676template<class T> 677void 678BObjectList<T>::SortItems(CompareFunction function) 679{ 680 _PointerList_::SortItems((GenericCompareFunction)function); 681} 682 683 684template<class T> 685void 686BObjectList<T>::SortItems(CompareFunctionWithState function, void* state) 687{ 688 _PointerList_::SortItems((GenericCompareFunctionWithState)function, state); 689} 690 691 692template<class T> 693void 694BObjectList<T>::HSortItems(CompareFunction function) 695{ 696 _PointerList_::HSortItems((GenericCompareFunction)function); 697} 698 699 700template<class T> 701void 702BObjectList<T>::HSortItems(CompareFunctionWithState function, void* state) 703{ 704 _PointerList_::HSortItems((GenericCompareFunctionWithState)function, state); 705} 706 707 708template<class T> 709T* 710BObjectList<T>::BinarySearch(const T& key, CompareFunction func) const 711{ 712 return (T*)_PointerList_::BinarySearch(&key, (GenericCompareFunction)func); 713} 714 715template<class T> 716T* 717BObjectList<T>::BinarySearch(const T& key, CompareFunctionWithState func, 718 void* state) const 719{ 720 return (T*)_PointerList_::BinarySearch(&key, 721 (GenericCompareFunctionWithState)func, state); 722} 723 724 725template<class T> 726template<typename Key> 727T* 728BObjectList<T>::BinarySearchByKey(const Key& key, 729 int (*compare)(const Key*, const T*)) const 730{ 731 return (T*)_PointerList_::BinarySearch(&key, 732 (GenericCompareFunction)compare); 733} 734 735 736template<class T> 737template<typename Key> 738T* 739BObjectList<T>::BinarySearchByKey(const Key &key, 740 int (*compare)(const Key*, const T*, void*), void* state) const 741{ 742 return (T*)_PointerList_::BinarySearch(&key, 743 (GenericCompareFunctionWithState)compare, state); 744} 745 746 747template<class T> 748int32 749BObjectList<T>::BinarySearchIndex(const T& item, CompareFunction compare) const 750{ 751 return _PointerList_::BinarySearchIndex(&item, 752 (GenericCompareFunction)compare); 753} 754 755 756template<class T> 757int32 758BObjectList<T>::BinarySearchIndex(const T& item, 759 CompareFunctionWithState compare, void* state) const 760{ 761 return _PointerList_::BinarySearchIndex(&item, 762 (GenericCompareFunctionWithState)compare, state); 763} 764 765 766template<class T> 767template<typename Key> 768int32 769BObjectList<T>::BinarySearchIndexByKey(const Key& key, 770 int (*compare)(const Key*, const T*)) const 771{ 772 return _PointerList_::BinarySearchIndex(&key, 773 (GenericCompareFunction)compare); 774} 775 776 777template<class T> 778bool 779BObjectList<T>::BinaryInsert(T* item, CompareFunction func) 780{ 781 int32 index = _PointerList_::BinarySearchIndex(item, 782 (GenericCompareFunction)func); 783 if (index >= 0) { 784 // already in list, add after existing 785 return AddItem(item, index + 1); 786 } 787 788 return AddItem(item, -index - 1); 789} 790 791 792template<class T> 793bool 794BObjectList<T>::BinaryInsert(T* item, CompareFunctionWithState func, 795 void* state) 796{ 797 int32 index = _PointerList_::BinarySearchIndex(item, 798 (GenericCompareFunctionWithState)func, state); 799 if (index >= 0) { 800 // already in list, add after existing 801 return AddItem(item, index + 1); 802 } 803 804 return AddItem(item, -index - 1); 805} 806 807 808template<class T> 809bool 810BObjectList<T>::BinaryInsertUnique(T* item, CompareFunction func) 811{ 812 int32 index = _PointerList_::BinarySearchIndex(item, 813 (GenericCompareFunction)func); 814 if (index >= 0) 815 return false; 816 817 return AddItem(item, -index - 1); 818} 819 820 821template<class T> 822bool 823BObjectList<T>::BinaryInsertUnique(T* item, CompareFunctionWithState func, 824 void* state) 825{ 826 int32 index = _PointerList_::BinarySearchIndex(item, 827 (GenericCompareFunctionWithState)func, state); 828 if (index >= 0) 829 return false; 830 831 return AddItem(item, -index - 1); 832} 833 834 835template<class T> 836T* 837BObjectList<T>::BinaryInsertCopy(const T& copyThis, CompareFunction func) 838{ 839 int32 index = _PointerList_::BinarySearchIndex(©This, 840 (GenericCompareFunction)func); 841 842 if (index >= 0) 843 index++; 844 else 845 index = -index - 1; 846 847 T* newItem = new (std::nothrow) T(copyThis); 848 AddItem(newItem, index); 849 return newItem; 850} 851 852 853template<class T> 854T* 855BObjectList<T>::BinaryInsertCopy(const T& copyThis, 856 CompareFunctionWithState func, void* state) 857{ 858 int32 index = _PointerList_::BinarySearchIndex(©This, 859 (GenericCompareFunctionWithState)func, state); 860 861 if (index >= 0) 862 index++; 863 else 864 index = -index - 1; 865 866 T* newItem = new (std::nothrow) T(copyThis); 867 AddItem(newItem, index); 868 return newItem; 869} 870 871 872template<class T> 873T* 874BObjectList<T>::BinaryInsertCopyUnique(const T& copyThis, CompareFunction func) 875{ 876 int32 index = _PointerList_::BinarySearchIndex(©This, 877 (GenericCompareFunction)func); 878 if (index >= 0) 879 return ItemAt(index); 880 881 index = -index - 1; 882 T* newItem = new (std::nothrow) T(copyThis); 883 AddItem(newItem, index); 884 return newItem; 885} 886 887 888template<class T> 889T* 890BObjectList<T>::BinaryInsertCopyUnique(const T& copyThis, 891 CompareFunctionWithState func, void* state) 892{ 893 int32 index = _PointerList_::BinarySearchIndex(©This, 894 (GenericCompareFunctionWithState)func, state); 895 if (index >= 0) 896 return ItemAt(index); 897 898 index = -index - 1; 899 T* newItem = new (std::nothrow) T(copyThis); 900 AddItem(newItem, index); 901 return newItem; 902} 903 904 905template<class T> 906int32 907BObjectList<T>::FindBinaryInsertionIndex(const UnaryPredicate<T>& pred, 908 bool* alreadyInList) const 909{ 910 int32 index = _PointerList_::BinarySearchIndexByPredicate(&pred, 911 (UnaryPredicateGlue)&UnaryPredicate<T>::_unary_predicate_glue); 912 913 if (alreadyInList) 914 *alreadyInList = index >= 0; 915 916 if (index < 0) 917 index = -index - 1; 918 919 return index; 920} 921 922 923template<class T> 924bool 925BObjectList<T>::BinaryInsert(T* item, const UnaryPredicate<T>& pred) 926{ 927 return AddItem(item, FindBinaryInsertionIndex(pred)); 928} 929 930 931template<class T> 932bool 933BObjectList<T>::BinaryInsertUnique(T* item, const UnaryPredicate<T>& pred) 934{ 935 bool alreadyInList; 936 int32 index = FindBinaryInsertionIndex(pred, &alreadyInList); 937 if (alreadyInList) 938 return false; 939 940 AddItem(item, index); 941 return true; 942} 943 944 945#endif /* _OBJECT_LIST_H */ 946