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 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 61private: 62 static int _unary_predicate_glue(const void *item, void *context); 63 64 friend class BObjectList<T>; 65}; 66 67 68template<class T> 69int 70UnaryPredicate<T>::_unary_predicate_glue(const void *item, void *context) 71{ 72 return ((UnaryPredicate<T> *)context)->operator()((const T *)item); 73} 74 75 76class _PointerList_ : public BList { 77public: 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 107protected: 108 bool owning; 109 110}; 111 112 113template<class T> 114class BObjectList : private _PointerList_ { 115public: 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 index) 487{ 488 return _PointerList_::AddItem((void*)item, index); 489} 490 491 492template<class T> 493bool 494BObjectList<T>::AddList(BObjectList<T>* list) 495{ 496 return _PointerList_::AddList(list); 497} 498 499 500template<class T> 501bool 502BObjectList<T>::AddList(BObjectList<T>* list, int32 index) 503{ 504 return _PointerList_::AddList(list, index); 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 544 return _PointerList_::ReplaceItem(index, (void*)item); 545} 546 547 548template<class T> 549T* 550BObjectList<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 559template<class T> 560bool 561BObjectList<T>::MoveItem(int32 from, int32 to) 562{ 563 return _PointerList_::MoveItem(from, to); 564} 565 566 567template<class T> 568void 569BObjectList<T>::_SetItem(int32 index, T* newItem) 570{ 571 _PointerList_::ReplaceItem(index, (void*)newItem); 572} 573 574 575template<class T> 576int32 577BObjectList<T>::IndexOf(const T* item) const 578{ 579 return _PointerList_::IndexOf((void*)item); 580} 581 582 583template<class T> 584T* 585BObjectList<T>::FirstItem() const 586{ 587 return (T*)_PointerList_::FirstItem(); 588} 589 590 591template<class T> 592T* 593BObjectList<T>::LastItem() const 594{ 595 return (T*)_PointerList_::LastItem(); 596} 597 598 599template<class T> 600bool 601BObjectList<T>::HasItem(const T* item) const 602{ 603 return _PointerList_::HasItem((void*)item); 604} 605 606 607template<class T> 608bool 609BObjectList<T>::IsEmpty() const 610{ 611 return _PointerList_::IsEmpty(); 612} 613 614 615template<class T> 616int32 617BObjectList<T>::CountItems() const 618{ 619 return _PointerList_::CountItems(); 620} 621 622 623template<class T> 624void 625BObjectList<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 636template<class T> 637T* 638BObjectList<T>::EachElement(EachFunction func, void* params) 639{ 640 return (T*)_PointerList_::EachElement((GenericEachFunction)func, params); 641} 642 643 644template<class T> 645const T* 646BObjectList<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 653template<class T> 654const T* 655BObjectList<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 665template<class T> 666T* 667BObjectList<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 678template<class T> 679void 680BObjectList<T>::SortItems(CompareFunction function) 681{ 682 _PointerList_::SortItems((GenericCompareFunction)function); 683} 684 685 686template<class T> 687void 688BObjectList<T>::SortItems(CompareFunctionWithState function, void* state) 689{ 690 _PointerList_::SortItems((GenericCompareFunctionWithState)function, state); 691} 692 693 694template<class T> 695void 696BObjectList<T>::HSortItems(CompareFunction function) 697{ 698 _PointerList_::HSortItems((GenericCompareFunction)function); 699} 700 701 702template<class T> 703void 704BObjectList<T>::HSortItems(CompareFunctionWithState function, void* state) 705{ 706 _PointerList_::HSortItems((GenericCompareFunctionWithState)function, state); 707} 708 709 710template<class T> 711T* 712BObjectList<T>::BinarySearch(const T& key, CompareFunction func) const 713{ 714 return (T*)_PointerList_::BinarySearch(&key, (GenericCompareFunction)func); 715} 716 717 718template<class T> 719T* 720BObjectList<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 728template<class T> 729template<typename Key> 730T* 731BObjectList<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 739template<class T> 740template<typename Key> 741T* 742BObjectList<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 750template<class T> 751int32 752BObjectList<T>::BinarySearchIndex(const T& item, CompareFunction compare) const 753{ 754 return _PointerList_::BinarySearchIndex(&item, 755 (GenericCompareFunction)compare); 756} 757 758 759template<class T> 760int32 761BObjectList<T>::BinarySearchIndex(const T& item, 762 CompareFunctionWithState compare, void* state) const 763{ 764 return _PointerList_::BinarySearchIndex(&item, 765 (GenericCompareFunctionWithState)compare, state); 766} 767 768 769template<class T> 770template<typename Key> 771int32 772BObjectList<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 780template<class T> 781bool 782BObjectList<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 795template<class T> 796bool 797BObjectList<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 811template<class T> 812bool 813BObjectList<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 824template<class T> 825bool 826BObjectList<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 838template<class T> 839T* 840BObjectList<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 856template<class T> 857T* 858BObjectList<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 875template<class T> 876T* 877BObjectList<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 891template<class T> 892T* 893BObjectList<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 908template<class T> 909int32 910BObjectList<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 926template<class T> 927bool 928BObjectList<T>::BinaryInsert(T* item, const UnaryPredicate<T>& pred) 929{ 930 return AddItem(item, FindBinaryInsertionIndex(pred)); 931} 932 933 934template<class T> 935bool 936BObjectList<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