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(&copyThis,
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(&copyThis,
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(&copyThis,
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(&copyThis,
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