gfsmAutomaton.h

Go to the documentation of this file.

/*=============================================================================*\
 * File: gfsmAutomaton.h
 * Author: Bryan Jurish <moocow.bovine@gmail.com>
 * Description: finite state machine library: automata
 *
 * 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 3 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
 *=============================================================================*/

#ifndef _GFSM_AUTOMATON_H
#define _GFSM_AUTOMATON_H

#include <gfsmAlphabet.h>
#include <gfsmState.h>
#include <gfsmWeightMap.h>
#include <gfsmBitVector.h>

/*======================================================================
 * Types
 */

typedef struct {
  guint32 is_transducer     : 1;       
  guint32 is_weighted       : 1;       
  guint32 is_deterministic  : 1;       
  guint32 sort_mode         : 24;      
  guint32 unused            : 5;       
} gfsmAutomatonFlags;

typedef struct {
  //-- basic data
  gfsmAutomatonFlags  flags;     
  gfsmSemiring       *sr;        
  GArray             *states;    
  gfsmWeightMap      *finals;    
  gfsmStateId         root_id;   
} gfsmAutomaton;

/*======================================================================
 * Constants
 */
extern const gfsmStateId gfsmAutomatonDefaultSize;

extern const gfsmAutomatonFlags gfsmAutomatonDefaultFlags;

extern const gfsmSRType gfsmAutomatonDefaultSRType;

/*======================================================================*/


GFSM_INLINE
gfsmAutomaton *gfsm_automaton_new_full(gfsmAutomatonFlags flags, gfsmSRType srtype, gfsmStateId n_states);

GFSM_INLINE
gfsmAutomaton *gfsm_automaton_new(void);

GFSM_INLINE
gfsmAutomaton *gfsm_automaton_clone(gfsmAutomaton *fsm);

GFSM_INLINE
gfsmAutomaton *gfsm_automaton_copy_shallow(gfsmAutomaton *dst, gfsmAutomaton *src);

gfsmAutomaton *gfsm_automaton_copy(gfsmAutomaton *dst, gfsmAutomaton *src);

GFSM_INLINE
gfsmAutomaton *gfsm_automaton_shadow(gfsmAutomaton *fsm);

GFSM_INLINE
void gfsm_automaton_swap(gfsmAutomaton *fsm1, gfsmAutomaton *fsm2);

void gfsm_automaton_clear(gfsmAutomaton *fsm);

GFSM_INLINE
void gfsm_automaton_free(gfsmAutomaton *fsm);


/*======================================================================*/


GFSM_INLINE
gfsmSemiring *gfsm_automaton_get_semiring(gfsmAutomaton *fsm);

GFSM_INLINE
gfsmSemiring *gfsm_automaton_set_semiring(gfsmAutomaton *fsm, gfsmSemiring *sr);

GFSM_INLINE
void gfsm_automaton_set_semiring_type(gfsmAutomaton *fsm, gfsmSRType srtype);


/*======================================================================*/


GFSM_INLINE
void gfsm_automaton_reserve_states(gfsmAutomaton *fsm, gfsmStateId n_states);

#define gfsm_automaton_reserve(fsm,n_states) gfsm_automaton_reserve_states((fsm),(n_states))


GFSM_INLINE
void gfsm_automaton_reserve_arcs(gfsmAutomaton *fsm, guint n_arcs);

GFSM_INLINE
gfsmStateId gfsm_automaton_n_states(gfsmAutomaton *fsm);

GFSM_INLINE
gfsmStateId gfsm_automaton_n_final_states(gfsmAutomaton *fsm);

GFSM_INLINE
guint gfsm_automaton_n_arcs(gfsmAutomaton *fsm);

GFSM_INLINE
gfsmStateId gfsm_automaton_get_root(gfsmAutomaton *fsm);

GFSM_INLINE
void gfsm_automaton_set_root(gfsmAutomaton *fsm, gfsmStateId new_root_id);

GFSM_INLINE
void gfsm_automaton_finals_foreach(gfsmAutomaton *fsm, GTraverseFunc func, gpointer data);

GFSM_INLINE
gfsmStateWeightPairArray* gfsm_automaton_finals_to_array(gfsmAutomaton *fsm, gfsmStateWeightPairArray *array);


/*======================================================================*/

#define gfsm_automaton_is_transducer(fsm) ((fsm)->flags.is_transducer)

#define gfsm_automaton_is_weighted(fsm) ((fsm)->flags.is_weighted)

#define gfsm_automaton_sortmode(fsm) \
    ((gfsmArcSortMode)(gfsm_acmask_nth((fsm)->flags.sort_mode,0)))

//  ((gfsmArcSortMode)((fsm)->flags.sort_mode))

guint gfsm_automaton_n_arcs_full(gfsmAutomaton *fsm,
                                 guint *n_lo_epsilon,
                                 guint *n_hi_epsilon,
                                 guint *n_both_epsilon);

