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 Types
using	const_iterator = typename Array< E, INDEX >::const_iterator

using	const_reverse_iterator = typename Array< E, INDEX >::const_reverse_iterator

using	iterator = typename Array< E, INDEX >::iterator

using	key_type = INDEX

using	reverse_iterator = typename Array< E, INDEX >::reverse_iterator

using	value_type = E

Public Member Functions
	ArrayBuffer ()
	Creates an empty array buffer, without initial memory allocation.

	ArrayBuffer (ArrayBuffer< E, INDEX > &&buffer)
	Creates an array buffer containing the elements of `buffer` (move semantics).

	ArrayBuffer (const Array< E, INDEX > &source, bool autogrow=true)
	Creates an array buffer, initialized by the given array; you may specify that the array should not grow.

	ArrayBuffer (const ArrayBuffer< E, INDEX > &buffer)
	Creates an array buffer that is a copy of `buffer`.

	ArrayBuffer (INDEX size, bool autogrow=true)
	Creates an empty array buffer, allocating memory for up to `size` elements; you may specify that the array should not grow automatically.

void	clear ()
	Clears the buffer.

bool	isGrowable () const
	Returns whether the buffer will automatically expand if the initial size is insufficient.

void	leftShift (ArrayBuffer< INDEX, INDEX > &ind)
	Removes the components listed in the buffer `ind` by shifting the remaining components to the left.

void	setCapacity (INDEX newCapacity)
	Changes the capacity of the buffer (independent whether the buffer is growable of not).

void	setGrowable (bool _growable)
	Sets the flag whether the buffer will automatically expand if the initial size is insufficient.

Iterators
These methods return random-access iterators to elements in the array.
iterator	begin ()
	Returns an iterator to the first element.

const_iterator	begin () const
	Returns a const iterator to the first element.

iterator	end ()
	Returns an iterator to one past the last element.

const_iterator	end () const
	Returns a const iterator to one past the last element.

reverse_iterator	rbegin ()
	Returns a reverse iterator to the last element.

const_reverse_iterator	rbegin () const
	Returns a const reverse iterator to the last element.

reverse_iterator	rend ()
	Returns a reverse iterator to one before the first element.

const_reverse_iterator	rend () const
	Returns a const reverse iterator to one before the first element.

Access methods
These methods provide access to elements, size, and index range.
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`.

const E &	top () const
	Returns the newest element of the buffer.

E &	top ()
	Returns the newest element of the buffer.

void	push (E e)
	Puts a new element in the buffer.

void	pop ()
	Removes the newest element from the buffer.

E	popRet ()
	Removes the newest element from the buffer and returns it.

bool	empty () const
	Returns true if the buffer is empty, false otherwise.

bool	full () const
	Returns true iff the buffer is non-growable and filled.

INDEX	size () const
	Returns number of elements in the buffer.

INDEX	capacity () const
	Returns the current capacity of the datastructure. Note that this value is rather irrelevant if the array is growable.

Initialization and assignment
These methods can be used to reinitialize or resize the array, or to initialize all elements with a given value.
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.

ArrayBuffer< E, INDEX > &	operator= (const ArrayBuffer< E, INDEX > &buffer)
	Assignment operator.

ArrayBuffer< E, INDEX > &	operator= (ArrayBuffer< E, INDEX > &&buffer)
	Assignment operator (move semantics).

void	compactCpycon (Array< E, INDEX > &A2) const
	Generates a compact copy holding the current elements.

template<typename EE = E, typename std::enable_if<!OGDF_TRIVIALLY_COPYABLE< EE >::value, int >::type = 0>
void	compactCopy (Array< E, INDEX > &A2) const
	Generates a compact copy holding the current elements.

template<typename EE = E, typename std::enable_if< OGDF_TRIVIALLY_COPYABLE< EE >::value, int >::type = 0>
void	compactCopy (Array< E, INDEX > &A2) const
	Generates a compact copy holding the current elements.

Comparison
bool	operator== (const ArrayBuffer< E, INDEX > &L) const
	Equality operator.

bool	operator!= (const ArrayBuffer< E, INDEX > &L) const
	Inequality operator.

Searching and sorting
These methods provide searching for values and sorting the array.
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`.

