fe::lct::Node< P, K > Class Template Reference

This is an intrusive Link-Cut-Tree. More...

#include <fe/lct.h>

Inheritance diagram for fe::lct::Node< P, K >:

Public Types
enum	Dir : size_t {   Bot ,   Top }
	Index into Node::kids. More...

Public Member Functions
constexpr	Node () noexcept=default
Getters
constexpr P *	find (const K &k) noexcept
	Find k or the element just greater than k.
bool	contains (const K &k) noexcept
parent
constexpr bool	is_aux_child () const noexcept
constexpr Node *	aux_parent () noexcept
constexpr P *	path_parent () noexcept
Splay Tree
constexpr Dir	dir (const Node *kid) const noexcept
	Which of Node::kids is kid?
constexpr void	splay () noexcept
	Splays this to the root of its splay tree.
constexpr void	rotate (Dir i) noexcept
	Helper for Splay-Tree: rotates this's ith kid c into this's (x's) place:
Link-Cut-Tree
constexpr void	link (Node *child) noexcept
	Registers the edge this -> child in the aux tree.
constexpr P *	expose () noexcept
	Make a preferred path from this to root while putting this at the root of the aux tree.
constexpr P *	lca (Node *other) noexcept
	Least Common Ancestor of this and other in the aux tree; leaves other exposed.
constexpr bool	is_descendant_of (Node *other) noexcept
	Is this a descendant of other in the aux tree?

Public Attributes
Node *	parent = nullptr
	parent or path-parent
std::array< Node *, 2 >	kids = {}
	Node::Bot/Node::Top children.

Detailed Description

template<class P, class K>
class fe::lct::Node< P, K >

This is an intrusive Link-Cut-Tree.

Intrusive means that you have to inherit from this class via CRTP like this:

class Node : public lct::Node<Node, MyKey> {
    constexpr bool lt(const MyKey& key) const noexcept { ... }
    constexpr bool eq(const MyKey& key) const noexcept { ... }
    // ...
};

Definition at line 21 of file lct.h.

Member Enumeration Documentation

Dir

template<class P, class K>

enum fe::lct::Node::Dir : size_t

Index into Node::kids.

Enumerator
Bot	left/deeper/bottom/leaf-direction
Top	right/shallower/top/root-direction

Definition at line 24 of file lct.h.

Constructor & Destructor Documentation

Node()

template<class P, class K>

fe::lct::Node< P, K >::Node ( )

constexprdefaultnoexcept

Member Function Documentation

aux_parent()

template<class P, class K>

Node * fe::lct::Node< P, K >::aux_parent ( )

inlineconstexprnoexcept

Definition at line 67 of file lct.h.

contains()

template<class P, class K>

bool fe::lct::Node< P, K >::contains ( const K & k )

inlinenodiscardnoexcept

Definition at line 57 of file lct.h.

dir()

template<class P, class K>

Dir fe::lct::Node< P, K >::dir ( const Node< P, K > * kid ) const

inlineconstexprnoexcept

Which of Node::kids is kid?

Definition at line 76 of file lct.h.

expose()

template<class P, class K>

P * fe::lct::Node< P, K >::expose ( )

inlineconstexprnoexcept

Make a preferred path from this to root while putting this at the root of the aux tree.

Returns

the last valid path_parent().

Definition at line 148 of file lct.h.

find()

template<class P, class K>

P * fe::lct::Node< P, K >::find ( const K & k )

inlineconstexprnoexcept

Find k or the element just greater than k.

Definition at line 40 of file lct.h.

is_aux_child()

template<class P, class K>

bool fe::lct::Node< P, K >::is_aux_child ( ) const

inlineconstexprnoexcept

Is this a child of Node::parent within the same splay tree?

Definition at line 63 of file lct.h.

is_descendant_of()

template<class P, class K>

bool fe::lct::Node< P, K >::is_descendant_of ( Node< P, K > * other )

inlineconstexprnoexcept

Is this a descendant of other in the aux tree?

Also true, if this == other.

Definition at line 165 of file lct.h.

lca()

template<class P, class K>

P * fe::lct::Node< P, K >::lca ( Node< P, K > * other )

inlineconstexprnoexcept

Least Common Ancestor of this and other in the aux tree; leaves other exposed.

Returns

nullptr, if a and b are in different trees.

Definition at line 161 of file lct.h.

link()

template<class P, class K>

void fe::lct::Node< P, K >::link ( Node< P, K > * child )

inlineconstexprnoexcept

Registers the edge this -> child in the aux tree.

Definition at line 137 of file lct.h.

path_parent()

template<class P, class K>

P * fe::lct::Node< P, K >::path_parent ( )

inlineconstexprnoexcept

Definition at line 68 of file lct.h.

rotate()

template<class P, class K>

void fe::lct::Node< P, K >::rotate ( Dir i )

inlineconstexprnoexcept

Helper for Splay-Tree: rotates this's ith kid c into this's (x's) place:

| i == Top              | i == Bot               |
|-----------------------|------------------------|
|   p              p    |       p          p     |
|   |              |    |       |          |     |
|   x              c    |       x          c     |
|  / \     ->     / \   |      / \   ->   / \    |
| a   c          x   d  |     c   a      d   x   |
|    / \        / \     |    / \            / \  |
|   b   d      a   b    |   d   b          b   a |

Definition at line 109 of file lct.h.

splay()

template<class P, class K>

void fe::lct::Node< P, K >::splay ( )

inlineconstexprnoexcept

Splays this to the root of its splay tree.

Definition at line 82 of file lct.h.

Member Data Documentation

kids

template<class P, class K>

std::array<Node*, 2> fe::lct::Node< P, K >::kids = {}

Node::Bot/Node::Top children.

Definition at line 177 of file lct.h.

Referenced by fe::lct::Node< Node, D * >::is_aux_child(), and fe::lct::Node< Node, D * >::link().

parent

template<class P, class K>

Node* fe::lct::Node< P, K >::parent = nullptr

parent or path-parent

Definition at line 176 of file lct.h.

Referenced by fe::lct::Node< Node, D * >::expose().

---

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

• fe/lct.h