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