#include $"$pch$.$h$"$

#include "MarkovChain.h$"$

#include

#include

#include

#include

#include

#include

#include

#include $//$ For std::min

using namespace std;

string pickRandomWord$($const wordsAndCounts$\_$t& wordsAndCounts$)\{$

unsigned int totalTickets $=0$;

for $($const auto& pair : wordsAndCounts$)\{$

totalTickets $+=$ pair.second;

$\}$

if $($totalTickets $==0)\{$

throw runtime$\_$error$("$No words to pick from."$)$;

$\}$

unsigned int winningTicket $=$ rand$()\%$ totalTickets;

unsigned int currentTicket $=0$;

for $($const auto& pair : wordsAndCounts$)\{$

currentTicket $+=$ pair.second;

if $($winningTicket $<$ currentTicket$)\{$

return pair.first;

$\}$

$\}$

throw runtime$\_$error$("$Failed to pick a random word."$)$;

$\}$

void MarkovChain::initializeChains$($const vector& words$)\{$

size$\_$t end $=($order $==0)?$ words.size$()$ : words.size$()-$ order;

for $($size$\_$t i $=0$; i $<$ end; $++$i$)\{$

vector key;

$//$ Create N$-$grams if order isn't $0$

if $($order $>0)\{$

key.assign$($words$.$begin$()+$ i$,$ words.begin$()+$ i $+$ order$)$;

$\}$

$//$ Determine the next word and increment the chain

string nextWord $=($order $==0)?$ words$[$i$]$ : words$[$i $+$ order$]$;

chains$[$key$][$nextWord$]++$;

$\}$

$//$ For order $0,$ the key should be an empty vector

if $($order $==0)\{$

vector emptyKey;

for $($const auto& word : words$)\{$

chains$[$emptyKey$][$word$]++$;

$\}$

$\}$

$\}$

string MarkovChain::generateText$($const unsigned int length$)$ const $\{$

if $($chains$.$empty$())\{$

throw EmptyMarkovChainException$()$; $//$ Throw exception if chains are not initialized

$\}$

vector generatedText;

unsigned int maxLength $=$ min$($length$,100$U$)$;

if $($order $==0)\{$

$//$ Directly generate random words from the source text for $0-$grams

const auto& wordMap $=$ chains.at$(\{\})$;

if $($wordMap$.$empty$())\{$

throw runtime$\_$error$("$No words available for zero$-$order generation."$)$;

$\}$

vector allWords;

for $($const auto& pair : wordMap$)\{$

for $($unsigned int i $=0$; i $<$ pair.second; $++$i$)\{$

allWords.push$\_$back$($pair$.$first$)$;

$\}$

$\}$

for $($unsigned int i $=0$; i $<$ maxLength; $++$i$)\{$

string nextWord $=$ allWords$[$rand$()\%$ allWords.size$()]$;

generatedText.push$\_$back$($nextWord$)$;

$\}$

$\}$

else $\{$

$//$ Initialize with a random n$-$gram

auto it $=$ chains.begin$()$;

advance$($it$,$ rand$()\%$ chains.size$())$;

vector currentNgram $=$ it$->$first;

generatedText.insert$($generatedText$.$end$(),$ currentNgram.begin$(),$ currentNgram.end$())$;

while $($generatedText$.$size$()<$ maxLength$)\{$

auto nextWordsIt $=$ chains.find$($currentNgram$)$;

if $($nextWordsIt $==$ chains.end$()||$ nextWordsIt$->$second.empty$())\{$

break; $//$ No possible next words

$\}$

string nextWord $=$ pickRandomWord$($nextWordsIt$->$second$)$;

generatedText.push$\_$back$($nextWord$)$;

$//$ Cycle to the next n$-$gram

currentNgram.erase$($currentNgram$.$begin$())$;

currentNgram.push$\_$back$($nextWord$)$;

$\}$

$\}$

$//$ Join generated words into a single string

stringstream result;

for $($size$\_$t i $=0$; i $<$ generatedText.size$()$; $++$i$)\{$

if $($i $!=0)\{$

result $<<""$;

$\}$

result $<<$ generatedText$[$i$]$;

$\}$

return result.str$()$;

$\}$

vector readCorpus$($const string fileName$)\{$

ifstream file$($fileName$)$;

if $(!$file.is$\_$open$())\{$

cerr $<<$ "Unable to open file" $<<$ endl;

throw runtime$\_$error$("$Could not open file"$)$;

$\}$

vector words;

string word;

while $($file $>>$ word$)\{$

words.push$\_$back$($word$)$;

$\}$

file.close$()$;

return words;

$\}$TEST$($GenerationTest$,$ RejectsOverfitting$)\{$

srand$(0)$;

MarkovChain mc$(10)$;

const vector words $=$ readCorpus$("$corpus$\_$small.txt$")$;

mc$.$initializeChains$($words$)$;

ASSERT$\_$THROW$(\{$

try $\{$

mc$.$generateText$(100)$;

$\}$ catch $($const OverfittingException& e$)\{$

$//$ and this tests that it has the correct message

ASSERT$\_$STREQ$("$Order was too high! Overfitting occured. Only one candidate was available at each step.", e$.$what$())$;

throw;

$\}$

$\},$ OverfittingException$)$;

$\}$

The code is failing these two test

TEST$($GenerationTest$,$ Generate$0$Grams$)\{$

srand$(0)$;

MarkovChain mc$(0)$;

const vector words $=$ readCorpus$("$corpus$\_$small.txt$")$;

mc$.$initializeChains$($words$)$;

const auto& chains $=$ mc$.$getChains$()$;

ASSERT$\_$EQ$($chains$.$size$(),1)<<$ "Expected $0-$grams chains to have a single key.";

const auto numUniqueWords $=$ set$($words$.$begin$(),$ words.end$()).$size$()$;

const auto onlyValueSize $=$ chains.at$(\{\}).$size$()$;

ASSERT$\_$EQ$($numUniqueWords$,$ onlyValueSize$)<<"0-$grams chain empty vector value should be the size of the words, which is $"<<$ numU