Open
Graph Drawing
Framework

 v.2012.07
 

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

The parameterized class Array<E,INDEX> implements dynamic arrays of type E. More...

#include <ogdf/basic/Array.h>

+ Inheritance diagram for ogdf::Array< E, INDEX >:

List of all members.

Public Types

enum  { maxSizeInsertionSort = 40 }

Public Member Functions

 Array ()
 Creates an array with empty index set.
 Array (INDEX s)
 Creates an array with index set [0..s-1].
 Array (INDEX a, INDEX b)
 Creates an array with index set [a..b].
 Array (INDEX a, INDEX b, const E &x)
 Creates an array with index set [a..b] and initializes each element with x.
 Array (const Array< E > &A)
 Creates an array that is a copy of A.
 ~Array ()
E * begin ()
 Returns a pointer to the first element.
const E * begin () const
 Returns a pointer to the first element.
int binarySearch (const E &x) const
 Performs a binary search for element x.
template<class COMPARER >
int binarySearch (const E &e, const COMPARER &comp) const
 Performs a binary search for element x with comparer comp.
E * end ()
 Returns a pointer to one past the last element.
const E * end () const
 Returns a pointer to one past the last element.
void fill (const E &x)
 Sets all elements to x.
void fill (INDEX i, INDEX j, const E &x)
 Sets elements in the intervall [i..j] to x.
void grow (INDEX add, const E &x)
 Enlarges the array by add elements and sets new elements to x.
void grow (INDEX add)
 Enlarges the array by add elements.
INDEX high () const
 Returns the maximal array index.
void init ()
 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.
int linearSearch (const E &e) const
 Performs a linear search for element x.
template<class COMPARER >
int linearSearch (const E &e, const COMPARER &comp) const
 Performs a linear search for element x with comparer comp.
INDEX low () const
 Returns the minimal array index.
Array< E, INDEX > & operator= (const Array< E, INDEX > &array2)
 Assignment operator.
const E & operator[] (INDEX i) const
 Returns a reference to the element at position i.
E & operator[] (INDEX i)
 Returns a reference to the element at position i.
void permute (INDEX l, INDEX r)
 Randomly permutes the subarray with index set [l..r].
void permute ()
 Randomly permutes the array.
void quicksort ()
 Sorts array using Quicksort.
void quicksort (INDEX l, INDEX r)
 Sorts subarray with index set [l..r] using Quicksort.
template<class COMPARER >
void quicksort (const COMPARER &comp)
 Sorts array using Quicksort and a user-defined comparer comp.
template<class COMPARER >
void quicksort (INDEX l, INDEX r, const COMPARER &comp)
 Sorts the subarray with index set [l..r] using Quicksort and a user-defined comparer comp.
E * rbegin ()
 Returns a pointer to the last element.
const E * rbegin () const
 Returns a pointer to the last element.
E * rend ()
 Returns a pointer to one before the first element.
const E * rend () const
 Returns a pointer to one before the first element.
INDEX size () const
 Returns the size (number of elements) of the array.
void swap (INDEX i, INDEX j)
 Swaps the elements at position i and j.

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 initialize ()
 Initializes elements with default constructor.
void initialize (const E &x)
 Initializes elements with x.

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

class ArrayBuffer

Detailed Description

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

The parameterized class Array<E,INDEX> 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 106 of file Array.h.


Member Enumeration Documentation

template<class E, class INDEX = int>
anonymous enum

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

Enumerator:
maxSizeInsertionSort 

Definition at line 110 of file Array.h.


Constructor & Destructor Documentation

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

Creates an array with empty index set.

Definition at line 114 of file Array.h.

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 117 of file Array.h.

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 122 of file Array.h.

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 127 of file Array.h.

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

Creates an array that is a copy of A.

Definition at line 132 of file Array.h.

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

Definition at line 137 of file Array.h.


Member Function Documentation

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

Returns a pointer to the first element.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 151 of file Array.h.

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

Returns a pointer to the first element.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 154 of file Array.h.

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

Performs a binary search for element x.

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

Definition at line 276 of file Array.h.

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 x 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 286 of file Array.h.

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 476 of file Array.h.

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 538 of file Array.h.

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

Deallocates array.

Definition at line 527 of file Array.h.

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

