<?php

	class Markov {
		protected $words = array();
		protected $cache = array();

		public function compile($source) {
			preg_match_all('([^\s(){}\[\]]+)', $source, $words);

			$words = $words[0];
			$length = count($words) - 3;
			$sets = array(); $progress = 0;

			while ($progress < $length) {
				$count = 0; $set = array();

				while ($count < 3) {
					$set[] = $words[$progress + $count]; $count++;
				}

				$sets[] = $set; $progress++;
			}

			foreach ($sets as $key) {
				$value = array_pop($key);
				$key = implode(' ', $key);

				if (isset($this->cache[$key])) {
					$this->cache[$key][] = $value;
				}

				else {
					$this->cache[$key] = array($value);
				}
			}

			$this->words = $words;
		}

		public function generate($length) {
			$index = $this->chooseFirst();
			$word_a = $this->words[$index];
			$word_b = $this->words[$index + 1];
			$count = 0; $size = $length * 8;
			$output = array();

			while ($count++ < $size) {
				$output[] = $word_a;

				if (preg_match('/[.!?]$/', $word_a)) {
					if (count($output) > $length) break;

					$index = $this->chooseFirst();
					$word_a = $this->words[$index];
					$word_b = $this->words[$index + 1];
				}

				else {
					$cache = $this->cache["{$word_a} {$word_b}"];
					$word_c = $cache[array_rand($cache)];
					$word_a = $word_b;
					$word_b = $word_c;
				}
			}

			return $output;
		}

		public function chooseFirst() {
			$choices = array();

			foreach ($this->words as $index => $word) {
				if (preg_match('/^[A-Z].*[^.!?]$/', $word)) {
					$choices[] = $index;
				}
			}

			return $choices[array_rand($choices)];
		}
	}

	$markov = new Markov(3);
	$markov->compile(file_get_contents('./markov3.txt'));
	$words = $markov->generate(100);

	echo '<p style="width: 30em;">', implode(' ', $words), '</p>';

?>