void	quicksort ()
	Sorts buffer using Quicksort.

template<class COMPARER >
void	quicksort (const COMPARER &comp)
	Sorts buffer using Quicksort and a user-defined comparer `comp`.

INDEX	binarySearch (const E &e) const
	Performs a binary search for element `e`.

template<class COMPARER >
INDEX	binarySearch (const E &e, const COMPARER &comp) const
	Performs a binary search for element `e` with comparer `comp`.

Reordering
template<class RNG >
void	permute (INDEX l, INDEX r, RNG &rng)
	Randomly permutes the subarray with index set [`l`..`r`] using random number generator `rng`.

template<class RNG >
void	permute (RNG &rng)
	Randomly permutes the array using random number generator `rng`.

void	permute (INDEX l, INDEX r)
	Randomly permutes the subarray with index set [`l`..`r`].

void	permute ()
	Randomly permutes the array.

Private Attributes
bool	growable

INDEX	num
	The number of elements in the buffer.

Additional Inherited Members
Private Types inherited from ogdf::Array< E, INDEX >
using	const_iterator = ArrayConstIterator< E >
	Provides a random-access iterator that can read a const element in an array.

using	const_reference = const E &
	Provides a reference to a const element stored in an array for reading and performing const operations.

using	const_reverse_iterator = ArrayConstReverseIterator< E >
	Provides a reverse random-access iterator that can read a const element in an array.

using	iterator = ArrayIterator< E >
	Provides a random-access iterator that can read or modify any element in an array.

using	reference = E &
	Provides a reference to an element stored in an array.

using	reverse_iterator = ArrayReverseIterator< E >
	Provides a reverse random-access iterator that can read or modify any element in an array.

using	value_type = E
	Represents the data type stored in an array element.

Private Member Functions inherited from ogdf::Array< E, INDEX >
	Array ()
	Creates an array with empty index set.

	Array (Array< E, INDEX > &&A)
	Creates an array containing the elements of `A` (move semantics).

	Array (const Array< E, INDEX > &A)
	Creates an array that is a copy of `A`.

	Array (const ArrayBuffer< E, INDEX > &A)
	Creates an array that is a copy of `A`. The array-size is set to be the number of elements (not the capacity) of the buffer.

	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 (INDEX s)
	Creates an array with index set [0..`s-1`].

	Array (std::initializer_list< E > initList)
	Creates an array containing the elements in the initializer list `initList`.

	~Array ()
	Destruction.

INDEX	low () const
	Returns the minimal array index.

INDEX	high () const
	Returns the maximal array index.

INDEX	size () const
	Returns the size (number of elements) of the array.

bool	empty () const
	Returns `true` iff there are no elements in the array.

const_reference	operator[] (INDEX i) const
	Returns a reference to the element at position `i`.

reference	operator[] (INDEX i)
	Returns a reference to the element at position `i`.

iterator	begin ()
	Returns an iterator to the first element.

const_iterator	begin () const
	Returns a const iterator to the first element.

const_iterator	cbegin () const
	Returns a const iterator to the first element.

iterator	end ()
	Returns an iterator to one past the last element.

const_iterator	end () const
	Returns a const iterator to one past the last element.

const_iterator	cend () const
	Returns a const iterator to one past the last element.

reverse_iterator	rbegin ()
	Returns an reverse iterator to the last element.

const_reverse_iterator	rbegin () const
	Returns a const reverse iterator to the last element.

const_reverse_iterator	crbegin () const
	Returns a const reverse iterator to the last element.

reverse_iterator	rend ()
	Returns an reverse iterator to one before the first element.

const_reverse_iterator	rend () const
	Returns a const reverse iterator to one before the first element.

const_reverse_iterator	crend () const
	Returns a const reverse iterator to one before the first element.

void	init ()
	Reinitializes the array to an array with empty index set.