Returns a pointer to one past the last element.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 157 of file Array.h.

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

Returns a pointer to one past the last element.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 160 of file Array.h.

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

Sets all elements to x.

Reimplemented in ogdf::ClusterArray< T >, ogdf::ClusterArray< NodeArray< bool > * >, ogdf::ClusterArray< node >, ogdf::ClusterArray< EdgeArray< Stack< edge > * > * >, ogdf::ClusterArray< EmbedPQTree * >, ogdf::ClusterArray< LHTreeNode * >, ogdf::ClusterArray< ClusterPQContainer >, ogdf::ClusterArray< int >, ogdf::ClusterArray< Graph * >, ogdf::ClusterArray< NodeArray< SListPure< adjEntry > > * >, ogdf::ClusterArray< String >, ogdf::ClusterArray< ListIterator< cluster > >, ogdf::ClusterArray< cluster >, ogdf::ClusterArray< NodeArray< cluster > * >, ogdf::ClusterArray< ClusterArray< cluster > * >, ogdf::ClusterArray< PlanarPQTree * >, ogdf::ClusterArray< bool >, ogdf::ClusterArray< ClusterGraph * >, ogdf::ClusterArray< NodeArray< node > * >, ogdf::EdgeArray< T >, ogdf::EdgeArray< EdgeStyle >, ogdf::EdgeArray< AssociationClass * >, ogdf::EdgeArray< StaticSkeleton * >, ogdf::EdgeArray< Stack< edge > * >, ogdf::EdgeArray< NodeSplit * >, ogdf::EdgeArray< double >, ogdf::EdgeArray< node >, ogdf::EdgeArray< ListIterator< edge > >, ogdf::EdgeArray< ATYPE >, ogdf::EdgeArray< List< List< LabelInfo > > >, ogdf::EdgeArray< List< PosInfo > >, ogdf::EdgeArray< float >, ogdf::EdgeArray< int >, ogdf::EdgeArray< String >, ogdf::EdgeArray< unsigned int >, ogdf::EdgeArray< EdgeType >, ogdf::EdgeArray< IPolyline >, ogdf::EdgeArray< List< IPoint > >, ogdf::EdgeArray< EdgeLabel< coordType > >, ogdf::EdgeArray< cluster >, ogdf::EdgeArray< List< edge > >, ogdf::EdgeArray< edgeType >, ogdf::EdgeArray< coordType >, ogdf::EdgeArray< PlanarLeafKey< IndInfo * > * >, ogdf::EdgeArray< ConstraintEdgeType >, ogdf::EdgeArray< List< GenericPoint< coordType > > >, ogdf::EdgeArray< MDMFLengthAttribute >, ogdf::EdgeArray< EdgeArrow >, ogdf::EdgeArray< ListPure< edge > >, ogdf::EdgeArray< DPolyline >, ogdf::EdgeArray< bool >, ogdf::EdgeArray< EdgeSegment >, ogdf::EdgeArray< List< EdgeLeg * > >, ogdf::EdgeArray< face >, ogdf::EdgeArray< edge >, ogdf::EdgeArray< Graph::EdgeType >, ogdf::EdgeArray< List< SegmentInfo > >, ogdf::EdgeArray< adjEntry >, ogdf::EdgeArray< SListPure< int > >, ogdf::FaceArray< T >, ogdf::FaceArray< node >, ogdf::FaceArray< ListIterator< face > >, ogdf::FaceArray< bool >, ogdf::NodeArray< T >, ogdf::NodeArray< EdgeStyle >, ogdf::NodeArray< bend_type >, ogdf::NodeArray< DRect >, ogdf::NodeArray< StaticSkeleton * >, ogdf::NodeArray< Grouping >, ogdf::NodeArray< EdgeArray< edge > >, ogdf::NodeArray< ListIterator< node > >, ogdf::NodeArray< TNodeType >, ogdf::NodeArray< double >, ogdf::NodeArray< node >, ogdf::NodeArray< InfoType >, ogdf::NodeArray< Graph >, ogdf::NodeArray< ATYPE >, ogdf::NodeArray< BrushPattern >, ogdf::NodeArray< float >, ogdf::NodeArray< SListPure< PlanarLeafKey< IndInfo * > * > >, ogdf::NodeArray< _int_set >, ogdf::NodeArray< IntersectionRectangle >, ogdf::NodeArray< SListPure< node > >, ogdf::NodeArray< int >, ogdf::NodeArray< String >, ogdf::NodeArray< unsigned int >, ogdf::NodeArray< SListPure< edge > >, ogdf::NodeArray< Array< node > >, ogdf::NodeArray< WInfo * >, ogdf::NodeArray< SListPure< Tuple2< node, int > > >, ogdf::NodeArray< vInfo >, ogdf::NodeArray< ListIterator< pa_label > >, ogdf::NodeArray< SList< int > >, ogdf::NodeArray< NodeInfo >, ogdf::NodeArray< ImageAlignment >, ogdf::NodeArray< cluster >, ogdf::NodeArray< List< edge > * >, ogdf::NodeArray< List< edge > >, ogdf::NodeArray< FeatureInfo >, ogdf::NodeArray< process_type >, ogdf::NodeArray< SList< adjEntry > >, ogdf::NodeArray< DPoint >, ogdf::NodeArray< SList< edge > >, ogdf::NodeArray< MDMFLengthAttribute >, ogdf::NodeArray< ImageStyle >, ogdf::NodeArray< List< node > >, ogdf::NodeArray< OrthoDir >, ogdf::NodeArray< std::vector< PathData > >, ogdf::NodeArray< NodeSegment >, ogdf::NodeArray< NodeType >, ogdf::NodeArray< pa_label >, ogdf::NodeArray< SList< VertexBlock > >, ogdf::NodeArray< bool >, ogdf::NodeArray< SListPure< adjEntry > >, ogdf::NodeArray< nodeType >, ogdf::NodeArray< Graph::NodeType >, ogdf::NodeArray< face >, ogdf::NodeArray< List< adjEntry > >, ogdf::NodeArray< VertexInfoUML * >, ogdf::NodeArray< edge >, ogdf::NodeArray< BNodeType >, ogdf::NodeArray< ListPure< node > >, ogdf::NodeArray< DynamicSkeleton * >, ogdf::NodeArray< sorterType >, ogdf::NodeArray< StaticSPQRTree * >, ogdf::NodeArray< NodeArray< int > >, ogdf::NodeArray< NodeArray< node > >, ogdf::NodeArray< adjEntry >, ogdf::AdjEntryArray< T >, ogdf::AdjEntryArray< bend_type >, ogdf::AdjEntryArray< node >, ogdf::AdjEntryArray< int >, ogdf::AdjEntryArray< bool >, ogdf::AdjEntryArray< OrthoDir >, ogdf::AdjEntryArray< BendString >, ogdf::AdjEntryArray< face >, ogdf::AdjEntryArray< edge >, and ogdf::AdjEntryArray< adjEntry >.

