cAI/cNLP/Library/c_NlpTrie.c

#include <c_NlpTrie.h>

#include "c_Memory.h"
#include <c_StringBuffer.h>

/* ------------------------------------------------------------------------------------------------------------------ */
/*  */

#define ALPHABET_SIZE 256

/* ------------------------------------------------------------------------------------------------------------------ */
/*  */

struct c_NlpTrieNode_t {
    struct c_NlpTrieNode_t* children[ALPHABET_SIZE];
    c_bool_t is_end_of_word;
};

/* ------------------------------------------------------------------------------------------------------------------ */
/*  */

C_STATIC_FORCE_INLINE
c_NlpTrieNode_t* c_NlpTrieNode_Create(void) {
    c_NlpTrieNode_t* node = (c_NlpTrieNode_t*)C_ALLOC(sizeof(*node));
    if (node == NULL) {
        return NULL;
    }
    node->is_end_of_word = C_FALSE;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    return node;
}

C_STATIC_FORCE_INLINE
void c_NlpTrieNode_Destroy(c_NlpTrieNode_t* node) {
    C_FREE(node);
}

static void c_NlpTrieNode_FreeSubtree(c_NlpTrieNode_t* node) {
    if (node == NULL) {
        return;
    }
    // 递归释放所有存活的子分支
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (node->children[i] != NULL) {
            c_NlpTrieNode_FreeSubtree(node->children[i]);
        }
    }
    // 使用用户指定的底层接口释放当前节点
    c_NlpTrieNode_Destroy(node);
}

/* ------------------------------------------------------------------------------------------------------------------ */
/*  */

c_err_t c_NlpTrie_Init(c_NlpTrie_t* self) {
    if (!self) return C_ERR_PARAM;
    self->root = c_NlpTrieNode_Create();
    if (self->root == NULL) {
        return C_ERR_NOMEM;
    }
    self->size = 0;
    return C_ERR_OK;
}

void c_NlpTrie_Destroy(c_NlpTrie_t* self) {
    if (self == NULL || self->root == NULL) {
        return;
    }
    // 调用带深度扫描的子树释放函数
    c_NlpTrieNode_FreeSubtree(self->root);
    self->root = NULL;
    self->size = 0;
}

c_err_t c_NlpTrie_Insert(c_NlpTrie_t* self, const char* word) {
    if (!self || !self->root || !word) {
        return C_ERR_PARAM;
    }

    c_NlpTrieNode_t* curr = self->root;
    for (c_size_t i = 0; word[i] != '\0'; i++) {
        // 转换为 uint8_t，确保中文字符等多字节编码（负值）在 0~255 范围内安全索引
        const uint8_t index = (uint8_t)word[i];

        if (curr->children[index] == NULL) {
            curr->children[index] = c_NlpTrieNode_Create();
            if (curr->children[index] == NULL) {
                return C_ERR_NOMEM; // 内存池耗尽或分配失败
            }
        }
        curr = curr->children[index];
    }

    curr->is_end_of_word = C_TRUE;
    self->size++;
    return C_ERR_OK;
}

c_bool_t c_NlpTrie_Contains(c_NlpTrie_t* self, const char* word) {
    if (!self || !self->root || !word) {
        return C_FALSE;
    }

    c_NlpTrieNode_t* curr = self->root;
    for (c_size_t i = 0; word[i] != '\0'; i++) {
        const uint8_t index = (uint8_t)word[i];

        if (curr->children[index] == NULL) {
            return C_FALSE;
        }
        curr = curr->children[index];
    }

    return curr->is_end_of_word;
}

c_bool_t c_NlpTrie_HasStartWith(c_NlpTrie_t* self, const char* word) {
    if (!self || !self->root || !word) {
        return C_FALSE;
    }

    c_NlpTrieNode_t* curr = self->root;
    for (c_size_t i = 0; word[i] != '\0'; i++) {
        const uint8_t index = (uint8_t)word[i];

        if (curr->children[index] == NULL) {
            return C_FALSE;
        }
        curr = curr->children[index];
    }

    return C_TRUE;
}