gboolean gfsm_automaton_is_cyclic_state(gfsmAutomaton *fsm,
                                        gfsmStateId    qid,
                                        gfsmBitVector *visited,
                                        gfsmBitVector *completed);

gboolean gfsm_automaton_is_cyclic(gfsmAutomaton *fsm);

#define gfsm_automaton_is_acyclic(fsm) (!gfsm_automaton_is_cyclic(fsm))

gfsmAlphabet *gfsm_automaton_get_alphabet(gfsmAutomaton *fsm,
                                          gfsmLabelSide  which,
                                          gfsmAlphabet  *alph);


void gfsm_automaton_renumber_states(gfsmAutomaton *fsm);

void gfsm_automaton_renumber_states_full(gfsmAutomaton *fsm, GArray *old2new, gfsmStateId n_new_states);

void gfsm_automaton_truncate_invalid_states(gfsmAutomaton *fsm);


/*======================================================================*/


GFSM_INLINE
gfsmState *gfsm_automaton_open_state(gfsmAutomaton *fsm, gfsmStateId qid);

GFSM_INLINE
gfsmState *gfsm_automaton_open_state_force(gfsmAutomaton *fsm, gfsmStateId qid);

GFSM_INLINE
void gfsm_automaton_close_state(gfsmAutomaton *fsm, gfsmState *qp);

#define gfsm_automaton_find_state(fsm,qid) gfsm_automaton_open_state((fsm),(qid))

#define gfsm_automaton_find_state_const(fsm,qid) ((const gfsmState*)(gfsm_automaton_open_state((fsm),(qid))))

#define gfsm_automaton_get_state(fsm,qid) gfsm_automaton_open_state_force((fsm),(qid))


/*======================================================================*/


/*--------------------------------------------------------------
 * has_state()
 */
GFSM_INLINE
gboolean gfsm_automaton_has_state(gfsmAutomaton *fsm, gfsmStateId qid);

GFSM_INLINE
gfsmStateId gfsm_automaton_add_state_full(gfsmAutomaton *fsm, gfsmStateId qid);

GFSM_INLINE
gfsmStateId gfsm_automaton_ensure_state(gfsmAutomaton *fsm, gfsmStateId qid);

GFSM_INLINE
gfsmStateId gfsm_automaton_add_state(gfsmAutomaton *fsm);

GFSM_INLINE
void gfsm_automaton_remove_state(gfsmAutomaton *fsm, gfsmStateId qid);

GFSM_INLINE
gboolean gfsm_automaton_lookup_final(gfsmAutomaton *fsm, gfsmStateId qid, gfsmWeight *wp);

GFSM_INLINE
gboolean gfsm_automaton_state_is_final(gfsmAutomaton *fsm, gfsmStateId qid);

#define gfsm_automaton_is_final_state(fsm,qid) gfsm_automaton_state_is_final((fsm),(qid))

GFSM_INLINE
gfsmWeight gfsm_automaton_get_final_weight(gfsmAutomaton *fsm, gfsmStateId qid);

GFSM_INLINE
void gfsm_automaton_set_final_state_full(gfsmAutomaton *fsm,
                                         gfsmStateId    qid,
                                         gboolean       is_final,
                                         gfsmWeight     final_weight);

GFSM_INLINE
void gfsm_automaton_set_final_state(gfsmAutomaton *fsm, gfsmStateId qid, gboolean is_final);

GFSM_INLINE
guint gfsm_automaton_out_degree(gfsmAutomaton *fsm, gfsmStateId qid);


/*======================================================================*/


GFSM_INLINE
void gfsm_automaton_add_arc(gfsmAutomaton *fsm,
                            gfsmStateId qid1,
                            gfsmStateId qid2,
                            gfsmLabelId lo,
                            gfsmLabelId hi,
                            gfsmWeight  w);

GFSM_INLINE
void gfsm_automaton_add_arc_node(gfsmAutomaton *fsm,
                                 gfsmState     *sp,
                                 gfsmArcList   *node);

GFSM_INLINE
void gfsm_automaton_remove_arc_ptr(gfsmAutomaton *fsm, gfsmArc *a);

GFSM_INLINE
void gfsm_automaton_remove_arc_node(gfsmAutomaton *fsm, gfsmState *sp, gfsmArcList *node);

GFSM_INLINE
gfsmAutomaton *gfsm_automaton_arcsort(gfsmAutomaton *fsm, gfsmArcCompMask mode);

void gfsm_automaton_arcsort_full(gfsmAutomaton *fsm, GCompareDataFunc cmpfunc, gpointer data);

#define gfsm_automaton_arcsort_with_data(fsm,cmpfunc,data) gfsm_automaton_arcsort_full((fsm),(cmpfunc),(data))

gfsmAutomaton* gfsm_automaton_arcuniq(gfsmAutomaton *fsm);


//-- inline definitions
#ifdef GFSM_INLINE_ENABLED
# include <gfsmAutomaton.hi>
#endif

#endif /* _GFSM_AUTOMATON_H */