Maintains a sequence of (key,info) pairs sorted by key. More...

#include <ogdf/basic/SortedSequence.h>

Classes
struct	Element
	Internal structure to hold the items and internal forward/backward pointers of the skiplist. More...

Public Types
using	const_iterator = SortedSequenceConstIterator< KEY, INFO, CMP >
	The const-iterator type for sorted sequences (bidirectional iterator).

using	const_reverse_iterator = SortedSequenceConstReverseIterator< KEY, INFO, CMP >
	The const reverse iterator type for sorted sequences (bidirectional iterator).

using	iterator = SortedSequenceIterator< KEY, INFO, CMP >
	The iterator type for sorted sequences (bidirectional iterator).

using	reverse_iterator = SortedSequenceReverseIterator< KEY, INFO, CMP >
	The reverse iterator type for sorted sequences (bidirectional iterator).

Public Member Functions
	SortedSequence (const CMP &comparer=CMP())
	Constructs an initially empty sorted sequence.

	SortedSequence (const SortedSequence< KEY, INFO, CMP > &S)
	Copy constructor.

	SortedSequence (SortedSequence< KEY, INFO, CMP > &&S)
	Copy constructor (move semantics).

	SortedSequence (std::initializer_list< std::pair< KEY, INFO > > initList)
	Constructs a sorted sequence containing the elements in `initList`.

	~SortedSequence ()
	Destructor.

General information and standard iterators
These methods provide basic information like the number of elements in the list, as well as iterators to the begin and end of the sequence allowing forward and backward iteration over the sequence.
int	size () const
	Returns the current size of the sequence, i.e., the number of stored elements.

bool	empty () const
	Returns true if the sequence is empty, false otherwise.

iterator	begin ()
	Returns an iterator pointing to the first element.

const_iterator	begin () const
	Returns a const-iterator pointing to the first element.

const_iterator	cbegin () const
	Returns a const-iterator pointing to the first element.

iterator	end ()
	Returns an iterator pointing to one past the last element.

const_iterator	end () const
	Returns a const-iterator pointing to one past the last element.

const_iterator	cend () const
	Returns a const-iterator pointing to one past the last element.

reverse_iterator	rbegin ()
	Returns a reverse iterator pointing to the last element.

const_reverse_iterator	rbegin () const
	Returns a const reverse iterator pointing to the last element.

const_reverse_iterator	crbegin () const
	Returns a const reverse iterator pointing to the last element.

reverse_iterator	rend ()
	Returns a reverse iterator pointing to one before the first element.

const_reverse_iterator	rend () const
	Returns a const reverse iterator pointing to one before the first element.

const_reverse_iterator	crend () const
	Returns a const reverse iterator pointing to one before the first element.

Lookup operations
These methods can be used to find elements by key. They return iterators pointing to the respective element in the sequence.
iterator	lookup (const KEY &key)
	Returns an iterator to the element with key `key`, or a null iterator if no such element exists.

const_iterator	lookup (const KEY &key) const
	Returns a const-iterator to the element with key `key`, or a null iterator if no such element exists.

iterator	locate (const KEY &key)
	Returns an iterator to the element < k1, i1 > such that k1 is minimal with k1 ≥ `key`, or a null iterator if no such element exists.

const_iterator	locate (const KEY &key) const
	Returns a const-iterator to the element < k1, i1 > such that k1 is minimal with k1 ≥ `key`, or a null iterator if no such element exists.

iterator	minItem ()
	Returns an iterator to the element with minimal key if the sequence is not empty, an invalid iterator otherwise.

const_iterator	minItem () const
	Returns a const-iterator to the element with minimal key if the sequence is not empty, an invalid const-iterator otherwise.

reverse_iterator	maxItem ()
	Returns a reverse iterator to the element with maximal key if the sequence is not empty, an invalid reverse iterator otherwise.

const_reverse_iterator	maxItem () const
	Returns a const reverse iterator to the element with maximal key if the sequence is not empty, an invalid const reverse iterator otherwise.

Insertion and deletion
These method provide basic modification methods, like inserting new elements or removing elements from the sequence.
iterator	insert (const KEY &key, const INFO &info)
	Updates information for `key` if contained in sequence, or adds a new element <`key`, `info>`.