c_err_t c_NlpTrie_LongestPrefixOf(c_NlpTrie_t* self, const char* text, char* result, c_size_t res_max_len) {
    if (!self || !self->root || !text || !result || res_max_len == 0) {
        return C_ERR_PARAM;
    }

    // 初始化返回值为空字符串
    result[0] = '\0';

    c_NlpTrieNode_t* curr = self->root;
    c_size_t longest_len = 0; // 记录最长匹配的字符长度

    // 遍历输入文本
    for (c_size_t i = 0; text[i] != '\0'; i++) {
        const uint8_t index = (uint8_t)text[i];

        // 字符链断开，无法继续匹配更长的前缀，退出循环
        if (curr->children[index] == NULL) {
            break;
        }

        curr = curr->children[index];

        // 如果当前节点是一个完整单词的结尾，更新最长匹配长度
        if (curr->is_end_of_word) {
            longest_len = i + 1;
        }
    }

    // 如果找到了有效匹配，且长度在安全缓冲区范围内，进行拷贝
    if (longest_len > 0) {
        c_size_t copy_len = (longest_len < res_max_len) ? longest_len : (res_max_len - 1);
        strncpy(result, text, copy_len);
        result[copy_len] = '\0';
    }

    return C_ERR_OK;
}

c_size_t c_NlpTrie_LongestPrefixOfLen(c_NlpTrie_t* self, const char* text) {
    if (!self || !self->root || !text) {
        return 0;
    }

    c_NlpTrieNode_t* curr = self->root;
    c_size_t longest_len = 0;

    for (c_size_t i = 0; text[i] != '\0'; i++) {
        const uint8_t index = (uint8_t)text[i];
        if (curr->children[index] == NULL) {
            break;
        }
        curr = curr->children[index];
        if (curr->is_end_of_word) {
            longest_len = i + 1;
        }
    }

    return longest_len;
}




/* --- DFS Core Backtracking Engine with StringBuffer --- */

/**
 * @brief Internal recursive function to perform DFS using c_StringBuffer.
 * @param node       Current Trie node being evaluated.
 * @param sb         Pointer to the active string buffer tracking the current path.
 * @param output     Pointer to the destination string list collector.
 * @return c_err_t   C_ERR_OK on success, or C_ERR_NOMEM if string buffer allocation fails.
 */
static c_err_t c_NlpTrie_CollectDFS(c_NlpTrieNode_t* node, c_StringBuffer_t* sb, c_NlpStringList_t* output) {
    if (node == NULL) {
        return C_ERR_OK;
    }

    // 1. If this node marks an established word end, copy the raw payload directly into the list
    if (node->is_end_of_word) {
        c_err_t err = c_NlpStringList_Add(output, sb->buffer, sb->size);
        if (err != C_ERR_OK) return err;
    }

    // 2. Recurse down all 256 possible byte paths (handles raw ASCII and UTF-8 branches seamlessly)
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (node->children[i] != NULL) {
            char ch = (char)i;

            // Append the single byte character onto the current tracking path path
            c_err_t err = c_StringBuffer_Append(sb, &ch, 1);
            if (err != C_ERR_OK) return err;

            // Deep traverse down the branch
            err = c_NlpTrie_CollectDFS(node->children[i], sb, output);
            if (err != C_ERR_OK) return err;

            // Backtrack: Remove the trailing byte character to restore original buffer size context
            err = c_StringBuffer_RemoveAt(sb, sb->size - 1, 1);
            if (err != C_ERR_OK) return err;
        }
    }

    return C_ERR_OK;
}

/* --- Public Core API Implementation --- */

c_err_t c_NlpTrie_KeysWithPrefix(c_NlpTrie_t* self, const char* prefix, c_NlpStringList_t* output) {
    if (!self || !self->root || !prefix || !output) {
        return C_ERR_PARAM;
    }

    // 1. Initialize output list allocation safely
    c_err_t err = c_NlpStringList_Init(output, 4);
    if (err != C_ERR_OK) return err;

    // 2. Locate the specific sub-root node where the given prefix stream terminates
    c_NlpTrieNode_t* curr = self->root;
    size_t prefix_len = 0;
    for (size_t i = 0; prefix[i] != '\0'; i++) {
        unsigned char index = (unsigned char)prefix[i];
        if (curr->children[index] == NULL) {
            // Prefix does not exist in the tree; return an empty list gracefully
            return C_ERR_OK;
        }
        curr = curr->children[index];
        prefix_len++;
    }

    // 3. Initialize the temporary dynamic path buffer structure
    c_StringBuffer_t sb;
    err = c_StringBuffer_Init(&sb, prefix_len + 16);
    if (err != C_ERR_OK) {
        c_NlpStringList_Destroy(output);
        return err;
    }

    // 4. Pre-populate the tracking path layout with the found prefix string base
    err = c_StringBuffer_Append(&sb, prefix, prefix_len);
    if (err != C_ERR_OK) {
        c_StringBuffer_Destroy(&sb);
        c_NlpStringList_Destroy(output);
        return err;
    }

    // 5. Deploy DFS traversal starting from the located prefix sub-root
    err = c_NlpTrie_CollectDFS(curr, &sb, output);

    // 6. Complete garbage collection on the temporary working buffer layout
    c_StringBuffer_Destroy(&sb);

    // Rollback entirely if OOM conditions tripped during sub-branch traversals
    if (err != C_ERR_OK) {
        c_NlpStringList_Destroy(output);
        return err;
    }

    return C_ERR_OK;
}

