Starts near-complete rewrite for code improvement.

5 files changed, 671 insertions, 707 deletions

diff --git a/src/core/CMakeLists.txt b/src/core/CMakeLists.txt
index a8ec17e..af5ca65 100644
--- a/src/core/CMakeLists.txt
+++ b/src/core/CMakeLists.txt
@@ -3,7 +3,7 @@ set(
    ${CMAKE_CURRENT_SOURCE_DIR}/main.c
    ${CMAKE_CURRENT_SOURCE_DIR}/knowledge.c
    ${CMAKE_CURRENT_SOURCE_DIR}/assimilate.c
-   ${CMAKE_CURRENT_SOURCE_DIR}/create_sentences.c
+   ${CMAKE_CURRENT_SOURCE_DIR}/create_sequence.c
    ${CMAKE_CURRENT_SOURCE_DIR}/sequence.c
 )
 
diff --git a/src/core/create_sentences.c b/src/core/create_sentences.c
deleted file mode 100644
index 93444a7..0000000
--- a/src/core/create_sentences.c
+++ /dev/null
@@ -1,706 +0,0 @@
-#include <stdlib.h>
-#include <stdio.h>
-#include <string.h>
-#include <stdint.h> /* defines SIZE_MAX */
-
-#include "../io/error.h"
-
-#include "knowledge.h"
-
-/** Functions to create sentences using a ZoO_knowledge structure *************/
-
-/*
- * Returns the index of a element in {links} chosen randomly according
- * to the distribution in {links_occurrences}.
- * Pre:
- *    (!= occurrences 0).
- *    (== (length links_occurrences) (length links)).
- *    (== (sum links_occurrences) occurrences).
- *    (can_store ZoO_index (length links)).
- */
-static ZoO_index pick_index
-(
-   ZoO_index const occurrences,
-   const ZoO_index links_occurrences [const restrict static 1]
-)
-{
-   ZoO_index result, accumulator, random_number;
-
-   result = 0;
-
-   /*
-    * Safe:
-    * (> (length links_occurrences) 0).
-    */
-   accumulator = links_occurrences[0];
-
-   random_number = (((ZoO_index) rand()) % occurrences);
-
-   while (accumulator < random_number)
-   {
-      /*
-       * Safe:
-       * (->
-       *    (and
-       *       (== accumulator (sum links_occurrences[0:result]))
-       *       (< accumulator random_number)
-       *       (< random_number occurrences)
-       *       (== occurrences (sum links_occurrences))
-       *       (can_store ZoO_index (length links))
-       *       (== (length links_occurrences) (length links))
-       *    )
-       *    (and
-       *       (< result' (length links_occurrences))
-       *       (can_store ZoO_index result')
-       *       (=< accumulator' occurrences)
-       *    )
-       * )
-       */
-      result += 1;
-      accumulator += links_occurrences[result];
-   }
-
-   /* Safe: (< result (length links)) */
-   return result;
-}
-
-static unsigned char * extend_left
-(
-   struct ZoO_knowledge k [const restrict static 1],
-   ZoO_index sequence [const restrict static ZoO_MARKOV_ORDER],
-   ZoO_char current_sentence [static 1],
-   size_t sentence_size [const restrict static 1],
-   ZoO_index credits [const static 1]
-)
-{
-   size_t addition_size;
-   struct ZoO_knowledge_word * w;
-   ZoO_char * next_sentence;
-   ZoO_index j;
-
-   /* prevents current_sentence [restrict] */
-   next_sentence = current_sentence;
-
-   for (;;)
-   {
-      if (*credits == 0)
-      {
-         return current_sentence;
-      }
-
-      *credits -= 1;
-
-      w = (k->words + sequence[ZoO_MARKOV_ORDER - 1]);
-
-      switch (w->special)
-      {
-         case ZoO_WORD_HAS_NO_EFFECT:
-            /* FIXME: not overflow-safe. */
-            /* word also contains an '\0', which we will replace by a ' ' */
-            addition_size = w->word_size;
-            break;
-
-         case ZoO_WORD_ENDS_SENTENCE:
-            ZoO_S_WARNING("END OF LINE should not be prefixable.");
-            return current_sentence;
-
-         case ZoO_WORD_STARTS_SENTENCE:
-            return current_sentence;
-
-         case ZoO_WORD_REMOVES_LEFT_SPACE:
-         case ZoO_WORD_REMOVES_RIGHT_SPACE:
-            /* word also contains an '\0', which we will remove. */
-            addition_size = w->word_size - 1;
-            break;
-      }
-
-      if (*sentence_size > (SIZE_MAX - addition_size))
-      {
-         ZoO_S_WARNING
-         (
-            "Sentence construction aborted to avoid size_t overflow."
-         );
-
-         return current_sentence;
-      }
-
-      next_sentence =
-         (ZoO_char *) calloc
-         (
-            /* overflow-safe */
-            (*sentence_size + addition_size),
-            sizeof(ZoO_char)
-         );
-
-      if (next_sentence == (ZoO_char *) NULL)
-      {
-         ZoO_S_ERROR("Could not allocate memory to store new sentence.");
-
-         return current_sentence;
-      }
-
-      /* overflow-safe */
-      *sentence_size = (*sentence_size + addition_size);
-
-      switch (w->special)
-      {
-         case ZoO_WORD_HAS_NO_EFFECT:
-            snprintf
-            (
-               next_sentence,
-               *sentence_size,
-               " " ZoO_CHAR_STRING_SYMBOL ZoO_CHAR_STRING_SYMBOL,
-               w->word,
-               current_sentence
-            );
-            break;
-
-         case ZoO_WORD_REMOVES_LEFT_SPACE:
-            snprintf
-            (
-               next_sentence,
-               *sentence_size,
-               ZoO_CHAR_STRING_SYMBOL ZoO_CHAR_STRING_SYMBOL,
-               w->word,
-               current_sentence
-            );
-            break;
-
-         case ZoO_WORD_REMOVES_RIGHT_SPACE:
-            snprintf
-            (
-               next_sentence,
-               *sentence_size,
-               ZoO_CHAR_STRING_SYMBOL ZoO_CHAR_STRING_SYMBOL,
-               w->word,
-               /* Safe: strlen(current_sentence) >= 2 */
-               (current_sentence + 1)
-            );
-            break;
-
-         default:
-            /* TODO: PROGRAM LOGIC ERROR */
-            break;
-      }
-
-      free((void *) current_sentence);
-
-      /* prevents current_sentence [const] */
-      current_sentence = next_sentence;
-
-      memmove
-      (
-         (void *) (sequence + 1),
-         (const void *) sequence,
-         /* Accepts 0. */
-         (sizeof(ZoO_index) * (ZoO_MARKOV_ORDER - 1))
-      );
-
-      if
-      (
-         ZoO_knowledge_find_link
-         (
-            w->backward_links_count,
-            w->backward_links,
-            (sequence + 1),
-            &j
-         )
-         < 0
-      )
-      {
-         ZoO_S_ERROR("Unexpectedly, no backtracking link was found.");
-
-         break;
-      }
-
-      sequence[0] =
-         w->backward_links[j].targets
-         [
-            pick_index
-            (
-               w->backward_links[j].occurrences,
-               w->backward_links[j].targets_occurrences
-            )
-         ];
-
-      /* prevents current_sentence [const] */
-      current_sentence = next_sentence;
-   }
-}
-
-static unsigned char * extend_right
-(
-   struct ZoO_knowledge k [const restrict static 1],
-   ZoO_index sequence [const restrict static ZoO_MARKOV_ORDER],
-   ZoO_char current_sentence [static 1],
-   size_t sentence_size [const restrict static 1],
-   ZoO_index credits [const static 1]
-)
-{
-   size_t addition_size;
-   struct ZoO_knowledge_word * w;
-   ZoO_char * next_sentence;
-   ZoO_index j;
-
-   /* prevents current_sentence [restrict] */
-   next_sentence = current_sentence;
-
-   for (;;)
-   {
-      if (*credits == 0)
-      {
-         return current_sentence;
-      }
-
-      *credits -= 1;
-
-      w = (k->words + sequence[0]);
-
-      switch (w->special)
-      {
-         case ZoO_WORD_HAS_NO_EFFECT:
-            /* FIXME: Assumed to be overflow-safe. */
-            /* word also contains an '\0', which we will replace by a ' '. */
-            addition_size = w->word_size;
-            break;
-
-         case ZoO_WORD_ENDS_SENTENCE:
-            return current_sentence;
-
-         case ZoO_WORD_STARTS_SENTENCE:
-            ZoO_S_WARNING("START OF LINE should not be suffixable.");
-            return current_sentence;
-
-         case ZoO_WORD_REMOVES_LEFT_SPACE:
-         case ZoO_WORD_REMOVES_RIGHT_SPACE:
-            /* word also contains an '\0', which we will remove. */
-            addition_size = w->word_size - 1;
-            break;
-      }
-
-      if (*sentence_size > (SIZE_MAX - addition_size))
-      {
-         ZoO_S_WARNING
-         (
-            "Sentence construction aborted to avoid size_t overflow."
-         );
-
-         return current_sentence;
-      }
-
-      next_sentence =
-         (ZoO_char *) calloc
-         (
-            /* overflow-safe */
-            (*sentence_size + addition_size),
-            sizeof(ZoO_char)
-         );
-
-      if (next_sentence == (ZoO_char *) NULL)
-      {
-         ZoO_S_ERROR("Could not allocate memory to store new sentence.");
-
-         return current_sentence;
-      }
-
-      /* overflow-safe */
-      *sentence_size = (*sentence_size + addition_size);
-
-      switch (w->special)
-      {
-         case ZoO_WORD_REMOVES_LEFT_SPACE:
-            current_sentence[*sentence_size - addition_size - 2] = '\0';
-
-         case ZoO_WORD_HAS_NO_EFFECT:
-            snprintf
-            (
-               next_sentence,
-               *sentence_size,
-               ZoO_CHAR_STRING_SYMBOL ZoO_CHAR_STRING_SYMBOL " ",
-               current_sentence,
-               w->word
-            );
-            break;
-
-         case ZoO_WORD_REMOVES_RIGHT_SPACE:
-            snprintf
-            (
-               next_sentence,
-               *sentence_size,
-               ZoO_CHAR_STRING_SYMBOL ZoO_CHAR_STRING_SYMBOL,
-               current_sentence,
-               w->word
-            );
-            break;
-
-         default:
-            /* TODO: PROGRAM LOGIC ERROR */
-            break;
-      }
-
-      free((void *) current_sentence);
-
-      /* prevents current_sentence [const] */
-      current_sentence = next_sentence;
-
-      memmove
-      (
-         (void *) sequence,
-         (const void *) (sequence + 1),
-         /* Accepts 0. */
-         (sizeof(ZoO_index) * (ZoO_MARKOV_ORDER - 1))
-      );
-
-      if
-      (
-         ZoO_knowledge_find_link
-         (
-            w->forward_links_count,
-            w->forward_links,
-            sequence,
-            &j
-         )
-         < 0
-      )
-      {
-         ZoO_S_ERROR("Unexpectedly, no forward link was found.");
-
-         break;
-      }
-
-      sequence[ZoO_MARKOV_ORDER - 1] =
-         w->forward_links[j].targets
-         [
-            pick_index
-            (
-               w->forward_links[j].occurrences,
-               w->forward_links[j].targets_occurrences
-            )
-         ];
-   }
-}
-
-static ZoO_index select_first_word
-(
-   struct ZoO_knowledge k [const static 1],
-   const struct ZoO_strings string [const],
-   ZoO_index const aliases_count,
-   const char * restrict aliases [const restrict static aliases_count]
-)
-{
-   ZoO_index i, j, word_id, word_min_score, word_min_id;
-   ZoO_index word_found;
-
-   if (string == (struct ZoO_strings *) NULL)
-   {
-      return word_min_id = (rand() % k->words_count);
-   }
-
-   word_found = 0;
-
-   for (i = 0; i < string->words_count; ++i)
-   {
-      for (j = 0; j < aliases_count; ++j)
-      {
-         if (ZoO_IS_PREFIX(aliases[j], string->words[i]))
-         {
-            goto NEXT_WORD;
-         }
-      }
-
-      /* prevents k [restrict] */
-      if (ZoO_knowledge_find(k, string->words[i], &word_min_id) == 0)
-      {
-         word_found = 1;
-         word_min_score = k->words[word_min_id].occurrences;
-
-         break;
-      }
-
-      NEXT_WORD:;
-   }
-
-   if (word_found == 0)
-   {
-      return word_min_id = (rand() % k->words_count);
-   }
-
-   for (; i < string->words_count; ++i)
-   {
-      for (j = 0; j < aliases_count; ++j)
-      {
-         if (ZoO_IS_PREFIX(aliases[j], string->words[i]))
-         {
-            goto NEXT_WORD_BIS;
-         }
-      }
-
-      if
-      (
-         (ZoO_knowledge_find(k, string->words[i], &word_id) == 0)
-         && (k->words[word_id].occurrences < word_min_score)
-      )
-      {
-         word_min_score = k->words[word_id].occurrences;
-         word_min_id = word_id;
-      }
-
-      NEXT_WORD_BIS:;
-   }
-
-   return word_min_id;
-}
-
-static void init_sequence
-(
-   struct ZoO_knowledge k [const static 1],
-   const struct ZoO_strings string [const],
-   ZoO_index const aliases_count,
-   const char * restrict aliases [const restrict static aliases_count],
-   ZoO_index sequence [const static (ZoO_MARKOV_ORDER * 2) + 1]
-)
-{
-   ZoO_index i, j, accumulator, random_number;
-   struct ZoO_knowledge_word * fiw;
-
-   sequence[ZoO_MARKOV_ORDER] =
-      select_first_word(
-         k,
-         string,
-         aliases_count,
-         aliases
-      );
-
-   fiw = (k->words + sequence[ZoO_MARKOV_ORDER]);
-
-   for (i = 0; i < ZoO_MARKOV_ORDER; ++i)
-   {
-      sequence[ZoO_MARKOV_ORDER - i - 1] = ZoO_WORD_START_OF_LINE;
-      sequence[ZoO_MARKOV_ORDER + i + 1] = ZoO_WORD_END_OF_LINE;
-   }
-
-   if (fiw->forward_links_count == 0)
-   {
-      ZoO_S_FATAL("First word has no forward links.");
-
-      return;
-   }
-
-   /* Chooses a likely forward link for the pillar. */
-   i = 0;
-   accumulator = fiw->forward_links[0].occurrences;
-
-   random_number = (((ZoO_index) rand()) % fiw->occurrences);
-
-   while (accumulator < random_number)
-   {
-      accumulator += fiw->forward_links[i].occurrences;
-      i += 1;
-   }
-
-/*   i = (((ZoO_index) rand()) % fiw->forward_links_count); */
-
-   /* Copies the forward link data into the sequence. */
-   /* This adds (ZoO_MARKOV_ORDER - 1) words, as the ZoO_MARKOV_ORDERth word */
-   /* is chosen aftewards. */
-   memcpy
-   (
-      (void *) (sequence + ZoO_MARKOV_ORDER + 1),
-      fiw->forward_links[i].sequence,
-      sizeof(ZoO_index) * (ZoO_MARKOV_ORDER - 1)
-   );
-
-   /* selects the last word */
-   sequence[ZoO_MARKOV_ORDER * 2] =
-      fiw->forward_links[i].targets
-      [
-         pick_index
-         (
-            fiw->forward_links[i].occurrences,
-            fiw->forward_links[i].targets_occurrences
-         )
-      ];
-
-   /* FIXME: Not clear enough. */
-   /* Now that we have the right side of the sequence, we are going to */
-   /* build the left one, one word at a time. */
-   for (i = 0; i < ZoO_MARKOV_ORDER; ++i)
-   {
-      /* temporary pillar (starts on the right side, minus one so we don't */
-      fiw = (k->words + sequence[(ZoO_MARKOV_ORDER * 2) - i - 1]);
-
-      if
-      (
-         /* finds the backward link corresponding to the words left of the */
-         /* temporary pillar. */
-         ZoO_knowledge_find_link
-         (
-            fiw->backward_links_count,
-            fiw->backward_links,
-            sequence + (ZoO_MARKOV_ORDER - i),
-            &j
-         )
-         < 0
-      )
-      {
-         ZoO_ERROR
-         (
-            "Unexpectedly, no back link was found at i=%u, expected to find"
-            "a backlink with %s, from %s.",
-            i,
-            k->words[sequence[(ZoO_MARKOV_ORDER - i)]].word,
-            fiw->word
-         );
-         ZoO_S_ERROR("Sequence was:");
-
-         for (j = 0; j <= (ZoO_MARKOV_ORDER * 2); ++j)
-         {
-            ZoO_ERROR("[%u] %s", j, k->words[sequence[j]].word);
-         }
-
-         break;
-      }
-
-      sequence[ZoO_MARKOV_ORDER - i - 1] =
-         fiw->backward_links[j].targets
-         [
-            pick_index
-            (
-               fiw->backward_links[j].occurrences,
-               fiw->backward_links[j].targets_occurrences
-            )
-         ];
-   }
-}
-
-int ZoO_knowledge_extend
-(
-   struct ZoO_knowledge k [const static 1],
-   const struct ZoO_strings string [const],
-   ZoO_index const aliases_count,
-   const char * restrict aliases [const restrict static aliases_count],
-   ZoO_char * result [const static 1]
-)
-{
-   int word_found;
-   size_t sentence_size;
-   ZoO_index sequence[(ZoO_MARKOV_ORDER * 2) + 1];
-   ZoO_index first_word, credits;
-
-   credits = ZoO_MAX_REPLY_WORDS;
-
-   init_sequence(k, string, aliases_count, aliases, sequence);
-
-   first_word = sequence[ZoO_MARKOV_ORDER];
-
-   /* 3: 2 spaces + '\0' */
-   /* FIXME: not overflow-safe */
-   switch (k->words[first_word].special)
-   {
-      case ZoO_WORD_REMOVES_LEFT_SPACE:
-      case ZoO_WORD_REMOVES_RIGHT_SPACE:
-         /* word + ' ' + '\0' */
-         sentence_size = (strlen(k->words[first_word].word) + 2);
-         break;
-
-      case ZoO_WORD_HAS_NO_EFFECT:
-         /* word + ' ' * 2 + '\0' */
-         sentence_size = (strlen(k->words[first_word].word) + 3);
-         break;
-
-      default:
-         ZoO_WARNING
-         (
-            "'%s' was unexpectedly selected as pillar.",
-            k->words[first_word].word
-         );
-         /* word + '[' + ']' + ' ' * 2 + '\0' */
-         sentence_size = (strlen(k->words[first_word].word) + 5);
-         break;
-   }
-
-   *result = (ZoO_char *) calloc(sentence_size, sizeof(ZoO_char));
-
-   if (*result == (ZoO_char *) NULL)
-   {
-      ZoO_S_ERROR("Could not allocate memory to start sentence.");
-
-      return -2;
-   }
-
-   switch (k->words[first_word].special)
-   {
-      case ZoO_WORD_REMOVES_LEFT_SPACE:
-         snprintf
-         (
-            *result,
-            sentence_size,
-            ZoO_CHAR_STRING_SYMBOL " ",
-            k->words[first_word].word
-         );
-         break;
-
-      case ZoO_WORD_REMOVES_RIGHT_SPACE:
-         snprintf
-         (
-            *result,
-            sentence_size,
-            " " ZoO_CHAR_STRING_SYMBOL,
-            k->words[first_word].word
-         );
-         break;
-
-      case ZoO_WORD_HAS_NO_EFFECT:
-         snprintf
-         (
-            *result,
-            sentence_size,
-            " " ZoO_CHAR_STRING_SYMBOL " ",
-            k->words[first_word].word
-         );
-         break;
-
-      default:
-         snprintf
-         (
-            *result,
-            sentence_size,
-            " [" ZoO_CHAR_STRING_SYMBOL "] ",
-            k->words[first_word].word
-         );
-         break;
-   }
-
-   /* prevents result [restrict] */
-   *result =
-      extend_right
-      (
-         k,
-         (sequence + ZoO_MARKOV_ORDER + 1),
-         *result,
-         &sentence_size,
-         &credits
-      );
-
-   if (*result == (ZoO_char *) NULL)
-   {
-      return -2;
-   }
-
-   *result =
-      extend_left
-      (
-         k,
-         sequence,
-         *result,
-         &sentence_size,
-         &credits
-      );
-
-   if (*result == (ZoO_char *) NULL)
-   {
-      return -2;
-   }
-
-   return 0;
-}
diff --git a/src/core/create_sequence.c b/src/core/create_sequence.c
new file mode 100644
index 0000000..a7b96f9
--- /dev/null
+++ b/src/core/create_sequence.c
@@ -0,0 +1,654 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <stdint.h> /* defines SIZE_MAX */
+
+#include "../io/error.h"
+
+#include "../core/index.h"
+
+#include "knowledge.h"
+
+/*
+ * Returns a randomly chosen index pointing to a element in {weights}.
+ * The values of {weights} are used as weights to guide the choice.
+ * Returns:
+ *    Value in [0, (length weights)[.
+ * Pre:
+ *    (> weights_sum 0).
+ *    (= (sum weights) weights_sum).
+ */
+static ZoO_index weighted_random_pick
+(
+   const ZoO_index weights [const restrict static 1],
+   const ZoO_index weights_sum
+)
+{
+   ZoO_index result, accumulator, random_number;
+
+   accumulator = 0;
+
+   /* Safe: Included in [0, weights_sum]. */
+   random_number = ZoO_index_random_up_to(weights_sum);
+
+   for (result = 0; accumulator < random_number; ++result)
+   {
+      /* Safe: (= (sum weights) weights_sum) */
+      accumulator += weights[result];
+   }
+
+   return result;
+}
+
+/*
+ * FIXME: This does not belong here.
+ * Calculates the size the sentence will have upon addition of the word, taking
+ * into account {effect}.
+ * Returns:
+ *    0 on success.
+ *    -1 iff adding the word would overflow {sentence_size}.
+ * Post:
+ *    (initialized new_size)
+ */
+static int get_new_size
+(
+   const size_t word_size,
+   const size_t sentence_size,
+   const enum ZoO_knowledge_special_effect effect,
+   size_t new_size [const restrict static 1]
+)
+{
+   size_t added_size;
+
+   switch (effect)
+   {
+      case ZoO_WORD_HAS_NO_EFFECT:
+         /* word also contains an '\0', which we will replace by a ' ' */
+         added_size = word_size;
+         break;
+
+      case ZoO_WORD_ENDS_SENTENCE:
+      case ZoO_WORD_STARTS_SENTENCE:
+         added_size = 0;
+         break;
+
+      case ZoO_WORD_REMOVES_LEFT_SPACE:
+      case ZoO_WORD_REMOVES_RIGHT_SPACE:
+         /* word also contains an '\0', which we will remove. */
+         added_size = (word_size - 1);
+         break;
+   }
+
+   if ((SIZE_MAX - word_size) > sentence_size)
+   {
+      /* New size Would overflow. */
+      *new_size = sentence_size;
+
+      return -1;
+   }
+
+   /* Safe: (=< SIZE_MAX (+ sentence_size added_size)) */
+   *new_size = (sentence_size + added_size);
+
+   return 0;
+}
+
+/******************************************************************************/
+/** ADDING ELEMENTS TO THE LEFT ***********************************************/
+/******************************************************************************/
+
+/*
+ * Adds an id to the left of the sequence.
+ * This requires the reallocation of {sequence}. The freeing of the previous
+ * memory space is handled. If an error happened, {sequence} remain untouched.
+ * Returns:
+ *    0 on success.
+ *    -1 iff adding the word would cause an overflow.
+ *    -2 iff memory allocation was unsuccessful.
+ * Post:
+ *    (initialized {sequence})
+ *    (initialized {*sequence})
+ */
+static int left_append
+(
+   const ZoO_index word_id,
+   ZoO_index * sequence [const restrict],
+   const size_t sequence_size
+)
+{
+   ZoO_index * new_sequence;
+
+   if ((SIZE_MAX - sizeof(ZoO_index)) > sequence_size)
+   {
+      ZoO_S_ERROR
+      (
+         "Left side append aborted, as the new sequence's size would overflow."
+      );
+
+      return -1;
+   }
+
+   new_sequence = (ZoO_index *) malloc(sizeof(ZoO_index) + sequence_size);
+
+   if (new_sequence == (ZoO_index *) NULL)
+   {
+      ZoO_S_ERROR
+      (
+         "Left side append aborted, as memory for the new sequence could not be"
+         " allocated."
+      );
+
+      return -2;
+   }
+
+   if (sequence_size > 0)
+   {
+      memcpy
+      (
+         (void *) (new_sequence + 1),
+         (const void *) sequence,
+         sequence_size
+      );
+
+      free((void *) sequence);
+   }
+
+   new_sequence[0] = word_id;
+
+   *sequence = new_sequence;
+
+   return 0;
+}
+
+/*
+ * Adds an id to the left of the sequence, according to what is known as likely
+ * to fit there.
+ * This requires the reallocation of {sequence}. The freeing of the previous
+ * memory space is handled. If an error happened, {sequence} remain untouched.
+ * Returns:
+ *    0 on success.
+ *    -1 iff nothing fitting was found.
+ *    -2 iff the addition of that id failed.
+ * Pre:
+ *    (initialized {sequence})
+ *    (initialized {*sequence[0..(MARKOV_ORDER - 1)]})
+ */
+static int extend_left
+(
+   ZoO_index * sequence [const restrict static 1],
+   const size_t sequence_size,
+   const struct ZoO_knowledge k [const restrict static 1]
+)
+{
+   const ZoO_index * restrict preceding_words;
+   const ZoO_index * restrict preceding_words_weights;
+   ZoO_index preceding_words_weights_sum;
+
+   if
+   (
+      ZoO_knowledge_get_preceding_words
+      (
+         k,
+         *sequence,
+         &preceding_words,
+         &preceding_words_weights,
+         &preceding_words_weights_sum
+      ) < 0
+   )
+   {
+      return -1;
+   }
+
+   /* preceding_words_weights_sum > 0 */
+
+   if
+   (
+      left_append
+      (
+         weighted_random_pick
+         (
+            preceding_words_weights,
+            preceding_words_weights_sum
+         ),
+         sequence,
+         sequence_size
+      ) < 0
+   )
+   {
+      return -3;
+   }
+
+   return 0;
+}
+
+static int complete_left_part_of_sequence
+(
+   ZoO_index * sequence [restrict static 1],
+   size_t sequence_size [const restrict static 1],
+   ZoO_index credits [const restrict],
+   const struct ZoO_knowledge k [const restrict static 1]
+)
+{
+   for (;;)
+   {
+      if ((credits == (ZoO_index *) NULL) || (*credits > 0))
+      {
+         if (extend_left(sequence, *sequence_size, k) < 0)
+         {
+            /* We are sure *sequence[0] is defined. */
+            if (*sequence[0] == ZoO_START_OF_SEQUENCE_ID)
+            {
+               /*
+                * We failed to add a word, but it was because none should have
+                * been added.
+                */
+               return 0;
+            }
+            else
+            {
+               return -1;
+            }
+         }
+      }
+      else
+      {
+         /* No more credits available, the sequence will have to start here. */
+         *sequence[0] = ZoO_START_OF_SEQUENCE_ID;
+
+         return 0;
+      }
+
+      /*
+       * Safe: if it was going to overflow, extend_left would have returned a
+       * negative value, making this statement unreachable.
+       */
+      *sequence_size = (*sequence_size + sizeof(ZoO_index));
+
+      if (credits != (ZoO_index *) NULL)
+      {
+         *credits -= 1;
+      }
+
+      /* We are sure *sequence[0] is defined. */
+      switch (*sequence[0])
+      {
+         case ZoO_END_OF_SEQUENCE_ID:
+            ZoO_S_WARNING
+            (
+               "END OF LINE was added at the left part of an sequence."
+            );
+
+            *sequence[0] = ZoO_START_OF_SEQUENCE_ID;
+            return 0;
+
+         case ZoO_START_OF_SEQUENCE_ID:
+            return 0;
+
+         default:
+            break;
+      }
+   }
+}
+
+/******************************************************************************/
+/** ADDING ELEMENTS TO THE RIGHT **********************************************/
+/******************************************************************************/
+
+/*
+ * Adds an id to the right of the sequence.
+ * This requires the reallocation of {sequence}. The freeing of the previous
+ * memory space is handled. If an error happened, {sequence} remain untouched.
+ * Returns:
+ *    0 on success.
+ *    -1 iff adding the word would cause an overflow.
+ *    -2 iff memory allocation was unsuccessful.
+ * Post:
+ *    (initialized {sequence})
+ *    (initialized {*sequence})
+ */
+static int right_append
+(
+   ZoO_index * sequence [const restrict],
+   const ZoO_index word_id,
+   const size_t sequence_size,
+   const ZoO_index sequence_length
+)
+{
+   ZoO_index * new_sequence;
+
+   if ((SIZE_MAX - sizeof(ZoO_index)) > sequence_size)
+   {
+      ZoO_S_ERROR
+      (
+         "Right side append aborted, as the new sequence's size would overflow."
+      );
+
+      return -1;
+   }
+
+   new_sequence =
+      (ZoO_index *) realloc
+      (
+         sequence,
+         (sequence_size + sizeof(ZoO_index))
+      );
+
+   if (new_sequence == (ZoO_index *) NULL)
+   {
+      ZoO_S_ERROR
+      (
+         "Right side append aborted, as memory for the new sequence could not "
+         "be allocated."
+      );
+
+      return -2;
+   }
+
+   new_sequence[sequence_length] = word_id;
+
+   *sequence = new_sequence;
+
+   return 0;
+}
+
+static int extend_right
+(
+   ZoO_index * sequence [const restrict static 1],
+   const size_t sequence_size,
+   const ZoO_index sequence_length,
+   const struct ZoO_knowledge k [const restrict static 1]
+)
+{
+   const ZoO_index * restrict following_words;
+   const ZoO_index * restrict following_words_weights;
+
+   ZoO_index following_words_weights_sum;
+
+   if
+   (
+      ZoO_knowledge_get_following_words
+      (
+         k,
+         *sequence,
+         sequence_length,
+         &following_words,
+         &following_words_weights,
+         &following_words_weights_sum
+      ) < 0
+   )
+   {
+      return -1;
+   }
+
+   /* following_words_weights_sum > 0 */
+
+   if
+   (
+      right_append
+      (
+         sequence,
+         weighted_random_pick
+         (
+            following_words_weights,
+            following_words_weights_sum
+         ),
+         sequence_size,
+         sequence_length
+      ) < 0
+   )
+   {
+      return -3;
+   }
+
+   return 0;
+}
+
+static int complete_right_part_of_sequence
+(
+   ZoO_index * sequence [const restrict static 1],
+   size_t sequence_size [const restrict static 1],
+   ZoO_index credits [const restrict],
+   const struct ZoO_knowledge k [const restrict static 1]
+)
+{
+   ZoO_index sequence_length;
+
+   sequence_length = (*sequence_size / sizeof(ZoO_index));
+
+   for (;;)
+   {
+      if ((credits == (ZoO_index *) NULL) || (*credits > 0))
+      {
+         if (extend_right(sequence, *sequence_size, sequence_length, k) < 0)
+         {
+            /* Safe: (> sequence_length 1) */
+            if (*sequence[(sequence_length - 1)] == ZoO_END_OF_SEQUENCE_ID)
+            {
+               /*
+                * We failed to add a word, but it was because none should have
+                * been added.
+                */
+               return 0;
+            }
+            else
+            {
+               return -1;
+            }
+         }
+      }
+      else
+      {
+         /* No more credits available, we end the sequence. */
+         *sequence[(sequence_length - 1)] = ZoO_END_OF_SEQUENCE_ID;
+
+         return 0;
+      }
+
+      /*
+       * Safe: if it was going to overflow, extend_left would have returned a
+       * negative value, making this statement unreachable.
+       */
+      *sequence_size = (*sequence_size + sizeof(ZoO_index));
+      sequence_length += 1;
+
+      if (credits != (ZoO_index *) NULL)
+      {
+         *credits -= 1;
+      }
+
+      /* Safe: (> sequence_length 1) */
+      switch (*sequence[(sequence_length - 1)])
+      {
+         case ZoO_START_OF_SEQUENCE_ID:
+            ZoO_S_WARNING
+            (
+               "END OF LINE was added at the right part of an sequence."
+            );
+
+            *sequence[(sequence_length - 1)] = ZoO_END_OF_SEQUENCE_ID;
+            return 0;
+
+         case ZoO_END_OF_SEQUENCE_ID:
+            return 0;
+
+         default:
+            break;
+      }
+   }
+}
+
+/******************************************************************************/
+/** INITIALIZING SEQUENCE *****************************************************/
+/******************************************************************************/
+
+static int allocate_initial_sequence
+(
+   ZoO_index * sequence [const restrict static 1],
+   size_t sequence_size [const restrict static 1],
+   const ZoO_index markov_order
+)
+{
+   if ((SIZE_MAX / sizeof(ZoO_index)) > ((size_t) markov_order))
+   {
+      ZoO_S_ERROR
+      (
+         "Unable to store size of the initial sequence in a size_t variable."
+         "Either reduce the size of a ZoO_index or the markovian order."
+      );
+
+      *sequence = (ZoO_index *) NULL;
+      *sequence_size = 0;
+
+      return -1;
+   }
+
+   *sequence_size = ((size_t) markov_order) * sizeof(ZoO_index);
+   *sequence = (ZoO_index *) malloc(*sequence_size);
+
+   if (*sequence == (void *) NULL)
+   {
+      *sequence_size = 0;
+
+      ZoO_S_ERROR
+      (
+         "Unable to allocate the memory required for an new sequence."
+      );
+
+      return -2;
+   }
+
+   return 0;
+}
+
+static int initialize_sequence
+(
+   ZoO_index sequence [const restrict static 1],
+   const ZoO_index initial_word,
+   const ZoO_index markov_order,
+   const struct ZoO_knowledge k [const static 1]
+)
+{
+   const ZoO_index * const restrict * restrict following_sequences;
+   const ZoO_index * restrict following_sequences_weights;
+   ZoO_index following_sequences_weights_sum;
+   ZoO_index chosen_sequence;
+
+   sequence[0] = initial_word;
+
+   if (markov_order == 1)
+   {
+      return 0;
+   }
+
+   if
+   (
+      ZoO_knowledge_get_following_sequences
+      (
+         k,
+         initial_word,
+         &following_sequences,
+         &following_sequences_weights,
+         &following_sequences_weights_sum
+      ) < 0
+   )
+   {
+      ZoO_S_ERROR
+      (
+         "Unable to find any sequence that would precede the initial word."
+      );
+
+      return -3;
+   }
+
+   chosen_sequence =
+      weighted_random_pick
+      (
+         following_sequences_weights,
+         following_sequences_weights_sum
+      );
+
+   /* Safe if 'allocate_initial_sequence' succeeded. */
+   memcpy
+   (
+      (void *) (sequence + 1),
+      (const void *) (following_sequences + chosen_sequence),
+      (((size_t) markov_order) - 1) * sizeof(ZoO_index)
+   );
+
+   return 0;
+}
+
+/******************************************************************************/
+/** EXPORTED ******************************************************************/
+/******************************************************************************/
+
+int ZoO_create_sequence_from
+(
+   const ZoO_index initial_word,
+   ZoO_index credits [const restrict],
+   const struct ZoO_knowledge k [const restrict static 1],
+   const ZoO_index markov_order,
+   ZoO_index * sequence [const restrict static 1],
+   size_t sequence_size [const restrict static 1]
+)
+{
+   if (allocate_initial_sequence(sequence, sequence_size, markov_order) < 0)
+   {
+      return -1;
+   }
+
+   if (initialize_sequence(*sequence, initial_word, markov_order, k) < 0)
+   {
+      free((void *) *sequence);
+      *sequence_size = 0;
+
+      return -2;
+   }
+
+   if
+   (
+      complete_right_part_of_sequence
+      (
+         sequence,
+         sequence_size,
+         credits,
+         k
+      ) < 0
+   )
+   {
+      free((void *) *sequence);
+      *sequence_size = 0;
+
+      return -3;
+   }
+
+   if
+   (
+      complete_left_part_of_sequence
+      (
+         sequence,
+         sequence_size,
+         credits,
+         k
+      ) < 0
+   )
+   {
+      free((void *) *sequence);
+      *sequence_size = 0;
+
+      return -4;
+   }
+
+   if ((*sequence_size / sizeof(ZoO_index)) < 3)
+   {
+      /* 2 elements, for start and stop. */
+      ZoO_S_ERROR("Created sequence was empty.");
+
+      free((void *) *sequence);
+      *sequence_size = 0;
+
+      return -5;
+   }
+
+   return 0;
+}
diff --git a/src/core/index.h b/src/core/index.h
new file mode 100644
index 0000000..76e3507
--- /dev/null
+++ b/src/core/index.h
@@ -0,0 +1,8 @@
+#ifndef _ZoO_CORE_INDEX_H_
+#define _ZoO_CORE_INDEX_H_
+
+#include "index_types.h"
+
+ZoO_index ZoO_index_random_up_to (const ZoO_index limit);
+
+#endif
diff --git a/src/core/index_types.h b/src/core/index_types.h
new file mode 100644
index 0000000..2d769ca
--- /dev/null
+++ b/src/core/index_types.h
@@ -0,0 +1,8 @@
+#ifndef _ZoO_CORE_INDEX_TYPES_H_
+#define _ZoO_CORE_INDEX_TYPES_H_
+
+typedef unsigned int ZoO_index;
+
+#define ZoO_INDEX_MAX UINT_MAX
+
+#endif