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 bool MoveItem(int32 from, int32 to); 105 106 protected: 107 bool owning; 108 109 }; 110 111 112 template<class T> 113 class BObjectList : private _PointerList_ { 114 public: 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; 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 atIndex) 487 { 488 return _PointerList_::AddItem((void*)item, atIndex); 489 } 490 491 492 template<class T> 493 bool 494 BObjectList<T>::AddList(BObjectList<T>* newItems) 495 { 496 return _PointerList_::AddList(newItems); 497 } 498 499 500 template<class T> 501 bool 502 BObjectList<T>::AddList(BObjectList<T>* newItems, int32 atIndex) 503 { 504 return _PointerList_::AddList(newItems, atIndex); 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 return _PointerList_::ReplaceItem(index, (void*)item); 544 } 545 546 547 template<class T> 548 T* 549 BObjectList<T>::SwapWithItem(int32 index, T* newItem) 550 { 551 T* result = ItemAt(index); 552 _PointerList_::ReplaceItem(index, (void*)newItem); 553 return result; 554 } 555 556 557 template<class T> 558 bool 559 BObjectList<T>::MoveItem(int32 from, int32 to) 560 { 561 return _PointerList_::MoveItem(from, to); 562 } 563 564 565 template<class T> 566 void 567 BObjectList<T>::_SetItem(int32 index, T* newItem) 568 { 569 _PointerList_::ReplaceItem(index, (void*)newItem); 570 } 571 572 573 template<class T> 574 int32 575 BObjectList<T>::IndexOf(const T* item) const 576 { 577 return _PointerList_::IndexOf((void*)item); 578 } 579 580 581 template<class T> 582 T* 583 BObjectList<T>::FirstItem() const 584 { 585 return (T*)_PointerList_::FirstItem(); 586 } 587 588 589 template<class T> 590 T* 591 BObjectList<T>::LastItem() const 592 { 593 return (T*)_PointerList_::LastItem(); 594 } 595 596 597 template<class T> 598 bool 599 BObjectList<T>::HasItem(const T* item) const 600 { 601 return _PointerList_::HasItem((void*)item); 602 } 603 604 605 template<class T> 606 bool 607 BObjectList<T>::IsEmpty() const 608 { 609 return _PointerList_::IsEmpty(); 610 } 611 612 613 template<class T> 614 int32 615 BObjectList<T>::CountItems() const 616 { 617 return _PointerList_::CountItems(); 618 } 619 620 621 template<class T> 622 void 623 BObjectList<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 634 template<class T> 635 T* 636 BObjectList<T>::EachElement(EachFunction func, void* params) 637 { 638 return (T*)_PointerList_::EachElement((GenericEachFunction)func, params); 639 } 640 641 642 template<class T> 643 const T* 644 BObjectList<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 651 template<class T> 652 const T* 653 BObjectList<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 663 template<class T> 664 T* 665 BObjectList<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 676 template<class T> 677 void 678 BObjectList<T>::SortItems(CompareFunction function) 679 { 680 _PointerList_::SortItems((GenericCompareFunction)function); 681 } 682 683 684 template<class T> 685 void 686 BObjectList<T>::SortItems(CompareFunctionWithState function, void* state) 687 { 688 _PointerList_::SortItems((GenericCompareFunctionWithState)function, state); 689 } 690 691 692 template<class T> 693 void 694 BObjectList<T>::HSortItems(CompareFunction function) 695 { 696 _PointerList_::HSortItems((GenericCompareFunction)function); 697 } 698 699 700 template<class T> 701 void 702 BObjectList<T>::HSortItems(CompareFunctionWithState function, void* state) 703 { 704 _PointerList_::HSortItems((GenericCompareFunctionWithState)function, state); 705 } 706 707 708 template<class T> 709 T* 710 BObjectList<T>::BinarySearch(const T& key, CompareFunction func) const 711 { 712 return (T*)_PointerList_::BinarySearch(&key, (GenericCompareFunction)func); 713 } 714 715 template<class T> 716 T* 717 BObjectList<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 725 template<class T> 726 template<typename Key> 727 T* 728 BObjectList<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 736 template<class T> 737 template<typename Key> 738 T* 739 BObjectList<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 747 template<class T> 748 int32 749 BObjectList<T>::BinarySearchIndex(const T& item, CompareFunction compare) const 750 { 751 return _PointerList_::BinarySearchIndex(&item, 752 (GenericCompareFunction)compare); 753 } 754 755 756 template<class T> 757 int32 758 BObjectList<T>::BinarySearchIndex(const T& item, 759 CompareFunctionWithState compare, void* state) const 760 { 761 return _PointerList_::BinarySearchIndex(&item, 762 (GenericCompareFunctionWithState)compare, state); 763 } 764 765 766 template<class T> 767 template<typename Key> 768 int32 769 BObjectList<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 777 template<class T> 778 bool 779 BObjectList<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 792 template<class T> 793 bool 794 BObjectList<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 808 template<class T> 809 bool 810 BObjectList<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 821 template<class T> 822 bool 823 BObjectList<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 835 template<class T> 836 T* 837 BObjectList<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 853 template<class T> 854 T* 855 BObjectList<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 872 template<class T> 873 T* 874 BObjectList<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 888 template<class T> 889 T* 890 BObjectList<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 905 template<class T> 906 int32 907 BObjectList<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 923 template<class T> 924 bool 925 BObjectList<T>::BinaryInsert(T* item, const UnaryPredicate<T>& pred) 926 { 927 return AddItem(item, FindBinaryInsertionIndex(pred)); 928 } 929 930 931 template<class T> 932 bool 933 BObjectList<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