Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::Array< E, INDEX > Class Template Reference

The parameterized class Array implements dynamic arrays of type E. More...

#include <ogdf/basic/Array.h>

Public Types

using const_iterator = ArrayConstIterator< E >
 Provides a random-access iterator that can read a const element in an array. More...
 
using const_reference = const E &
 Provides a reference to a const element stored in an array for reading and performing const operations. More...
 
using const_reverse_iterator = ArrayConstReverseIterator< E >
 Provides a reverse random-access iterator that can read a const element in an array. More...
 
using iterator = ArrayIterator< E >
 Provides a random-access iterator that can read or modify any element in an array. More...
 
using reference = E &
 Provides a reference to an element stored in an array. More...
 
using reverse_iterator = ArrayReverseIterator< E >
 Provides a reverse random-access iterator that can read or modify any element in an array. More...
 
using value_type = E
 Represents the data type stored in an array element. More...
 

Public Member Functions

 Array ()
 Creates an array with empty index set. More...
 
 Array (Array< E, INDEX > &&A)
 Creates an array containing the elements of A (move semantics). More...
 
 Array (const Array< E, INDEX > &A)
 Creates an array that is a copy of A. More...
 
 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. More...
 
 Array (INDEX a, INDEX b)
 Creates an array with index set [a..b]. More...
 
 Array (INDEX a, INDEX b, const E &x)
 Creates an array with index set [a..b] and initializes each element with x. More...
 
 Array (INDEX s)
 Creates an array with index set [0..s-1]. More...
 
 Array (std::initializer_list< E > initList)
 Creates an array containing the elements in the initializer list initList. More...
 
 ~Array ()
 Destruction. More...
 
Access methods

These methods provide access to elements, size, and index range.

INDEX low () const
 Returns the minimal array index. More...
 
INDEX high () const
 Returns the maximal array index. More...
 
INDEX size () const
 Returns the size (number of elements) of the array. More...
 
bool empty () const
 Returns true iff there are no elements in the array. More...
 
const_reference operator[] (INDEX i) const
 Returns a reference to the element at position i. More...
 
reference operator[] (INDEX i)
 Returns a reference to the element at position i. More...
 
Iterators

These methods return random-access iterators to elements in the array.

iterator begin ()
 Returns an iterator to the first element. More...
 
const_iterator begin () const
 Returns a const iterator to the first element. More...
 
const_iterator cbegin () const
 Returns a const iterator to the first element. More...
 
iterator end ()
 Returns an iterator to one past the last element. More...
 
const_iterator end () const
 Returns a const iterator to one past the last element. More...
 
const_iterator cend () const
 Returns a const iterator to one past the last element. More...
 
reverse_iterator rbegin ()
 Returns an reverse iterator to the last element. More...
 
const_reverse_iterator rbegin () const
 Returns a const reverse iterator to the last element. More...
 
const_reverse_iterator crbegin () const
 Returns a const reverse iterator to the last element. More...
 
reverse_iterator rend ()
 Returns an reverse iterator to one before the first element. More...
 
const_reverse_iterator rend () const
 Returns a const reverse iterator to one before the first element. More...
 
const_reverse_iterator crend () const
 Returns a const reverse iterator to one before the first element. More...
 
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 to an array with empty index set. More...
 
void init (INDEX s)
 Reinitializes the array to an array with index set [0..s-1]. More...
 
void init (INDEX a, INDEX b)
 Reinitializes the array to an array with index set [a..b]. More...
 
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. More...
 
void fill (const E &x)
 Sets all elements to x. More...
 
void fill (INDEX i, INDEX j, const E &x)
 Sets elements in the intervall [i..j] to x. More...
 
void grow (INDEX add, const E &x)
 Enlarges the array by add elements and sets new elements to x. More...
 
void grow (INDEX add)
 Enlarges the array by add elements. More...
 
void resize (INDEX newSize, const E &x)
 Resizes (enlarges or shrinks) the array to hold newSize elements and sets new elements to x. More...
 
void resize (INDEX newSize)
 Resizes (enlarges or shrinks) the array to hold newSize elements. More...
 
