paal::data_structures::splay_tree< T > Class Template Reference

detail More...

#include <splay_tree.hpp>

Public Types
using	value_type = T
using	node_type = detail::Node< value_type >
using	node_ptr = typename node_type::node_ptr
using	iterator = detail::Iterator< value_type, detail::forward_tag >
using	const_iterator = const iterator
using	reverse_iterator = detail::Iterator< value_type, detail::reversed_tag >
using	const_reverse_iterator = const reverse_iterator

Public Member Functions
template<typename I >
	splay_tree (const I b, const I e)
	constructs tree from elements between two iterators More...
	splay_tree (splay_tree &&splay)=default
	constructor
splay_tree &	operator= (splay_tree &&splay)=default
	operator=
splay_tree &	operator= (splay_tree &splay)
	operator=
	splay_tree (const splay_tree &splay)
	constructor
template<typename A >
	splay_tree (const A &array)
	creates tree from elements in std::vector More...
iterator	begin () const
iterator	end () const
reverse_iterator	rbegin ()
reverse_iterator	rend ()
std::size_t	size () const
bool	empty ()
value_type &	operator[] (std::size_t i) const
std::size_t	get_idx (const T &t) const
std::size_t	get_rotation_cnt () const
	gets rotationCnt() More...
iterator	splay (std::size_t i) const
	splays tree according to splay policy More...
splay_tree	split_higher (std::size_t i)
	splits sequence, modified this contains elements {0, ..., i} More...
splay_tree	split_lower (std::size_t i)
	splits sequence, modified this contains elements {i, ...} More...
void	merge_right (splay_tree other)
	merges given tree to the right of the biggest element of this More...
void	merge_left (splay_tree other)
	merges given tree to the left of the smallest element of this More...
void	reverse (std::size_t i, std::size_t j)
	reverses subsequence of elements with indices in {i, ..., j} More...

Detailed Description

template<typename T>
class paal::data_structures::splay_tree< T >

detail

Splay trees with logarithmic reversing of any subsequence.

All tree operations are amortized logarithmic time in size of tree, each element is indexed by number of smaller elements than this element. Note that lookups are also amortized logarithmic in size of tree. Order of elements is induced from infix ordering of nodes storing these elements.

Definition at line 31 of file splay_tree.hpp.

Constructor & Destructor Documentation

template<typename T>

template<typename I >

paal::data_structures::splay_tree< T >::splay_tree ( const I  b, const I  e  )

inline

constructs tree from elements between two iterators

Parameters

b	iterator to first element
e	iterator to element after last

Definition at line 351 of file splay_tree.hpp.

template<typename T>

template<typename A >

paal::data_structures::splay_tree< T >::splay_tree ( const A &  array )

inlineexplicit

creates tree from elements in std::vector

Parameters

array

vector container

Definition at line 383 of file splay_tree.hpp.

Member Function Documentation

template<typename T>

iterator paal::data_structures::splay_tree< T >::begin ( ) const

inline

Returns

forward iterator to first element in container

Definition at line 388 of file splay_tree.hpp.

template<typename T>

bool paal::data_structures::splay_tree< T >::empty ( )

inline

Returns

true iff tree contains no elements

Definition at line 411 of file splay_tree.hpp.

template<typename T>

iterator paal::data_structures::splay_tree< T >::end ( ) const

inline

Returns

forward iterator to element after last in container

Definition at line 395 of file splay_tree.hpp.

template<typename T>

std::size_t paal::data_structures::splay_tree< T >::get_idx ( const T &  t ) const

inline

Parameters

t	referenced element

Definition at line 417 of file splay_tree.hpp.

template<typename T>

std::size_t paal::data_structures::splay_tree< T >::get_rotation_cnt ( ) const

inline

gets rotationCnt()

Returns

Definition at line 441 of file splay_tree.hpp.

template<typename T>

void paal::data_structures::splay_tree< T >::merge_left ( splay_tree< T >  other )

inline

merges given tree to the left of the smallest element of this

Parameters

other

tree to be merged

Definition at line 476 of file splay_tree.hpp.

template<typename T>

void paal::data_structures::splay_tree< T >::merge_right ( splay_tree< T >  other )

inline

merges given tree to the right of the biggest element of this

Parameters

other

tree to be merged

Definition at line 470 of file splay_tree.hpp.

template<typename T>

value_type& paal::data_structures::splay_tree< T >::operator[] ( std::size_t  i ) const

inline

Parameters

i	index of referenced element

Definition at line 414 of file splay_tree.hpp.

template<typename T>

reverse_iterator paal::data_structures::splay_tree< T >::rbegin ( )

inline

Returns

reverse iterator to last element in container

Definition at line 398 of file splay_tree.hpp.

template<typename T>

reverse_iterator paal::data_structures::splay_tree< T >::rend ( )

inline

Returns

reverse iterator to element before first in container

Definition at line 405 of file splay_tree.hpp.

template<typename T>

void paal::data_structures::splay_tree< T >::reverse ( std::size_t  i, std::size_t  j  )

inline

reverses subsequence of elements with indices in {i, ..., j}

Parameters

i	index of first element of subsequence
j	index of last element of subsequence

Definition at line 483 of file splay_tree.hpp.

template<typename T>

std::size_t paal::data_structures::splay_tree< T >::size ( ) const

inline

Returns

number of elements in tree

Definition at line 408 of file splay_tree.hpp.

template<typename T>

iterator paal::data_structures::splay_tree< T >::splay ( std::size_t  i ) const

inline

splays tree according to splay policy

Parameters

i	index of element to become root

Definition at line 447 of file splay_tree.hpp.

template<typename T>

splay_tree paal::data_structures::splay_tree< T >::split_higher ( std::size_t  i )

inline

splits sequence, modified this contains elements {0, ..., i}

Parameters

i	index of last element of this after modification

Returns

tree containing elements {i+1, ...}

Definition at line 457 of file splay_tree.hpp.

template<typename T>

splay_tree paal::data_structures::splay_tree< T >::split_lower ( std::size_t  i )

inline

splits sequence, modified this contains elements {i, ...}

Parameters

i	index of first element of this after modification

Returns

tree containing elements {0, ..., i-1}

Definition at line 464 of file splay_tree.hpp.

---

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

• include/paal/data_structures/splay_tree.hpp