Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::SortedSequence< KEY, INFO, CMP > Class Template Reference

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 k1key, 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 k1key, 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...
 

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 >
 

Special modification methods

These methods must be handled with care; they are only useful in very specific scenarios.

First read their documentation carefully!

CMP m_comparer
 
int m_size
 number of elements stored in the sequence. More...
 
Elementm_dummy
 dummy element representing the head and tail of the skiplist. More...
 
int m_height
 current height of head/tail. More...
 
int m_realHeight
 actual height of head/tail arrays. More...
 
std::minstd_rand m_rng
 Random number generator. More...
 
std::uniform_int_distribution m_randomBits
 
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...
 
void initEmpty ()
 
int randomHeightAndGrow ()
 
void grow (int newHeight)
 
const Element_lookup (const KEY &key) const
 
const Element_locate (const KEY &key) const
 
void removeElement (Element *p)
 
void insertElementAfterElement (Element *p, Element *q)
 
void reverseElements (Element *p, Element *q)
 

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 65 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 487 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 496 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 508 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 607 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 577 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 777 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 180 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 189 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 270 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 198 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 207 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 699 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 765 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 171 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 792 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 636 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 355 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 665 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 722 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 k1key, or a null iterator if no such element exists.

Definition at line 623 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 k1key, or a null iterator if no such element exists.

Definition at line 629 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 594 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 600 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 244 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 250 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 232 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 238 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 308 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 520 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 533 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 559 of file SortedSequence.h.

◆ randomHeightAndGrow()

template<class KEY , class INFO , class CMP >
int ogdf::SortedSequence< KEY, INFO, CMP >::randomHeightAndGrow
private

Definition at line 651 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 807 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 751 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 822 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 739 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 338 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 168 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 67 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 69 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 68 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 70 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 345 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 347 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 348 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 352 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 349 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 351 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 346 of file SortedSequence.h.


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