Fix core WST file
[jabaws.git] / binaries / src / disembl / biopython-1.50 / Bio / trie.c
1 #include <stdio.h>    /* printf */
2 #include <stdlib.h>   /* malloc */
3 #include <string.h>   /* strcmp, strlen */
4
5 #include "trie.h"
6
7 /* The following is necessary to make sure that trie.pyd won't link
8  * to msvcrt.dll in addition to msvcr71.dll on Windows.
9  * See Bug #1767 on Bugzilla.
10  */
11 #ifdef __MINGW32__
12 #  define strdup _strdup
13 #endif
14
15 struct _Transition;   /* Forward declaration, needed in _Trie. */
16
17
18 /* _Trie is a recursive data structure.  A _Trie contains zero or more
19  * _Transitions that lead to more _Tries.  The transitions are stored
20  * in alphabetical order of the suffix member of the data structure.
21  * _Trie also contains a pointer called value where the user can store
22  * arbitrary data.  If value is NULL, then no data is stored here.
23  */
24 struct _Trie {
25     struct _Transition *transitions;
26     unsigned char num_transitions;
27     void *value;   /* specified by user, never freed or allocated by me! */
28 };
29
30 /* _Transition holds information about the transitions leading from
31  * one _Trie to another.  The trie structure here is different from
32  * typical ones, because the transitions between nodes can contain
33  * strings of arbitrary length, not just single characters.  Suffix is
34  * the string that is matched from one node to the next.
35  */
36 typedef struct _Transition {
37     unsigned char *suffix;
38     Trie next;
39 } *Transition;
40
41
42 #define MAX_KEY_LENGTH 1000
43 static unsigned char KEY[MAX_KEY_LENGTH];
44
45
46 Trie Trie_new(void) {
47     Trie trie;
48
49     if(!(trie = (Trie)malloc(sizeof(struct _Trie))))
50         return NULL;
51     trie->transitions = NULL;
52     trie->num_transitions = 0;
53     trie->value = NULL;
54     return trie;
55 }
56
57 int Trie_set(Trie trie, const unsigned char *key, const void *value) {
58     int i;
59     Transition transition=NULL;
60     unsigned char *suffix=NULL;
61     int retval = 0;
62     int first, last, mid;
63
64     if(!key[0]) {
65         trie->value = (void *)value;
66         return 0;
67     }
68
69     /* Insert the key in alphabetical order.  Do a binary search to
70        find the proper place. */
71     first = 0;
72     last = trie->num_transitions-1;
73     i = -1;
74     while(first <= last) {
75         mid = (first+last)/2;
76         transition = &trie->transitions[mid];
77         suffix = transition->suffix;
78         if(key[0] < suffix[0])
79             last = mid-1;
80         else if(key[0] > suffix[0])
81             first = mid+1;
82         else {
83             i = mid;
84             break;
85         }
86     }
87
88     /* If no place was found for it, then the indexes will be in the
89        order last,first.  Place it at index first. */
90     if(i == -1)
91         i = first;
92
93     /* If nothing matches, then insert a new trie here. */
94     if((i >= trie->num_transitions) || (key[0] != suffix[0])) {
95         unsigned char *new_suffix=NULL;
96         Trie newtrie=NULL;
97         Transition new_transitions=NULL;
98
99         /* Create some variables for the new transition.  I'm going to
100            allocate these first so that if I can detect memory errors
101            before I mess up the data structure of the transitions.
102         */
103         if(!(new_suffix = (unsigned char *)strdup(key)))
104             goto insert_memerror;
105         if(!(newtrie = Trie_new()))
106             goto insert_memerror;
107
108         /* Create some space for the next transition.  Allocate some
109            memory and shift the old transitions over to make room for
110            this one.
111         */
112         if(!(new_transitions = malloc(sizeof(struct _Transition) *
113                                       (trie->num_transitions+1))))
114             goto insert_memerror;
115         memcpy(new_transitions, trie->transitions,
116                sizeof(struct _Transition)*i);
117         memcpy(&new_transitions[i+1], &trie->transitions[i],
118                sizeof(struct _Transition)*(trie->num_transitions-i));
119         free(trie->transitions);
120         trie->transitions = new_transitions;
121         new_transitions = NULL;
122         trie->num_transitions += 1;
123
124         /* Initialize the new transition. */
125         transition = &trie->transitions[i];
126         transition->suffix = new_suffix;
127         transition->next = newtrie;
128         transition->next->value = (void *)value;
129
130         if(0) {
131         insert_memerror:
132             if(new_transitions) free(new_transitions);
133             if(newtrie) free(newtrie);
134             if(new_suffix) free(new_suffix);
135             return 1;
136         }
137     } 
138     /* There are three cases where the key and suffix share some
139        letters. 
140        1.  suffix is proper substring of key.
141        2.  key is proper substring of suffix.
142        3.  neither is proper substring of other.
143
144        For cases 2 and 3, I need to first split up the transition
145        based on the number of characters shared.  Then, I can insert
146        the rest of the key into the next trie.
147     */
148     else {
149         /* Count the number of characters shared between key
150            and suffix. */
151         int chars_shared = 0;
152         while(key[chars_shared] && key[chars_shared] == suffix[chars_shared])
153             chars_shared++;
154
155         /* Case 2 or 3, split this sucker! */
156         if(chars_shared < strlen(suffix)) {
157             Trie newtrie=NULL;
158             unsigned char *new_suffix1=NULL, *new_suffix2=NULL;
159
160             if(!(new_suffix1 = (unsigned char *)malloc(chars_shared+1)))
161                 goto split_memerror;
162             strncpy(new_suffix1, key, chars_shared);
163             new_suffix1[chars_shared] = 0;
164             if(!(new_suffix2 = (unsigned char *)strdup(suffix+chars_shared)))
165                 goto split_memerror;
166             if(!(newtrie = Trie_new()))
167                 goto split_memerror;
168             if(!(newtrie->transitions = 
169                  (Transition)malloc(sizeof(struct _Transition))))
170                 goto split_memerror;
171             newtrie->num_transitions = 1;
172             newtrie->transitions[0].next = transition->next;
173             newtrie->transitions[0].suffix = new_suffix2;
174
175             free(transition->suffix);
176             transition->suffix = new_suffix1;
177             transition->next = newtrie;
178
179             if(0) {
180             split_memerror:
181                 if(newtrie && newtrie->transitions) free(newtrie->transitions);
182                 if(newtrie) free(newtrie);
183                 if(new_suffix2) free(new_suffix2);
184                 if(new_suffix1) free(new_suffix1);
185                 return 1;
186             }
187         }
188         retval = Trie_set(transition->next, key+chars_shared, value);
189     }
190
191     return retval;
192 }
193
194 void Trie_del(Trie trie) {
195     int i;
196     if(!trie)
197         return;
198     for(i=0; i<trie->num_transitions; i++) {
199         Transition transition = &trie->transitions[i];
200         if(transition->suffix)
201             free(transition->suffix);
202         Trie_del(transition->next);
203     }
204     free(trie);
205 }
206
207 void *Trie_get(const Trie trie, const unsigned char *key) {
208     int first, last, mid;
209
210     if(!key[0]) {
211         return trie->value;
212     }
213
214     /* The transitions are stored in alphabetical order.  Do a binary
215      * search to find the proper one.
216      */
217     first = 0;
218     last = trie->num_transitions-1;
219     while(first <= last) {
220         Transition transition;
221         unsigned char *suffix;
222         int c;
223         mid = (first+last)/2;
224         transition = &trie->transitions[mid];
225         suffix = transition->suffix;
226         /* If suffix is a substring of key, then get the value from
227            the next trie.
228         */
229         c = strncmp(key, suffix, strlen(suffix));
230         if(c < 0)
231             last = mid-1;
232         else if(c > 0)
233             first = mid+1;
234         else
235             return Trie_get(transition->next, key+strlen(suffix));
236     }
237     return NULL;
238 }
239
240
241 /* Mutually recursive, so need to make a forward declaration. */
242 void
243 _get_approximate_trie(const Trie trie, const unsigned char *key, const int k,
244                       void (*callback)(const unsigned char *key, 
245                                        const void *value,
246                                        const int mismatches,
247                                        void *data),
248                       void *data, 
249                       const int mismatches,
250                       unsigned char *current_key, const int max_key
251                       );
252
253 void 
254 _get_approximate_transition(const unsigned char *key, 
255                             const int k,
256                             const Transition transition, 
257                             const unsigned char *suffix,
258                             void (*callback)(const unsigned char *key, 
259                                              const void *value,
260                                              const int mismatches,
261                                              void *data),
262                             void *data, 
263                             const int mismatches,
264                             unsigned char *current_key, const int max_key
265                             )
266 {
267     int i;
268     int prev_keylen = strlen(current_key);
269
270     /* Short circuit optimization.  If there's too many characters to
271        possibly be a match, then don't even try to match things. */
272     if((int)(strlen(suffix) - strlen(key)) > k)
273         return;
274
275     /* Match as many characters as possible. */
276     i = 0;
277     while(suffix[i] && (key[i] == suffix[i])) {
278         i++;
279     }
280     /* Check to make sure the key is not too long.  BUG: If it is,
281        fails silently. */
282     if((prev_keylen+i) >= max_key)
283         return;
284     strncat(current_key, suffix, i);
285
286     /* If all the letters in the suffix matched, then move to the
287        next trie. */
288     if(!suffix[i]) {
289         _get_approximate_trie(transition->next, &key[i], k, callback, data,
290                               mismatches, current_key, max_key);
291     }
292     /* Otherwise, try out different kinds of mismatches. */
293     else if(k) {
294         int new_keylen = prev_keylen+i;
295
296         /* Letter replacement, skip the next letter in both the key and
297            suffix. */
298         if((new_keylen+1 < max_key) && key[i] && suffix[i]) {
299             current_key[new_keylen] = suffix[i];
300             current_key[new_keylen+1] = 0;
301             _get_approximate_transition(&key[i+1], k-1,
302                                         transition, &suffix[i+1],
303                                         callback, data,
304                                         mismatches+1, current_key, max_key);
305             current_key[new_keylen] = 0;
306         }
307
308         /* Insertion in key, skip the next letter in the key. */
309         if(key[i]) {
310             _get_approximate_transition(&key[i+1], k-1, 
311                                         transition, &suffix[i],
312                                         callback, data,
313                                         mismatches+1, current_key, max_key);
314         }
315
316         /* Deletion from key, skip the next letter in the suffix. */
317         if((new_keylen+1 < max_key) && suffix[i]) {
318             current_key[new_keylen] = suffix[i];
319             current_key[new_keylen+1] = 0;
320             _get_approximate_transition(&key[i], k-1,
321                                         transition, &suffix[i+1],
322                                         callback, data,
323                                         mismatches+1, current_key, max_key);
324             current_key[new_keylen] = 0;
325         }
326     }
327     current_key[prev_keylen] = 0;
328 }
329
330 void
331 _get_approximate_trie(const Trie trie, const unsigned char *key, const int k,
332                       void (*callback)(const unsigned char *key, 
333                                        const void *value,
334                                        const int mismatches,
335                                        void *data),
336                       void *data, 
337                       const int mismatches,
338                       unsigned char *current_key, const int max_key
339                       )
340 {
341     int i;
342
343     /* If there's no more key to match, then I'm done. */
344     if(!key[0]) {
345         if(trie->value)
346             (*callback)(current_key, trie->value, mismatches, data);
347     }
348     /* If there are no more mismatches allowed, then fall back to the
349        faster Trie_get. */
350     else if(!k) {
351         void *value = Trie_get(trie, key);
352         if(value) {
353             int l = strlen(current_key);
354             /* Make sure I have enough space for the full key. */
355             if(l + strlen(key) < max_key) {
356                 strcat(current_key, key);
357                 (*callback)(current_key, value, mismatches, data);
358                 current_key[l] = 0;
359             }
360             /* BUG: Ran out of space for the key.  This fails
361                silently, but should signal an error. */
362         }
363     }
364     /* If there are no more transitions, then all the characters left
365        in the key are mismatches. */
366     else if(!trie->num_transitions) {
367         if(trie->value && (strlen(key) <= k)) {
368             (*callback)(current_key, trie->value, 
369                         mismatches+strlen(key), data);
370         }
371     }
372     /* Otherwise, try to match each of the transitions. */
373     else {
374         for(i=0; i<trie->num_transitions; i++) {
375             Transition transition = &trie->transitions[i];
376             unsigned char *suffix = transition->suffix;
377             _get_approximate_transition(key, k, transition, suffix,
378                                         callback, data, 
379                                         mismatches, current_key, max_key);
380         }
381     }
382
383 }
384
385
386 void 
387 Trie_get_approximate(const Trie trie, const unsigned char *key, const int k,
388                      void (*callback)(const unsigned char *key, 
389                                       const void *value,
390                                       const int mismatches,
391                                       void *data),
392                      void *data
393                      )
394 {
395     KEY[0] = 0;
396     _get_approximate_trie(trie, key, k, callback, data, 0, KEY,MAX_KEY_LENGTH);
397 }
398
399 int Trie_len(const Trie trie) 
400 {
401     int i;
402     int length = 0;
403     
404     if(!trie)
405         return 0;
406     if(trie->value)
407         length += 1;
408     for(i=0; i<trie->num_transitions; i++) {
409         length += Trie_len(trie->transitions[i].next);
410     }
411     return length;
412 }
413
414 int Trie_has_key(const Trie trie, const unsigned char *key) 
415 {
416     return Trie_get(trie, key) != NULL;
417 }
418
419 int Trie_has_prefix(const Trie trie, const unsigned char *prefix) 
420 {
421     int first, last, mid;
422
423     if(!prefix[0]) {
424         return 1;
425     }
426
427     /* The transitions are stored in alphabetical order.  Do a binary
428      * search to find the proper one.
429      */
430     first = 0;
431     last = trie->num_transitions-1;
432     while(first <= last) {
433         Transition transition;
434         unsigned char *suffix;
435         int suffixlen, prefixlen, minlen;
436         int c;
437         mid = (first+last)/2;
438         transition = &trie->transitions[mid];
439         suffix = transition->suffix;
440         suffixlen = strlen(suffix);
441         prefixlen = strlen(prefix);
442         minlen = (suffixlen < prefixlen) ? suffixlen : prefixlen;
443         c = strncmp(prefix, suffix, minlen);
444         if(c < 0)
445             last = mid-1;
446         else if(c > 0)
447             first = mid+1;
448         else
449             return Trie_has_prefix(transition->next, prefix+minlen);
450     }
451     return 0;
452 }
453
454 static void 
455 _iterate_helper(const Trie trie, 
456                 void (*callback)(const unsigned char *key, 
457                                  const void *value,
458                                  void *data),
459                 void *data,
460                 unsigned char *current_key, const int max_key)
461 {
462     int i;
463     if(trie->value)
464         (*callback)(current_key, trie->value, data);
465     for(i=0; i<trie->num_transitions; i++) {
466         Transition transition = &trie->transitions[i];
467         unsigned char *suffix = transition->suffix;
468         int keylen = strlen(current_key);
469
470         if(keylen + strlen(suffix) >= max_key) {
471             /* BUG: This will fail silently.  It should raise some
472                sort of error. */
473             continue;
474         }
475         strcat(current_key, suffix);
476         _iterate_helper(transition->next, callback, data, 
477                         current_key, max_key);
478         current_key[keylen] = 0;
479     }
480 }
481
482 void 
483 Trie_iterate(const Trie trie, 
484              void (*callback)(const unsigned char *key, 
485                               const void *value,
486                               void *data),
487              void *data)
488 {
489     KEY[0] = 0;
490     _iterate_helper(trie, callback, data, KEY, MAX_KEY_LENGTH);
491 }
492
493 static void
494 _with_prefix_helper(const Trie trie, const unsigned char *prefix,
495                     void (*callback)(const unsigned char *key, 
496                                      const void *value,
497                                      void *data),
498                     void *data,
499                     unsigned char *current_key, const int max_key)
500 {
501     int first, last, mid;
502
503     if(!prefix[0]) {
504         _iterate_helper(trie, callback, data, current_key, max_key);
505         return;
506     }
507
508     /* The transitions are stored in alphabetical order.  Do a binary
509      * search to find the proper one.
510      */
511     first = 0;
512     last = trie->num_transitions-1;
513     while(first <= last) {
514         Transition transition;
515         unsigned char *suffix;
516         int suffixlen, prefixlen, minlen;
517         int c;
518         mid = (first+last)/2;
519         transition = &trie->transitions[mid];
520         suffix = transition->suffix;
521         suffixlen = strlen(suffix);
522         prefixlen = strlen(prefix);
523         minlen = (suffixlen < prefixlen) ? suffixlen : prefixlen;
524         c = strncmp(prefix, suffix, minlen);
525         if(c < 0)
526             last = mid-1;
527         else if(c > 0)
528             first = mid+1;
529         else {
530             int keylen = strlen(current_key);
531             if(keylen + minlen >= max_key) {
532                 /* BUG: This will fail silently.  It should raise some
533                    sort of error. */
534                 break;
535             }
536             strncat(current_key, suffix, minlen);
537             _with_prefix_helper(transition->next, prefix+minlen,
538                                 callback, data, current_key, max_key);
539             current_key[keylen] = 0;
540             break;
541         }
542     }
543 }
544
545 void 
546 Trie_with_prefix(const Trie trie, const unsigned char *prefix,
547                  void (*callback)(const unsigned char *key, 
548                                   const void *value,
549                                   void *data),
550                  void *data
551                  )
552 {
553     KEY[0] = 0;
554     _with_prefix_helper(trie, prefix, callback, data, KEY, MAX_KEY_LENGTH);
555 }
556
557
558
559 /* Need to declare _serialize_transition here so it can be called from
560    _serialize_trie. */
561 int _serialize_transition(const Transition transition, 
562                           int (*write)(const void *towrite, const int length,
563                                        void *data),
564                           int (*write_value)(const void *value, void *data),
565                           void *data);
566
567 /* This library also provides code for flattening tries so that they
568  * can be saved and read back in later.  The format of a serialized
569  * trie is:
570  * TYPE        NBYTES    DESCRIPTION
571  * byte        1         Whether or not there is a value
572  * variable    variable  If there is a value, let the client store it.
573  * byte        1         Number of transitions for this Trie.
574  * transition  variable
575  *   int       4         Number of characters in the suffix.
576  *   suffix    variable  the suffix for this transition
577  *   byte      1         Whether or not there is a trie
578  *   trie      variable  Recursively points to another trie.
579  * 
580  * The number of bytes and the endian may vary from platform to
581  * platform.
582  */
583
584 int _serialize_trie(const Trie trie, 
585                     int (*write)(const void *towrite, const int length,
586                                  void *data),
587                     int (*write_value)(const void *value, void *data),
588                     void *data)
589 {
590     int i;
591     unsigned char has_value;
592
593     has_value = (trie->value != NULL);
594     if(!(*write)(&has_value, sizeof(has_value), data))
595         return 0;
596     if(has_value) {
597         if(!(*write_value)(trie->value, data))
598             return 0;
599     }
600
601     if(!(*write)(&trie->num_transitions, sizeof(trie->num_transitions), data))
602         return 0;
603     for(i=0; i<trie->num_transitions; i++) {
604         if(!_serialize_transition(&trie->transitions[i], 
605                                   write, write_value, data))
606             return 0;
607     }
608
609     return 1;
610 }
611
612 int _serialize_transition(const Transition transition, 
613                           int (*write)(const void *towrite, const int length,
614                                        void *data),
615                           int (*write_value)(const void *value, void *data),
616                           void *data)
617 {
618     int suffixlen;
619     unsigned char has_trie;
620
621     suffixlen = strlen(transition->suffix);
622     if(!(*write)(&suffixlen, sizeof(suffixlen), data))
623         return 0;
624     if(!(*write)(transition->suffix, suffixlen, data))
625         return 0;
626
627     has_trie = (transition->next != NULL);
628     if(!(*write)(&has_trie, sizeof(has_trie), data))
629         return 0;
630     if(has_trie) {
631         if(!_serialize_trie(transition->next, write, write_value, data))
632             return 0;
633     }
634     return 1;
635 }
636
637 int Trie_serialize(const Trie trie, 
638                    int (*write)(const void *towrite, const int length, 
639                                 void *data),
640                    int (*write_value)(const void *value, void *data),
641                    void *data)
642 {
643     int success = _serialize_trie(trie, write, write_value, data);
644     (*write)(NULL, 0, data);
645     return success;
646 }
647
648 int _deserialize_transition(Transition transition,
649                             int (*read)(void *wasread, const int length, 
650                                         void *data),
651                             void *(*read_value)(void *data),
652                             void *data);
653
654 int _deserialize_trie(Trie trie, 
655                       int (*read)(void *wasread, const int length, void *data),
656                       void *(*read_value)(void *data),
657                       void *data)
658 {
659     int i;
660     unsigned char has_value;
661
662     if(!(*read)(&has_value, sizeof(has_value), data))
663         goto _deserialize_trie_error;
664     if(has_value != 0 && has_value != 1)
665         goto _deserialize_trie_error;
666     if(has_value) {
667         if(!(trie->value = (*read_value)(data)))
668             goto _deserialize_trie_error;
669     }
670     if(!(*read)(&trie->num_transitions, sizeof(trie->num_transitions), data))
671         goto _deserialize_trie_error;
672     if(!(trie->transitions = 
673          malloc(trie->num_transitions*sizeof(struct _Transition))))
674         goto _deserialize_trie_error;
675     for(i=0; i<trie->num_transitions; i++) {
676         if(!_deserialize_transition(&trie->transitions[i], 
677                                     read, read_value, data))
678             goto _deserialize_trie_error;
679     }
680     return 1;
681    
682  _deserialize_trie_error:
683     trie->num_transitions = 0;
684     if(trie->transitions) {
685         free(trie->transitions);
686         trie->transitions = NULL;
687     }
688     trie->value = NULL;
689     return 0;
690 }
691
692 int _deserialize_transition(Transition transition,
693                             int (*read)(void *wasread, const int length, 
694                                         void *data),
695                             void *(*read_value)(void *data),
696                             void *data)
697 {
698     int suffixlen;
699     unsigned char has_trie;
700     
701     if(!(*read)(&suffixlen, sizeof(suffixlen), data))
702         goto _deserialize_transition_error;
703     if(suffixlen < 0 || suffixlen >= MAX_KEY_LENGTH)
704         goto _deserialize_transition_error;
705     if(!(*read)(KEY, suffixlen, data))
706         goto _deserialize_transition_error;
707     KEY[suffixlen] = 0;
708     if(!(transition->suffix = (unsigned char *)strdup(KEY)))
709         goto _deserialize_transition_error;
710     if(!(*read)(&has_trie, sizeof(has_trie), data))
711         goto _deserialize_transition_error;
712     if(has_trie != 0 && has_trie != 1)
713         goto _deserialize_transition_error;
714     if(has_trie) {
715         transition->next = Trie_new();
716         if(!_deserialize_trie(transition->next, read, read_value, data))
717             goto _deserialize_transition_error;
718     }
719     return 1;
720
721  _deserialize_transition_error:
722     if(transition->suffix) {
723         free(transition->suffix);
724         transition->suffix = NULL;
725     }
726     if(transition->next) {
727         Trie_del(transition->next);
728         transition->next = NULL;
729     }
730     return 0;
731 }
732
733 Trie Trie_deserialize(int (*read)(void *wasread, const int length, void *data),
734                       void *(*read_value)(void *data),
735                       void *data)
736 {
737     Trie trie = Trie_new();
738     if(!_deserialize_trie(trie, read, read_value, data)) {
739         Trie_del(trie);
740         return NULL;
741     }
742     return trie;
743 }
744
745 void test(void) {
746     Trie trie;
747
748     printf("Hello world!\n");
749
750     trie = Trie_new();
751     printf("New trie %p\n", trie);
752     Trie_set(trie, "hello world", "s1");
753     Trie_set(trie, "bye", "s2");
754     Trie_set(trie, "hell sucks", "s3");
755     Trie_set(trie, "hebee", "s4");
756
757     printf("%s\n", (char *)Trie_get(trie, "hello world"));
758     printf("%s\n", (char *)Trie_get(trie, "bye"));
759     printf("%s\n", (char *)Trie_get(trie, "hell sucks"));
760     printf("%s\n", (char *)Trie_get(trie, "hebee"));
761
762     Trie_set(trie, "blah", "s5");
763     printf("%s\n", (char *)Trie_get(trie, "blah"));
764
765     printf("%p\n", Trie_get(trie, "foobar"));
766     printf("%d\n", Trie_len(trie));
767
768     Trie_set(trie, "blah", "snew");
769     printf("%s\n", (char *)Trie_get(trie, "blah"));
770
771     Trie_del(trie);
772 }
773
774 #if 0
775 int main() {
776     test();
777 }
778 #endif