1 # Copyright (C) 2013 Martin A. Hansen.
3 # This program is free software; you can redistribute it and/or
4 # modify it under the terms of the GNU General Public License
5 # as published by the Free Software Foundation; either version 2
6 # of the License, or (at your option) any later version.
8 # This program is distributed in the hope that it will be useful,
9 # but WITHOUT ANY WARRANTY; without even the implied warranty of
10 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 # GNU General Public License for more details.
13 # You should have received a copy of the GNU General Public License
14 # along with this program; if not, write to the Free Software
15 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 # http://www.gnu.org/copyleft/gpl.html
19 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
21 # This software is part of the Biopieces framework (www.biopieces.org).
23 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
30 def self.distance(s, t)
32 return t.length if s.length == 0;
33 return s.length if t.length == 0;
35 v0 = "\0" * (t.length + 1) * BYTES_IN_INT
36 v1 = "\0" * (t.length + 1) * BYTES_IN_INT
39 l.distance_C(s, t, s.length, t.length, v0, v1)
45 # >>>>>>>>>>>>>>> RubyInline C code <<<<<<<<<<<<<<<
49 unsigned int min(unsigned int a, unsigned int b, unsigned int c)
70 char *s = (char *) StringValuePtr(_s);
71 char *t = (char *) StringValuePtr(_t);
72 unsigned int s_len = FIX2UINT(_s_len);
73 unsigned int t_len = FIX2UINT(_t_len);
74 unsigned int *v0 = (unsigned int *) StringValuePtr(_v0);
75 unsigned int *v1 = (unsigned int *) StringValuePtr(_v1);
79 unsigned int cost = 0;
81 for (i = 0; i < t_len + 1; i++)
84 for (i = 0; i < s_len; i++)
88 for (j = 0; j < t_len; j++)
90 cost = (s[i] == t[j]) ? 0 : 1;
91 v1[j + 1] = min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);
94 for (j = 0; j < t_len + 1; j++)
98 return UINT2NUM(v1[t_len]);
104 # >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<