path: root/gfsm/gfsm/src/libgfsm/gfsmAutomaton.hi

/*=============================================================================*\
 * File: gfsmAutomaton.hi
 * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
 * Description: finite state machine library: automata: inline definitions
 *
 * Copyright (c) 2004-2008 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 <gfsmUtils.h>
#include <gfsmBitVector.h>
#include <stdlib.h>

/*======================================================================
 * Methods: Constructors etc.
 */

/*--------------------------------------------------------------
 * new_full()
 */
GFSM_INLINE
gfsmAutomaton *gfsm_automaton_new_full(gfsmAutomatonFlags flags, gfsmSRType srtype, gfsmStateId size)
{
  gfsmAutomaton *fsm = (gfsmAutomaton*)g_new0(gfsmAutomaton,1);
  fsm->flags         = flags;
  fsm->sr            = gfsm_semiring_new(srtype);
  fsm->states        = g_array_sized_new(FALSE, TRUE, sizeof(gfsmState), size);
  fsm->finals        = gfsm_set_new(gfsm_uint_compare);
  fsm->root_id       = gfsmNoState;
  return fsm;
}

/*--------------------------------------------------------------
 * new()
 */
GFSM_INLINE
gfsmAutomaton *gfsm_automaton_new(void)
{
  return gfsm_automaton_new_full(gfsmAutomatonDefaultFlags,
				 gfsmAutomatonDefaultSRType,
				 gfsmAutomatonDefaultSize);
}


/*--------------------------------------------------------------
 * copy_shallow()
 */
//#define GFSM_SHALLOW_ROOT 1
#undef  GFSM_SHALLOW_ROOT  //-- for local testing
GFSM_INLINE
gfsmAutomaton *gfsm_automaton_copy_shallow(gfsmAutomaton *dst, gfsmAutomaton *src)
{
  dst->flags   = src->flags;
#ifdef GFSM_SHALLOW_ROOT
  dst->root_id = src->root_id; //-- pre v0.0.9: DANGEROUS! (assumed by clone() ?!)
#endif
  //
  //-- copy semiring
  if (dst->sr && dst->sr->type != src->sr->type) {
    gfsm_semiring_free(dst->sr);
    dst->sr = gfsm_semiring_copy(src->sr);
  }
  return dst;
}

/*--------------------------------------------------------------
 * copy()
 */
//--extern

/*--------------------------------------------------------------
 * clone()
 */
GFSM_INLINE
gfsmAutomaton *gfsm_automaton_clone(gfsmAutomaton *fsm)
{
  return gfsm_automaton_copy(gfsm_automaton_new_full(gfsmAutomatonDefaultFlags,fsm->sr->type,0),fsm);
}

/*--------------------------------------------------------------
 * shadow()
 */
GFSM_INLINE
gfsmAutomaton *gfsm_automaton_shadow(gfsmAutomaton *fsm)
{
  return gfsm_automaton_copy_shallow(gfsm_automaton_new(), fsm);
}

/*--------------------------------------------------------------
 * swap()
 */
GFSM_INLINE
void gfsm_automaton_swap(gfsmAutomaton *fsm1, gfsmAutomaton *fsm2)
{
  if (fsm1 != fsm2) {
    gfsmAutomaton *tmp = g_new0(gfsmAutomaton,1);
    *tmp = *fsm2;
    *fsm2 = *fsm1;
    *fsm1 = *tmp;
    g_free(tmp);
  }
}

/*--------------------------------------------------------------
 * clear()
 */
//--extern

/*--------------------------------------------------------------
 * free()
 */
GFSM_INLINE
void gfsm_automaton_free(gfsmAutomaton *fsm)
{
  if (!fsm) return;
  gfsm_automaton_clear(fsm); //-- implicitly frees indices
  if (fsm->sr)     gfsm_semiring_free(fsm->sr);
  if (fsm->states) g_array_free(fsm->states,TRUE);
  if (fsm->finals) gfsm_weightmap_free(fsm->finals);
  g_free(fsm);
}

/*======================================================================
 * Methods: Accessors: Semiring
 */

/*--------------------------------------------------------------
 * get_semiring()
 */
