List which can be reversed in $\mathcal{O}(1)$ . More...

#include <JETSCAPE/blob/main/external_packages/gtl/include/GTL/symlist.h>

Collaboration diagram for symlist< T >:

Public Types
typedef symlist_iterator< T, T & >	iterator

typedef symlist_iterator< T, const T & >	const_iterator

Public Member Functions
	symlist ()
	Creates empty symlist.

	symlist (const symlist< T > &li)
	Makes the created list a copy of `li`.

symlist< T > &	operator= (const symlist< T > &li)
	Assignes `li` to this list.

	~symlist ()
	Destructor.

bool	empty () const
	Checks whether list is empty.

T &	front ()
	First element in list.

T &	back ()
	Last element in list.

iterator	begin ()
	Start iteration through elements of list.

iterator	end ()
	End of iteration through elements of list.

const_iterator	begin () const
	Start iteration through elements of list.

const_iterator	end () const
	End of iteration through elements of list.

iterator	rbegin ()
	Start iteration through element of list in reverse order.

iterator	rend ()
	End of iteration through elements of list in reverse order.

const_iterator	rbegin () const
	Start iteration through element of list in reverse order.

const_iterator	rend () const
	End of iteration through elements of list in reverse order.

iterator	insert (iterator pos, const T &data)
	Inserts `data` before `pos` in list.

void	splice (iterator pos, iterator it)
	Inserts the element `it` points to before `pos` into this list.

void	splice (iterator pos, iterator it, iterator end)
	Inserts the elements `[it,end)` refers to before `pos` into this list.

iterator	erase (iterator pos)
	Deletes element at position `pos` from list.

iterator	erase (iterator it, iterator end)
	Deletes the elements `[it, end)` from list.

void	attach_sublist (iterator, iterator)

void	detach_sublist ()

void	reverse ()
	Change the direction of list.

Private Attributes
symnode< T > *	link

iterator	_prev

iterator	_next

Detailed Description

template<class T>
class symlist< T >

List which can be reversed in $\mathcal{O}(1)$ .

The problem with the STL class list - as with most doubly linked lists – is that isn't possible to turn it in constant time, because each entry in the list contains next and prev pointer and turning the list means to switch these two in each element in the list. Another point is the splice operation in STL lists, which is constant time, but for the same reason as mentioned above it is not possible to splice a list in reverse order into another in constant time.

The problems arise from the fact that each element "knows" what its next and previous elements are. An element in a symlist only knows what its neighbors are, what is next and what previous depends on the direction of iteration. This of course imposes some overhead in iteration (one if-statement) but allows reversion and a splice in reversed order in constant time.

Definition at line 209 of file symlist.h.

View newest version in sPHENIX GitHub at line 209 of file symlist.h

Member Typedef Documentation

template<class T>

typedef symlist_iterator<T, const T&> symlist< T >::const_iterator

Definition at line 220 of file symlist.h.

View newest version in sPHENIX GitHub at line 220 of file symlist.h

template<class T>

typedef symlist_iterator<T, T&> symlist< T >::iterator

Definition at line 215 of file symlist.h.

View newest version in sPHENIX GitHub at line 215 of file symlist.h

Constructor & Destructor Documentation

template<class T>

symlist< T >::symlist ( )

inline

Creates empty symlist.

Definition at line 225 of file symlist.h.

View newest version in sPHENIX GitHub at line 225 of file symlist.h

template<class T>

symlist< T >::symlist ( const symlist< T > & li )

Makes the created list a copy of li.

Parameters

li symlist.

Definition at line 487 of file symlist.h.

View newest version in sPHENIX GitHub at line 487 of file symlist.h

References symnode< T >::adj, symlist< T >::begin(), Acts::UnitConstants::e, end, symlist< T >::end(), and it.

Here is the call graph for this function:

template<class T >

symlist< T >::~symlist ( )

Destructor.