/* ------------------------------------------------------------------------------------------------------------------ */
/*  */



/**
 * @brief Internal recursive engine to perform wildcard pattern matching traversal.
 * @param node         Current Trie node being evaluated.
 * @param pattern      The full pattern query string.
 * @param pattern_idx  The current character position we are evaluating in the pattern.
 * @param sb           Pointer to the dynamic string buffer managing the matching path.
 * @param output       Pointer to the string list collector.
 * @return c_err_t     C_ERR_OK on success, or execution allocation errors.
 */
static c_err_t c_NlpTrie_MatchDFS(c_NlpTrieNode_t* node, const char* pattern, size_t pattern_idx,
                                  c_StringBuffer_t* sb, c_NlpStringList_t* output) {
    if (node == NULL) {
        return C_ERR_OK;
    }

    char current_pattern_char = pattern[pattern_idx];

    // Base Case: We reached the end of the pattern string
    if (current_pattern_char == '\0') {
        // If the current path structure forms a valid dictionary entry, collect it
        if (node->is_end_of_word) {
            c_err_t err = c_NlpStringList_Add(output, sb->buffer, sb->size);
            if (err != C_ERR_OK) return err;
        }
        return C_ERR_OK;
    }

    // Branch Case A: Wildcard character '.' matches any of the 256 branches
    if (current_pattern_char == '.') {
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            if (node->children[i] != NULL) {
                char ch = (char)i;

                // Push branch byte onto string buffer path
                c_err_t err = c_StringBuffer_Append(sb, &ch, 1);
                if (err != C_ERR_OK) return err;

                // Move forward to the next node and advance pattern evaluation index
                err = c_NlpTrie_MatchDFS(node->children[i], pattern, pattern_idx + 1, sb, output);
                if (err != C_ERR_OK) return err;

                // Backtrack: Remove trailing byte character context
                err = c_StringBuffer_RemoveAt(sb, sb->size - 1, 1);
                if (err != C_ERR_OK) return err;
            }
        }
    }
    // Branch Case B: Literal character match - process direct branch index
    else {
        unsigned char index = (unsigned char)current_pattern_char;
        if (node->children[index] != NULL) {
            // Push literal character byte onto string buffer path
            c_err_t err = c_StringBuffer_Append(sb, &current_pattern_char, 1);
            if (err != C_ERR_OK) return err;

            // Recurse to next node
            err = c_NlpTrie_MatchDFS(node->children[index], pattern, pattern_idx + 1, sb, output);
            if (err != C_ERR_OK) return err;

            // Backtrack
            err = c_StringBuffer_RemoveAt(sb, sb->size - 1, 1);
            if (err != C_ERR_OK) return err;
        }
    }

    return C_ERR_OK;
}

/* --- Public Core API Implementation --- */

c_err_t c_NlpTrie_KeysThatMatch(c_NlpTrie_t* self, const char* pattern, c_NlpStringList_t* output) {
    if (!self || !self->root || !pattern || !output) {
        return C_ERR_PARAM;
    }

    // Initialize list to collect matches (initial capacity of 4 items)
    c_err_t err = c_NlpStringList_Init(output, 4);
    if (err != C_ERR_OK) return err;

    // Initialize tracking string buffer path to dynamically record characters
    c_StringBuffer_t sb;
    c_size_t estimate_len = strlen(pattern);
    err = c_StringBuffer_Init(&sb, estimate_len + 4);
    if (err != C_ERR_OK) {
        c_NlpStringList_Destroy(output);
        return err;
    }

    // Deploy the recursive match search starting at the root layout node
    err = c_NlpTrie_MatchDFS(self->root, pattern, 0, &sb, output);

    // Clean up temporary path string buffer state
    c_StringBuffer_Destroy(&sb);

    if (err != C_ERR_OK) {
        c_NlpStringList_Destroy(output); // Rollback dynamic arrays on inner traversal failures
        return err;
    }

    return C_ERR_OK;
}

