trie::Node Class Reference

A vector of edges to child nodes, sorted by edge child node character value, and a bool indicating whether or not a word terminates at this node. More...

#include <node.hpp>

Classes
struct	Edge

Public Types
using	Edges = boost::container::small_vector< Edge, 4 >
using	EdgesIterator = Edges::const_iterator

Public Member Functions
	Node (bool is_end_of_word)
Node *	add_char (char c)
	Inserts a child node corresponding to the character c if it doesn't exist, and returns a pointer to the child node.
void	set_is_end_of_word (bool is_end_of_word)
const Node *	test (const char c) const
	Test if a node has an edge containing the character c. More...
bool	any () const
bool	is_end_of_word () const
const Edges &	edges () const

Private Attributes
Edges	edges_
bool	is_end_of_word_

Friends
std::ostream &	operator<< (std::ostream &os, const Node &node)

Detailed Description

A vector of edges to child nodes, sorted by edge child node character value, and a bool indicating whether or not a word terminates at this node.

Member Function Documentation

test()

const Node * trie::Node::test

(

const char

c

)

const

Test if a node has an edge containing the character c.

Note

We use linear search here. Could use binary search. For the English alphabet, nodes tend to be fairly sparse and small, especially once beyond the first few letters. On the massive_wordsearch benchmark, using binary search is noticably (~8%) slower.

---

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

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