Array< E, INDEX > & operator= (const Array< E, INDEX > &A)
 Assignment operator. More...
 
Array< E, INDEX > & operator= (Array< E, INDEX > &&A)
 Assignment operator (move semantics). More...
 
Comparison
bool operator== (const Array< E, INDEX > &L) const
 Equality operator. More...
 
bool operator!= (const Array< E, INDEX > &L) const
 Inequality operator. More...
 
Reordering

These following methods change the order of elements in the array.

void swap (INDEX i, INDEX j)
 Swaps the elements at position i and j. More...
 
void permute (INDEX l, INDEX r)
 Randomly permutes the subarray with index set [l..r]. More...
 
void permute ()
 Randomly permutes the array. More...
 
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. More...
 
template<class RNG >
void permute (RNG &rng)
 Randomly permutes the array using random number generator rng. More...
 

Static Public Attributes

static const int maxSizeInsertionSort = 40
 Threshold used by quicksort() such that insertion sort is called for instances smaller than maxSizeInsertionSort. More...
 

Searching and sorting

These methods provide searching for values and sorting the array.

template<class F , class I >
class ArrayBuffer
 
E * m_vpStart
 The virtual start of the array (address of A[0]). More...
 
E * m_pStart
 The real start of the array (address of A[m_low]). More...
 
E * m_pStop
 Successor of last element (address of A[m_high+1]). More...
 
INDEX m_low
 The lowest index. More...
 
INDEX m_high
 The highest index. More...
 
int binarySearch (const E &e) const
 Performs a binary search for element e. More...
 
int binarySearch (INDEX l, INDEX r, const E &e) const
 Performs a binary search for element e within the array section [l, ..., r] . More...
 
template<class COMPARER >
int binarySearch (const E &e, const COMPARER &comp) const
 Performs a binary search for element e with comparer comp. More...
 
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. More...
 
INDEX linearSearch (const E &e) const
 Performs a linear search for element e. More...
 
template<class COMPARER >
INDEX linearSearch (const E &e, const COMPARER &comp) const
 Performs a linear search for element e with comparer comp. More...
 
void quicksort ()
 Sorts array using Quicksort. More...
 
void quicksort (INDEX l, INDEX r)
 Sorts subarray with index set [l, ..., r] using Quicksort. More...
 
template<class COMPARER >
void quicksort (const COMPARER &comp)
 Sorts array using Quicksort and a user-defined comparer comp. More...
 
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. More...
 
void leftShift (ArrayBuffer< INDEX, INDEX > &ind)
 Removes the components listed in ind by shifting the remaining components to the left. More...
 
void leftShift (ArrayBuffer< INDEX, INDEX > &ind, const E &val)
 Removes the components listed in ind by shifting the remaining components to the left. More...
 
void construct (INDEX a, INDEX b)
 Allocates new array with index set [a, ..., b]. More...
 
void initialize ()
 Initializes elements with default constructor. More...
 
void initialize (const E &x)
 Initializes elements with x. More...
 
void initialize (std::initializer_list< E > initList)
 Initializes elements from given initializer list initList. More...
 
void deconstruct ()
 Deallocates array. More...
 
void copy (const Array< E, INDEX > &A)
 Constructs a new array which is a copy of A. More...
 
void expandArray (INDEX add)
 Used by grow() to enlarge the array. More...
 
template<typename EE = E, typename std::enable_if< OGDF_TRIVIALLY_COPYABLE< EE >::value, int >::type = 0>
void expandArrayHelper (INDEX sOld, INDEX sNew)
 Used by expandArray() to reallocate the array elements. More...
 
template<typename EE = E, typename std::enable_if<!OGDF_TRIVIALLY_COPYABLE< EE >::value, int >::type = 0>
void expandArrayHelper (INDEX sOld, INDEX sNew)
 Used by expandArray() to reallocate the array elements. More...
 
template<class COMPARER >
static void quicksortInt (E *pL, E *pR, const COMPARER &comp)
 Internal Quicksort implementation with comparer template. More...
 

Detailed Description

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

