1731be7ddSAugustin Cavalier/*
2731be7ddSAugustin Cavalier * Copyright 2003, Ingo Weinhold, ingo_weinhold@gmx.de.
3731be7ddSAugustin Cavalier * All rights reserved. Distributed under the terms of the MIT license.
4731be7ddSAugustin Cavalier */
54489db25SIngo Weinhold#ifndef _VECTOR_SET_H
64489db25SIngo Weinhold#define _VECTOR_SET_H
74489db25SIngo Weinhold
84489db25SIngo Weinhold#include <stdlib.h>
94489db25SIngo Weinhold#include <string.h>
104489db25SIngo Weinhold
114489db25SIngo Weinhold#include <SupportDefs.h>
124489db25SIngo Weinhold
13960371b7SAxel Dörfler#include <util/kernel_cpp.h>
144489db25SIngo Weinhold#include <Vector.h>
154489db25SIngo Weinhold
164489db25SIngo Weinhold// element orders
174489db25SIngo Weinholdnamespace VectorSetOrder {
184489db25SIngo Weinhold	template<typename Value> class Ascending;
194489db25SIngo Weinhold	template<typename Value> class Descending;
204489db25SIngo Weinhold}
214489db25SIngo Weinhold
224489db25SIngo Weinhold// for convenience
234489db25SIngo Weinhold#define _VECTOR_SET_TEMPLATE_LIST template<typename Value, \
244489db25SIngo Weinhold										   typename ElementOrder>
254489db25SIngo Weinhold#define _VECTOR_SET_CLASS_NAME VectorSet<Value, ElementOrder>
269eed5c27SAxel Dörfler#define _VECTOR_SET_CLASS_TYPE typename VectorSet<Value, ElementOrder>
274489db25SIngo Weinhold
284489db25SIngo Weinhold/*!
294489db25SIngo Weinhold	\class VectorSet
304489db25SIngo Weinhold	\brief A generic vector-based set implementation.
314489db25SIngo Weinhold
324489db25SIngo Weinhold	The elements of the set are ordered according to the supplied
334489db25SIngo Weinhold	compare function object. Default is ascending order.
344489db25SIngo Weinhold*/
354489db25SIngo Weinholdtemplate<typename Value,
364489db25SIngo Weinhold		 typename ElementOrder = VectorSetOrder::Ascending<Value> >
374489db25SIngo Weinholdclass VectorSet {
384489db25SIngo Weinholdprivate:
394489db25SIngo Weinhold	typedef Vector<Value>							ElementVector;
404489db25SIngo Weinhold
414489db25SIngo Weinholdpublic:
424489db25SIngo Weinhold	typedef typename ElementVector::Iterator		Iterator;
434489db25SIngo Weinhold	typedef typename ElementVector::ConstIterator	ConstIterator;
444489db25SIngo Weinhold
454489db25SIngo Weinholdprivate:
464489db25SIngo Weinhold	static const size_t				kDefaultChunkSize = 10;
474489db25SIngo Weinhold	static const size_t				kMaximalChunkSize = 1024 * 1024;
484489db25SIngo Weinhold
494489db25SIngo Weinholdpublic:
504489db25SIngo Weinhold	VectorSet(size_t chunkSize = kDefaultChunkSize);
514489db25SIngo Weinhold// TODO: Copy constructor, assignment operator.
524489db25SIngo Weinhold	~VectorSet();
534489db25SIngo Weinhold
544489db25SIngo Weinhold	status_t Insert(const Value &value, bool replace = true);
554489db25SIngo Weinhold
564489db25SIngo Weinhold	int32 Remove(const Value &value);
574489db25SIngo Weinhold	Iterator Erase(const Iterator &iterator);
584489db25SIngo Weinhold
594489db25SIngo Weinhold	inline int32 Count() const;
604489db25SIngo Weinhold	inline bool IsEmpty() const;
614489db25SIngo Weinhold	void MakeEmpty();
624489db25SIngo Weinhold
634489db25SIngo Weinhold	inline Iterator Begin();
644489db25SIngo Weinhold	inline ConstIterator Begin() const;
654489db25SIngo Weinhold	inline Iterator End();
664489db25SIngo Weinhold	inline ConstIterator End() const;
674489db25SIngo Weinhold	inline Iterator Null();
684489db25SIngo Weinhold	inline ConstIterator Null() const;
694489db25SIngo Weinhold
704489db25SIngo Weinhold	Iterator Find(const Value &value);
714489db25SIngo Weinhold	ConstIterator Find(const Value &value) const;
724489db25SIngo Weinhold	Iterator FindClose(const Value &value, bool less);
734489db25SIngo Weinhold	ConstIterator FindClose(const Value &value, bool less) const;
744489db25SIngo Weinhold
754489db25SIngo Weinholdprivate:
764489db25SIngo Weinhold	int32 _FindInsertionIndex(const Value &value, bool &exists) const;
774489db25SIngo Weinhold
784489db25SIngo Weinholdprivate:
794489db25SIngo Weinhold	ElementVector	fElements;
804489db25SIngo Weinhold	ElementOrder	fCompare;
814489db25SIngo Weinhold};
824489db25SIngo Weinhold
834489db25SIngo Weinhold
844489db25SIngo Weinhold// VectorSet
854489db25SIngo Weinhold
864489db25SIngo Weinhold// constructor
874489db25SIngo Weinhold/*!	\brief Creates an empty set.
884489db25SIngo Weinhold	\param chunkSize The granularity for the underlying vector's capacity,
894489db25SIngo Weinhold		   i.e. the minimal number of elements the capacity grows or shrinks
904489db25SIngo Weinhold		   when necessary.
914489db25SIngo Weinhold*/
924489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
934489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::VectorSet(size_t chunkSize)
944489db25SIngo Weinhold	: fElements(chunkSize)
954489db25SIngo Weinhold{
964489db25SIngo Weinhold}
974489db25SIngo Weinhold
984489db25SIngo Weinhold// destructor
994489db25SIngo Weinhold/*!	\brief Frees all resources associated with the object.
1004489db25SIngo Weinhold
1014489db25SIngo Weinhold	The contained elements are destroyed. Note, that, if the element
1024489db25SIngo Weinhold	type is a pointer type, only the pointer is destroyed, not the object
1034489db25SIngo Weinhold	it points to.
1044489db25SIngo Weinhold*/
1054489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
1064489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::~VectorSet()
1074489db25SIngo Weinhold{
1084489db25SIngo Weinhold}
1094489db25SIngo Weinhold
1104489db25SIngo Weinhold// Insert
1114489db25SIngo Weinhold/*!	\brief Inserts a copy of the the supplied value.
1124489db25SIngo Weinhold
1134489db25SIngo Weinhold	If an element with the supplied value is already in the set, the
1144489db25SIngo Weinhold	operation will not fail, but return \c B_OK. \a replace specifies
1154489db25SIngo Weinhold	whether the element shall be replaced with the supplied in such a case.
1164489db25SIngo Weinhold	Otherwise \a replace is ignored.
1174489db25SIngo Weinhold
1184489db25SIngo Weinhold	\param value The value to be inserted.
1194489db25SIngo Weinhold	\param replace If the an element with this value does already exist and
1204489db25SIngo Weinhold		   \a replace is \c true, the element is replaced, otherwise left
1214489db25SIngo Weinhold		   untouched.
1224489db25SIngo Weinhold	\return
1234489db25SIngo Weinhold	- \c B_OK: Everything went fine.
1244489db25SIngo Weinhold	- \c B_NO_MEMORY: Insufficient memory for this operation.
1254489db25SIngo Weinhold*/
1264489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
1274489db25SIngo Weinholdstatus_t
1284489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::Insert(const Value &value, bool replace)
1294489db25SIngo Weinhold{
1304489db25SIngo Weinhold	bool exists = false;
1314489db25SIngo Weinhold	int32 index = _FindInsertionIndex(value, exists);
1324489db25SIngo Weinhold	if (exists) {
1334489db25SIngo Weinhold		if (replace)
1344489db25SIngo Weinhold			fElements[index] = value;
1354489db25SIngo Weinhold		return B_OK;
1364489db25SIngo Weinhold	}
1374489db25SIngo Weinhold	return fElements.Insert(value, index);
1384489db25SIngo Weinhold}
1394489db25SIngo Weinhold
1404489db25SIngo Weinhold// Remove
1414489db25SIngo Weinhold/*!	\brief Removes the element with the supplied value.
1424489db25SIngo Weinhold	\param value The value of the element to be removed.
1434489db25SIngo Weinhold	\return The number of removed occurrences, i.e. \c 1, if the set
1444489db25SIngo Weinhold			contained an element with the value, \c 0 otherwise.
1454489db25SIngo Weinhold*/
1464489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
1474489db25SIngo Weinholdint32
1484489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::Remove(const Value &value)
1494489db25SIngo Weinhold{
1504489db25SIngo Weinhold	bool exists = false;
1514489db25SIngo Weinhold	int32 index = _FindInsertionIndex(value, exists);
1524489db25SIngo Weinhold	if (!exists)
1534489db25SIngo Weinhold		return 0;
1544489db25SIngo Weinhold	fElements.Erase(index);
1554489db25SIngo Weinhold	return 1;
1564489db25SIngo Weinhold}
1574489db25SIngo Weinhold
1584489db25SIngo Weinhold// Erase
1594489db25SIngo Weinhold/*!	\brief Removes the element at the given position.
1604489db25SIngo Weinhold	\param iterator An iterator referring to the element to be removed.
1614489db25SIngo Weinhold	\return An iterator referring to the element succeeding the removed
1624489db25SIngo Weinhold			one (End(), if it was the last element that has been
1634489db25SIngo Weinhold			removed), or Null(), if \a iterator was an invalid iterator
1644489db25SIngo Weinhold			(in this case including End()).
1654489db25SIngo Weinhold*/
1664489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
1679eed5c27SAxel Dörfler_VECTOR_SET_CLASS_TYPE::Iterator
1684489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::Erase(const Iterator &iterator)
1694489db25SIngo Weinhold{
1704489db25SIngo Weinhold	return fElements.Erase(iterator);
1714489db25SIngo Weinhold}
1724489db25SIngo Weinhold
1734489db25SIngo Weinhold// Count
1744489db25SIngo Weinhold/*!	\brief Returns the number of elements the set contains.
1754489db25SIngo Weinhold	\return The number of elements the set contains.
1764489db25SIngo Weinhold*/
1774489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
1784489db25SIngo Weinholdinline
1794489db25SIngo Weinholdint32
1804489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::Count() const
1814489db25SIngo Weinhold{
1824489db25SIngo Weinhold	return fElements.Count();
1834489db25SIngo Weinhold}
1844489db25SIngo Weinhold
1854489db25SIngo Weinhold// IsEmpty
1864489db25SIngo Weinhold/*!	\brief Returns whether the set is empty.
1874489db25SIngo Weinhold	\return \c true, if the set is empty, \c false otherwise.
1884489db25SIngo Weinhold*/
1894489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
1904489db25SIngo Weinholdinline
1914489db25SIngo Weinholdbool
1924489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::IsEmpty() const
1934489db25SIngo Weinhold{
1944489db25SIngo Weinhold	return fElements.IsEmpty();
1954489db25SIngo Weinhold}
1964489db25SIngo Weinhold
1974489db25SIngo Weinhold// MakeEmpty
1984489db25SIngo Weinhold/*!	\brief Removes all elements from the set.
1994489db25SIngo Weinhold*/
2004489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
2014489db25SIngo Weinholdvoid
2024489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::MakeEmpty()
2034489db25SIngo Weinhold{
2044489db25SIngo Weinhold	fElements.MakeEmpty();
2054489db25SIngo Weinhold}
2064489db25SIngo Weinhold
2074489db25SIngo Weinhold// Begin
2084489db25SIngo Weinhold/*!	\brief Returns an iterator referring to the beginning of the set.
2094489db25SIngo Weinhold
2104489db25SIngo Weinhold	If the set is not empty, Begin() refers to its first element,
21192ec26a3SIngo Weinhold	otherwise it is equal to End() and must not be dereferenced!
2124489db25SIngo Weinhold
2134489db25SIngo Weinhold	\return An iterator referring to the beginning of the set.
2144489db25SIngo Weinhold*/
2154489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
2164489db25SIngo Weinholdinline
2179eed5c27SAxel Dörfler_VECTOR_SET_CLASS_TYPE::Iterator
2184489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::Begin()
2194489db25SIngo Weinhold{
2204489db25SIngo Weinhold	return fElements.Begin();
2214489db25SIngo Weinhold}
2224489db25SIngo Weinhold
2234489db25SIngo Weinhold// Begin
2244489db25SIngo Weinhold/*!	\brief Returns an iterator referring to the beginning of the set.
2254489db25SIngo Weinhold
2264489db25SIngo Weinhold	If the set is not empty, Begin() refers to its first element,
22792ec26a3SIngo Weinhold	otherwise it is equal to End() and must not be dereferenced!
2284489db25SIngo Weinhold
2294489db25SIngo Weinhold	\return An iterator referring to the beginning of the set.
2304489db25SIngo Weinhold*/
2314489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
2324489db25SIngo Weinholdinline
2339eed5c27SAxel Dörfler_VECTOR_SET_CLASS_TYPE::ConstIterator
2344489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::Begin() const
2354489db25SIngo Weinhold{
2364489db25SIngo Weinhold	return fElements.Begin();
2374489db25SIngo Weinhold}
2384489db25SIngo Weinhold
2394489db25SIngo Weinhold// End
2404489db25SIngo Weinhold/*!	\brief Returns an iterator referring to the end of the set.
2414489db25SIngo Weinhold
2424489db25SIngo Weinhold	The position identified by End() is the one succeeding the last
2434489db25SIngo Weinhold	element, i.e. it must not be dereferenced!
2444489db25SIngo Weinhold
2454489db25SIngo Weinhold	\return An iterator referring to the end of the set.
2464489db25SIngo Weinhold*/
2474489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
2484489db25SIngo Weinholdinline
2499eed5c27SAxel Dörfler_VECTOR_SET_CLASS_TYPE::Iterator
2504489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::End()
2514489db25SIngo Weinhold{
2524489db25SIngo Weinhold	return fElements.End();
2534489db25SIngo Weinhold}
2544489db25SIngo Weinhold
2554489db25SIngo Weinhold// End
2564489db25SIngo Weinhold/*!	\brief Returns an iterator referring to the end of the set.
2574489db25SIngo Weinhold
2584489db25SIngo Weinhold	The position identified by End() is the one succeeding the last
2594489db25SIngo Weinhold	element, i.e. it must not be dereferenced!
2604489db25SIngo Weinhold
2614489db25SIngo Weinhold	\return An iterator referring to the end of the set.
2624489db25SIngo Weinhold*/
2634489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
2644489db25SIngo Weinholdinline
2659eed5c27SAxel Dörfler_VECTOR_SET_CLASS_TYPE::ConstIterator
2664489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::End() const
2674489db25SIngo Weinhold{
2684489db25SIngo Weinhold	return fElements.End();
2694489db25SIngo Weinhold}
2704489db25SIngo Weinhold
2714489db25SIngo Weinhold// Null
2724489db25SIngo Weinhold/*!	\brief Returns an invalid iterator.
2734489db25SIngo Weinhold
2744489db25SIngo Weinhold	Null() is used as a return value, if something went wrong. It must
2754489db25SIngo Weinhold	neither be incremented or decremented nor dereferenced!
2764489db25SIngo Weinhold
2774489db25SIngo Weinhold	\return An invalid iterator.
2784489db25SIngo Weinhold*/
2794489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
2804489db25SIngo Weinholdinline
2819eed5c27SAxel Dörfler_VECTOR_SET_CLASS_TYPE::Iterator
2824489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::Null()
2834489db25SIngo Weinhold{
2844489db25SIngo Weinhold	return fElements.Null();
2854489db25SIngo Weinhold}
2864489db25SIngo Weinhold
2874489db25SIngo Weinhold// Null
2884489db25SIngo Weinhold/*!	\brief Returns an invalid iterator.
2894489db25SIngo Weinhold
2904489db25SIngo Weinhold	Null() is used as a return value, if something went wrong. It must
2914489db25SIngo Weinhold	neither be incremented or decremented nor dereferenced!
2924489db25SIngo Weinhold
2934489db25SIngo Weinhold	\return An invalid iterator.
2944489db25SIngo Weinhold*/
2954489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
2964489db25SIngo Weinholdinline
2979eed5c27SAxel Dörfler_VECTOR_SET_CLASS_TYPE::ConstIterator
2984489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::Null() const
2994489db25SIngo Weinhold{
3004489db25SIngo Weinhold	return fElements.Null();
3014489db25SIngo Weinhold}
3024489db25SIngo Weinhold
3034489db25SIngo Weinhold// Find
3044489db25SIngo Weinhold/*!	\brief Returns an iterator referring to the element with the
3054489db25SIngo Weinhold		   specified value.
3064489db25SIngo Weinhold	\param value The value of the element to be found.
3074489db25SIngo Weinhold	\return An iterator referring to the found element, or End(), if the
3084489db25SIngo Weinhold			set doesn't contain any element with the given value.
3094489db25SIngo Weinhold*/
3104489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
3119eed5c27SAxel Dörfler_VECTOR_SET_CLASS_TYPE::Iterator
3124489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::Find(const Value &value)
3134489db25SIngo Weinhold{
3144489db25SIngo Weinhold	bool exists = false;
3154489db25SIngo Weinhold	int32 index = _FindInsertionIndex(value, exists);
3164489db25SIngo Weinhold	if (!exists)
3174489db25SIngo Weinhold		return fElements.End();
3184489db25SIngo Weinhold	return fElements.IteratorForIndex(index);
3194489db25SIngo Weinhold}
3204489db25SIngo Weinhold
3214489db25SIngo Weinhold// Find
3224489db25SIngo Weinhold/*!	\brief Returns an iterator referring to the element with the
3234489db25SIngo Weinhold		   specified value.
3244489db25SIngo Weinhold	\param value The value of the element to be found.
3254489db25SIngo Weinhold	\return An iterator referring to the found element, or End(), if the
3264489db25SIngo Weinhold			set doesn't contain any element with the given value.
3274489db25SIngo Weinhold*/
3284489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
3299eed5c27SAxel Dörfler_VECTOR_SET_CLASS_TYPE::ConstIterator
3304489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::Find(const Value &value) const
3314489db25SIngo Weinhold{
3324489db25SIngo Weinhold	bool exists = false;
3334489db25SIngo Weinhold	int32 index = _FindInsertionIndex(value, exists);
3344489db25SIngo Weinhold	if (!exists)
3354489db25SIngo Weinhold		return fElements.End();
3364489db25SIngo Weinhold	return fElements.IteratorForIndex(index);
3374489db25SIngo Weinhold}
3384489db25SIngo Weinhold
3394489db25SIngo Weinhold// FindClose
3404489db25SIngo Weinhold/*!	\brief Returns an iterator referring to the element with a value closest
3414489db25SIngo Weinhold		   to the specified one.
3424489db25SIngo Weinhold
3434489db25SIngo Weinhold	If the set contains an element with the specified value, an iterator
3444489db25SIngo Weinhold	to it is returned. Otherwise \a less indicates whether an iterator to
34592ec26a3SIngo Weinhold	the directly smaller or greater element shall be returned.
3464489db25SIngo Weinhold
3474489db25SIngo Weinhold	If \a less is \c true and the first element in the set has a greater
3484489db25SIngo Weinhold	value than the specified one, End() is returned. Similarly, when \a less
3494489db25SIngo Weinhold	is \c false and the last element is smaller. Find() invoked on an empty
3504489db25SIngo Weinhold	set always returns End().
3514489db25SIngo Weinhold
3524489db25SIngo Weinhold	Note, that the element order used for the set is specified as template
3534489db25SIngo Weinhold	argument to the class. Default is ascending order. Descending order
3544489db25SIngo Weinhold	inverts the meaning of \a less, i.e. if \c true, greater values will
3554489db25SIngo Weinhold	be returned, since they are smaller ones according to the order.
3564489db25SIngo Weinhold
3574489db25SIngo Weinhold	\param value The value of the element to be found.
3584489db25SIngo Weinhold	\return An iterator referring to the found element, or End(), if the
3594489db25SIngo Weinhold			set doesn't contain any element with the given value or a close
3604489db25SIngo Weinhold			one according to \a less.
3614489db25SIngo Weinhold*/
3624489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
3639eed5c27SAxel Dörfler_VECTOR_SET_CLASS_TYPE::Iterator
3644489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::FindClose(const Value &value, bool less)
3654489db25SIngo Weinhold{
3664489db25SIngo Weinhold	bool exists = false;
3674489db25SIngo Weinhold	int32 index = _FindInsertionIndex(value, exists);
3684489db25SIngo Weinhold	// If not found, the index _FindInsertionIndex() returns will point to
3694489db25SIngo Weinhold	// an element with a greater value or to End(). So, no special handling
3704489db25SIngo Weinhold	// is needed for !less.
3714489db25SIngo Weinhold	if (exists || !less)
3724489db25SIngo Weinhold		return fElements.IteratorForIndex(index);
3734489db25SIngo Weinhold	// An element with a smaller value is desired. The previous one (if any)
3744489db25SIngo Weinhold	// will do.
3754489db25SIngo Weinhold	if (index > 0)
3764489db25SIngo Weinhold		return fElements.IteratorForIndex(index - 1);
3774489db25SIngo Weinhold	return fElements.End();
3784489db25SIngo Weinhold}
3794489db25SIngo Weinhold
3804489db25SIngo Weinhold// FindClose
3814489db25SIngo Weinhold/*!	\brief Returns an iterator referring to the element with a value closest
3824489db25SIngo Weinhold		   to the specified one.
3834489db25SIngo Weinhold
3844489db25SIngo Weinhold	If the set contains an element with the specified value, an iterator
3854489db25SIngo Weinhold	to it is returned. Otherwise \a less indicates whether an iterator to
38692ec26a3SIngo Weinhold	the directly smaller or greater element shall be returned.
3874489db25SIngo Weinhold
3884489db25SIngo Weinhold	If \a less is \c true and the first element in the set has a greater
3894489db25SIngo Weinhold	value than the specified one, End() is returned. Similarly, when \a less
3904489db25SIngo Weinhold	is \c false and the last element is smaller. Find() invoked on an empty
3914489db25SIngo Weinhold	set always returns End().
3924489db25SIngo Weinhold
3934489db25SIngo Weinhold	Note, that the element order used for the set is specified as template
3944489db25SIngo Weinhold	argument to the class. Default is ascending order. Descending order
3954489db25SIngo Weinhold	inverts the meaning of \a less, i.e. if \c true, greater values will
3964489db25SIngo Weinhold	be returned, since they are smaller ones according to the order.
3974489db25SIngo Weinhold
3984489db25SIngo Weinhold	\param value The value of the element to be found.
3994489db25SIngo Weinhold	\return An iterator referring to the found element, or End(), if the
4004489db25SIngo Weinhold			set doesn't contain any element with the given value or a close
4014489db25SIngo Weinhold			one according to \a less.
4024489db25SIngo Weinhold*/
4034489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
4049eed5c27SAxel Dörfler_VECTOR_SET_CLASS_TYPE::ConstIterator
4054489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::FindClose(const Value &value, bool less) const
4064489db25SIngo Weinhold{
4074489db25SIngo Weinhold	bool exists = false;
4084489db25SIngo Weinhold	int32 index = _FindInsertionIndex(value, exists);
4094489db25SIngo Weinhold	// If not found, the index _FindInsertionIndex() returns will point to
4104489db25SIngo Weinhold	// an element with a greater value or to End(). So, no special handling
4114489db25SIngo Weinhold	// is needed for !less.
4124489db25SIngo Weinhold	if (exists || !less)
4134489db25SIngo Weinhold		return fElements.IteratorForIndex(index);
4144489db25SIngo Weinhold	// An element with a smaller value is desired. The previous one (if any)
4154489db25SIngo Weinhold	// will do.
4164489db25SIngo Weinhold	if (index > 0)
4174489db25SIngo Weinhold		return fElements.IteratorForIndex(index - 1);
4184489db25SIngo Weinhold	return fElements.End();
4194489db25SIngo Weinhold}
4204489db25SIngo Weinhold
4214489db25SIngo Weinhold// _FindInsertionIndex
4224489db25SIngo Weinhold/*!	\brief Finds the index at which the element with the supplied value is
4234489db25SIngo Weinhold		   located or at which it would need to be inserted.
4244489db25SIngo Weinhold	\param value The value.
4254489db25SIngo Weinhold	\param exists Is set to \c true, if the set does already contain an
4264489db25SIngo Weinhold		   element with that value.
4274489db25SIngo Weinhold	\return The index at which the element with the supplied value is
4284489db25SIngo Weinhold			located or at which it would need to be inserted.
4294489db25SIngo Weinhold*/
4304489db25SIngo Weinhold_VECTOR_SET_TEMPLATE_LIST
4314489db25SIngo Weinholdint32
4324489db25SIngo Weinhold_VECTOR_SET_CLASS_NAME::_FindInsertionIndex(const Value &value,
4334489db25SIngo Weinhold											bool &exists) const
4344489db25SIngo Weinhold{
4354489db25SIngo Weinhold	// binary search
4364489db25SIngo Weinhold	int32 lower = 0;
4374489db25SIngo Weinhold	int32 upper = Count();
4384489db25SIngo Weinhold	while (lower < upper) {
4394489db25SIngo Weinhold		int32 mid = (lower + upper) / 2;
4404489db25SIngo Weinhold		int cmp = fCompare(fElements[mid], value);
4414489db25SIngo Weinhold		if (cmp < 0)
4424489db25SIngo Weinhold			lower = mid + 1;
4434489db25SIngo Weinhold		else
4444489db25SIngo Weinhold			upper = mid;
4454489db25SIngo Weinhold	}
4464489db25SIngo Weinhold	exists = (lower < Count() && fCompare(value, fElements[lower]) == 0);
4474489db25SIngo Weinhold	return lower;
4484489db25SIngo Weinhold}
4494489db25SIngo Weinhold
4504489db25SIngo Weinhold
4514489db25SIngo Weinhold// element orders
4524489db25SIngo Weinhold
4534489db25SIngo Weinholdnamespace VectorSetOrder {
4544489db25SIngo Weinhold
4554489db25SIngo Weinhold// Ascending
4564489db25SIngo Weinhold/*!	\brief A compare function object implying and ascending order.
4574489db25SIngo Weinhold
4584489db25SIngo Weinhold	The < operator must be defined on the template argument.
4594489db25SIngo Weinhold*/
4604489db25SIngo Weinholdtemplate<typename Value>
4614489db25SIngo Weinholdclass Ascending {
4624489db25SIngo Weinholdpublic:
4634489db25SIngo Weinhold	inline int operator()(const Value &a, const Value &b) const
4644489db25SIngo Weinhold	{
4654489db25SIngo Weinhold		if (a < b)
4664489db25SIngo Weinhold			return -1;
4674489db25SIngo Weinhold		else if (b < a)
4684489db25SIngo Weinhold			return 1;
4694489db25SIngo Weinhold		return 0;
4704489db25SIngo Weinhold	}
4714489db25SIngo Weinhold};
4724489db25SIngo Weinhold
4734489db25SIngo Weinhold// Descending
4744489db25SIngo Weinhold/*!	\brief A compare function object implying and descending order.
4754489db25SIngo Weinhold
4764489db25SIngo Weinhold	The < operator must be defined on the template argument.
4774489db25SIngo Weinhold*/
4784489db25SIngo Weinholdtemplate<typename Value>
4794489db25SIngo Weinholdclass Descending {
4804489db25SIngo Weinholdpublic:
4814489db25SIngo Weinhold	inline int operator()(const Value &a, const Value &b) const
4824489db25SIngo Weinhold	{
4834489db25SIngo Weinhold		if (a < b)
4844489db25SIngo Weinhold			return -1;
4854489db25SIngo Weinhold		else if (b < a)
4864489db25SIngo Weinhold			return 1;
4874489db25SIngo Weinhold		return 0;
4884489db25SIngo Weinhold	}
4894489db25SIngo Weinhold};
4904489db25SIngo Weinhold
4914489db25SIngo Weinhold}	// namespace VectorSetOrder
4924489db25SIngo Weinhold
4934489db25SIngo Weinhold#endif	// _VECTOR_SET_H
494