Constant-time set operations. More...

#include <ogdf/basic/RegisteredSet.h>

Public Types
using	element_type = typename Registry::key_type

using	list_type = typename std::conditional< SupportFastSizeQuery, List< element_type >, ListPure< element_type > >::type

Public Member Functions
	RegisteredSet ()
	Creates an empty set associated with no registry. More...

template<bool OtherSupportsFastSizeQuery>
	RegisteredSet (const RegisteredSet< Registry, OtherSupportsFastSizeQuery > &other)
	Copy constructor. More...

	RegisteredSet (const Registry &R)
	Creates an empty set associated with registry `R`. More...

list_type::const_iterator	begin () const

void	clear ()
	Removes all elements from this set. More...

const list_type &	elements () const
	Returns a reference to the list of elements contained in this set. More...

list_type::const_iterator	end () const

void	init ()
	Reinitializes the set. Associates the set with no registry. More...

void	init (const Registry &R)
	Reinitializes the set. Associates the set with registry `R`. More...

void	insert (element_type v)
	Inserts element `v` into this set. More...

bool	isMember (element_type v) const
	Returns `true` iff element `v` is contained in this set. More...

bool	operator() (element_type v) const
	Returns the same as isMember() to use an RegisteredSet instance as filter function. More...

template<bool OtherSupportsFastSizeQuery>
RegisteredSet &	operator= (const RegisteredSet< Registry, OtherSupportsFastSizeQuery > &other)
	Assignment operator. More...

const Registry *	registeredAt () const
	Returns the associated registry. More...

bool	remove (element_type v)
	Removes element `v` from this set and return `true` iff `v` was previously present. More...

int	size () const
	Returns the number of elements in this set. More...

Private Attributes
list_type	m_elements
	The list of elements contained in this set. More...

RegisteredArray< Registry, ListIterator< element_type >, false >	m_it
	m_it[v] contains the list iterator pointing to v if v is contained in this set, or an invalid list iterator otherwise. More...

Detailed Description

template<class Registry, bool SupportFastSizeQuery = true>
class ogdf::RegisteredSet< Registry, SupportFastSizeQuery >

Constant-time set operations.

Maintains a subset of indexed keys managed by a registry.

Provides efficient operations for testing membership, iteration, insertion, and deletion of elements, as well as clearing the set.

Template Parameters

Registry	The class which manages the registered keys. Must provide the functions defined in class RegistryBase.
SupportFastSizeQuery	Whether this set supports querying its size in constant instead of linear time (in the size).

See also: RegisteredArray, NodeSet

Definition at line 55 of file RegisteredSet.h.

Member Typedef Documentation

◆ element_type

template<class Registry , bool SupportFastSizeQuery = true>

using ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::element_type = typename Registry::key_type

Definition at line 57 of file RegisteredSet.h.

◆ list_type

template<class Registry , bool SupportFastSizeQuery = true>

using ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::list_type = typename std::conditional<SupportFastSizeQuery, List<element_type>, ListPure<element_type> >::type

Definition at line 59 of file RegisteredSet.h.

Constructor & Destructor Documentation

◆ RegisteredSet() [1/3]

template<class Registry , bool SupportFastSizeQuery = true>

ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::RegisteredSet ( const Registry & R )

inlineexplicit

Creates an empty set associated with registry R.

Definition at line 62 of file RegisteredSet.h.

◆ RegisteredSet() [2/3]

template<class Registry , bool SupportFastSizeQuery = true>

ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::RegisteredSet ( )

inlineexplicit

Creates an empty set associated with no registry.

Definition at line 65 of file RegisteredSet.h.

◆ RegisteredSet() [3/3]

template<class Registry , bool SupportFastSizeQuery = true>

template<bool OtherSupportsFastSizeQuery>

ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::RegisteredSet ( const RegisteredSet< Registry, OtherSupportsFastSizeQuery > & other )

inlineexplicit

Copy constructor.

Definition at line 161 of file RegisteredSet.h.

Member Function Documentation

◆ begin()

template<class Registry , bool SupportFastSizeQuery = true>

list_type::const_iterator ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::begin ( ) const

inline

Definition at line 155 of file RegisteredSet.h.

◆ clear()

template<class Registry , bool SupportFastSizeQuery = true>

void ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::clear ( )

inline

Removes all elements from this set.

After this operation, this set is empty and still associated with the same registry. The runtime of this operation is linear in the size(). Implementation Detail: If less than 10% of all elements are part of this set, they will be individually cleared. Otherwise, std::vector::assign(...) will be used to clear all values.