The parameterized class Array implements dynamic arrays of type E.

Template Parameters
Edenotes the element type.
INDEXdenotes 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 204 of file Array.h.

Member Typedef Documentation

◆ const_iterator

template<class E , class INDEX = int>
using ogdf::Array< E, INDEX >::const_iterator = ArrayConstIterator<E>

Provides a random-access iterator that can read a const element in an array.

Definition at line 217 of file Array.h.

◆ const_reference

template<class E , class INDEX = int>
using ogdf::Array< E, INDEX >::const_reference = const E&

Provides a reference to a const element stored in an array for reading and performing const operations.

Definition at line 215 of file Array.h.

◆ const_reverse_iterator

template<class E , class INDEX = int>
using ogdf::Array< E, INDEX >::const_reverse_iterator = ArrayConstReverseIterator<E>

Provides a reverse random-access iterator that can read a const element in an array.

Definition at line 221 of file Array.h.

◆ iterator

template<class E , class INDEX = int>
using ogdf::Array< E, INDEX >::iterator = ArrayIterator<E>

Provides a random-access iterator that can read or modify any element in an array.

Definition at line 219 of file Array.h.

◆ reference

template<class E , class INDEX = int>
using ogdf::Array< E, INDEX >::reference = E&

Provides a reference to an element stored in an array.

Definition at line 213 of file Array.h.

◆ reverse_iterator

template<class E , class INDEX = int>
using ogdf::Array< E, INDEX >::reverse_iterator = ArrayReverseIterator<E>

Provides a reverse random-access iterator that can read or modify any element in an array.

Definition at line 223 of file Array.h.

◆ value_type

template<class E , class INDEX = int>
using ogdf::Array< E, INDEX >::value_type = E

Represents the data type stored in an array element.

Definition at line 211 of file Array.h.

Constructor & Destructor Documentation

◆ Array() [1/8]

template<class E , class INDEX = int>
ogdf::Array< E, INDEX >::Array ( )
inline

Creates an array with empty index set.

Definition at line 226 of file Array.h.

◆ Array() [2/8]

template<class E , class INDEX = int>
ogdf::Array< E, INDEX >::Array ( INDEX  s)
inlineexplicit

Creates an array with index set [0..s-1].

Definition at line 229 of file Array.h.

◆ Array() [3/8]

template<class E , class INDEX = int>
ogdf::Array< E, INDEX >::Array ( INDEX  a,
INDEX  b 
)
inline

Creates an array with index set [a..b].

Definition at line 232 of file Array.h.

◆ Array() [4/8]

template<class E , class INDEX = int>
ogdf::Array< E, INDEX >::Array ( INDEX  a,
INDEX  b,
const E &  x 
)
inline

Creates an array with index set [a..b] and initializes each element with x.

Definition at line 237 of file Array.h.

◆ Array() [5/8]

template<class E , class INDEX = int>
ogdf::Array< E, INDEX >::Array ( std::initializer_list< E >  initList)
inline

Creates an array containing the elements in the initializer list initList.

The index set of the array is set to 0, ..., number of elements in initList - 1.

Definition at line 245 of file Array.h.

◆ Array() [6/8]

template<class E , class INDEX = int>
ogdf::Array< E, INDEX >::Array ( const Array< E, INDEX > &  A)
inline

Creates an array that is a copy of A.

Definition at line 251 of file Array.h.

◆ Array() [7/8]

template<class E , class INDEX = int>
ogdf::Array< E, INDEX >::Array ( Array< E, INDEX > &&  A)
inline

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

The array A is empty afterwards.

Definition at line 259 of file Array.h.

◆ Array() [8/8]

template<class E , class INDEX >
ogdf::Array< E, INDEX >::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.

Definition at line 986 of file Array.h.

◆ ~Array()

template<class E , class INDEX = int>
ogdf::Array< E, INDEX >::~Array ( )
inline

Destruction.

Definition at line 269 of file Array.h.

Member Function Documentation

◆ begin() [1/2]

template<class E , class INDEX = int>
iterator ogdf::Array< E, INDEX >::begin ( )
inline