Definition at line 504 of file symlist.h.

View newest version in sPHENIX GitHub at line 504 of file symlist.h

References parse_cmake_options::begin, and end.

Member Function Documentation

template<class T >

void symlist< T >::attach_sublist	(	iterator	it,
		iterator	end
	)

Definition at line 672 of file symlist.h.

View newest version in sPHENIX GitHub at line 672 of file symlist.h

References symlist_iterator< T, Ref >::act, symnode< T >::adj, assert, end, it, symlist_iterator< T, Ref >::next(), and symlist_iterator< T, Ref >::prev().

Referenced by pq_tree::reduce().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T>

T& symlist< T >::back ( void )

inline

Last element in list.

Assumes that list ins't empty.

Returns: last element

Definition at line 285 of file symlist.h.

View newest version in sPHENIX GitHub at line 285 of file symlist.h

Referenced by pq_tree::integrity_check(), q_node::merge(), pq_tree::P4(), pq_tree::P5(), pq_tree::P6(), q_node::pertinent(), pq_tree::Q1(), pq_tree::reduce(), and pq_tree::reset().

Here is the caller graph for this function:

template<class T>

iterator symlist< T >::begin ( void )

inline

Start iteration through elements of list.

Returns: start iterator

Definition at line 295 of file symlist.h.

View newest version in sPHENIX GitHub at line 295 of file symlist.h

Referenced by pq_tree::blocked_in_subtree(), planarity::case_A(), planarity::case_B(), planarity::case_D(), p_node::clear(), pq_tree::dfs(), planarity::examine_obstruction(), pq_tree::integrity_check(), planarity::mark_all_neighbors_of_leaves(), operator<<(), planar_embedding::operator=(), symlist< T >::operator=(), pq_tree::P1(), pq_tree::P3(), pq_tree::P4(), pq_tree::P5(), pq_tree::P6(), p_node::p_node(), pq_tree::Q2(), pq_tree::reduce(), planarity::run_on_biconnected(), planarity::search_empty_leaf(), symlist< T >::symlist(), pq_tree::where_bubble_up_failed(), and pq_node::~pq_node().

Here is the caller graph for this function:

template<class T>

const_iterator symlist< T >::begin ( void ) const

inline

Start iteration through elements of list.

Returns: start iterator

Definition at line 315 of file symlist.h.

View newest version in sPHENIX GitHub at line 315 of file symlist.h

template<class T >

void symlist< T >::detach_sublist ( )

Definition at line 695 of file symlist.h.

View newest version in sPHENIX GitHub at line 695 of file symlist.h

References symlist_iterator< T, Ref >::act, symnode< T >::adj, parse_cmake_options::begin, Acts::UnitConstants::e, end, it, symlist_iterator< T, Ref >::next(), and symlist_iterator< T, Ref >::prev().

Referenced by pq_tree::reduce(), and pq_tree::reset().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T>

bool symlist< T >::empty ( void ) const

inline

Checks whether list is empty.

Takes constant time.

Return values

true	iff list is empty

Definition at line 261 of file symlist.h.

View newest version in sPHENIX GitHub at line 261 of file symlist.h

Referenced by p_node::clear(), pq_tree::P3(), pq_tree::P4(), pq_tree::P5(), pq_tree::P6(), pq_tree::reduce(), pq_tree::replace_pert(), pq_tree::reset(), and pq_node::~pq_node().

Here is the caller graph for this function:

template<class T>

iterator symlist< T >::end ( void )

inline

End of iteration through elements of list.

Returns: end iterator

Definition at line 305 of file symlist.h.

View newest version in sPHENIX GitHub at line 305 of file symlist.h

