Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::AdjEntryArray< T > Class Template Reference

Dynamic arrays indexed with adjacency entries. More...

#include <ogdf/basic/AdjEntryArray.h>

+ Inheritance diagram for ogdf::AdjEntryArray< T >:

Public Types

using const_iterator = internal::GraphArrayConstIterator< AdjEntryArray< T > >
 The type for adjEntry array const iterators. More...
 
using iterator = internal::GraphArrayIterator< AdjEntryArray< T > >
 The type for adjEntry array iterators. More...
 
using key_type = adjEntry
 The type for array keys. More...
 
using value_type = T
 The type for array entries. More...
 

Public Member Functions

 AdjEntryArray ()
 Constructs an empty adjacency entry array associated with no graph. More...
 
 AdjEntryArray (AdjEntryArray< T > &&A)
 Constructs an adjacency entry array containing the elements of A (move semantics). More...
 
 AdjEntryArray (const AdjEntryArray< T > &A)
 Constructs an adjacency entry array that is a copy of A. More...
 
 AdjEntryArray (const Graph &G)
 Constructs an adjacency entry array associated with G. More...
 
 AdjEntryArray (const Graph &G, const T &x)
 Constructs an adjacency entry array associated with G. More...
 
Access methods

These methods provide access to elements, size, and corresponding graph.

bool valid () const
 Returns true iff the array is associated with a graph. More...
 
const GraphgraphOf () const
 Returns a pointer to the associated graph. More...
 
const T & operator[] (adjEntry adj) const
 Returns a reference to the element with index adj. More...
 
T & operator[] (adjEntry adj)
 Returns a reference to the element with index adj. More...
 
const T & operator() (adjEntry adj) const
 Returns a reference to the element with index adj. More...
 
T & operator() (adjEntry adj)
 Returns a reference to the element with index adj. More...
 
Iterators

These methods return bidirectional iterators to elements in the array.

iterator begin ()
 Returns an iterator to the first entry in the array. More...
 
const_iterator begin () const
 Returns a const iterator to the first entry in the array. More...
 
const_iterator cbegin () const
 Returns a const iterator to the first entry in the array. More...
 
iterator end ()
 Returns an iterator to one-past-last entry in the array. More...
 
const_iterator end () const
 Returns a const iterator to one-past-last entry in the array. More...
 
const_iterator cend () const
 Returns a const iterator to one-past-last entry in the array. More...
 
Initialization and assignment

These methods can be used to reinitialize the array, or to initialize all elements with a given value.

void init ()
 Reinitializes the array. Associates the array with no graph. More...
 
void init (const Graph &G)
 Reinitializes the array. Associates the array with G. More...
 
void init (const Graph &G, const T &x)
 Reinitializes the array. Associates the array with G. More...
 
void fill (const T &x)
 Sets all array elements to x. More...
 
AdjEntryArray< T > & operator= (const AdjEntryArray< T > &A)
 Assignment operator. More...
 
AdjEntryArray< T > & operator= (AdjEntryArray< T > &&a)
 Assignment operator (move semantics). More...
 

Private Attributes

m_x
 The default value for array elements. More...
 

Helper functions

These methods are mainly intended for internal use.

static adjEntry findSuccKey (adjEntry adj)
 Returns the key succeeding adj. More...
 
static adjEntry findPredKey (adjEntry adj)
 Returns the key preceeding adj. More...
 
adjEntry findFirstKey () const
 Returns the first key (adjacency entry in the graph). More...
 
adjEntry findLastKey () const
 Returns the last key (adjacency entry in the graph). More...
 
virtual void enlargeTable (int newTableSize)
 Virtual function called when table size has to be enlarged. More...
 
virtual void reinit (int initTableSize)
 Virtual function called when table has to be reinitialized. More...
 
virtual void resetIndex (int newIndex, int oldIndex)
 Virtual function called when the index of an adjacency entry is changed. More...
 
virtual void disconnect ()
 Virtual function called when array is disconnected from the graph. More...
 

