fe::XTrie< D, K, N > Class Template Reference

Hash-consed sets of D*. More...

#include <fe/xtrie.h>

Classes
class	Set

Public Member Functions
Construction
XTrie &	operator= (const XTrie &)=delete
	XTrie ()
	XTrie (const XTrie &)=delete
	XTrie (XTrie &&other)
Set Operations
Note These operations do not modify the input set(s); they create a new Set.
template<std::random_access_iterator I>
Set	create (I begin, I end)
	Create a Set with all elements in [begin, end).
template<std::ranges::input_range R>
Set	create (R &&r)
	Create a Set wih all elements in r.
Set	create (std::initializer_list< D * > list)
	Create a Set wih all elements in list.
Set	insert (Set s, D *d)
	Yields \(s \cup \{d\}\).
Set	merge (Set s1, Set s2)
	Yields \(s_1 \cup s_2\).
Set	erase (Set s, D *d)
	Yields \(s \setminus \{d\}\).

DOT output
void	dot ()
void	dot (std::ostream &os) const
void	swap (XTrie &s1, XTrie &s2) noexcept

Detailed Description

template<class D, class K, size_t N = 16>
class fe::XTrie< D, K, N >

Hash-consed sets of D*.

Small sets are sorted arrays, large ones paths in a trie; either way, equal sets are pointer-equal. This is an IndexedTrie as described here. K is a key trait that grants access to the two uint32_ts XTrie needs on D:

struct Key {
    static uint32_t gid(const D*) noexcept;               ///< Unique id; orders and hashes the elements.
    static uint32_t tid(const D*) noexcept;               ///< Trie id; `0` means "not assigned yet".
    static void set_tid(const D*, uint32_t) noexcept;
    static std::ostream& stream(std::ostream&, const D*); ///< Optional; defaults to Key::gid.
};

N is the maximum size of an array set; bigger sets live in the trie.

Definition at line 39 of file xtrie.h.

Constructor & Destructor Documentation

XTrie() [1/3]

template<class D, class K, size_t N = 16>

fe::XTrie< D, K, N >::XTrie ( )

inline

Definition at line 406 of file xtrie.h.

Referenced by operator=(), swap, XTrie(), and XTrie().

XTrie() [2/3]

template<class D, class K, size_t N = 16>

fe::XTrie< D, K, N >::XTrie ( const XTrie< D, K, N > & )

delete

References XTrie().

XTrie() [3/3]

template<class D, class K, size_t N = 16>

fe::XTrie< D, K, N >::XTrie ( XTrie< D, K, N > && other )

inline

Definition at line 409 of file xtrie.h.

References swap, and XTrie().

Member Function Documentation

create() [1/3]

template<class D, class K, size_t N = 16>

template<std::random_access_iterator I>

Set fe::XTrie< D, K, N >::create ( I begin, I end )

inlinenodiscard

Create a Set with all elements in [begin, end).

Attention

Reorders [begin, end) in place.

Definition at line 422 of file xtrie.h.

Referenced by create(), create(), and erase().

create() [2/3]

template<class D, class K, size_t N = 16>

template<std::ranges::input_range R>

Set fe::XTrie< D, K, N >::create ( R && r )

inlinenodiscard

Create a Set wih all elements in r.

Definition at line 441 of file xtrie.h.

References create().

create() [3/3]

template<class D, class K, size_t N = 16>

Set fe::XTrie< D, K, N >::create ( std::initializer_list< D * > list )

inlinenodiscard

Create a Set wih all elements in list.

Definition at line 447 of file xtrie.h.

References create().

dot() [1/2]

template<class D, class K, size_t N = 16>

void fe::XTrie< D, K, N >::dot ( )

inline

Definition at line 604 of file xtrie.h.

References dot().

Referenced by dot().

dot() [2/2]

template<class D, class K, size_t N = 16>

void fe::XTrie< D, K, N >::dot ( std::ostream & os ) const

inline

Definition at line 609 of file xtrie.h.

erase()

template<class D, class K, size_t N = 16>

Set fe::XTrie< D, K, N >::erase ( Set s, D * d )

inlinenodiscard

Yields \(s \setminus \{d\}\).

Definition at line 568 of file xtrie.h.

References create(), erase(), and fe::XTrie< D, K, N >::Set::Set().

Referenced by erase().

insert()

template<class D, class K, size_t N = 16>

Set fe::XTrie< D, K, N >::insert ( Set s, D * d )

inlinenodiscard

Yields \(s \cup \{d\}\).

Definition at line 453 of file xtrie.h.

References insert().

Referenced by insert(), and merge().

merge()

template<class D, class K, size_t N = 16>

Set fe::XTrie< D, K, N >::merge ( Set s1, Set s2 )

inlinenodiscard

Yields \(s_1 \cup s_2\).

Definition at line 504 of file xtrie.h.

References fe::XTrie< D, K, N >::Set::empty(), insert(), and merge().

Referenced by merge().

operator=()

template<class D, class K, size_t N = 16>

XTrie & fe::XTrie< D, K, N >::operator= ( const XTrie< D, K, N > & )

delete

References XTrie().

Friends And Related Symbol Documentation

swap

template<class D, class K, size_t N = 16>

void swap ( XTrie< D, K, N > & s1, XTrie< D, K, N > & s2 )

friend

Definition at line 617 of file xtrie.h.

References swap, and XTrie().

Referenced by swap, and XTrie().

---

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

• fe/xtrie.h