Definition at line 118 of file RegisteredSet.h.

◆ elements()

template<class Registry , bool SupportFastSizeQuery = true>

const list_type& ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::elements ( ) const

inline

Returns a reference to the list of elements contained in this set.

Definition at line 144 of file RegisteredSet.h.

◆ end()

template<class Registry , bool SupportFastSizeQuery = true>

list_type::const_iterator ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::end ( ) const

inline

Definition at line 157 of file RegisteredSet.h.

◆ init() [1/2]

template<class Registry , bool SupportFastSizeQuery = true>

void ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::init ( )

inline

Reinitializes the set. Associates the set with no registry.

Definition at line 68 of file RegisteredSet.h.

◆ init() [2/2]

template<class Registry , bool SupportFastSizeQuery = true>

void ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::init ( const Registry & R )

inline

Reinitializes the set. Associates the set with registry R.

Definition at line 74 of file RegisteredSet.h.

◆ insert()

template<class Registry , bool SupportFastSizeQuery = true>

void ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::insert ( element_type v )

inline

Inserts element v into this set.

This operation has constant runtime. If the element is already contained in this set, nothing happens.

Precondition: v is an element in the associated registry.

Definition at line 86 of file RegisteredSet.h.

◆ isMember()

template<class Registry , bool SupportFastSizeQuery = true>

bool ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::isMember ( element_type v ) const

inline

Returns true iff element v is contained in this set.

This operation has constant runtime.

Precondition: v is an element in the associated registry.

Definition at line 138 of file RegisteredSet.h.

◆ operator()()

template<class Registry , bool SupportFastSizeQuery = true>

bool ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::operator() ( element_type v ) const

inline

Returns the same as isMember() to use an RegisteredSet instance as filter function.

Definition at line 141 of file RegisteredSet.h.

◆ operator=()

template<class Registry , bool SupportFastSizeQuery = true>

template<bool OtherSupportsFastSizeQuery>

RegisteredSet& ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::operator= ( const RegisteredSet< Registry, OtherSupportsFastSizeQuery > & other )

inline

Assignment operator.

Definition at line 167 of file RegisteredSet.h.

◆ registeredAt()

template<class Registry , bool SupportFastSizeQuery = true>

const Registry* ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::registeredAt ( ) const

inline

Returns the associated registry.

Definition at line 147 of file RegisteredSet.h.

◆ remove()

template<class Registry , bool SupportFastSizeQuery = true>

bool ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::remove ( element_type v )

inline

Removes element v from this set and return true iff v was previously present.

This operation has constant runtime. If the element is not contained in this set, nothing happens and false is returned.

Precondition: v is an element in the associated registry.

Definition at line 100 of file RegisteredSet.h.

◆ size()

template<class Registry , bool SupportFastSizeQuery = true>

int ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::size ( ) const

inline

Returns the number of elements in this set.

This operation has either linear or constant runtime, depending on SupportFastSizeQuery.

Definition at line 153 of file RegisteredSet.h.

Member Data Documentation

◆ m_elements

template<class Registry , bool SupportFastSizeQuery = true>

list_type ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::m_elements

private

The list of elements contained in this set.

Definition at line 181 of file RegisteredSet.h.

◆ m_it

template<class Registry , bool SupportFastSizeQuery = true>

RegisteredArray<Registry, ListIterator<element_type>, false> ogdf::RegisteredSet< Registry, SupportFastSizeQuery >::m_it

private

m_it[v] contains the list iterator pointing to v if v is contained in this set, or an invalid list iterator otherwise.

Definition at line 178 of file RegisteredSet.h.

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

include/ogdf/basic/RegisteredSet.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Private Attributes

Detailed Description

template<class Registry, bool SupportFastSizeQuery = true> class ogdf::RegisteredSet< Registry, SupportFastSizeQuery >

Member Typedef Documentation

◆ element_type

◆ list_type

Constructor & Destructor Documentation

◆ RegisteredSet() [1/3]

◆ RegisteredSet() [2/3]

◆ RegisteredSet() [3/3]

Member Function Documentation

◆ begin()

◆ clear()

◆ elements()

◆ end()

◆ init() [1/2]

◆ init() [2/2]

◆ insert()

◆ isMember()

◆ operator()()

◆ operator=()

◆ registeredAt()

◆ remove()

◆ size()

Member Data Documentation

◆ m_elements

◆ m_it

Open
Graph Drawing
Framework

template<class Registry, bool SupportFastSizeQuery = true>
class ogdf::RegisteredSet< Registry, SupportFastSizeQuery >