/*
 * Copyright (C) 2025 Валери Владев <vdev@lavabit.com>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; version 2
 * of the License.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

/**
 * Linear Trie implementation for directed graphs, dictionaries, or other sequence-based data.
 * Supports insertion and search of paths (e.g., graph routes [0,1,2] or words "cat").
 * Uses bit manipulation for compact storage and efficient lookup.
 *
 * Key features:
 * - letters_table: Bitmask for available elements (nodes or letters).
 * - count_uper_bits: Compresses shared prefixes for memory efficiency.
 * - weight: Stores metadata (e.g., latency for routes, frequency for words).
 *
 * Potential extensions:
 * - Add delete_trie() for removing paths.
 * - Implement autocomplete for prefixes (e.g., all words starting with "ca").
 * - Support cycles in graphs by modifying path validation.
 * - Optimize for large alphabets (LLA > 64) with larger bitmasks.
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define LLA 100 // Maximum number of elements (nodes in graph or letters in alphabet)
#define BIT_END (LLA) // Position for BIT_END marker

struct node {
    uint64_t letters_table; // Bitmask for available elements
    struct node* next;      // Pointer to next node in the list
    uint32_t weight;        // Weight for BIT_END nodes (e.g., latency, frequency)
};

/**
 * Counts bits set in letters_table from pos+1 to LLA-1.
 * Used for prefix compression and skipping nodes.
 */
int count_uper_bits(struct node* i, int pos) {
    int count = 0;
    for (int j = pos + 1; j < LLA; j++) {
        if (i->letters_table & (1ULL << j)) {
            count++;
        }
    }
    return count;
}

/**
 * Inserts a path (sequence of elements) into the Trie.
 * @param root Pointer to the root node.
 * @param path Array of element IDs (e.g., [0,1,2] for graph, [2,0,19] for "cat").
 * @param path_len Length of the path.
 * @param weight Weight for the path (e.g., latency, frequency).
 */
void insert_trie(struct node* root, int* path, int path_len, int weight) {
    struct node* i = root;
    for (int k = 0; k < path_len; k++) {
        int pos = path[k];
        i->letters_table |= (1ULL << pos); // Set bit for current element
        int n = count_uper_bits(i, pos);
        if (n > 0) {
            // Skip n nodes for existing elements
            for (int j = n; j > 0; j--) {
                i = i->next;
            }
        } else {
            // Create new node and maintain list integrity
            struct node* new_node = calloc(1, sizeof(struct node));
            if (!new_node) {
                fprintf(stderr, "Memory allocation failed\n");
                exit(1);
            }
            struct node* temp = i->next; // Preserve current next
            i->next = new_node;          // Link new node
            i = i->next;                 // Move to new node
            i->next = temp;              // Restore link to old next
        }
    }
    // Mark end of path and set weight
    i->letters_table |= (1ULL << BIT_END);
    i->weight = weight;
}

/**
 * Searches for a path in the Trie.
 * @param root Pointer to the root node.
 * @param path Array of element IDs.
 * @param path_len Length of the path.
 * @param weight Pointer to store the weight (if found).
 * @return 1 if path exists, 0 otherwise.
 */
int search_trie(struct node* root, int* path, int path_len, uint32_t* weight) {
    struct node* i = root;
    for (int k = 0; k < path_len; k++) {
        int pos = path[k];
        if (!(i->letters_table & (1ULL << pos))) {
            return 0; // Element not found
        }
        int n = count_uper_bits(i, pos);
        for (int j = n; j > 0; j--) {
            if (!i->next) return 0;
            i = i->next;
        }
    }
    if (i->letters_table & (1ULL << BIT_END)) {
        *weight = i->weight;
        return 1; // Path found
    }
    return 0; // Path not found
}

/**
 * Frees the Trie memory.
 * @param root Pointer to the root node.
 */
void free_trie(struct node* root) {
    if (!root) return;
    free_trie(root->next);
    free(root);
}

/**
 * Example usage (can be removed or extended by community).
 */
int main() {
    struct node* root = calloc(1, sizeof(struct node));
    if (!root) {
        fprintf(stderr, "Memory allocation failed\n");
        return 1;
    }

    // Example: Insert graph paths
    int path1[] = {0, 1};     // Path 0->1
    int path2[] = {1, 2};     // Path 1->2
    int path3[] = {0, 1, 2};  // Path 0->1->2
    insert_trie(root, path1, 2, 10);  // Weight: 10
    insert_trie(root, path2, 2, 15);  // Weight: 15
    insert_trie(root, path3, 3, 25);  // Weight: 25

    // Example: Search paths
    uint32_t weight;
    if (search_trie(root, path1, 2, &weight)) {
        printf("Path [0,1] found, weight: %u\n", weight);
    } else {
        printf("Path [0,1] not found\n");
    }
    int path4[] = {0, 2};
    if (search_trie(root, path4, 2, &weight)) {
        printf("Path [0,2] found, weight: %u\n", weight);
    } else {
        printf("Path [0,2] not found\n");
    }

    free_trie(root);
    return 0;
}