Returns an iterator to the first element.

Definition at line 314 of file Array.h.

◆ begin() [2/2]

template<class E , class INDEX = int>
const_iterator ogdf::Array< E, INDEX >::begin ( ) const
inline

Returns a const iterator to the first element.

Definition at line 317 of file Array.h.

◆ binarySearch() [1/4]

template<class E , class INDEX = int>
int ogdf::Array< E, INDEX >::binarySearch ( const E &  e) const
inline

Performs a binary search for element e.

Precondition
The array must be sorted!
Returns
the index of the found element, and low()-1 if not found.

Definition at line 550 of file Array.h.

◆ binarySearch() [2/4]

template<class E , class INDEX = int>
template<class COMPARER >
int ogdf::Array< E, INDEX >::binarySearch ( const E &  e,
const COMPARER &  comp 
) const
inline

Performs a binary search for element e with comparer comp.

Precondition
The array must be sorted according to comp!
Returns
the index of the found element, and low()-1 if not found.

Definition at line 569 of file Array.h.

◆ binarySearch() [3/4]

template<class E , class INDEX = int>
int ogdf::Array< E, INDEX >::binarySearch ( INDEX  l,
INDEX  r,
const E &  e 
) const
inline

Performs a binary search for element e within the array section [l, ..., r] .

Precondition
The array must be sorted!
Returns
the index of the found element, and low()-1 if not found.

Definition at line 559 of file Array.h.

◆ binarySearch() [4/4]

template<class E , class INDEX = int>
template<class COMPARER >
INDEX ogdf::Array< E, INDEX >::binarySearch ( INDEX  l,
INDEX  r,
const E &  e,
const COMPARER &  comp 
) const
inline

Performs a binary search for element e within the array section [l, ..., r] with comparer comp.

Precondition
The array must be sorted according to comp!
Returns
the index of the found element, and low()-1 if not found.

Definition at line 579 of file Array.h.

◆ cbegin()

template<class E , class INDEX = int>
const_iterator ogdf::Array< E, INDEX >::cbegin ( ) const
inline

Returns a const iterator to the first element.

Definition at line 320 of file Array.h.

◆ cend()

template<class E , class INDEX = int>
const_iterator ogdf::Array< E, INDEX >::cend ( ) const
inline

Returns a const iterator to one past the last element.

Definition at line 329 of file Array.h.

◆ construct()

template<class E , class INDEX >
void ogdf::Array< E, INDEX >::construct ( INDEX  a,
INDEX  b 
)
private

Allocates new array with index set [a, ..., b].

Definition at line 823 of file Array.h.

◆ copy()

template<class E , class INDEX >
void ogdf::Array< E, INDEX >::copy ( const Array< E, INDEX > &  A)
private

Constructs a new array which is a copy of A.

Definition at line 902 of file Array.h.

◆ crbegin()

template<class E , class INDEX = int>
const_reverse_iterator ogdf::Array< E, INDEX >::crbegin ( ) const
inline

Returns a const reverse iterator to the last element.

Definition at line 338 of file Array.h.

◆ crend()

template<class E , class INDEX = int>
const_reverse_iterator ogdf::Array< E, INDEX >::crend ( ) const
inline

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

Definition at line 347 of file Array.h.

◆ deconstruct()

template<class E , class INDEX >
void ogdf::Array< E, INDEX >::deconstruct
private

Deallocates array.

Definition at line 891 of file Array.h.

◆ empty()

template<class E , class INDEX = int>
bool ogdf::Array< E, INDEX >::empty ( ) const
inline

Returns true iff there are no elements in the array.

Definition at line 289 of file Array.h.

◆ end() [1/2]

template<class E , class INDEX = int>
iterator ogdf::Array< E, INDEX >::end ( )
inline

Returns an iterator to one past the last element.

Definition at line 323 of file Array.h.

◆ end() [2/2]

template<class E , class INDEX = int>
const_iterator ogdf::Array< E, INDEX >::end ( ) const
inline

Returns a const iterator to one past the last element.

Definition at line 326 of file Array.h.

