Constant-time set operations. More...

#include <ogdf/basic/RegisteredSet.h>

Inheritance diagram for ogdf::RegisteredSet< Registry >:

Public Types
using	element_type = typename Registry::key_type

using	list_type = List< element_type >

using	registry_type = Registry

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

	RegisteredSet (const RegisteredSet &copy)

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

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

	RegisteredSet (RegisteredSet &&move) noexcept

list_type::const_iterator	begin () const

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

bool	contains (element_type v) const
	Returns the same as isMember() 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...

RegisteredSet &	operator= (const RegisteredSet &copy)

RegisteredSet &	operator= (RegisteredSet &&move) noexcept

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

Protected Member Functions
void	keyAdded (typename Registry::key_type v) override
	Called by watched registry after a key has been added. More...

void	keyRemoved (typename Registry::key_type v) override
	Called by watched registry just before a key is deleted. More...

void	keysCleared () override
	Called by watched registry when its clear function is called, just before things are removed. More...

void	keysCopied (int toIndex, int fromIndex) override
	Called when an entry is copied from `fromIndex` to `toIndex` in all registered arrays. More...

void	keysSwapped (int index1, int index2) override
	Called when an entry is swapped between `index1` and `index2` in all registered arrays. More...

void	registrationChanged (const Registry *old) override
	Called after reregister() changed the observed instance. More...

Private Types
using	Obs = RegisteredObserver< Registry >

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

Friends
bool	operator!= (const RegisteredSet &lhs, const RegisteredSet &rhs)

bool	operator== (const RegisteredSet &lhs, const RegisteredSet &rhs)

Additional Inherited Members
Private Member Functions inherited from ogdf::RegisteredObserver< Registry >
	RegisteredObserver ()=default
	Constructs instance of RegisteredObserver class. More...

	RegisteredObserver (const Registry *R)

const Registry *	getRegistry () const

Private Member Functions inherited from ogdf::Observer< Registry, RegisteredObserver< Registry > >
	Observer ()=default
	Constructs unregistered instance of Observer class. More...

	Observer (const Observer &copy)=delete
	If you want to copy a subclass of Observer, call the default Observer() constructor and optionally also call reregister if it makes sense. More...

	Observer (const Registry *R)

	Observer (Observer &&move)=delete
	If you want to move a subclass of Observer, call the default Observer() constructor and optionally also call reregister if it makes sense. More...

virtual	~Observer ()
	Destroys the instance, unregisters it from watched instance. More...

const Registry *	getObserved () const

Observer &	operator= (const Observer &copy)=delete

Observer &	operator= (Observer &&move)=delete

void	reregister (const Registry *obs)
	Associates observer instance with instance `obs`. More...

Detailed Description

template<class Registry>
class ogdf::RegisteredSet< Registry >

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.

See also: RegisteredArray, NodeSet

Definition at line 53 of file RegisteredSet.h.

Member Typedef Documentation

◆ element_type

template<class Registry >

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

Definition at line 58 of file RegisteredSet.h.

◆ list_type

template<class Registry >

using ogdf::RegisteredSet< Registry >::list_type = List<element_type>

Definition at line 59 of file RegisteredSet.h.

◆ Obs

template<class Registry >

using ogdf::RegisteredSet< Registry >::Obs = RegisteredObserver<Registry>

private

Definition at line 54 of file RegisteredSet.h.

◆ registry_type

template<class Registry >

using ogdf::RegisteredSet< Registry >::registry_type = Registry

Definition at line 57 of file RegisteredSet.h.

Constructor & Destructor Documentation

◆ RegisteredSet() [1/5]

template<class Registry >

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

inlineexplicit

Creates an empty set associated with registry R.

Definition at line 62 of file RegisteredSet.h.

◆ RegisteredSet() [2/5]

template<class Registry >

ogdf::RegisteredSet< Registry >::RegisteredSet ( const Registry * R )

inlineexplicit

Creates an empty set associated with registry R.

Definition at line 69 of file RegisteredSet.h.

◆ RegisteredSet() [3/5]

template<class Registry >

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

inlineexplicit

Creates an empty set associated with no registry.

Definition at line 72 of file RegisteredSet.h.

◆ RegisteredSet() [4/5]

template<class Registry >

ogdf::RegisteredSet< Registry >::RegisteredSet ( const RegisteredSet< Registry > & copy )

inline

Definition at line 74 of file RegisteredSet.h.

◆ RegisteredSet() [5/5]

template<class Registry >

ogdf::RegisteredSet< Registry >::RegisteredSet ( RegisteredSet< Registry > && move )

inlinenoexcept

Definition at line 85 of file RegisteredSet.h.

Member Function Documentation

◆ begin()

template<class Registry >

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

inline

Definition at line 183 of file RegisteredSet.h.

◆ clear()

template<class Registry >

void ogdf::RegisteredSet< Registry >::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 143 of file RegisteredSet.h.

◆ contains()

template<class Registry >

bool ogdf::RegisteredSet< Registry >::contains ( element_type v ) const

inline

Returns the same as isMember()

Definition at line 166 of file RegisteredSet.h.

◆ elements()

template<class Registry >

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

inline

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

Definition at line 172 of file RegisteredSet.h.

◆ end()

template<class Registry >

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

inline

Definition at line 185 of file RegisteredSet.h.

◆ init() [1/2]

template<class Registry >

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

inline

Reinitializes the set. Associates the set with no registry.

Definition at line 96 of file RegisteredSet.h.

◆ init() [2/2]

template<class Registry >

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

inline