GFSM_INLINE
gfsmSemiring *gfsm_automaton_get_semiring(gfsmAutomaton *fsm) { return fsm->sr; }

/*--------------------------------------------------------------
 * set_semiring()
 */
GFSM_INLINE
gfsmSemiring *gfsm_automaton_set_semiring(gfsmAutomaton *fsm, gfsmSemiring *sr)
{
  if (fsm->sr) gfsm_semiring_free(fsm->sr);
  fsm->sr = gfsm_semiring_copy(sr);
  return fsm->sr; //-- WARNING: in gfsm < v0.0.9, returned literal 'sr' parameter!
}

/*--------------------------------------------------------------
 * set_semiring_type()
 */
GFSM_INLINE
void gfsm_automaton_set_semiring_type(gfsmAutomaton *fsm, gfsmSRType srtype)
{
  if (!fsm->sr) fsm->sr = gfsm_semiring_new(srtype);
  else if (fsm->sr->type != srtype) {
    gfsm_semiring_free(fsm->sr);
    fsm->sr = gfsm_semiring_new(srtype);  
  }
}

/*======================================================================*/
///\name API: Automaton Structure

/*--------------------------------------------------------------
 * reserve_states()
 */
GFSM_INLINE
void gfsm_automaton_reserve_states(gfsmAutomaton *fsm, gfsmStateId n_states)
{
  if (n_states != gfsmNoState && n_states > fsm->states->len)
    g_array_set_size(fsm->states, n_states);
}

/*--------------------------------------------------------------
 * reserve_arcs()
 */
GFSM_INLINE
void gfsm_automaton_reserve_arcs(GFSM_UNUSED gfsmAutomaton *fsm, GFSM_UNUSED guint n_arcs)
{
  return;
}

/*--------------------------------------------------------------
 * n_states()
 */
GFSM_INLINE
gfsmStateId gfsm_automaton_n_states(gfsmAutomaton *fsm)
{
  return fsm->states->len;
} 

/*--------------------------------------------------------------
 * n_arcs()
 */
GFSM_INLINE
guint gfsm_automaton_n_arcs(gfsmAutomaton *fsm)
{
  return gfsm_automaton_n_arcs_full(fsm,NULL,NULL,NULL);
}

/*--------------------------------------------------------------
 * n_final_states()
 */
GFSM_INLINE
gfsmStateId gfsm_automaton_n_final_states(gfsmAutomaton *fsm)
{
  return gfsm_weightmap_size(fsm->finals);
}

/*--------------------------------------------------------------
 * finals_foreach
 */
GFSM_INLINE
void gfsm_automaton_finals_foreach(gfsmAutomaton *fsm, GTraverseFunc func, gpointer data)
{
  gfsm_weightmap_foreach(fsm->finals,func,data);
  return;
}

/*--------------------------------------------------------------
 * finals_to_array
 */
GFSM_INLINE
gfsmStateWeightPairArray* gfsm_automaton_finals_to_array(gfsmAutomaton *fsm, gfsmStateWeightPairArray *array)
{
  return gfsm_weightmap_to_array(fsm->finals,array);
}

/*--------------------------------------------------------------
 * get_root()
 */
GFSM_INLINE
gfsmStateId gfsm_automaton_get_root(gfsmAutomaton *fsm)
{
  return fsm->root_id;
}

/*--------------------------------------------------------------
 * set_root()
 */
GFSM_INLINE
void gfsm_automaton_set_root(gfsmAutomaton *fsm, gfsmStateId qid)
{
  if (qid!=gfsmNoState) qid = gfsm_automaton_ensure_state(fsm,qid);
  fsm->root_id = qid;
}


/*======================================================================
 * API: Automaton Properties
 */

/*--------------------------------------------------------------
 * is_cyclic_state()
 */
//--EXTERN

/*--------------------------------------------------------------
 * is_cyclic()
 */
//--extern

/*--------------------------------------------------------------
 * get_alphabet()
 */
//--EXTERN

/*======================================================================
 * API: Automaton States: gfsmState*
 */

/*--------------------------------------------------------------
 * open_state() [aka find_state()]
 */