Additional Inherited Members

- Protected Member Functions inherited from ogdf::AdjEntryArrayBase
 AdjEntryArrayBase ()
 Initializes an adjacency entry array not associated with a graph. More...
 
 AdjEntryArrayBase (AdjEntryArrayBase &base)
 Moves adjacency entry array base to this adjacency entry array. More...
 
 AdjEntryArrayBase (const Graph *pG)
 Initializes an adjacency entry array associated with pG. More...
 
virtual ~AdjEntryArrayBase ()
 Destructor, unregisters the array. More...
 
void moveRegister (AdjEntryArrayBase &base)
 Moves array registration from base to this array. More...
 
void reregister (const Graph *pG)
 Associates the array with a new graph. More...
 
- Protected Attributes inherited from ogdf::AdjEntryArrayBase
const Graphm_pGraph
 The associated graph. More...
 
- Private Types inherited from ogdf::Array< T >
using const_iterator = ArrayConstIterator< T >
 Provides a random-access iterator that can read a const element in an array. More...
 
using const_reference = const T &
 Provides a reference to a const element stored in an array for reading and performing const operations. More...
 
using const_reverse_iterator = ArrayConstReverseIterator< T >
 Provides a reverse random-access iterator that can read a const element in an array. More...
 
using iterator = ArrayIterator< T >
 Provides a random-access iterator that can read or modify any element in an array. More...
 
using reference = T &
 Provides a reference to an element stored in an array. More...
 
using reverse_iterator = ArrayReverseIterator< T >
 Provides a reverse random-access iterator that can read or modify any element in an array. More...
 
using value_type = T
 Represents the data type stored in an array element. More...
 