/* ------------------------------------------------------------------------------------------------------------------ */
/*  */

/**
 * @brief Internal helper to check if a node contains any active child pointer.
 * @return c_bool_t C_TRUE if completely empty of branches, otherwise C_FALSE.
 */
C_STATIC_FORCE_INLINE
c_bool_t c_NlpTrieNode_IsEmpty(c_NlpTrieNode_t* node) {
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (node->children[i] != NULL) {
            return C_FALSE; // Found an active sub-branch path
        }
    }
    return C_TRUE;
}

/**
 * @brief Internal recursive engine to trace characters and clean up dead nodes bottom-up.
 * @param node       Current Trie node being evaluated.
 * @param word       The target deletion string text stream.
 * @param depth      The current character offset index.
 * @param deleted    Output flag signaling the parent layout layer that the child was destroyed.
 * @return c_NlpTrieNode_t* Returns the adjusted pointer state of the evaluated node to update its parent.
 */
static c_NlpTrieNode_t* c_NlpTrie_DeleteDFS(c_NlpTrieNode_t* node, const char* word, size_t depth, c_bool_t* deleted) {
    if (node == NULL) {
        return NULL;
    }

    // Base Case: We have fully processed the last byte character of the word
    if (word[depth] == '\0') {
        if (node->is_end_of_word) {
            node->is_end_of_word = C_FALSE; // Deactivate word completion flag
            *deleted = C_TRUE;
        }

        // If this node serves no purpose for another word suffix, mark it for pruning
        if (c_NlpTrieNode_IsEmpty(node)) {
            c_NlpTrieNode_Destroy(node);
            return NULL;
        }
        return node;
    }

    // Recursive Step: Extract index byte and traverse deeper down the branch
    const uint8_t index = (uint8_t)word[depth];
    node->children[index] = c_NlpTrie_DeleteDFS(node->children[index], word, depth + 1, deleted);

    // Post-Order Backtracking Pruning: Evaluate this node on the way up
    // We can only prune this node if:
    // 1. It is not marked as the end of a shorter word (is_end_of_word == C_FALSE)
    // 2. It has no other active branches left hanging under it
    if (node->is_end_of_word == C_FALSE && c_NlpTrieNode_IsEmpty(node)) {
        c_NlpTrieNode_Destroy(node);
        return NULL;
    }

    return node;
}

/* --- Public Core API Implementation --- */

c_err_t c_NlpTrie_Delete(c_NlpTrie_t* self, const char* word) {
    if (!self || !self->root || !word) {
        return C_ERR_PARAM;
    }

    // Edge Case: Prevent actions if attempting to pass an empty string
    if (word[0] == '\0') {
        return C_ERR_OK;
    }

    c_bool_t deleted = C_FALSE;

    // Execute the recursive deletion pattern starting right from the root node layer
    self->root = c_NlpTrie_DeleteDFS(self->root, word, 0, &deleted);

    // Safety fallback: If the entire tree was pruned down, restore a valid base root node layout
    if (self->root == NULL) {
        self->root = c_NlpTrieNode_Create();
        if (self->root == NULL) {
            return C_ERR_NOMEM;
        }
    }

    return C_ERR_OK;
}

/* ------------------------------------------------------------------------------------------------------------------ */
/*  */

c_err_t c_NlpTrie_Clear(c_NlpTrie_t* self) {
    // 1. Guard against invalid instances or missing base parameters
    if (!self || !self->root) {
        return C_ERR_PARAM;
    }

    // 2. Loop through all 256 structural starting slot positions of the root node
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (self->root->children[i] != NULL) {
            // Recursively destroy every deeper sub-branch path found
            c_NlpTrieNode_FreeSubtree(self->root->children[i]);
            self->root->children[i] = NULL; // Explicitly nullify pointer to prevent dangling handles
        }
    }

    // 3. Reset the root node's completion flag context
    self->root->is_end_of_word = C_FALSE;

    return C_ERR_OK;
}