void	del (const KEY &key)
	Removes the element with key `key` (if such an element exists).

void	delItem (iterator it)
	Removes the element to which `it` points from the sequence.

void	clear ()
	Removes all elements from the sorted sequence.

Operators
The following operators are overloeded for sorted sequences.
SortedSequence< KEY, INFO, CMP > &	operator= (const SortedSequence< KEY, INFO, CMP > &S)
	Assignment operator.

SortedSequence< KEY, INFO, CMP > &	operator= (SortedSequence< KEY, INFO, CMP > &&S)
	Assignment operator (move semantics).

bool	operator== (const SortedSequence< KEY, INFO, CMP > &S)
	Returns true if the keys stored in this sequence equal the keys in `S`, false otherwise.

bool	operator!= (const SortedSequence< KEY, INFO, CMP > &S)
	Returns false if the keys stored in this sequence equal the keys in `S`, true otherwise.

Special modification methods
These methods must be handled with care; they are only useful in very specific scenarios. First read their documentation carefully!
iterator	insertAfter (iterator it, const KEY &key, const INFO &info)
	Adds a new element <`key`, `info>` after element `it`.

void	reverseItems (iterator itBegin, iterator itEnd)
	Reverses the items in the subsequence from `itBegin` to `itEnd` (inclusive).

Private Member Functions
const Element *	_locate (const KEY &key) const

const Element *	_lookup (const KEY &key) const

void	grow (int newHeight)

void	initEmpty ()

void	insertElementAfterElement (Element p, Element q)

int	randomHeightAndGrow ()

void	removeElement (Element *p)

void	reverseElements (Element p, Element q)

Private Attributes
CMP	m_comparer

Element *	m_dummy
	dummy element representing the head and tail of the skiplist.

int	m_height
	current height of head/tail.

std::uniform_int_distribution	m_randomBits

int	m_realHeight
	actual height of head/tail arrays.

std::minstd_rand	m_rng
	Random number generator.

int	m_size
	number of elements stored in the sequence.

Friends
class	SortedSequenceIteratorBase< KEY, INFO, CMP, false, false >

class	SortedSequenceIteratorBase< KEY, INFO, CMP, false, true >

class	SortedSequenceIteratorBase< KEY, INFO, CMP, true, false >

class	SortedSequenceIteratorBase< KEY, INFO, CMP, true, true >

Detailed Description

template<class KEY, class INFO, class CMP = StdComparer<KEY>>
class ogdf::SortedSequence< KEY, INFO, CMP >

Maintains a sequence of (key,info) pairs sorted by key.

Sorted sequences a implemented by doubly linked skiplists. Operations lookup, locate, insert, del, delItem take expected time O(log n), where n is the current size of the sequence.

Definition at line 66 of file SortedSequence.h.

Member Typedef Documentation

◆ const_iterator

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

using ogdf::SortedSequence< KEY, INFO, CMP >::const_iterator = SortedSequenceConstIterator<KEY, INFO, CMP>

The const-iterator type for sorted sequences (bidirectional iterator).

Definition at line 128 of file SortedSequence.h.

◆ const_reverse_iterator

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

using ogdf::SortedSequence< KEY, INFO, CMP >::const_reverse_iterator = SortedSequenceConstReverseIterator<KEY, INFO, CMP>

The const reverse iterator type for sorted sequences (bidirectional iterator).

Definition at line 132 of file SortedSequence.h.

◆ iterator

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

using ogdf::SortedSequence< KEY, INFO, CMP >::iterator = SortedSequenceIterator<KEY, INFO, CMP>

The iterator type for sorted sequences (bidirectional iterator).

Definition at line 126 of file SortedSequence.h.

◆ reverse_iterator

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

using ogdf::SortedSequence< KEY, INFO, CMP >::reverse_iterator = SortedSequenceReverseIterator<KEY, INFO, CMP>

The reverse iterator type for sorted sequences (bidirectional iterator).

Definition at line 130 of file SortedSequence.h.

Constructor & Destructor Documentation

◆ SortedSequence() [1/4]

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

