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

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

#include <ogdf/basic/Array.h>

Inherited by ogdf::AdjEntryArray< ogdf::FaceElement > [private], ogdf::AdjEntryArray< int > [private], ogdf::AdjEntryArray< ogdf::NodeElement > [private], ogdf::AdjEntryArray< BendType > [private], ogdf::AdjEntryArray< bool > [private], ogdf::AdjEntryArray< ogdf::InOutPoint * > [private], ogdf::AdjEntryArray< ogdf::EdgeElement > [private], ogdf::AdjEntryArray< ogdf::AdjElement > [private], ogdf::AdjEntryArray< ogdf::BendString > [private], ogdf::AdjEntryArray< OrthoDir > [private], ogdf::AdjEntryArray< ogdf::ListIteratorBase< ogdf::AdjElement > > [private], ogdf::ArrayBuffer< ogdf::steiner_tree::FullComponentStore::Metadata< ExtraDataType > > [private], ogdf::ArrayBuffer< ogdf::steiner_tree::FullComponentStore::Metadata< LossMetadata< T > > > [private], ogdf::ArrayBuffer< edge > [private], ogdf::ArrayBuffer< abacus::PoolSlotRef< abacus::Variable, abacus::Constraint > * > [private], ogdf::ArrayBuffer< abacus::FSVarStat * > [private], ogdf::ArrayBuffer< double > [private], ogdf::ArrayBuffer< abacus::InfeasCon * > [private], ogdf::ArrayBuffer< BaseType * > [private], ogdf::ArrayBuffer< int > [private], ogdf::ArrayBuffer< abacus::Sub * > [private], ogdf::ArrayBuffer< ogdf::AdjElement > [private], ogdf::ArrayBuffer< ogdf::EdgeElement > [private], ogdf::ArrayBuffer< ogdf::ClusterElement > [private], ogdf::ArrayBuffer< ogdf::NodeElement > [private], ogdf::ArrayBuffer< ogdf::steiner_tree::FullComponentStore::Metadata< double > > [private], ogdf::ArrayBuffer< ogdf::PlanRep::Deg1RestoreInfo > [private], ogdf::ArrayBuffer< T > [private], ogdf::ArrayBuffer< abacus::Constraint * > [private], ogdf::ArrayBuffer< NodePair > [private], ogdf::ArrayBuffer< const ogdf::steiner_tree::FullComponentGeneratorDreyfusWagner::DWMData * > [private], ogdf::ArrayBuffer< const ogdf::steiner_tree::FullComponentGeneratorDreyfusWagnerWithoutMatrix::DWMData * > [private], ogdf::ArrayBuffer< ogdf::steiner_tree::FullComponentStore::Metadata< void > > [private], ogdf::ArrayBuffer< ogdf::steiner_tree::LowerBoundDualAscent::TerminalDataReference > [private], ogdf::ArrayBuffer< ogdf::ArrayBuffer< ogdf::NodeElement > > [private], ogdf::ClusterArray< ogdf::booth_lueker::PlanarPQTree * > [private], ogdf::ClusterArray< ogdf::booth_lueker::EmbedPQTree * > [private], ogdf::ClusterArray< ogdf::NodeArray< ogdf::SListPure< ogdf::AdjElement > > * > [private], ogdf::ClusterArray< ogdf::Graph * > [private], ogdf::ClusterArray< ogdf::NodeArray< bool > * > [private], ogdf::ClusterArray< ogdf::NodeArray< ogdf::ClusterElement > * > [private], ogdf::ClusterArray< ogdf::NodeArray< ogdf::NodeElement > * > [private], ogdf::ClusterArray< ogdf::ClusterGraph * > [private], ogdf::ClusterArray< ogdf::ClusterArray< ogdf::ClusterElement > * > [private], ogdf::ClusterArray< ogdf::ClusterElement > [private], ogdf::ClusterArray< ogdf::NodeElement > [private], ogdf::ClusterArray< ogdf::EdgeArray< ogdf::ArrayBuffer< ogdf::EdgeElement > * > * > [private], ogdf::ClusterArray< ogdf::cluster_planarity::ClusterPQContainer > [private], ogdf::ClusterArray< bool > [private], ogdf::ClusterArray< int > [private], ogdf::ClusterArray< ogdf::List< ogdf::NodeElement > > [private], ogdf::ClusterArray< ogdf::List< ogdf::EdgeElement > > [private], ogdf::ClusterArray< double > [private], ogdf::ClusterArray< string > [private], ogdf::ClusterArray< ogdf::Stroke > [private], ogdf::ClusterArray< ogdf::Fill > [private], ogdf::ClusterArray< ogdf::ListIteratorBase< ogdf::ClusterElement > > [private], ogdf::ClusterArray< ogdf::LHTreeNode * > [private], ogdf::EdgeArray< TCap > [private], ogdf::EdgeArray< PrioritizedQueue< edge, P, C, Impl >::Handle > [private], ogdf::EdgeArray< ogdf::EdgeElement > [private], ogdf::EdgeArray< ogdf::NodeElement > [private], ogdf::EdgeArray< ogdf::Block * > [private], ogdf::EdgeArray< bool > [private], ogdf::EdgeArray< ogdf::ListPure< ogdf::EdgeElement > > [private], ogdf::EdgeArray< int > [private], ogdf::EdgeArray< BoyerMyrvoldEdgeType > [private], ogdf::EdgeArray< ogdf::AdjElement > [private], ogdf::EdgeArray< ogdf::ArrayBuffer< ogdf::EdgeElement > * > [private], ogdf::EdgeArray< double > [private], ogdf::EdgeArray< ConstraintEdgeType > [private], ogdf::EdgeArray< ATYPE > [private], ogdf::EdgeArray< ogdf::ListIteratorBase< ogdf::EdgeElement > > [private], ogdf::EdgeArray< ogdf::EdgeLabel< coordType > > [private], ogdf::EdgeArray< ogdf::HyperedgeElement > [private], ogdf::EdgeArray< ogdf::embedder::MDMFLengthAttribute > [private], ogdf::EdgeArray< ogdf::List< ogdf::EdgeElement > > [private], ogdf::EdgeArray< float > [private], ogdf::EdgeArray< uint32_t > [private], ogdf::EdgeArray< ogdf::List< ogdf::NonPlanarCore::CutEdge > > [private], ogdf::EdgeArray< TCost > [private], ogdf::EdgeArray< ogdf::NodeArray< ogdf::NodeElement > * > [private], ogdf::EdgeArray< ogdf::EdgeArray< ogdf::EdgeElement > * > [private], ogdf::EdgeArray< ogdf::Graph * > [private], ogdf::EdgeArray< ogdf::GenericPolyline > [private], ogdf::EdgeArray< string > [private], ogdf::EdgeArray< EdgeArrow > [private], ogdf::EdgeArray< ogdf::Stroke > [private], ogdf::EdgeArray< Graph::EdgeType > [private], ogdf::EdgeArray< ogdf::MinSteinerTreeDirectedCut::EdgeVariable * > [private], ogdf::EdgeArray< EdgeType > [private], ogdf::EdgeArray< edgeType > [private], ogdf::EdgeArray< ogdf::PlanRepExpansion::NodeSplit * > [private], ogdf::EdgeArray< TWeight > [private], ogdf::EdgeArray< ogdf::StaticSkeleton * > [private], ogdf::EdgeArray< ogdf::List< ogdf::topology_module::EdgeLeg * > > [private], ogdf::EdgeArray< ogdf::ListIteratorBase< int > > [private], ogdf::EdgeArray< ogdf::UMLGraph::AssociationClass * > [private], ogdf::EdgeArray< ogdf::VisibilityLayout::EdgeSegment > [private], ogdf::EdgeArray< ogdf::ClusterElement > [private], ogdf::EdgeArray< ogdf::booth_lueker::PlanarLeafKey > [private], ogdf::EdgeArray< ogdf::List< GenericPoint< int > > > [private], ogdf::EdgeArray< ogdf::SListPure< int > > [private], ogdf::EdgeArray< ogdf::fast_multipole_embedder::GalaxyMultilevel::LevelEdgeInfo > [private], ogdf::FaceArray< ogdf::NodeElement > [private], ogdf::FaceArray< ogdf::ListIteratorBase< ogdf::FaceElement > > [private], ogdf::FaceArray< int > [private], ogdf::FaceArray< ogdf::FaceElement > [private], ogdf::FaceArray< ogdf::List< ogdf::NodeElement > > [private], ogdf::FaceArray< bool > [private], ogdf::HyperedgeArray< ogdf::List< ogdf::EdgeElement > > [private], ogdf::HypernodeArray< ogdf::NodeElement > [private], ogdf::HypernodeArray< string > [private], ogdf::HypernodeArray< double > [private], ogdf::HypernodeArray< int > [private], ogdf::NodeArray< PrioritizedQueue< node, P, C, Impl >::Handle > [private], ogdf::NodeArray< bool > [private], ogdf::NodeArray< ogdf::NodeElement > [private], ogdf::NodeArray< ogdf::EdgeElement > [private], ogdf::NodeArray< int > [private], ogdf::NodeArray< BNodeType > [private], ogdf::NodeArray< ogdf::SList< ogdf::EdgeElement > > [private], ogdf::NodeArray< double > [private], ogdf::NodeArray< ogdf::List< ogdf::NodeElement > > [private], ogdf::NodeArray< ogdf::BertaultLayout::BertaultSections > [private], ogdf::NodeArray< ogdf::Block * > [private], ogdf::NodeArray< ogdf::Array< ogdf::NodeElement > > [private], ogdf::NodeArray< ogdf::AdjElement > [private], ogdf::NodeArray< ogdf::ListPure< ogdf::NodeElement > > [private], ogdf::NodeArray< ogdf::ListIteratorBase< ogdf::NodeElement > > [private], ogdf::NodeArray< ogdf::SListPure< ogdf::AdjElement > > [private], ogdf::NodeArray< ogdf::SListPure< ogdf::NodeElement > > [private], ogdf::NodeArray< ogdf::ClusterElement > [private], ogdf::NodeArray< ogdf::ClusterArray< int > * > [private], ogdf::NodeArray< ogdf::CoffmanGrahamRanking::_int_set > [private], ogdf::NodeArray< ATYPE > [private], ogdf::NodeArray< ogdf::FaceElement > [private], ogdf::NodeArray< TNodeType > [private], ogdf::NodeArray< ogdf::List< ogdf::EdgeElement > * > [private], ogdf::NodeArray< ogdf::DynamicSkeleton * > [private], ogdf::NodeArray< ogdf::RoutingChannel::vInfo > [private], ogdf::NodeArray< ogdf::MinimumEdgeDistances::InfoType > [private], ogdf::NodeArray< ogdf::edge_router::NodeInfo > [private], ogdf::NodeArray< BendType > [private], ogdf::NodeArray< ProcessType > [private], ogdf::NodeArray< OrthoDir > [private], ogdf::NodeArray< ogdf::HypernodeElement > [private], ogdf::NodeArray< ogdf::Graph > [private], ogdf::NodeArray< ogdf::NodeArray< ogdf::NodeElement > > [private], ogdf::NodeArray< ogdf::EdgeArray< ogdf::EdgeElement > > [private], ogdf::NodeArray< ogdf::NodeArray< int > > [private], ogdf::NodeArray< ogdf::List< ogdf::AdjElement > > [private], ogdf::NodeArray< ogdf::StaticSPQRTree * > [private], ogdf::NodeArray< ogdf::embedder::MDMFLengthAttribute > [private], ogdf::NodeArray< ogdf::SList< int > > [private], ogdf::NodeArray< NodeType > [private], ogdf::NodeArray< float > [private], ogdf::NodeArray< ogdf::WInfo * > [private], ogdf::NodeArray< Shape > [private], ogdf::NodeArray< string > [private], ogdf::NodeArray< ogdf::Stroke > [private], ogdf::NodeArray< ogdf::Fill > [private], ogdf::NodeArray< Graph::NodeType > [private], ogdf::NodeArray< ogdf::List< ogdf::InOutPoint > > [private], ogdf::NodeArray< ogdf::SListPure< ogdf::Tuple2< ogdf::NodeElement, int > > > [private], ogdf::NodeArray< unsigned int > [private], ogdf::NodeArray< TCap > [private], ogdf::NodeArray< cutType > [private], ogdf::NodeArray< ogdf::NodeArray< T > > [private], ogdf::NodeArray< ogdf::NodeArray< ogdf::EdgeElement > > [private], ogdf::NodeArray< ogdf::ListIteratorBase< ogdf::InOutPoint > > [private], ogdf::NodeArray< ogdf::SList< ogdf::MultiEdgeApproxInserter::VertexBlock > > [private], ogdf::NodeArray< ogdf::NodeArray< double > > [private], ogdf::NodeArray< ogdf::OrthoRep::VertexInfoUML * > [private], ogdf::NodeArray< nodeType > [private], ogdf::NodeArray< ogdf::PALabel > [private], ogdf::NodeArray< ogdf::ListIteratorBase< ogdf::PALabel > > [private], ogdf::NodeArray< ogdf::SList< ogdf::AdjElement > > [private], ogdf::NodeArray< std::vector< ogdf::SolarMerger::PathData > > [private], ogdf::NodeArray< ogdf::NodeArray< TWeight > > [private], ogdf::NodeArray< TWeight > [private], ogdf::NodeArray< ogdf::StaticSkeleton * > [private], ogdf::NodeArray< GenericPoint< double > > [private], ogdf::NodeArray< ogdf::List< ogdf::EdgeElement > > [private], ogdf::NodeArray< ogdf::List< int > > [private], ogdf::NodeArray< ogdf::DRect > [private], ogdf::NodeArray< ogdf::VisibilityLayout::NodeSegment > [private], ogdf::NodeArray< ogdf::NodeArray< bool > > [private], ogdf::NodeArray< ogdf::SListPure< ogdf::booth_lueker::PlanarLeafKey > > [private], ogdf::NodeArray< ogdf::SListPure< ogdf::EdgeElement > > [private], ogdf::NodeArray< ogdf::DIntersectableRect > [private], ogdf::NodeArray< ogdf::energybased::dtree::DTreeEmbedder::NodeInfo > [private], ogdf::NodeArray< ogdf::fast_multipole_embedder::GalaxyMultilevel::LevelNodeInfo > [private], ogdf::NodeArray< ogdf::fast_multipole_embedder::GalaxyMultilevelBuilder::LevelNodeState > [private], ogdf::NodeArray< short > [private], ogdf::NodeArray< ogdf::List< ogdf::ListIteratorBase< ogdf::steiner_tree::LowerBoundDualAscent::TerminalData > > > [private], ogdf::NodeArray< ogdf::ArrayBuffer< ogdf::EdgeElement > > [private], and ogdf::ArrayBuffer< E, INDEX > [private].

