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). More...

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

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

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

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

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

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

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

	~SortedSequence ()
	Destructor. More...

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. More...

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

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

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

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

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

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

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

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

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

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

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

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

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

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. More...

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. More...

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. More...

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. More...

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

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. More...

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

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. More...

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>`. More...

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

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

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

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

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

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

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

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`. More...

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

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. More...

int	m_height
	current height of head/tail. More...

std::uniform_int_distribution	m_randomBits

int	m_realHeight
	actual height of head/tail arrays. More...

std::minstd_rand	m_rng
	Random number generator. More...

int	m_size
	number of elements stored in the sequence. More...

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 71 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 133 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 137 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 131 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 135 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 140 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 495 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 503 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 514 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 158 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 615 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 585 of file SortedSequence.h.

◆ begin() [1/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::const_iterator ogdf::SortedSequence< KEY, INFO, CMP >::begin

inline

Returns an iterator pointing to the first element.

Definition at line 773 of file SortedSequence.h.

◆ begin() [2/2]

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

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

Returns a const-iterator pointing to the first element.

◆ 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 183 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 192 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 279 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 201 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 210 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 705 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 764 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 174 of file SortedSequence.h.

◆ end() [1/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::const_iterator ogdf::SortedSequence< KEY, INFO, CMP >::end

inline

Returns an iterator pointing to one past the last element.

Definition at line 784 of file SortedSequence.h.

◆ end() [2/2]

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

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

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

◆ grow()

template<class KEY , class INFO , class CMP >

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

private

Definition at line 643 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 361 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 671 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 713 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 726 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 631 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 637 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 603 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 609 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 253 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 260 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 239 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 246 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 317 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 529 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 542 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 567 of file SortedSequence.h.

◆ randomHeightAndGrow()

template<class KEY , class INFO , class CMP >

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

private

Definition at line 657 of file SortedSequence.h.

◆ rbegin() [1/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::const_reverse_iterator ogdf::SortedSequence< KEY, INFO, CMP >::rbegin

inline

Returns a reverse iterator pointing to the last element.

Definition at line 796 of file SortedSequence.h.

◆ rbegin() [2/2]

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

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

Returns a const reverse iterator pointing to the last element.

◆ removeElement()

template<class KEY , class INFO , class CMP >

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

private

Definition at line 752 of file SortedSequence.h.

◆ rend() [1/2]

template<class KEY , class INFO , class CMP >

SortedSequence< KEY, INFO, CMP >::const_reverse_iterator ogdf::SortedSequence< KEY, INFO, CMP >::rend

inline

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

Definition at line 807 of file SortedSequence.h.

◆ rend() [2/2]

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

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

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

◆ reverseElements()

template<class KEY , class INFO , class CMP >

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

private

Definition at line 742 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 345 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 171 of file SortedSequence.h.

Friends And Related Function 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 72 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 74 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 73 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 75 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 352 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 354 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 355 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 359 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 356 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 358 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 353 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

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

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 Function 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

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