Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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

An array that keeps track of the number of inserted elements; also usable as an efficient stack. More...

#include <ogdf/basic/Array.h>

Public Types

using const_iterator = typename Array< E, INDEX >::const_iterator
 
using const_reverse_iterator = typename Array< E, INDEX >::const_reverse_iterator
 
using iterator = typename Array< E, INDEX >::iterator
 
using key_type = INDEX
 
using reverse_iterator = typename Array< E, INDEX >::reverse_iterator
 
using value_type = E
 

Public Member Functions

 ArrayBuffer ()
 Creates an empty array buffer, without initial memory allocation. More...
 
 ArrayBuffer (ArrayBuffer< E, INDEX > &&buffer)
 Creates an array buffer containing the elements of buffer (move semantics). More...
 
 ArrayBuffer (const Array< E, INDEX > &source, bool autogrow=true)
 Creates an array buffer, initialized by the given array; you may specify that the array should not grow. More...
 
 ArrayBuffer (const ArrayBuffer< E, INDEX > &buffer)
 Creates an array buffer that is a copy of buffer. More...
 
 ArrayBuffer (INDEX size, bool autogrow=true)
 Creates an empty array buffer, allocating memory for up to size elements; you may specify that the array should not grow automatically. More...
 
iterator begin ()
 Returns an iterator to the first element. More...
 
const_iterator begin () const
 Returns a const iterator to the first element. More...
 
INDEX binarySearch (const E &e) const
 Performs a binary search for element e. More...
 
template<class COMPARER >
INDEX binarySearch (const E &e, const COMPARER &comp) const
 Performs a binary search for element e with comparer comp. More...
 
INDEX capacity () const
 Returns the current capacity of the datastructure. Note that this value is rather irrelevant if the array is growable. More...
 
void clear ()
 Clears the buffer. More...
 
template<typename EE = E, typename std::enable_if<!OGDF_TRIVIALLY_COPYABLE< EE >::value, int >::type = 0>
void compactCopy (Array< E, INDEX > &A2) const
 Generates a compact copy holding the current elements. More...
 
template<typename EE = E, typename std::enable_if< OGDF_TRIVIALLY_COPYABLE< EE >::value, int >::type = 0>
void compactCopy (Array< E, INDEX > &A2) const
 Generates a compact copy holding the current elements. More...
 
void compactCpycon (Array< E, INDEX > &A2) const
 Generates a compact copy holding the current elements. More...
 
bool empty () const
 Returns true if the buffer is empty, false otherwise. 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...
 
bool full () const
 Returns true iff the buffer is non-growable and filled. More...
 
void init ()
 Reinitializes the array, clearing it, and without initial memory allocation. More...
 
void init (INDEX size)
 Reinitializes the array, clearing it, and allocating memory for up to size elements. More...
 
bool isGrowable () const
 Returns whether the buffer will automatically expand if the initial size is insufficient. More...
 
void leftShift (ArrayBuffer< INDEX, INDEX > &ind)
 Removes the components listed in the buffer ind by shifting the remaining components to the left. More...
 
INDEX linearSearch (const E &x) const
 Performs a linear search for element x. More...
 
template<class COMPARER >
INDEX linearSearch (const E &x, const COMPARER &comp) const
 Performs a linear search for element x with comparer comp. More...
 
bool operator!= (const ArrayBuffer< E, INDEX > &L) const
 Inequality operator. More...
 
ArrayBuffer< E, INDEX > & operator= (ArrayBuffer< E, INDEX > &&buffer)
 Assignment operator (move semantics). More...
 
ArrayBuffer< E, INDEX > & operator= (const ArrayBuffer< E, INDEX > &buffer)
 Assignment operator. More...
 
bool operator== (const ArrayBuffer< E, INDEX > &L) const
 Equality operator. More...
 
E & operator[] (INDEX i)
 Returns a reference to the element at position i. More...
 
const E & operator[] (INDEX i) const
 Returns a reference to the element at position i. More...
 