Public Types
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.

Public Member Functions
	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.
Access methods
These methods provide access to elements, size, and index range.
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.
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.
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.
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.
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).
Comparison
bool	operator== (const Array< E, INDEX > &L) const
	Equality operator.
bool	operator!= (const Array< E, INDEX > &L) const
	Inequality operator.
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.
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.
Searching and sorting
These methods provide searching for values and sorting the array.
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 Public Attributes
static const int	maxSizeInsertionSort = 40
	Threshold used by quicksort() such that insertion sort is called for instances smaller than maxSizeInsertionSort.

Private Member Functions
void	construct (INDEX a, INDEX b)
	Allocates new array with index set [a, ..., b].
void	copy (const Array< E, INDEX > &A)
	Constructs a new array which is a copy of A.
void	deconstruct ()
	Deallocates array.
void	expandArray (INDEX add)
	Used by grow() to enlarge the array.
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.
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.
void	initialize ()
	Initializes elements with default constructor.
void	initialize (const E &x)
	Initializes elements with x.
void	initialize (std::initializer_list< E > initList)
	Initializes elements from given initializer list initList.

Static Private Member Functions
template<class COMPARER >
static void	quicksortInt (E *pL, E *pR, const COMPARER &comp)
	Internal Quicksort implementation with comparer template.