Definition at line 232 of file Array.h.

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 239 of file Array.h.

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 427 of file Array.h.

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 452 of file Array.h.

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

Returns the maximal array index.

Definition at line 145 of file Array.h.

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

Reinitializes the array to an array with empty index set.

Reimplemented in ogdf::ClusterArray< T >, ogdf::ClusterArray< NodeArray< bool > * >, ogdf::ClusterArray< node >, ogdf::ClusterArray< EdgeArray< Stack< edge > * > * >, ogdf::ClusterArray< EmbedPQTree * >, ogdf::ClusterArray< LHTreeNode * >, ogdf::ClusterArray< ClusterPQContainer >, ogdf::ClusterArray< int >, ogdf::ClusterArray< Graph * >, ogdf::ClusterArray< NodeArray< SListPure< adjEntry > > * >, ogdf::ClusterArray< String >, ogdf::ClusterArray< ListIterator< cluster > >, ogdf::ClusterArray< cluster >, ogdf::ClusterArray< NodeArray< cluster > * >, ogdf::ClusterArray< ClusterArray< cluster > * >, ogdf::ClusterArray< PlanarPQTree * >, ogdf::ClusterArray< bool >, ogdf::ClusterArray< ClusterGraph * >, ogdf::ClusterArray< NodeArray< node > * >, ogdf::EdgeArray< T >, ogdf::EdgeArray< EdgeStyle >, ogdf::EdgeArray< AssociationClass * >, ogdf::EdgeArray< StaticSkeleton * >, ogdf::EdgeArray< Stack< edge > * >, ogdf::EdgeArray< NodeSplit * >, ogdf::EdgeArray< double >, ogdf::EdgeArray< node >, ogdf::EdgeArray< ListIterator< edge > >, ogdf::EdgeArray< ATYPE >, ogdf::EdgeArray< List< List< LabelInfo > > >, ogdf::EdgeArray< List< PosInfo > >, ogdf::EdgeArray< float >, ogdf::EdgeArray< int >, ogdf::EdgeArray< String >, ogdf::EdgeArray< unsigned int >, ogdf::EdgeArray< EdgeType >, ogdf::EdgeArray< IPolyline >, ogdf::EdgeArray< List< IPoint > >, ogdf::EdgeArray< EdgeLabel< coordType > >, ogdf::EdgeArray< cluster >, ogdf::EdgeArray< List< edge > >, ogdf::EdgeArray< edgeType >, ogdf::EdgeArray< coordType >, ogdf::EdgeArray< PlanarLeafKey< IndInfo * > * >, ogdf::EdgeArray< ConstraintEdgeType >, ogdf::EdgeArray< List< GenericPoint< coordType > > >, ogdf::EdgeArray< MDMFLengthAttribute >, ogdf::EdgeArray< EdgeArrow >, ogdf::EdgeArray< ListPure< edge > >, ogdf::EdgeArray< DPolyline >, ogdf::EdgeArray< bool >, ogdf::EdgeArray< EdgeSegment >, ogdf::EdgeArray< List< EdgeLeg * > >, ogdf::EdgeArray< face >, ogdf::EdgeArray< edge >, ogdf::EdgeArray< Graph::EdgeType >, ogdf::EdgeArray< List< SegmentInfo > >, ogdf::EdgeArray< adjEntry >, ogdf::EdgeArray< SListPure< int > >, ogdf::FaceArray< T >, ogdf::FaceArray< node >, ogdf::FaceArray< ListIterator< face > >, ogdf::FaceArray< bool >, ogdf::NodeArray< T >, ogdf::NodeArray< EdgeStyle >, ogdf::NodeArray< bend_type >, ogdf::NodeArray< DRect >, ogdf::NodeArray< StaticSkeleton * >, ogdf::NodeArray< Grouping >, ogdf::NodeArray< EdgeArray< edge > >, ogdf::NodeArray< ListIterator< node > >, ogdf::NodeArray< TNodeType >, ogdf::NodeArray< double >, ogdf::NodeArray< node >, ogdf::NodeArray< InfoType >, ogdf::NodeArray< Graph >, ogdf::NodeArray< ATYPE >, ogdf::NodeArray< BrushPattern >, ogdf::NodeArray< float >, ogdf::NodeArray< SListPure< PlanarLeafKey< IndInfo * > * > >, ogdf::NodeArray< _int_set >, ogdf::NodeArray< IntersectionRectangle >, ogdf::NodeArray< SListPure< node > >, ogdf::NodeArray< int >, ogdf::NodeArray< String >, ogdf::NodeArray< unsigned int >, ogdf::NodeArray< SListPure< edge > >, ogdf::NodeArray< Array< node > >, ogdf::NodeArray< WInfo * >, ogdf::NodeArray< SListPure< Tuple2< node, int > > >, ogdf::NodeArray< vInfo >, ogdf::NodeArray< ListIterator< pa_label > >, ogdf::NodeArray< SList< int > >, ogdf::NodeArray< NodeInfo >, ogdf::NodeArray< ImageAlignment >, ogdf::NodeArray< cluster >, ogdf::NodeArray< List< edge > * >, ogdf::NodeArray< List< edge > >, ogdf::NodeArray< FeatureInfo >, ogdf::NodeArray< process_type >, ogdf::NodeArray< SList< adjEntry > >, ogdf::NodeArray< DPoint >, ogdf::NodeArray< SList< edge > >, ogdf::NodeArray< MDMFLengthAttribute >, ogdf::NodeArray< ImageStyle >, ogdf::NodeArray< List< node > >, ogdf::NodeArray< OrthoDir >, ogdf::NodeArray< std::vector< PathData > >, ogdf::NodeArray< NodeSegment >, ogdf::NodeArray< NodeType >, ogdf::NodeArray< pa_label >, ogdf::NodeArray< SList< VertexBlock > >, ogdf::NodeArray< bool >, ogdf::NodeArray< SListPure< adjEntry > >, ogdf::NodeArray< nodeType >, ogdf::NodeArray< Graph::NodeType >, ogdf::NodeArray< face >, ogdf::NodeArray< List< adjEntry > >, ogdf::NodeArray< VertexInfoUML * >, ogdf::NodeArray< edge >, ogdf::NodeArray< BNodeType >, ogdf::NodeArray< ListPure< node > >, ogdf::NodeArray< DynamicSkeleton * >, ogdf::NodeArray< sorterType >, ogdf::NodeArray< StaticSPQRTree * >, ogdf::NodeArray< NodeArray< int > >, ogdf::NodeArray< NodeArray< node > >, ogdf::NodeArray< adjEntry >, ogdf::AdjEntryArray< T >, ogdf::AdjEntryArray< bend_type >, ogdf::AdjEntryArray< node >, ogdf::AdjEntryArray< int >, ogdf::AdjEntryArray< bool >, ogdf::AdjEntryArray< OrthoDir >, ogdf::AdjEntryArray< BendString >, ogdf::AdjEntryArray< face >, ogdf::AdjEntryArray< edge >, ogdf::AdjEntryArray< adjEntry >, ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 195 of file Array.h.

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!

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 205 of file Array.h.

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 211 of file Array.h.

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 218 of file Array.h.

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

