source: tags/arb_5.1/NALIGNER/ali_postree.hxx

Last change on this file was 4912, checked in by westram, 17 years ago
  • untabified + indented
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 5.1 KB
Line 
1
2
3#ifndef _ALI_POSTREE_INC_
4#define _ALI_POSTREE_INC_
5
6#include <string.h>
7// #include <malloc.h>
8
9#include "ali_misc.hxx"
10#include "ali_tlist.hxx"
11#include "ali_tstack.hxx"
12
13/*****************************************************************************
14 *
15 * STRUCT: ALI_POSTREE_NODE
16 *
17 *****************************************************************************/
18
19enum ALI_POSTREE_NODE_TYPE {Node, Leaf};
20
21struct ALI_POSTREE_NODE {
22    ALI_POSTREE_NODE_TYPE typ;
23    union {
24        struct ALI_POSTREE_LEAF_PART {                          /* leaf part */
25            unsigned long position;
26            struct ALI_POSTREE_NODE *next;
27        } leaf;
28        struct ALI_POSTREE_NODE_PART {                          /* node part */
29            unsigned long number_of_children;
30            struct ALI_POSTREE_NODE *(*children)[];
31        } node;
32    };
33
34    ALI_POSTREE_NODE(ALI_POSTREE_NODE_TYPE t,
35                     unsigned long nochild_position = 0);
36    ~ALI_POSTREE_NODE(void);
37
38    int is_leaf(void) {
39        return (typ == Leaf);
40    }
41    int is_node(void) {
42        return (typ == Node);
43    }
44
45    ALI_POSTREE_NODE *leftmost_leaf(void);
46    ALI_POSTREE_NODE *rightmost_leaf(void);
47    ALI_POSTREE_NODE *link_leafs(ALI_POSTREE_NODE *last);
48    void print(unsigned long depth);
49};
50
51
52
53/*****************************************************************************
54 *
55 * CLASS: ALI_POSTREE
56 *
57 *****************************************************************************/
58
59struct ali_postree_sol {
60    char *path;
61    ALI_TLIST<unsigned long> *position_list;
62
63    ali_postree_sol(char *p, ALI_TLIST<unsigned long> *pos) {
64        path = p;
65        position_list = pos;
66    }
67    ali_postree_sol(ALI_TSTACK<char> *stack, ALI_TLIST<unsigned long> *pos,
68                    char *prefix = "", char *postfix = "") {
69        unsigned long i, akt;
70        position_list = pos;
71
72        path = (char *) calloc(strlen(prefix) + (unsigned int)stack->akt_size() +
73                               strlen(postfix) + 1, sizeof(char));
74        if (path == 0)
75            ali_fatal_error("Out of memory");
76
77        for (akt = 0; akt < strlen(prefix); akt++)
78            path[akt] = prefix[akt];
79        for (i = 0; i < stack->akt_size(); i++, akt++)
80            path[akt] = stack->get(i);
81        for (i = 0; i < strlen(postfix); i++, akt++)
82            path[akt] = postfix[i];
83
84        path[akt] = '\0';
85    }
86    ~ali_postree_sol(void) {
87        if (path)
88            free((char *) path);
89        if (position_list)
90            delete position_list;
91    }
92};
93
94
95
96#define ALI_POSTREE_STACK_INS 'I'
97#define ALI_POSTREE_STACK_DEL 'D'
98#define ALI_POSTREE_STACK_SUB 'S'
99
100
101
102class ALI_POSTREE {
103    unsigned long length_of_sequence;
104    unsigned long number_of_branches;
105    ALI_POSTREE_NODE *root;
106
107    unsigned char *make_postree_sequence(
108                                         unsigned char *seq, unsigned long seq_len,
109                                         unsigned char terminal);
110    void insert(unsigned char *seq, unsigned char terminal);
111    void link_leafs(void);
112    ali_postree_sol *make_postree_solution(
113                                           ALI_POSTREE_NODE *first, ALI_POSTREE_NODE *last,
114                                           unsigned long min_pos, unsigned long max_pos,
115                                           unsigned long seq_len, unsigned long errors,
116                                           ALI_TSTACK<char> *stack);
117    unsigned long maximal_position(ALI_POSTREE_NODE *first,
118                                   ALI_POSTREE_NODE *last);
119    void handle_remaining_sequence(
120                                   unsigned char *seq, unsigned long seq_len,
121                                   unsigned long seq_pos, unsigned long im_seq_len,
122                                   unsigned long min_pos, unsigned long max_pos,
123                                   unsigned long ref_pos, unsigned long errors,
124                                   ALI_TSTACK<char> *stack,
125                                   ALI_TLIST<ali_postree_sol *> *sol_list);
126    void finder(ALI_POSTREE_NODE *n,
127                unsigned char *seq, unsigned long seq_len,
128                unsigned long seq_pos, unsigned long im_seq_len,
129                unsigned long min_pos, unsigned long max_pos,
130                unsigned long errors,
131                ALI_TSTACK<char> *stack,
132                ALI_TLIST<ali_postree_sol *> *sol_list);
133
134public:
135    ALI_POSTREE(unsigned long branches,
136                unsigned char *seq, unsigned long seq_len,
137                unsigned char terminal = 4);
138    ~ALI_POSTREE(void) {
139        delete root;
140    }
141    ALI_TLIST<ali_postree_sol *> *find(
142                                       unsigned char *seq, unsigned long seq_len,
143                                       unsigned long min_pos, unsigned long max_pos,
144                                       unsigned long errors = 0);
145    ALI_TLIST<ali_postree_sol *> *find_complement(
146                                                  unsigned char *seq, unsigned long seq_len,
147                                                  unsigned long min_pos, unsigned long max_pos,
148                                                  float costs = 0.0);
149    void print(void);
150};
151
152
153#endif
Note: See TracBrowser for help on using the repository browser.