Referenced by symlist< pq_node * >::begin(), pq_tree::blocked_in_subtree(), pq_tree::bubble_up(), planarity::case_B(), planarity::case_D(), p_node::clear(), pq_tree::dfs(), planarity::examine_obstruction(), planarity::extend_embedding(), p_node::full(), pq_tree::integrity_check(), planarity::mark_all_neighbors_of_leaves(), operator<<(), planar_embedding::operator=(), symlist< T >::operator=(), pq_tree::P1(), pq_tree::P2(), pq_tree::P3(), pq_tree::P4(), pq_tree::P5(), pq_tree::P6(), p_node::p_node(), p_node::partial(), q_node::pertinent(), pq_tree::pq_tree(), pq_tree::replace_pert(), planarity::search_full_leaf(), symlist< T >::symlist(), and pq_tree::where_bubble_up_failed().

Here is the caller graph for this function:

template<class T>

const_iterator symlist< T >::end ( void ) const

inline

End of iteration through elements of list.

Returns: end iterator

Definition at line 325 of file symlist.h.

View newest version in sPHENIX GitHub at line 325 of file symlist.h

template<class T >

symlist_iterator< T, T & > symlist< T >::erase ( iterator pos )

Deletes element at position pos from list.

Parameters

pos	position to be deleted

Returns: position of next element

Definition at line 621 of file symlist.h.

View newest version in sPHENIX GitHub at line 621 of file symlist.h

References symlist_iterator< T, Ref >::act, assert, symlist_iterator< T, Ref >::next(), next, Acts::Test::pos, and symlist_iterator< T, Ref >::prev().

Referenced by planarity::examine_obstruction(), q_node::merge(), pq_tree::P3(), pq_tree::P4(), pq_tree::P5(), pq_tree::P6(), pq_tree::remove_dir_ind(), pq_tree::replace_pert(), and pq_node::~pq_node().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T >

symlist_iterator< T, T & > symlist< T >::erase	(	iterator	it,
		iterator	end
	)

Deletes the elements [it, end) from list.

Parameters

it	first position to be deleted
end	one-past the last position to be deleted

Returns: position of next element.

Definition at line 643 of file symlist.h.

View newest version in sPHENIX GitHub at line 643 of file symlist.h

References symlist_iterator< T, Ref >::act, assert, end, it, symlist_iterator< T, Ref >::next(), and symlist_iterator< T, Ref >::prev().

Here is the call graph for this function:

template<class T>

T& symlist< T >::front ( void )

inline

First element in list.

Assumes that list ins't empty.

Returns: first element

Definition at line 273 of file symlist.h.

View newest version in sPHENIX GitHub at line 273 of file symlist.h

Referenced by planarity::attachment_cycle(), pq_tree::integrity_check(), q_node::merge(), pq_tree::P3(), pq_tree::P4(), pq_tree::P5(), pq_tree::P6(), q_node::pertinent(), pq_tree::Q1(), pq_tree::reduce(), pq_tree::reset(), and pq_node::~pq_node().

Here is the caller graph for this function:

template<class T>

symlist_iterator< T, T & > symlist< T >::insert	(	iterator	pos,
		const T &	data
	)

Inserts data before pos in list.

Parameters

pos	position
data	element to be inserted

Returns: position of insertion

Definition at line 538 of file symlist.h.

View newest version in sPHENIX GitHub at line 538 of file symlist.h

References symlist_iterator< T, Ref >::act, symnode< T >::adj, n, symlist_iterator< T, Ref >::next(), Acts::Test::pos, and symlist_iterator< T, Ref >::prev().

Referenced by pq_tree::P2(), pq_tree::P3(), pq_tree::P4(), pq_tree::P5(), pq_tree::P6(), pq_tree::pq_tree(), and pq_tree::replace_pert().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T>

symlist< T > & symlist< T >::operator= ( const symlist< T > & li )

Assignes li to this list.

Note: All elements in this list will be deleted.

Parameters

li

Returns: this list

Definition at line 520 of file symlist.h.

View newest version in sPHENIX GitHub at line 520 of file symlist.h