void pop ()
 Removes the newest element from the buffer. More...
 
popRet ()
 Removes the newest element from the buffer and returns it. More...
 
void push (E e)
 Puts a new element in the buffer. More...
 
void quicksort ()
 Sorts buffer using Quicksort. More...
 
template<class COMPARER >
void quicksort (const COMPARER &comp)
 Sorts buffer using Quicksort and a user-defined comparer comp. More...
 
reverse_iterator rbegin ()
 Returns a reverse iterator to the last element. More...
 
const_reverse_iterator rbegin () const
 Returns a const reverse iterator to the last element. More...
 
reverse_iterator rend ()
 Returns a 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...
 
void setCapacity (INDEX newCapacity)
 Changes the capacity of the buffer (independent whether the buffer is growable of not). More...
 
void setGrowable (bool _growable)
 Sets the flag whether the buffer will automatically expand if the initial size is insufficient. More...
 
INDEX size () const
 Returns number of elements in the buffer. More...
 
E & top ()
 Returns the newest element of the buffer. More...
 
const E & top () const
 Returns the newest element of the buffer. More...
 
Reordering
template<class RNG >
void permute (INDEX l, INDEX r, RNG &rng)
 Randomly permutes the subarray with index set [l..r] using random number generator rng. More...
 
template<class RNG >
void permute (RNG &rng)
 Randomly permutes the array using random number generator rng. More...
 
void permute (INDEX l, INDEX r)
 Randomly permutes the subarray with index set [l..r]. More...
 
void permute ()
 Randomly permutes the array. More...
 

Private Attributes

bool growable
 
INDEX num
 The number of elements in the buffer. More...
 

Detailed Description

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

An array that keeps track of the number of inserted elements; also usable as an efficient stack.

This is a (by default automatically growable) array (with some initial size s) which starts out being empty. Using stack functions you can put elements into and out of it. The initial array size is automatically expanded if neccessary (unless growing is forbidden), but never automatically shrunken. You may also access the elements it contains using the []-operator. The valid indices are 0..(s - 1).

Template Parameters
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 45 of file Array.h.

Member Typedef Documentation

◆ const_iterator

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

Definition at line 62 of file ArrayBuffer.h.

◆ const_reverse_iterator

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

Definition at line 64 of file ArrayBuffer.h.

◆ iterator

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

Definition at line 63 of file ArrayBuffer.h.

◆ key_type

template<class E , class INDEX = int>
using ogdf::ArrayBuffer< E, INDEX >::key_type = INDEX

Definition at line 60 of file ArrayBuffer.h.

◆ reverse_iterator

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

Definition at line 65 of file ArrayBuffer.h.

◆ value_type

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

Definition at line 61 of file ArrayBuffer.h.

Constructor & Destructor Documentation

◆ ArrayBuffer() [1/5]

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

Creates an empty array buffer, without initial memory allocation.

Definition at line 68 of file ArrayBuffer.h.

◆ ArrayBuffer() [2/5]

template<class E , class INDEX = int>
ogdf::ArrayBuffer< E, INDEX >::ArrayBuffer ( INDEX  size,
bool  autogrow = true 
)
inlineexplicit

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

Definition at line 71 of file ArrayBuffer.h.

◆ ArrayBuffer() [3/5]

template<class E , class INDEX = int>
ogdf::ArrayBuffer< E, INDEX >::ArrayBuffer ( const Array< E, INDEX > &  source,
bool  autogrow = true 
)
inlineexplicit

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

Definition at line 74 of file ArrayBuffer.h.

◆ ArrayBuffer() [4/5]

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

Creates an array buffer that is a copy of buffer.

Definition at line 77 of file ArrayBuffer.h.

◆ ArrayBuffer() [5/5]

template<class E , class INDEX = int>
ogdf::ArrayBuffer< E, INDEX >::ArrayBuffer ( ArrayBuffer< E, INDEX > &&  buffer)
inline

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

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

Definition at line 83 of file ArrayBuffer.h.

