basic trie

tries.c

//
//  tries.c
//  chitchat
//
//  Created by Ben Oliver on 06/11/15.
//  Copyright © 2015 Ben Oliver. All rights reserved.
//

// assume that we allow 8 char sequences from an alphabet of 26 characters
// there are 26 ^ 8 possible sequences 208,827,064,576
// if a trie had 208,827,064,576 entries
// the worst case lookup would be (26 * 8) + 1 = 209
// average case (13 * 8) + 1 = 105
// best case 8 + 1 = 9





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

#include "tries.h"


typedef struct ascii_trie_s {
    char key;
    int val;
    unsigned short weight;
    struct ascii_trie_s* child;
    struct ascii_trie_s* next;
} ascii_trie ;



void free_ascii_trie(ascii_trie* node) {
    if (node != NULL) {
        free_ascii_trie(node->next);
        free_ascii_trie(node->child);
        free(node);
    }
}



void print_weights(ascii_trie* node) {
    if (node != NULL) {
        printf("node: %c weight: %d\n", node->key, node->weight);
        print_weights(node->next);
        print_weights(node->child);
    }
}



static ascii_trie* unsafe_trie_insert(char* key, int val, ascii_trie* node) {
    
    // element must not allready exist in trie
    
    while (1) {
        
        // move right untill we find a match OR reach the end of the row
        
        while ((*key != node->key) && (node->next != NULL)) {
            node = node->next;
        }
        
        if (*key == node->key) {
            
            node->weight += 1 ;
            node = node->child ;
            key  = key+1 ;
            
        } else {
            
            node->next   = malloc(sizeof(ascii_trie));
            node         = node->next;
            node->weight = 1;
            node->key    = *key;
            node->next   = NULL;
            node->child  = NULL;
            
            while (*key != '\0') {
                key          = key+1;
                node->child  = malloc(sizeof(ascii_trie));
                node         = node->child;
                node->weight = 1;
                node->key    = *key;
                node->next   = NULL;
                node->child  = NULL;
            }
         
            node->weight = 0;
            node->val = val;
            return node;
        }
    }
}



static void unsafe_trie_delete(char* key, ascii_trie* node, ascii_trie* parent) {
    
    ascii_trie* prev = NULL;
    
    while ((node->key != *key) && (node->next != NULL)) {
        prev = node;
        node = node->next;
    }
    
    // we have now found the node that we need to use
    
    if (node->weight < 2) {
        if (prev == NULL) {
            assert(parent != NULL);
            parent->child = node->next;
        } else {
            prev->next = node->next;
        }
        // only one string uses this node
        // thus only one string uses the children of the node
        // use < 2 as we might allready be at the terminal node
        // which has weight 0
        // remember that we might not be at the end of a row
        // so we use prev->next to join the previous node with node->next
        // which is either a node or NULL
        free_ascii_trie(node->child);
        free(node);
    } else {
        // node weight is > 1
        node->weight--;
        unsafe_trie_delete(key+1, node->child, node);
    }
    
    
}



ascii_trie* ascii_trie_lookup(char* key, int* valp, ascii_trie* node) {
    
    while (1) {
        
        while ((*key != node->key) && (node->next != NULL)) {
            node = node->next;
        }
        
        if (*key != node->key) {
            return NULL;
        }
        
        if (*key == 0x00) {
            *valp = node->val;
            return node;
        }
        
        key  = key+1;
        node = node->child;
        
    }
}





int main(int argc, char** argv) {
    
    printf("%lu\n", sizeof(ascii_trie));
    
    ascii_trie* root = malloc(sizeof(ascii_trie));
    root->weight     = 0;
    root->key        = 0x00;
    root->child      = NULL;
    root->next       = NULL;
    
    char* ben = "ben";
    char* benjamin = "benjamin";
    char* cat = "cat";
    char* dog = "dog";
    
    unsafe_trie_insert(ben, 10, root);
    unsafe_trie_insert(benjamin, 20, root);
    unsafe_trie_insert(cat, 30, root);
    unsafe_trie_insert(dog, 40, root);
    
    print_weights(root);
    
    int val;
    
    if (ascii_trie_lookup(ben, &val, root) != NULL) {
        printf("%s exists with key: %d\n", ben, val);
    } else {
        printf("%s does not exist\n", ben);
    }
    
    printf("deleting: %s\n", ben);
    unsafe_trie_delete(ben, root, NULL);
    
    if (ascii_trie_lookup(ben, &val, root) != NULL) {
        printf("%s exists with key: %d\n", ben, val);
    } else {
        printf("%s does not exist\n", ben);
    }
    


    
    
    print_weights(root);
    
    free_ascii_trie(root);
    
    
}