void	init (INDEX s)
	Reinitializes the array to an array with index set [0..`s-1`].

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`.

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.

void	resize (INDEX newSize, const E &x)
	Resizes (enlarges or shrinks) the array to hold `newSize` elements and sets new elements to `x`.

void	resize (INDEX newSize)
	Resizes (enlarges or shrinks) the array to hold `newSize` elements.

Array< E, INDEX > &	operator= (const Array< E, INDEX > &A)
	Assignment operator.

Array< E, INDEX > &	operator= (Array< E, INDEX > &&A)
	Assignment operator (move semantics).

bool	operator== (const Array< E, INDEX > &L) const
	Equality operator.

bool	operator!= (const Array< E, INDEX > &L) const
	Inequality operator.

void	swap (INDEX i, INDEX j)
	Swaps the elements at position `i` and `j`.

void	permute (INDEX l, INDEX r)
	Randomly permutes the subarray with index set [`l`..`r`].

void	permute ()
	Randomly permutes the array.

template<class RNG >
void	permute (INDEX l, INDEX r, RNG &rng)
	Randomly permutes the subarray with index set [`l`..`r`] using random number generator `rng`.

template<class RNG >
void	permute (RNG &rng)
	Randomly permutes the array using random number generator `rng`.

int	binarySearch (const E &e) const
	Performs a binary search for element `e`.

int	binarySearch (INDEX l, INDEX r, const E &e) const
	Performs a binary search for element `e` within the array section [`l`, ..., `r`] .

template<class COMPARER >
int	binarySearch (const E &e, const COMPARER &comp) const
	Performs a binary search for element `e` with comparer `comp`.

template<class COMPARER >
INDEX	binarySearch (INDEX l, INDEX r, const E &e, const COMPARER &comp) const
	Performs a binary search for element `e` within the array section [`l`, ..., `r`] with comparer `comp`.

INDEX	linearSearch (const E &e) const
	Performs a linear search for element `e`.

template<class COMPARER >
INDEX	linearSearch (const E &e, const COMPARER &comp) const
	Performs a linear search for element `e` with comparer `comp`.

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	leftShift (ArrayBuffer< INDEX, INDEX > &ind)
	Removes the components listed in `ind` by shifting the remaining components to the left.

void	leftShift (ArrayBuffer< INDEX, INDEX > &ind, const E &val)
	Removes the components listed in `ind` by shifting the remaining components to the left.

Static Private Attributes inherited from ogdf::Array< E, INDEX >
static const int	maxSizeInsertionSort = 40
	Threshold used by quicksort() such that insertion sort is called for instances smaller than maxSizeInsertionSort.

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 (by default automatically 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 (unless growing is forbidden), but never automatically shrunken. You may also access the elements it contains using the []-operator. The 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 56 of file ArrayBuffer.h.

Member Typedef Documentation

◆ const_iterator

template<class E , class INDEX = int>

using ogdf::ArrayBuffer< E, INDEX >::const_iterator = typename Array<E, INDEX>::const_iterator

Definition at line 63 of file ArrayBuffer.h.

◆ const_reverse_iterator

template<class E , class INDEX = int>

using ogdf::ArrayBuffer< E, INDEX >::const_reverse_iterator = typename Array<E, INDEX>::const_reverse_iterator

Definition at line 65 of file ArrayBuffer.h.

◆ iterator

template<class E , class INDEX = int>

using ogdf::ArrayBuffer< E, INDEX >::iterator = typename Array<E, INDEX>::iterator

Definition at line 64 of file ArrayBuffer.h.

◆ key_type

template<class E , class INDEX = int>

using ogdf::ArrayBuffer< E, INDEX >::key_type = INDEX

Definition at line 61 of file ArrayBuffer.h.

◆ reverse_iterator

template<class E , class INDEX = int>

using ogdf::ArrayBuffer< E, INDEX >::reverse_iterator = typename Array<E, INDEX>::reverse_iterator

Definition at line 66 of file ArrayBuffer.h.

◆ value_type

template<class E , class INDEX = int>

using ogdf::ArrayBuffer< E, INDEX >::value_type = E

Definition at line 62 of file ArrayBuffer.h.

Constructor & Destructor Documentation

◆ ArrayBuffer() [1/5]

template<class E , class INDEX = int>

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

inline

Creates an empty array buffer, without initial memory allocation.

Definition at line 69 of file ArrayBuffer.h.

◆ ArrayBuffer() [2/5]

template<class E , class INDEX = int>

ogdf::ArrayBuffer< E, INDEX >::ArrayBuffer	(	INDEX	size,
		bool	autogrow = `true`
	)

inlineexplicit

Creates an empty array buffer, allocating memory for up to size elements; you may specify that the array should not grow automatically.

Definition at line 73 of file ArrayBuffer.h.

◆ ArrayBuffer() [3/5]

template<class E , class INDEX = int>

ogdf::ArrayBuffer< E, INDEX >::ArrayBuffer	(	const Array< E, INDEX > &	source,
		bool	autogrow = `true`
	)

inlineexplicit

Creates an array buffer, initialized by the given array; you may specify that the array should not grow.

Definition at line 77 of file ArrayBuffer.h.

◆ ArrayBuffer() [4/5]

template<class E , class INDEX = int>

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

inline

Creates an array buffer that is a copy of buffer.

Definition at line 81 of file ArrayBuffer.h.

◆ ArrayBuffer() [5/5]

template<class E , class INDEX = int>

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

inline

Creates an array buffer containing the elements of buffer (move semantics).

The array buffer buffer is empty (and growable) afterwards.

Definition at line 88 of file ArrayBuffer.h.

Member Function Documentation

◆ begin() [1/2]

template<class E , class INDEX = int>

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

inline

Returns an iterator to the first element.

Definition at line 151 of file ArrayBuffer.h.

◆ begin() [2/2]

template<class E , class INDEX = int>

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

inline

Returns a const iterator to the first element.

Definition at line 154 of file ArrayBuffer.h.

◆ binarySearch() [1/2]

template<class E , class INDEX = int>

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

inline

Performs a binary search for element e.

Precondition: The buffer must be sorted!

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

Definition at line 439 of file ArrayBuffer.h.

◆ binarySearch() [2/2]

template<class E , class INDEX = int>

template<class COMPARER >

INDEX ogdf::ArrayBuffer< E, INDEX >::binarySearch	(	const E &	e,
		const COMPARER &	comp
	)		const

inline

Performs a binary search for element e with comparer comp.

Precondition: The buffer must be sorted according to comp!

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

Definition at line 449 of file ArrayBuffer.h.

◆ capacity()

template<class E , class INDEX = int>

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

inline

Returns the current capacity of the datastructure. Note that this value is rather irrelevant if the array is growable.

Definition at line 239 of file ArrayBuffer.h.

◆ clear()

template<class E , class INDEX = int>

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

inline

Clears the buffer.

Definition at line 95 of file ArrayBuffer.h.

◆ compactCopy() [1/2]

template<class E , class INDEX = int>

template<typename EE = E, typename std::enable_if<!OGDF_TRIVIALLY_COPYABLE< EE >::value, int >::type = 0>

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 A2. A2 has exactly the neccessary size to hold all elements in the buffer.

This method uses an elementwise operator=. If you need a traditional array copy (using the Array's copy-constructor), use compactCpycon() instead.

Definition at line 311 of file ArrayBuffer.h.

◆ compactCopy() [2/2]

template<class E , class INDEX = int>

template<typename EE = E, typename std::enable_if< OGDF_TRIVIALLY_COPYABLE< EE >::value, int >::type = 0>

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 A2. A2 has exactly the neccessary size to hold all elements in the buffer.

This method uses memcpy. If you need a traditional array copy (using the Array's copy-constructor), use compactCpycon() instead.

Definition at line 335 of file ArrayBuffer.h.

◆ compactCpycon()

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 A2. A2 has exactly the neccessary size to hold all elements in the buffer

This method uses the Array's copy constructor. If you need an elementwise operator=-copy or a bitcopy, use compactCopy() instead.

Definition at line 287 of file ArrayBuffer.h.

◆ empty()

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 230 of file ArrayBuffer.h.

◆ end() [1/2]

template<class E , class INDEX = int>

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

inline

Returns an iterator to one past the last element.

Definition at line 157 of file ArrayBuffer.h.

◆ end() [2/2]

template<class E , class INDEX = int>

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

inline

Returns a const iterator to one past the last element.

Definition at line 160 of file ArrayBuffer.h.

◆ full()

template<class E , class INDEX = int>

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

inline

Returns true iff the buffer is non-growable and filled.

Definition at line 233 of file ArrayBuffer.h.

◆ init() [1/2]

template<class E , class INDEX = int>

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

inline

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

Definition at line 250 of file ArrayBuffer.h.

◆ init() [2/2]

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.

Definition at line 253 of file ArrayBuffer.h.

◆ isGrowable()

template<class E , class INDEX = int>

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

inline

Returns whether the buffer will automatically expand if the initial size is insufficient.

Definition at line 139 of file ArrayBuffer.h.

◆ leftShift()

template<class E , class INDEX = int>

void ogdf::ArrayBuffer< E, INDEX >::leftShift ( ArrayBuffer< INDEX, INDEX > & ind )

inline

Removes the components listed in the buffer ind by shifting the remaining components to the left.

The values stored in ind have to be upward sorted. Memory management of the removed components must be carefully implemented by the user of this function to avoid memory leaks.

If this function is compiled with OGDF_DEBUG then it is checked if each value of ind is in the range 0,..., size() -1.

Parameters

ind	The numbers of the components being removed.

copy the rest of the buffer

Definition at line 110 of file ArrayBuffer.h.

◆ linearSearch() [1/2]

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 -1 if not found.

Definition at line 387 of file ArrayBuffer.h.

◆ linearSearch() [2/2]

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 -1 if not found.

Definition at line 404 of file ArrayBuffer.h.

◆ operator!=()

template<class E , class INDEX = int>

bool ogdf::ArrayBuffer< E, INDEX >::operator!= ( const ArrayBuffer< E, INDEX > & L ) const

inline

Inequality operator.

Definition at line 371 of file ArrayBuffer.h.

◆ operator=() [1/2]

template<class E , class INDEX = int>

ArrayBuffer< E, INDEX > & ogdf::ArrayBuffer< E, INDEX >::operator= ( ArrayBuffer< E, INDEX > && buffer )

inline

Assignment operator (move semantics).

The array buffer buffer is empty (and growable) afterwards.

Definition at line 267 of file ArrayBuffer.h.

◆ operator=() [2/2]

template<class E , class INDEX = int>

ArrayBuffer< E, INDEX > & ogdf::ArrayBuffer< E, INDEX >::operator= ( const ArrayBuffer< E, INDEX > & buffer )

inline

Assignment operator.

Definition at line 256 of file ArrayBuffer.h.

◆ operator==()

template<class E , class INDEX = int>

bool ogdf::ArrayBuffer< E, INDEX >::operator== ( const ArrayBuffer< E, INDEX > & L ) const

inline

Equality operator.

Definition at line 350 of file ArrayBuffer.h.

◆ operator[]() [1/2]

template<class E , class INDEX = int>

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

inline

Returns a reference to the element at position i.

Definition at line 190 of file ArrayBuffer.h.

◆ operator[]() [2/2]

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.

Definition at line 183 of file ArrayBuffer.h.

◆ permute() [1/4]

template<class E , class INDEX = int>

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

inline

Randomly permutes the array.

Definition at line 479 of file ArrayBuffer.h.

◆ permute() [2/4]

template<class E , class INDEX = int>

void ogdf::ArrayBuffer< E, INDEX >::permute	(	INDEX	l,
		INDEX	r
	)

inline

Randomly permutes the subarray with index set [l..r].

Definition at line 473 of file ArrayBuffer.h.

◆ permute() [3/4]

template<class E , class INDEX = int>

template<class RNG >

void ogdf::ArrayBuffer< E, INDEX >::permute	(	INDEX	l,
		INDEX	r,
		RNG &	rng
	)

inline

Randomly permutes the subarray with index set [l..r] using random number generator rng.

Parameters

l	left border
r	right border
rng	random number generator

Definition at line 462 of file ArrayBuffer.h.

◆ permute() [4/4]

template<class E , class INDEX = int>

template<class RNG >

void ogdf::ArrayBuffer< E, INDEX >::permute ( RNG & rng )

inline

Randomly permutes the array using random number generator rng.

Parameters

rng	random number generator

Definition at line 468 of file ArrayBuffer.h.

◆ pop()

template<class E , class INDEX = int>

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

inline

Removes the newest element from the buffer.

Definition at line 218 of file ArrayBuffer.h.

◆ popRet()

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 224 of file ArrayBuffer.h.

◆ push()

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 209 of file ArrayBuffer.h.

◆ quicksort() [1/2]

template<class E , class INDEX = int>

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

inline

Sorts buffer using Quicksort.

Definition at line 415 of file ArrayBuffer.h.

◆ quicksort() [2/2]

template<class E , class INDEX = int>

template<class COMPARER >

void ogdf::ArrayBuffer< E, INDEX >::quicksort ( const COMPARER & comp )

inline

Sorts buffer using Quicksort and a user-defined comparer comp.

Parameters

comp	is a user-defined comparer; it must provide a `less(x,y)` method.

Definition at line 427 of file ArrayBuffer.h.

◆ rbegin() [1/2]

template<class E , class INDEX = int>

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

inline

Returns a reverse iterator to the last element.

Definition at line 163 of file ArrayBuffer.h.

◆ rbegin() [2/2]

template<class E , class INDEX = int>

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

inline

Returns a const reverse iterator to the last element.

Definition at line 166 of file ArrayBuffer.h.

◆ rend() [1/2]

template<class E , class INDEX = int>

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

inline

Returns a reverse iterator to one before the first element.

Definition at line 169 of file ArrayBuffer.h.

◆ rend() [2/2]

template<class E , class INDEX = int>

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

inline

Returns a const reverse iterator to one before the first element.

Definition at line 172 of file ArrayBuffer.h.

◆ setCapacity()

template<class E , class INDEX = int>

void ogdf::ArrayBuffer< E, INDEX >::setCapacity ( INDEX newCapacity )

inline

Changes the capacity of the buffer (independent whether the buffer is growable of not).

If the new capacity if smaller that the currently stored elements, only the first elements (as many as fit) are retained in the buffer. The user is responsible that no memory leaks occur.

Definition at line 488 of file ArrayBuffer.h.

◆ setGrowable()

template<class E , class INDEX = int>

void ogdf::ArrayBuffer< E, INDEX >::setGrowable ( bool _growable )

inline

Sets the flag whether the buffer will automatically expand if the initial size is insufficient.

Definition at line 142 of file ArrayBuffer.h.

◆ size()

template<class E , class INDEX = int>

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

inline

Returns number of elements in the buffer.

Definition at line 236 of file ArrayBuffer.h.

◆ top() [1/2]

template<class E , class INDEX = int>

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

inline

Returns the newest element of the buffer.

Definition at line 203 of file ArrayBuffer.h.

◆ top() [2/2]

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 197 of file ArrayBuffer.h.

Member Data Documentation

◆ growable

template<class E , class INDEX = int>

bool ogdf::ArrayBuffer< E, INDEX >::growable

private

Definition at line 58 of file ArrayBuffer.h.

◆ num

template<class E , class INDEX = int>

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

private

The number of elements in the buffer.

Definition at line 57 of file ArrayBuffer.h.

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

include/ogdf/basic/Array.h
include/ogdf/basic/ArrayBuffer.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_reverse_iterator

◆ iterator

◆ key_type

◆ reverse_iterator

◆ value_type

Constructor & Destructor Documentation

◆ ArrayBuffer() [1/5]

◆ ArrayBuffer() [2/5]

◆ ArrayBuffer() [3/5]

◆ ArrayBuffer() [4/5]

◆ ArrayBuffer() [5/5]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ binarySearch() [1/2]

◆ binarySearch() [2/2]

◆ capacity()

◆ clear()

◆ compactCopy() [1/2]

◆ compactCopy() [2/2]

◆ compactCpycon()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ full()

◆ init() [1/2]

◆ init() [2/2]

◆ isGrowable()

◆ leftShift()

◆ linearSearch() [1/2]

◆ linearSearch() [2/2]

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ permute() [1/4]

◆ permute() [2/4]

◆ permute() [3/4]

◆ permute() [4/4]

◆ pop()

◆ popRet()

◆ push()

◆ quicksort() [1/2]

◆ quicksort() [2/2]

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ rend() [1/2]

◆ rend() [2/2]

◆ setCapacity()

◆ setGrowable()

◆ size()

◆ top() [1/2]

◆ top() [2/2]

Member Data Documentation

◆ growable

◆ num

Open
Graph Drawing
Framework