dictionary_std_vector::DictionaryStdVector Class Reference

Solver implementation using a sorted std::vector. More...

#include <dictionary_std_vector.hpp>

Public Member Functions
	DictionaryStdVector (DictionaryStdVector &&)=default
DictionaryStdVector &	operator= (DictionaryStdVector &&)=default
	DictionaryStdVector (const DictionaryStdVector &)=delete
DictionaryStdVector &	operator= (const DictionaryStdVector &)=delete
	DictionaryStdVector (const std::initializer_list< std::string_view > &words)
	DictionaryStdVector (const std::initializer_list< std::string > &words)
	DictionaryStdVector (const std::initializer_list< const char * > &words)
template<class Iterator1 , class Iterator2 >
	DictionaryStdVector (Iterator1 first, const Iterator2 last)
	Actual constructor that does the work.
template<class ForwardRange >
	DictionaryStdVector (const ForwardRange &words)
std::size_t	size () const
bool	empty () const
template<class OutputIndexIterator >
void	contains_further (const std::string_view stem, const std::string_view suffixes, OutputIndexIterator 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...
bool	contains (const std::string_view word) const
	Check if this dictionary contains word. More...
bool	further (const std::string_view word) const
	Check if this dictionary might contain words with word as a prefix. More...

Private Types
using	Iterator = std::vector< std::string >::const_iterator

Private Member Functions
bool	further_impl (const std::string_view key, Iterator first, Iterator last) const

Private Attributes
std::vector< std::string >	dict_

Friends
std::ostream &	operator<< (std::ostream &, const DictionaryStdVector &)

Detailed Description

Solver implementation using a sorted std::vector.

contains() is O(log(n)) further() is more complicated, and suffers from being unable to definitively determine whether there may be further words. O(log(n))

Significantly faster than the std::set based solver dictionary implementation due to an optimisation where we find the upper limit of a search, see calc_stop() and contains_further(). Still significantly slower than any of the actual tries.

Member Function Documentation

contains()

bool dictionary_std_vector::DictionaryStdVector::contains

(

const 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 OutputIndexIterator >

void dictionary_std_vector::DictionaryStdVector::contains_further	(	const std::string_view	stem,
		const std::string_view	suffixes,
		OutputIndexIterator	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 dictionary_std_vector::DictionaryStdVector::further

(

const 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.

---

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

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