Reinitializes the set. Associates the set with registry R.

Definition at line 102 of file RegisteredSet.h.

◆ insert()

template<class Registry >

void ogdf::RegisteredSet< Registry >::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 111 of file RegisteredSet.h.

◆ isMember()

template<class Registry >

bool ogdf::RegisteredSet< Registry >::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 163 of file RegisteredSet.h.

◆ keyAdded()

template<class Registry >

void ogdf::RegisteredSet< Registry >::keyAdded ( typename Registry::key_type v )

inlineoverrideprotectedvirtual

Called by watched registry after a key has been added.

Implements ogdf::RegisteredObserver< Registry >.

Definition at line 217 of file RegisteredSet.h.

◆ keyRemoved()

template<class Registry >

void ogdf::RegisteredSet< Registry >::keyRemoved ( typename Registry::key_type v )

inlineoverrideprotectedvirtual

Called by watched registry just before a key is deleted.

Implements ogdf::RegisteredObserver< Registry >.

Definition at line 215 of file RegisteredSet.h.

◆ keysCleared()

template<class Registry >

void ogdf::RegisteredSet< Registry >::keysCleared ( )

inlineoverrideprotectedvirtual

Called by watched registry when its clear function is called, just before things are removed.

Implements ogdf::RegisteredObserver< Registry >.

Definition at line 227 of file RegisteredSet.h.

◆ keysCopied()

template<class Registry >

void ogdf::RegisteredSet< Registry >::keysCopied	(	int	toIndex,
		int	fromIndex
	)

inlineoverrideprotectedvirtual

Called when an entry is copied from fromIndex to toIndex in all registered arrays.

Implements ogdf::RegisteredObserver< Registry >.

Definition at line 223 of file RegisteredSet.h.

◆ keysSwapped()

template<class Registry >

void ogdf::RegisteredSet< Registry >::keysSwapped	(	int	index1,
		int	index2
	)

inlineoverrideprotectedvirtual

Called when an entry is swapped between index1 and index2 in all registered arrays.

Implements ogdf::RegisteredObserver< Registry >.

Definition at line 219 of file RegisteredSet.h.

◆ operator()()

template<class Registry >

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

inline

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

Definition at line 169 of file RegisteredSet.h.

◆ operator=() [1/2]

template<class Registry >

RegisteredSet& ogdf::RegisteredSet< Registry >::operator= ( const RegisteredSet< Registry > & copy )

inline

Definition at line 76 of file RegisteredSet.h.

◆ operator=() [2/2]

template<class Registry >

RegisteredSet& ogdf::RegisteredSet< Registry >::operator= ( RegisteredSet< Registry > && move )

inlinenoexcept

Definition at line 87 of file RegisteredSet.h.

◆ registeredAt()

template<class Registry >

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

inline

Returns the associated registry.

Definition at line 175 of file RegisteredSet.h.

◆ registrationChanged()

template<class Registry >

void ogdf::RegisteredSet< Registry >::registrationChanged ( const Registry * old )

inlineoverrideprotectedvirtual

Called after reregister() changed the observed instance.

Reimplemented from ogdf::Observer< Registry, RegisteredObserver< Registry > >.

Definition at line 229 of file RegisteredSet.h.

◆ remove()

template<class Registry >

bool ogdf::RegisteredSet< Registry >::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 125 of file RegisteredSet.h.

◆ size()

template<class Registry >

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

inline

Returns the number of elements in this set.

This operation has constant runtime.

Definition at line 181 of file RegisteredSet.h.

Friends And Related Function Documentation

◆ operator!=

template<class Registry >

bool operator!=	(	const RegisteredSet< Registry > &	lhs,
		const RegisteredSet< Registry > &	rhs
	)

friend

Definition at line 202 of file RegisteredSet.h.

◆ operator==

template<class Registry >

bool operator==	(	const RegisteredSet< Registry > &	lhs,
		const RegisteredSet< Registry > &	rhs
	)

friend

Definition at line 187 of file RegisteredSet.h.

Member Data Documentation

◆ m_elements

template<class Registry >

list_type ogdf::RegisteredSet< Registry >::m_elements

private

The list of elements contained in this set.

Definition at line 212 of file RegisteredSet.h.

◆ m_it

template<class Registry >

RegisteredArray<Registry, ListIterator<element_type>, false> ogdf::RegisteredSet< Registry >::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 209 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

Protected Member Functions

Private Types

Private Attributes

Friends

Additional Inherited Members

Detailed Description

template<class Registry> class ogdf::RegisteredSet< Registry >

Member Typedef Documentation

◆ element_type

◆ list_type

◆ Obs

◆ registry_type

Constructor & Destructor Documentation

◆ RegisteredSet() [1/5]

◆ RegisteredSet() [2/5]

◆ RegisteredSet() [3/5]

◆ RegisteredSet() [4/5]

◆ RegisteredSet() [5/5]

Member Function Documentation

◆ begin()

◆ clear()

◆ contains()

◆ elements()

◆ end()

◆ init() [1/2]

◆ init() [2/2]

◆ insert()

◆ isMember()

◆ keyAdded()

◆ keyRemoved()

◆ keysCleared()

◆ keysCopied()

◆ keysSwapped()

◆ operator()()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ registeredAt()

◆ registrationChanged()

◆ remove()

◆ size()

Friends And Related Function Documentation

◆ operator!=

◆ operator==

Member Data Documentation

◆ m_elements

◆ m_it

Open
Graph Drawing
Framework

template<class Registry>
class ogdf::RegisteredSet< Registry >