gfsmPaths.h

Go to the documentation of this file.

/*=============================================================================*\
 * File: gfsmPaths.h
 * Author: Bryan Jurish <moocow.bovine@gmail.com>
 * Description: finite state machine library
 *
 * Copyright (c) 2005-2011 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_PATHS_H
#define _GFSM_PATHS_H

#include <gfsmAutomaton.h>

/*======================================================================
 * Types: paths
 */

typedef struct {
  gfsmLabelVector *lo;  
  gfsmLabelVector *hi;  
  gfsmWeight       w;   
} gfsmPath;

/*  The pointer data in the \a data field are (gfsmArc*)s
 *  (usually pointing into an existing gfsmAutomaton) for all but the final
 *  pointer element of the gfsmArcPath, and the
 *  final element is a gpointer-encoded gfsmWeight representing
 *  the final weight associated with the arc path; extract it
 *  e.g. with gfsm_ptr2weight(arcpath->data[arcpath->len-1]).
 */
typedef GPtrArray gfsmArcPath;


/*======================================================================
 * Methods: Path Utilities
 */

//------------------------------


gfsmLabelVector *gfsm_label_vector_copy(gfsmLabelVector *dst, gfsmLabelVector *src);

#define gfsm_label_vector_dup(src) \
  gfsm_label_vector_copy(g_ptr_array_sized_new(src->len), src)

gfsmLabelVector *gfsm_label_vector_reverse(gfsmLabelVector *v);

//------------------------------


GFSM_INLINE
gfsmPath *gfsm_path_new_full(gfsmLabelVector *lo, gfsmLabelVector *hi, gfsmWeight w);

#define gfsm_path_new(sr) \
  gfsm_path_new_full(NULL,NULL,gfsm_sr_one(sr))

gfsmPath *gfsm_path_new_copy(gfsmPath *p1);

gfsmPath *gfsm_path_new_append(gfsmPath *p1, gfsmLabelVal lo, gfsmLabelVal hi, gfsmWeight w, gfsmSemiring *sr);

gfsmPath *gfsm_path_new_times_w(gfsmPath *p1, gfsmWeight w, gfsmSemiring *sr);

GFSM_INLINE
void gfsm_path_push(gfsmPath *p, gfsmLabelVal lo, gfsmLabelVal hi, gfsmWeight w, gfsmSemiring *sr);

GFSM_INLINE
void gfsm_path_pop(gfsmPath *p, gfsmLabelVal lo, gfsmLabelVal hi);

gint gfsm_path_compare_data(const gfsmPath *p1, const gfsmPath *p2, gfsmSemiring *sr);

GFSM_INLINE
gfsmPath *gfsm_path_reverse(gfsmPath *p);

GFSM_INLINE
void gfsm_path_free(gfsmPath *p);

//======================================================================


gfsmSet *gfsm_automaton_paths(gfsmAutomaton *fsm, gfsmSet *paths);

gfsmSet *gfsm_automaton_paths_full(gfsmAutomaton *fsm, gfsmSet *paths, gfsmLabelSide which);


gfsmSet *_gfsm_automaton_paths_r(gfsmAutomaton *fsm,
                                 gfsmSet       *paths,
                                 gfsmLabelSide  which, 
                                 gfsmStateId    q,
                                 gfsmPath      *path);


//------------------------------
GSList *gfsm_paths_to_strings(gfsmSet *paths,
                              gfsmAlphabet *abet_lo,
                              gfsmAlphabet *abet_hi,
                              gfsmSemiring       *sr,
                              gboolean warn_on_undefined,
                              gboolean att_style,
                              GSList *strings);

typedef struct gfsmPathsToStringsOptions_ {
  gfsmAlphabet *abet_lo;  
  gfsmAlphabet *abet_hi;  
  gfsmSemiring       *sr; 
  gboolean warn_on_undefined;  
  gboolean att_style;          
  GSList *strings;             
} gfsmPathsToStringsOptions;

#define _gfsm_paths_to_strings_options gfsmPathsToStringsOptions_

gboolean _gfsm_paths_to_strings_foreach_func(gfsmPath *path,
                                             gpointer value_dummy,
                                             gfsmPathsToStringsOptions *opts);

GString *gfsm_path_to_gstring(gfsmPath     *path,
                              GString      *gs,
                              gfsmAlphabet *abet_lo,
                              gfsmAlphabet *abet_hi,
                              gfsmSemiring *sr,
                              gboolean      warn_on_undefined,
                              gboolean      att_style);

char *gfsm_path_to_string(gfsmPath     *path,
                          gfsmAlphabet *abet_lo,
                          gfsmAlphabet *abet_hi,
                          gfsmSemiring *sr,
                          gboolean      warn_on_undefined,
                          gboolean      att_style);

//------------------------------
// \name gfsmArcPath Utilities

GFSM_INLINE
gfsmArcPath *gfsm_arcpath_new(void);

GFSM_INLINE
gfsmArcPath *gfsm_arcpath_new_append(gfsmArcPath *p1, gfsmArc *a);

gfsmArcPath *gfsm_arcpath_copy(gfsmArcPath *dst, gfsmArcPath *src);

GFSM_INLINE
gfsmArcPath *gfsm_arcpath_dup(gfsmArcPath *p1);

GFSM_INLINE
void gfsm_arcpath_free(gfsmArcPath *p);

void gfsm_arcpath_list_free(GSList *arcpaths);

//======================================================================


GSList *gfsm_automaton_arcpaths(gfsmAutomaton *fsm);


void _gfsm_automaton_arcpaths_r(gfsmAutomaton  *fsm,
                                gfsmStateId     qid,
                                GSList         *path,
                                guint           path_len,
                                GSList        **paths,
                                GSList        **nodes
                                );

typedef struct gfsmArcPathToStringOptions_ {
  gfsmStateId   q0;            
  gfsmAlphabet *abet_q;        
  gfsmAlphabet *abet_lo;       
  gfsmAlphabet *abet_hi;       
  gfsmSemiring *sr;            
  gboolean warn_on_undefined;  
  gboolean att_style;          
  gboolean compress_id;        
  gboolean show_states;        
} gfsmArcPathToStringOptions;


GString *gfsm_arcpath_to_gstring(gfsmArcPath *path, GString *gs, gfsmArcPathToStringOptions *opts);

char *gfsm_arcpath_to_string(gfsmArcPath *path, gfsmArcPathToStringOptions *opts);

GSList *gfsm_arcpaths_to_strings(GSList *paths, gfsmArcPathToStringOptions *opts);


//======================================================================


#define gfsm_viterbi_trellis_paths(trellis,paths) \
  gfsm_viterbi_trellis_paths_full((trellis),(paths),gfsmLSUpper)


gfsmSet *gfsm_viterbi_trellis_paths_full(gfsmAutomaton *trellis, gfsmSet *paths, gfsmLabelSide which);


#define gfsm_viterbi_trellis_bestpath(trellis,path) \
  gfsm_viterbi_trellis_bestpath_full((trellis),(path),gfsmLSUpper)

gfsmPath *gfsm_viterbi_trellis_bestpath_full(gfsmAutomaton *trellis, gfsmPath *path, gfsmLabelSide which);

void _gfsm_viterbi_trellis_bestpath_r(gfsmAutomaton *trellis,
                                      gfsmPath      *path,
                                      gfsmLabelSide  which,
                                      gfsmStateId    qid);


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

#endif /* _GFSM_PATHS_H */