183812f67SIngo Weinhold// Vector.h
283812f67SIngo Weinhold//
383812f67SIngo Weinhold// Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de)
483812f67SIngo Weinhold//
583812f67SIngo Weinhold// Permission is hereby granted, free of charge, to any person obtaining a
683812f67SIngo Weinhold// copy of this software and associated documentation files (the "Software"),
783812f67SIngo Weinhold// to deal in the Software without restriction, including without limitation
883812f67SIngo Weinhold// the rights to use, copy, modify, merge, publish, distribute, sublicense,
983812f67SIngo Weinhold// and/or sell copies of the Software, and to permit persons to whom the
1083812f67SIngo Weinhold// Software is furnished to do so, subject to the following conditions:
1183812f67SIngo Weinhold//
1283812f67SIngo Weinhold// The above copyright notice and this permission notice shall be included in
1383812f67SIngo Weinhold// all copies or substantial portions of the Software.
1483812f67SIngo Weinhold//
1583812f67SIngo Weinhold// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1683812f67SIngo Weinhold// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1783812f67SIngo Weinhold// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
1883812f67SIngo Weinhold// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
1983812f67SIngo Weinhold// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
2083812f67SIngo Weinhold// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
2183812f67SIngo Weinhold// DEALINGS IN THE SOFTWARE.
2283812f67SIngo Weinhold//
2383812f67SIngo Weinhold// Except as contained in this notice, the name of a copyright holder shall
2483812f67SIngo Weinhold// not be used in advertising or otherwise to promote the sale, use or other
2583812f67SIngo Weinhold// dealings in this Software without prior written authorization of the
2683812f67SIngo Weinhold// copyright holder.
2783812f67SIngo Weinhold
2883812f67SIngo Weinhold#ifndef _VECTOR_H
2983812f67SIngo Weinhold#define _VECTOR_H
3083812f67SIngo Weinhold
3183812f67SIngo Weinhold#include <new>
3283812f67SIngo Weinhold#include <stdlib.h>
3383812f67SIngo Weinhold#include <string.h>
3483812f67SIngo Weinhold
3583812f67SIngo Weinhold#include <SupportDefs.h>
3683812f67SIngo Weinhold
3783812f67SIngo Weinholdtemplate<typename Value> class VectorIterator;
3883812f67SIngo Weinhold
3983812f67SIngo Weinhold// for convenience
4083812f67SIngo Weinhold#define _VECTOR_TEMPLATE_LIST template<typename Value>
4183812f67SIngo Weinhold#define _VECTOR_CLASS_NAME Vector<Value>
4283812f67SIngo Weinhold
4383812f67SIngo Weinhold/*!
4483812f67SIngo Weinhold	\class Vector
4583812f67SIngo Weinhold	\brief A generic vector implementation.
4683812f67SIngo Weinhold*/
4783812f67SIngo Weinholdtemplate<typename Value>
4883812f67SIngo Weinholdclass Vector {
4983812f67SIngo Weinholdpublic:
5083812f67SIngo Weinhold	typedef VectorIterator<Value>		Iterator;
5183812f67SIngo Weinhold	typedef VectorIterator<const Value>	ConstIterator;
5283812f67SIngo Weinhold
5383812f67SIngo Weinholdprivate:
5483812f67SIngo Weinhold	static const size_t				kDefaultChunkSize = 10;
5583812f67SIngo Weinhold	static const size_t				kMaximalChunkSize = 1024 * 1024;
5683812f67SIngo Weinhold
5783812f67SIngo Weinholdpublic:
5883812f67SIngo Weinhold	Vector(size_t chunkSize = kDefaultChunkSize);
5983812f67SIngo Weinhold	~Vector();
6083812f67SIngo Weinhold
6183812f67SIngo Weinhold	status_t PushFront(const Value &value);
6283812f67SIngo Weinhold	status_t PushBack(const Value &value);
6383812f67SIngo Weinhold
6483812f67SIngo Weinhold	void PopFront();
6583812f67SIngo Weinhold	void PopBack();
6683812f67SIngo Weinhold
6783812f67SIngo Weinhold	status_t Insert(const Value &value, int32 index);
6883812f67SIngo Weinhold	status_t Insert(const Value &value, const Iterator &iterator);
6983812f67SIngo Weinhold
7083812f67SIngo Weinhold	int32 Remove(const Value &value);
7183812f67SIngo Weinhold	Iterator Erase(int32 index);
7283812f67SIngo Weinhold	Iterator Erase(const Iterator &iterator);
7383812f67SIngo Weinhold
7483812f67SIngo Weinhold	inline int32 Count() const;
7583812f67SIngo Weinhold	inline bool IsEmpty() const;
7683812f67SIngo Weinhold	void MakeEmpty();
7783812f67SIngo Weinhold
7883812f67SIngo Weinhold	inline Iterator Begin();
7983812f67SIngo Weinhold	inline ConstIterator Begin() const;
8083812f67SIngo Weinhold	inline Iterator End();
8183812f67SIngo Weinhold	inline ConstIterator End() const;
8283812f67SIngo Weinhold	inline Iterator Null();
8383812f67SIngo Weinhold	inline ConstIterator Null() const;
8483812f67SIngo Weinhold	inline Iterator IteratorForIndex(int32 index);
8583812f67SIngo Weinhold	inline ConstIterator IteratorForIndex(int32 index) const;
8683812f67SIngo Weinhold
8783812f67SIngo Weinhold	inline const Value &ElementAt(int32 index) const;
8883812f67SIngo Weinhold	inline Value &ElementAt(int32 index);
8983812f67SIngo Weinhold
9083812f67SIngo Weinhold	int32 IndexOf(const Value &value, int32 start = 0) const;
9183812f67SIngo Weinhold	Iterator Find(const Value &value);
9283812f67SIngo Weinhold	Iterator Find(const Value &value, const Iterator &start);
9383812f67SIngo Weinhold	ConstIterator Find(const Value &value) const;
9483812f67SIngo Weinhold	ConstIterator Find(const Value &value, const ConstIterator &start) const;
9583812f67SIngo Weinhold
9683812f67SIngo Weinhold	inline Value &operator[](int32 index);
9783812f67SIngo Weinhold	inline const Value &operator[](int32 index) const;
9883812f67SIngo Weinhold
9983812f67SIngo Weinhold	// debugging
10083812f67SIngo Weinhold	int32 GetCapacity() const	{ return fCapacity; }
10183812f67SIngo Weinhold
10283812f67SIngo Weinholdprivate:
10383812f67SIngo Weinhold	inline static void _MoveItems(Value *values, int32 offset, int32 count);
10483812f67SIngo Weinhold	bool _Resize(size_t count);
10583812f67SIngo Weinhold	inline int32 _IteratorIndex(const Iterator &iterator) const;
10683812f67SIngo Weinhold	inline int32 _IteratorIndex(const ConstIterator &iterator) const;
10783812f67SIngo Weinhold
10883812f67SIngo Weinholdprivate:
10983812f67SIngo Weinhold	size_t	fCapacity;
11083812f67SIngo Weinhold	size_t	fChunkSize;
11183812f67SIngo Weinhold	int32	fItemCount;
11283812f67SIngo Weinhold	Value	*fItems;
11383812f67SIngo Weinhold};
11483812f67SIngo Weinhold
11583812f67SIngo Weinhold
11683812f67SIngo Weinhold// VectorIterator
11783812f67SIngo Weinholdtemplate<typename Value>
11883812f67SIngo Weinholdclass VectorIterator {
11983812f67SIngo Weinholdprivate:
12083812f67SIngo Weinhold	typedef VectorIterator<Value>	Iterator;
12183812f67SIngo Weinhold
12283812f67SIngo Weinholdpublic:
12383812f67SIngo Weinhold	inline VectorIterator<Value>()
12483812f67SIngo Weinhold		: fElement(NULL)
12583812f67SIngo Weinhold	{
12683812f67SIngo Weinhold	}
12783812f67SIngo Weinhold
12883812f67SIngo Weinhold	inline VectorIterator<Value>(const Iterator &other)
12983812f67SIngo Weinhold		: fElement(other.fElement)
13083812f67SIngo Weinhold	{
13183812f67SIngo Weinhold	}
13283812f67SIngo Weinhold
13383812f67SIngo Weinhold	inline Iterator &operator++()
13483812f67SIngo Weinhold	{
13583812f67SIngo Weinhold		if (fElement)
13683812f67SIngo Weinhold			++fElement;
13783812f67SIngo Weinhold		return *this;
13883812f67SIngo Weinhold	}
13983812f67SIngo Weinhold
14083812f67SIngo Weinhold	inline Iterator operator++(int)
14183812f67SIngo Weinhold	{
14283812f67SIngo Weinhold		Iterator it(*this);
14383812f67SIngo Weinhold		++*this;
14483812f67SIngo Weinhold		return it;
14583812f67SIngo Weinhold	}
14683812f67SIngo Weinhold
14783812f67SIngo Weinhold	inline Iterator &operator--()
14883812f67SIngo Weinhold	{
14983812f67SIngo Weinhold		if (fElement)
15083812f67SIngo Weinhold			--fElement;
15183812f67SIngo Weinhold		return *this;
15283812f67SIngo Weinhold	}
15383812f67SIngo Weinhold
15483812f67SIngo Weinhold	inline Iterator operator--(int)
15583812f67SIngo Weinhold	{
15683812f67SIngo Weinhold		Iterator it(*this);
15783812f67SIngo Weinhold		--*this;
15883812f67SIngo Weinhold		return it;
15983812f67SIngo Weinhold	}
16083812f67SIngo Weinhold
16183812f67SIngo Weinhold	inline Iterator &operator=(const Iterator &other)
16283812f67SIngo Weinhold	{
16383812f67SIngo Weinhold		fElement = other.fElement;
16483812f67SIngo Weinhold		return *this;
16583812f67SIngo Weinhold	}
16683812f67SIngo Weinhold
16783812f67SIngo Weinhold
16883812f67SIngo Weinhold	inline bool operator==(const Iterator &other) const
16983812f67SIngo Weinhold	{
17083812f67SIngo Weinhold		return (fElement == other.fElement);
17183812f67SIngo Weinhold	}
17283812f67SIngo Weinhold
17383812f67SIngo Weinhold	inline bool operator!=(const Iterator &other) const
17483812f67SIngo Weinhold	{
17583812f67SIngo Weinhold		return !(*this == other);
17683812f67SIngo Weinhold	}
17783812f67SIngo Weinhold
17883812f67SIngo Weinhold	inline Value &operator*() const
17983812f67SIngo Weinhold	{
18083812f67SIngo Weinhold		return *fElement;
18183812f67SIngo Weinhold	}
18283812f67SIngo Weinhold
18383812f67SIngo Weinhold	inline Value *operator->() const
18483812f67SIngo Weinhold	{
18583812f67SIngo Weinhold		return fElement;
18683812f67SIngo Weinhold	}
18783812f67SIngo Weinhold
18883812f67SIngo Weinhold	inline operator bool() const
18983812f67SIngo Weinhold	{
19083812f67SIngo Weinhold		return fElement;
19183812f67SIngo Weinhold	}
19283812f67SIngo Weinhold
19383812f67SIngo Weinhold// private
19483812f67SIngo Weinholdpublic:
19583812f67SIngo Weinhold	inline VectorIterator<Value>(Value *element)
19683812f67SIngo Weinhold		: fElement(element)
19783812f67SIngo Weinhold	{
19883812f67SIngo Weinhold	}
19983812f67SIngo Weinhold
20083812f67SIngo Weinhold	inline Value *Element() const
20183812f67SIngo Weinhold	{
20283812f67SIngo Weinhold		return fElement;
20383812f67SIngo Weinhold	}
20483812f67SIngo Weinhold
20583812f67SIngo Weinholdprotected:
20683812f67SIngo Weinhold	Value	*fElement;
20783812f67SIngo Weinhold};
20883812f67SIngo Weinhold
20983812f67SIngo Weinhold
21083812f67SIngo Weinhold// Vector
21183812f67SIngo Weinhold
21283812f67SIngo Weinhold// constructor
21383812f67SIngo Weinhold/*!	\brief Creates an empty vector.
21483812f67SIngo Weinhold	\param chunkSize The granularity for the vector's capacity, i.e. the
21583812f67SIngo Weinhold		   minimal number of elements the capacity grows or shrinks when
21683812f67SIngo Weinhold		   necessary.
21783812f67SIngo Weinhold*/
21883812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
21983812f67SIngo Weinhold_VECTOR_CLASS_NAME::Vector(size_t chunkSize)
22083812f67SIngo Weinhold	: fCapacity(0),
22183812f67SIngo Weinhold	  fChunkSize(chunkSize),
22283812f67SIngo Weinhold	  fItemCount(0),
22383812f67SIngo Weinhold	  fItems(NULL)
22483812f67SIngo Weinhold{
22583812f67SIngo Weinhold	if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize)
22683812f67SIngo Weinhold		fChunkSize = kDefaultChunkSize;
22783812f67SIngo Weinhold	_Resize(0);
22883812f67SIngo Weinhold}
22983812f67SIngo Weinhold
23083812f67SIngo Weinhold// destructor
23183812f67SIngo Weinhold/*!	\brief Frees all resources associated with the object.
23283812f67SIngo Weinhold
23383812f67SIngo Weinhold	The contained elements are destroyed. Note, that, if the element
23483812f67SIngo Weinhold	type is a pointer type, only the pointer is destroyed, not the object
23583812f67SIngo Weinhold	it points to.
23683812f67SIngo Weinhold*/
23783812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
23883812f67SIngo Weinhold_VECTOR_CLASS_NAME::~Vector()
23983812f67SIngo Weinhold{
24083812f67SIngo Weinhold	MakeEmpty();
24183812f67SIngo Weinhold	free(fItems);
24283812f67SIngo Weinhold}
24383812f67SIngo Weinhold
24483812f67SIngo Weinhold// PushFront
24583812f67SIngo Weinhold/*!	\brief Inserts a copy of the supplied value at the beginning of the
24683812f67SIngo Weinhold		   vector.
24783812f67SIngo Weinhold	\param value The element to be inserted.
24883812f67SIngo Weinhold	\return
24983812f67SIngo Weinhold	- \c B_OK: Everything went fine.
25083812f67SIngo Weinhold	- \c B_NO_MEMORY: Insufficient memory for this operation.
25183812f67SIngo Weinhold*/
25283812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
25383812f67SIngo Weinholdstatus_t
25483812f67SIngo Weinhold_VECTOR_CLASS_NAME::PushFront(const Value &value)
25583812f67SIngo Weinhold{
25683812f67SIngo Weinhold	return Insert(value, 0);
25783812f67SIngo Weinhold}
25883812f67SIngo Weinhold
25983812f67SIngo Weinhold// PushBack
26083812f67SIngo Weinhold/*!	\brief Inserts a copy of the supplied value at the end of the vector.
26183812f67SIngo Weinhold	\param value The element to be inserted.
26283812f67SIngo Weinhold	\return
26383812f67SIngo Weinhold	- \c B_OK: Everything went fine.
26483812f67SIngo Weinhold	- \c B_NO_MEMORY: Insufficient memory for this operation.
26583812f67SIngo Weinhold*/
26683812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
26783812f67SIngo Weinholdstatus_t
26883812f67SIngo Weinhold_VECTOR_CLASS_NAME::PushBack(const Value &value)
26983812f67SIngo Weinhold{
27083812f67SIngo Weinhold	return Insert(value, fItemCount);
27183812f67SIngo Weinhold}
27283812f67SIngo Weinhold
27383812f67SIngo Weinhold// PopFront
27483812f67SIngo Weinhold/*!	\brief Removes the first element of the vector.
27583812f67SIngo Weinhold
27683812f67SIngo Weinhold	Invocation on an empty vector is harmless.
27783812f67SIngo Weinhold*/
27883812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
27983812f67SIngo Weinholdvoid
28083812f67SIngo Weinhold_VECTOR_CLASS_NAME::PopFront()
28183812f67SIngo Weinhold{
28283812f67SIngo Weinhold	if (fItemCount > 0)
28383812f67SIngo Weinhold		Erase(0);
28483812f67SIngo Weinhold}
28583812f67SIngo Weinhold
28683812f67SIngo Weinhold// PopBack
28783812f67SIngo Weinhold/*!	\brief Removes the last element of the vector.
28883812f67SIngo Weinhold
28983812f67SIngo Weinhold	Invocation on an empty vector is harmless.
29083812f67SIngo Weinhold*/
29183812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
29283812f67SIngo Weinholdvoid
29383812f67SIngo Weinhold_VECTOR_CLASS_NAME::PopBack()
29483812f67SIngo Weinhold{
29583812f67SIngo Weinhold	if (fItemCount > 0)
29683812f67SIngo Weinhold		Erase(fItemCount - 1);
29783812f67SIngo Weinhold}
29883812f67SIngo Weinhold
29983812f67SIngo Weinhold// _MoveItems
30083812f67SIngo Weinhold/*!	\brief Moves elements within an array.
30183812f67SIngo Weinhold	\param items The elements to be moved.
30283812f67SIngo Weinhold	\param offset The index to which the elements shall be moved. May be
30383812f67SIngo Weinhold		   negative.
30483812f67SIngo Weinhold	\param count The number of elements to be moved.
30583812f67SIngo Weinhold*/
30683812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
30783812f67SIngo Weinholdinline
30883812f67SIngo Weinholdvoid
30983812f67SIngo Weinhold_VECTOR_CLASS_NAME::_MoveItems(Value* items, int32 offset, int32 count)
31083812f67SIngo Weinhold{
31183812f67SIngo Weinhold	if (count > 0 && offset != 0)
31283812f67SIngo Weinhold		memmove(items + offset, items, count * sizeof(Value));
31383812f67SIngo Weinhold}
31483812f67SIngo Weinhold
31583812f67SIngo Weinhold// Insert
31683812f67SIngo Weinhold/*!	\brief Inserts a copy of the the supplied value at the given index.
31783812f67SIngo Weinhold	\param value The value to be inserted.
31883812f67SIngo Weinhold	\param index The index at which to insert the new element. It must
31983812f67SIngo Weinhold		   hold: 0 <= \a index <= Count().
32083812f67SIngo Weinhold	\return
32183812f67SIngo Weinhold	- \c B_OK: Everything went fine.
32283812f67SIngo Weinhold	- \c B_BAD_VALUE: \a index is out of range.
32383812f67SIngo Weinhold	- \c B_NO_MEMORY: Insufficient memory for this operation.
32483812f67SIngo Weinhold*/
32583812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
32683812f67SIngo Weinholdstatus_t
32783812f67SIngo Weinhold_VECTOR_CLASS_NAME::Insert(const Value &value, int32 index)
32883812f67SIngo Weinhold{
32983812f67SIngo Weinhold	if (index < 0 || index > fItemCount)
33083812f67SIngo Weinhold		return B_BAD_VALUE;
33183812f67SIngo Weinhold	if (!_Resize(fItemCount + 1))
33283812f67SIngo Weinhold		return B_NO_MEMORY;
33383812f67SIngo Weinhold	_MoveItems(fItems + index, 1, fItemCount - index - 1);
33483812f67SIngo Weinhold	new(fItems + index) Value(value);
33583812f67SIngo Weinhold	return B_OK;
33683812f67SIngo Weinhold}
33783812f67SIngo Weinhold
33883812f67SIngo Weinhold// Insert
33983812f67SIngo Weinhold/*!	\brief Inserts a copy of the the supplied value at the given position.
34083812f67SIngo Weinhold	\param value The value to be inserted.
34183812f67SIngo Weinhold	\param iterator An iterator specifying the position at which to insert
34283812f67SIngo Weinhold		   the new element.
34383812f67SIngo Weinhold	\return
34483812f67SIngo Weinhold	- \c B_OK: Everything went fine.
34583812f67SIngo Weinhold	- \c B_BAD_VALUE: \a iterator is is invalid.
34683812f67SIngo Weinhold	- \c B_NO_MEMORY: Insufficient memory for this operation.
34783812f67SIngo Weinhold*/
34883812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
34983812f67SIngo Weinholdstatus_t
35083812f67SIngo Weinhold_VECTOR_CLASS_NAME::Insert(const Value &value, const Iterator &iterator)
35183812f67SIngo Weinhold{
35283812f67SIngo Weinhold	int32 index = _IteratorIndex(iterator);
35383812f67SIngo Weinhold	if (index >= 0)
35483812f67SIngo Weinhold		return Insert(value, index);
35583812f67SIngo Weinhold	return B_BAD_VALUE;
35683812f67SIngo Weinhold}
35783812f67SIngo Weinhold
35883812f67SIngo Weinhold// Remove
35983812f67SIngo Weinhold/*!	\brief Removes all elements of the supplied value.
36083812f67SIngo Weinhold	\param value The value of the elements to be removed.
36183812f67SIngo Weinhold	\return The number of removed occurrences.
36283812f67SIngo Weinhold*/
36383812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
36483812f67SIngo Weinholdint32
36583812f67SIngo Weinhold_VECTOR_CLASS_NAME::Remove(const Value &value)
36683812f67SIngo Weinhold{
36783812f67SIngo Weinhold	int32 count = 0;
36883812f67SIngo Weinhold	for (int32 i = fItemCount - 1; i >= 0; i--) {
36983812f67SIngo Weinhold		if (ElementAt(i) == value) {
37083812f67SIngo Weinhold			Erase(i);
37183812f67SIngo Weinhold			count++;
37283812f67SIngo Weinhold		}
37383812f67SIngo Weinhold	}
37483812f67SIngo Weinhold	return count;
37583812f67SIngo Weinhold}
37683812f67SIngo Weinhold
37783812f67SIngo Weinhold// Erase
37883812f67SIngo Weinhold/*!	\brief Removes the element at the given index.
37983812f67SIngo Weinhold	\param index The position of the element to be removed.
38083812f67SIngo Weinhold	\return An iterator referring to the element now being located at index
38183812f67SIngo Weinhold			\a index (End(), if it was the last element that has been
38283812f67SIngo Weinhold			removed), or Null(), if \a index was out of range.
38383812f67SIngo Weinhold*/
38483812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
3856aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::Iterator
38683812f67SIngo Weinhold_VECTOR_CLASS_NAME::Erase(int32 index)
38783812f67SIngo Weinhold{
38883812f67SIngo Weinhold	if (index >= 0 && index < fItemCount) {
38983812f67SIngo Weinhold		fItems[index].~Value();
39083812f67SIngo Weinhold		_MoveItems(fItems + index + 1, -1, fItemCount - index - 1);
39183812f67SIngo Weinhold		_Resize(fItemCount - 1);
39283812f67SIngo Weinhold		return Iterator(fItems + index);
39383812f67SIngo Weinhold	}
39483812f67SIngo Weinhold	return Null();
39583812f67SIngo Weinhold}
39683812f67SIngo Weinhold
39783812f67SIngo Weinhold// Erase
39883812f67SIngo Weinhold/*!	\brief Removes the element at the given position.
39983812f67SIngo Weinhold	\param iterator An iterator referring to the element to be removed.
40083812f67SIngo Weinhold	\return An iterator referring to the element succeeding the removed
40183812f67SIngo Weinhold			one (End(), if it was the last element that has been
40283812f67SIngo Weinhold			removed), or Null(), if \a iterator was an invalid iterator
40383812f67SIngo Weinhold			(in this case including End()).
40483812f67SIngo Weinhold*/
40583812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
4066aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::Iterator
40783812f67SIngo Weinhold_VECTOR_CLASS_NAME::Erase(const Iterator &iterator)
40883812f67SIngo Weinhold{
40983812f67SIngo Weinhold	int32 index = _IteratorIndex(iterator);
41083812f67SIngo Weinhold	if (index >= 0 && index < fItemCount)
41183812f67SIngo Weinhold		return Erase(index);
41283812f67SIngo Weinhold	return Null();
41383812f67SIngo Weinhold}
41483812f67SIngo Weinhold
41583812f67SIngo Weinhold// Count
41683812f67SIngo Weinhold/*!	\brief Returns the number of elements the vector contains.
41783812f67SIngo Weinhold	\return The number of elements the vector contains.
41883812f67SIngo Weinhold*/
41983812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
42083812f67SIngo Weinholdinline
42183812f67SIngo Weinholdint32
42283812f67SIngo Weinhold_VECTOR_CLASS_NAME::Count() const
42383812f67SIngo Weinhold{
42483812f67SIngo Weinhold	return fItemCount;
42583812f67SIngo Weinhold}
42683812f67SIngo Weinhold
42783812f67SIngo Weinhold// IsEmpty
42883812f67SIngo Weinhold/*!	\brief Returns whether the vector is empty.
42983812f67SIngo Weinhold	\return \c true, if the vector is empty, \c false otherwise.
43083812f67SIngo Weinhold*/
43183812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
43283812f67SIngo Weinholdinline
43383812f67SIngo Weinholdbool
43483812f67SIngo Weinhold_VECTOR_CLASS_NAME::IsEmpty() const
43583812f67SIngo Weinhold{
43683812f67SIngo Weinhold	return (fItemCount == 0);
43783812f67SIngo Weinhold}
43883812f67SIngo Weinhold
43983812f67SIngo Weinhold// MakeEmpty
44083812f67SIngo Weinhold/*!	\brief Removes all elements from the vector.
44183812f67SIngo Weinhold*/
44283812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
44383812f67SIngo Weinholdvoid
44483812f67SIngo Weinhold_VECTOR_CLASS_NAME::MakeEmpty()
44583812f67SIngo Weinhold{
44683812f67SIngo Weinhold	for (int32 i = 0; i < fItemCount; i++)
44783812f67SIngo Weinhold		fItems[i].~Value();
44883812f67SIngo Weinhold	_Resize(0);
44983812f67SIngo Weinhold}
45083812f67SIngo Weinhold
45183812f67SIngo Weinhold// Begin
45283812f67SIngo Weinhold/*!	\brief Returns an iterator referring to the beginning of the vector.
45383812f67SIngo Weinhold
45483812f67SIngo Weinhold	If the vector is not empty, Begin() refers to its first element,
45583812f67SIngo Weinhold	otherwise it is equal to End() and must not be dereferenced!
45683812f67SIngo Weinhold
45783812f67SIngo Weinhold	\return An iterator referring to the beginning of the vector.
45883812f67SIngo Weinhold*/
45983812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
46083812f67SIngo Weinholdinline
4616aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::Iterator
46283812f67SIngo Weinhold_VECTOR_CLASS_NAME::Begin()
46383812f67SIngo Weinhold{
46483812f67SIngo Weinhold	return Iterator(fItems);
46583812f67SIngo Weinhold}
46683812f67SIngo Weinhold
46783812f67SIngo Weinhold// Begin
46883812f67SIngo Weinhold/*!	\brief Returns an iterator referring to the beginning of the vector.
46983812f67SIngo Weinhold
47083812f67SIngo Weinhold	If the vector is not empty, Begin() refers to its first element,
47183812f67SIngo Weinhold	otherwise it is equal to End() and must not be dereferenced!
47283812f67SIngo Weinhold
47383812f67SIngo Weinhold	\return An iterator referring to the beginning of the vector.
47483812f67SIngo Weinhold*/
47583812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
47683812f67SIngo Weinholdinline
4776aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::ConstIterator
47883812f67SIngo Weinhold_VECTOR_CLASS_NAME::Begin() const
47983812f67SIngo Weinhold{
48083812f67SIngo Weinhold	return ConstIterator(fItems);
48183812f67SIngo Weinhold}
48283812f67SIngo Weinhold
48383812f67SIngo Weinhold// End
48483812f67SIngo Weinhold/*!	\brief Returns an iterator referring to the end of the vector.
48583812f67SIngo Weinhold
48683812f67SIngo Weinhold	The position identified by End() is the one succeeding the last
48783812f67SIngo Weinhold	element, i.e. it must not be dereferenced!
48883812f67SIngo Weinhold
48983812f67SIngo Weinhold	\return An iterator referring to the end of the vector.
49083812f67SIngo Weinhold*/
49183812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
49283812f67SIngo Weinholdinline
4936aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::Iterator
49483812f67SIngo Weinhold_VECTOR_CLASS_NAME::End()
49583812f67SIngo Weinhold{
49683812f67SIngo Weinhold	return Iterator(fItems + fItemCount);
49783812f67SIngo Weinhold}
49883812f67SIngo Weinhold
49983812f67SIngo Weinhold// End
50083812f67SIngo Weinhold/*!	\brief Returns an iterator referring to the end of the vector.
50183812f67SIngo Weinhold
50283812f67SIngo Weinhold	The position identified by End() is the one succeeding the last
50383812f67SIngo Weinhold	element, i.e. it must not be dereferenced!
50483812f67SIngo Weinhold
50583812f67SIngo Weinhold	\return An iterator referring to the end of the vector.
50683812f67SIngo Weinhold*/
50783812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
50883812f67SIngo Weinholdinline
5096aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::ConstIterator
51083812f67SIngo Weinhold_VECTOR_CLASS_NAME::End() const
51183812f67SIngo Weinhold{
51283812f67SIngo Weinhold	return ConstIterator(fItems + fItemCount);
51383812f67SIngo Weinhold}
51483812f67SIngo Weinhold
51583812f67SIngo Weinhold// Null
51683812f67SIngo Weinhold/*!	\brief Returns an invalid iterator.
51783812f67SIngo Weinhold
51883812f67SIngo Weinhold	Null() is used as a return value, if something went wrong. It must
51983812f67SIngo Weinhold	neither be incremented or decremented nor dereferenced!
52083812f67SIngo Weinhold
52183812f67SIngo Weinhold	\return An invalid iterator.
52283812f67SIngo Weinhold*/
52383812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
52483812f67SIngo Weinholdinline
5256aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::Iterator
52683812f67SIngo Weinhold_VECTOR_CLASS_NAME::Null()
52783812f67SIngo Weinhold{
52883812f67SIngo Weinhold	return Iterator(NULL);
52983812f67SIngo Weinhold}
53083812f67SIngo Weinhold
53183812f67SIngo Weinhold// Null
53283812f67SIngo Weinhold/*!	\brief Returns an invalid iterator.
53383812f67SIngo Weinhold
53483812f67SIngo Weinhold	Null() is used as a return value, if something went wrong. It must
53583812f67SIngo Weinhold	neither be incremented or decremented nor dereferenced!
53683812f67SIngo Weinhold
53783812f67SIngo Weinhold	\return An invalid iterator.
53883812f67SIngo Weinhold*/
53983812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
54083812f67SIngo Weinholdinline
5416aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::ConstIterator
54283812f67SIngo Weinhold_VECTOR_CLASS_NAME::Null() const
54383812f67SIngo Weinhold{
54483812f67SIngo Weinhold	return ConstIterator(NULL);
54583812f67SIngo Weinhold}
54683812f67SIngo Weinhold
54783812f67SIngo Weinhold// IteratorForIndex
54883812f67SIngo Weinhold/*!	\brief Returns an iterator for a given index.
54983812f67SIngo Weinhold	\return An iterator referring to the same element as \a index, or
55083812f67SIngo Weinhold			End(), if \a index is out of range.
55183812f67SIngo Weinhold*/
55283812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
55383812f67SIngo Weinholdinline
5546aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::Iterator
55583812f67SIngo Weinhold_VECTOR_CLASS_NAME::IteratorForIndex(int32 index)
55683812f67SIngo Weinhold{
55783812f67SIngo Weinhold	if (index >= 0 && index <= fItemCount)
55883812f67SIngo Weinhold		return Iterator(fItems + index);
55983812f67SIngo Weinhold	return End();
56083812f67SIngo Weinhold}
56183812f67SIngo Weinhold
56283812f67SIngo Weinhold// IteratorForIndex
56383812f67SIngo Weinhold/*!	\brief Returns an iterator for a given index.
56483812f67SIngo Weinhold	\return An iterator referring to the same element as \a index, or
56583812f67SIngo Weinhold			End(), if \a index is out of range.
56683812f67SIngo Weinhold*/
56783812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
56883812f67SIngo Weinholdinline
5696aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::ConstIterator
57083812f67SIngo Weinhold_VECTOR_CLASS_NAME::IteratorForIndex(int32 index) const
57183812f67SIngo Weinhold{
57283812f67SIngo Weinhold	if (index >= 0 && index <= fItemCount)
57383812f67SIngo Weinhold		return ConstIterator(fItems + index);
57483812f67SIngo Weinhold	return End();
57583812f67SIngo Weinhold}
57683812f67SIngo Weinhold
57783812f67SIngo Weinhold// ElementAt
57883812f67SIngo Weinhold/*!	\brief Returns the element at a given index.
57983812f67SIngo Weinhold	\param index The index identifying the element to be returned.
58083812f67SIngo Weinhold	\return The element identified by the given index.
58183812f67SIngo Weinhold*/
58283812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
58383812f67SIngo Weinholdinline
58483812f67SIngo Weinholdconst Value &
58583812f67SIngo Weinhold_VECTOR_CLASS_NAME::ElementAt(int32 index) const
58683812f67SIngo Weinhold{
58783812f67SIngo Weinhold	if (index >= 0 && index < fItemCount)
58883812f67SIngo Weinhold		return fItems[index];
58983812f67SIngo Weinhold	// Return the 0th element by default. Unless the allocation failed, there
59083812f67SIngo Weinhold	// is always a 0th element -- uninitialized perhaps.
59183812f67SIngo Weinhold	return fItems[0];
59283812f67SIngo Weinhold}
59383812f67SIngo Weinhold
59483812f67SIngo Weinhold// ElementAt
59583812f67SIngo Weinhold/*!	\brief Returns the element at a given index.
59683812f67SIngo Weinhold	\param index The index identifying the element to be returned.
59783812f67SIngo Weinhold	\return The element identified by the given index.
59883812f67SIngo Weinhold*/
59983812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
60083812f67SIngo Weinholdinline
60183812f67SIngo WeinholdValue &
60283812f67SIngo Weinhold_VECTOR_CLASS_NAME::ElementAt(int32 index)
60383812f67SIngo Weinhold{
60483812f67SIngo Weinhold	if (index >= 0 && index < fItemCount)
60583812f67SIngo Weinhold		return fItems[index];
60683812f67SIngo Weinhold	// Return the 0th element by default. Unless the allocation failed, there
60783812f67SIngo Weinhold	// is always a 0th element -- uninitialized perhaps.
60883812f67SIngo Weinhold	return fItems[0];
60983812f67SIngo Weinhold}
61083812f67SIngo Weinhold
61183812f67SIngo Weinhold// IndexOf
61283812f67SIngo Weinhold/*!	\brief Returns the index of the next element with the specified value.
61383812f67SIngo Weinhold	\param value The value of the element to be found.
61483812f67SIngo Weinhold	\param start The index at which to be started to search for the element.
61583812f67SIngo Weinhold	\return The index of the found element, or \c -1, if no further element
61683812f67SIngo Weinhold			with the given value could be found or \a index is out of range.
61783812f67SIngo Weinhold*/
61883812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
61983812f67SIngo Weinholdint32
62083812f67SIngo Weinhold_VECTOR_CLASS_NAME::IndexOf(const Value &value, int32 start) const
62183812f67SIngo Weinhold{
62283812f67SIngo Weinhold	if (start >= 0) {
62383812f67SIngo Weinhold		for (int32 i = start; i < fItemCount; i++) {
62483812f67SIngo Weinhold			if (fItems[i] == value)
62583812f67SIngo Weinhold				return i;
62683812f67SIngo Weinhold		}
62783812f67SIngo Weinhold	}
62883812f67SIngo Weinhold	return -1;
62983812f67SIngo Weinhold}
63083812f67SIngo Weinhold
63183812f67SIngo Weinhold// Find
63283812f67SIngo Weinhold/*!	\brief Returns an iterator referring to the next element with the
63383812f67SIngo Weinhold		   specified value.
63483812f67SIngo Weinhold	\param value The value of the element to be found.
63583812f67SIngo Weinhold	\return An iterator referring to the found element, or End(), if no
63683812f67SIngo Weinhold			further with the given value could be found.
63783812f67SIngo Weinhold*/
63883812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
63983812f67SIngo Weinholdinline
6406aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::Iterator
64183812f67SIngo Weinhold_VECTOR_CLASS_NAME::Find(const Value &value)
64283812f67SIngo Weinhold{
64383812f67SIngo Weinhold	return Find(value, Begin());
64483812f67SIngo Weinhold}
64583812f67SIngo Weinhold
64683812f67SIngo Weinhold// Find
64783812f67SIngo Weinhold/*!	\brief Returns an iterator referring to the next element with the
64883812f67SIngo Weinhold		   specified value.
64983812f67SIngo Weinhold	\param value The value of the element to be found.
65083812f67SIngo Weinhold	\param start And iterator specifying where to start searching for the
65183812f67SIngo Weinhold		   element.
65283812f67SIngo Weinhold	\return An iterator referring to the found element, or End(), if no
65383812f67SIngo Weinhold			further with the given value could be found or \a start was
65483812f67SIngo Weinhold			invalid.
65583812f67SIngo Weinhold*/
65683812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
6576aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::Iterator
65883812f67SIngo Weinhold_VECTOR_CLASS_NAME::Find(const Value &value, const Iterator &start)
65983812f67SIngo Weinhold{
66083812f67SIngo Weinhold	int32 index = IndexOf(value, _IteratorIndex(start));
66183812f67SIngo Weinhold	if (index >= 0)
66283812f67SIngo Weinhold		return Iterator(fItems + index);
66383812f67SIngo Weinhold	return End();
66483812f67SIngo Weinhold}
66583812f67SIngo Weinhold
66683812f67SIngo Weinhold// Find
66783812f67SIngo Weinhold/*!	\brief Returns an iterator referring to the of the next element with the
66883812f67SIngo Weinhold		   specified value.
66983812f67SIngo Weinhold	\param value The value of the element to be found.
67083812f67SIngo Weinhold	\return An iterator referring to the found element, or End(), if no
67183812f67SIngo Weinhold			further with the given value could be found.
67283812f67SIngo Weinhold*/
67383812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
67483812f67SIngo Weinholdinline
6756aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::ConstIterator
67683812f67SIngo Weinhold_VECTOR_CLASS_NAME::Find(const Value &value) const
67783812f67SIngo Weinhold{
67883812f67SIngo Weinhold	return Find(value, Begin());
67983812f67SIngo Weinhold}
68083812f67SIngo Weinhold
68183812f67SIngo Weinhold// Find
68283812f67SIngo Weinhold/*!	\brief Returns an iterator referring to the of the next element with the
68383812f67SIngo Weinhold		   specified value.
68483812f67SIngo Weinhold	\param value The value of the element to be found.
68583812f67SIngo Weinhold	\param start And iterator specifying where to start searching for the
68683812f67SIngo Weinhold		   element.
68783812f67SIngo Weinhold	\return An iterator referring to the found element, or End(), if no
68883812f67SIngo Weinhold			further with the given value could be found or \a start was
68983812f67SIngo Weinhold			invalid.
69083812f67SIngo Weinhold*/
69183812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
6926aeea78cSIngo Weinholdtypename _VECTOR_CLASS_NAME::ConstIterator
69383812f67SIngo Weinhold_VECTOR_CLASS_NAME::Find(const Value &value, const ConstIterator &start) const
69483812f67SIngo Weinhold{
69583812f67SIngo Weinhold	int32 index = IndexOf(value, _IteratorIndex(start));
69683812f67SIngo Weinhold	if (index >= 0)
69783812f67SIngo Weinhold		return ConstIterator(fItems + index);
69883812f67SIngo Weinhold	return End();
69983812f67SIngo Weinhold}
70083812f67SIngo Weinhold
70183812f67SIngo Weinhold// []
70283812f67SIngo Weinhold/*!	\brief Semantically equivalent to ElementAt().
70383812f67SIngo Weinhold*/
70483812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
70583812f67SIngo Weinholdinline
70683812f67SIngo WeinholdValue &
70783812f67SIngo Weinhold_VECTOR_CLASS_NAME::operator[](int32 index)
70883812f67SIngo Weinhold{
70983812f67SIngo Weinhold	return ElementAt(index);
71083812f67SIngo Weinhold}
71183812f67SIngo Weinhold
71283812f67SIngo Weinhold// []
71383812f67SIngo Weinhold/*!	\brief Semantically equivalent to ElementAt().
71483812f67SIngo Weinhold*/
71583812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
71683812f67SIngo Weinholdinline
71783812f67SIngo Weinholdconst Value &
71883812f67SIngo Weinhold_VECTOR_CLASS_NAME::operator[](int32 index) const
71983812f67SIngo Weinhold{
72083812f67SIngo Weinhold	return ElementAt(index);
72183812f67SIngo Weinhold}
72283812f67SIngo Weinhold
72383812f67SIngo Weinhold// _Resize
72483812f67SIngo Weinhold/*!	\brief Resizes the vector.
72583812f67SIngo Weinhold
72683812f67SIngo Weinhold	The internal element array will be grown or shrunk to the next multiple
72783812f67SIngo Weinhold	of \a fChunkSize >= \a count, but no less than \a fChunkSize.
72883812f67SIngo Weinhold
72983812f67SIngo Weinhold	Also adjusts \a fItemCount according to the supplied \a count, but does
73083812f67SIngo Weinhold	not invoke a destructor or constructor on any element.
73183812f67SIngo Weinhold
73283812f67SIngo Weinhold	\param count The number of element.
73383812f67SIngo Weinhold	\return \c true, if everything went fine, \c false, if the memory
73483812f67SIngo Weinhold			allocation failed.
73583812f67SIngo Weinhold*/
73683812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
73783812f67SIngo Weinholdbool
73883812f67SIngo Weinhold_VECTOR_CLASS_NAME::_Resize(size_t count)
73983812f67SIngo Weinhold{
74083812f67SIngo Weinhold	bool result = true;
74183812f67SIngo Weinhold	// calculate the new capacity
74283812f67SIngo Weinhold	int32 newSize = count;
74383812f67SIngo Weinhold	if (newSize <= 0)
74483812f67SIngo Weinhold		newSize = 1;
74583812f67SIngo Weinhold	newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize;
74683812f67SIngo Weinhold	// resize if necessary
74783812f67SIngo Weinhold	if ((size_t)newSize != fCapacity) {
74883812f67SIngo Weinhold		Value* newItems = (Value*)realloc(fItems, newSize * sizeof(Value));
74983812f67SIngo Weinhold		if (newItems) {
75083812f67SIngo Weinhold			fItems = newItems;
75183812f67SIngo Weinhold			fCapacity = newSize;
75283812f67SIngo Weinhold		} else
75383812f67SIngo Weinhold			result = false;
75483812f67SIngo Weinhold	}
75583812f67SIngo Weinhold	if (result)
75683812f67SIngo Weinhold		fItemCount = count;
75783812f67SIngo Weinhold	return result;
75883812f67SIngo Weinhold}
75983812f67SIngo Weinhold
76083812f67SIngo Weinhold// _IteratorIndex
76183812f67SIngo Weinhold/*!	\brief Returns index of the element the supplied iterator refers to.
76283812f67SIngo Weinhold	\return The index of the element the supplied iterator refers to, or
76383812f67SIngo Weinhold			\c -1, if the iterator is invalid (End() is considered valid
76483812f67SIngo Weinhold			here, and Count() is returned).
76583812f67SIngo Weinhold*/
76683812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
76783812f67SIngo Weinholdinline
76883812f67SIngo Weinholdint32
76983812f67SIngo Weinhold_VECTOR_CLASS_NAME::_IteratorIndex(const Iterator &iterator) const
77083812f67SIngo Weinhold{
77183812f67SIngo Weinhold	if (iterator.Element()) {
77283812f67SIngo Weinhold		int32 index = iterator.Element() - fItems;
77383812f67SIngo Weinhold		if (index >= 0 && index <= fItemCount)
77483812f67SIngo Weinhold			return index;
77583812f67SIngo Weinhold	}
77683812f67SIngo Weinhold	return -1;
77783812f67SIngo Weinhold}
77883812f67SIngo Weinhold
77983812f67SIngo Weinhold// _IteratorIndex
78083812f67SIngo Weinhold/*!	\brief Returns index of the element the supplied iterator refers to.
78183812f67SIngo Weinhold	\return The index of the element the supplied iterator refers to, or
78283812f67SIngo Weinhold			\c -1, if the iterator is invalid (End() is considered valid
78383812f67SIngo Weinhold			here, and Count() is returned).
78483812f67SIngo Weinhold*/
78583812f67SIngo Weinhold_VECTOR_TEMPLATE_LIST
78683812f67SIngo Weinholdinline
78783812f67SIngo Weinholdint32
78883812f67SIngo Weinhold_VECTOR_CLASS_NAME::_IteratorIndex(const ConstIterator &iterator) const
78983812f67SIngo Weinhold{
79083812f67SIngo Weinhold	if (iterator.Element()) {
79183812f67SIngo Weinhold		int32 index = iterator.Element() - fItems;
79283812f67SIngo Weinhold		if (index >= 0 && index <= fItemCount)
79383812f67SIngo Weinhold			return index;
79483812f67SIngo Weinhold	}
79583812f67SIngo Weinhold	return -1;
79683812f67SIngo Weinhold}
79783812f67SIngo Weinhold
79883812f67SIngo Weinhold#endif	// _VECTOR_H
799