Back to index

python-biopython  1.60
Typedefs | Functions
trie.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs

typedef struct Trie

Functions

TrieTrie_new (void)
void Trie_del (Trie *trie)
int Trie_set (Trie *trie, const char *key, const void *value)
void * Trie_get (const Trie *trie, const char *key)
void Trie_get_approximate (const Trie *trie, const char *key, const int k, void(*callback)(const char *key, const void *value, const int mismatches, void *data), void *data)
int Trie_len (const Trie *trie)
int Trie_has_key (const Trie *trie, const char *key)
int Trie_has_prefix (const Trie *trie, const char *prefix)
void Trie_with_prefix (const Trie *trie, const char *prefix, void(*callback)(const char *key, const void *value, void *data), void *data)
void Trie_iterate (const Trie *trie, void(*callback)(const char *key, const void *value, void *data), void *data)
int Trie_serialize (const Trie *trie, int(*write)(const void *towrite, const int length, void *data), int(*write_value)(const void *value, void *data), void *data)
TrieTrie_deserialize (int(*read)(void *wasread, const int length, void *data), void *(*read_value)(void *data), void *data)

Typedef Documentation

typedef struct Trie

Definition at line 1 of file trie.h.


Function Documentation

void Trie_del ( Trie trie)

Definition at line 192 of file trie.c.

                          {
    int i;
    if(!trie)
       return;
    for(i=0; i<trie->num_transitions; i++) {
       Transition* transition = &trie->transitions[i];
       if(transition->suffix)
           free(transition->suffix);
       Trie_del(transition->next);
    }
    free(trie);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Trie* Trie_deserialize ( int(*)(void *wasread, const int length, void *data)  read,
void *(*)(void *data)  read_value,
void *  data 
)

Definition at line 736 of file trie.c.

{
    Trie* trie = Trie_new();
    if(!_deserialize_trie(trie, read, read_value, data)) {
       Trie_del(trie);
       return NULL;
    }
    return trie;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* Trie_get ( const Trie trie,
const char *  key 
)

Definition at line 205 of file trie.c.

                                                  {
    int first, last, mid;

    if(!key[0]) {
       return trie->value;
    }

    /* The transitions are stored in alphabetical order.  Do a binary
     * search to find the proper one.
     */
    first = 0;
    last = trie->num_transitions-1;
    while(first <= last) {
       Transition* transition;
       char *suffix;
       int c;
       mid = (first+last)/2;
       transition = &trie->transitions[mid];
       suffix = transition->suffix;
       /* If suffix is a substring of key, then get the value from
          the next trie.
       */
       c = strncmp(key, suffix, strlen(suffix));
       if(c < 0)
           last = mid-1;
       else if(c > 0)
           first = mid+1;
       else
           return Trie_get(transition->next, key+strlen(suffix));
    }
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void Trie_get_approximate ( const Trie trie,
const char *  key,
const int  k,
void(*)(const char *key, const void *value, const int mismatches, void *data)  callback,
void *  data 
)

Definition at line 385 of file trie.c.

{
    KEY[0] = 0;
    _get_approximate_trie(trie, key, k, callback, data, 0, KEY,MAX_KEY_LENGTH);
}

Here is the call graph for this function:

Here is the caller graph for this function:

int Trie_has_key ( const Trie trie,
const char *  key 
)

Definition at line 412 of file trie.c.

{
    return Trie_get(trie, key) != NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int Trie_has_prefix ( const Trie trie,
const char *  prefix 
)

Definition at line 417 of file trie.c.

{
    int first, last, mid;

    if(!prefix[0]) {
       return 1;
    }

    /* The transitions are stored in alphabetical order.  Do a binary
     * search to find the proper one.
     */
    first = 0;
    last = trie->num_transitions-1;
    while(first <= last) {
       Transition* transition;
       char *suffix;
       int suffixlen, prefixlen, minlen;
       int c;
       mid = (first+last)/2;
       transition = &trie->transitions[mid];
       suffix = transition->suffix;
       suffixlen = strlen(suffix);
       prefixlen = strlen(prefix);
       minlen = (suffixlen < prefixlen) ? suffixlen : prefixlen;
       c = strncmp(prefix, suffix, minlen);
       if(c < 0)
           last = mid-1;
       else if(c > 0)
           first = mid+1;
       else
           return Trie_has_prefix(transition->next, prefix+minlen);
    }
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void Trie_iterate ( const Trie trie,
void(*)(const char *key, const void *value, void *data)  callback,
void *  data 
)

Definition at line 481 of file trie.c.

{
    KEY[0] = 0;
    _iterate_helper(trie, callback, data, KEY, MAX_KEY_LENGTH);
}

Here is the call graph for this function:

Here is the caller graph for this function:

int Trie_len ( const Trie trie)

Definition at line 397 of file trie.c.

{
    int i;
    int length = 0;
    
    if(!trie)
       return 0;
    if(trie->value)
       length += 1;
    for(i=0; i<trie->num_transitions; i++) {
       length += Trie_len(trie->transitions[i].next);
    }
    return length;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Trie* Trie_new ( void  )

Definition at line 45 of file trie.c.

                     {
    Trie* trie;

    if(!(trie = malloc(sizeof(struct Trie))))
       return NULL;
    trie->transitions = NULL;
    trie->num_transitions = 0;
    trie->value = NULL;
    return trie;
}

Here is the caller graph for this function:

int Trie_serialize ( const Trie trie,
int(*)(const void *towrite, const int length, void *data)  write,
int(*)(const void *value, void *data)  write_value,
void *  data 
)

Definition at line 637 of file trie.c.

{
    int success = _serialize_trie(trie, write, write_value, data);
    (*write)(NULL, 0, data);
    return success;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int Trie_set ( Trie trie,
const char *  key,
const void *  value 
)

Definition at line 56 of file trie.c.

                                                             {
    int i;
    Transition* transition=NULL;
    const char *suffix=NULL;
    int retval = 0;
    int first, last, mid;

    if(!key[0]) {
       trie->value = (void *)value;
       return 0;
    }

    /* Insert the key in alphabetical order.  Do a binary search to
       find the proper place. */
    first = 0;
    last = trie->num_transitions-1;
    i = -1;
    while(first <= last) {
       mid = (first+last)/2;
       transition = &trie->transitions[mid];
       suffix = transition->suffix;
       if(key[0] < suffix[0])
           last = mid-1;
       else if(key[0] > suffix[0])
           first = mid+1;
       else {
           i = mid;
           break;
       }
    }

    /* If no place was found for it, then the indexes will be in the
       order last,first.  Place it at index first. */
    if(i == -1)
       i = first;

    /* If nothing matches, then insert a new trie here. */
    if((i >= trie->num_transitions) || (key[0] != suffix[0])) {
       char *new_suffix=NULL;
       Trie* newtrie=NULL;
       Transition* new_transitions=NULL;

       /* Create some variables for the new transition.  I'm going to
          allocate these first so that if I can detect memory errors
          before I mess up the data structure of the transitions.
       */
       if(!(new_suffix = duplicate(key)))
           goto insert_memerror;
       if(!(newtrie = Trie_new()))
           goto insert_memerror;

       /* Create some space for the next transition.  Allocate some
          memory and shift the old transitions over to make room for
          this one.
       */
       if(!(new_transitions = malloc(sizeof(Transition) *
                                  (trie->num_transitions+1))))
           goto insert_memerror;
       memcpy(new_transitions, trie->transitions,
              sizeof(Transition)*i);
       memcpy(&new_transitions[i+1], &trie->transitions[i],
              sizeof(Transition)*(trie->num_transitions-i));
       free(trie->transitions);
       trie->transitions = new_transitions;
       new_transitions = NULL;
       trie->num_transitions += 1;

       /* Initialize the new transition. */
       transition = &trie->transitions[i];
       transition->suffix = new_suffix;
       transition->next = newtrie;
       transition->next->value = (void *)value;

       if(0) {
       insert_memerror:
           if(new_transitions) free(new_transitions);
           if(newtrie) free(newtrie);
           if(new_suffix) free(new_suffix);
           return 1;
       }
    } 
    /* There are three cases where the key and suffix share some
       letters. 
       1.  suffix is proper substring of key.
       2.  key is proper substring of suffix.
       3.  neither is proper substring of other.

       For cases 2 and 3, I need to first split up the transition
       based on the number of characters shared.  Then, I can insert
       the rest of the key into the next trie.
    */
    else {
       /* Count the number of characters shared between key
          and suffix. */
       int chars_shared = 0;
       while(key[chars_shared] && key[chars_shared] == suffix[chars_shared])
           chars_shared++;

       /* Case 2 or 3, split this sucker! */
       if(chars_shared < strlen(suffix)) {
           Trie* newtrie=NULL;
           char *new_suffix1=NULL, *new_suffix2=NULL;

           if(!(new_suffix1 = malloc(chars_shared+1)))
              goto split_memerror;
           strncpy(new_suffix1, key, chars_shared);
           new_suffix1[chars_shared] = 0;
           if(!(new_suffix2 = duplicate(suffix+chars_shared)))
              goto split_memerror;
           if(!(newtrie = Trie_new()))
              goto split_memerror;
           if(!(newtrie->transitions = malloc(sizeof(Transition))))
              goto split_memerror;
           newtrie->num_transitions = 1;
           newtrie->transitions[0].next = transition->next;
           newtrie->transitions[0].suffix = new_suffix2;

           free(transition->suffix);
           transition->suffix = new_suffix1;
           transition->next = newtrie;

           if(0) {
           split_memerror:
              if(newtrie && newtrie->transitions) free(newtrie->transitions);
              if(newtrie) free(newtrie);
              if(new_suffix2) free(new_suffix2);
              if(new_suffix1) free(new_suffix1);
              return 1;
           }
       }
       retval = Trie_set(transition->next, key+chars_shared, value);
    }

    return retval;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void Trie_with_prefix ( const Trie trie,
const char *  prefix,
void(*)(const char *key, const void *value, void *data)  callback,
void *  data 
)

Definition at line 544 of file trie.c.

{
    KEY[0] = 0;
    _with_prefix_helper(trie, prefix, callback, data, KEY, MAX_KEY_LENGTH);
}

Here is the call graph for this function:

Here is the caller graph for this function: