Struct toipe::textgen::RawWordSelector

pub struct RawWordSelector<T> { /* private fields */ }

Efficient selector of words from a word list.

The word list is given by a BufReader.

Assumptions

The word list is assumed to:

• Have a list of words separated by newline.
• Use only English alphabet and ASCII.
• Be sorted alphabetically.
  • In case-insensitive manner.
  • For example, both “Apple” and “apple” must appear before words started with “b”.
• Be a file that is not modified while the object is alive.
• Have no empty lines except at the end of the file.

Note: only words between length 2 and 8, inclusive, are considered. Having no words matching the criteria may lead to an infinite loop.

Algorithm

During initialization, the RawWordSelector iterates through all the words in the list and builds an index mapping each letter (of the alphabet) to its byte position in the file and the cumulative number of words present starting with it.

To select a (pesudo-)random word, a random number between 0 (inclusive) and number of lines (exclusive) is generated. Using binary search, the index of where this number lies in the cumulative no. of words list is found. Using this index, the byte offset of the corresponding letter is found. The file is then read starting from this byte offset and read line-by-line until the correct word (at line number - cumulative num. words from the starting of this letter).

Time complexity

Initialization: O(n)

Selecting a word: O(1) (best case) or O(n) (worst case)

Space complexity

O(1) (only needs fixed length arrays).

Implementations

impl<T: Seek + Read> RawWordSelector<T>

pub fn new(reader: BufReader<T>) -> Result<Self, Error>

Create from any arbitrary BufReader.

Please ensure that assumptions defined at RawWordSelector are valid for the contents.

impl RawWordSelector<File>

pub fn from_path(word_list_path: PathBuf) -> Result<Self, Error>

Create from a file at a path given by a PathBuf.

Please ensure that assumptions defined at RawWordSelector are valid for this file.

impl RawWordSelector<Cursor<String>>

pub fn from_string(word_list: String) -> Result<Self, Error>

Create from a String representing the word list file.

Please ensure that assumptions defined at RawWordSelector are valid for the contents.

Trait Implementations

impl<T: Debug> Debug for RawWordSelector<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Seek + Read> WordSelector for RawWordSelector<T>

fn new_word(&mut self) -> Result<String, Error>

Returns a new word.

fn new_words(&mut self, num_words: usize) -> Result<Vec<String>, Error>

Returns a Vec containing num_words words.