GFSM_INLINE
gfsmState *gfsm_automaton_open_state(gfsmAutomaton *fsm, gfsmStateId qid)
{
  return (qid < fsm->states->len
	  ? (((gfsmState*)fsm->states->data)+qid)
	  : NULL);
}

/*--------------------------------------------------------------
 * add_state_full()
 */
GFSM_INLINE
gfsmStateId gfsm_automaton_add_state_full(gfsmAutomaton *fsm, gfsmStateId qid)
{
  gfsmState *st;
  if (qid == gfsmNoState)      qid = fsm->states->len;
  if (qid >= fsm->states->len) gfsm_automaton_reserve(fsm,qid+1);
  st           = gfsm_automaton_open_state(fsm,qid);
  st->is_valid = TRUE;
  return qid;
}

/*--------------------------------------------------------------
 * ensure_state()
 */
GFSM_INLINE
gfsmStateId gfsm_automaton_ensure_state(gfsmAutomaton *fsm, gfsmStateId qid)
{ return gfsm_automaton_add_state_full(fsm,qid); }

/*--------------------------------------------------------------
 * open_state_force() [aka get_state()]
 */
GFSM_INLINE
gfsmState *gfsm_automaton_open_state_force(gfsmAutomaton *fsm, gfsmStateId qid)
{
  return ((gfsmState*)fsm->states->data) + gfsm_automaton_ensure_state(fsm,qid);
}

/*--------------------------------------------------------------
 * close_state()
 */
GFSM_INLINE
void gfsm_automaton_close_state(GFSM_UNUSED gfsmAutomaton *fsm, GFSM_UNUSED gfsmState *qp)
{
  //gfsm_state_close(qp);
  return;
}

/*======================================================================
 * API: Automaton States
 */

/*--------------------------------------------------------------
 * has_state()
 */
GFSM_INLINE
gboolean gfsm_automaton_has_state(gfsmAutomaton *fsm, gfsmStateId qid)
{
  return qid < fsm->states->len && ((gfsmState*)fsm->states->data)[qid].is_valid;
}

/*--------------------------------------------------------------
 * state_is_final()
 */
GFSM_INLINE
gboolean gfsm_automaton_state_is_final(gfsmAutomaton *fsm, gfsmStateId qid)
{
  gfsmState *qp = gfsm_automaton_find_state(fsm,qid);
  return qp!=NULL && qp->is_valid && qp->is_final;
}

/*--------------------------------------------------------------
 * add_state()
 */
GFSM_INLINE
gfsmStateId gfsm_automaton_add_state(gfsmAutomaton *fsm)
{
  return gfsm_automaton_add_state_full(fsm,gfsmNoState);
}


/*--------------------------------------------------------------
 * remove_state()
 */
GFSM_INLINE
void gfsm_automaton_remove_state(gfsmAutomaton *fsm, gfsmStateId qid)
{
  gfsmState *s = gfsm_automaton_find_state(fsm,qid);
  if (!s || !s->is_valid) return;
  //
  if (s->is_final) gfsm_weightmap_remove(fsm->finals,GUINT_TO_POINTER(qid));
  if (qid==fsm->root_id) fsm->root_id = gfsmNoState;
  //
  gfsm_arclist_free(s->arcs);
  s->arcs     = NULL;
  s->is_valid = FALSE;
}

/*--------------------------------------------------------------
 * lookup_final()
 */
GFSM_INLINE
gboolean gfsm_automaton_lookup_final(gfsmAutomaton *fsm, gfsmStateId qid, gfsmWeight *wp)
{
  gfsmState *qp = gfsm_automaton_find_state(fsm,qid);
  if (!qp || !qp->is_valid || !qp->is_final) {
    *wp = fsm->sr->zero;
    return FALSE;
  }
  return gfsm_weightmap_lookup(fsm->finals, GUINT_TO_POINTER(qid), wp);
}

/*--------------------------------------------------------------
 * get_final_weight
 */