Member Function Documentation

◆ begin() [1/2]

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

Returns an iterator to the first element.

Definition at line 134 of file ArrayBuffer.h.

◆ begin() [2/2]

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

Returns a const iterator to the first element.

Definition at line 137 of file ArrayBuffer.h.

◆ binarySearch() [1/2]

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

Performs a binary search for element e.

Precondition
The buffer must be sorted!
Returns
the index of the found element, and -1 if not found.

Definition at line 339 of file ArrayBuffer.h.

◆ binarySearch() [2/2]

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

Performs a binary search for element e with comparer comp.

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

Definition at line 349 of file ArrayBuffer.h.

◆ capacity()

template<class E , class INDEX = int>
INDEX ogdf::ArrayBuffer< E, INDEX >::capacity ( ) const
inline

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

Definition at line 125 of file ArrayBuffer.h.

◆ clear()

template<class E , class INDEX = int>
void ogdf::ArrayBuffer< E, INDEX >::clear ( )
inline

Clears the buffer.

Definition at line 94 of file ArrayBuffer.h.

◆ compactCopy() [1/2]

template<class E , class INDEX = int>
template<typename EE = E, typename std::enable_if<!OGDF_TRIVIALLY_COPYABLE< EE >::value, int >::type = 0>
void ogdf::ArrayBuffer< E, INDEX >::compactCopy ( Array< E, INDEX > &  A2) const
inline

Generates a compact copy holding the current elements.

Creates a copy of the ArrayBuffer and stores it into the given Array A2. A2 has exactly the neccessary size to hold all elements in the buffer.

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

Definition at line 255 of file ArrayBuffer.h.

◆ compactCopy() [2/2]

template<class E , class INDEX = int>
template<typename EE = E, typename std::enable_if< OGDF_TRIVIALLY_COPYABLE< EE >::value, int >::type = 0>
void ogdf::ArrayBuffer< E, INDEX >::compactCopy ( Array< E, INDEX > &  A2) const
inline

Generates a compact copy holding the current elements.

Creates a copy of the ArrayBuffer and stores it into the given Array A2. A2 has exactly the neccessary size to hold all elements in the buffer.

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

Definition at line 278 of file ArrayBuffer.h.

◆ compactCpycon()

template<class E , class INDEX = int>
void ogdf::ArrayBuffer< E, INDEX >::compactCpycon ( Array< E, INDEX > &  A2) const
inline

Generates a compact copy holding the current elements.

Creates a copy of the ArrayBuffer and stores it into the given Array A2. A2 has exactly the neccessary size to hold all elements in the buffer

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

Definition at line 231 of file ArrayBuffer.h.

◆ empty()

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

Returns true if the buffer is empty, false otherwise.

Definition at line 116 of file ArrayBuffer.h.

◆ end() [1/2]

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

Returns an iterator to one past the last element.

Definition at line 140 of file ArrayBuffer.h.

◆ end() [2/2]

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

Returns a const iterator to one past the last element.

Definition at line 143 of file ArrayBuffer.h.

◆ full()

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

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

Definition at line 119 of file ArrayBuffer.h.

◆ init() [1/2]

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

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

Definition at line 89 of file ArrayBuffer.h.

◆ init() [2/2]

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

Reinitializes the array, clearing it, and allocating memory for up to size elements.

Definition at line 91 of file ArrayBuffer.h.

◆ isGrowable()

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

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

Definition at line 128 of file ArrayBuffer.h.

◆ leftShift()

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

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

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

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

Parameters
indThe numbers of the components being removed.

copy the rest of the buffer

Definition at line 396 of file ArrayBuffer.h.

◆ linearSearch() [1/2]

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

Performs a linear search for element x.

Warning: linear running time! Note that the linear search runs from back to front.

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

Definition at line 293 of file ArrayBuffer.h.

◆ linearSearch() [2/2]

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

Performs a linear search for element x with comparer comp.

Warning: linear running time! Note that the linear search runs from back to front.

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

