An array that keeps track of the number of inserted elements; also usable as an efficient stack. More...

#include <ogdf/basic/ArrayBuffer.h>

Inheritance diagram for ogdf::ArrayBuffer< E, INDEX >:

Public Member Functions
	ArrayBuffer ()
	Constructs an empty ArrayBuffer, without initial memory allocation.
	ArrayBuffer (INDEX size)
	Constructs an empty ArrayBuffer, allocating memory for up to size elements.
E *	begin ()
	Returns a pointer to the first element.
const E *	begin () const
	Returns a pointer to the first element.
void	clear ()
	Clears the buffer.
void	compactCopy (Array< E, INDEX > &A2) const
	Generates a compact copy holding the current elements.
void	compactCpycon (Array< E, INDEX > &A2) const
	Generates a compact copy holding the current elements.
void	compactMemcpy (Array< E, INDEX > &A2) const
	Generates a compact copy holding the current elements.
bool	empty () const
	Returns true if the buffer is empty, false otherwise.
E *	end ()
	Returns a pointer to one past the last element.
const E *	end () const
	Returns a pointer to one past the last element.
void	init ()
	Reinitializes the array, clearing it, and without initial memory allocation.
void	init (INDEX size)
	Reinitializes the array, clearing it, and allocating memory for up to size elements.
INDEX	linearSearch (const E &x) const
	Performs a linear search for element x.
template<class COMPARER >
INDEX	linearSearch (const E &x, const COMPARER &comp) const
	Performs a linear search for element x with comparer comp.
const E &	operator[] (INDEX i) const
	Returns a reference to the element at position i.
E &	operator[] (INDEX i)
	Returns a reference to the element at position i.
void	pop ()
	Removes the newest element from the buffer.
E	popRet ()
	Removes the newest element from the buffer and returns it.
void	push (E e)
	Puts a new element in the buffer.
E *	rbegin ()
	Returns a pointer to the last element.
const E *	rbegin () const
	Returns a pointer to the last element.
E *	rend ()
	Returns a pointer to one before the first element.
const E *	rend () const
	Returns a pointer to one before the first element.
INDEX	size () const
	Returns number of elements in the buffer.
const E &	top () const
	Returns the newest element of the buffer.
E &	top ()
	Returns the newest element of the buffer.

Private Attributes
INDEX	num
	The number of elements in te buffer.

Additional Inherited Members
Private Types inherited from ogdf::Array< E, INDEX >
enum	{ maxSizeInsertionSort = 40 }
Private Member Functions inherited from ogdf::Array< E, INDEX >
	Array ()
	Creates an array with empty index set.
	Array (INDEX s)
	Creates an array with index set [0..s-1].
	Array (INDEX a, INDEX b)
	Creates an array with index set [a..b].
	Array (INDEX a, INDEX b, const E &x)
	Creates an array with index set [a..b] and initializes each element with x.
	Array (const Array< E > &A)
	Creates an array that is a copy of A.
	~Array ()
int	binarySearch (const E &x) const
	Performs a binary search for element x.
template<class COMPARER >
int	binarySearch (const E &e, const COMPARER &comp) const
	Performs a binary search for element x with comparer comp.
void	fill (const E &x)
	Sets all elements to x.
void	fill (INDEX i, INDEX j, const E &x)
	Sets elements in the intervall [i..j] to x.
void	grow (INDEX add, const E &x)
	Enlarges the array by add elements and sets new elements to x.
void	grow (INDEX add)
	Enlarges the array by add elements.
INDEX	high () const
	Returns the maximal array index.
void	init (INDEX a, INDEX b)
	Reinitializes the array to an array with index set [a..b].
void	init (INDEX a, INDEX b, const E &x)
	Reinitializes the array to an array with index set [a..b] and sets all entries to x.
INDEX	low () const
	Returns the minimal array index.
Array< E, INDEX > &	operator= (const Array< E, INDEX > &array2)
	Assignment operator.
void	permute (INDEX l, INDEX r)
	Randomly permutes the subarray with index set [l..r].
void	permute ()
	Randomly permutes the array.
void	quicksort ()
	Sorts array using Quicksort.
void	quicksort (INDEX l, INDEX r)
	Sorts subarray with index set [l..r] using Quicksort.
template<class COMPARER >
void	quicksort (const COMPARER &comp)
	Sorts array using Quicksort and a user-defined comparer comp.
