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

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

#include <mim/util/link_cut_tree.h>

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

Public Member Functions
constexpr	Node () noexcept=default
Getters
bool	contains (const K &k) noexcept
constexpr P *	find (const K &k) noexcept
	Find k or the element just greater than k.
parent
constexpr Node *	aux_parent () noexcept
constexpr P *	path_parent () noexcept
Splay Tree
constexpr void	splay () noexcept
	Splays this to the root of its splay tree.
template<size_t l>
constexpr void	rotate () noexcept
	Helper for Splay-Tree: rotate left/right:
constexpr void	rol () noexcept
constexpr void	ror () noexcept
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
Node *	bot = nullptr
	left/deeper/bottom/leaf-direction
Node *	top = nullptr
	right/shallower/top/root-direction

Detailed Description

template<class P, class K>
class mim::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 { /*...*&zwj;/ }
    constexpr bool eq(const MyKey& key) const noexcept { /*...*&zwj;/ }
    // ...
};

Definition at line 18 of file link_cut_tree.h.

Constructor & Destructor Documentation

Node()

template<class P, class K>

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

constexprdefaultnoexcept

Member Function Documentation

aux_parent()

template<class P, class K>

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

inlineconstexprnoexcept

Definition at line 58 of file link_cut_tree.h.

Referenced by mim::lct::Node< Node, D * >::splay().

contains()

template<class P, class K>

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

inlinenodiscardnoexcept

Definition at line 28 of file link_cut_tree.h.

expose()

template<class P, class K>

P * mim::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 152 of file link_cut_tree.h.

Referenced by mim::lct::Node< Node, D * >::contains(), mim::lct::Node< Node, D * >::find(), mim::lct::Node< Node, D * >::is_descendant_of(), mim::lct::Node< Node, D * >::lca(), and mim::lct::Node< Node, D * >::link().

find()

template<class P, class K>

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

inlineconstexprnoexcept

Find k or the element just greater than k.

Definition at line 37 of file link_cut_tree.h.

is_descendant_of()

template<class P, class K>

bool mim::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 169 of file link_cut_tree.h.

lca()

template<class P, class K>

P * mim::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 165 of file link_cut_tree.h.

link()

template<class P, class K>

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

inlineconstexprnoexcept

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

Definition at line 141 of file link_cut_tree.h.

path_parent()

template<class P, class K>

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

inlineconstexprnoexcept

Definition at line 59 of file link_cut_tree.h.

rol()

template<class P, class K>

void mim::lct::Node< P, K >::rol ( )

inlineconstexprnoexcept

Definition at line 133 of file link_cut_tree.h.

ror()

template<class P, class K>

void mim::lct::Node< P, K >::ror ( )

inlineconstexprnoexcept

Definition at line 134 of file link_cut_tree.h.

rotate()

template<class P, class K>

template<size_t l>

void mim::lct::Node< P, K >::rotate ( )

inlineconstexprnoexcept

Helper for Splay-Tree: rotate left/right:

| Left                  | Right                  |
|-----------------------|------------------------|
|   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 106 of file link_cut_tree.h.

Referenced by mim::lct::Node< Node, D * >::rol(), and mim::lct::Node< Node, D * >::ror().

splay()

template<class P, class K>

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

inlineconstexprnoexcept

Splays this to the root of its splay tree.

Definition at line 67 of file link_cut_tree.h.

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

Member Data Documentation

bot

template<class P, class K>

Node* mim::lct::Node< P, K >::bot = nullptr

left/deeper/bottom/leaf-direction

Definition at line 181 of file link_cut_tree.h.

Referenced by mim::lct::Node< Node, D * >::rotate().

parent

template<class P, class K>

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

parent or path-parent

Definition at line 180 of file link_cut_tree.h.

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

top

template<class P, class K>

Node* mim::lct::Node< P, K >::top = nullptr

right/shallower/top/root-direction

Definition at line 182 of file link_cut_tree.h.

Referenced by mim::lct::Node< Node, D * >::rotate().

---

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

• include/mim/util/link_cut_tree.h