diff options
Diffstat (limited to 'gfsm/gfsm/src/libgfsm/gfsmStateSet.c')
| -rw-r--r-- | gfsm/gfsm/src/libgfsm/gfsmStateSet.c | 222 |
1 files changed, 222 insertions, 0 deletions
diff --git a/gfsm/gfsm/src/libgfsm/gfsmStateSet.c b/gfsm/gfsm/src/libgfsm/gfsmStateSet.c new file mode 100644 index 0000000..0afc852 --- /dev/null +++ b/gfsm/gfsm/src/libgfsm/gfsmStateSet.c @@ -0,0 +1,222 @@ + +/*=============================================================================*\ + * File: gfsmStateSet.c + * Author: Bryan Jurish <moocow@ling.uni-potsdam.de> + * Description: finite state machine library + * + * 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 <gfsmStateSet.h> +#include <gfsmArcIter.h> + +//-- no-inline definitions +#ifndef GFSM_INLINE_ENABLED +# include <gfsmStateSet.hi> +#endif + +/*====================================================================== + * Constants + */ +const guint gfsmStateSetDefaultSize = 2; + +/*====================================================================== + * Methods: Constructors etc. + */ +//-- inlined + +/*====================================================================== + * Methods: Accessors + */ + +//-------------------------------------------------------------- +// find() +gfsmStateSetIter gfsm_stateset_find(gfsmStateSet *sset, gfsmStateId id) +{ + gfsmStateSetIter sseti; + gfsmStateId iid; + for (sseti = gfsm_stateset_iter_begin(sset); + (iid=gfsm_stateset_iter_id(sseti)) != gfsmNoState; + sseti = gfsm_stateset_iter_next(sset,sseti)) + { + if (id == iid) return sseti; + else if (id < iid) return NULL; + } + return NULL; +} + +//-------------------------------------------------------------- +// insert() +gboolean gfsm_stateset_insert(gfsmStateSet *sset, gfsmStateId id) +{ + guint i; + for (i = 0; i < sset->len && id > g_array_index(sset,gfsmStateId,i); i++) ; + + if (i == sset->len) { + g_array_append_val(sset,id); + } + else if (id == g_array_index(sset,gfsmStateId,i)) { + return TRUE; + } + else { + g_array_insert_val(sset,i,id); + } + return FALSE; +} + +//-------------------------------------------------------------- +// union() +gfsmStateSet *gfsm_stateset_union(gfsmStateSet *sset1, gfsmStateSet *sset2) +{ + guint i1=0, i2; + for (i2=0; i2 < sset2->len; i2++) { + gfsmStateId id = g_array_index(sset2,gfsmStateId,i2); + for (; i1 < sset1->len && id > g_array_index(sset1,gfsmStateId,i1); i1++) ; + + if (i1 == sset1->len) g_array_append_val(sset1,id); + else if (id == g_array_index(sset1,gfsmStateId,i1)) continue; + else g_array_insert_val(sset1,i1,id); + } + return sset1; +} + +//-------------------------------------------------------------- +// remove() +gboolean gfsm_stateset_remove(gfsmStateSet *sset, gfsmStateId id) { + guint i; + for (i = 0; i < sset->len && id > g_array_index(sset,gfsmStateId,i); i++) ; + if (i != sset->len && id == g_array_index(sset,gfsmStateId,i)) { + g_array_remove_index(sset,i); + return TRUE; + } + return FALSE; +} + + +//-------------------------------------------------------------- +// equal() +gboolean gfsm_stateset_equal(gfsmStateSet *sset1, gfsmStateSet *sset2) +{ + guint i; + if (sset1->len != sset2->len) return FALSE; + for (i=0; i < sset1->len; i++) { + if (g_array_index(sset1,gfsmStateId,i) != g_array_index(sset2,gfsmStateId,i)) return FALSE; + } + return TRUE; +} + +//-------------------------------------------------------------- +// foreach() +void gfsm_stateset_foreach(gfsmStateSet *sset, gfsmStateSetForeachFunc func, gpointer data) +{ + guint i; + for (i = 0; i < sset->len; i++) { + if ((*func)(g_array_index(sset,gfsmStateId,i), data)) break; + } +} + + +/*====================================================================== + * Methods: iterators + */ +//-- inlined + +/*====================================================================== + * Methods: Utilities + */ + +/*-------------------------------------------------------------- + * hash() + */ +guint gfsm_stateset_hash(gfsmStateSet *sset) +{ + guint hv = 0; + gfsmStateSetIter sseti; + gfsmStateId iid; + for (sseti = gfsm_stateset_iter_begin(sset); + (iid=gfsm_stateset_iter_id(sseti)) != gfsmNoState; + sseti = gfsm_stateset_iter_next(sset,sseti)) + { + hv += 5*iid; + } + return hv; +} + + +/*====================================================================== + * Methods: Automaton access + */ + +//-------------------------------------------------------------- +// has_final_state() +gboolean gfsm_stateset_has_final_state(gfsmStateSet *sset, gfsmAutomaton *fsm) +{ + guint i; + for (i = 0; i < sset->len; i++) { + if (gfsm_automaton_is_final_state(fsm, g_array_index(sset,gfsmStateId,i))) return TRUE; + } + return FALSE; +} + +//-------------------------------------------------------------- +// lookup_final_weight() +gboolean gfsm_stateset_lookup_final_weight(gfsmStateSet *sset, gfsmAutomaton *fsm, gfsmWeight *wp) +{ + guint i; + gboolean rc=FALSE; + *wp = fsm->sr->one; + gfsmWeight w; + for (i = 0; i < sset->len; i++) { + gfsmStateId id = g_array_index(sset,gfsmStateId,i); + if (gfsm_automaton_lookup_final(fsm,id,&w)) { + *wp = gfsm_sr_plus(fsm->sr, *wp, w); + rc = TRUE; + } + } + return rc; +} + +/*-------------------------------------------------------------- + * populate() + */ +void gfsm_stateset_populate(gfsmStateSet *sset, + gfsmAutomaton *fsm, + gfsmStateId id, + gfsmLabelVal lo, + gfsmLabelVal hi) +{ + gfsmArcIter ai; + if (gfsm_stateset_insert(sset,id)) return; + + for (gfsm_arciter_open(&ai,fsm,id), gfsm_arciter_seek_both(&ai,lo,hi); + gfsm_arciter_ok(&ai); + gfsm_arciter_next(&ai), gfsm_arciter_seek_both(&ai,lo,hi)) + { + gfsm_stateset_populate(sset,fsm,gfsm_arciter_arc(&ai)->target,lo,hi); + } + gfsm_arciter_close(&ai); +} + +/*-------------------------------------------------------------- + * has_final_state() + */ +//--inlined + +/*-------------------------------------------------------------- + * lookup_final_weight() + */ +//--inlined |