References parse_cmake_options::begin, symlist< T >::begin(), Acts::UnitConstants::e, end, symlist< T >::end(), and it.

Here is the call graph for this function:

template<class T>

iterator symlist< T >::rbegin ( )

inline

Start iteration through element of list in reverse order.

Returns: start iterator

Definition at line 335 of file symlist.h.

View newest version in sPHENIX GitHub at line 335 of file symlist.h

template<class T>

const_iterator symlist< T >::rbegin ( ) const

inline

Start iteration through element of list in reverse order.

Returns: start iterator

Definition at line 355 of file symlist.h.

View newest version in sPHENIX GitHub at line 355 of file symlist.h

template<class T>

iterator symlist< T >::rend ( )

inline

End of iteration through elements of list in reverse order.

Returns: end iterator

Definition at line 345 of file symlist.h.

View newest version in sPHENIX GitHub at line 345 of file symlist.h

Referenced by symlist< pq_node * >::rbegin().

Here is the caller graph for this function:

template<class T>

const_iterator symlist< T >::rend ( ) const

inline

End of iteration through elements of list in reverse order.

Returns: end iterator

Definition at line 365 of file symlist.h.

View newest version in sPHENIX GitHub at line 365 of file symlist.h

template<class T >

void symlist< T >::reverse ( )

inline

Change the direction of list.

Takes constant time.

Definition at line 722 of file symlist.h.

View newest version in sPHENIX GitHub at line 722 of file symlist.h

References Acts::Test::tmp().

Referenced by planarity::correct_embedding(), and q_node::turn().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T >

void symlist< T >::splice	(	iterator	pos,
		iterator	it
	)

Inserts the element it points to before pos into this list.

It is assumed that the element it refers lies in a different list. All iterators to elements in either of the two lists stay valid. Takes constant time.

Parameters

pos	position
it	position of element to be inserted

Definition at line 611 of file symlist.h.

View newest version in sPHENIX GitHub at line 611 of file symlist.h

References Acts::Test::tmp().

Referenced by planarity::add_to_embedding(), p_node::clear(), p_node::full(), q_node::merge(), pq_tree::P1(), pq_tree::P4(), pq_tree::P6(), p_node::p_node(), and p_node::partial().

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T >

void symlist< T >::splice	(	iterator	pos,
		iterator	it,
		iterator	end
	)

Inserts the elements [it,end) refers to before pos into this list.

It is assumed that [it,end) lies in a different list. All iterators to elements in either of the two lists stay valid. Takes constant time.

Parameters

pos	position
it	position of first element to be inserted
end	position of one-past the last element to be inserted

Definition at line 561 of file symlist.h.

View newest version in sPHENIX GitHub at line 561 of file symlist.h

References symlist_iterator< T, Ref >::act, end, symlist_iterator< T, Ref >::next(), Acts::Test::pos, and symlist_iterator< T, Ref >::prev().

Here is the call graph for this function:

Member Data Documentation

template<class T>

iterator symlist< T >::_next

private

Definition at line 460 of file symlist.h.

View newest version in sPHENIX GitHub at line 460 of file symlist.h

template<class T>

iterator symlist< T >::_prev

private

Definition at line 453 of file symlist.h.

View newest version in sPHENIX GitHub at line 453 of file symlist.h

template<class T>

symnode<T>* symlist< T >::link

private

Definition at line 446 of file symlist.h.

View newest version in sPHENIX GitHub at line 446 of file symlist.h

Referenced by symlist< pq_node * >::back(), symlist< pq_node * >::empty(), symlist< pq_node * >::end(), symlist< pq_node * >::front(), symlist< pq_node * >::rend(), and symlist< pq_node * >::symlist().

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

JETSCAPE/blob/main/external_packages/gtl/include/GTL/symlist.h

Public Types

Public Member Functions

Private Attributes

Detailed Description

template<class T> class symlist< T >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class T>
class symlist< T >