ogdf::SortedSequence< KEY, INFO, CMP >::SortedSequence ( const CMP & comparer = CMP() )

inline

Constructs an initially empty sorted sequence.

Definition at line 135 of file SortedSequence.h.

◆ SortedSequence() [2/4]

template<class KEY , class INFO , class CMP >

ogdf::SortedSequence< KEY, INFO, CMP >::SortedSequence ( std::initializer_list< std::pair< KEY, INFO > > initList )

Constructs a sorted sequence containing the elements in initList.

Definition at line 490 of file SortedSequence.h.

◆ SortedSequence() [3/4]

template<class KEY , class INFO , class CMP >

ogdf::SortedSequence< KEY, INFO, CMP >::SortedSequence ( const SortedSequence< KEY, INFO, CMP > & S )

Copy constructor.

Definition at line 498 of file SortedSequence.h.

◆ SortedSequence() [4/4]

template<class KEY , class INFO , class CMP >

ogdf::SortedSequence< KEY, INFO, CMP >::SortedSequence ( SortedSequence< KEY, INFO, CMP > && S )

Copy constructor (move semantics).

The sequence S is empty afterwards.

Definition at line 509 of file SortedSequence.h.

◆ ~SortedSequence()

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

ogdf::SortedSequence< KEY, INFO, CMP >::~SortedSequence ( )

inline

Destructor.

Definition at line 153 of file SortedSequence.h.

Member Function Documentation

◆ _locate()

template<class KEY , class INFO , class CMP >

const SortedSequence< KEY, INFO, CMP >::Element * ogdf::SortedSequence< KEY, INFO, CMP >::_locate ( const KEY & key ) const

private

Definition at line 610 of file SortedSequence.h.

◆ _lookup()

template<class KEY , class INFO , class CMP >

const SortedSequence< KEY, INFO, CMP >::Element * ogdf::SortedSequence< KEY, INFO, CMP >::_lookup ( const KEY & key ) const

private

Definition at line 580 of file SortedSequence.h.

