1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
/*=============================================================================*\
* File: gfsmStateSet.h
* 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
*=============================================================================*/
/** \file gfsmStateSet.h
* \brief Sets of (gfsmStateId)s
*/
#ifndef _GFSM_STATESET_H
#define _GFSM_STATESET_H
#include <gfsmAutomaton.h>
/*======================================================================
* Types
*/
/** \brief typedef for sets of automaton state-Ids
* \detail current implementation uses a sorted array
*/
typedef GArray gfsmStateSet;
/** \brief typedef for weighted sets of automaton state-Ids */
typedef struct {
gfsmStateSet *set; /**< Set of gfsmStateIds */
gfsmWeight weight; /**< Weight of this set */
} gfsmWeightedStateSet;
/*======================================================================
* Constants
*/
///\name Constants
//@{
/** Default initial size of state-sets */
extern const guint gfsmStateSetDefaultSize;
//@}
/*======================================================================
* Methods: Constructors etc.
*/
/// \name Constructors etc.
//@{
/** Create and return a new state-set, giving initial reserved size */
GFSM_INLINE
gfsmStateSet *gfsm_stateset_sized_new(guint isize);
/** Create and return a new state-set */
GFSM_INLINE
gfsmStateSet *gfsm_stateset_new(void);
/** Create and return a new singleton state-set */
GFSM_INLINE
gfsmStateSet *gfsm_stateset_new_singleton(gfsmStateId id);
/** clear a state-set */
GFSM_INLINE
void gfsm_stateset_clear(gfsmStateSet *sset);
/** Create and return an exact copy of a state-set */
GFSM_INLINE
gfsmStateSet *gfsm_stateset_clone(gfsmStateSet *src);
/** destroy a state-set */
GFSM_INLINE
void gfsm_stateset_free(gfsmStateSet *sset);
//@}
/*======================================================================
* Methods: Accessors
*/
///\name Accessors
//@{
/** Get minimum element of a state-set */
GFSM_INLINE
gfsmStateId gfsm_stateset_min(gfsmStateSet *sset);
/** Get number of elements in a state-set */
GFSM_INLINE
guint gfsm_stateset_size(gfsmStateSet *sset);
/** Check whether a state-id is contained in a state-set */
GFSM_INLINE
gboolean gfsm_stateset_contains(gfsmStateSet *sset, gfsmStateId id);
/** Insert a single state-id into a state-set.
* \returns true iff \a sset already contained \a id
*/
gboolean gfsm_stateset_insert(gfsmStateSet *sset, gfsmStateId id);
/** Assign \a sset1 to be the union of itself with \a sset2 */
gfsmStateSet *gfsm_stateset_union(gfsmStateSet *sset1, gfsmStateSet *sset2);
/** Remove a state-id from a state-set
* \returns true iff \a sset contained \a id
*/
gboolean gfsm_stateset_remove(gfsmStateSet *sset, gfsmStateId id);
/** Equality test */
gboolean gfsm_stateset_equal(gfsmStateSet *sset1, gfsmStateSet *sset2);
//@}
/*======================================================================
* Methods: Iteration
*/
///\name Iteration
//@{
/// state-set iterator type
typedef gfsmStateId* gfsmStateSetIter;
/** Iterator access: get current state-id, or gfsmNoState if none defined */
#define gfsm_stateset_iter_id(sseti) \
((sseti) ? *(sseti) : gfsmNoState)
/** Check validity of a state-set iterator */
#define gfsm_stateset_iter_ok(sseti) \
((sseti)!=NULL)
/** Get first state in the state-set.
* \returns iterator (value) pointing to the first state in the
* state-set.
*/
#define gfsm_stateset_iter_begin(sset) \
((gfsmStateId*)((sset)->data))
/** Increment a state-set iterator one position. */
#define gfsm_stateset_iter_next(sset,sseti) \
((++(sseti)) < (((gfsmStateId*)((sset)->data))+((sset)->len)) \
? (sseti) \
: NULL)
/** Find an iterator pointing to the element for \a id in \a sset,
* or a bad iterator if no such element exists */
gfsmStateSetIter gfsm_stateset_find(gfsmStateSet *sset, gfsmStateId id);
//@}
/*======================================================================
* Methods: Utiltiies
*/
///\name Utilities
//@{
/// typedef for iteration functions: return TRUE to stop iteration
typedef gboolean (*gfsmStateSetForeachFunc) (gfsmStateId id, gpointer data);
/** General iteration utilitiy for state-sets */
void gfsm_stateset_foreach(gfsmStateSet *sset, gfsmStateSetForeachFunc func, gpointer data);
/** Hashing function for state-sets */
guint gfsm_stateset_hash(gfsmStateSet *sset);
//@}
/*======================================================================
* Methods: Automaton
*/
///\name Methods: Automaton access
//@{
/** Populate a state-set representing targets of arcs with
* lower label \a lo and upper label \a hi leaving state with id \a id
* in automaton \a fsm.
*
* If either \a lo or \a hi is gfsmNoLabel, the corresponding labels
* will be ignored.
*
* Note that this method does not clear \a sset.
*/
void gfsm_stateset_populate(gfsmStateSet *sset,
gfsmAutomaton *fsm,
gfsmStateId id,
gfsmLabelVal lo,
gfsmLabelVal hi);
/** Convenience macro to populate a state-set from I/O-epsilon arcs */
#define gfsm_stateset_populate_eps(sset,fsm,id) \
gfsm_stateset_populate((sset),(fsm),(id),gfsmEpsilon,gfsmEpsilon)
/** Returns true iff some \a id in \a sset is a final state in \a fsm */
gboolean gfsm_stateset_has_final_state(gfsmStateSet *sset, gfsmAutomaton *fsm);
/** Lookup sum of final weights in \a fsm of states \a id in \a sset
* Returns TRUE iff at least one state in \a sset is final, and
* sets \a *wp to the sum of final weights.
*/
gboolean gfsm_stateset_lookup_final_weight(gfsmStateSet *sset, gfsmAutomaton *fsm, gfsmWeight *wp);
//@}
//-- inline definitions
#ifdef GFSM_INLINE_ENABLED
# include <gfsmStateSet.hi>
#endif
#endif /* _GFSM_STATESET_H */
|