GFSM_INLINE
gfsmWeight gfsm_automaton_get_final_weight(gfsmAutomaton *fsm, gfsmStateId qid)
{
  gfsmWeight w =0; //-- convince gcc not to complain about uninitialized 'w'
#if 0
  //-- old implementation: direct weightmap lookup
  if (gfsm_weightmap_lookup(fsm->finals, GUINT_TO_POINTER(id), &w)) return w;
  return fsm->sr->zero;
#else
  gfsm_automaton_lookup_final(fsm,qid,&w);
  return w;
#endif
}

/*--------------------------------------------------------------
 * set_final_state_full
 */
GFSM_INLINE
void gfsm_automaton_set_final_state_full(gfsmAutomaton *fsm,
					 gfsmStateId    qid,
					 gboolean       is_final,
					 gfsmWeight     final_weight)
{
  gfsm_state_set_final(gfsm_automaton_get_state(fsm,qid),is_final);
  if (is_final) {
    gfsm_weightmap_insert(fsm->finals, GUINT_TO_POINTER(qid), final_weight);
  } else {
    gfsm_weightmap_remove(fsm->finals, GUINT_TO_POINTER(qid));
  }
}

/*--------------------------------------------------------------
 * set_final_state()
 */
GFSM_INLINE
void gfsm_automaton_set_final_state(gfsmAutomaton *fsm, gfsmStateId qid, gboolean is_final)
{
  gfsm_automaton_set_final_state_full(fsm,qid,is_final,fsm->sr->one);
}


/*--------------------------------------------------------------
 * out_degree()
 */
GFSM_INLINE
guint gfsm_automaton_out_degree(gfsmAutomaton *fsm, gfsmStateId qid)
{
  gfsmState *qp = gfsm_automaton_open_state(fsm,qid);
  if (!qp || !qp->is_valid) return 0;
  return gfsm_state_out_degree(qp);
}

/*--------------------------------------------------------------
 * renumber_states()
 */
//--EXTERN

/*--------------------------------------------------------------
 * renumber_states_full()
 */
//--EXTERN


/*======================================================================
 * Methods: Accessors: Automaton Arcs
 */

/*--------------------------------------------------------------
 * add_arc_link()
 */
GFSM_INLINE
void gfsm_automaton_add_arc_node(gfsmAutomaton *fsm,
				 gfsmState      *sp,
				 gfsmArcList    *node)
{
  //-- possibly sorted
  gfsmArcCompData acdata = { fsm->flags.sort_mode, fsm->sr, NULL, NULL };
  sp->arcs = gfsm_arclist_insert_node(sp->arcs, node, &acdata);

  //-- always unmark 'deterministic' flag -- better: check
  fsm->flags.is_deterministic = FALSE;

  //-- always mark arcs "dirty"
  /*fsm->flags.arcs_dirty=1;
   */

  //- always mark 'unsorted'
  /*
  alp->next = sp->arcs;
  sp->arcs = alp;
  fsm->flags.sort_mode = gfsmASMNone;
  */
}

/*--------------------------------------------------------------
 * add_arc()
 */
GFSM_INLINE
void gfsm_automaton_add_arc(gfsmAutomaton *fsm,
			    gfsmStateId qid1,
			    gfsmStateId qid2,
			    gfsmLabelId lo,
			    gfsmLabelId hi,
			    gfsmWeight  w)
{
  gfsmState *qp1;
  gfsm_automaton_ensure_state(fsm,qid2);
  qp1 = gfsm_automaton_get_state(fsm,qid1);
  gfsm_automaton_add_arc_node(fsm,
			      qp1,
			      gfsm_arclist_new_full(qid1,qid2,lo,hi,w,NULL));
}


/*--------------------------------------------------------------
 * arcsort_full()
 */
//-- EXTERN

/*--------------------------------------------------------------
 * arcsort()
 */
GFSM_INLINE
gfsmAutomaton *gfsm_automaton_arcsort(gfsmAutomaton *fsm, gfsmArcCompMask mode)
{
  if (mode != fsm->flags.sort_mode && mode != gfsmASMNone) {
    gfsmArcCompData acdata = { mode, fsm->sr, NULL, NULL };    
    gfsm_automaton_arcsort_full(fsm, (GCompareDataFunc)gfsm_arc_compare_bymask, &acdata);
  }
  fsm->flags.sort_mode = mode;
  return fsm;
}