Private Attributes
INDEX	m_high
	The highest index.
INDEX	m_low
	The lowest index.
E *	m_pStart
	The real start of the array (address of A[m_low]).
E *	m_pStop
	Successor of last element (address of A[m_high+1]).
E *	m_vpStart
	The virtual start of the array (address of A[0]).

Friends
template<class F , class I >
class	ArrayBuffer

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

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 214 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 227 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 225 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 231 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 229 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 223 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 233 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 221 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 236 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 239 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 242 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 248 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 257 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 263 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 269 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 1018 of file Array.h.

~Array()

template<class E , class INDEX = int>

ogdf::Array< E, INDEX >::~Array ( )

inline

Destruction.

Definition at line 282 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 324 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 327 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 556 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 575 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 565 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 585 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 330 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 339 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 856 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 934 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 348 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 357 of file Array.h.

deconstruct()

template<class E , class INDEX >

void ogdf::Array< E, INDEX >::deconstruct ( )

private

Deallocates array.

Definition at line 924 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 300 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 333 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 336 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 805 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 732 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 743 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 396 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 404 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

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

Definition at line 841 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

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

Definition at line 825 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 294 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 367 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 382 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 389 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 376 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 876 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 892 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 908 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

ind	The compenents being removed from the array.

copy the rest of the buffer

Definition at line 991 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

ind	specifies the components that are removed from the array.
val	is the value used to fill the positions that become free.

Definition at line 692 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 606 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 623 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 291 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 496 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 457 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 447 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 475 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 310 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 303 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 522 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 516 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

l	left border
r	right border
rng	random number generator

Definition at line 951 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

rng	random number generator

Definition at line 538 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 634 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

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

Definition at line 644 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 637 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

l	is the left-most position in the range to be sorted.
r	is the right-most position in the range to be sorted.
comp	is a user-defined comparer; it must be a class providing a less(x,y) method.

Definition at line 657 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 761 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 342 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 345 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 351 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 354 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

newSize

is new size of the array

Definition at line 444 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

newSize	is new size of the array
x	is the inital value of all new elements.

Definition at line 437 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 297 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 506 of file Array.h.

Friends And Related Symbol Documentation

ArrayBuffer

template<class E , class INDEX = int>

template<class F , class I >

friend class ArrayBuffer

friend

Definition at line 700 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 707 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 706 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 704 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 705 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 703 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 218 of file Array.h.

---

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

• include/ogdf/basic/Array.h