◆ begin() [1/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::iterator ogdf::SortedSequence< KEY, INFO, CMP >::begin ( )

inline

Returns an iterator pointing to the first element.

Definition at line 768 of file SortedSequence.h.

◆ begin() [2/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::const_iterator ogdf::SortedSequence< KEY, INFO, CMP >::begin ( ) const

inline

Returns a const-iterator pointing to the first element.

Definition at line 774 of file SortedSequence.h.

◆ cbegin()

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

const_iterator ogdf::SortedSequence< KEY, INFO, CMP >::cbegin ( ) const

inline

Returns a const-iterator pointing to the first element.

Definition at line 178 of file SortedSequence.h.

◆ cend()

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

const_iterator ogdf::SortedSequence< KEY, INFO, CMP >::cend ( ) const

inline

Returns a const-iterator pointing to one past the last element.

Definition at line 187 of file SortedSequence.h.

◆ clear()

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

void ogdf::SortedSequence< KEY, INFO, CMP >::clear ( )

inline

Removes all elements from the sorted sequence.

Definition at line 274 of file SortedSequence.h.

◆ crbegin()

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

const_reverse_iterator ogdf::SortedSequence< KEY, INFO, CMP >::crbegin ( ) const

inline

Returns a const reverse iterator pointing to the last element.

Definition at line 196 of file SortedSequence.h.

◆ crend()

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

const_reverse_iterator ogdf::SortedSequence< KEY, INFO, CMP >::crend ( ) const

inline

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

Definition at line 205 of file SortedSequence.h.

◆ del()

template<class KEY , class INFO , class CMP >

void ogdf::SortedSequence< KEY, INFO, CMP >::del ( const KEY & key )

Removes the element with key key (if such an element exists).

Definition at line 700 of file SortedSequence.h.

◆ delItem()

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

void ogdf::SortedSequence< KEY, INFO, CMP >::delItem ( iterator it )

Removes the element to which it points from the sequence.

Definition at line 759 of file SortedSequence.h.

◆ empty()

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

bool ogdf::SortedSequence< KEY, INFO, CMP >::empty ( ) const

inline

Returns true if the sequence is empty, false otherwise.

Definition at line 169 of file SortedSequence.h.

◆ end() [1/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::iterator ogdf::SortedSequence< KEY, INFO, CMP >::end ( )

inline

Returns an iterator pointing to one past the last element.

Definition at line 779 of file SortedSequence.h.

◆ end() [2/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::const_iterator ogdf::SortedSequence< KEY, INFO, CMP >::end ( ) const

inline

Returns a const-iterator pointing to one past the last element.

Definition at line 785 of file SortedSequence.h.

◆ grow()

template<class KEY , class INFO , class CMP >

void ogdf::SortedSequence< KEY, INFO, CMP >::grow ( int newHeight )

private

Definition at line 638 of file SortedSequence.h.

◆ initEmpty()

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

void ogdf::SortedSequence< KEY, INFO, CMP >::initEmpty ( )

inlineprivate

Definition at line 356 of file SortedSequence.h.

◆ insert()

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::iterator ogdf::SortedSequence< KEY, INFO, CMP >::insert	(	const KEY &	key,
		const INFO &	info
	)

Updates information for key if contained in sequence, or adds a new element <key, info>.

Definition at line 666 of file SortedSequence.h.

◆ insertAfter()

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::iterator ogdf::SortedSequence< KEY, INFO, CMP >::insertAfter	(	iterator	it,
		const KEY &	key,
		const INFO &	info
	)

Adds a new element <key, info> after element it.

Precondition: it points to an element in the sequence that shall appear before <key, info> in the sorted sequence, and its current successor itSucc shall appear after <key, info>, i.e., it's key is smaller than key and itSucc's key is greater than key.

Definition at line 708 of file SortedSequence.h.

◆ insertElementAfterElement()

template<class KEY , class INFO , class CMP >

void ogdf::SortedSequence< KEY, INFO, CMP >::insertElementAfterElement	(	Element *	p,
		Element *	q
	)

private

Definition at line 721 of file SortedSequence.h.

◆ locate() [1/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::iterator ogdf::SortedSequence< KEY, INFO, CMP >::locate ( const KEY & key )

Returns an iterator to the element < k1, i1 > such that k1 is minimal with k1 ≥ key, or a null iterator if no such element exists.

Definition at line 626 of file SortedSequence.h.

◆ locate() [2/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::const_iterator ogdf::SortedSequence< KEY, INFO, CMP >::locate ( const KEY & key ) const

Returns a const-iterator to the element < k1, i1 > such that k1 is minimal with k1 ≥ key, or a null iterator if no such element exists.

Definition at line 632 of file SortedSequence.h.

◆ lookup() [1/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::iterator ogdf::SortedSequence< KEY, INFO, CMP >::lookup ( const KEY & key )

Returns an iterator to the element with key key, or a null iterator if no such element exists.

Definition at line 598 of file SortedSequence.h.

◆ lookup() [2/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::const_iterator ogdf::SortedSequence< KEY, INFO, CMP >::lookup ( const KEY & key ) const

Returns a const-iterator to the element with key key, or a null iterator if no such element exists.

Definition at line 604 of file SortedSequence.h.

◆ maxItem() [1/2]

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

reverse_iterator ogdf::SortedSequence< KEY, INFO, CMP >::maxItem ( )

inline

Returns a reverse iterator to the element with maximal key if the sequence is not empty, an invalid reverse iterator otherwise.

Calling this method is equivalent to calling rbegin(), but has a more intuitive name.

Definition at line 248 of file SortedSequence.h.

◆ maxItem() [2/2]

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

const_reverse_iterator ogdf::SortedSequence< KEY, INFO, CMP >::maxItem ( ) const

inline

Returns a const reverse iterator to the element with maximal key if the sequence is not empty, an invalid const reverse iterator otherwise.

Calling this method is equivalent to calling rbegin(), but has a more intuitive name.

Definition at line 255 of file SortedSequence.h.

◆ minItem() [1/2]

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

iterator ogdf::SortedSequence< KEY, INFO, CMP >::minItem ( )

inline

Returns an iterator to the element with minimal key if the sequence is not empty, an invalid iterator otherwise.

Calling this method is equivalent to calling begin(), but has a more intuitive name.

Definition at line 234 of file SortedSequence.h.

◆ minItem() [2/2]

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

const_iterator ogdf::SortedSequence< KEY, INFO, CMP >::minItem ( ) const

inline

Returns a const-iterator to the element with minimal key if the sequence is not empty, an invalid const-iterator otherwise.

Calling this method is equivalent to calling begin(), but has a more intuitive name.

Definition at line 241 of file SortedSequence.h.

◆ operator!=()

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

bool ogdf::SortedSequence< KEY, INFO, CMP >::operator!= ( const SortedSequence< KEY, INFO, CMP > & S )

inline

Returns false if the keys stored in this sequence equal the keys in S, true otherwise.

Uses the given comparer object to compare keys.

Definition at line 312 of file SortedSequence.h.

◆ operator=() [1/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP > & ogdf::SortedSequence< KEY, INFO, CMP >::operator= ( const SortedSequence< KEY, INFO, CMP > & S )

Assignment operator.

Definition at line 524 of file SortedSequence.h.

◆ operator=() [2/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP > & ogdf::SortedSequence< KEY, INFO, CMP >::operator= ( SortedSequence< KEY, INFO, CMP > && S )

Assignment operator (move semantics).

The sequence S is empty afterwards.

Definition at line 537 of file SortedSequence.h.

◆ operator==()

template<class KEY , class INFO , class CMP >

bool ogdf::SortedSequence< KEY, INFO, CMP >::operator== ( const SortedSequence< KEY, INFO, CMP > & S )

Returns true if the keys stored in this sequence equal the keys in S, false otherwise.

Uses the given comparer object to compare keys.

Definition at line 562 of file SortedSequence.h.

◆ randomHeightAndGrow()

template<class KEY , class INFO , class CMP >

int ogdf::SortedSequence< KEY, INFO, CMP >::randomHeightAndGrow ( )

private

Definition at line 652 of file SortedSequence.h.

◆ rbegin() [1/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::reverse_iterator ogdf::SortedSequence< KEY, INFO, CMP >::rbegin ( )

inline

Returns a reverse iterator pointing to the last element.

Definition at line 791 of file SortedSequence.h.

◆ rbegin() [2/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::const_reverse_iterator ogdf::SortedSequence< KEY, INFO, CMP >::rbegin ( ) const

inline

Returns a const reverse iterator pointing to the last element.

Definition at line 797 of file SortedSequence.h.

◆ removeElement()

template<class KEY , class INFO , class CMP >

void ogdf::SortedSequence< KEY, INFO, CMP >::removeElement ( Element * p )

private

Definition at line 747 of file SortedSequence.h.

◆ rend() [1/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::reverse_iterator ogdf::SortedSequence< KEY, INFO, CMP >::rend ( )

inline

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

Definition at line 802 of file SortedSequence.h.

◆ rend() [2/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::const_reverse_iterator ogdf::SortedSequence< KEY, INFO, CMP >::rend ( ) const

inline

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

Definition at line 808 of file SortedSequence.h.

◆ reverseElements()

template<class KEY , class INFO , class CMP >

void ogdf::SortedSequence< KEY, INFO, CMP >::reverseElements	(	Element *	p,
		Element *	q
	)

private

Definition at line 737 of file SortedSequence.h.

◆ reverseItems()

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

void ogdf::SortedSequence< KEY, INFO, CMP >::reverseItems	(	iterator	itBegin,
		iterator	itEnd
	)

inline

Reverses the items in the subsequence from itBegin to itEnd (inclusive).

Precondition: itBegin appears before itEnd in the sequence.

Warning: Usually, you do not need this method as the sequence is always sorted. It only makes sense if you use a special compare function that changes the underlying linear ordering, and you have to adjust the sorting manually. Do not use this method unless you know exactly what you are doing! After applying this method the subsequence should be ordered correctly according to the compare function.

Definition at line 340 of file SortedSequence.h.

◆ size()

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

int ogdf::SortedSequence< KEY, INFO, CMP >::size ( ) const

inline

Returns the current size of the sequence, i.e., the number of stored elements.

Definition at line 166 of file SortedSequence.h.

Friends And Related Symbol Documentation

◆ SortedSequenceIteratorBase< KEY, INFO, CMP, false, false >

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

friend class SortedSequenceIteratorBase< KEY, INFO, CMP, false, false >

friend

Definition at line 808 of file SortedSequence.h.

◆ SortedSequenceIteratorBase< KEY, INFO, CMP, false, true >

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

friend class SortedSequenceIteratorBase< KEY, INFO, CMP, false, true >

friend

Definition at line 808 of file SortedSequence.h.

◆ SortedSequenceIteratorBase< KEY, INFO, CMP, true, false >

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

friend class SortedSequenceIteratorBase< KEY, INFO, CMP, true, false >

friend

Definition at line 808 of file SortedSequence.h.

◆ SortedSequenceIteratorBase< KEY, INFO, CMP, true, true >

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

friend class SortedSequenceIteratorBase< KEY, INFO, CMP, true, true >

friend

Definition at line 808 of file SortedSequence.h.

Member Data Documentation

◆ m_comparer

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

CMP ogdf::SortedSequence< KEY, INFO, CMP >::m_comparer

private

Definition at line 347 of file SortedSequence.h.

◆ m_dummy

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

Element* ogdf::SortedSequence< KEY, INFO, CMP >::m_dummy

private

dummy element representing the head and tail of the skiplist.

Definition at line 349 of file SortedSequence.h.

◆ m_height

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

int ogdf::SortedSequence< KEY, INFO, CMP >::m_height

private

current height of head/tail.

Definition at line 350 of file SortedSequence.h.

◆ m_randomBits

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

std::uniform_int_distribution ogdf::SortedSequence< KEY, INFO, CMP >::m_randomBits

private

Definition at line 354 of file SortedSequence.h.

◆ m_realHeight

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

int ogdf::SortedSequence< KEY, INFO, CMP >::m_realHeight

private

actual height of head/tail arrays.

Definition at line 351 of file SortedSequence.h.

◆ m_rng

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

std::minstd_rand ogdf::SortedSequence< KEY, INFO, CMP >::m_rng

private

Random number generator.

Definition at line 353 of file SortedSequence.h.

◆ m_size

template<class KEY , class INFO , class CMP = StdComparer<KEY>>

int ogdf::SortedSequence< KEY, INFO, CMP >::m_size

private

number of elements stored in the sequence.

Definition at line 348 of file SortedSequence.h.

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

include/ogdf/basic/SortedSequence.h

OpenGraph DrawingFramework

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_reverse_iterator

◆ iterator

◆ reverse_iterator

Constructor & Destructor Documentation

◆ SortedSequence() [1/4]

◆ SortedSequence() [2/4]

◆ SortedSequence() [3/4]

◆ SortedSequence() [4/4]

◆ ~SortedSequence()

Member Function Documentation

◆ _locate()

◆ _lookup()

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ clear()

◆ crbegin()

◆ crend()

◆ del()

◆ delItem()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ grow()

◆ initEmpty()

◆ insert()

◆ insertAfter()

◆ insertElementAfterElement()

◆ locate() [1/2]

◆ locate() [2/2]

◆ lookup() [1/2]

◆ lookup() [2/2]

◆ maxItem() [1/2]

◆ maxItem() [2/2]

◆ minItem() [1/2]

◆ minItem() [2/2]

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ randomHeightAndGrow()

◆ rbegin() [1/2]

◆ rbegin() [2/2]

◆ removeElement()

◆ rend() [1/2]

◆ rend() [2/2]

◆ reverseElements()

◆ reverseItems()

◆ size()

Friends And Related Symbol Documentation

◆ SortedSequenceIteratorBase< KEY, INFO, CMP, false, false >

◆ SortedSequenceIteratorBase< KEY, INFO, CMP, false, true >

◆ SortedSequenceIteratorBase< KEY, INFO, CMP, true, false >

◆ SortedSequenceIteratorBase< KEY, INFO, CMP, true, true >

Member Data Documentation

◆ m_comparer

◆ m_dummy

◆ m_height

◆ m_randomBits

◆ m_realHeight

◆ m_rng

◆ m_size

Open
Graph Drawing
Framework