Initializes elements with default constructor.

Definition at line 495 of file Array.h.

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

Initializes elements with x.

Definition at line 511 of file Array.h.

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

Performs a linear search for element x.

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.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 310 of file Array.h.

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

Performs a linear search for element x 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.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 323 of file Array.h.

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

Returns the minimal array index.

Definition at line 142 of file Array.h.

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

Assignment operator.

Definition at line 225 of file Array.h.

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

Returns a reference to the element at position i.

Reimplemented in ogdf::ClusterArray< T >, ogdf::ClusterArray< NodeArray< bool > * >, ogdf::ClusterArray< node >, ogdf::ClusterArray< EdgeArray< Stack< edge > * > * >, ogdf::ClusterArray< EmbedPQTree * >, ogdf::ClusterArray< LHTreeNode * >, ogdf::ClusterArray< ClusterPQContainer >, ogdf::ClusterArray< int >, ogdf::ClusterArray< Graph * >, ogdf::ClusterArray< NodeArray< SListPure< adjEntry > > * >, ogdf::ClusterArray< String >, ogdf::ClusterArray< ListIterator< cluster > >, ogdf::ClusterArray< cluster >, ogdf::ClusterArray< NodeArray< cluster > * >, ogdf::ClusterArray< ClusterArray< cluster > * >, ogdf::ClusterArray< PlanarPQTree * >, ogdf::ClusterArray< bool >, ogdf::ClusterArray< ClusterGraph * >, ogdf::ClusterArray< NodeArray< node > * >, ogdf::EdgeArray< T >, ogdf::EdgeArray< EdgeStyle >, ogdf::EdgeArray< AssociationClass * >, ogdf::EdgeArray< StaticSkeleton * >, ogdf::EdgeArray< Stack< edge > * >, ogdf::EdgeArray< NodeSplit * >, ogdf::EdgeArray< double >, ogdf::EdgeArray< node >, ogdf::EdgeArray< ListIterator< edge > >, ogdf::EdgeArray< ATYPE >, ogdf::EdgeArray< List< List< LabelInfo > > >, ogdf::EdgeArray< List< PosInfo > >, ogdf::EdgeArray< float >, ogdf::EdgeArray< int >, ogdf::EdgeArray< String >, ogdf::EdgeArray< unsigned int >, ogdf::EdgeArray< EdgeType >, ogdf::EdgeArray< IPolyline >, ogdf::EdgeArray< List< IPoint > >, ogdf::EdgeArray< EdgeLabel< coordType > >, ogdf::EdgeArray< cluster >, ogdf::EdgeArray< List< edge > >, ogdf::EdgeArray< edgeType >, ogdf::EdgeArray< coordType >, ogdf::EdgeArray< PlanarLeafKey< IndInfo * > * >, ogdf::EdgeArray< ConstraintEdgeType >, ogdf::EdgeArray< List< GenericPoint< coordType > > >, ogdf::EdgeArray< MDMFLengthAttribute >, ogdf::EdgeArray< EdgeArrow >, ogdf::EdgeArray< ListPure< edge > >, ogdf::EdgeArray< DPolyline >, ogdf::EdgeArray< bool >, ogdf::EdgeArray< EdgeSegment >, ogdf::EdgeArray< List< EdgeLeg * > >, ogdf::EdgeArray< face >, ogdf::EdgeArray< edge >, ogdf::EdgeArray< Graph::EdgeType >, ogdf::EdgeArray< List< SegmentInfo > >, ogdf::EdgeArray< adjEntry >, ogdf::EdgeArray< SListPure< int > >, ogdf::FaceArray< T >, ogdf::FaceArray< node >, ogdf::FaceArray< ListIterator< face > >, ogdf::FaceArray< bool >, ogdf::NodeArray< T >, ogdf::NodeArray< EdgeStyle >, ogdf::NodeArray< bend_type >, ogdf::NodeArray< DRect >, ogdf::NodeArray< StaticSkeleton * >, ogdf::NodeArray< Grouping >, ogdf::NodeArray< EdgeArray< edge > >, ogdf::NodeArray< ListIterator< node > >, ogdf::NodeArray< TNodeType >, ogdf::NodeArray< double >, ogdf::NodeArray< node >, ogdf::NodeArray< InfoType >, ogdf::NodeArray< Graph >, ogdf::NodeArray< ATYPE >, ogdf::NodeArray< BrushPattern >, ogdf::NodeArray< float >, ogdf::NodeArray< SListPure< PlanarLeafKey< IndInfo * > * > >, ogdf::NodeArray< _int_set >, ogdf::NodeArray< IntersectionRectangle >, ogdf::NodeArray< SListPure< node > >, ogdf::NodeArray< int >, ogdf::NodeArray< String >, ogdf::NodeArray< unsigned int >, ogdf::NodeArray< SListPure< edge > >, ogdf::NodeArray< Array< node > >, ogdf::NodeArray< WInfo * >, ogdf::NodeArray< SListPure< Tuple2< node, int > > >, ogdf::NodeArray< vInfo >, ogdf::NodeArray< ListIterator< pa_label > >, ogdf::NodeArray< SList< int > >, ogdf::NodeArray< NodeInfo >, ogdf::NodeArray< ImageAlignment >, ogdf::NodeArray< cluster >, ogdf::NodeArray< List< edge > * >, ogdf::NodeArray< List< edge > >, ogdf::NodeArray< FeatureInfo >, ogdf::NodeArray< process_type >, ogdf::NodeArray< SList< adjEntry > >, ogdf::NodeArray< DPoint >, ogdf::NodeArray< SList< edge > >, ogdf::NodeArray< MDMFLengthAttribute >, ogdf::NodeArray< ImageStyle >, ogdf::NodeArray< List< node > >, ogdf::NodeArray< OrthoDir >, ogdf::NodeArray< std::vector< PathData > >, ogdf::NodeArray< NodeSegment >, ogdf::NodeArray< NodeType >, ogdf::NodeArray< pa_label >, ogdf::NodeArray< SList< VertexBlock > >, ogdf::NodeArray< bool >, ogdf::NodeArray< SListPure< adjEntry > >, ogdf::NodeArray< nodeType >, ogdf::NodeArray< Graph::NodeType >, ogdf::NodeArray< face >, ogdf::NodeArray< List< adjEntry > >, ogdf::NodeArray< VertexInfoUML * >, ogdf::NodeArray< edge >, ogdf::NodeArray< BNodeType >, ogdf::NodeArray< ListPure< node > >, ogdf::NodeArray< DynamicSkeleton * >, ogdf::NodeArray< sorterType >, ogdf::NodeArray< StaticSPQRTree * >, ogdf::NodeArray< NodeArray< int > >, ogdf::NodeArray< NodeArray< node > >, ogdf::NodeArray< adjEntry >, ogdf::AdjEntryArray< T >, ogdf::AdjEntryArray< bend_type >, ogdf::AdjEntryArray< node >, ogdf::AdjEntryArray< int >, ogdf::AdjEntryArray< bool >, ogdf::AdjEntryArray< OrthoDir >, ogdf::AdjEntryArray< BendString >, ogdf::AdjEntryArray< face >, ogdf::AdjEntryArray< edge >, ogdf::AdjEntryArray< adjEntry >, ogdf::ShellingOrderSet, ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 175 of file Array.h.

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

