trie::Trie Class Reference

Recursive immutable node based trie. More...

#include <trie.hpp>

Public Member Functions
	Trie (Trie &&)=default
Trie &	operator= (Trie &&)=default
	Trie (const Trie &)=delete
Trie &	operator= (const Trie &)=delete
	Trie (const std::initializer_list< std::string_view > &words)
	Trie (const std::initializer_list< std::string > &words)
	Trie (const std::initializer_list< const char * > &words)
template<class Iterator1 , class Iterator2 >
	Trie (Iterator1 first, const Iterator2 last)
template<class Strings >
	Trie (Strings &&strings_in)
	The constructor that actually does the work.
bool	contains (std::string_view word) const
	Check if this dictionary contains word. More...
bool	further (std::string_view word) const
	Check if this dictionary might contain words with word as a prefix. More...
template<class OutputIterator >
void	contains_further (const std::string_view stem, const std::string_view suffixes, OutputIterator contains_further_it) const
	For each char in suffix appended to stem, check whether this dictionary contains this word and if it may contain longer words with this prefix. More...
std::size_t	size () const
bool	empty () const

Private Member Functions
const Node *	search (std::string_view word) const
std::pair< Node *, bool >	insert (std::string_view word)

Private Attributes
Node	root_
std::size_t	size_
utility::FlatCharValueMap< const Node * >	cache_

Friends
std::ostream &	operator<< (std::ostream &os, const Trie &ct)

Detailed Description

Recursive immutable node based trie.

Recursive tree structure of nodes, where each node holds a vector-like container of edges, and each edge consists of a character and a pointer to the corresponding child node. To lookup a word of length "m", using a dictionary with "d" distinct characters, for example d == 26 for lowercase ascii and the English alphabet, lookup is O(m * d).

Realistically, the factor of d will usually be much less than the actual value of d, so really more like just O(m). Could say that furthermore, since (in English at least) average word length is much shorter than max(m) anyway, essentially this becomes almost constant time lookup.

Note

Not thread safe even for just reading, due to use of unprotected internal cache.

Constructor & Destructor Documentation

Trie()

trie::Trie::Trie ( const Trie &  )

delete

Note

See trie/include/wordsearch_solver/trie/node.hpp before changing/implementing this, must implement proper deep copy, traits don't behave nicely.

Member Function Documentation

contains()

bool trie::Trie::contains

(

std::string_view

word

)

const

Check if this dictionary contains word.

Parameters

[in]

word

The word to check

Returns

true if word is present, else false

contains_further()

template<class OutputIterator >

void trie::Trie::contains_further	(	const std::string_view	stem,
		const std::string_view	suffixes,
		OutputIterator	contains_further_it
	)		const

For each char in suffix appended to stem, check whether this dictionary contains this word and if it may contain longer words with this prefix.

Parameters

[in]	stem
[in]	suffixes
[out]	contains_further_it	This function is what the solver algorithm calls every iteration to ask the dictionary solver implementation to do its work.

contains_further_it should be assigned to and incremented like an output iterator. The value written should be a std::pair<bool, bool>.

Example contains_further implementation:

const auto* node = this->search(stem);
if (!node) {
  return;
}
 
for (const auto [i, c] : ranges::views::enumerate(suffixes)) {
  const std::string_view suffix = {&c, 1};
  const auto contains = detail::contains(*node, suffix);
  const auto further = detail::further(*node, suffix);
  *contains_further_it++ = {contains, further};
}

Each character's position in suffix corresponds to the order that that suffix's output should be written to contains_further_it.

suffixes is not guaranteed to be sorted.

further()

bool trie::Trie::further

(

std::string_view

word

)

const

Check if this dictionary might contain words with word as a prefix.

Parameters

[in]

word

The prefix to check

Returns

false if there are no more strings in the dictionary with word as a prefix, true if there might be.

Note

Some solvers do not conclusively know whether, for a prefix word, there are more words that contain that prefix. This is acceptable, though sub-optimal and will result in wasted search time, as long as eventually this returns false, assuming for word there are in fact no more words with that prefix.

insert()

std::pair< Node *, bool > trie::Trie::insert ( std::string_view  word )

private

Returns

A std::pair of a pointer to the node corresponding to the end of the word, and a bool indicating whether or not insertion was successful (false if the word was already present).

search()

const Node * trie::Trie::search ( std::string_view  word ) const

private

Returns

Node* to the node corresponding to the end of the word if found, else nullptr

---

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

• trie/include/wordsearch_solver/trie/trie.hpp
• trie/include/wordsearch_solver/trie/trie.tpp
• trie/src/trie.cpp