template<class COMPARER >
void	quicksort (INDEX l, INDEX r, const COMPARER &comp)
	Sorts the subarray with index set [l..r] using Quicksort and a user-defined comparer comp.
void	swap (INDEX i, INDEX j)
	Swaps the elements at position i and j.

Detailed Description

template<class E, class INDEX = int>
class ogdf::ArrayBuffer< E, INDEX >

An array that keeps track of the number of inserted elements; also usable as an efficient stack.

This is a growable array (with some initial size s) which starts out being empty. Using stack functions you can put elements into and out of it. The initial array size is automatically expanded if neccessary, but never automatically shrunken. You may also access the elements it contains using the []-operator. Tha valid indices are 0..(s - 1).

Template Parameters:

E	denotes the element type.
INDEX	denotes the index type. The index type must be chosen such that it can express the whole index range of the array instance, as well as its size. The default index type is `int`, other possible types are `short` and `long long` (on 64-bit systems).

Definition at line 68 of file ArrayBuffer.h.

Constructor & Destructor Documentation

template<class E, class INDEX = int>

ogdf::ArrayBuffer< E, INDEX >::ArrayBuffer ( )

inline

Constructs an empty ArrayBuffer, without initial memory allocation.

Definition at line 72 of file ArrayBuffer.h.

template<class E, class INDEX = int>

ogdf::ArrayBuffer< E, INDEX >::ArrayBuffer ( INDEX size )

inlineexplicit

Constructs an empty ArrayBuffer, allocating memory for up to size elements.

Definition at line 74 of file ArrayBuffer.h.

Member Function Documentation

template<class E, class INDEX = int>

E* ogdf::ArrayBuffer< E, INDEX >::begin ( )

inline

Returns a pointer to the first element.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 108 of file ArrayBuffer.h.

template<class E, class INDEX = int>

const E* ogdf::ArrayBuffer< E, INDEX >::begin ( ) const

inline

Returns a pointer to the first element.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 111 of file ArrayBuffer.h.

template<class E, class INDEX = int>

void ogdf::ArrayBuffer< E, INDEX >::clear ( )

inline

Clears the buffer.

Definition at line 82 of file ArrayBuffer.h.

template<class E, class INDEX = int>

void ogdf::ArrayBuffer< E, INDEX >::compactCopy ( Array< E, INDEX > & A2 ) const

inline

Generates a compact copy holding the current elements.

Creates a copy of the ArrayBuffer and stores it into the given Array A. A has exactly the neccessary size to hold all elements in the buffer.