Returns a reference to the element at position i.

Reimplemented in ogdf::ClusterArray< T >, ogdf::ClusterArray< NodeArray< bool > * >, ogdf::ClusterArray< node >, ogdf::ClusterArray< EdgeArray< Stack< edge > * > * >, ogdf::ClusterArray< EmbedPQTree * >, ogdf::ClusterArray< LHTreeNode * >, ogdf::ClusterArray< ClusterPQContainer >, ogdf::ClusterArray< int >, ogdf::ClusterArray< Graph * >, ogdf::ClusterArray< NodeArray< SListPure< adjEntry > > * >, ogdf::ClusterArray< String >, ogdf::ClusterArray< ListIterator< cluster > >, ogdf::ClusterArray< cluster >, ogdf::ClusterArray< NodeArray< cluster > * >, ogdf::ClusterArray< ClusterArray< cluster > * >, ogdf::ClusterArray< PlanarPQTree * >, ogdf::ClusterArray< bool >, ogdf::ClusterArray< ClusterGraph * >, ogdf::ClusterArray< NodeArray< node > * >, ogdf::EdgeArray< T >, ogdf::EdgeArray< EdgeStyle >, ogdf::EdgeArray< AssociationClass * >, ogdf::EdgeArray< StaticSkeleton * >, ogdf::EdgeArray< Stack< edge > * >, ogdf::EdgeArray< NodeSplit * >, ogdf::EdgeArray< double >, ogdf::EdgeArray< node >, ogdf::EdgeArray< ListIterator< edge > >, ogdf::EdgeArray< ATYPE >, ogdf::EdgeArray< List< List< LabelInfo > > >, ogdf::EdgeArray< List< PosInfo > >, ogdf::EdgeArray< float >, ogdf::EdgeArray< int >, ogdf::EdgeArray< String >, ogdf::EdgeArray< unsigned int >, ogdf::EdgeArray< EdgeType >, ogdf::EdgeArray< IPolyline >, ogdf::EdgeArray< List< IPoint > >, ogdf::EdgeArray< EdgeLabel< coordType > >, ogdf::EdgeArray< cluster >, ogdf::EdgeArray< List< edge > >, ogdf::EdgeArray< edgeType >, ogdf::EdgeArray< coordType >, ogdf::EdgeArray< PlanarLeafKey< IndInfo * > * >, ogdf::EdgeArray< ConstraintEdgeType >, ogdf::EdgeArray< List< GenericPoint< coordType > > >, ogdf::EdgeArray< MDMFLengthAttribute >, ogdf::EdgeArray< EdgeArrow >, ogdf::EdgeArray< ListPure< edge > >, ogdf::EdgeArray< DPolyline >, ogdf::EdgeArray< bool >, ogdf::EdgeArray< EdgeSegment >, ogdf::EdgeArray< List< EdgeLeg * > >, ogdf::EdgeArray< face >, ogdf::EdgeArray< edge >, ogdf::EdgeArray< Graph::EdgeType >, ogdf::EdgeArray< List< SegmentInfo > >, ogdf::EdgeArray< adjEntry >, ogdf::EdgeArray< SListPure< int > >, ogdf::FaceArray< T >, ogdf::FaceArray< node >, ogdf::FaceArray< ListIterator< face > >, ogdf::FaceArray< bool >, ogdf::NodeArray< T >, ogdf::NodeArray< EdgeStyle >, ogdf::NodeArray< bend_type >, ogdf::NodeArray< DRect >, ogdf::NodeArray< StaticSkeleton * >, ogdf::NodeArray< Grouping >, ogdf::NodeArray< EdgeArray< edge > >, ogdf::NodeArray< ListIterator< node > >, ogdf::NodeArray< TNodeType >, ogdf::NodeArray< double >, ogdf::NodeArray< node >, ogdf::NodeArray< InfoType >, ogdf::NodeArray< Graph >, ogdf::NodeArray< ATYPE >, ogdf::NodeArray< BrushPattern >, ogdf::NodeArray< float >, ogdf::NodeArray< SListPure< PlanarLeafKey< IndInfo * > * > >, ogdf::NodeArray< _int_set >, ogdf::NodeArray< IntersectionRectangle >, ogdf::NodeArray< SListPure< node > >, ogdf::NodeArray< int >, ogdf::NodeArray< String >, ogdf::NodeArray< unsigned int >, ogdf::NodeArray< SListPure< edge > >, ogdf::NodeArray< Array< node > >, ogdf::NodeArray< WInfo * >, ogdf::NodeArray< SListPure< Tuple2< node, int > > >, ogdf::NodeArray< vInfo >, ogdf::NodeArray< ListIterator< pa_label > >, ogdf::NodeArray< SList< int > >, ogdf::NodeArray< NodeInfo >, ogdf::NodeArray< ImageAlignment >, ogdf::NodeArray< cluster >, ogdf::NodeArray< List< edge > * >, ogdf::NodeArray< List< edge > >, ogdf::NodeArray< FeatureInfo >, ogdf::NodeArray< process_type >, ogdf::NodeArray< SList< adjEntry > >, ogdf::NodeArray< DPoint >, ogdf::NodeArray< SList< edge > >, ogdf::NodeArray< MDMFLengthAttribute >, ogdf::NodeArray< ImageStyle >, ogdf::NodeArray< List< node > >, ogdf::NodeArray< OrthoDir >, ogdf::NodeArray< std::vector< PathData > >, ogdf::NodeArray< NodeSegment >, ogdf::NodeArray< NodeType >, ogdf::NodeArray< pa_label >, ogdf::NodeArray< SList< VertexBlock > >, ogdf::NodeArray< bool >, ogdf::NodeArray< SListPure< adjEntry > >, ogdf::NodeArray< nodeType >, ogdf::NodeArray< Graph::NodeType >, ogdf::NodeArray< face >, ogdf::NodeArray< List< adjEntry > >, ogdf::NodeArray< VertexInfoUML * >, ogdf::NodeArray< edge >, ogdf::NodeArray< BNodeType >, ogdf::NodeArray< ListPure< node > >, ogdf::NodeArray< DynamicSkeleton * >, ogdf::NodeArray< sorterType >, ogdf::NodeArray< StaticSPQRTree * >, ogdf::NodeArray< NodeArray< int > >, ogdf::NodeArray< NodeArray< node > >, ogdf::NodeArray< adjEntry >, ogdf::AdjEntryArray< T >, ogdf::AdjEntryArray< bend_type >, ogdf::AdjEntryArray< node >, ogdf::AdjEntryArray< int >, ogdf::AdjEntryArray< bool >, ogdf::AdjEntryArray< OrthoDir >, ogdf::AdjEntryArray< BendString >, ogdf::AdjEntryArray< face >, ogdf::AdjEntryArray< edge >, ogdf::AdjEntryArray< adjEntry >, ogdf::ShellingOrderSet, ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 181 of file Array.h.

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

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

