paal::data_structures::detail::Node< V > Class Template Reference

#include <splay_tree.hpp>

Public Types
using	value_type = V
using	node_type = Node< value_type >
using	node_ptr = std::unique_ptr< node_type >

Public Member Functions
	Node (const value_type &val)
	Node (const Node &n)
	constructor
node_type *	parent ()
void	set_parent (node_type *p)
void	make_root ()
	detaches this node from parent
node_ptr &	left ()
void	set_left (node_ptr node)
	sets left child pointer More...
node_ptr &	right ()
void	set_right (node_ptr node)
template<typename Direction >
void	set (node_ptr node, Direction dir_tag)
	sets child pointer More...
template<typename Direction >
void	set_internal (node_ptr node, Direction dir_tag)
	sets child pointer (no relaxation) More...
void	update_size ()
	recomputes subtree size from sizes of children's subtrees
node_ptr &	child (reversed_tag)
node_ptr &	child (forward_tag)
template<typename Direction >
node_type *	extreme (Direction dir_tag)
template<typename Direction >
node_type *	advance (Direction dir_tag)
node_type *	next ()
node_type *	prev ()
std::size_t	size ()
void	subtree_reverse ()
	lazily reverses order in subtree
void	normalize ()
	locally relaxes tree
void	normalize_root_path ()
	relaxes all nodes on path from root to this

Public Attributes
value_type	val_
	value of the node

Detailed Description

template<typename V>
class paal::data_structures::detail::Node< V >

Node of a splay_tree.

Left/right relaxation should be understood as follows. Meaning of left/right field changes iff xor of all bits on the path to the root is 1. This enables us to reverse entire subtree in constant time (by flipping bit in the root). Normalization is needed to determine which child is the real left/right.

Definition at line 42 of file splay_tree.hpp.

Constructor & Destructor Documentation

template<typename V >

paal::data_structures::detail::Node< V >::Node ( const value_type &  val )

inlineexplicit

Parameters

val	stored value

Definition at line 86 of file splay_tree.hpp.

Member Function Documentation

template<typename V >

template<typename Direction >

node_type* paal::data_structures::detail::Node< V >::advance ( Direction  dir_tag )

inline

Returns

next in same tree according to infix order WARNING, we assume that path from root to the this node is normalized

Definition at line 175 of file splay_tree.hpp.

template<typename V >

node_ptr& paal::data_structures::detail::Node< V >::left ( )

inline

Returns

left child pointer

Definition at line 110 of file splay_tree.hpp.

template<typename V >

node_type* paal::data_structures::detail::Node< V >::next ( )

inline

Returns

next in same tree according to infix order WARNING, we assume that path from root to the this node is normalized

Definition at line 197 of file splay_tree.hpp.

template<typename V >

node_type* paal::data_structures::detail::Node< V >::parent ( )

inline

Returns

parent node

Definition at line 102 of file splay_tree.hpp.

template<typename V >

node_type* paal::data_structures::detail::Node< V >::prev ( )

inline

Returns

previous in same tree according to infix order

Definition at line 202 of file splay_tree.hpp.

template<typename V >

node_ptr& paal::data_structures::detail::Node< V >::right ( )

inline

Returns

true right child pointer

Definition at line 124 of file splay_tree.hpp.

template<typename V >

template<typename Direction >

void paal::data_structures::detail::Node< V >::set ( node_ptr  node, Direction  dir_tag  )

inline

sets child pointer

Parameters

node

new child

Definition at line 137 of file splay_tree.hpp.

template<typename V >

template<typename Direction >

void paal::data_structures::detail::Node< V >::set_internal ( node_ptr  node, Direction  dir_tag  )

inline

sets child pointer (no relaxation)

Parameters

node

new child

Definition at line 148 of file splay_tree.hpp.

template<typename V >

void paal::data_structures::detail::Node< V >::set_left ( node_ptr  node )

inline

sets left child pointer

Parameters

node

new child

Definition at line 119 of file splay_tree.hpp.

template<typename V >

std::size_t paal::data_structures::detail::Node< V >::size ( )

inline

Returns

size of subtree

Definition at line 207 of file splay_tree.hpp.

---

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

• include/paal/data_structures/splay_tree.hpp