diff options
Diffstat (limited to 'gfsm/gfsm/src/libgfsm/gfsmSemiring.hi')
| -rw-r--r-- | gfsm/gfsm/src/libgfsm/gfsmSemiring.hi | 257 |
1 files changed, 257 insertions, 0 deletions
diff --git a/gfsm/gfsm/src/libgfsm/gfsmSemiring.hi b/gfsm/gfsm/src/libgfsm/gfsmSemiring.hi new file mode 100644 index 0000000..cff434b --- /dev/null +++ b/gfsm/gfsm/src/libgfsm/gfsmSemiring.hi @@ -0,0 +1,257 @@ + +/*=============================================================================*\ + * File: gfsmSemiring.def + * Author: Bryan Jurish <moocow@ling.uni-potsdam.de> + * Description: finite state machine library: semirings: inline definitions + * + * Copyright (c) 2004-2007 Bryan Jurish. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + *=============================================================================*/ + +#include <float.h> +#include <math.h> +#include <string.h> + +/*====================================================================== + * Semiring: general utilities + */ + +// LOG_BIG = log(1E31) +#define LOG_BIG 71.3801378828154 +/* +//#define LOG_ZERO -FLT_MAX +#define LOG_ZERO -1E+38F +#define LOG_ONE 0 +#define LOG_NONE 1 +*/ +GFSM_INLINE +gfsmWeight gfsm_log_add(gfsmWeight x, gfsmWeight y) +{ + if (y-x > LOG_BIG) return y; + else if (x-y > LOG_BIG) return x; + /*else return min(x,y) + log(exp(x-min(x,y)) + exp(y-min(x,y))); */ + else if (x<y) return x + log( 1 + exp(y-x)); + else return y + log(exp(x-y) + 1); +} +#undef LOG_BIG + + +/*====================================================================== + * Semiring: methods: constructors etc. + */ + +/*-------------------------------------------------------------- + * init() + */ +GFSM_INLINE +void gfsm_semiring_init(gfsmSemiring *sr, gfsmSRType type) +{ + memset(sr, 0, type==gfsmSRTUser ? sizeof(gfsmUserSemiring) : sizeof(gfsmSemiring)); + sr->type = type; + switch (type) { + case gfsmSRTBoolean: + sr->zero = 0; + sr->one = 1; + break; + case gfsmSRTLog: + sr->zero = FLT_MAX; + sr->one = 0; + break; + case gfsmSRTPLog: + sr->zero = -FLT_MAX; + sr->one = 0; + break; + case gfsmSRTTrivial: + sr->zero = 0; + sr->one = 0; + break; + case gfsmSRTTropical: + sr->zero = FLT_MAX; + sr->one = 0; + break; + case gfsmSRTReal: + default: + sr->zero = 0; + sr->one = 1; + break; + } +} + +/*-------------------------------------------------------------- + * new() + */ +GFSM_INLINE +gfsmSemiring *gfsm_semiring_new(gfsmSRType type) +{ + gfsmSemiring *sr = (gfsmSemiring*)g_new(gfsmSemiring,1); + gfsm_semiring_init(sr,type); + return sr; +} + +/*-------------------------------------------------------------- + * user_new() + */ +GFSM_INLINE +gfsmUserSemiring *gfsm_user_semiring_new(gfsmSRBinaryPredicate equal_func, + gfsmSRBinaryPredicate less_func, + gfsmSRBinaryOp plus_func, + gfsmSRBinaryOp times_func) +{ + gfsmUserSemiring *sr = g_new(gfsmUserSemiring, 1); + gfsm_semiring_init((gfsmSemiring*)sr,gfsmSRTUser); + sr->equal_func = equal_func; + sr->less_func = less_func; + sr->plus_func = plus_func; + sr->times_func = times_func; + return sr; +} + +/*-------------------------------------------------------------- + * copy() + */ +GFSM_INLINE +gfsmSemiring *gfsm_semiring_copy(gfsmSemiring *sr) +{ + if (sr->type==gfsmSRTUser) + return (gfsmSemiring*)gfsm_user_semiring_new(((gfsmUserSemiring*)sr)->equal_func, + ((gfsmUserSemiring*)sr)->less_func, + ((gfsmUserSemiring*)sr)->plus_func, + ((gfsmUserSemiring*)sr)->times_func); + return gfsm_semiring_new(sr->type); +} + +/*-------------------------------------------------------------- + * free() + */ +GFSM_INLINE +void gfsm_semiring_free(gfsmSemiring *sr) +{ + if (sr->type==gfsmSRTUser) g_free((gfsmUserSemiring*)sr); + else g_free(sr); +} + + +/*====================================================================== + * Semiring: methods: general accessors + */ + +/*-------------------------------------------------------------- + * zero() + */ +GFSM_INLINE +gfsmWeight gfsm_sr_zero(gfsmSemiring *sr) { return sr ? sr->zero : 0; } + +/*-------------------------------------------------------------- + * one() + */ +GFSM_INLINE +gfsmWeight gfsm_sr_one(gfsmSemiring *sr) { return sr ? sr->one : 1; } + +/*-------------------------------------------------------------- + * equal() + */ +GFSM_INLINE +gboolean gfsm_sr_equal(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y) +{ + return (sr->type == gfsmSRTUser && ((gfsmUserSemiring*)sr)->equal_func + ? ((*((gfsmUserSemiring*)sr)->equal_func)(sr,x,y)) \ + : (x==y)); +} + +/*-------------------------------------------------------------- + * less() + */ +GFSM_INLINE +gboolean gfsm_sr_less(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y) +{ + switch (sr->type) { + case gfsmSRTLog: + case gfsmSRTTropical: return (x < y); + + case gfsmSRTPLog: return (x > y); + + case gfsmSRTTrivial: return 0; + + case gfsmSRTUser: + if (((gfsmUserSemiring*)sr)->less_func) + return (*((gfsmUserSemiring*)sr)->less_func)(sr,x,y); + + case gfsmSRTBoolean: + case gfsmSRTReal: + default: return (x > y); + } + return FALSE; //-- should never happen +} + +/*-------------------------------------------------------------- + * plus() + */ +GFSM_INLINE +gfsmWeight gfsm_sr_plus(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y) +{ + switch (sr->type) { + case gfsmSRTBoolean: return x || y; + //case gfsmSRTLog: return -log(exp(-x) + exp(-y)); + case gfsmSRTLog: return -gfsm_log_add(-x,-y); + case gfsmSRTPLog: return gfsm_log_add( x, y); + case gfsmSRTTropical: return (x < y ? x : y); + case gfsmSRTTrivial: return 0; + + case gfsmSRTUser: + if (((gfsmUserSemiring*)sr)->plus_func) + return (*((gfsmUserSemiring*)sr)->plus_func)(sr,x,y); + + case gfsmSRTReal: + default: return x + y; + } + return sr->zero; //-- should never happen +} + +/*-------------------------------------------------------------- + * times() + */ +GFSM_INLINE +gfsmWeight gfsm_sr_times(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y) +{ + switch (sr->type) { + case gfsmSRTBoolean: return x && y; + case gfsmSRTLog: + case gfsmSRTPLog: + case gfsmSRTTropical: return x + y; + case gfsmSRTTrivial: return 0; + + case gfsmSRTUser: + if (((gfsmUserSemiring*)sr)->times_func) + return (*((gfsmUserSemiring*)sr)->times_func)(sr,x,y); + + case gfsmSRTReal: + default: return x * y; + } + return sr->zero; //-- should never happen +} + +/*-------------------------------------------------------------- + * div() + */ +/*gboolean gfsm_sr_div(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y) + { return (sr->div_func ? ((*sr->div_func)(sr,x,y)) : (x/y)); } +*/ +//@} + + +/*====================================================================== + * Semiring: string utilities + */ |