This method uses an elementwise operator=. If you need a bitcopy of the buffer, use compactMemcpy() instead; if you need a traditional array copy (using the Array's copy-constructor) use compactCpyCon() instead.

Definition at line 154 of file ArrayBuffer.h.

template<class E, class INDEX = int>

void ogdf::ArrayBuffer< E, INDEX >::compactCpycon ( Array< E, INDEX > & A2 ) const

inline

Generates a compact copy holding the current elements.

Creates a copy of the ArrayBuffer and stores it into the given Array A. A has exactly the neccessary size to hold all elements in the buffer

This method uses the Array's copy constructur. If you need a bitcopy of the buffer, use compactMemcpy() instead; if you neeed a elementwise operator=-copy, use compactCopy() instead.

Definition at line 176 of file ArrayBuffer.h.

template<class E, class INDEX = int>

void ogdf::ArrayBuffer< E, INDEX >::compactMemcpy ( Array< E, INDEX > & A2 ) const

inline

Generates a compact copy holding the current elements.

Creates a copy of the ArrayBuffer and stores it into the given Array A. A has exactly the neccessary size to hold all elements in the buffer.

This method uses memcpy. If you need a traditional arraycopy using a copy constructur, use compactCopy() instead; if you neeed a elementwise operator=-copy, use compactCopy() instead.

Definition at line 199 of file ArrayBuffer.h.

template<class E, class INDEX = int>

bool ogdf::ArrayBuffer< E, INDEX >::empty ( ) const

inline

Returns true if the buffer is empty, false otherwise.

Definition at line 102 of file ArrayBuffer.h.

template<class E, class INDEX = int>

E* ogdf::ArrayBuffer< E, INDEX >::end ( )

inline

Returns a pointer to one past the last element.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 114 of file ArrayBuffer.h.

template<class E, class INDEX = int>

const E* ogdf::ArrayBuffer< E, INDEX >::end ( ) const

inline

Returns a pointer to one past the last element.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 117 of file ArrayBuffer.h.

template<class E, class INDEX = int>

void ogdf::ArrayBuffer< E, INDEX >::init ( )

inline

Reinitializes the array, clearing it, and without initial memory allocation.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 77 of file ArrayBuffer.h.

template<class E, class INDEX = int>

void ogdf::ArrayBuffer< E, INDEX >::init ( INDEX size )

inline

Reinitializes the array, clearing it, and allocating memory for up to size elements.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 79 of file ArrayBuffer.h.

template<class E, class INDEX = int>

INDEX ogdf::ArrayBuffer< E, INDEX >::linearSearch ( const E & x ) const

inline

Performs a linear search for element x.

Warning: linear running time! Note that the linear search runs from back to front.

Returns:: the index of the found element, and low()-1 if not found.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 214 of file ArrayBuffer.h.

template<class E, class INDEX = int>

template<class COMPARER >

INDEX ogdf::ArrayBuffer< E, INDEX >::linearSearch	(	const E &	x,
		const COMPARER &	comp
	)		const

inline

Performs a linear search for element x with comparer comp.

Warning: linear running time! Note that the linear search runs from back to front.

Returns:: the index of the found element, and low()-1 if not found.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 228 of file ArrayBuffer.h.

template<class E, class INDEX = int>

const E& ogdf::ArrayBuffer< E, INDEX >::operator[] ( INDEX i ) const

inline

Returns a reference to the element at position i.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 132 of file ArrayBuffer.h.

template<class E, class INDEX = int>

E& ogdf::ArrayBuffer< E, INDEX >::operator[] ( INDEX i )

inline

Returns a reference to the element at position i.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 137 of file ArrayBuffer.h.

template<class E, class INDEX = int>

void ogdf::ArrayBuffer< E, INDEX >::pop ( )

inline

Removes the newest element from the buffer.

Definition at line 97 of file ArrayBuffer.h.

template<class E, class INDEX = int>

E ogdf::ArrayBuffer< E, INDEX >::popRet ( )

inline

Removes the newest element from the buffer and returns it.

Definition at line 99 of file ArrayBuffer.h.

template<class E, class INDEX = int>

void ogdf::ArrayBuffer< E, INDEX >::push ( E e )

inline

Puts a new element in the buffer.

Definition at line 90 of file ArrayBuffer.h.

template<class E, class INDEX = int>

E* ogdf::ArrayBuffer< E, INDEX >::rbegin ( )

inline

Returns a pointer to the last element.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 120 of file ArrayBuffer.h.

template<class E, class INDEX = int>

const E* ogdf::ArrayBuffer< E, INDEX >::rbegin ( ) const

inline

Returns a pointer to the last element.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 123 of file ArrayBuffer.h.

template<class E, class INDEX = int>

E* ogdf::ArrayBuffer< E, INDEX >::rend ( )

inline

Returns a pointer to one before the first element.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 126 of file ArrayBuffer.h.

template<class E, class INDEX = int>

const E* ogdf::ArrayBuffer< E, INDEX >::rend ( ) const

inline

Returns a pointer to one before the first element.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 129 of file ArrayBuffer.h.

template<class E, class INDEX = int>

INDEX ogdf::ArrayBuffer< E, INDEX >::size ( ) const

inline

Returns number of elements in the buffer.

Reimplemented from ogdf::Array< E, INDEX >.

Definition at line 105 of file ArrayBuffer.h.

template<class E, class INDEX = int>

const E& ogdf::ArrayBuffer< E, INDEX >::top ( ) const

inline

Returns the newest element of the buffer.

Definition at line 85 of file ArrayBuffer.h.

template<class E, class INDEX = int>

E& ogdf::ArrayBuffer< E, INDEX >::top ( )

inline

Returns the newest element of the buffer.

Definition at line 87 of file ArrayBuffer.h.

Member Data Documentation

template<class E, class INDEX = int>

INDEX ogdf::ArrayBuffer< E, INDEX >::num

private

The number of elements in te buffer.

Definition at line 69 of file ArrayBuffer.h.

The documentation for this class was generated from the following file:

ogdf/basic/ArrayBuffer.h

OpenGraph DrawingFramework

Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

template<class E, class INDEX = int> class ogdf::ArrayBuffer< E, INDEX >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Open
Graph Drawing
Framework

template<class E, class INDEX = int>
class ogdf::ArrayBuffer< E, INDEX >