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