Definition at line 307 of file ArrayBuffer.h.

◆ operator!=()

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

Inequality operator.

Definition at line 213 of file ArrayBuffer.h.

◆ operator=() [1/2]

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

Assignment operator (move semantics).

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

Definition at line 182 of file ArrayBuffer.h.

◆ operator=() [2/2]

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

Assignment operator.

Definition at line 171 of file ArrayBuffer.h.

◆ operator==()

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

Equality operator.

Definition at line 192 of file ArrayBuffer.h.

◆ operator[]() [1/2]

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

Returns a reference to the element at position i.

Definition at line 164 of file ArrayBuffer.h.

◆ operator[]() [2/2]

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

Returns a reference to the element at position i.

Definition at line 158 of file ArrayBuffer.h.

◆ permute() [1/4]

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

Randomly permutes the array.

Definition at line 377 of file ArrayBuffer.h.

◆ permute() [2/4]

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

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

Definition at line 371 of file ArrayBuffer.h.

◆ permute() [3/4]

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

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

Parameters
lleft border
rright border
rngrandom number generator

Definition at line 360 of file ArrayBuffer.h.

◆ permute() [4/4]

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

Randomly permutes the array using random number generator rng.

Parameters
rngrandom number generator

Definition at line 366 of file ArrayBuffer.h.

◆ pop()

template<class E , class INDEX = int>
void ogdf::ArrayBuffer< E, INDEX >::pop ( )
inline

Removes the newest element from the buffer.

Definition at line 111 of file ArrayBuffer.h.

◆ popRet()

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

Removes the newest element from the buffer and returns it.

Definition at line 113 of file ArrayBuffer.h.

◆ push()

template<class E , class INDEX = int>
void ogdf::ArrayBuffer< E, INDEX >::push ( e)
inline

Puts a new element in the buffer.

Definition at line 102 of file ArrayBuffer.h.

◆ quicksort() [1/2]

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

Sorts buffer using Quicksort.

Definition at line 315 of file ArrayBuffer.h.

◆ quicksort() [2/2]

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

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

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

Definition at line 327 of file ArrayBuffer.h.

◆ rbegin() [1/2]

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

Returns a reverse iterator to the last element.

Definition at line 146 of file ArrayBuffer.h.

◆ rbegin() [2/2]

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

Returns a const reverse iterator to the last element.

Definition at line 149 of file ArrayBuffer.h.

◆ rend() [1/2]

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

Returns a reverse iterator to one before the first element.

Definition at line 152 of file ArrayBuffer.h.

◆ rend() [2/2]

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

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

Definition at line 155 of file ArrayBuffer.h.

◆ setCapacity()

template<class E , class INDEX = int>
void ogdf::ArrayBuffer< E, INDEX >::setCapacity ( INDEX  newCapacity)
inline

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

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

Definition at line 425 of file ArrayBuffer.h.

◆ setGrowable()

template<class E , class INDEX = int>
void ogdf::ArrayBuffer< E, INDEX >::setGrowable ( bool  _growable)
inline

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

Definition at line 131 of file ArrayBuffer.h.

◆ size()

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

Returns number of elements in the buffer.

Definition at line 122 of file ArrayBuffer.h.

◆ top() [1/2]

template<class E , class INDEX = int>
E& ogdf::ArrayBuffer< E, INDEX >::top ( )
inline

Returns the newest element of the buffer.

Definition at line 99 of file ArrayBuffer.h.

◆ top() [2/2]

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

Returns the newest element of the buffer.

Definition at line 97 of file ArrayBuffer.h.

Member Data Documentation

◆ growable

template<class E , class INDEX = int>
bool ogdf::ArrayBuffer< E, INDEX >::growable
private

Definition at line 58 of file ArrayBuffer.h.

◆ num

template<class E , class INDEX = int>
INDEX ogdf::ArrayBuffer< E, INDEX >::num
private

The number of elements in the buffer.

Definition at line 57 of file ArrayBuffer.h.


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