#include 
#include 
#include 
#include 
using namespace std;
struct PatriciaTrieNode {
    int number, data;
    PatriciaTrieNode *left_child, *right_child;
    
    PatriciaTrieNode() {
        left_child = NULL;
        right_child = NULL;
    }
};
struct PatriciaTrie {
    PatriciaTrieNode *root;
    const int max_bits = 10;
    
    
    PatriciaTrie() {
        root = NULL;
    }
    void clear_trie() {
        root = NULL;
    }
    bool is_empty() {
        if(root == NULL) {
            return true;
        }
        return false;
    }
    
    bool bit(int k, int i) {
        string to_binary = "";
        for(int j = k; j > 0; j /= 2) {
            int modulo = j % 2;
            to_binary += (modulo + '0');
        }
        
        while(to_binary.size() != max_bits) {
            to_binary += "0";
        }
        reverse(to_binary.begin(), to_binary.end());
        
        return (to_binary[i - 1] == '1');
    }
    PatriciaTrieNode * search_node(PatriciaTrieNode * node, int k) {
        PatriciaTrieNode * current_node, * next_node;
        
        if(node == NULL) {
            return NULL;
        }
        
        next_node = node->left_child;
        current_node = node;
        
        while(next_node->number > current_node->number) {
            current_node = next_node;
            
            if(bit(k, next_node->number)) {
                next_node = next_node->right_child;
            }
            else {
                next_node = next_node->left_child;
            }
        }
        return next_node;
    }

    bool search(int k) {
        int tmp = (int) (log(k) / log(2));
        if(tmp > max_bits) {
            cout << "Trie is full!" << endl;
            return false;
        }
        PatriciaTrieNode * tmp_node = search_node(root, k);
        
        return (tmp_node->data == k);
    }
    
    PatriciaTrieNode * insert_node(PatriciaTrieNode * node, int value) {
        PatriciaTrieNode * current_node = NULL;
        PatriciaTrieNode * parent, * last_node, * new_node;
        
        if(node == NULL) {
            node = new PatriciaTrieNode();
            node->number = 0;
            node->data = value;
            node->left_child = node;
            node->right_child = NULL;
            
            return node;
        }
        last_node = search_node(node, value);
        if(value == last_node->data) {
            cout << "This key already exists" << endl;
            return node;
        }
        int i;
        for(i = 1; bit(value, i) == bit(last_node->data, i); i++) {
            current_node = root->left_child;
        }
        parent = node;

        while(current_node->number > parent->number and current_node->number < i) {
            parent = current_node;
            
            if(bit(value, current_node->number)) {
                current_node = current_node->right_child;
            }
            else {
                current_node = current_node->left_child;
            }
        }
        new_node = new PatriciaTrieNode();
        new_node->number = i;
        new_node->data = value;
        
        if(bit(value, i)) {
            new_node->left_child = current_node;
            new_node->right_child = new_node;
        }
        else {
            new_node->left_child = new_node;
            new_node->right_child = current_node;
        }
        
        if(current_node == parent->left_child) {
            parent->left_child = new_node;
        }
        else {
            parent->right_child = new_node;
        }
        
        return node;
        
        
    }
    void insert(int value) {
        int tmp = (int) (log(value) / log(2)) + 1;
        
        if(tmp > max_bits) {
            cout << "Trie is full!" << endl;
            return;
        }
        root = insert_node(root, value);
    }
};

int main() {
    
    PatriciaTrie *trie = new PatriciaTrie();
    trie->insert(3);
    trie->insert(5);
    trie->insert(10);
    trie->insert(15);
    
    cout << trie-> search(6) << endl;
    
    
    
    return 0;
}