Dynamic 1D array tuned for performance. More...

Classes
class	DefaultComparator
	Uses < and == to evaluate operator(); this is the default comparator for Array::partition. More...

Public Types
typedef ConstIterator	const_iterator
	stl porting compatibility helper

typedef const T *	ConstIterator
	G3D C++ STL style const iterator in same style as Iterator.

typedef int	difference_type
	stl porting compatibility helper

typedef T *	Iterator
	G3D C++ STL style iterator variable.

typedef Iterator	iterator
	stl porting compatibility helper

typedef int	size_type
	stl porting compatibility helper

typedef T	value_type
	stl porting compatibility helper

Public Member Functions
	Array ()
	Creates a zero length array (no heap allocation occurs until resize).

	Array (const T &v0)
	Creates an array containing v0.

	Array (const T &v0, const T &v1)
	Creates an array containing v0 and v1.

	Array (const T &v0, const T &v1, const T &v2)
	Creates an array containing v0...v2.

	Array (const T &v0, const T &v1, const T &v2, const T &v3)
	Creates an array containing v0...v3.

	Array (const T &v0, const T &v1, const T &v2, const T &v3, const T &v4)
	Creates an array containing v0...v4.

	Array (const Array &other)
	Copy constructor.

	Array (const std::vector< T > &other)

	~Array ()
	Destructor does not delete() the objects if T is a pointer type (e.g.

void	append (const T &value)
	Add an element to the end of the array.

void	append (const T &v1, const T &v2)

void	append (const T &v1, const T &v2, const T &v3)

void	append (const T &v1, const T &v2, const T &v3, const T &v4)

void	append (const T &v1, const T &v2, const T &v3, const T &v4, const T &v5)

void	append (const T &v1, const T &v2, const T &v3, const T &v4, const T &v5, const T &v6)

void	append (const Array< T > &array)
	Append the elements of array.

void	appendPOD (const Array< T > &other)
	Resizes this to just barely match the size of other + itself and then copies the data to the end of the array from other using memcpy.

T &	back ()
	"The member function returns a reference to the last element of the controlled sequence, which must be non-empty.

const T &	back () const
	"The member function returns a reference to the last element of the controlled sequence, which must be non-empty.

Iterator	begin ()
	C++ STL style iterator method.

ConstIterator	begin () const

int	capacity () const
	"The member function returns the storage currently allocated to hold the controlled sequence, a value at least as large as size()" For compatibility with std::vector.

void	clear (bool shrink=true)
	Removes all elements.

void	clearAndSetMemoryManager (const MemoryManager::Ref &m)

bool	contains (const T &e) const
	Returns true if the given element is in the array.

void	copyFrom (const Array< T > &other)

void	copyPOD (const Array< T > &other)
	Resizes this to match the size of other and then copies the data from other using memcpy.

void G3D_DEPRECATED	deleteAll ()

ConstIterator	end () const
	C++ STL style iterator method.

Iterator	end ()

void	fastClear ()
	resize(0, false)

void	fastRemove (int index, bool shrinkIfNecessary=false)
	Swaps element index with the last element in the array then shrinks the array by one.

Iterator	find (const T &value)
	Finds an element and returns the iterator to it.

ConstIterator	find (const T &value) const

int	findIndex (const T &value) const
	Returns the index of (the first occurance of) an index or -1 if not found.

T &	first ()
	Returns element firstIndex(), performing a check in debug mode to ensure that there is at least one.

const T &	first () const

int	firstIndex () const

T &	front ()
	"The member function returns a reference to the first element of the controlled sequence, which must be non-empty.

const T &	front () const
	"The member function returns a reference to the first element of the controlled sequence, which must be non-empty.

T *	getCArray ()
	The array returned is only valid until the next append() or resize call, or the Array is deallocated.

const T *	getCArray () const
	The array returned is only valid until the next append() or resize call, or the Array is deallocated.

void	insert (int n, const T &value)
	Inserts at the specified index and shifts all other elements up by one.

void	invokeDeleteOnAllElements ()
	Calls delete on all objects[0...size-1] and sets the size to zero.

const T &	last () const
	Returns the last element, performing a check in debug mode that there is at least one element.

T &	last ()
	Returns element lastIndex()

int	lastIndex () const
	Returns size() - 1

int	length () const
	Number of elements in the array.

template<typename Comparator >
void	medianPartition (Array< T > &ltMedian, Array< T > &eqMedian, Array< T > &gtMedian, Array< T > &tempArray, const Comparator &comparator) const
	Paritions the array into those below the median, those above the median, and those elements equal to the median in expected O(n) time using quickselect.

void	medianPartition (Array< T > &ltMedian, Array< T > &eqMedian, Array< T > &gtMedian) const
	Computes a median partition using the default comparator and a dynamically allocated temporary working array.

MemoryManager::Ref	memoryManager () const

const T &	middle () const
	Returns element middleIndex()

T &	middle ()
	Returns element middleIndex()

int	middleIndex () const
	Returns iFloor(size() / 2), throws an assertion in debug mode if the array is empty.

T &	next ()
	Pushes a new element onto the end and returns its address.

Array &	operator= (const Array &other)
	Assignment operator.

Array &	operator= (const std::vector< T > &other)

T &	operator[] (int n)
	Performs bounds checks in debug mode.

T &	operator[] (uint32 n)

T &	operator[] (uint64 n)

const T &	operator[] (int n) const
	Performs bounds checks in debug mode.

const T &	operator[] (uint32 n) const

const T &	operator[] (uint64 n) const

template<typename Comparator >
void	partition (const T &partitionElement, Array< T > &ltArray, Array< T > &eqArray, Array< T > &gtArray, const Comparator &comparator) const
	The output arrays are resized with fastClear() so that if they are already of the same size as this array no memory is allocated during partitioning.

void	partition (const T &partitionElement, Array< T > &ltArray, Array< T > &eqArray, Array< T > &gtArray) const
	Uses < and == on elements to perform a partition.

T	pop (bool shrinkUnderlyingArrayIfNecessary=true)
	Removes the last element and returns it.

void	pop_back ()
	"The member function removes the last element of the controlled sequence, which must be non-empty." For compatibility with std::vector.

void	popDiscard (bool shrinkUnderlyingArrayIfNecessary=false)
	Pops the last element and discards it without returning anything.

void	push (const T &value)
	Pushes an element onto the end (appends)

void	push (const Array< T > &array)

void	push_back (const T &v)
	Alias to provide std::vector compatibility.

T &	randomElement ()

const T &	randomElement () const

void	randomize ()
	Redistributes the elements so that the new order is statistically independent of the original order.

void	remove (Iterator element, int count=1)
	Removes count elements from the array referenced either by index or Iterator.

void	remove (int index, int count=1)

void	reserve (int n)
	Ensures that future append() calls can grow up to size n without allocating memory.

void	resize (size_t n, bool shrinkIfNecessary=true)

void	reverse ()
	Reverse the elements of the array in place.

int	rfindIndex (const T &value) const
	Returns the index of (the first occurance of) an index or -1 if not found.

int	size () const
	Number of elements in the array.

size_t	sizeInMemory () const
	Number of bytes used by the array object and the memory allocated for it's data pointer.

template<class LessThan >
void	sort (const LessThan &lessThan)
	Sort using a specific less-than function, e.g.

void	sort (int direction=SORT_INCREASING)
	Sorts the array in increasing order using the > or < operator.

void	sortSubArray (int beginIndex, int endIndex, int direction=SORT_INCREASING)
	Sorts elements beginIndex through and including endIndex.

void	sortSubArray (int beginIndex, int endIndex, bool(__cdecl *lessThan)(const T &elem1, const T &elem2))

template<typename StrictWeakOrdering >
void	sortSubArray (int beginIndex, int endIndex, StrictWeakOrdering &lessThan)
	The StrictWeakOrdering can be either a class that overloads the function call operator() or a function pointer of the form `bool (__cdecl *lessThan)(const T& elem1, const T& elem2)`

void	swap (Array< T > &str)
	"The member function swaps the controlled sequences between *this and str." Note that this is slower than the optimal std implementation.

void	trimToSize ()
	Resize this array to consume exactly the capacity required by its size.

Static Public Member Functions
static void	swap (Array< T, MIN_ELEMENTS, MIN_BYTES > &a, Array< T, MIN_ELEMENTS, MIN_BYTES > &b)
	Exchanges all data between the two arrays, which are required to have a common MemoryManager.

Detailed Description

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>
class G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >

Dynamic 1D array tuned for performance.

Objects must have a default constructor (constructor that takes no arguments) in order to be used with this template. You will get the error "no appropriate default constructor found" if they do not.

Do not use with objects that overload placement operator new, since the speed of Array is partly due to pooled allocation.

Array is highly optimized compared to std::vector. Array operations are less expensive than on std::vector and for large amounts of data, Array consumes only 1.5x the total size of the data, while std::vector consumes 2.0x. The default array takes up zero heap space. The first resize (or append) operation grows it to a reasonable internal size so it is efficient to append to small arrays.

Then Array needs to copy data internally on a resize operation it correctly invokes copy constructors of the elements (the MSVC6 implementation of std::vector uses realloc, which can create memory leaks for classes containing references and pointers). Array provides a guaranteed safe way to access the underlying data as a flat C array – Array::getCArray. Although (T*)std::vector::begin() can be used for this purpose, it is not guaranteed to succeed on all platforms.

To serialize an array, see G3D::serialize.

The template parameter MIN_ELEMENTS indicates the smallest number of elements that will be allocated. The default of 10 is designed to avoid the overhead of repeatedly allocating the array as it grows from 1, to 2, and so on. If you are creating a lot of small Arrays, however, you may want to set this smaller to reduce the memory cost. Once the array has been allocated, it will never deallocate the underlying array unless MIN_ELEMENTS is set to 0, MIN_BYTES is 0, and the array is empty.

Do not subclass an Array.

See Also: G3D::SmallArray

Member Typedef Documentation

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

typedef ConstIterator G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::const_iterator

stl porting compatibility helper

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

typedef const T* G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::ConstIterator

G3D C++ STL style const iterator in same style as Iterator.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

typedef int G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::difference_type

stl porting compatibility helper

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

typedef T* G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::Iterator

G3D C++ STL style iterator variable.

Call begin() to get the first iterator, pre-increment (++i) the iterator to get to the next value. Use dereference (*i) to access the element.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

typedef Iterator G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::iterator

stl porting compatibility helper

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

typedef int G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::size_type

stl porting compatibility helper

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

typedef T G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::value_type

stl porting compatibility helper

Constructor & Destructor Documentation

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::Array ( )

inline

Creates a zero length array (no heap allocation occurs until resize).

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::Array ( const T & v0 )

inlineexplicit

Creates an array containing v0.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::Array	(	const T &	v0,
		const T &	v1
	)

inline

Creates an array containing v0 and v1.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::Array	(	const T &	v0,
		const T &	v1,
		const T &	v2
	)

inline

Creates an array containing v0...v2.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::Array	(	const T &	v0,
		const T &	v1,
		const T &	v2,
		const T &	v3
	)

inline

Creates an array containing v0...v3.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::Array	(	const T &	v0,
		const T &	v1,
		const T &	v2,
		const T &	v3,
		const T &	v4
	)

inline

Creates an array containing v0...v4.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::Array ( const Array< T, MIN_ELEMENTS, MIN_BYTES > & other )

inline

Copy constructor.

Copying arrays is slow...perhaps you want to pass a reference or a pointer instead?

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::Array ( const std::vector< T > & other )

inlineexplicit

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::~Array ( )

inline

Destructor does not delete() the objects if T is a pointer type (e.g.

T = int*) instead, it deletes the pointers themselves and leaves the objects. Call deleteAll if you want to dealocate the objects referenced. Do not call deleteAll if T is not a pointer type (e.g. do call Array<Foo*>::deleteAll, do not call Array<Foo>::deleteAll).

Member Function Documentation

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::append ( const T & value )

inline

Add an element to the end of the array.

Will not shrink the underlying array under any circumstances. It is safe to append an element that is already in the array.

Referenced by G3D::Spline< UprightFrame >::append(), G3D::Array< PreprocessedShaderSource >::append(), G3D::GLFWWindow::appendFileToFileList(), G3D::GuiDropDownList::appendValue(), G3D::Array< PreprocessedShaderSource >::copyFrom(), G3D::GApp::Settings::FilmSettings::FilmSettings(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getHandles(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::getHandles(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getIntersectingMembers(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::getIntersectingMembers(), G3D::PointHashGrid< Value, PosFunc, EqualsFunc >::getIntersectingMembers(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::getIntersectingMembers(), G3D::KDTree< Triangle >::getIntersectingMembers(), G3D::Table< std::string, DependencyList >::getKeys(), G3D::KDTree< Triangle >::getMembers(), G3D::FastPointHashGrid< Value, PosFunc >::insert(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::insert(), G3D::KDTree< Triangle >::insert(), G3D::KDTree< Triangle >::makeNode(), G3D::Array< PreprocessedShaderSource >::medianPartition(), G3D::Array< PreprocessedShaderSource >::partition(), G3D::SmallArray< Face, 6 >::push(), G3D::Array< PreprocessedShaderSource >::push(), and G3D::Welder::weld().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::append	(	const T &	v1,
		const T &	v2
	)

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::append	(	const T &	v1,
		const T &	v2,
		const T &	v3
	)

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::append	(	const T &	v1,
		const T &	v2,
		const T &	v3,
		const T &	v4
	)

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::append	(	const T &	v1,
		const T &	v2,
		const T &	v3,
		const T &	v4,
		const T &	v5
	)

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::append	(	const T &	v1,
		const T &	v2,
		const T &	v3,
		const T &	v4,
		const T &	v5,
		const T &	v6
	)

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::append ( const Array< T > & array )

inline

Append the elements of array.

Cannot be called with this array as an argument.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::appendPOD ( const Array< T > & other )

inline

Resizes this to just barely match the size of other + itself and then copies the data to the end of the array from other using memcpy.

This is only safe for POD types

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::back ( )

inline

"The member function returns a reference to the last element of the controlled sequence, which must be non-empty.

" For compatibility with std::vector.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

const T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::back ( ) const

inline

"The member function returns a reference to the last element of the controlled sequence, which must be non-empty.

" For compatibility with std::vector.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

Iterator G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::begin ( )

inline

C++ STL style iterator method.

Returns the first iterator element. Do not change the size of the array while iterating.

Referenced by G3D::Array< PreprocessedShaderSource >::remove().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

ConstIterator G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::begin ( ) const

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

int G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::capacity ( ) const

inline

"The member function returns the storage currently allocated to hold the controlled sequence, a value at least as large as size()" For compatibility with std::vector.

Referenced by G3D::Array< PreprocessedShaderSource >::trimToSize().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::clear ( bool shrink = true )

inline

Removes all elements.

Use resize(0, false) or fastClear if you want to remove all elements without deallocating the underlying array so that future append() calls will be faster.

Referenced by G3D::Spline< UprightFrame >::clear(), G3D::MeshAlg::Geometry::clear(), G3D::Array< PreprocessedShaderSource >::clearAndSetMemoryManager(), G3D::_internal::_DirectInput::clearJoysticks(), G3D::Rect2D::clip(), G3D::Array< PreprocessedShaderSource >::fastClear(), and G3D::KDTree< Triangle >::makeNode().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::clearAndSetMemoryManager ( const MemoryManager::Ref & m )

inline

Referenced by G3D::SmallArray< Face, 6 >::clearAndSetMemoryManager().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

bool G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::contains ( const T & e ) const

inline

Returns true if the given element is in the array.

Referenced by G3D::SmallArray< Face, 6 >::contains(), G3D::CameraControlWindow::containsBookmark(), and G3D::BlockPoolMemoryManager::free().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::copyFrom ( const Array< T > & other )

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::copyPOD ( const Array< T > & other )

inline

Resizes this to match the size of other and then copies the data from other using memcpy.

This is only safe for POD types

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D_DEPRECATED G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::deleteAll ( )

inline

Deprecated:

Referenced by G3D::Set< string >::deleteAll(), and G3D::BlockPoolMemoryManager::~BlockPoolMemoryManager().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

ConstIterator G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::end ( ) const

inline

C++ STL style iterator method.

Returns one after the last valid iterator element.

Referenced by G3D::Array< PreprocessedShaderSource >::find(), and G3D::Array< PreprocessedShaderSource >::remove().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

Iterator G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::end ( )

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::fastClear ( )

inline

resize(0, false)

Deprecated:

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::balance(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::clearData(), G3D::GLFWWindow::clearDroppedFileList(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::makeNode(), G3D::Array< PreprocessedShaderSource >::medianPartition(), and G3D::Array< PreprocessedShaderSource >::partition().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::fastRemove	(	int	index,
		bool	shrinkIfNecessary = `false`
	)

inline

Swaps element index with the last element in the array then shrinks the array by one.

Referenced by G3D::SmallArray< Face, 6 >::fastRemove(), G3D::KDTree< Triangle >::makeNode(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::remove(), and G3D::KDTree< Triangle >::remove().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

Iterator G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::find ( const T & value )

inline

Finds an element and returns the iterator to it.

If the element isn't found then returns end().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

ConstIterator G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::find ( const T & value ) const

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

int G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::findIndex ( const T & value ) const

inline

Returns the index of (the first occurance of) an index or -1 if not found.

Referenced by G3D::SmallArray< Face, 6 >::findIndex(), and G3D::VideoRecordDialog::setScreenShotFormat().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::first ( )

inline

Returns element firstIndex(), performing a check in debug mode to ensure that there is at least one.

Referenced by G3D::Array< PreprocessedShaderSource >::medianPartition().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

const T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::first ( ) const

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

int G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::firstIndex ( ) const

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::front ( )

inline

"The member function returns a reference to the first element of the controlled sequence, which must be non-empty.

" For compatibility with std::vector.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

const T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::front ( ) const

inline

"The member function returns a reference to the first element of the controlled sequence, which must be non-empty.

" For compatibility with std::vector.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

T* G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::getCArray ( )

inline

The array returned is only valid until the next append() or resize call, or the Array is deallocated.

Referenced by G3D::AttributeArray::AttributeArray(), G3D::cyclicCatmullRomSpline(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::getIntersectingMembers(), G3D::LightweightConduit::receive(), G3D::RenderDevice::sendIndices(), G3D::Args::setAttributePointer(), G3D::Args::setIndexPointer(), G3D::AttributeArray::update(), and G3D::AttributeArray::updateInterleaved().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

const T* G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::getCArray ( ) const

inline

The array returned is only valid until the next append() or resize call, or the Array is deallocated.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::insert	(	int	n,
		const T &	value
	)

inline

Inserts at the specified index and shifts all other elements up by one.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::invokeDeleteOnAllElements ( )

inline

Calls delete on all objects[0...size-1] and sets the size to zero.

Referenced by G3D::Array< PreprocessedShaderSource >::deleteAll().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

const T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::last ( ) const

inline

Returns the last element, performing a check in debug mode that there is at least one element.

Referenced by G3D::BlockPoolMemoryManager::alloc(), G3D::Spline< UprightFrame >::append(), G3D::_internal::PolyLineGeneric< SegmentType, VertexType >::closed(), G3D::Spline< UprightFrame >::getControl(), G3D::Array< PreprocessedShaderSource >::medianPartition(), G3D::Array< PreprocessedShaderSource >::next(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator T *(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator T *(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator->(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator->(), G3D::Array< PreprocessedShaderSource >::remove(), and G3D::_internal::PolyLineGeneric< SegmentType, VertexType >::vertex().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::last ( )

inline

Returns element lastIndex()

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

int G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::lastIndex ( ) const

inline

Returns size() - 1

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

int G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::length ( ) const

inline

Number of elements in the array.

(Same as size; this is just here for convenience).

Referenced by G3D::Array< PreprocessedShaderSource >::append(), G3D::_internal::_DirectInput::clearJoysticks(), G3D::Matrix::fromDiagonal(), G3D::_internal::_DirectInput::getJoystickInfo(), G3D::_internal::_DirectInput::getJoystickName(), G3D::_internal::_DirectInput::getJoystickState(), G3D::_internal::_DirectInput::getNumJoysticks(), G3D::_internal::_DirectInput::joystickExists(), G3D::ConvexPolygon::normal(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator++(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator++(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator==(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator==(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::remove(), G3D::KDTree< Triangle >::remove(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::Node::verifyNode(), and G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::Node::verifyNode().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

template<typename Comparator >

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::medianPartition	(	Array< T > &	ltMedian,
		Array< T > &	eqMedian,
		Array< T > &	gtMedian,
		Array< T > &	tempArray,
		const Comparator &	comparator
	)		const

inline

Paritions the array into those below the median, those above the median, and those elements equal to the median in expected O(n) time using quickselect.

If the array has an even number of different elements, the median for partition purposes is the largest value less than the median.

Parameters

tempArray	used for working scratch space
comparator	see parition() for a discussion.

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::makeNode(), G3D::KDTree< Triangle >::makeNode(), and G3D::Array< PreprocessedShaderSource >::medianPartition().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::medianPartition	(	Array< T > &	ltMedian,
		Array< T > &	eqMedian,
		Array< T > &	gtMedian
	)		const

inline

Computes a median partition using the default comparator and a dynamically allocated temporary working array.

If the median is not in the array, it is chosen to be the largest value smaller than the true median.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

MemoryManager::Ref G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::memoryManager ( ) const

inline

Referenced by G3D::Array< PreprocessedShaderSource >::swap().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

const T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::middle ( ) const

inline

Returns element middleIndex()

Referenced by G3D::Array< PreprocessedShaderSource >::medianPartition().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::middle ( )

inline

Returns element middleIndex()

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

int G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::middleIndex ( ) const

inline

Returns iFloor(size() / 2), throws an assertion in debug mode if the array is empty.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::next ( )

inline

Pushes a new element onto the end and returns its address.

This is the same as A.resize(A.size() + 1, false); A.last()

Referenced by G3D::SmallArray< Face, 6 >::next().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

Array& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::operator= ( const Array< T, MIN_ELEMENTS, MIN_BYTES > & other )

inline

Assignment operator.

Will be private in a future release because this is slow and can be invoked by accident by novice C++ programmers. If you really want to copy an Array, use the explicit copy constructor.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

Array& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::operator= ( const std::vector< T > & other )

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::operator[] ( int n )

inline

Performs bounds checks in debug mode.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::operator[] ( uint32 n )

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::operator[] ( uint64 n )

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

const T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::operator[] ( int n ) const

inline

Performs bounds checks in debug mode.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

const T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::operator[] ( uint32 n ) const

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

const T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::operator[] ( uint64 n ) const

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

template<typename Comparator >

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::partition	(	const T &	partitionElement,
		Array< T > &	ltArray,
		Array< T > &	eqArray,
		Array< T > &	gtArray,
		const Comparator &	comparator
	)		const

inline

The output arrays are resized with fastClear() so that if they are already of the same size as this array no memory is allocated during partitioning.

Parameters

comparator A function, or class instance with an overloaded operator() that compares two elements of type T and returns 0 if they are equal, -1 if the second is smaller, and 1 if the first is smaller (i.e., following the conventions of std::string::compare). For example:

int compare(int A, int B) {
    if (A < B) {
        return 1;
    } else if (A == B) {
        return 0;
    } else {
        return -1;
    }
}

Referenced by G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::makeNode(), G3D::KDTree< Triangle >::makeNode(), G3D::Array< PreprocessedShaderSource >::medianPartition(), and G3D::Array< PreprocessedShaderSource >::partition().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::partition	(	const T &	partitionElement,
		Array< T > &	ltArray,
		Array< T > &	eqArray,
		Array< T > &	gtArray
	)		const

inline

Uses < and == on elements to perform a partition.

See partition().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

T G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::pop ( bool shrinkUnderlyingArrayIfNecessary = true )

inline

Removes the last element and returns it.

By default, shrinks the underlying array.

Referenced by G3D::BlockPoolMemoryManager::alloc(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::clearData(), G3D::SmallArray< Face, 6 >::fastRemove(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator++(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator++(), G3D::SmallArray< Face, 6 >::pop(), G3D::Array< PreprocessedShaderSource >::pop_back(), and G3D::TextInput::popSettings().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::pop_back ( )

inline

"The member function removes the last element of the controlled sequence, which must be non-empty." For compatibility with std::vector.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::popDiscard ( bool shrinkUnderlyingArrayIfNecessary = false )

inline

Pops the last element and discards it without returning anything.

Faster than pop. By default, does not shrink the underlying array.

Referenced by G3D::SmallArray< Face, 6 >::popDiscard().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::push ( const T & value )

inline

Pushes an element onto the end (appends)

Referenced by G3D::BlockPoolMemoryManager::alloc(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::clearData(), G3D::BlockPoolMemoryManager::free(), G3D::PointKDTree< T, PositionFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator++(), G3D::KDTree< T, BoundsFunc, HashFunc, EqualsFunc >::BoxIntersectionIterator::operator++(), G3D::Array< PreprocessedShaderSource >::push_back(), G3D::OSWindow::pushLoopBody(), and G3D::TextInput::pushSettings().

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::push ( const Array< T > & array )

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::push_back ( const T & v )

inline

Alias to provide std::vector compatibility.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::randomElement ( )

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

const T& G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::randomElement ( ) const

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::randomize ( )

inline

Redistributes the elements so that the new order is statistically independent of the original order.

O(n) time.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::remove	(	Iterator	element,
		int	count = `1`
	)

inline

Removes count elements from the array referenced either by index or Iterator.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::remove	(	int	index,
		int	count = `1`
	)

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::reserve ( int n )

inline

Ensures that future append() calls can grow up to size n without allocating memory.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::resize	(	size_t	n,
		bool	shrinkIfNecessary = `true`
	)

inline

Parameters

shrinkIfNecessary if false, memory will never be reallocated when the array shrinks. This makes resizing much faster but can waste memory. Default = true.

See Also: clear, trimToSize

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::reverse ( )

inline

Reverse the elements of the array in place.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

int G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::rfindIndex ( const T & value ) const

inline

Returns the index of (the first occurance of) an index or -1 if not found.

Searches from the right.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

int G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::size ( ) const

inline

Number of elements in the array.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

size_t G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::sizeInMemory ( ) const

inline

Number of bytes used by the array object and the memory allocated for it's data pointer.

Does not include the memory of objects pointed to by objects in the data array

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

template<class LessThan >

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::sort ( const LessThan & lessThan )

inline

Sort using a specific less-than function, e.g.

:

bool __cdecl myLT(const MyClass& elem1, const MyClass& elem2) {
    return elem1.x < elem2.x;
}

Note that for pointer arrays, the const must come after the class name, e.g., Array<MyClass*> uses:

bool __cdecl myLT(MyClass*const& elem1, MyClass*const& elem2) {
    return elem1->x < elem2->x;
}

or a functor, e.g.,

bool
less_than_functor::operator()( const double& lhs, const double& rhs ) const
{
return( lhs < rhs? true : false );
}

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::sort ( int direction = SORT_INCREASING )

inline

Sorts the array in increasing order using the > or < operator.

To invoke this method on Array<T>, T must override those operator. You can overide these operators as follows:

bool T::operator>(const T& other) const {
   return ...;
}
bool T::operator<(const T& other) const {
   return ...;
}

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::sortSubArray	(	int	beginIndex,
		int	endIndex,
		int	direction = `SORT_INCREASING`
	)

inline

Sorts elements beginIndex through and including endIndex.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::sortSubArray	(	int	beginIndex,
		int	endIndex,
		bool(__cdecl *lessThan)(const T &elem1, const T &elem2)
	)

inline

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

template<typename StrictWeakOrdering >

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::sortSubArray	(	int	beginIndex,
		int	endIndex,
		StrictWeakOrdering &	lessThan
	)

inline

The StrictWeakOrdering can be either a class that overloads the function call operator() or a function pointer of the form bool (__cdecl *lessThan)(const T& elem1, const T& elem2)

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

static void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::swap	(	Array< T, MIN_ELEMENTS, MIN_BYTES > &	a,
		Array< T, MIN_ELEMENTS, MIN_BYTES > &	b
	)

inlinestatic

Exchanges all data between the two arrays, which are required to have a common MemoryManager.

This is a convenient way to avoid large array copies when handing off data without involving reference counting or manual memory management. Beware that pointers or references into the arrays will access memory in the other array after the swap.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::swap ( Array< T > & str )

inline

"The member function swaps the controlled sequences between *this and str." Note that this is slower than the optimal std implementation.

For compatibility with std::vector.

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>

void G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >::trimToSize ( )

inline

Resize this array to consume exactly the capacity required by its size.

See Also: clear, resize, capacity, size

Classes

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32> class G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<class T, size_t MIN_ELEMENTS = 10, size_t MIN_BYTES = 32>
class G3D::Array< T, MIN_ELEMENTS, MIN_BYTES >