← Back to branch summary

~ubuntu-branches/debian/jessie/ugene/jessie

« back to all changes in this revision

Viewing changes to src/core/src/util_algorithm/DynTable.h

  • Committer: Package Import Robot
  • Author(s): Steffen Moeller
  • Date: 2011-11-02 13:29:07 UTC
  • mfrom: (1.2.1) (3.1.11 natty)
  • Revision ID: package-import@ubuntu.com-20111102132907-o34gwnt0uj5g6hen
Tags: 1.9.8+repack-1
* First release to Debian
  - added README.Debian
  - increased policy version to 3.9.2
  - added URLs for version control system
* Added debug package.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/src/util_algorithm/DynTable.h
1
 
/*****************************************************************
2
 
* Unipro UGENE - Integrated Bioinformatics Suite
3
 
* Copyright (C) 2008 Unipro, Russia (http://ugene.unipro.ru)
4
 
* All Rights Reserved
5
 
* 
6
 
*     This source code is distributed under the terms of the
7
 
*     GNU General Public License. See the files COPYING and LICENSE
8
 
*     for details.
9
 
*****************************************************************/
10
 
 
11
 
#ifndef _GB2_DYN_TABLE_H_
12
 
#define _GB2_DYN_TABLE_H_
13
 
 
14
 
#include "RollingMatrix.h"
15
 
 
16
 
namespace GB2 {
17
 
 
18
 
struct GB2_COREAPI_EXPORT MatchScores
19
 
{
20
 
    int match;
21
 
    int mismatch;
22
 
    int ins;
23
 
    int del;
24
 
};
25
 
 
26
 
class GB2_COREAPI_EXPORT DynTable : public RollingMatrix {
27
 
public:
28
 
    enum FillStrategy
29
 
    {
30
 
        Strategy_Max,
31
 
        Strategy_Min
32
 
    };
33
 
    DynTable(int n, int m, bool _allowInsDel) 
34
 
        : RollingMatrix(n, m), allowInsDel(_allowInsDel) 
35
 
    {
36
 
        init();
37
 
        scores.match = DEFAULT_SCORE_MATCH;
38
 
        scores.ins = DEFAULT_SCORE_INS;
39
 
        scores.del = DEFAULT_SCORE_DEL;
40
 
        scores.mismatch = DEFAULT_SCORE_MISMATCH;
41
 
        strategy = Strategy_Min;
42
 
    }
43
 
    DynTable(): RollingMatrix(0,0), allowInsDel(false)
44
 
    {
45
 
    }
46
 
    DynTable( int n, int m, bool _allowInsDel, MatchScores _scores, FillStrategy _strategy = Strategy_Min )
47
 
        : RollingMatrix(n, m), allowInsDel(_allowInsDel), scores(_scores), strategy(_strategy)
48
 
    {
49
 
        init();
50
 
    }
51
 
 
52
 
    int getLast() const {
53
 
        return get_value(n-1, m-1);
54
 
    }
55
 
    
56
 
    int getLastLen() const {
57
 
        return getLen(n-1, m-1);
58
 
    }
59
 
    
60
 
    void match(int y, bool ok) {
61
 
        match( n-1, y, ok );
62
 
    }
63
 
 
64
 
    virtual int get(int x, int y) const {
65
 
        if (y<0) {return 0;}
66
 
        if (x<0) {return y+1;}
67
 
        return RollingMatrix::get(x, y);
68
 
    }
69
 
protected:
70
 
    void match( int x, int y, bool ok )
71
 
    {
72
 
        int d = get_value( x-1, y-1 );
73
 
        int res = d + (ok ? scores.match : scores.mismatch);
74
 
        if( allowInsDel ) {
75
 
            int u = get_value(x, y-1);
76
 
            int l = get_value(x-1, y);
77
 
            int insdelRes = 0;
78
 
            switch( strategy )
79
 
            {
80
 
            case Strategy_Min:
81
 
                insdelRes = qMin( l+scores.ins, u+scores.del );
82
 
                res = qMin( insdelRes, res );
83
 
                break;
84
 
            default:
85
 
                assert( false );
86
 
            }
87
 
        }
88
 
        set_pair( x, y, res, ok );
89
 
    }
90
 
 
91
 
    int getLen(int x, int y) const { 
92
 
        if (y == -1) {
93
 
            return 0;
94
 
        }
95
 
        assert(x!=-1);
96
 
        
97
 
        if (!allowInsDel) {
98
 
            return 1 + getLen(x-1, y-1);
99
 
        }
100
 
        int v = get_value(x, y);
101
 
        bool match = get_flag( x, y );
102
 
        int d = get_value(x-1, y-1);
103
 
        int l = get_value(x-1, y);
104
 
        int u = get_value(x, y-1);
105
 
                
106
 
        if( match && v == d + scores.match ) {
107
 
            return 1 + getLen( x-1, y-1 );
108
 
        }
109
 
        if ( v == u + scores.del ) { //prefer deletion in X sequence to minimize result len
110
 
            return getLen(x, y-1);
111
 
        } 
112
 
        if ( !match && v == d + scores.mismatch ) { // prefer mismatch instead of insertion into X sequence
113
 
            return 1 + getLen(x-1, y-1);
114
 
        } 
115
 
        assert( v == l + scores.ins );
116
 
        return 1 + getLen(x-1, y); // this is insertion into X sequence
117
 
    }
118
 
private:
119
 
    void init()
120
 
    {
121
 
        for (int i=0; i<n; i++) {
122
 
            for (int j=0; j<m; j++) {
123
 
                set_pair(i, j, j+1, false);
124
 
            }
125
 
        }
126
 
    }
127
 
    void set_value( int x, int y, int val )
128
 
    {
129
 
        assert( !(val & MASK_FLAG_MISMATCH) );
130
 
        int oldval = get( x, y );
131
 
        set( x, y, (oldval & MASK_FLAG_MISMATCH) | val );
132
 
    }
133
 
    void set_mm_flag( int x, int y, bool flag )
134
 
    {
135
 
        int oldval = get( x, y );
136
 
        set( x, y, (oldval & MASK_VALUE)|(flag ? Flag_Match : Flag_Mismatch) );
137
 
    }
138
 
    void set_pair( int x, int y, int val, bool flag )
139
 
    {
140
 
        assert( !(val & MASK_FLAG_MISMATCH) );
141
 
        set( x, y, val | (flag ? Flag_Match : Flag_Mismatch) );
142
 
    }
143
 
    int get_value( int x, int y ) const
144
 
    {
145
 
        return get( x, y ) & MASK_VALUE;
146
 
    }
147
 
    bool get_flag( int x, int y ) const
148
 
    {
149
 
        return get( x, y ) & MASK_FLAG_MISMATCH;
150
 
    }
151
 
protected:
152
 
    bool allowInsDel;
153
 
private:
154
 
    const static int DEFAULT_SCORE_MATCH = 0;
155
 
    const static int DEFAULT_SCORE_MISMATCH = 1;
156
 
    const static int DEFAULT_SCORE_DEL = 1;
157
 
    const static int DEFAULT_SCORE_INS = 1;
158
 
 
159
 
    const static int MASK_VALUE = 0x7FFFFFFF;
160
 
    const static int MASK_FLAG_MISMATCH = 0x80000000;
161
 
    enum MismatchFlag
162
 
    {
163
 
        Flag_Mismatch = 0x00000000,
164
 
        Flag_Match = 0x80000000
165
 
    };
166
 
 
167
 
    MatchScores scores;
168
 
    FillStrategy strategy;
169
 
};
170
 
 
171
 
} //namespace
172
 
 
173
 
#endif