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 | |
---|
19 | enum ALI_POSTREE_NODE_TYPE {Node, Leaf}; |
---|
20 | |
---|
21 | struct 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 | |
---|
59 | struct 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 | |
---|
102 | class 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 | |
---|
134 | public: |
---|
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 |
---|