◆ expandArray()

template<class E , class INDEX >
void ogdf::Array< E, INDEX >::expandArray ( INDEX  add)
private

Used by grow() to enlarge the array.

Definition at line 777 of file Array.h.

◆ expandArrayHelper() [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::Array< E, INDEX >::expandArrayHelper ( INDEX  sOld,
INDEX  sNew 
)
inlineprivate

Used by expandArray() to reallocate the array elements.

Definition at line 717 of file Array.h.

◆ expandArrayHelper() [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::Array< E, INDEX >::expandArrayHelper ( INDEX  sOld,
INDEX  sNew 
)
inlineprivate

Used by expandArray() to reallocate the array elements.

Definition at line 727 of file Array.h.

◆ fill() [1/2]

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::fill ( const E &  x)
inline

Sets all elements to x.

Definition at line 387 of file Array.h.

◆ fill() [2/2]

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::fill ( INDEX  i,
INDEX  j,
const E &  x 
)
inline

Sets elements in the intervall [i..j] to x.

Definition at line 394 of file Array.h.

◆ grow() [1/2]

template<class E , class INDEX >
void ogdf::Array< E, INDEX >::grow ( INDEX  add)

Enlarges the array by add elements.

Note: address of array entries in memory may change!

Parameters
addis the number of additional elements; add can be negative in order to shrink the array.

Definition at line 810 of file Array.h.

◆ grow() [2/2]

template<class E , class INDEX >
void ogdf::Array< E, INDEX >::grow ( INDEX  add,
const E &  x 
)

Enlarges the array by add elements and sets new elements to x.

Note: address of array entries in memory may change!

Parameters
addis the number of additional elements; add can be negative in order to shrink the array.
xis the inital value of all new elements.

Definition at line 796 of file Array.h.

◆ high()

template<class E , class INDEX = int>
INDEX ogdf::Array< E, INDEX >::high ( ) const
inline

Returns the maximal array index.

Definition at line 283 of file Array.h.

◆ init() [1/4]

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::init ( )
inline

Reinitializes the array to an array with empty index set.

Definition at line 358 of file Array.h.

◆ init() [2/4]

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::init ( INDEX  a,
INDEX  b 
)
inline

Reinitializes the array to an array with index set [a..b].

Notice that the elements contained in the array get discarded!

Definition at line 373 of file Array.h.

◆ init() [3/4]

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::init ( INDEX  a,
INDEX  b,
const E &  x 
)
inline

Reinitializes the array to an array with index set [a..b] and sets all entries to x.

Definition at line 380 of file Array.h.

◆ init() [4/4]

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::init ( INDEX  s)
inline

Reinitializes the array to an array with index set [0..s-1].

Notice that the elements contained in the array get discarded!

Definition at line 367 of file Array.h.

◆ initialize() [1/3]

template<class E , class INDEX >
void ogdf::Array< E, INDEX >::initialize
private

Initializes elements with default constructor.

Definition at line 842 of file Array.h.

◆ initialize() [2/3]

template<class E , class INDEX >
void ogdf::Array< E, INDEX >::initialize ( const E &  x)
private

Initializes elements with x.

Definition at line 858 of file Array.h.

◆ initialize() [3/3]

template<class E , class INDEX >
void ogdf::Array< E, INDEX >::initialize ( std::initializer_list< E >  initList)
private

Initializes elements from given initializer list initList.

Definition at line 874 of file Array.h.

◆ leftShift() [1/2]

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

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

shift all items up to the last element of ind to the left

The "free" positions in the array at the end remain as they are.

This function is mainly used by Abacus. Other uses are supposed to be rare.

Memory management of the removed components must be carefully implemented by the user of this function to avoid memory leaks.

Parameters
indThe compenents being removed from the array.

copy the rest of the buffer

Definition at line 963 of file Array.h.

◆ leftShift() [2/2]

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::leftShift ( ArrayBuffer< INDEX, INDEX > &  ind,
const E &  val 
)
inline

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

The "free" positions in the array at the end are filled with val.

Memory management of the removed components must be carefully implemented by the user of this function to avoid memory leaks.

Parameters
indspecifies the components that are removed from the array.
valis the value used to fill the positions that become free.

Definition at line 677 of file Array.h.

◆ linearSearch() [1/2]

template<class E , class INDEX = int>
INDEX ogdf::Array< E, INDEX >::linearSearch ( const E &  e) const
inline

Performs a linear search for element e.

Warning: This method has 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.

Definition at line 596 of file Array.h.

◆ linearSearch() [2/2]

template<class E , class INDEX = int>
template<class COMPARER >
INDEX ogdf::Array< E, INDEX >::linearSearch ( const E &  e,
const COMPARER &  comp 
) const
inline

Performs a linear search for element e with comparer comp.

Warning: This method has 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.

Definition at line 609 of file Array.h.

◆ low()

template<class E , class INDEX = int>
INDEX ogdf::Array< E, INDEX >::low ( ) const
inline

Returns the minimal array index.

Definition at line 280 of file Array.h.

◆ operator!=()

template<class E , class INDEX = int>
bool ogdf::Array< E, INDEX >::operator!= ( const Array< E, INDEX > &  L) const
inline

Inequality operator.

Definition at line 485 of file Array.h.

◆ operator=() [1/2]

template<class E , class INDEX = int>
Array<E,INDEX>& ogdf::Array< E, INDEX >::operator= ( Array< E, INDEX > &&  A)
inline

Assignment operator (move semantics).

Array A is empty afterwards.

Definition at line 446 of file Array.h.

◆ operator=() [2/2]

template<class E , class INDEX = int>
Array<E,INDEX>& ogdf::Array< E, INDEX >::operator= ( const Array< E, INDEX > &  A)
inline

Assignment operator.

Definition at line 436 of file Array.h.

◆ operator==()

template<class E , class INDEX = int>
bool ogdf::Array< E, INDEX >::operator== ( const Array< E, INDEX > &  L) const
inline

Equality operator.

Definition at line 464 of file Array.h.

◆ operator[]() [1/2]

template<class E , class INDEX = int>
reference ogdf::Array< E, INDEX >::operator[] ( INDEX  i)
inline

Returns a reference to the element at position i.

Definition at line 299 of file Array.h.

◆ operator[]() [2/2]

template<class E , class INDEX = int>
const_reference ogdf::Array< E, INDEX >::operator[] ( INDEX  i) const
inline

Returns a reference to the element at position i.

Definition at line 292 of file Array.h.

◆ permute() [1/4]

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::permute ( )
inline

Randomly permutes the array.

Definition at line 513 of file Array.h.

◆ permute() [2/4]

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::permute ( INDEX  l,
INDEX  r 
)
inline

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

Definition at line 507 of file Array.h.

◆ permute() [3/4]

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

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

Parameters
lleft border
rright border
rngrandom number generator

Definition at line 921 of file Array.h.

◆ permute() [4/4]

template<class E , class INDEX = int>
template<class RNG >
void ogdf::Array< E, INDEX >::permute ( RNG &  rng)
inline

Randomly permutes the array using random number generator rng.

Parameters
rngrandom number generator

Definition at line 531 of file Array.h.

◆ quicksort() [1/4]

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::quicksort ( )
inline

Sorts array using Quicksort.

Definition at line 617 of file Array.h.

◆ quicksort() [2/4]

template<class E , class INDEX = int>
template<class COMPARER >
void ogdf::Array< E, INDEX >::quicksort ( const COMPARER &  comp)
inline

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

Parameters
compis a user-defined comparer; it must be a class providing a less(x,y) method.

Definition at line 631 of file Array.h.

◆ quicksort() [3/4]

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::quicksort ( INDEX  l,
INDEX  r 
)
inline

Sorts subarray with index set [l, ..., r] using Quicksort.

Definition at line 622 of file Array.h.

◆ quicksort() [4/4]

template<class E , class INDEX = int>
template<class COMPARER >
void ogdf::Array< E, INDEX >::quicksort ( INDEX  l,
INDEX  r,
const COMPARER &  comp 
)
inline

Sorts the subarray with index set [l, ..., r] using Quicksort and a user-defined comparer comp.

Parameters
lis the left-most position in the range to be sorted.
ris the right-most position in the range to be sorted.
compis a user-defined comparer; it must be a class providing a less(x,y) method.

Definition at line 643 of file Array.h.

◆ quicksortInt()

template<class E , class INDEX = int>
template<class COMPARER >
static void ogdf::Array< E, INDEX >::quicksortInt ( E *  pL,
E *  pR,
const COMPARER &  comp 
)
inlinestaticprivate

Internal Quicksort implementation with comparer template.

Definition at line 743 of file Array.h.

◆ rbegin() [1/2]

template<class E , class INDEX = int>
reverse_iterator ogdf::Array< E, INDEX >::rbegin ( )
inline

Returns an reverse iterator to the last element.

Definition at line 332 of file Array.h.

◆ rbegin() [2/2]

template<class E , class INDEX = int>
const_reverse_iterator ogdf::Array< E, INDEX >::rbegin ( ) const
inline

Returns a const reverse iterator to the last element.

Definition at line 335 of file Array.h.

◆ rend() [1/2]

template<class E , class INDEX = int>
reverse_iterator ogdf::Array< E, INDEX >::rend ( )
inline

Returns an reverse iterator to one before the first element.

Definition at line 341 of file Array.h.

◆ rend() [2/2]

template<class E , class INDEX = int>
const_reverse_iterator ogdf::Array< E, INDEX >::rend ( ) const
inline

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

Definition at line 344 of file Array.h.

◆ resize() [1/2]

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::resize ( INDEX  newSize)
inline

Resizes (enlarges or shrinks) the array to hold newSize elements.

Note: address of array entries in memory may change!

Parameters
newSizeis new size of the array

Definition at line 433 of file Array.h.

◆ resize() [2/2]

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::resize ( INDEX  newSize,
const E &  x 
)
inline

Resizes (enlarges or shrinks) the array to hold newSize elements and sets new elements to x.

Note: address of array entries in memory may change!

Parameters
newSizeis new size of the array
xis the inital value of all new elements.

Definition at line 426 of file Array.h.

◆ size()

template<class E , class INDEX = int>
INDEX ogdf::Array< E, INDEX >::size ( ) const
inline

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

Definition at line 286 of file Array.h.

◆ swap()

template<class E , class INDEX = int>
void ogdf::Array< E, INDEX >::swap ( INDEX  i,
INDEX  j 
)
inline

Swaps the elements at position i and j.

Definition at line 497 of file Array.h.

Friends And Related Function Documentation

◆ ArrayBuffer

template<class E , class INDEX = int>
template<class F , class I >
friend class ArrayBuffer
friend

Definition at line 684 of file Array.h.

Member Data Documentation

◆ m_high

template<class E , class INDEX = int>
INDEX ogdf::Array< E, INDEX >::m_high
private

The highest index.

Definition at line 691 of file Array.h.

◆ m_low

template<class E , class INDEX = int>
INDEX ogdf::Array< E, INDEX >::m_low
private

The lowest index.

Definition at line 690 of file Array.h.

◆ m_pStart

template<class E , class INDEX = int>
E* ogdf::Array< E, INDEX >::m_pStart
private

The real start of the array (address of A[m_low]).

Definition at line 688 of file Array.h.

◆ m_pStop

template<class E , class INDEX = int>
E* ogdf::Array< E, INDEX >::m_pStop
private

Successor of last element (address of A[m_high+1]).

Definition at line 689 of file Array.h.

◆ m_vpStart

template<class E , class INDEX = int>
E* ogdf::Array< E, INDEX >::m_vpStart
private

The virtual start of the array (address of A[0]).

Definition at line 687 of file Array.h.

◆ maxSizeInsertionSort

template<class E , class INDEX = int>
const int ogdf::Array< E, INDEX >::maxSizeInsertionSort = 40
static

Threshold used by quicksort() such that insertion sort is called for instances smaller than maxSizeInsertionSort.

Definition at line 208 of file Array.h.


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