dictionary_std_set::DictionaryStdSet Class Reference

Naive implementation that stores the dictionary in a std::set. More...

#include <dictionary_std_set.hpp>

Public Member Functions
	DictionaryStdSet (DictionaryStdSet &&)=default
DictionaryStdSet &	operator= (DictionaryStdSet &&)=default
	DictionaryStdSet (const DictionaryStdSet &)=delete
DictionaryStdSet &	operator= (const DictionaryStdSet &)=delete
	DictionaryStdSet (const std::initializer_list< std::string_view > &words)
	DictionaryStdSet (const std::initializer_list< std::string > &words)
	DictionaryStdSet (const std::initializer_list< const char * > &words)
template<class Iterator1 , class Iterator2 , std::enable_if_t< std::is_same_v< typename std::iterator_traits< Iterator1 >::value_type, std::string_view >, int > = 0>
	DictionaryStdSet (Iterator1 first, const Iterator2 last)
	Constructor that does the work if given a range of std::string_views. More...
template<class Iterator1 , class Iterator2 , std::enable_if_t< !std::is_same_v< typename std::iterator_traits< Iterator1 >::value_type, std::string_view >, int > = 0>
	DictionaryStdSet (Iterator1 first, const Iterator2 last)
	Constructor that does the work.
template<class ForwardRange >
	DictionaryStdSet (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::set< std::string >::const_iterator

Private Attributes
std::set< std::string, std::less< void > >	dict_

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

Detailed Description

Naive implementation that stores the dictionary in a std::set.

contains() is log(n), but further() returns a large number of false positives as we cannot do better, which is a lot of wasted work.

Constructor & Destructor Documentation

DictionaryStdSet()

template<class Iterator1 , class Iterator2 , std::enable_if_t< !std::is_same_v< typename std::iterator_traits< Iterator1 >::value_type, std::string_view >, int > >

dictionary_std_set::DictionaryStdSet::DictionaryStdSet	(	Iterator1	first,
		const Iterator2	last
	)

Constructor that does the work if given a range of std::string_views.

Disgusting but necessary as string_view cannot be implicitly converted to string

Member Function Documentation

contains()

bool dictionary_std_set::DictionaryStdSet::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_set::DictionaryStdSet::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_set::DictionaryStdSet::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.

Member Data Documentation

dict_

std::set<std::string, std::less<void> > dictionary_std_set::DictionaryStdSet::dict_

private

Note

Needs "transparent" comparator to be able to search up std::string_view in a set of strings, hence the std::less<void> specialisation

---

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

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