summaryrefslogtreecommitdiff
path: root/src/knowledge
diff options
context:
space:
mode:
Diffstat (limited to 'src/knowledge')
-rw-r--r--src/knowledge/CMakeLists.txt15
-rw-r--r--src/knowledge/knowledge.c180
-rw-r--r--src/knowledge/knowledge.h234
-rw-r--r--src/knowledge/knowledge_finalize.c122
-rw-r--r--src/knowledge/knowledge_get_random_sequence.c89
-rw-r--r--src/knowledge/knowledge_get_random_target.c109
-rw-r--r--src/knowledge/knowledge_learn_markov_sequence.c418
-rw-r--r--src/knowledge/knowledge_learn_sequence.c264
-rw-r--r--src/knowledge/knowledge_learn_word.c309
-rw-r--r--src/knowledge/knowledge_search.c213
-rw-r--r--src/knowledge/knowledge_swt_tws_modifications.c333
-rw-r--r--src/knowledge/knowledge_types.h62
12 files changed, 2348 insertions, 0 deletions
diff --git a/src/knowledge/CMakeLists.txt b/src/knowledge/CMakeLists.txt
new file mode 100644
index 0000000..ba3293d
--- /dev/null
+++ b/src/knowledge/CMakeLists.txt
@@ -0,0 +1,15 @@
+set(
+ SRC_FILES ${SRC_FILES}
+ ${CMAKE_CURRENT_SOURCE_DIR}/knowledge.c
+ ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_finalize.c
+ ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_get_random_sequence.c
+ ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_get_random_target.c
+ ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_learn_markov_sequence.c
+ ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_learn_sequence.c
+ ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_learn_word.c
+ ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_search.c
+ ${CMAKE_CURRENT_SOURCE_DIR}/knowledge_swt_tws_modifications.c
+)
+
+set(SRC_FILES ${SRC_FILES} PARENT_SCOPE)
+
diff --git a/src/knowledge/knowledge.c b/src/knowledge/knowledge.c
new file mode 100644
index 0000000..93351da
--- /dev/null
+++ b/src/knowledge/knowledge.c
@@ -0,0 +1,180 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdint.h> /* defines SIZE_MAX */
+
+#include "../error/error.h"
+
+#include "knowledge.h"
+
+/** Basic functions of the JH_knowledge structure ****************************/
+
+/* See: "knowledge.h" */
+int JH_knowledge_initialize (struct JH_knowledge k [const restrict static 1])
+{
+ int error;
+ JH_index reserved_word_id;
+
+ k->words = (struct JH_knowledge_word *) NULL;
+ k->words_length = 0;
+ k->words_sorted = (JH_index *) NULL;
+
+ k->sequences = (JH_index **) NULL;
+ k->sequences_length = 0;
+ k->sequences_sorted = (JH_index *) NULL;
+
+#ifndef JH_RUNNING_FRAMA_C
+ error = pthread_mutex_init(&(k->mutex), (const pthread_mutexattr_t *) NULL);
+#else
+ k->mutex = 1;
+ error = 0;
+#endif
+
+ if (error != 0)
+ {
+ JH_FATAL
+ (
+ stderr,
+ "Unable to initialize knowledge mutex: %s.",
+ strerror(error)
+ );
+
+ return -1;
+ }
+
+ if
+ (
+ (
+ JH_knowledge_learn_word
+ (
+ k,
+ "[SoS]",
+ 5,
+ &reserved_word_id,
+ stderr
+ ) < 0
+ )
+ ||
+ (
+ JH_knowledge_learn_word
+ (
+ k,
+ "[EoS]",
+ 5,
+ &reserved_word_id,
+ stderr
+ ) < 0
+ )
+ )
+ {
+ JH_S_FATAL(stderr, "Unable to learn reserved words.");
+
+ return -1;
+ }
+
+ return 0;
+}
+
+int JH_knowledge_lock_access
+(
+ struct JH_knowledge k [const restrict static 1],
+ FILE io [const restrict static 1]
+)
+{
+ int err;
+
+#ifndef JH_RUNNING_FRAMA_C
+ err = pthread_mutex_lock(&(k->mutex));
+#else
+ /*@ assert (k->mutex == 1); @*/
+ k->mutex = 0;
+ err = 0;
+#endif
+
+ if (err != 0)
+ {
+ JH_ERROR
+ (
+ io,
+ "Unable to get exclusive access to knowledge: %s",
+ strerror(err)
+ );
+
+ return -1;
+ }
+
+ return 0;
+}
+
+void JH_knowledge_unlock_access
+(
+ struct JH_knowledge k [const restrict static 1],
+ FILE io [const restrict static 1]
+)
+{
+ int err;
+
+#ifndef JH_RUNNING_FRAMA_C
+ err = pthread_mutex_unlock(&(k->mutex));
+#else
+ /*@ assert (k->mutex == 0); @*/
+ k->mutex = 1;
+ err = 0;
+#endif
+
+ if (err != 0)
+ {
+ JH_ERROR
+ (
+ io,
+ "Unable to release exclusive access to knowledge: %s",
+ strerror(err)
+ );
+ }
+}
+
+void JH_knowledge_get_word
+(
+ const struct JH_knowledge k [const static 1],
+ const JH_index word_ref,
+ const JH_char * word [const restrict static 1],
+ JH_index word_length [const restrict static 1]
+)
+{
+ *word = k->words[word_ref].word;
+ *word_length = k->words[word_ref].word_length;
+}
+
+int JH_knowledge_rarest_word
+(
+ const struct JH_knowledge k [const static 1],
+ const JH_index sequence [const restrict static 1],
+ const size_t sequence_length,
+ JH_index word_id [const restrict static 1]
+)
+{
+ JH_index current_max_score;
+ size_t i;
+ int success;
+
+ current_max_score = JH_INDEX_MAX;
+
+ success = -1;
+
+ for (i = 0; i < sequence_length; ++i)
+ {
+ if
+ (
+ (k->words[sequence[i]].occurrences <= current_max_score)
+ /* Otherwise we might just have learned it, or it must not be used. */
+ && (k->words[sequence[i]].occurrences > 1)
+ )
+ {
+ current_max_score = k->words[sequence[i]].occurrences;
+ *word_id = sequence[i];
+ success = 0;
+ }
+ }
+
+ return success;
+}
diff --git a/src/knowledge/knowledge.h b/src/knowledge/knowledge.h
new file mode 100644
index 0000000..20293bc
--- /dev/null
+++ b/src/knowledge/knowledge.h
@@ -0,0 +1,234 @@
+#ifndef _JH_KNOWLEDGE_KNOWLEDGE_H_
+#define _JH_KNOWLEDGE_KNOWLEDGE_H_
+
+#include "../core/char_types.h"
+#include "../core/index_types.h"
+
+#include "../error/error.h"
+
+#include "knowledge_types.h"
+
+/*@
+ requires \valid(k);
+ requires \separated(k, io);
+
+// Do not use if lock is already yours.
+ requires (k->mutex == 1);
+
+// Returns zero on success, -1 on failure.
+ assigns \result;
+ ensures ((\result == 0) || (\result == -1));
+
+// On success, lock is acquired.
+ ensures ((\result == 0) ==> (k->mutex == 0));
+
+// Changes the status of the lock.
+ assigns (k->mutex);
+@*/
+int JH_knowledge_lock_access
+(
+ struct JH_knowledge k [const restrict static 1],
+ FILE io [const restrict static 1]
+);
+
+/*@
+ requires \valid(k);
+ requires \separated(k, io);
+
+// Do not use if lock is not yours.
+ requires (k->mutex == 0);
+
+// Lock is released.
+ ensures (k->mutex == 1);
+
+// Changes the status of the lock.
+ assigns (k->mutex);
+@*/
+void JH_knowledge_unlock_access
+(
+ struct JH_knowledge k [const restrict static 1],
+ FILE io [const restrict static 1]
+);
+
+/*@
+ requires (\block_length(k) >= 1);
+
+// Returns zero on success, -1 on failure.
+ assigns \result;
+ ensures ((\result == 0) || (\result == -1));
+
+// On success, all fields of {*k} are set.
+ ensures ((\result == 0) ==> \valid(k));
+
+// On success, the two reserved words are learnt.
+ ensures ((\result == 0) ==> (k->words_length == 2));
+
+// On success, the mutex is initialized and unlocked.
+ ensures ((\result == 0) ==> (k->mutex == 1));
+
+// At least some fields of k are set in any case.
+ assigns (*k);
+@*/
+int JH_knowledge_initialize (struct JH_knowledge k [const restrict static 1]);
+
+void JH_knowledge_finalize (struct JH_knowledge k [const restrict static 1]);
+
+/*
+ * When returning 0:
+ * {word} was added to {k}, or was already there.
+ * {*result} indicates where {word} is in {k->words}.
+ *
+ * When returning -1:
+ * Something went wrong when adding the occurrence of {word} to {k}.
+ * {k} remains semantically unchanged.
+ * {*result} may or may not have been altered.
+ */
+int JH_knowledge_learn_word
+(
+ struct JH_knowledge k [const static 1],
+ const JH_char word [const restrict static 1],
+ const size_t word_length,
+ JH_index result [const restrict static 1],
+ FILE io [const restrict static 1]
+);
+
+int JH_knowledge_learn_sequence
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index sequence [const restrict static 1],
+ const size_t sequence_length,
+ const JH_index markov_order,
+ FILE io [const restrict static 1]
+);
+
+int JH_knowledge_learn_markov_sequence
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index sequence [const restrict static 1],
+ const JH_index markov_order, /* Pre (> markov_order 1) */
+ JH_index sequence_id [const restrict static 1],
+ FILE io [const restrict static 1]
+);
+
+void JH_knowledge_get_word
+(
+ const struct JH_knowledge k [const static 1],
+ const JH_index word_ref,
+ const JH_char * word [const restrict static 1],
+ JH_index word_length [const restrict static 1]
+);
+
+/*
+ * When returning 0:
+ * {word} is in {k}.
+ * {word} is located at {k->words[*result]}.
+ *
+ * When returning -1:
+ * {word} is not in {k}.
+ * {*result} is where {word} was expected to be found in
+ * {k->sorted_indices}.
+ */
+int JH_knowledge_find_word_id
+(
+ const struct JH_knowledge k [const restrict static 1],
+ const JH_char word [const restrict static 1],
+ const size_t word_size,
+ JH_index result [const restrict static 1]
+);
+
+int JH_knowledge_find_sequence
+(
+ const struct JH_knowledge k [const static 1],
+ const JH_index sequence [const restrict static 1],
+ const JH_index markov_order, /* Pre: (> 1) */
+ JH_index sequence_id [const restrict static 1]
+);
+
+int JH_knowledge_rarest_word
+(
+ const struct JH_knowledge k [const static 1],
+ const JH_index sequence [const restrict static 1],
+ const size_t sequence_length,
+ JH_index word_id [const restrict static 1]
+);
+
+int JH_knowledge_find_markov_sequence
+(
+ const JH_index sequence_id,
+ const struct JH_knowledge_sequence_collection sc [const restrict static 1],
+ JH_index result [const restrict static 1]
+);
+
+int JH_knowledge_find_sequence_target
+(
+ const JH_index target_id,
+ const struct JH_knowledge_sequence_data sd [const restrict static 1],
+ JH_index result [const restrict static 1]
+);
+
+int JH_knowledge_random_tws_target
+(
+ const struct JH_knowledge k [const static 1],
+ JH_index target [const restrict static 1],
+ const JH_index word_id,
+ const JH_index sequence_id
+);
+
+int JH_knowledge_random_swt_target
+(
+ const struct JH_knowledge k [const static 1],
+ const JH_index sequence_id,
+ const JH_index word_id,
+ JH_index target [const restrict static 1]
+);
+
+int JH_knowledge_copy_random_swt_sequence
+(
+ const struct JH_knowledge k [const static 1],
+ JH_index sequence [const restrict static 1],
+ const JH_index word_id,
+ const JH_index markov_order,
+ FILE io [const restrict static 1]
+);
+
+int JH_knowledge_strengthen_swt
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index sequence_id,
+ const JH_index word_id,
+ const JH_index target_id,
+ FILE io [const restrict static 1]
+);
+
+int JH_knowledge_strengthen_tws
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index target_id,
+ const JH_index word_id,
+ const JH_index sequence_id,
+ FILE io [const restrict static 1]
+);
+
+/*
+ * TODO
+ */
+/*
+int JH_knowledge_weaken_swt
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index sequence_id,
+ const JH_index word_id,
+ const JH_index target_id,
+ FILE io [const restrict static 1]
+);
+
+int JH_knowledge_weaken_tws
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index target_id,
+ const JH_index word_id,
+ const JH_index sequence_id,
+ FILE io [const restrict static 1]
+);
+*/
+#endif
diff --git a/src/knowledge/knowledge_finalize.c b/src/knowledge/knowledge_finalize.c
new file mode 100644
index 0000000..8020b9a
--- /dev/null
+++ b/src/knowledge/knowledge_finalize.c
@@ -0,0 +1,122 @@
+#include <stdlib.h>
+
+#include "knowledge.h"
+
+/*@
+ requires \valid(sd);
+@*/
+static void knowledge_sequence_data_finalize
+(
+ struct JH_knowledge_sequence_data sd [const restrict static 1]
+)
+{
+ sd->occurrences = 0;
+
+ if (sd->targets != (struct JH_knowledge_target *) NULL)
+ {
+ free((void *) sd->targets);
+
+ sd->targets = (struct JH_knowledge_target *) NULL;
+ }
+
+ sd->targets_length = 0;
+
+}
+
+static void knowledge_sequence_collection_finalize
+(
+ struct JH_knowledge_sequence_collection c [const restrict static 1]
+)
+{
+ JH_index i;
+
+ for (i = 0; i < c->sequences_ref_length; ++i)
+ {
+ knowledge_sequence_data_finalize(c->sequences_ref + i);
+ }
+
+ if (c->sequences_ref != (struct JH_knowledge_sequence_data *) NULL)
+ {
+ free((void *) c->sequences_ref);
+
+ c->sequences_ref = (struct JH_knowledge_sequence_data *) NULL;
+ }
+
+ if (c->sequences_ref_sorted != (JH_index *) NULL)
+ {
+ free((void *) c->sequences_ref_sorted);
+
+ c->sequences_ref_sorted = (JH_index *) NULL;
+ }
+
+ c->sequences_ref_length = 0;
+}
+
+static void knowledge_word_finalize
+(
+ struct JH_knowledge_word w [const restrict static 1]
+)
+{
+ w->word_length = 0;
+ w->occurrences = 0;
+
+ if (w->word != (JH_char *) NULL)
+ {
+ free((void *) w->word);
+
+ w->word = (JH_char *) NULL;
+ }
+
+ knowledge_sequence_collection_finalize(&(w->swt));
+ knowledge_sequence_collection_finalize(&(w->tws));
+}
+
+/* See: "knowledge.h" */
+void JH_knowledge_finalize (struct JH_knowledge k [const restrict static 1])
+{
+ JH_index i;
+
+ for (i = 0; i < k->words_length; ++i)
+ {
+ knowledge_word_finalize(k->words + i);
+ }
+
+ k->words_length = 0;
+
+ if (k->words != (struct JH_knowledge_word *) NULL)
+ {
+ free((void *) k->words);
+
+ k->words = (struct JH_knowledge_word *) NULL;
+ }
+
+ if (k->words_sorted != (JH_index *) NULL)
+ {
+ free((void *) k->words_sorted);
+
+ k->words_sorted = (JH_index *) NULL;
+ }
+
+ for (i = 0; i < k->sequences_length; ++i)
+ {
+ free((void *) k->sequences[i]);
+ }
+
+ k->sequences_length = 0;
+
+ if (k->sequences != (JH_index **) NULL)
+ {
+ free((void *) k->sequences);
+
+ k->sequences = (JH_index **) NULL;
+ }
+
+ if (k->sequences_sorted != (JH_index *) NULL)
+ {
+ free((void *) k->sequences_sorted);
+
+ k->sequences_sorted = (JH_index *) NULL;
+ }
+
+ pthread_mutex_destroy(&(k->mutex));
+}
diff --git a/src/knowledge/knowledge_get_random_sequence.c b/src/knowledge/knowledge_get_random_sequence.c
new file mode 100644
index 0000000..60a075f
--- /dev/null
+++ b/src/knowledge/knowledge_get_random_sequence.c
@@ -0,0 +1,89 @@
+#include <stdlib.h>
+
+#include "../core/char.h"
+#include "../core/index.h"
+
+#include "../sequence/sequence.h"
+
+#include "../error/error.h"
+
+#include "knowledge.h"
+
+static int weighted_random_pick
+(
+ const struct JH_knowledge_sequence_collection sc [const restrict static 1],
+ const JH_index sum,
+ JH_index result [const restrict static 1]
+)
+{
+ JH_index accumulator, random_number;
+
+ accumulator = 0;
+
+ if (sum == 0)
+ {
+ return -1;
+ }
+
+ random_number = JH_index_random_up_to(sum);
+ /*@ ensures (0 <= random_number <= weights_sum); @*/
+
+ *result = 0;
+
+ for (;;)
+ {
+ accumulator += sc->sequences_ref[*result].occurrences;
+
+ if (accumulator < random_number)
+ {
+ *result += 1;
+ }
+ else
+ {
+ *result = sc->sequences_ref[*result].id;
+
+ return 0;
+ }
+ }
+}
+
+int JH_knowledge_copy_random_swt_sequence
+(
+ const struct JH_knowledge k [const static 1],
+ JH_index sequence [const restrict static 1],
+ const JH_index word_id,
+ const JH_index markov_order,
+ FILE io [const restrict static 1]
+)
+{
+ JH_index sequence_id;
+
+ if
+ (
+ weighted_random_pick
+ (
+ &(k->words[word_id].swt),
+ k->words[word_id].occurrences,
+ &sequence_id
+ ) < 0
+ )
+ {
+ JH_S_PROG_ERROR
+ (
+ io,
+ "Knowledge inconsistency; there are no acceptable markov sequences "
+ "linked to a word that has been picked as being an acceptable pillar."
+ )
+ ;
+ return -1;
+ }
+
+ memcpy
+ (
+ (void *) sequence,
+ (const void *) k->sequences[sequence_id],
+ (((size_t) (markov_order - 1)) * sizeof(JH_index))
+ );
+
+ return 0;
+}
diff --git a/src/knowledge/knowledge_get_random_target.c b/src/knowledge/knowledge_get_random_target.c
new file mode 100644
index 0000000..d5f321d
--- /dev/null
+++ b/src/knowledge/knowledge_get_random_target.c
@@ -0,0 +1,109 @@
+#include <stdlib.h>
+
+#include "../core/char.h"
+#include "../core/index.h"
+
+#include "../error/error.h"
+
+#include "../sequence/sequence.h"
+
+#include "knowledge.h"
+
+static int weighted_random_pick
+(
+ const struct JH_knowledge_sequence_data sd [const restrict static 1],
+ JH_index result [const restrict static 1]
+)
+{
+ JH_index accumulator, random_number;
+
+ accumulator = 0;
+
+ if (sd->occurrences == 0)
+ {
+ return -1;
+ }
+
+ random_number = JH_index_random_up_to(sd->occurrences);
+ /*@ ensures (0 <= random_number <= weights_sum); @*/
+
+ *result = 0;
+
+ for (;;)
+ {
+ accumulator += sd->targets[*result].occurrences;
+
+ if (accumulator < random_number)
+ {
+ *result += 1;
+ }
+ else
+ {
+ *result = sd->targets[*result].id;
+
+ return 0;
+ }
+ }
+}
+
+int JH_knowledge_random_tws_target
+(
+ const struct JH_knowledge k [const static 1],
+ JH_index target [const restrict static 1],
+ const JH_index word_id,
+ const JH_index sequence_id
+)
+{
+ JH_index s_index;
+
+ if
+ (
+ JH_knowledge_find_markov_sequence
+ (
+ sequence_id,
+ &(k->words[word_id].tws),
+ &s_index
+ ) < 0
+ )
+ {
+ return -1;
+ }
+
+ return
+ weighted_random_pick
+ (
+ &(k->words[word_id].tws.sequences_ref[s_index]),
+ target
+ );
+}
+
+int JH_knowledge_random_swt_target
+(
+ const struct JH_knowledge k [const static 1],
+ const JH_index sequence_id,
+ const JH_index word_id,
+ JH_index target [const restrict static 1]
+)
+{
+ JH_index s_index;
+
+ if
+ (
+ JH_knowledge_find_markov_sequence
+ (
+ sequence_id,
+ &(k->words[word_id].swt),
+ &s_index
+ ) < 0
+ )
+ {
+ return -1;
+ }
+
+ return
+ weighted_random_pick
+ (
+ &(k->words[word_id].swt.sequences_ref[s_index]),
+ target
+ );
+}
diff --git a/src/knowledge/knowledge_learn_markov_sequence.c b/src/knowledge/knowledge_learn_markov_sequence.c
new file mode 100644
index 0000000..4a770e2
--- /dev/null
+++ b/src/knowledge/knowledge_learn_markov_sequence.c
@@ -0,0 +1,418 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h> /* defines SIZE_MAX */
+
+#include "../sequence/sequence.h"
+
+#include "../error/error.h"
+
+#include "knowledge.h"
+
+/******************************************************************************/
+/** INITIALIZE ****************************************************************/
+/******************************************************************************/
+static void set_nth_sequence
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index sorted_sequence_id,
+ const JH_index sequence_id
+)
+{
+ if (sorted_sequence_id < (k->sequences_length - 1))
+ {
+ memmove
+ (
+ (void *) (k->sequences_sorted + (sorted_sequence_id + 1)),
+ (const void *) (k->sequences_sorted + sorted_sequence_id),
+ (
+ ((size_t) ((k->sequences_length - 1) - sorted_sequence_id))
+ * sizeof(JH_index)
+ )
+ );
+ }
+
+ k->sequences_sorted[sorted_sequence_id] = sequence_id;
+}
+
+/******************************************************************************/
+/** ALLOCATING MEMORY *********************************************************/
+/******************************************************************************/
+static int reallocate_sequences_list
+(
+ struct JH_knowledge k [const restrict static 1],
+ FILE io [const restrict static 1]
+)
+{
+ JH_index ** new_sequences;
+
+ if ((SIZE_MAX / sizeof(JH_index *)) < (size_t) k->sequences_length)
+ {
+ JH_S_ERROR
+ (
+ io,
+ "Unable to store the size of the sequences list, as it would overflow "
+ "size_t variables."
+ );
+
+ return -1;
+ }
+
+ new_sequences =
+ (JH_index **) realloc
+ (
+ (void *) k->sequences,
+ (((size_t) k->sequences_length) * sizeof(JH_index *))
+ );
+
+ if (new_sequences == (JH_index **) NULL)
+ {
+ JH_S_ERROR
+ (
+ io,
+ "Unable to allocate the memory required for the new sequence list."
+ );
+
+ return -1;
+ }
+
+ k->sequences = new_sequences;
+
+ return 0;
+}
+
+static int reallocate_sequences_sorted_list
+(
+ struct JH_knowledge k [const restrict static 1],
+ FILE io [const restrict static 1]
+)
+{
+ JH_index * new_sequences_sorted;
+
+ if ((SIZE_MAX / sizeof(JH_index)) < (size_t) k->sequences_length)
+ {
+ JH_S_ERROR
+ (
+ io,
+ "Unable to store the size of the sorted sequences list, as it would "
+ "overflow size_t variables."
+ );
+
+ return -1;
+ }
+
+ new_sequences_sorted =
+ (JH_index *) realloc
+ (
+ (void *) k->sequences_sorted,
+ (((size_t) k->sequences_length) * sizeof(JH_index))
+ );
+
+ if (new_sequences_sorted == (JH_index *) NULL)
+ {
+ JH_S_ERROR
+ (
+ io,
+ "Unable to allocate the memory required for the new sorted sequences "
+ "list."
+ );
+
+ return -1;
+ }
+
+ k->sequences_sorted = new_sequences_sorted;
+
+ return 0;
+}
+
+/* Pre: (=< JH_INDEX_MAX SIZE_MAX) */
+/*@
+ requires
+ (
+ (base_length == destination_length)
+ ||
+ (
+ (base_length < destination_length)
+ &&
+ (
+ (base[0] == JH_START_OF_SEQUENCE)
+ (base[base_length - 1] == JH_END_OF_SEQUENCE)
+ )
+ )
+ );
+@*/
+static JH_index * copy_sequence
+(
+ const JH_index base [const restrict static 1],
+ const JH_index destination_length,
+ FILE io [const restrict static 1]
+)
+{
+ JH_index * result;
+
+ result =
+ (JH_index *) calloc
+ (
+ (size_t) (destination_length),
+ sizeof(JH_index)
+ );
+
+ if (result == (JH_index *) NULL)
+ {
+ JH_S_ERROR
+ (
+ io,
+ "Unable to allocate the memory required to store a new sequence."
+ );
+
+ return (JH_index *) NULL;
+ }
+
+ memcpy
+ (
+ (void *) result,
+ (const void *) base,
+ (((size_t) destination_length) * sizeof(JH_index))
+ );
+
+ return result;
+}
+
+/******************************************************************************/
+/** ADD A NEW SEQUENCE ********************************************************/
+/******************************************************************************/
+
+static int add_sequence
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index sequence [const restrict static 1],
+ const JH_index markov_order, /* Pre (> markov_order 1) */
+ const JH_index sequence_id,
+ const JH_index sorted_sequence_id,
+ FILE io [const restrict static 1]
+)
+{
+ JH_index * stored_sequence;
+
+ if (k->sequences_length == JH_INDEX_MAX)
+ {
+ JH_S_ERROR
+ (
+ io,
+ "Unable to add sequence: the variable that stores the number of known "
+ "sequences would overflow."
+ );
+
+ return -1;
+ }
+
+ stored_sequence = copy_sequence(sequence, (markov_order - 1), io);
+
+ if (stored_sequence == (JH_index *) NULL)
+ {
+ return -1;
+ }
+
+ if (JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE)
+ {
+ JH_index i;
+
+ JH_S_DEBUG
+ (
+ io,
+ JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE,
+ "Learning new sequence."
+ );
+
+ for (i = 0; i < (markov_order - 1); ++i)
+ {
+ JH_DEBUG
+ (
+ io,
+ JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE,
+ "markov_sequence[%u]: %u",
+ i,
+ stored_sequence[i]
+ );
+ }
+ }
+
+ k->sequences_length += 1;
+
+ if (reallocate_sequences_list(k, io) < 0)
+ {
+ k->sequences_length -= 1;
+
+ free((void *) stored_sequence);
+
+ return -1;
+ }
+
+ k->sequences[sequence_id] = stored_sequence;
+
+ if (reallocate_sequences_sorted_list(k, io) < 0)
+ {
+ k->sequences_length -= 1;
+
+ free((void *) stored_sequence);
+
+ return -1;
+ }
+
+ set_nth_sequence(k, sorted_sequence_id, sequence_id);
+
+ return 0;
+}
+
+/******************************************************************************/
+/** SEARCH EXISTING SEQUENCES *************************************************/
+/******************************************************************************/
+
+int JH_knowledge_find_sequence
+(
+ const struct JH_knowledge k [const static 1],
+ const JH_index sequence [const restrict static 1],
+ const JH_index markov_order, /* Pre: (> 1) */
+ JH_index sequence_id [const restrict static 1]
+)
+{
+ /* This is a binary search */
+ int cmp;
+ JH_index i, current_min, current_max;
+ const JH_index markov_sequence_length = (markov_order - 1);
+
+ /* Handles the case where the list is empty ********************************/
+ current_max = k->sequences_length;
+
+ if (current_max == 0)
+ {
+ *sequence_id = 0;
+
+ return -1;
+ }
+ /***************************************************************************/
+
+ current_min = 0;
+ current_max -= 1;
+
+ while (current_min <= current_max)
+ {
+ i = (current_min + ((current_max - current_min) / 2));
+
+ cmp =
+ JH_sequence_cmp
+ (
+ sequence,
+ k->sequences[k->sequences_sorted[i]],
+ markov_sequence_length
+ );
+
+ if (cmp > 0)
+ {
+ current_min = (i + 1);
+
+ if (current_min > current_max)
+ {
+ *sequence_id = current_min;
+
+ return -1;
+ }
+ }
+ else if (cmp < 0)
+ {
+ if ((current_min >= current_max) || (i == 0))
+ {
+ *sequence_id = current_min;
+
+ return -1;
+ }
+
+ current_max = (i - 1);
+ }
+ else
+ {
+ *sequence_id = k->sequences_sorted[i];
+
+ return 0;
+ }
+ }
+
+ *sequence_id = current_min;
+
+ return -1;
+}
+
+/******************************************************************************/
+/** EXPORTED ******************************************************************/
+/******************************************************************************/
+
+int JH_knowledge_learn_markov_sequence
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index sequence [const restrict static 1],
+ const JH_index markov_order, /* Pre (> markov_order 1) */
+ JH_index sequence_id [const restrict static 1],
+ FILE io [const restrict static 1]
+)
+{
+ JH_index sorted_id;
+
+ if (JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE)
+ {
+ JH_index i;
+
+ JH_S_DEBUG
+ (
+ io,
+ JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE,
+ "Studying markov sequence..."
+ );
+
+ for (i = 0; i < (markov_order - 1); ++i)
+ {
+ JH_DEBUG
+ (
+ io,
+ JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE,
+ "markov_sequence[%u]: %u",
+ i,
+ sequence[i]
+ );
+ }
+ }
+
+ if
+ (
+ JH_knowledge_find_sequence
+ (
+ k,
+ sequence,
+ markov_order,
+ sequence_id
+ ) == 0
+ )
+ {
+ JH_DEBUG
+ (
+ io,
+ JH_DEBUG_KNOWLEDGE_LEARN_SEQUENCE,
+ "Markov sequence is known. ID: %u",
+ *sequence_id
+ );
+
+ return 0;
+ }
+
+ sorted_id = *sequence_id;
+ *sequence_id = k->sequences_length;
+
+ return
+ add_sequence
+ (
+ k,
+ sequence,
+ markov_order,
+ *sequence_id,
+ sorted_id,
+ io
+ );
+}
diff --git a/src/knowledge/knowledge_learn_sequence.c b/src/knowledge/knowledge_learn_sequence.c
new file mode 100644
index 0000000..90dbc88
--- /dev/null
+++ b/src/knowledge/knowledge_learn_sequence.c
@@ -0,0 +1,264 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h> /* defines SIZE_MAX */
+
+#include "../sequence/sequence.h"
+
+#include "../error/error.h"
+
+#include "knowledge.h"
+
+/******************************************************************************/
+/** LEARN FOLLOWING SEQUENCE **************************************************/
+/******************************************************************************/
+static void parse_swt_sequence
+(
+ const JH_index sequence [const restrict static 1],
+ const size_t index,
+ JH_index buffer [const restrict static 1],
+ const JH_index buffer_length
+)
+{
+ size_t j;
+ size_t index_offset;
+
+ index_offset = buffer_length;
+
+ for (j = 0; j < buffer_length; ++j)
+ {
+ if (index >= index_offset)
+ {
+ buffer[j] = sequence[index - index_offset];
+ }
+ else
+ {
+ buffer[j] = JH_START_OF_SEQUENCE_ID;
+ }
+
+ --index_offset;
+ }
+}
+
+static int add_swt_sequence
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index sequence [const restrict static 1],
+ const size_t index,
+ const size_t sequence_length,
+ const JH_index markov_order,
+ JH_index buffer [const restrict static 1],
+ const JH_index buffer_length,
+ FILE io [const restrict static 1]
+)
+{
+ JH_index sequence_id;
+
+ parse_swt_sequence(sequence, index, buffer, buffer_length);
+
+ if
+ (
+ JH_knowledge_learn_markov_sequence
+ (
+ k,
+ buffer,
+ (buffer_length + 1),
+ &sequence_id,
+ io
+ ) < 0
+ )
+ {
+ return -1;
+ }
+
+ if (index == (sequence_length - 1))
+ {
+ return
+ JH_knowledge_strengthen_swt
+ (
+ k,
+ sequence_id,
+ sequence[index],
+ JH_END_OF_SEQUENCE_ID,
+ io
+ );
+ }
+ else
+ {
+ return
+ JH_knowledge_strengthen_swt
+ (
+ k,
+ sequence_id,
+ sequence[index],
+ sequence[index + 1],
+ io
+ );
+ }
+}
+
+/******************************************************************************/
+/** LEARN PRECEDING SEQUENCE **************************************************/
+/******************************************************************************/
+static void parse_tws_sequence
+(
+ const JH_index sequence [const restrict static 1],
+ const size_t index,
+ const size_t sequence_length,
+ JH_index buffer [const restrict static 1],
+ const JH_index buffer_length
+)
+{
+ size_t j;
+ size_t index_offset;
+
+ for (j = 0; j < buffer_length; ++j)
+ {
+ index_offset = (j + 1) + index;
+
+ if (sequence_length > index_offset)
+ {
+ buffer[j] = sequence[index_offset];
+ }
+ else
+ {
+ buffer[j] = JH_END_OF_SEQUENCE_ID;
+ }
+ }
+}
+
+static int add_tws_sequence
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index sequence [const restrict static 1],
+ const size_t index,
+ const size_t sequence_length,
+ const JH_index markov_order,
+ JH_index buffer [const restrict static 1],
+ const JH_index buffer_length,
+ FILE io [const restrict static 1]
+)
+{
+ JH_index sequence_id;
+
+ parse_tws_sequence(sequence, index, sequence_length, buffer, buffer_length);
+
+ if
+ (
+ JH_knowledge_learn_markov_sequence
+ (
+ k,
+ buffer,
+ (buffer_length + 1),
+ &sequence_id,
+ io
+ ) < 0
+ )
+ {
+ return -1;
+ }
+
+ if (index == 0)
+ {
+ return
+ JH_knowledge_strengthen_tws
+ (
+ k,
+ JH_START_OF_SEQUENCE_ID,
+ sequence[index],
+ sequence_id,
+ io
+ );
+ }
+ else
+ {
+ return
+ JH_knowledge_strengthen_tws
+ (
+ k,
+ sequence[index - 1],
+ sequence[index],
+ sequence_id,
+ io
+ );
+ }
+}
+
+/******************************************************************************/
+/** EXPORTED ******************************************************************/
+/******************************************************************************/
+int JH_knowledge_learn_sequence
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index sequence [const restrict static 1],
+ const size_t sequence_length,
+ const JH_index markov_order,
+ FILE io [const restrict static 1]
+)
+{
+ JH_index * buffer;
+ size_t i;
+ const JH_index buffer_length = (markov_order - 1);
+
+ buffer =
+ (JH_index *) calloc
+ (
+ (size_t) buffer_length,
+ sizeof(JH_index)
+ );
+
+ if (buffer == (JH_index *) NULL)
+ {
+ JH_S_ERROR
+ (
+ io,
+ "Unable to allocate memory required to create markov sequences."
+ );
+
+ return -1;
+ }
+
+ for (i = 0; i < sequence_length; ++i)
+ {
+ if
+ (
+ add_swt_sequence
+ (
+ k,
+ sequence,
+ i,
+ sequence_length,
+ markov_order,
+ buffer,
+ buffer_length,
+ io
+ ) < 0
+ )
+ {
+ return -1;
+ }
+
+ /* TODO: handle failure. */
+ if
+ (
+ add_tws_sequence
+ (
+ k,
+ sequence,
+ i,
+ sequence_length,
+ markov_order,
+ buffer,
+ buffer_length,
+ io
+ ) < 0
+ )
+ {
+ return -1;
+ }
+
+
+ k->words[sequence[i]].occurrences += 1;
+ }
+
+ return 0;
+}
diff --git a/src/knowledge/knowledge_learn_word.c b/src/knowledge/knowledge_learn_word.c
new file mode 100644
index 0000000..1389cdb
--- /dev/null
+++ b/src/knowledge/knowledge_learn_word.c
@@ -0,0 +1,309 @@
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h> /* defines SIZE_MAX */
+
+#include "../error/error.h"
+
+#include "knowledge.h"
+
+/******************************************************************************/
+/** INITIALIZING STRUCTURES ***************************************************/
+/******************************************************************************/
+
+static void initialize_sequence_collection
+(
+ struct JH_knowledge_sequence_collection c [const restrict static 1]
+)
+{
+ c->sequences_ref = (struct JH_knowledge_sequence_data *) NULL;
+ c->sequences_ref_length = 0;
+ c->sequences_ref_sorted = (JH_index *) NULL;
+}
+
+static void initialize_word
+(
+ struct JH_knowledge_word w [const restrict static 1]
+)
+{
+ w->word = (const JH_char *) NULL;
+ w->word_length = 0;
+ w->occurrences = 0;
+
+ initialize_sequence_collection(&(w->swt));
+ initialize_sequence_collection(&(w->tws));
+}
+
+/******************************************************************************/
+/** ALLOCATING MEMORY *********************************************************/
+/******************************************************************************/
+static JH_char * copy_word
+(
+ const JH_char original [const restrict static 1],
+ const JH_index original_length,
+ FILE io [const restrict static 1]
+)
+{
+ JH_char * result;
+
+ result =
+ (JH_char *)
+ calloc
+ (
+ original_length,
+ sizeof(JH_char)
+ );
+
+ if (result == (JH_char *) NULL)
+ {
+ JH_S_ERROR(io, "Unable to allocate memory to store new word.");
+
+ return (JH_char *) NULL;
+ }
+
+ memcpy
+ (
+ (void *) result,
+ (const void *) original,
+ (((size_t) original_length) * sizeof(JH_char))
+ );
+
+ return result;
+}
+
+static int reallocate_words_list
+(
+ struct JH_knowledge k [const restrict static 1],
+ FILE io [const restrict static 1]
+)
+{
+ struct JH_knowledge_word * new_words;
+
+ if
+ (
+ (SIZE_MAX / sizeof(struct JH_knowledge_word))
+ < (size_t) k->words_length
+ )
+ {
+ JH_S_ERROR
+ (
+ io,
+ "Unable to store the size of the words list, as it would overflow "
+ "size_t variables."
+ );
+
+ return -1;
+ }
+
+ new_words =
+ (struct JH_knowledge_word *) realloc
+ (
+ (void *) k->words,
+ (((size_t) k->words_length) * sizeof(struct JH_knowledge_word))
+ );
+
+ if (new_words == (struct JH_knowledge_word *) NULL)
+ {
+ JH_S_ERROR
+ (
+ io,
+ "Unable to allocate the memory required for the new words list."
+ );
+
+ return -1;
+ }
+
+ k->words = new_words;
+
+ return 0;
+}
+
+static int reallocate_words_sorted_list
+(
+ struct JH_knowledge k [const restrict static 1],
+ FILE io [const restrict static 1]
+)
+{
+ JH_index * new_words_sorted;
+
+ /*
+ * This has already been tested previously for a struct JH_knowledge_word,
+ * whose size is bigger than a JH_index.
+ * */
+ /*
+ if ((SIZE_MAX / sizeof(JH_index)) < k->words_length)
+ {
+ JH_S_ERROR
+ (
+ "Unable to store the size of the sorted words list, as it would "
+ "overflow size_t variables."
+ );
+
+ return -1;
+ }
+ */
+
+ new_words_sorted =
+ (JH_index *) realloc
+ (
+ (void *) k->words_sorted,
+ (((size_t) k->words_length) * sizeof(JH_index))
+ );
+
+ if (new_words_sorted == (JH_index *) NULL)
+ {
+ JH_S_ERROR
+ (
+ io,
+ "Unable to allocate the memory required for the new sorted words list."
+ );
+
+ return -1;
+ }
+
+ k->words_sorted = new_words_sorted;
+
+ return 0;
+}
+
+static void set_nth_word
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index sorted_word_id,
+ const JH_index word_id
+)
+{
+ /* Safe: (> k->words_length 1) */
+ if (sorted_word_id < (k->words_length - 1))
+ {
+ memmove
+ (
+ /* Safe: (=< (+ sorted_word_id 1) k->words_length) */
+ (void *) (k->words_sorted + (sorted_word_id + 1)),
+ (const void *) (k->words_sorted + sorted_word_id),
+ (
+ ((size_t) ((k->words_length - 1) - sorted_word_id))
+ * sizeof(JH_index)
+ )
+ );
+ }
+
+ k->words_sorted[sorted_word_id] = word_id;
+}
+
+static int add_word
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_char word [const restrict static 1],
+ const JH_index word_length,
+ const JH_index word_id,
+ const JH_index sorted_word_id,
+ FILE io [const restrict static 1]
+)
+{
+ JH_char * stored_word;
+
+ if (k->words_length == JH_INDEX_MAX)
+ {
+ JH_S_ERROR
+ (
+ io,
+ "Unable to add word: the variable that stores the number of known "
+ "words would overflow."
+ );
+
+ return -1;
+ }
+
+ stored_word = copy_word(word, word_length, io);
+
+ if (stored_word == (JH_char *) NULL)
+ {
+ return -1;
+ }
+
+ k->words_length += 1;
+
+ if (reallocate_words_list(k, io) < 0)
+ {
+ k->words_length -= 1;
+
+ return -1;
+ }
+
+ initialize_word(k->words + word_id);
+
+ k->words[word_id].word = stored_word;
+ k->words[word_id].word_length = word_length;
+
+ if (reallocate_words_sorted_list(k, io) < 0)
+ {
+ k->words_length -= 1;
+
+ return -1;
+ }
+
+ set_nth_word(k, sorted_word_id, word_id);
+
+ return 0;
+}
+
+/******************************************************************************/
+/** EXPORTED ******************************************************************/
+/******************************************************************************/
+
+int JH_knowledge_learn_word
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_char word [const restrict static 1],
+ const size_t word_length,
+ JH_index word_id [const restrict static 1],
+ FILE io [const restrict static 1]
+)
+{
+ JH_index sorted_id;
+
+ if (word_length >= (size_t) JH_INDEX_MAX)
+ {
+ JH_S_ERROR(io, "Word is too long to be learned.");
+
+ return -1;
+ }
+
+ if
+ (
+ JH_knowledge_find_word_id
+ (
+ k,
+ word,
+ (((size_t) word_length) * sizeof(JH_char)),
+ word_id
+ ) == 0
+ )
+ {
+ JH_DEBUG
+ (
+ io,
+ JH_DEBUG_KNOWLEDGE_LEARN_WORD,
+ "Word of size %u is already known (id: %u).",
+ (JH_index) word_length,
+ *word_id
+ );
+
+ return 0;
+ }
+
+ sorted_id = *word_id;
+ *word_id = k->words_length;
+
+ JH_DEBUG
+ (
+ io,
+ JH_DEBUG_KNOWLEDGE_LEARN_WORD,
+ "Learning new word of size %u (id: %u, sorted_id: %u).",
+ (JH_index) word_length,
+ *word_id,
+ sorted_id
+ );
+
+ return add_word(k, word, (JH_index) word_length, *word_id, sorted_id, io);
+}
diff --git a/src/knowledge/knowledge_search.c b/src/knowledge/knowledge_search.c
new file mode 100644
index 0000000..40feae9
--- /dev/null
+++ b/src/knowledge/knowledge_search.c
@@ -0,0 +1,213 @@
+#include <stdlib.h>
+
+#include "../core/char.h"
+#include "../core/index.h"
+#include "../sequence/sequence.h"
+
+#include "../error/error.h"
+
+#include "knowledge.h"
+
+/* See "knowledge.h". */
+int JH_knowledge_find_word_id
+(
+ const struct JH_knowledge k [const restrict static 1],
+ const JH_char word [const restrict static 1],
+ const size_t word_length,
+ JH_index result [const restrict static 1]
+)
+{
+ /* This is a binary search */
+ int cmp;
+ JH_index i, current_min, current_max;
+
+ /* Handles the case where the list is empty ********************************/
+ current_max = k->words_length;
+
+ if (current_max == 0)
+ {
+ *result = 0;
+
+ return -1;
+ }
+ /***************************************************************************/
+
+ current_min = 0;
+ current_max -= 1;
+
+ while (current_min <= current_max)
+ {
+ i = (current_min + ((current_max - current_min) / 2));
+
+ cmp =
+ JH_word_cmp
+ (
+ word,
+ word_length,
+ k->words[k->words_sorted[i]].word,
+ k->words[k->words_sorted[i]].word_length
+ );
+
+ if (cmp > 0)
+ {
+ current_min = (i + 1);
+
+ if (current_min > current_max)
+ {
+ *result = current_min;
+
+ return -1;
+ }
+ }
+ else if (cmp < 0)
+ {
+ if ((current_min >= current_max) || (i == 0))
+ {
+ *result = current_min;
+
+ return -1;
+ }
+
+ current_max = (i - 1);
+ }
+ else
+ {
+ *result = k->words_sorted[i];
+
+ return 0;
+ }
+ }
+
+ *result = current_min;
+
+ return -1;
+}
+
+int JH_knowledge_find_markov_sequence
+(
+ const JH_index sequence_id,
+ const struct JH_knowledge_sequence_collection sc [const restrict static 1],
+ JH_index result [const restrict static 1]
+)
+{
+ /* This is a binary search */
+ int cmp;
+ JH_index i, current_min, current_max;
+
+ if (sc->sequences_ref_length == 0)
+ {
+ *result = 0;
+
+ return -1;
+ }
+
+ current_min = 0;
+ current_max = (sc->sequences_ref_length - 1);
+
+ while (current_min <= current_max)
+ {
+ i = (current_min + ((current_max - current_min) / 2));
+
+ cmp =
+ JH_index_cmp
+ (
+ sequence_id,
+ sc->sequences_ref[sc->sequences_ref_sorted[i]].id
+ );
+
+ if (cmp > 0)
+ {
+ current_min = (i + 1);
+
+ if (current_min > current_max)
+ {
+ *result = current_min;
+
+ return -1;
+ }
+ }
+ else if (cmp < 0)
+ {
+ if ((current_min >= current_max) || (i == 0))
+ {
+ *result = current_min;
+
+ return -1;
+ }
+
+ current_max = (i - 1);
+ }
+ else
+ {
+ *result = sc->sequences_ref_sorted[i];
+
+ return 0;
+ }
+ }
+
+ *result = current_min;
+
+ return -1;
+}
+
+int JH_knowledge_find_sequence_target
+(
+ const JH_index target_id,
+ const struct JH_knowledge_sequence_data sd [const restrict static 1],
+ JH_index result [const restrict static 1]
+)
+{
+ /* This is a binary search */
+ int cmp;
+ JH_index i, current_min, current_max;
+
+ if (sd->targets_length == 0)
+ {
+ *result = 0;
+
+ return -1;
+ }
+
+ current_min = 0;
+ current_max = (sd->targets_length - 1);
+
+ while (current_min <= current_max)
+ {
+ i = (current_min + ((current_max - current_min) / 2));
+
+ cmp = JH_index_cmp(target_id, sd->targets[i].id);
+
+ if (cmp > 0)
+ {
+ current_min = (i + 1);
+
+ if (current_min > current_max)
+ {
+ *result = current_min;
+
+ return -1;
+ }
+ }
+ else if (cmp < 0)
+ {
+ if ((current_min >= current_max) || (i == 0))
+ {
+ *result = current_min;
+
+ return -1;
+ }
+
+ current_max = (i - 1);
+ }
+ else
+ {
+ *result = i;
+
+ return 0;
+ }
+ }
+
+ *result = current_min;
+
+ return -1;
+}
diff --git a/src/knowledge/knowledge_swt_tws_modifications.c b/src/knowledge/knowledge_swt_tws_modifications.c
new file mode 100644
index 0000000..2acd093
--- /dev/null
+++ b/src/knowledge/knowledge_swt_tws_modifications.c
@@ -0,0 +1,333 @@
+#include <stdlib.h>
+
+#include "../core/index.h"
+
+#include "../error/error.h"
+
+#include "knowledge.h"
+
+static int add_target
+(
+ struct JH_knowledge_sequence_data sd [const restrict static 1],
+ const JH_index target_id,
+ const JH_index s_index,
+ const JH_index t_index,
+ FILE io [const restrict static 1]
+)
+{
+ struct JH_knowledge_target * new_p;
+
+ /* (sd->targets_length == JH_INDEX_MAX) => target_id \in sd->targets. */
+
+ sd->targets_length += 1;
+
+ new_p =
+ (struct JH_knowledge_target *) realloc
+ (
+ (void *) sd->targets,
+ (sd->targets_length * sizeof(struct JH_knowledge_target))
+ );
+
+ if (new_p == (struct JH_knowledge_target *) NULL)
+ {
+ JH_S_ERROR
+ (
+ io,
+ "[E] Unable to allocate memory required to store more targets."
+ );
+
+ sd->targets_length -= 1;
+
+ return -1;
+ }
+
+ sd->targets = new_p;
+
+ if (t_index != (sd->targets_length - 1))
+ {
+ memmove
+ (
+ (void *) (sd->targets + t_index + 1),
+ (const void *) (sd->targets + t_index),
+ (size_t)
+ (
+ ((sd->targets_length - t_index) - 1)
+ * sizeof(struct JH_knowledge_target)
+ )
+ );
+ }
+
+ sd->targets[t_index].id = target_id;
+ sd->targets[t_index].occurrences = 0;
+
+ return 0;
+}
+
+static int add_sequence
+(
+ struct JH_knowledge_sequence_collection sc [const restrict static 1],
+ const JH_index sequence_id,
+ JH_index s_index [const restrict static 1],
+ FILE io [const restrict static 1]
+)
+{
+ struct JH_knowledge_sequence_data * new_p;
+ JH_index * new_ps;
+
+ /*
+ * (sc->sequences_ref_length == JH_INDEX_MAX) =>
+ * sequence_id \in sc->sequences_ref.
+ */
+
+ sc->sequences_ref_length += 1;
+
+ new_p =
+ (struct JH_knowledge_sequence_data *) realloc
+ (
+ (void *) sc->sequences_ref,
+ (sc->sequences_ref_length * sizeof(struct JH_knowledge_sequence_data))
+ );
+
+ if (new_p == (struct JH_knowledge_sequence_data *) NULL)
+ {
+ JH_S_ERROR
+ (
+ io,
+ "[E] Unable to allocate memory required to store new preceding or "
+ " following sequence."
+ );
+
+ sc->sequences_ref_length -= 1;
+
+ return -1;
+ }
+
+ sc->sequences_ref = new_p;
+
+ new_ps =
+ (JH_index *) realloc
+ (
+ (void *) sc->sequences_ref_sorted,
+ (sc->sequences_ref_length * sizeof(JH_index))
+ );
+
+ if (new_p == (struct JH_knowledge_sequence_data *) NULL)
+ {
+ JH_S_ERROR
+ (
+ io,
+ "[E] Unable to allocate memory required to store new preceding or "
+ " following sequence."
+ );
+
+ sc->sequences_ref_length -= 1;
+
+ return -1;
+ }
+
+ sc->sequences_ref_sorted = new_ps;
+
+ if (*s_index != (sc->sequences_ref_length - 1))
+ {
+ memmove
+ (
+ (void *) (sc->sequences_ref_sorted + (*s_index) + 1),
+ (const void *) (sc->sequences_ref_sorted + (*s_index)),
+ (size_t)
+ (
+ ((sc->sequences_ref_length - (*s_index)) - 1)
+ * sizeof(JH_index)
+ )
+ );
+ }
+
+ sc->sequences_ref_sorted[*s_index] = (sc->sequences_ref_length - 1);
+ *s_index = (sc->sequences_ref_length - 1);
+
+ sc->sequences_ref[*s_index].id = sequence_id;
+ sc->sequences_ref[*s_index].occurrences = 0;
+ sc->sequences_ref[*s_index].targets = (struct JH_knowledge_target *) NULL;
+ sc->sequences_ref[*s_index].targets_length = 0;
+
+ return 0;
+}
+
+int JH_knowledge_strengthen_swt
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index sequence_id,
+ const JH_index word_id,
+ const JH_index target_id,
+ FILE io [const restrict static 1]
+)
+{
+ JH_index s_index, t_index;
+
+ if
+ (
+ JH_knowledge_find_markov_sequence
+ (
+ sequence_id,
+ &(k->words[word_id].swt),
+ &s_index
+ ) < 0
+ )
+ {
+ if
+ (
+ add_sequence
+ (
+ &(k->words[word_id].swt),
+ sequence_id,
+ &s_index,
+ io
+ ) < 0
+ )
+ {
+ return -1;
+ }
+ }
+
+ if
+ (
+ JH_knowledge_find_sequence_target
+ (
+ target_id,
+ (k->words[word_id].swt.sequences_ref + s_index),
+ &t_index
+ ) < 0
+ )
+ {
+ if
+ (
+ add_target
+ (
+ &(k->words[word_id].swt.sequences_ref[s_index]),
+ target_id,
+ s_index,
+ t_index,
+ io
+ ) < 0
+ )
+ {
+ return -1;
+ }
+ }
+
+ if
+ (
+ (
+ k->words[word_id].swt.sequences_ref[s_index].occurrences
+ == JH_INDEX_MAX
+ )
+ ||
+ (
+ k->words[word_id].swt.sequences_ref[s_index].targets[t_index].occurrences
+ == JH_INDEX_MAX
+ )
+ )
+ {
+ JH_S_WARNING
+ (
+ io,
+ "[W] Unable to strengthen SWT link: link is already at max strength."
+ );
+
+ return 1;
+ }
+
+ k->words[word_id].swt.sequences_ref[s_index].occurrences += 1;
+ k->words[word_id].swt.sequences_ref[s_index].targets[t_index].occurrences += 1;
+
+ return 0;
+}
+
+int JH_knowledge_strengthen_tws
+(
+ struct JH_knowledge k [const restrict static 1],
+ const JH_index target_id,
+ const JH_index word_id,
+ const JH_index sequence_id,
+ FILE io [const restrict static 1]
+)
+{
+ JH_index s_index, t_index;
+
+ if
+ (
+ JH_knowledge_find_markov_sequence
+ (
+ sequence_id,
+ &(k->words[word_id].tws),
+ &s_index
+ ) < 0
+ )
+ {
+ if
+ (
+ add_sequence
+ (
+ &(k->words[word_id].tws),
+ sequence_id,
+ &s_index,
+ io
+ ) < 0
+ )
+ {
+ return -1;
+ }
+ }
+
+ if
+ (
+ JH_knowledge_find_sequence_target
+ (
+ target_id,
+ (k->words[word_id].tws.sequences_ref + s_index),
+ &t_index
+ ) < 0
+ )
+ {
+ if
+ (
+ add_target
+ (
+ &(k->words[word_id].tws.sequences_ref[s_index]),
+ target_id,
+ s_index,
+ t_index,
+ io
+ ) < 0
+ )
+ {
+ return -1;
+ }
+ }
+
+ if
+ (
+ (
+ k->words[word_id].tws.sequences_ref[s_index].occurrences
+ == JH_INDEX_MAX
+ )
+ ||
+ (
+ k->words[word_id].tws.sequences_ref[s_index].targets[t_index].occurrences
+ == JH_INDEX_MAX
+ )
+ )
+ {
+ JH_S_ERROR
+ (
+ io,
+ "[E] Unable to strengthen TWS link: link is already at max strength."
+ );
+
+ return -1;
+ }
+
+ k->words[word_id].tws.sequences_ref[s_index].occurrences += 1;
+ k->words[word_id].tws.sequences_ref[s_index].targets[t_index].occurrences += 1;
+
+ return 0;
+}
diff --git a/src/knowledge/knowledge_types.h b/src/knowledge/knowledge_types.h
new file mode 100644
index 0000000..82073ff
--- /dev/null
+++ b/src/knowledge/knowledge_types.h
@@ -0,0 +1,62 @@
+#ifndef _JH_KNOWLEDGE_KNOWLEDGE_TYPES_H_
+#define _JH_KNOWLEDGE_KNOWLEDGE_TYPES_H_
+
+#ifndef JH_RUNNING_FRAMA_C
+ #include <pthread.h>
+#endif
+
+#include "../core/index_types.h"
+#include "../core/char_types.h"
+
+struct JH_knowledge_target
+{
+ JH_index id;
+ JH_index occurrences;
+};
+
+struct JH_knowledge_sequence_data
+{
+ JH_index id;
+ JH_index occurrences;
+ struct JH_knowledge_target * targets;
+ JH_index targets_length;
+};
+
+struct JH_knowledge_sequence_collection
+{
+ struct JH_knowledge_sequence_data * sequences_ref;
+ JH_index sequences_ref_length;
+ JH_index * sequences_ref_sorted;
+};
+
+struct JH_knowledge_word
+{
+ const JH_char * word;
+ JH_index word_length;
+ JH_index occurrences;
+
+ /* [Sequence] [Word] [Target] */
+ struct JH_knowledge_sequence_collection swt;
+
+ /* [Target] [Word] [Sequence] */
+ struct JH_knowledge_sequence_collection tws;
+};
+
+struct JH_knowledge
+{
+#ifndef JH_RUNNING_FRAMA_C
+ pthread_mutex_t mutex;
+#else
+ int mutex;
+#endif
+
+ struct JH_knowledge_word * words;
+ JH_index words_length;
+ JH_index * words_sorted;
+
+ JH_index ** sequences;
+ JH_index sequences_length;
+ JH_index * sequences_sorted;
+};
+
+#endif