#define INT_BITS 32
#define MAX_ASSETS 1000  

typedef struct TrieNode {
    struct TrieNode* bit[2];
} TrieNode;

// Dynamically Allocate Trie Nodes
TrieNode* newTrieNode() {
    TrieNode* newNode = (TrieNode*)malloc(sizeof(TrieNode));  
    if (!newNode) {
        printf("\n Memory allocation failed in newTrieNode()");
        return NULL;
    }
    newNode->bit[0] = NULL;
    newNode->bit[1] = NULL;
    return newNode;
}

// Free Trie Memory After Use
void freeTrie(TrieNode* root) {
    if (!root) return;
    freeTrie(root->bit[0]);
    freeTrie(root->bit[1]);
    free(root);
}

// Find the Highest Bit Position in the Dataset
int findHighestBit(int* numbers, int size) {
    int highestBit = 0;
    int i;
    for (i = 0; i < size; i++) {
        int num = numbers[i];
        int bitPos = 0;
        while (num) {
            bitPos++;
            num >>= 1;
        }
        if (bitPos > highestBit) highestBit = bitPos;
    }
    return highestBit - 1;  // Only use as many bits as needed
}

// Insert a Number into the Trie
void insert(TrieNode* root, int number, int highestBit) {
    if (!root) {
        printf("\n Error: Root is NULL in insert()! Skipping...\n");
        return;
    }

    TrieNode* current = root;
    int i;
    for (i = highestBit; i >= 0; i--) {
        int bit = (number >> i) & 1;
        if (!current->bit[bit]) {
            current->bit[bit] = newTrieNode();
            if (!current->bit[bit]) {
                printf("\n Error: Trie Node Creation Failed at Bit %d! Skipping...\n", i);
                return;
            }
        }
        current = current->bit[bit];
    }
}

// Find the Maximum XOR for a Given Number
int findMaxXOR(TrieNode* root, int number, int highestBit) {
    TrieNode* current = root;
    int maxXOR = 0;
    int i;
    for (i = highestBit; i >= 0; i--) {
        int bit = (number >> i) & 1;
        if (current->bit[1 - bit]) {
            maxXOR |= (1 << i);
            current = current->bit[1 - bit];
        } else {
            current = current->bit[bit];
        }
    }
    return maxXOR;
}

// Brute Force XOR Calculation
void maxXorBruteForce(int* assetReturns, int size) {
    int maxXOR = 0, best1 = 0, best2 = 0;
    int i, j;
    var start = timer();  // Start Timing

    for (i = 0; i < size; i++) {
        for (j = i + 1; j < size; j++) {
            int currentXOR = assetReturns[i] ^ assetReturns[j];
            if (currentXOR > maxXOR) {
                maxXOR = currentXOR;
                best1 = assetReturns[i];
                best2 = assetReturns[j];
            }
        }
    }

    var execTime = (timer() - start) * 1000;  // End Timing
    printf("\n Brute Force XOR: (%d, %d) -> XOR: %d | Time: %.3f ms", best1, best2, maxXOR, execTime);
}

// Optimized Max XOR Function (Trie)
void maxXorOptimized(int* assetReturns, int size) {
    TrieNode* root = newTrieNode();
    if (!root) return;

    int highestBit = findHighestBit(assetReturns, size);
    insert(root, assetReturns[0], highestBit);

    int maxXOR = 0, best1 = 0, best2 = 0;
    int i;
    var start = timer();  // Start Timing

    for (i = 1; i < size; i++) {
        int currentXOR = findMaxXOR(root, assetReturns[i], highestBit);
        if (currentXOR > maxXOR) {
            maxXOR = currentXOR;
            best1 = assetReturns[i];
            best2 = best1 ^ maxXOR;
        }
        insert(root, assetReturns[i], highestBit);
    }

    var execTime = (timer() - start) * 1000;  // End Timing
    printf("\n Optimized Trie XOR: (%d, %d) -> XOR: %d | Time: %.3f ms", best1, best2, maxXOR, execTime);

    freeTrie(root);  // Free Memory
}

// Generate Proper Random Asset Returns
void generateRandomAssetReturns(var* assetReturns, int numAssets, int numBars) {
    int i, j;
    printf("\n Debugging Random Values Before Conversion:\n");

    for (i = 0; i < numAssets; i++) {
        vars RandomSeries = series(0);  // Create a series to maintain randomness
        
        printf("Asset %d: ", i + 1);
        
        for (j = 0; j < numBars; j++) {
            if (j == 0)
                RandomSeries[j] = random();  // First value is random
            else
                RandomSeries[j] = RandomSeries[j - 1] + random() - 0.5;  //  Follow series logic
            
            assetReturns[i * numBars + j] = RandomSeries[j];  //  Store random values
            printf("%.5f ", assetReturns[i * numBars + j]);  //  Print values for debugging
        }
        printf("\n");
    }
}

// Convert Asset Returns to Binary Representation
int convertReturnsToBinary(var* returns, int length) {
    int binaryValue = 0;
    int i;

    for (i = 0; i < length; i++) {
        if (returns[i] > 0.05) binaryValue |= (1 << i);  
        else if (returns[i] < -0.05) binaryValue |= (1 << (i + length));  
    }

    return binaryValue;
}

// Lite-C Main Function
function run() {
    if (is(INITRUN)) {
        int numAssets = 1000;
        int numBars = 5;
        int i;
        int assetBinaryReturns[MAX_ASSETS];
        var* assetReturns = (var*)malloc(numAssets * numBars * sizeof(var));

        if (!assetReturns) {
            printf("\n Memory Allocation Failed for assetReturns! Exiting...\n");
            return;
        }

        generateRandomAssetReturns(assetReturns, numAssets, numBars);

        printf("\n Debugging Binary Conversions:\n");

        for (i = 0; i < numAssets; i++) {
            assetBinaryReturns[i] = convertReturnsToBinary(&assetReturns[i * numBars], numBars);
            printf("Asset %d Binary: %d\n", i + 1, assetBinaryReturns[i]);  //  Print binary values
        }

        //  Compare Brute Force and Optimized Trie Method
        maxXorBruteForce(assetBinaryReturns, numAssets);
        maxXorOptimized(assetBinaryReturns, numAssets);

        free(assetReturns);
    }
}

Asset 994 Binary: 775
Asset 995 Binary: 992
Asset 996 Binary: 992
Asset 997 Binary: 961
Asset 998 Binary: 961
Asset 999 Binary: 961
Asset 1000 Binary: 992
Brute Force XOR: (31, 992) -> XOR: 1023 | Time: 4095.300 ms
Optimized Trie XOR: (992, 31) -> XOR: 1023 | Time: 488.400 ms