Definition at line 554 of file Array.h.

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

Randomly permutes the array.

Definition at line 267 of file Array.h.

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

Sorts array using Quicksort.

Definition at line 331 of file Array.h.

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 336 of file Array.h.

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; C must be a class providing a less(x,y) method.

Definition at line 345 of file Array.h.

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; C must be a class providing a less(x,y) method.

Definition at line 357 of file Array.h.

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 390 of file Array.h.

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

Returns a pointer to the last element.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 163 of file Array.h.

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

Returns a pointer to the last element.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 166 of file Array.h.

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

Returns a pointer to one before the first element.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 169 of file Array.h.

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

Returns a pointer to one before the first element.

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 172 of file Array.h.

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

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

Reimplemented in ogdf::ArrayBuffer< E, INDEX >, ogdf::ArrayBuffer< int >, and ogdf::ArrayBuffer< ABA_CONSTRAINT * >.

Definition at line 148 of file Array.h.

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 187 of file Array.h.


Friends And Related Function Documentation

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

Definition at line 364 of file Array.h.


Member Data Documentation

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

The highest index.

Definition at line 371 of file Array.h.

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

The lowest index.

Definition at line 370 of file Array.h.

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 368 of file Array.h.

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 369 of file Array.h.

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 367 of file Array.h.


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