- Private Member Functions inherited from ogdf::Array< T >
 Array ()
 Creates an array with empty index set. More...
 
 Array (Array< T, int > &&A)
 Creates an array containing the elements of A (move semantics). More...
 
 Array (const Array< T, int > &A)
 Creates an array that is a copy of A. More...
 
 Array (const ArrayBuffer< T, int > &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 (int a, int b)
 Creates an array with index set [a..b]. More...
 
 Array (int a, int b, const T &x)
 Creates an array with index set [a..b] and initializes each element with x. More...
 
 Array (int s)
 Creates an array with index set [0..s-1]. More...
 
 Array (std::initializer_list< T > initList)
 Creates an array containing the elements in the initializer list initList. More...
 
 ~Array ()
 Destruction. More...
 
int low () const
 Returns the minimal array index. More...
 
int high () const
 Returns the maximal array index. More...
 
int 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[] (int i) const
 Returns a reference to the element at position i. More...
 
reference operator[] (int i)
 Returns a reference to the element at position i. More...
 
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...
 
void init ()
 Reinitializes the array to an array with empty index set. More...
 
void init (int s)
 Reinitializes the array to an array with index set [0..s-1]. More...
 
void init (int a, int b)
 Reinitializes the array to an array with index set [a..b]. More...
 
void init (int a, int b, const T &x)
 Reinitializes the array to an array with index set [a..b] and sets all entries to x. More...
 
void fill (const T &x)
 Sets all elements to x. More...
 
void fill (int i, int j, const T &x)
 Sets elements in the intervall [i..j] to x. More...
 
void grow (int add, const T &x)
 Enlarges the array by add elements and sets new elements to x. More...
 
void grow (int add)
 Enlarges the array by add elements. More...
 
void resize (int newSize, const T &x)
 Resizes (enlarges or shrinks) the array to hold newSize elements and sets new elements to x. More...
 
void resize (int newSize)
 Resizes (enlarges or shrinks) the array to hold newSize elements. More...
 
Array< T, int > & operator= (const Array< T, int > &A)
 Assignment operator. More...
 
Array< T, int > & operator= (Array< T, int > &&A)
 Assignment operator (move semantics). More...
 
bool operator== (const Array< T, int > &L) const
 Equality operator. More...
 
bool operator!= (const Array< T, int > &L) const
 Inequality operator. More...
 
void swap (int i, int j)
 Swaps the elements at position i and j. More...
 
void permute (int l, int r)
 Randomly permutes the subarray with index set [l..r]. More...
 
void permute ()
 Randomly permutes the array. More...
 
void permute (int l, int r, RNG &rng)
 Randomly permutes the subarray with index set [l..r] using random number generator rng. More...
 
void permute (RNG &rng)
 Randomly permutes the array using random number generator rng. More...
 
int binarySearch (const T &e) const
 Performs a binary search for element e. More...
 
int binarySearch (int l, int r, const T &e) const
 Performs a binary search for element e within the array section [l, ..., r] . More...
 
int binarySearch (const T &e, const COMPARER &comp) const
 Performs a binary search for element e with comparer comp. More...
 
int binarySearch (int l, int r, const T &e, const COMPARER &comp) const
 Performs a binary search for element e within the array section [l, ..., r] with comparer comp. More...
 
int linearSearch (const T &e) const
 Performs a linear search for element e. More...
 
int linearSearch (const T &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 (int l, int r)
 Sorts subarray with index set [l, ..., r] using Quicksort. More...
 
void quicksort (const COMPARER &comp)
 Sorts array using Quicksort and a user-defined comparer comp. More...
 
void quicksort (int l, int r, const COMPARER &comp)
 Sorts the subarray with index set [l, ..., r] using Quicksort and a user-defined comparer comp. More...
 
void leftShift (ArrayBuffer< int, int > &ind)
 Removes the components listed in ind by shifting the remaining components to the left. More...
 
void leftShift (ArrayBuffer< int, int > &ind, const T &val)
 Removes the components listed in ind by shifting the remaining components to the left. More...
 
- Static Private Attributes inherited from ogdf::Array< T >
static const int maxSizeInsertionSort
 Threshold used by quicksort() such that insertion sort is called for instances smaller than maxSizeInsertionSort. More...
 

Detailed Description

template<class T>
class ogdf::AdjEntryArray< T >

Dynamic arrays indexed with adjacency entries.

Adjacency entry arrays represent a mapping from adjacency entries to data of type T. They adjust their table size automatically when the graph grows.

Warning
Undefined behavior can occur when the array is used in the left-hand side of an assignment and the observed graph is changed in the right-hand side. To resolve the issue, use:
auto tmp = RHS; LHS = std::move(tmp);
Template Parameters
Tis the element type.

Definition at line 114 of file AdjEntryArray.h.

Member Typedef Documentation

◆ const_iterator

The type for adjEntry array const iterators.

Definition at line 126 of file AdjEntryArray.h.

◆ iterator

The type for adjEntry array iterators.

Definition at line 124 of file AdjEntryArray.h.

◆ key_type

template<class T >
using ogdf::AdjEntryArray< T >::key_type = adjEntry

The type for array keys.

Definition at line 119 of file AdjEntryArray.h.

◆ value_type

template<class T >
using ogdf::AdjEntryArray< T >::value_type = T

The type for array entries.

Definition at line 121 of file AdjEntryArray.h.

Constructor & Destructor Documentation

◆ AdjEntryArray() [1/5]

template<class T >
ogdf::AdjEntryArray< T >::AdjEntryArray ( )
inline

Constructs an empty adjacency entry array associated with no graph.

Definition at line 130 of file AdjEntryArray.h.

◆ AdjEntryArray() [2/5]

template<class T >
ogdf::AdjEntryArray< T >::AdjEntryArray ( const Graph G)
inlineexplicit

Constructs an adjacency entry array associated with G.

Definition at line 133 of file AdjEntryArray.h.

◆ AdjEntryArray() [3/5]

template<class T >
ogdf::AdjEntryArray< T >::AdjEntryArray ( const Graph G,
const T &  x 
)
inline

Constructs an adjacency entry array associated with G.

Parameters
Gis the associated graph.
xis the default value for all array elements.

Definition at line 140 of file AdjEntryArray.h.

◆ AdjEntryArray() [4/5]

template<class T >
ogdf::AdjEntryArray< T >::AdjEntryArray ( const AdjEntryArray< T > &  A)
inline

Constructs an adjacency entry array that is a copy of A.

Associates the array with the same graph as A and copies all elements.

Definition at line 147 of file AdjEntryArray.h.

◆ AdjEntryArray() [5/5]

template<class T >
ogdf::AdjEntryArray< T >::AdjEntryArray ( AdjEntryArray< T > &&  A)
inline

Constructs an adjacency entry array containing the elements of A (move semantics).

Adjacency entry array A is empty afterwards and not associated with any graph.

Definition at line 153 of file AdjEntryArray.h.

Member Function Documentation

◆ begin() [1/2]

template<class T >
iterator ogdf::AdjEntryArray< T >::begin ( )
inline

Returns an iterator to the first entry in the array.

If the array is empty, a null pointer iterator is returned.

Definition at line 210 of file AdjEntryArray.h.

◆ begin() [2/2]

template<class T >
const_iterator ogdf::AdjEntryArray< T >::begin ( ) const
inline

Returns a const iterator to the first entry in the array.

If the array is empty, a null pointer iterator is returned.

Definition at line 218 of file AdjEntryArray.h.

◆ cbegin()

template<class T >
const_iterator ogdf::AdjEntryArray< T >::cbegin ( ) const
inline

Returns a const iterator to the first entry in the array.

If the array is empty, a null pointer iterator is returned.

Definition at line 224 of file AdjEntryArray.h.

◆ cend()

template<class T >
const_iterator ogdf::AdjEntryArray< T >::cend ( ) const
inline

Returns a const iterator to one-past-last entry in the array.

This is always a null pointer iterator.

Definition at line 242 of file AdjEntryArray.h.

◆ disconnect()

template<class T >
virtual void ogdf::AdjEntryArray< T >::disconnect ( )
inlineprivatevirtual

Virtual function called when array is disconnected from the graph.

Implements ogdf::AdjEntryArrayBase.

Definition at line 357 of file AdjEntryArray.h.

◆ end() [1/2]

template<class T >
iterator ogdf::AdjEntryArray< T >::end ( )
inline

Returns an iterator to one-past-last entry in the array.

This is always a null pointer iterator.

Definition at line 230 of file AdjEntryArray.h.

◆ end() [2/2]

template<class T >
const_iterator ogdf::AdjEntryArray< T >::end ( ) const
inline

Returns a const iterator to one-past-last entry in the array.

This is always a null pointer iterator.

Definition at line 236 of file AdjEntryArray.h.

◆ enlargeTable()

template<class T >
virtual void ogdf::AdjEntryArray< T >::enlargeTable ( int  newTableSize)
inlineprivatevirtual

Virtual function called when table size has to be enlarged.

Implements ogdf::AdjEntryArrayBase.

Definition at line 345 of file AdjEntryArray.h.

◆ fill()

template<class T >
void ogdf::AdjEntryArray< T >::fill ( const T &  x)
inline

Sets all array elements to x.

Definition at line 271 of file AdjEntryArray.h.

◆ findFirstKey()

template<class T >
adjEntry ogdf::AdjEntryArray< T >::findFirstKey ( ) const
inlineprivate

Returns the first key (adjacency entry in the graph).

Definition at line 328 of file AdjEntryArray.h.

◆ findLastKey()

template<class T >
adjEntry ogdf::AdjEntryArray< T >::findLastKey ( ) const
inlineprivate

Returns the last key (adjacency entry in the graph).

Definition at line 337 of file AdjEntryArray.h.

◆ findPredKey()

template<class T >
static adjEntry ogdf::AdjEntryArray< T >::findPredKey ( adjEntry  adj)
inlinestatic

Returns the key preceeding adj.

Definition at line 315 of file AdjEntryArray.h.

◆ findSuccKey()

template<class T >
static adjEntry ogdf::AdjEntryArray< T >::findSuccKey ( adjEntry  adj)
inlinestatic

Returns the key succeeding adj.

Definition at line 305 of file AdjEntryArray.h.

◆ graphOf()

template<class T >
const Graph* ogdf::AdjEntryArray< T >::graphOf ( ) const
inline

Returns a pointer to the associated graph.

Definition at line 166 of file AdjEntryArray.h.

◆ init() [1/3]

template<class T >
void ogdf::AdjEntryArray< T >::init ( )
inline

Reinitializes the array. Associates the array with no graph.

Definition at line 252 of file AdjEntryArray.h.

◆ init() [2/3]

template<class T >
void ogdf::AdjEntryArray< T >::init ( const Graph G)
inline

Reinitializes the array. Associates the array with G.

Definition at line 257 of file AdjEntryArray.h.

◆ init() [3/3]

template<class T >
void ogdf::AdjEntryArray< T >::init ( const Graph G,
const T &  x 
)
inline

Reinitializes the array. Associates the array with G.

Parameters
Gis the associated graph.
xis the default value.

Definition at line 266 of file AdjEntryArray.h.

◆ operator()() [1/2]

template<class T >
T& ogdf::AdjEntryArray< T >::operator() ( adjEntry  adj)
inline

Returns a reference to the element with index adj.

Definition at line 192 of file AdjEntryArray.h.

◆ operator()() [2/2]

template<class T >
const T& ogdf::AdjEntryArray< T >::operator() ( adjEntry  adj) const
inline

Returns a reference to the element with index adj.

Definition at line 185 of file AdjEntryArray.h.

◆ operator=() [1/2]

template<class T >
AdjEntryArray<T>& ogdf::AdjEntryArray< T >::operator= ( AdjEntryArray< T > &&  a)
inline

Assignment operator (move semantics).

Adjacency entry array a is empty afterwards and not associated with any graph.

Definition at line 289 of file AdjEntryArray.h.

◆ operator=() [2/2]

template<class T >
AdjEntryArray<T>& ogdf::AdjEntryArray< T >::operator= ( const AdjEntryArray< T > &  A)
inline

Assignment operator.

Definition at line 278 of file AdjEntryArray.h.

◆ operator[]() [1/2]

template<class T >
T& ogdf::AdjEntryArray< T >::operator[] ( adjEntry  adj)
inline

Returns a reference to the element with index adj.

Definition at line 178 of file AdjEntryArray.h.

◆ operator[]() [2/2]

template<class T >
const T& ogdf::AdjEntryArray< T >::operator[] ( adjEntry  adj) const
inline

Returns a reference to the element with index adj.

Definition at line 171 of file AdjEntryArray.h.

◆ reinit()

template<class T >
virtual void ogdf::AdjEntryArray< T >::reinit ( int  initTableSize)
inlineprivatevirtual

Virtual function called when table has to be reinitialized.

Implements ogdf::AdjEntryArrayBase.

Definition at line 349 of file AdjEntryArray.h.

◆ resetIndex()

template<class T >
virtual void ogdf::AdjEntryArray< T >::resetIndex ( int  newIndex,
int  oldIndex 
)
inlineprivatevirtual

Virtual function called when the index of an adjacency entry is changed.

Implements ogdf::AdjEntryArrayBase.

Definition at line 353 of file AdjEntryArray.h.

◆ valid()

template<class T >
bool ogdf::AdjEntryArray< T >::valid ( ) const
inline

Returns true iff the array is associated with a graph.

Definition at line 163 of file AdjEntryArray.h.

Member Data Documentation

◆ m_x

template<class T >
T ogdf::AdjEntryArray< T >::m_x
private

The default value for array elements.

Definition at line 115 of file AdjEntryArray.h.


The documentation for this class was generated from the following file:
backward::details::move
const T & move(const T &v)
Definition: backward.hpp:243