aboutsummaryrefslogtreecommitdiff
path: root/src/test
diff options
context:
space:
mode:
Diffstat (limited to 'src/test')
-rw-r--r--src/test/Makefile.am12
-rw-r--r--src/test/Makefile.in608
-rw-r--r--src/test/algo_test.cc155
-rw-r--r--src/test/algo_test.h1315
-rw-r--r--src/test/fst_test.cc228
-rw-r--r--src/test/fst_test.h299
-rw-r--r--src/test/weight-tester.h225
-rw-r--r--src/test/weight_test.cc258
8 files changed, 3100 insertions, 0 deletions
diff --git a/src/test/Makefile.am b/src/test/Makefile.am
new file mode 100644
index 0000000..1456436
--- /dev/null
+++ b/src/test/Makefile.am
@@ -0,0 +1,12 @@
+AM_CPPFLAGS = -I$(srcdir)/../include $(ICU_CPPFLAGS)
+LDADD = ../lib/libfst.la -lm -ldl
+
+check_PROGRAMS = fst_test weight_test algo_test
+
+fst_test_SOURCES = fst_test.cc fst_test.h
+
+weight_test_SOURCES = weight_test.cc weight-tester.h
+
+algo_test_SOURCES = algo_test.cc algo_test.h
+
+TESTS = fst_test weight_test algo_test
diff --git a/src/test/Makefile.in b/src/test/Makefile.in
new file mode 100644
index 0000000..00fe859
--- /dev/null
+++ b/src/test/Makefile.in
@@ -0,0 +1,608 @@
+# Makefile.in generated by automake 1.11.1 from Makefile.am.
+# @configure_input@
+
+# Copyright (C) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002,
+# 2003, 2004, 2005, 2006, 2007, 2008, 2009 Free Software Foundation,
+# Inc.
+# This Makefile.in is free software; the Free Software Foundation
+# gives unlimited permission to copy and/or distribute it,
+# with or without modifications, as long as this notice is preserved.
+
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY, to the extent permitted by law; without
+# even the implied warranty of MERCHANTABILITY or FITNESS FOR A
+# PARTICULAR PURPOSE.
+
+@SET_MAKE@
+VPATH = @srcdir@
+pkgdatadir = $(datadir)/@PACKAGE@
+pkgincludedir = $(includedir)/@PACKAGE@
+pkglibdir = $(libdir)/@PACKAGE@
+pkglibexecdir = $(libexecdir)/@PACKAGE@
+am__cd = CDPATH="$${ZSH_VERSION+.}$(PATH_SEPARATOR)" && cd
+install_sh_DATA = $(install_sh) -c -m 644
+install_sh_PROGRAM = $(install_sh) -c
+install_sh_SCRIPT = $(install_sh) -c
+INSTALL_HEADER = $(INSTALL_DATA)
+transform = $(program_transform_name)
+NORMAL_INSTALL = :
+PRE_INSTALL = :
+POST_INSTALL = :
+NORMAL_UNINSTALL = :
+PRE_UNINSTALL = :
+POST_UNINSTALL = :
+build_triplet = @build@
+host_triplet = @host@
+check_PROGRAMS = fst_test$(EXEEXT) weight_test$(EXEEXT) \
+ algo_test$(EXEEXT)
+TESTS = fst_test$(EXEEXT) weight_test$(EXEEXT) algo_test$(EXEEXT)
+subdir = src/test
+DIST_COMMON = $(srcdir)/Makefile.am $(srcdir)/Makefile.in
+ACLOCAL_M4 = $(top_srcdir)/aclocal.m4
+am__aclocal_m4_deps = $(top_srcdir)/m4/ax_check_icu.m4 \
+ $(top_srcdir)/m4/libtool.m4 $(top_srcdir)/m4/ltoptions.m4 \
+ $(top_srcdir)/m4/ltsugar.m4 $(top_srcdir)/m4/ltversion.m4 \
+ $(top_srcdir)/m4/lt~obsolete.m4 $(top_srcdir)/configure.ac
+am__configure_deps = $(am__aclocal_m4_deps) $(CONFIGURE_DEPENDENCIES) \
+ $(ACLOCAL_M4)
+mkinstalldirs = $(install_sh) -d
+CONFIG_HEADER = $(top_builddir)/config.h \
+ $(top_builddir)/src/include/fst/config.h
+CONFIG_CLEAN_FILES =
+CONFIG_CLEAN_VPATH_FILES =
+am_algo_test_OBJECTS = algo_test.$(OBJEXT)
+algo_test_OBJECTS = $(am_algo_test_OBJECTS)
+algo_test_LDADD = $(LDADD)
+algo_test_DEPENDENCIES = ../lib/libfst.la
+am_fst_test_OBJECTS = fst_test.$(OBJEXT)
+fst_test_OBJECTS = $(am_fst_test_OBJECTS)
+fst_test_LDADD = $(LDADD)
+fst_test_DEPENDENCIES = ../lib/libfst.la
+am_weight_test_OBJECTS = weight_test.$(OBJEXT)
+weight_test_OBJECTS = $(am_weight_test_OBJECTS)
+weight_test_LDADD = $(LDADD)
+weight_test_DEPENDENCIES = ../lib/libfst.la
+DEFAULT_INCLUDES =
+depcomp = $(SHELL) $(top_srcdir)/depcomp
+am__depfiles_maybe = depfiles
+am__mv = mv -f
+CXXCOMPILE = $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) \
+ $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS)
+LTCXXCOMPILE = $(LIBTOOL) --tag=CXX $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) \
+ --mode=compile $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) \
+ $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS)
+CXXLD = $(CXX)
+CXXLINK = $(LIBTOOL) --tag=CXX $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) \
+ --mode=link $(CXXLD) $(AM_CXXFLAGS) $(CXXFLAGS) $(AM_LDFLAGS) \
+ $(LDFLAGS) -o $@
+COMPILE = $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) \
+ $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS)
+LTCOMPILE = $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) \
+ --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) \
+ $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS)
+CCLD = $(CC)
+LINK = $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) \
+ --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) \
+ $(LDFLAGS) -o $@
+SOURCES = $(algo_test_SOURCES) $(fst_test_SOURCES) \
+ $(weight_test_SOURCES)
+DIST_SOURCES = $(algo_test_SOURCES) $(fst_test_SOURCES) \
+ $(weight_test_SOURCES)
+ETAGS = etags
+CTAGS = ctags
+am__tty_colors = \
+red=; grn=; lgn=; blu=; std=
+DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST)
+ACLOCAL = @ACLOCAL@
+AMTAR = @AMTAR@
+AR = @AR@
+AUTOCONF = @AUTOCONF@
+AUTOHEADER = @AUTOHEADER@
+AUTOMAKE = @AUTOMAKE@
+AWK = @AWK@
+CC = @CC@
+CCDEPMODE = @CCDEPMODE@
+CFLAGS = @CFLAGS@
+CPP = @CPP@
+CPPFLAGS = @CPPFLAGS@
+CXX = @CXX@
+CXXCPP = @CXXCPP@
+CXXDEPMODE = @CXXDEPMODE@
+CXXFLAGS = @CXXFLAGS@
+CYGPATH_W = @CYGPATH_W@
+DEFS = @DEFS@
+DEPDIR = @DEPDIR@
+DSYMUTIL = @DSYMUTIL@
+DUMPBIN = @DUMPBIN@
+ECHO_C = @ECHO_C@
+ECHO_N = @ECHO_N@
+ECHO_T = @ECHO_T@
+EGREP = @EGREP@
+EXEEXT = @EXEEXT@
+FGREP = @FGREP@
+GREP = @GREP@
+ICU_CFLAGS = @ICU_CFLAGS@
+ICU_CONFIG = @ICU_CONFIG@
+ICU_CPPFLAGS = @ICU_CPPFLAGS@
+ICU_CXXFLAGS = @ICU_CXXFLAGS@
+ICU_LIBS = @ICU_LIBS@
+INSTALL = @INSTALL@
+INSTALL_DATA = @INSTALL_DATA@
+INSTALL_PROGRAM = @INSTALL_PROGRAM@
+INSTALL_SCRIPT = @INSTALL_SCRIPT@
+INSTALL_STRIP_PROGRAM = @INSTALL_STRIP_PROGRAM@
+LD = @LD@
+LDFLAGS = @LDFLAGS@
+LIBOBJS = @LIBOBJS@
+LIBS = @LIBS@
+LIBTOOL = @LIBTOOL@
+LIPO = @LIPO@
+LN_S = @LN_S@
+LTLIBOBJS = @LTLIBOBJS@
+MAKEINFO = @MAKEINFO@
+MKDIR_P = @MKDIR_P@
+NM = @NM@
+NMEDIT = @NMEDIT@
+OBJDUMP = @OBJDUMP@
+OBJEXT = @OBJEXT@
+OTOOL = @OTOOL@
+OTOOL64 = @OTOOL64@
+PACKAGE = @PACKAGE@
+PACKAGE_BUGREPORT = @PACKAGE_BUGREPORT@
+PACKAGE_NAME = @PACKAGE_NAME@
+PACKAGE_STRING = @PACKAGE_STRING@
+PACKAGE_TARNAME = @PACKAGE_TARNAME@
+PACKAGE_URL = @PACKAGE_URL@
+PACKAGE_VERSION = @PACKAGE_VERSION@
+PATH_SEPARATOR = @PATH_SEPARATOR@
+RANLIB = @RANLIB@
+SED = @SED@
+SET_MAKE = @SET_MAKE@
+SHELL = @SHELL@
+STRIP = @STRIP@
+VERSION = @VERSION@
+abs_builddir = @abs_builddir@
+abs_srcdir = @abs_srcdir@
+abs_top_builddir = @abs_top_builddir@
+abs_top_srcdir = @abs_top_srcdir@
+ac_ct_CC = @ac_ct_CC@
+ac_ct_CXX = @ac_ct_CXX@
+ac_ct_DUMPBIN = @ac_ct_DUMPBIN@
+am__include = @am__include@
+am__leading_dot = @am__leading_dot@
+am__quote = @am__quote@
+am__tar = @am__tar@
+am__untar = @am__untar@
+bindir = @bindir@
+build = @build@
+build_alias = @build_alias@
+build_cpu = @build_cpu@
+build_os = @build_os@
+build_vendor = @build_vendor@
+builddir = @builddir@
+datadir = @datadir@
+datarootdir = @datarootdir@
+docdir = @docdir@
+dvidir = @dvidir@
+exec_prefix = @exec_prefix@
+host = @host@
+host_alias = @host_alias@
+host_cpu = @host_cpu@
+host_os = @host_os@
+host_vendor = @host_vendor@
+htmldir = @htmldir@
+includedir = @includedir@
+infodir = @infodir@
+install_sh = @install_sh@
+libdir = @libdir@
+libexecdir = @libexecdir@
+libfstdir = @libfstdir@
+localedir = @localedir@
+localstatedir = @localstatedir@
+lt_ECHO = @lt_ECHO@
+mandir = @mandir@
+mkdir_p = @mkdir_p@
+oldincludedir = @oldincludedir@
+pdfdir = @pdfdir@
+prefix = @prefix@
+program_transform_name = @program_transform_name@
+psdir = @psdir@
+sbindir = @sbindir@
+sharedstatedir = @sharedstatedir@
+srcdir = @srcdir@
+sysconfdir = @sysconfdir@
+target_alias = @target_alias@
+top_build_prefix = @top_build_prefix@
+top_builddir = @top_builddir@
+top_srcdir = @top_srcdir@
+AM_CPPFLAGS = -I$(srcdir)/../include $(ICU_CPPFLAGS)
+LDADD = ../lib/libfst.la -lm -ldl
+fst_test_SOURCES = fst_test.cc fst_test.h
+weight_test_SOURCES = weight_test.cc weight-tester.h
+algo_test_SOURCES = algo_test.cc algo_test.h
+all: all-am
+
+.SUFFIXES:
+.SUFFIXES: .cc .lo .o .obj
+$(srcdir)/Makefile.in: $(srcdir)/Makefile.am $(am__configure_deps)
+ @for dep in $?; do \
+ case '$(am__configure_deps)' in \
+ *$$dep*) \
+ ( cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh ) \
+ && { if test -f $@; then exit 0; else break; fi; }; \
+ exit 1;; \
+ esac; \
+ done; \
+ echo ' cd $(top_srcdir) && $(AUTOMAKE) --foreign src/test/Makefile'; \
+ $(am__cd) $(top_srcdir) && \
+ $(AUTOMAKE) --foreign src/test/Makefile
+.PRECIOUS: Makefile
+Makefile: $(srcdir)/Makefile.in $(top_builddir)/config.status
+ @case '$?' in \
+ *config.status*) \
+ cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh;; \
+ *) \
+ echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe)'; \
+ cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe);; \
+ esac;
+
+$(top_builddir)/config.status: $(top_srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES)
+ cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh
+
+$(top_srcdir)/configure: $(am__configure_deps)
+ cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh
+$(ACLOCAL_M4): $(am__aclocal_m4_deps)
+ cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh
+$(am__aclocal_m4_deps):
+
+clean-checkPROGRAMS:
+ @list='$(check_PROGRAMS)'; test -n "$$list" || exit 0; \
+ echo " rm -f" $$list; \
+ rm -f $$list || exit $$?; \
+ test -n "$(EXEEXT)" || exit 0; \
+ list=`for p in $$list; do echo "$$p"; done | sed 's/$(EXEEXT)$$//'`; \
+ echo " rm -f" $$list; \
+ rm -f $$list
+algo_test$(EXEEXT): $(algo_test_OBJECTS) $(algo_test_DEPENDENCIES)
+ @rm -f algo_test$(EXEEXT)
+ $(CXXLINK) $(algo_test_OBJECTS) $(algo_test_LDADD) $(LIBS)
+fst_test$(EXEEXT): $(fst_test_OBJECTS) $(fst_test_DEPENDENCIES)
+ @rm -f fst_test$(EXEEXT)
+ $(CXXLINK) $(fst_test_OBJECTS) $(fst_test_LDADD) $(LIBS)
+weight_test$(EXEEXT): $(weight_test_OBJECTS) $(weight_test_DEPENDENCIES)
+ @rm -f weight_test$(EXEEXT)
+ $(CXXLINK) $(weight_test_OBJECTS) $(weight_test_LDADD) $(LIBS)
+
+mostlyclean-compile:
+ -rm -f *.$(OBJEXT)
+
+distclean-compile:
+ -rm -f *.tab.c
+
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/algo_test.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/fst_test.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/weight_test.Po@am__quote@
+
+.cc.o:
+@am__fastdepCXX_TRUE@ $(CXXCOMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $<
+@am__fastdepCXX_TRUE@ $(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Po
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@ source='$<' object='$@' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCXX_FALSE@ $(CXXCOMPILE) -c -o $@ $<
+
+.cc.obj:
+@am__fastdepCXX_TRUE@ $(CXXCOMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ `$(CYGPATH_W) '$<'`
+@am__fastdepCXX_TRUE@ $(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Po
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@ source='$<' object='$@' libtool=no @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCXX_FALSE@ $(CXXCOMPILE) -c -o $@ `$(CYGPATH_W) '$<'`
+
+.cc.lo:
+@am__fastdepCXX_TRUE@ $(LTCXXCOMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $<
+@am__fastdepCXX_TRUE@ $(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Plo
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@ source='$<' object='$@' libtool=yes @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCXX_FALSE@ $(LTCXXCOMPILE) -c -o $@ $<
+
+mostlyclean-libtool:
+ -rm -f *.lo
+
+clean-libtool:
+ -rm -rf .libs _libs
+
+ID: $(HEADERS) $(SOURCES) $(LISP) $(TAGS_FILES)
+ list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \
+ unique=`for i in $$list; do \
+ if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \
+ done | \
+ $(AWK) '{ files[$$0] = 1; nonempty = 1; } \
+ END { if (nonempty) { for (i in files) print i; }; }'`; \
+ mkid -fID $$unique
+tags: TAGS
+
+TAGS: $(HEADERS) $(SOURCES) $(TAGS_DEPENDENCIES) \
+ $(TAGS_FILES) $(LISP)
+ set x; \
+ here=`pwd`; \
+ list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \
+ unique=`for i in $$list; do \
+ if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \
+ done | \
+ $(AWK) '{ files[$$0] = 1; nonempty = 1; } \
+ END { if (nonempty) { for (i in files) print i; }; }'`; \
+ shift; \
+ if test -z "$(ETAGS_ARGS)$$*$$unique"; then :; else \
+ test -n "$$unique" || unique=$$empty_fix; \
+ if test $$# -gt 0; then \
+ $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \
+ "$$@" $$unique; \
+ else \
+ $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \
+ $$unique; \
+ fi; \
+ fi
+ctags: CTAGS
+CTAGS: $(HEADERS) $(SOURCES) $(TAGS_DEPENDENCIES) \
+ $(TAGS_FILES) $(LISP)
+ list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \
+ unique=`for i in $$list; do \
+ if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \
+ done | \
+ $(AWK) '{ files[$$0] = 1; nonempty = 1; } \
+ END { if (nonempty) { for (i in files) print i; }; }'`; \
+ test -z "$(CTAGS_ARGS)$$unique" \
+ || $(CTAGS) $(CTAGSFLAGS) $(AM_CTAGSFLAGS) $(CTAGS_ARGS) \
+ $$unique
+
+GTAGS:
+ here=`$(am__cd) $(top_builddir) && pwd` \
+ && $(am__cd) $(top_srcdir) \
+ && gtags -i $(GTAGS_ARGS) "$$here"
+
+distclean-tags:
+ -rm -f TAGS ID GTAGS GRTAGS GSYMS GPATH tags
+
+check-TESTS: $(TESTS)
+ @failed=0; all=0; xfail=0; xpass=0; skip=0; \
+ srcdir=$(srcdir); export srcdir; \
+ list=' $(TESTS) '; \
+ $(am__tty_colors); \
+ if test -n "$$list"; then \
+ for tst in $$list; do \
+ if test -f ./$$tst; then dir=./; \
+ elif test -f $$tst; then dir=; \
+ else dir="$(srcdir)/"; fi; \
+ if $(TESTS_ENVIRONMENT) $${dir}$$tst; then \
+ all=`expr $$all + 1`; \
+ case " $(XFAIL_TESTS) " in \
+ *[\ \ ]$$tst[\ \ ]*) \
+ xpass=`expr $$xpass + 1`; \
+ failed=`expr $$failed + 1`; \
+ col=$$red; res=XPASS; \
+ ;; \
+ *) \
+ col=$$grn; res=PASS; \
+ ;; \
+ esac; \
+ elif test $$? -ne 77; then \
+ all=`expr $$all + 1`; \
+ case " $(XFAIL_TESTS) " in \
+ *[\ \ ]$$tst[\ \ ]*) \
+ xfail=`expr $$xfail + 1`; \
+ col=$$lgn; res=XFAIL; \
+ ;; \
+ *) \
+ failed=`expr $$failed + 1`; \
+ col=$$red; res=FAIL; \
+ ;; \
+ esac; \
+ else \
+ skip=`expr $$skip + 1`; \
+ col=$$blu; res=SKIP; \
+ fi; \
+ echo "$${col}$$res$${std}: $$tst"; \
+ done; \
+ if test "$$all" -eq 1; then \
+ tests="test"; \
+ All=""; \
+ else \
+ tests="tests"; \
+ All="All "; \
+ fi; \
+ if test "$$failed" -eq 0; then \
+ if test "$$xfail" -eq 0; then \
+ banner="$$All$$all $$tests passed"; \
+ else \
+ if test "$$xfail" -eq 1; then failures=failure; else failures=failures; fi; \
+ banner="$$All$$all $$tests behaved as expected ($$xfail expected $$failures)"; \
+ fi; \
+ else \
+ if test "$$xpass" -eq 0; then \
+ banner="$$failed of $$all $$tests failed"; \
+ else \
+ if test "$$xpass" -eq 1; then passes=pass; else passes=passes; fi; \
+ banner="$$failed of $$all $$tests did not behave as expected ($$xpass unexpected $$passes)"; \
+ fi; \
+ fi; \
+ dashes="$$banner"; \
+ skipped=""; \
+ if test "$$skip" -ne 0; then \
+ if test "$$skip" -eq 1; then \
+ skipped="($$skip test was not run)"; \
+ else \
+ skipped="($$skip tests were not run)"; \
+ fi; \
+ test `echo "$$skipped" | wc -c` -le `echo "$$banner" | wc -c` || \
+ dashes="$$skipped"; \
+ fi; \
+ report=""; \
+ if test "$$failed" -ne 0 && test -n "$(PACKAGE_BUGREPORT)"; then \
+ report="Please report to $(PACKAGE_BUGREPORT)"; \
+ test `echo "$$report" | wc -c` -le `echo "$$banner" | wc -c` || \
+ dashes="$$report"; \
+ fi; \
+ dashes=`echo "$$dashes" | sed s/./=/g`; \
+ if test "$$failed" -eq 0; then \
+ echo "$$grn$$dashes"; \
+ else \
+ echo "$$red$$dashes"; \
+ fi; \
+ echo "$$banner"; \
+ test -z "$$skipped" || echo "$$skipped"; \
+ test -z "$$report" || echo "$$report"; \
+ echo "$$dashes$$std"; \
+ test "$$failed" -eq 0; \
+ else :; fi
+
+distdir: $(DISTFILES)
+ @srcdirstrip=`echo "$(srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \
+ topsrcdirstrip=`echo "$(top_srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \
+ list='$(DISTFILES)'; \
+ dist_files=`for file in $$list; do echo $$file; done | \
+ sed -e "s|^$$srcdirstrip/||;t" \
+ -e "s|^$$topsrcdirstrip/|$(top_builddir)/|;t"`; \
+ case $$dist_files in \
+ */*) $(MKDIR_P) `echo "$$dist_files" | \
+ sed '/\//!d;s|^|$(distdir)/|;s,/[^/]*$$,,' | \
+ sort -u` ;; \
+ esac; \
+ for file in $$dist_files; do \
+ if test -f $$file || test -d $$file; then d=.; else d=$(srcdir); fi; \
+ if test -d $$d/$$file; then \
+ dir=`echo "/$$file" | sed -e 's,/[^/]*$$,,'`; \
+ if test -d "$(distdir)/$$file"; then \
+ find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \
+ fi; \
+ if test -d $(srcdir)/$$file && test $$d != $(srcdir); then \
+ cp -fpR $(srcdir)/$$file "$(distdir)$$dir" || exit 1; \
+ find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \
+ fi; \
+ cp -fpR $$d/$$file "$(distdir)$$dir" || exit 1; \
+ else \
+ test -f "$(distdir)/$$file" \
+ || cp -p $$d/$$file "$(distdir)/$$file" \
+ || exit 1; \
+ fi; \
+ done
+check-am: all-am
+ $(MAKE) $(AM_MAKEFLAGS) $(check_PROGRAMS)
+ $(MAKE) $(AM_MAKEFLAGS) check-TESTS
+check: check-am
+all-am: Makefile
+installdirs:
+install: install-am
+install-exec: install-exec-am
+install-data: install-data-am
+uninstall: uninstall-am
+
+install-am: all-am
+ @$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am
+
+installcheck: installcheck-am
+install-strip:
+ $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \
+ install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \
+ `test -z '$(STRIP)' || \
+ echo "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'"` install
+mostlyclean-generic:
+
+clean-generic:
+
+distclean-generic:
+ -test -z "$(CONFIG_CLEAN_FILES)" || rm -f $(CONFIG_CLEAN_FILES)
+ -test . = "$(srcdir)" || test -z "$(CONFIG_CLEAN_VPATH_FILES)" || rm -f $(CONFIG_CLEAN_VPATH_FILES)
+
+maintainer-clean-generic:
+ @echo "This command is intended for maintainers to use"
+ @echo "it deletes files that may require special tools to rebuild."
+clean: clean-am
+
+clean-am: clean-checkPROGRAMS clean-generic clean-libtool \
+ mostlyclean-am
+
+distclean: distclean-am
+ -rm -rf ./$(DEPDIR)
+ -rm -f Makefile
+distclean-am: clean-am distclean-compile distclean-generic \
+ distclean-tags
+
+dvi: dvi-am
+
+dvi-am:
+
+html: html-am
+
+html-am:
+
+info: info-am
+
+info-am:
+
+install-data-am:
+
+install-dvi: install-dvi-am
+
+install-dvi-am:
+
+install-exec-am:
+
+install-html: install-html-am
+
+install-html-am:
+
+install-info: install-info-am
+
+install-info-am:
+
+install-man:
+
+install-pdf: install-pdf-am
+
+install-pdf-am:
+
+install-ps: install-ps-am
+
+install-ps-am:
+
+installcheck-am:
+
+maintainer-clean: maintainer-clean-am
+ -rm -rf ./$(DEPDIR)
+ -rm -f Makefile
+maintainer-clean-am: distclean-am maintainer-clean-generic
+
+mostlyclean: mostlyclean-am
+
+mostlyclean-am: mostlyclean-compile mostlyclean-generic \
+ mostlyclean-libtool
+
+pdf: pdf-am
+
+pdf-am:
+
+ps: ps-am
+
+ps-am:
+
+uninstall-am:
+
+.MAKE: check-am install-am install-strip
+
+.PHONY: CTAGS GTAGS all all-am check check-TESTS check-am clean \
+ clean-checkPROGRAMS clean-generic clean-libtool ctags \
+ distclean distclean-compile distclean-generic \
+ distclean-libtool distclean-tags distdir dvi dvi-am html \
+ html-am info info-am install install-am install-data \
+ install-data-am install-dvi install-dvi-am install-exec \
+ install-exec-am install-html install-html-am install-info \
+ install-info-am install-man install-pdf install-pdf-am \
+ install-ps install-ps-am install-strip installcheck \
+ installcheck-am installdirs maintainer-clean \
+ maintainer-clean-generic mostlyclean mostlyclean-compile \
+ mostlyclean-generic mostlyclean-libtool pdf pdf-am ps ps-am \
+ tags uninstall uninstall-am
+
+
+# Tell versions [3.59,3.63) of GNU make to not export all variables.
+# Otherwise a system limit (for SysV at least) may be exceeded.
+.NOEXPORT:
diff --git a/src/test/algo_test.cc b/src/test/algo_test.cc
new file mode 100644
index 0000000..9538d54
--- /dev/null
+++ b/src/test/algo_test.cc
@@ -0,0 +1,155 @@
+// algo_test.h
+
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Copyright 2005-2010 Google, Inc.
+// Author: riley@google.com (Michael Riley)
+//
+// \file
+// Regression test for various FST algorithms.
+
+#include "./algo_test.h"
+
+// These determine which semirings are tested. Defining at least
+// TEST_TROPICAL and TEST_LOG is recommended. More increase the
+// comprehensiveness, but also increase the compilation time.
+
+#define TEST_TROPICAL
+#define TEST_LOG
+// #define TEST_MINMAX
+// #define TEST_LEFT_STRING
+// #define TEST_RIGHT_STRING
+// #define TEST_GALLIC
+// #define TEST_LEXICOGRAPHIC
+// #define TEST_POWER
+
+DEFINE_int32(seed, -1, "random seed");
+DEFINE_int32(repeat, 25, "number of test repetitions");
+
+using fst::StdArc;
+using fst::TropicalWeightGenerator;
+
+using fst::LogArc;
+using fst::LogWeightGenerator;
+
+using fst::MinMaxArc;
+using fst::MinMaxWeightGenerator;
+
+using fst::StringArc;
+using fst::StringWeightGenerator;
+using fst::STRING_LEFT;
+using fst::STRING_RIGHT;
+
+using fst::GallicArc;
+using fst::GallicWeightGenerator;
+
+using fst::LexicographicArc;
+using fst::TropicalWeight;
+using fst::LexicographicWeightGenerator;
+
+using fst::ArcTpl;
+using fst::PowerWeight;
+using fst::PowerWeightGenerator;
+
+using fst::AlgoTester;
+
+int main(int argc, char **argv) {
+ FLAGS_fst_verify_properties = true;
+ std::set_new_handler(FailedNewHandler);
+ SetFlags(argv[0], &argc, &argv, true);
+
+ static const int kCacheGcLimit = 20;
+
+ int seed = FLAGS_seed >= 0 ? FLAGS_seed : time(0);
+ srand(seed);
+ LOG(INFO) << "Seed = " << seed;
+
+ FLAGS_fst_default_cache_gc = rand() % 2;
+ FLAGS_fst_default_cache_gc_limit = rand() % kCacheGcLimit;
+ VLOG(1) << "default_cache_gc:" << FLAGS_fst_default_cache_gc;
+ VLOG(1) << "default_cache_gc_limit:" << FLAGS_fst_default_cache_gc_limit;
+
+#ifdef TEST_TROPICAL
+ TropicalWeightGenerator tropical_generator(seed, false);
+ AlgoTester<StdArc, TropicalWeightGenerator>
+ tropical_tester(tropical_generator, seed);
+ tropical_tester.Test();
+#endif // TEST_TROPICAL
+
+#ifdef TEST_LOG
+ LogWeightGenerator log_generator(seed, false);
+ AlgoTester<LogArc, LogWeightGenerator>
+ log_tester(log_generator, seed);
+ log_tester.Test();
+#endif // TEST_LOG
+
+#ifdef TEST_MINMAX
+ MinMaxWeightGenerator minmax_generator(seed, false);
+ AlgoTester<MinMaxArc, MinMaxWeightGenerator>
+ minmax_tester(minmax_generator, seed);
+ minmax_tester.Test();
+#endif
+
+#ifdef TEST_LEFT_STRING
+ StringWeightGenerator<int> left_string_generator(seed, false);
+ AlgoTester<StringArc<>, StringWeightGenerator<int> >
+ left_string_tester(left_string_generator, seed);
+ left_string_tester.Test();
+#endif // TEST_LEFT_STRING
+
+#ifdef TEST_RIGHT_STRING
+ StringWeightGenerator<int, STRING_RIGHT> right_string_generator(seed, false);
+ AlgoTester<StringArc<STRING_RIGHT>,
+ StringWeightGenerator<int, STRING_RIGHT> >
+ right_string_tester(right_string_generator, seed);
+ right_string_tester.Test();
+#endif // TEST_RIGHT_STRING
+
+#ifdef TEST_GALLIC
+ typedef GallicArc<StdArc> StdGallicArc;
+ typedef GallicWeightGenerator<int, TropicalWeightGenerator>
+ TropicalGallicWeightGenerator;
+
+ TropicalGallicWeightGenerator tropical_gallic_generator(seed, false);
+ AlgoTester<StdGallicArc, TropicalGallicWeightGenerator>
+ gallic_tester(tropical_gallic_generator, seed);
+ gallic_tester.Test();
+#endif // TEST_GALLIC
+
+#ifdef TEST_LEXICOGRAPHIC
+ typedef LexicographicArc<TropicalWeight, TropicalWeight>
+ TropicalLexicographicArc;
+ typedef LexicographicWeightGenerator<TropicalWeightGenerator,
+ TropicalWeightGenerator> TropicalLexicographicWeightGenerator;
+ TropicalLexicographicWeightGenerator lexicographic_generator(seed, false);
+ AlgoTester<TropicalLexicographicArc, TropicalLexicographicWeightGenerator>
+ lexicographic_tester(lexicographic_generator, seed);
+ lexicographic_tester.Test();
+#endif // TEST_LEXICOGRAPHIC
+
+#ifdef TEST_POWER
+ typedef PowerWeight<TropicalWeight, 3> TropicalCubeWeight;
+ typedef ArcTpl<TropicalCubeWeight> TropicalCubeArc;
+ typedef PowerWeightGenerator<TropicalWeightGenerator, 3>
+ TropicalCubeWeightGenerator;
+
+ TropicalCubeWeightGenerator tropical_cube_generator(seed, false);
+ AlgoTester<TropicalCubeArc, TropicalCubeWeightGenerator>
+ tropical_cube_tester(tropical_cube_generator, seed);
+ tropical_cube_tester.Test();
+#endif // TEST_POWER
+
+ cout << "PASS" << endl;
+
+ return 0;
+}
diff --git a/src/test/algo_test.h b/src/test/algo_test.h
new file mode 100644
index 0000000..3aca3cc
--- /dev/null
+++ b/src/test/algo_test.h
@@ -0,0 +1,1315 @@
+// algo_test.h
+
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Copyright 2005-2010 Google, Inc.
+// Author: riley@google.com (Michael Riley)
+//
+// \file
+// Regression test for various FST algorithms.
+
+#ifndef FST_TEST_ALGO_TEST_H__
+#define FST_TEST_ALGO_TEST_H__
+
+#include <fst/fstlib.h>
+#include <fst/random-weight.h>
+
+DECLARE_int32(repeat); // defined in ./algo_test.cc
+
+namespace fst {
+
+// Mapper to change input and output label of every transition into
+// epsilons.
+template <class A>
+class EpsMapper {
+ public:
+ EpsMapper() {}
+
+ A operator()(const A &arc) const {
+ return A(0, 0, arc.weight, arc.nextstate);
+ }
+
+ uint64 Properties(uint64 props) const {
+ props &= ~kNotAcceptor;
+ props |= kAcceptor;
+ props &= ~kNoIEpsilons & ~kNoOEpsilons & ~kNoEpsilons;
+ props |= kIEpsilons | kOEpsilons | kEpsilons;
+ props &= ~kNotILabelSorted & ~kNotOLabelSorted;
+ props |= kILabelSorted | kOLabelSorted;
+ return props;
+ }
+
+ MapFinalAction FinalAction() const { return MAP_NO_SUPERFINAL; }
+
+
+ MapSymbolsAction InputSymbolsAction() const { return MAP_COPY_SYMBOLS;}
+
+ MapSymbolsAction OutputSymbolsAction() const { return MAP_COPY_SYMBOLS;}
+};
+
+// This class tests a variety of identities and properties that must
+// hold for various algorithms on weighted FSTs.
+template <class Arc, class WeightGenerator>
+class WeightedTester {
+ public:
+ typedef typename Arc::Label Label;
+ typedef typename Arc::StateId StateId;
+ typedef typename Arc::Weight Weight;
+
+ WeightedTester(int seed, const Fst<Arc> &zero_fst, const Fst<Arc> &one_fst,
+ const Fst<Arc> &univ_fst, WeightGenerator *weight_generator)
+ : seed_(seed), zero_fst_(zero_fst), one_fst_(one_fst),
+ univ_fst_(univ_fst), weight_generator_(weight_generator) {}
+
+ void Test(const Fst<Arc> &T1, const Fst<Arc> &T2, const Fst<Arc> &T3) {
+ TestRational(T1, T2, T3);
+ TestMap(T1);
+ TestCompose(T1, T2, T3);
+ TestSort(T1);
+ TestOptimize(T1);
+ TestSearch(T1);
+ }
+
+ private:
+ // Tests rational operations with identities
+ void TestRational(const Fst<Arc> &T1, const Fst<Arc> &T2,
+ const Fst<Arc> &T3) {
+
+ {
+ VLOG(1) << "Check destructive and delayed union are equivalent.";
+ VectorFst<Arc> U1(T1);
+ Union(&U1, T2);
+ UnionFst<Arc> U2(T1, T2);
+ CHECK(Equiv(U1, U2));
+ }
+
+
+ {
+ VLOG(1) << "Check destructive and delayed concatenation are equivalent.";
+ VectorFst<Arc> C1(T1);
+ Concat(&C1, T2);
+ ConcatFst<Arc> C2(T1, T2);
+ CHECK(Equiv(C1, C2));
+ VectorFst<Arc> C3(T2);
+ Concat(T1, &C3);
+ CHECK(Equiv(C3, C2));
+ }
+
+ {
+ VLOG(1) << "Check destructive and delayed closure* are equivalent.";
+ VectorFst<Arc> C1(T1);
+ Closure(&C1, CLOSURE_STAR);
+ ClosureFst<Arc> C2(T1, CLOSURE_STAR);
+ CHECK(Equiv(C1, C2));
+ }
+
+ {
+ VLOG(1) << "Check destructive and delayed closure+ are equivalent.";
+ VectorFst<Arc> C1(T1);
+ Closure(&C1, CLOSURE_PLUS);
+ ClosureFst<Arc> C2(T1, CLOSURE_PLUS);
+ CHECK(Equiv(C1, C2));
+ }
+
+ {
+ VLOG(1) << "Check union is associative (destructive).";
+ VectorFst<Arc> U1(T1);
+ Union(&U1, T2);
+ Union(&U1, T3);
+
+ VectorFst<Arc> U3(T2);
+ Union(&U3, T3);
+ VectorFst<Arc> U4(T1);
+ Union(&U4, U3);
+
+ CHECK(Equiv(U1, U4));
+ }
+
+ {
+ VLOG(1) << "Check union is associative (delayed).";
+ UnionFst<Arc> U1(T1, T2);
+ UnionFst<Arc> U2(U1, T3);
+
+ UnionFst<Arc> U3(T2, T3);
+ UnionFst<Arc> U4(T1, U3);
+
+ CHECK(Equiv(U2, U4));
+ }
+
+
+ {
+ VLOG(1) << "Check union is associative (destructive delayed).";
+ UnionFst<Arc> U1(T1, T2);
+ Union(&U1, T3);
+
+ UnionFst<Arc> U3(T2, T3);
+ UnionFst<Arc> U4(T1, U3);
+
+ CHECK(Equiv(U1, U4));
+ }
+
+ {
+ VLOG(1) << "Check concatenation is associative (destructive).";
+ VectorFst<Arc> C1(T1);
+ Concat(&C1, T2);
+ Concat(&C1, T3);
+
+ VectorFst<Arc> C3(T2);
+ Concat(&C3, T3);
+ VectorFst<Arc> C4(T1);
+ Concat(&C4, C3);
+
+ CHECK(Equiv(C1, C4));
+ }
+
+ {
+ VLOG(1) << "Check concatenation is associative (delayed).";
+ ConcatFst<Arc> C1(T1, T2);
+ ConcatFst<Arc> C2(C1, T3);
+
+ ConcatFst<Arc> C3(T2, T3);
+ ConcatFst<Arc> C4(T1, C3);
+
+ CHECK(Equiv(C2, C4));
+ }
+
+ {
+ VLOG(1) << "Check concatenation is associative (destructive delayed).";
+ ConcatFst<Arc> C1(T1, T2);
+ Concat(&C1, T3);
+
+ ConcatFst<Arc> C3(T2, T3);
+ ConcatFst<Arc> C4(T1, C3);
+
+ CHECK(Equiv(C1, C4));
+ }
+
+ if (Weight::Properties() & kLeftSemiring) {
+ VLOG(1) << "Check concatenation left distributes"
+ << " over union (destructive).";
+
+ VectorFst<Arc> U1(T1);
+ Union(&U1, T2);
+ VectorFst<Arc> C1(T3);
+ Concat(&C1, U1);
+
+ VectorFst<Arc> C2(T3);
+ Concat(&C2, T1);
+ VectorFst<Arc> C3(T3);
+ Concat(&C3, T2);
+ VectorFst<Arc> U2(C2);
+ Union(&U2, C3);
+
+ CHECK(Equiv(C1, U2));
+ }
+
+ if (Weight::Properties() & kRightSemiring) {
+ VLOG(1) << "Check concatenation right distributes"
+ << " over union (destructive).";
+ VectorFst<Arc> U1(T1);
+ Union(&U1, T2);
+ VectorFst<Arc> C1(U1);
+ Concat(&C1, T3);
+
+ VectorFst<Arc> C2(T1);
+ Concat(&C2, T3);
+ VectorFst<Arc> C3(T2);
+ Concat(&C3, T3);
+ VectorFst<Arc> U2(C2);
+ Union(&U2, C3);
+
+ CHECK(Equiv(C1, U2));
+ }
+
+ if (Weight::Properties() & kLeftSemiring) {
+ VLOG(1) << "Check concatenation left distributes over union (delayed).";
+ UnionFst<Arc> U1(T1, T2);
+ ConcatFst<Arc> C1(T3, U1);
+
+ ConcatFst<Arc> C2(T3, T1);
+ ConcatFst<Arc> C3(T3, T2);
+ UnionFst<Arc> U2(C2, C3);
+
+ CHECK(Equiv(C1, U2));
+ }
+
+ if (Weight::Properties() & kRightSemiring) {
+ VLOG(1) << "Check concatenation right distributes over union (delayed).";
+ UnionFst<Arc> U1(T1, T2);
+ ConcatFst<Arc> C1(U1, T3);
+
+ ConcatFst<Arc> C2(T1, T3);
+ ConcatFst<Arc> C3(T2, T3);
+ UnionFst<Arc> U2(C2, C3);
+
+ CHECK(Equiv(C1, U2));
+ }
+
+
+ if (Weight::Properties() & kLeftSemiring) {
+ VLOG(1) << "Check T T* == T+ (destructive).";
+ VectorFst<Arc> S(T1);
+ Closure(&S, CLOSURE_STAR);
+ VectorFst<Arc> C(T1);
+ Concat(&C, S);
+
+ VectorFst<Arc> P(T1);
+ Closure(&P, CLOSURE_PLUS);
+
+ CHECK(Equiv(C, P));
+ }
+
+
+ if (Weight::Properties() & kRightSemiring) {
+ VLOG(1) << "Check T* T == T+ (destructive).";
+ VectorFst<Arc> S(T1);
+ Closure(&S, CLOSURE_STAR);
+ VectorFst<Arc> C(S);
+ Concat(&C, T1);
+
+ VectorFst<Arc> P(T1);
+ Closure(&P, CLOSURE_PLUS);
+
+ CHECK(Equiv(C, P));
+ }
+
+ if (Weight::Properties() & kLeftSemiring) {
+ VLOG(1) << "Check T T* == T+ (delayed).";
+ ClosureFst<Arc> S(T1, CLOSURE_STAR);
+ ConcatFst<Arc> C(T1, S);
+
+ ClosureFst<Arc> P(T1, CLOSURE_PLUS);
+
+ CHECK(Equiv(C, P));
+ }
+
+ if (Weight::Properties() & kRightSemiring) {
+ VLOG(1) << "Check T* T == T+ (delayed).";
+ ClosureFst<Arc> S(T1, CLOSURE_STAR);
+ ConcatFst<Arc> C(S, T1);
+
+ ClosureFst<Arc> P(T1, CLOSURE_PLUS);
+
+ CHECK(Equiv(C, P));
+ }
+ }
+
+ // Tests map-based operations.
+ void TestMap(const Fst<Arc> &T) {
+
+ {
+ VLOG(1) << "Check destructive and delayed projection are equivalent.";
+ VectorFst<Arc> P1(T);
+ Project(&P1, PROJECT_INPUT);
+ ProjectFst<Arc> P2(T, PROJECT_INPUT);
+ CHECK(Equiv(P1, P2));
+ }
+
+
+ {
+ VLOG(1) << "Check destructive and delayed inversion are equivalent.";
+ VectorFst<Arc> I1(T);
+ Invert(&I1);
+ InvertFst<Arc> I2(T);
+ CHECK(Equiv(I1, I2));
+ }
+
+ {
+ VLOG(1) << "Check Pi_1(T) = Pi_2(T^-1) (destructive).";
+ VectorFst<Arc> P1(T);
+ VectorFst<Arc> I1(T);
+ Project(&P1, PROJECT_INPUT);
+ Invert(&I1);
+ Project(&I1, PROJECT_OUTPUT);
+ CHECK(Equiv(P1, I1));
+ }
+
+ {
+ VLOG(1) << "Check Pi_2(T) = Pi_1(T^-1) (destructive).";
+ VectorFst<Arc> P1(T);
+ VectorFst<Arc> I1(T);
+ Project(&P1, PROJECT_OUTPUT);
+ Invert(&I1);
+ Project(&I1, PROJECT_INPUT);
+ CHECK(Equiv(P1, I1));
+ }
+
+ {
+ VLOG(1) << "Check Pi_1(T) = Pi_2(T^-1) (delayed).";
+ ProjectFst<Arc> P1(T, PROJECT_INPUT);
+ InvertFst<Arc> I1(T);
+ ProjectFst<Arc> P2(I1, PROJECT_OUTPUT);
+ CHECK(Equiv(P1, P2));
+ }
+
+
+ {
+ VLOG(1) << "Check Pi_2(T) = Pi_1(T^-1) (delayed).";
+ ProjectFst<Arc> P1(T, PROJECT_OUTPUT);
+ InvertFst<Arc> I1(T);
+ ProjectFst<Arc> P2(I1, PROJECT_INPUT);
+ CHECK(Equiv(P1, P2));
+ }
+
+
+ {
+ VLOG(1) << "Check destructive relabeling";
+ static const int kNumLabels = 10;
+ // set up relabeling pairs
+ vector<Label> labelset(kNumLabels);
+ for (size_t i = 0; i < kNumLabels; ++i) labelset[i] = i;
+ for (size_t i = 0; i < kNumLabels; ++i) {
+ swap(labelset[i], labelset[rand() % kNumLabels]);
+ }
+
+ vector<pair<Label, Label> > ipairs1(kNumLabels);
+ vector<pair<Label, Label> > opairs1(kNumLabels);
+ for (size_t i = 0; i < kNumLabels; ++i) {
+ ipairs1[i] = make_pair(i, labelset[i]);
+ opairs1[i] = make_pair(labelset[i], i);
+ }
+ VectorFst<Arc> R(T);
+ Relabel(&R, ipairs1, opairs1);
+
+ vector<pair<Label, Label> > ipairs2(kNumLabels);
+ vector<pair<Label, Label> > opairs2(kNumLabels);
+ for (size_t i = 0; i < kNumLabels; ++i) {
+ ipairs2[i] = make_pair(labelset[i], i);
+ opairs2[i] = make_pair(i, labelset[i]);
+ }
+ Relabel(&R, ipairs2, opairs2);
+ CHECK(Equiv(R, T));
+
+ VLOG(1) << "Check on-the-fly relabeling";
+ RelabelFst<Arc> Rdelay(T, ipairs1, opairs1);
+
+ RelabelFst<Arc> RRdelay(Rdelay, ipairs2, opairs2);
+ CHECK(Equiv(RRdelay, T));
+ }
+
+ {
+ VLOG(1) << "Check encoding/decoding (destructive).";
+ VectorFst<Arc> D(T);
+ uint32 encode_props = 0;
+ if (rand() % 2)
+ encode_props |= kEncodeLabels;
+ if (rand() % 2)
+ encode_props |= kEncodeWeights;
+ EncodeMapper<Arc> encoder(encode_props, ENCODE);
+ Encode(&D, &encoder);
+ Decode(&D, encoder);
+ CHECK(Equiv(D, T));
+ }
+
+ {
+ VLOG(1) << "Check encoding/decoding (delayed).";
+ uint32 encode_props = 0;
+ if (rand() % 2)
+ encode_props |= kEncodeLabels;
+ if (rand() % 2)
+ encode_props |= kEncodeWeights;
+ EncodeMapper<Arc> encoder(encode_props, ENCODE);
+ EncodeFst<Arc> E(T, &encoder);
+ VectorFst<Arc> Encoded(E);
+ DecodeFst<Arc> D(Encoded, encoder);
+ CHECK(Equiv(D, T));
+ }
+
+ {
+ VLOG(1) << "Check gallic mappers (constructive).";
+ ToGallicMapper<Arc> to_mapper;
+ FromGallicMapper<Arc> from_mapper;
+ VectorFst< GallicArc<Arc> > G;
+ VectorFst<Arc> F;
+ ArcMap(T, &G, to_mapper);
+ ArcMap(G, &F, from_mapper);
+ CHECK(Equiv(T, F));
+ }
+
+ {
+ VLOG(1) << "Check gallic mappers (delayed).";
+ ToGallicMapper<Arc> to_mapper;
+ FromGallicMapper<Arc> from_mapper;
+ ArcMapFst<Arc, GallicArc<Arc>, ToGallicMapper<Arc> >
+ G(T, to_mapper);
+ ArcMapFst<GallicArc<Arc>, Arc, FromGallicMapper<Arc> >
+ F(G, from_mapper);
+ CHECK(Equiv(T, F));
+ }
+ }
+
+ // Tests compose-based operations.
+ void TestCompose(const Fst<Arc> &T1, const Fst<Arc> &T2,
+ const Fst<Arc> &T3) {
+ if (!(Weight::Properties() & kCommutative))
+ return;
+
+ VectorFst<Arc> S1(T1);
+ VectorFst<Arc> S2(T2);
+ VectorFst<Arc> S3(T3);
+
+ ILabelCompare<Arc> icomp;
+ OLabelCompare<Arc> ocomp;
+
+ ArcSort(&S1, ocomp);
+ ArcSort(&S2, ocomp);
+ ArcSort(&S3, icomp);
+
+ {
+ VLOG(1) << "Check composition is associative.";
+ ComposeFst<Arc> C1(S1, S2);
+
+ ComposeFst<Arc> C2(C1, S3);
+ ComposeFst<Arc> C3(S2, S3);
+ ComposeFst<Arc> C4(S1, C3);
+
+ CHECK(Equiv(C2, C4));
+ }
+
+ {
+ VLOG(1) << "Check composition left distributes over union.";
+ UnionFst<Arc> U1(S2, S3);
+ ComposeFst<Arc> C1(S1, U1);
+
+ ComposeFst<Arc> C2(S1, S2);
+ ComposeFst<Arc> C3(S1, S3);
+ UnionFst<Arc> U2(C2, C3);
+
+ CHECK(Equiv(C1, U2));
+ }
+
+ {
+ VLOG(1) << "Check composition right distributes over union.";
+ UnionFst<Arc> U1(S1, S2);
+ ComposeFst<Arc> C1(U1, S3);
+
+ ComposeFst<Arc> C2(S1, S3);
+ ComposeFst<Arc> C3(S2, S3);
+ UnionFst<Arc> U2(C2, C3);
+
+ CHECK(Equiv(C1, U2));
+ }
+
+ VectorFst<Arc> A1(S1);
+ VectorFst<Arc> A2(S2);
+ VectorFst<Arc> A3(S3);
+ Project(&A1, PROJECT_OUTPUT);
+ Project(&A2, PROJECT_INPUT);
+ Project(&A3, PROJECT_INPUT);
+
+ {
+ VLOG(1) << "Check intersection is commutative.";
+ IntersectFst<Arc> I1(A1, A2);
+ IntersectFst<Arc> I2(A2, A1);
+ CHECK(Equiv(I1, I2));
+ }
+
+ {
+ VLOG(1) << "Check all epsilon filters leads to equivalent results.";
+ typedef Matcher< Fst<Arc> > M;
+ ComposeFst<Arc> C1(S1, S2);
+ ComposeFst<Arc> C2(
+ S1, S2,
+ ComposeFstOptions<Arc, M, AltSequenceComposeFilter<M> >());
+ ComposeFst<Arc> C3(
+ S1, S2,
+ ComposeFstOptions<Arc, M, MatchComposeFilter<M> >());
+
+ CHECK(Equiv(C1, C2));
+ CHECK(Equiv(C1, C3));
+ }
+ }
+
+ // Tests sorting operations
+ void TestSort(const Fst<Arc> &T) {
+ ILabelCompare<Arc> icomp;
+ OLabelCompare<Arc> ocomp;
+
+ {
+ VLOG(1) << "Check arc sorted Fst is equivalent to its input.";
+ VectorFst<Arc> S1(T);
+ ArcSort(&S1, icomp);
+ CHECK(Equiv(T, S1));
+ }
+
+ {
+ VLOG(1) << "Check destructive and delayed arcsort are equivalent.";
+ VectorFst<Arc> S1(T);
+ ArcSort(&S1, icomp);
+ ArcSortFst< Arc, ILabelCompare<Arc> > S2(T, icomp);
+ CHECK(Equiv(S1, S2));
+ }
+
+ {
+ VLOG(1) << "Check ilabel sorting vs. olabel sorting with inversions.";
+ VectorFst<Arc> S1(T);
+ VectorFst<Arc> S2(T);
+ ArcSort(&S1, icomp);
+ Invert(&S2);
+ ArcSort(&S2, ocomp);
+ Invert(&S2);
+ CHECK(Equiv(S1, S2));
+ }
+
+ {
+ VLOG(1) << "Check topologically sorted Fst is equivalent to its input.";
+ VectorFst<Arc> S1(T);
+ TopSort(&S1);
+ CHECK(Equiv(T, S1));
+ }
+
+ {
+ VLOG(1) << "Check reverse(reverse(T)) = T";
+ VectorFst< ReverseArc<Arc> > R1;
+ VectorFst<Arc> R2;
+ Reverse(T, &R1);
+ Reverse(R1, &R2);
+ CHECK(Equiv(T, R2));
+ }
+ }
+
+ // Tests optimization operations
+ void TestOptimize(const Fst<Arc> &T) {
+ uint64 tprops = T.Properties(kFstProperties, true);
+ uint64 wprops = Weight::Properties();
+
+ VectorFst<Arc> A(T);
+ Project(&A, PROJECT_INPUT);
+
+ {
+ VLOG(1) << "Check connected FST is equivalent to its input.";
+ VectorFst<Arc> C1(T);
+ Connect(&C1);
+ CHECK(Equiv(T, C1));
+ }
+
+ if ((wprops & kSemiring) == kSemiring &&
+ (tprops & kAcyclic || wprops & kIdempotent)) {
+ VLOG(1) << "Check epsilon-removed FST is equivalent to its input.";
+ VectorFst<Arc> R1(T);
+ RmEpsilon(&R1);
+ CHECK(Equiv(T, R1));
+
+ VLOG(1) << "Check destructive and delayed epsilon removal"
+ << "are equivalent.";
+ RmEpsilonFst<Arc> R2(T);
+ CHECK(Equiv(R1, R2));
+
+ VLOG(1) << "Check an FST with a large proportion"
+ << " of epsilon transitions:";
+ // Maps all transitions of T to epsilon-transitions and append
+ // a non-epsilon transition.
+ VectorFst<Arc> U;
+ ArcMap(T, &U, EpsMapper<Arc>());
+ VectorFst<Arc> V;
+ V.SetStart(V.AddState());
+ Arc arc(1, 1, Weight::One(), V.AddState());
+ V.AddArc(V.Start(), arc);
+ V.SetFinal(arc.nextstate, Weight::One());
+ Concat(&U, V);
+ // Check that epsilon-removal preserves the shortest-distance
+ // from the initial state to the final states.
+ vector<Weight> d;
+ ShortestDistance(U, &d, true);
+ Weight w = U.Start() < d.size() ? d[U.Start()] : Weight::Zero();
+ VectorFst<Arc> U1(U);
+ RmEpsilon(&U1);
+ ShortestDistance(U1, &d, true);
+ Weight w1 = U1.Start() < d.size() ? d[U1.Start()] : Weight::Zero();
+ CHECK(ApproxEqual(w, w1, kTestDelta));
+ RmEpsilonFst<Arc> U2(U);
+ ShortestDistance(U2, &d, true);
+ Weight w2 = U2.Start() < d.size() ? d[U2.Start()] : Weight::Zero();
+ CHECK(ApproxEqual(w, w2, kTestDelta));
+ }
+
+ if ((wprops & kSemiring) == kSemiring && tprops & kAcyclic) {
+ VLOG(1) << "Check determinized FSA is equivalent to its input.";
+ DeterminizeFst<Arc> D(A);
+ CHECK(Equiv(A, D));
+
+
+ int n;
+ {
+ VLOG(1) << "Check size(min(det(A))) <= size(det(A))"
+ << " and min(det(A)) equiv det(A)";
+ VectorFst<Arc> M(D);
+ n = M.NumStates();
+ Minimize(&M);
+ CHECK(Equiv(D, M));
+ CHECK(M.NumStates() <= n);
+ n = M.NumStates();
+ }
+
+ if (n && (wprops & kIdempotent) == kIdempotent &&
+ A.Properties(kNoEpsilons, true)) {
+ VLOG(1) << "Check that Revuz's algorithm leads to the"
+ << " same number of states as Brozozowski's algorithm";
+
+ // Skip test if A is the empty machine or contains epsilons or
+ // if the semiring is not idempotent (to avoid floating point
+ // errors)
+ VectorFst<Arc> R;
+ Reverse(A, &R);
+ RmEpsilon(&R);
+ DeterminizeFst<Arc> DR(R);
+ VectorFst<Arc> RD;
+ Reverse(DR, &RD);
+ DeterminizeFst<Arc> DRD(RD);
+ VectorFst<Arc> M(DRD);
+ CHECK_EQ(n + 1, M.NumStates()); // Accounts for the epsilon transition
+ // to the initial state
+ }
+ }
+
+ if (Arc::Type() == LogArc::Type() || Arc::Type() == StdArc::Type()) {
+ VLOG(1) << "Check reweight(T) equiv T";
+ vector<Weight> potential;
+ VectorFst<Arc> RI(T);
+ VectorFst<Arc> RF(T);
+ while (potential.size() < RI.NumStates())
+ potential.push_back((*weight_generator_)());
+
+ Reweight(&RI, potential, REWEIGHT_TO_INITIAL);
+ CHECK(Equiv(T, RI));
+
+ Reweight(&RF, potential, REWEIGHT_TO_FINAL);
+ CHECK(Equiv(T, RF));
+ }
+
+ if ((wprops & kIdempotent) || (tprops & kAcyclic)) {
+ VLOG(1) << "Check pushed FST is equivalent to input FST.";
+ // Pushing towards the final state.
+ if (wprops & kRightSemiring) {
+ VectorFst<Arc> P1;
+ Push<Arc, REWEIGHT_TO_FINAL>(T, &P1, kPushLabels);
+ CHECK(Equiv(T, P1));
+
+ VectorFst<Arc> P2;
+ Push<Arc, REWEIGHT_TO_FINAL>(T, &P2, kPushWeights);
+ CHECK(Equiv(T, P2));
+
+ VectorFst<Arc> P3;
+ Push<Arc, REWEIGHT_TO_FINAL>(T, &P3, kPushLabels | kPushWeights);
+ CHECK(Equiv(T, P3));
+ }
+
+ // Pushing towards the initial state.
+ if (wprops & kLeftSemiring) {
+ VectorFst<Arc> P1;
+ Push<Arc, REWEIGHT_TO_INITIAL>(T, &P1, kPushLabels);
+ CHECK(Equiv(T, P1));
+
+ VectorFst<Arc> P2;
+ Push<Arc, REWEIGHT_TO_INITIAL>(T, &P2, kPushWeights);
+ CHECK(Equiv(T, P2));
+ VectorFst<Arc> P3;
+ Push<Arc, REWEIGHT_TO_INITIAL>(T, &P3, kPushLabels | kPushWeights);
+ CHECK(Equiv(T, P3));
+ }
+ }
+
+ if ((wprops & (kPath | kCommutative)) == (kPath | kCommutative)) {
+ VLOG(1) << "Check pruning algorithm";
+ {
+ VLOG(1) << "Check equiv. of constructive and destructive algorithms";
+ Weight thresold = (*weight_generator_)();
+ VectorFst<Arc> P1(T);
+ Prune(&P1, thresold);
+ VectorFst<Arc> P2;
+ Prune(T, &P2, thresold);
+ CHECK(Equiv(P1,P2));
+ }
+
+ {
+ VLOG(1) << "Check prune(reverse) equiv reverse(prune)";
+ Weight thresold = (*weight_generator_)();
+ VectorFst< ReverseArc<Arc> > R;
+ VectorFst<Arc> P1(T);
+ VectorFst<Arc> P2;
+ Prune(&P1, thresold);
+ Reverse(T, &R);
+ Prune(&R, thresold.Reverse());
+ Reverse(R, &P2);
+ CHECK(Equiv(P1, P2));
+ }
+ {
+ VLOG(1) << "Check: ShortestDistance(T- prune(T))"
+ << " > ShortestDistance(T) times Thresold";
+ Weight thresold = (*weight_generator_)();
+ VectorFst<Arc> P;
+ Prune(A, &P, thresold);
+ DifferenceFst<Arc> C(A, DeterminizeFst<Arc>
+ (RmEpsilonFst<Arc>
+ (ArcMapFst<Arc, Arc,
+ RmWeightMapper<Arc> >
+ (P, RmWeightMapper<Arc>()))));
+ Weight sum1 = Times(ShortestDistance(A), thresold);
+ Weight sum2 = ShortestDistance(C);
+ CHECK(Plus(sum1, sum2) == sum1);
+ }
+ }
+ if (tprops & kAcyclic) {
+ VLOG(1) << "Check synchronize(T) equiv T";
+ SynchronizeFst<Arc> S(T);
+ CHECK(Equiv(T, S));
+ }
+ }
+
+ // Tests search operations
+ void TestSearch(const Fst<Arc> &T) {
+ uint64 wprops = Weight::Properties();
+
+ VectorFst<Arc> A(T);
+ Project(&A, PROJECT_INPUT);
+
+ if ((wprops & (kPath | kRightSemiring)) == (kPath | kRightSemiring)) {
+ VLOG(1) << "Check 1-best weight.";
+ VectorFst<Arc> path;
+ ShortestPath(T, &path);
+ Weight tsum = ShortestDistance(T);
+ Weight psum = ShortestDistance(path);
+ CHECK(ApproxEqual(tsum, psum, kTestDelta));
+ }
+
+ if ((wprops & (kPath | kSemiring)) == (kPath | kSemiring)) {
+ VLOG(1) << "Check n-best weights";
+ VectorFst<Arc> R(A);
+ RmEpsilon(&R);
+ int nshortest = rand() % kNumRandomShortestPaths + 2;
+ VectorFst<Arc> paths;
+ ShortestPath(R, &paths, nshortest, true, false,
+ Weight::Zero(), kNumShortestStates);
+ vector<Weight> distance;
+ ShortestDistance(paths, &distance, true);
+ StateId pstart = paths.Start();
+ if (pstart != kNoStateId) {
+ ArcIterator< Fst<Arc> > piter(paths, pstart);
+ for (; !piter.Done(); piter.Next()) {
+ StateId s = piter.Value().nextstate;
+ Weight nsum = s < distance.size() ?
+ Times(piter.Value().weight, distance[s]) : Weight::Zero();
+ VectorFst<Arc> path;
+ ShortestPath(R, &path);
+ Weight dsum = ShortestDistance(path);
+ CHECK(ApproxEqual(nsum, dsum, kTestDelta));
+ ArcMap(&path, RmWeightMapper<Arc>());
+ VectorFst<Arc> S;
+ Difference(R, path, &S);
+ R = S;
+ }
+ }
+ }
+ }
+
+ // Tests if two FSTS are equivalent by checking if random
+ // strings from one FST are transduced the same by both FSTs.
+ bool Equiv(const Fst<Arc> &fst1, const Fst<Arc> &fst2) {
+ VLOG(1) << "Check FSTs for sanity (including property bits).";
+ CHECK(Verify(fst1));
+ CHECK(Verify(fst2));
+
+ UniformArcSelector<Arc> uniform_selector(seed_);
+ RandGenOptions< UniformArcSelector<Arc> >
+ opts(uniform_selector, kRandomPathLength);
+ return RandEquivalent(fst1, fst2, kNumRandomPaths, kTestDelta, opts);
+ }
+
+ // Random seed
+ int seed_;
+
+ // FST with no states
+ VectorFst<Arc> zero_fst_;
+
+ // FST with one state that accepts epsilon.
+ VectorFst<Arc> one_fst_;
+
+ // FST with one state that accepts all strings.
+ VectorFst<Arc> univ_fst_;
+
+ // Generates weights used in testing.
+ WeightGenerator *weight_generator_;
+
+ // Maximum random path length.
+ static const int kRandomPathLength;
+
+ // Number of random paths to explore.
+ static const int kNumRandomPaths;
+
+ // Maximum number of nshortest paths.
+ static const int kNumRandomShortestPaths;
+
+ // Maximum number of nshortest states.
+ static const int kNumShortestStates;
+
+ // Delta for equivalence tests.
+ static const float kTestDelta;
+
+ DISALLOW_COPY_AND_ASSIGN(WeightedTester);
+};
+
+
+template <class A, class WG>
+const int WeightedTester<A, WG>::kRandomPathLength = 25;
+
+template <class A, class WG>
+const int WeightedTester<A, WG>::kNumRandomPaths = 100;
+
+template <class A, class WG>
+const int WeightedTester<A, WG>::kNumRandomShortestPaths = 100;
+
+template <class A, class WG>
+const int WeightedTester<A, WG>::kNumShortestStates = 10000;
+
+template <class A, class WG>
+const float WeightedTester<A, WG>::kTestDelta = .05;
+
+// This class tests a variety of identities and properties that must
+// hold for various algorithms on unweighted FSAs and that are not tested
+// by WeightedTester. Only the specialization does anything interesting.
+template <class Arc>
+class UnweightedTester {
+ public:
+ UnweightedTester(const Fst<Arc> &zero_fsa, const Fst<Arc> &one_fsa,
+ const Fst<Arc> &univ_fsa) {}
+
+ void Test(const Fst<Arc> &A1, const Fst<Arc> &A2, const Fst<Arc> &A3) {}
+};
+
+
+// Specialization for StdArc. This should work for any commutative,
+// idempotent semiring when restricted to the unweighted case
+// (being isomorphic to the boolean semiring).
+template <>
+class UnweightedTester<StdArc> {
+ public:
+ typedef StdArc Arc;
+ typedef Arc::Label Label;
+ typedef Arc::StateId StateId;
+ typedef Arc::Weight Weight;
+
+ UnweightedTester(const Fst<Arc> &zero_fsa, const Fst<Arc> &one_fsa,
+ const Fst<Arc> &univ_fsa)
+ : zero_fsa_(zero_fsa), one_fsa_(one_fsa), univ_fsa_(univ_fsa) {}
+
+ void Test(const Fst<Arc> &A1, const Fst<Arc> &A2, const Fst<Arc> &A3) {
+ TestRational(A1, A2, A3);
+ TestIntersect(A1, A2, A3);
+ TestOptimize(A1);
+ }
+
+ private:
+ // Tests rational operations with identities
+ void TestRational(const Fst<Arc> &A1, const Fst<Arc> &A2,
+ const Fst<Arc> &A3) {
+
+ {
+ VLOG(1) << "Check the union contains its arguments (destructive).";
+ VectorFst<Arc> U(A1);
+ Union(&U, A2);
+
+ CHECK(Subset(A1, U));
+ CHECK(Subset(A2, U));
+ }
+
+ {
+ VLOG(1) << "Check the union contains its arguments (delayed).";
+ UnionFst<Arc> U(A1, A2);
+
+ CHECK(Subset(A1, U));
+ CHECK(Subset(A2, U));
+ }
+
+ {
+ VLOG(1) << "Check if A^n c A* (destructive).";
+ VectorFst<Arc> C(one_fsa_);
+ int n = rand() % 5;
+ for (int i = 0; i < n; ++i)
+ Concat(&C, A1);
+
+ VectorFst<Arc> S(A1);
+ Closure(&S, CLOSURE_STAR);
+ CHECK(Subset(C, S));
+ }
+
+ {
+ VLOG(1) << "Check if A^n c A* (delayed).";
+ int n = rand() % 5;
+ Fst<Arc> *C = new VectorFst<Arc>(one_fsa_);
+ for (int i = 0; i < n; ++i) {
+ ConcatFst<Arc> *F = new ConcatFst<Arc>(*C, A1);
+ delete C;
+ C = F;
+ }
+ ClosureFst<Arc> S(A1, CLOSURE_STAR);
+ CHECK(Subset(*C, S));
+ delete C;
+ }
+ }
+
+ // Tests intersect-based operations.
+ void TestIntersect(const Fst<Arc> &A1, const Fst<Arc> &A2,
+ const Fst<Arc> &A3) {
+ VectorFst<Arc> S1(A1);
+ VectorFst<Arc> S2(A2);
+ VectorFst<Arc> S3(A3);
+
+ ILabelCompare<Arc> comp;
+
+ ArcSort(&S1, comp);
+ ArcSort(&S2, comp);
+ ArcSort(&S3, comp);
+
+ {
+ VLOG(1) << "Check the intersection is contained in its arguments.";
+ IntersectFst<Arc> I1(S1, S2);
+ CHECK(Subset(I1, S1));
+ CHECK(Subset(I1, S2));
+ }
+
+ {
+ VLOG(1) << "Check union distributes over intersection.";
+ IntersectFst<Arc> I1(S1, S2);
+ UnionFst<Arc> U1(I1, S3);
+
+ UnionFst<Arc> U2(S1, S3);
+ UnionFst<Arc> U3(S2, S3);
+ ArcSortFst< Arc, ILabelCompare<Arc> > S4(U3, comp);
+ IntersectFst<Arc> I2(U2, S4);
+
+ CHECK(Equiv(U1, I2));
+ }
+
+ VectorFst<Arc> C1;
+ VectorFst<Arc> C2;
+ Complement(S1, &C1);
+ Complement(S2, &C2);
+ ArcSort(&C1, comp);
+ ArcSort(&C2, comp);
+
+
+ {
+ VLOG(1) << "Check S U S' = Sigma*";
+ UnionFst<Arc> U(S1, C1);
+ CHECK(Equiv(U, univ_fsa_));
+ }
+
+ {
+ VLOG(1) << "Check S n S' = {}";
+ IntersectFst<Arc> I(S1, C1);
+ CHECK(Equiv(I, zero_fsa_));
+ }
+
+ {
+ VLOG(1) << "Check (S1' U S2') == (S1 n S2)'";
+ UnionFst<Arc> U(C1, C2);
+
+ IntersectFst<Arc> I(S1, S2);
+ VectorFst<Arc> C3;
+ Complement(I, &C3);
+ CHECK(Equiv(U, C3));
+ }
+
+ {
+ VLOG(1) << "Check (S1' n S2') == (S1 U S2)'";
+ IntersectFst<Arc> I(C1, C2);
+
+ UnionFst<Arc> U(S1, S2);
+ VectorFst<Arc> C3;
+ Complement(U, &C3);
+ CHECK(Equiv(I, C3));
+ }
+ }
+
+ // Tests optimization operations
+ void TestOptimize(const Fst<Arc> &A) {
+ {
+ VLOG(1) << "Check determinized FSA is equivalent to its input.";
+ DeterminizeFst<Arc> D(A);
+ CHECK(Equiv(A, D));
+ }
+
+ {
+ VLOG(1) << "Check minimized FSA is equivalent to its input.";
+ int n;
+ {
+ RmEpsilonFst<Arc> R(A);
+ DeterminizeFst<Arc> D(R);
+ VectorFst<Arc> M(D);
+ Minimize(&M);
+ CHECK(Equiv(A, M));
+ n = M.NumStates();
+ }
+
+ if (n) { // Skip test if A is the empty machine
+ VLOG(1) << "Check that Hopcroft's and Revuz's algorithms lead to the"
+ << " same number of states as Brozozowski's algorithm";
+ VectorFst<Arc> R;
+ Reverse(A, &R);
+ RmEpsilon(&R);
+ DeterminizeFst<Arc> DR(R);
+ VectorFst<Arc> RD;
+ Reverse(DR, &RD);
+ DeterminizeFst<Arc> DRD(RD);
+ VectorFst<Arc> M(DRD);
+ CHECK_EQ(n + 1, M.NumStates()); // Accounts for the epsilon transition
+ // to the initial state
+ }
+ }
+ }
+
+ // Tests if two FSAS are equivalent.
+ bool Equiv(const Fst<Arc> &fsa1, const Fst<Arc> &fsa2) {
+ VLOG(1) << "Check FSAs for sanity (including property bits).";
+ CHECK(Verify(fsa1));
+ CHECK(Verify(fsa2));
+
+ VectorFst<Arc> vfsa1(fsa1);
+ VectorFst<Arc> vfsa2(fsa2);
+ RmEpsilon(&vfsa1);
+ RmEpsilon(&vfsa2);
+ DeterminizeFst<Arc> dfa1(vfsa1);
+ DeterminizeFst<Arc> dfa2(vfsa2);
+
+ // Test equivalence using union-find algorithm
+ bool equiv1 = Equivalent(dfa1, dfa2);
+
+ // Test equivalence by checking if (S1 - S2) U (S2 - S1) is empty
+ ILabelCompare<Arc> comp;
+ VectorFst<Arc> sdfa1(dfa1);
+ ArcSort(&sdfa1, comp);
+ VectorFst<Arc> sdfa2(dfa2);
+ ArcSort(&sdfa2, comp);
+
+ DifferenceFst<Arc> dfsa1(sdfa1, sdfa2);
+ DifferenceFst<Arc> dfsa2(sdfa2, sdfa1);
+
+ VectorFst<Arc> ufsa(dfsa1);
+ Union(&ufsa, dfsa2);
+ Connect(&ufsa);
+ bool equiv2 = ufsa.NumStates() == 0;
+
+ // Check two equivalence tests match
+ CHECK((equiv1 && equiv2) || (!equiv1 && !equiv2));
+
+ return equiv1;
+ }
+
+ // Tests if FSA1 is a subset of FSA2 (disregarding weights).
+ bool Subset(const Fst<Arc> &fsa1, const Fst<Arc> &fsa2) {
+ VLOG(1) << "Check FSAs (incl. property bits) for sanity";
+ CHECK(Verify(fsa1));
+ CHECK(Verify(fsa2));
+
+ VectorFst<StdArc> vfsa1;
+ VectorFst<StdArc> vfsa2;
+ RmEpsilon(&vfsa1);
+ RmEpsilon(&vfsa2);
+ ILabelCompare<StdArc> comp;
+ ArcSort(&vfsa1, comp);
+ ArcSort(&vfsa2, comp);
+ IntersectFst<StdArc> ifsa(vfsa1, vfsa2);
+ DeterminizeFst<StdArc> dfa1(vfsa1);
+ DeterminizeFst<StdArc> dfa2(ifsa);
+ return Equivalent(dfa1, dfa2);
+ }
+
+ // Returns complement Fsa
+ void Complement(const Fst<Arc> &ifsa, MutableFst<Arc> *ofsa) {
+ RmEpsilonFst<Arc> rfsa(ifsa);
+ DeterminizeFst<Arc> dfa(rfsa);
+ DifferenceFst<Arc> cfsa(univ_fsa_, dfa);
+ *ofsa = cfsa;
+ }
+
+ // FSA with no states
+ VectorFst<Arc> zero_fsa_;
+
+ // FSA with one state that accepts epsilon.
+ VectorFst<Arc> one_fsa_;
+
+ // FSA with one state that accepts all strings.
+ VectorFst<Arc> univ_fsa_;
+
+ DISALLOW_COPY_AND_ASSIGN(UnweightedTester);
+};
+
+
+// This class tests a variety of identities and properties that must
+// hold for various FST algorithms. It randomly generates FSTs, using
+// function object 'weight_generator' to select weights. 'WeightTester'
+// and 'UnweightedTester' are then called.
+template <class Arc, class WeightGenerator>
+class AlgoTester {
+ public:
+ typedef typename Arc::Label Label;
+ typedef typename Arc::StateId StateId;
+ typedef typename Arc::Weight Weight;
+
+ AlgoTester(WeightGenerator generator, int seed) :
+ weight_generator_(generator), seed_(seed) {
+ one_fst_.AddState();
+ one_fst_.SetStart(0);
+ one_fst_.SetFinal(0, Weight::One());
+
+ univ_fst_.AddState();
+ univ_fst_.SetStart(0);
+ univ_fst_.SetFinal(0, Weight::One());
+ for (int i = 0; i < kNumRandomLabels; ++i)
+ univ_fst_.AddArc(0, Arc(i, i, Weight::One(), 0));
+ }
+
+ void Test() {
+ VLOG(1) << "weight type = " << Weight::Type();
+
+ for (int i = 0; i < FLAGS_repeat; ++i) {
+ // Random transducers
+ VectorFst<Arc> T1;
+ VectorFst<Arc> T2;
+ VectorFst<Arc> T3;
+ RandFst(&T1);
+ RandFst(&T2);
+ RandFst(&T3);
+ WeightedTester<Arc, WeightGenerator>
+ weighted_tester(seed_, zero_fst_, one_fst_,
+ univ_fst_, &weight_generator_);
+ weighted_tester.Test(T1, T2, T3);
+
+ VectorFst<Arc> A1(T1);
+ VectorFst<Arc> A2(T2);
+ VectorFst<Arc> A3(T3);
+ Project(&A1, PROJECT_OUTPUT);
+ Project(&A2, PROJECT_INPUT);
+ Project(&A3, PROJECT_INPUT);
+ ArcMap(&A1, rm_weight_mapper);
+ ArcMap(&A2, rm_weight_mapper);
+ ArcMap(&A3, rm_weight_mapper);
+ UnweightedTester<Arc> unweighted_tester(zero_fst_, one_fst_, univ_fst_);
+ unweighted_tester.Test(A1, A2, A3);
+ }
+ }
+
+ private:
+ // Generates a random FST.
+ void RandFst(MutableFst<Arc> *fst) {
+ // Determines direction of the arcs wrt state numbering. This way we
+ // can force acyclicity when desired.
+ enum ArcDirection { ANY_DIRECTION = 0, FORWARD_DIRECTION = 1,
+ REVERSE_DIRECTION = 2, NUM_DIRECTIONS = 3 };
+
+ ArcDirection arc_direction = ANY_DIRECTION;
+ if (rand()/(RAND_MAX + 1.0) < kAcyclicProb)
+ arc_direction = rand() % 2 ? FORWARD_DIRECTION : REVERSE_DIRECTION;
+
+ fst->DeleteStates();
+ StateId ns = rand() % kNumRandomStates;
+
+ if (ns == 0)
+ return;
+ for (StateId s = 0; s < ns; ++s)
+ fst->AddState();
+
+ StateId start = rand() % ns;
+ fst->SetStart(start);
+
+ size_t na = rand() % kNumRandomArcs;
+ for (size_t n = 0; n < na; ++n) {
+ StateId s = rand() % ns;
+ Arc arc;
+ arc.ilabel = rand() % kNumRandomLabels;
+ arc.olabel = rand() % kNumRandomLabels;
+ arc.weight = weight_generator_();
+ arc.nextstate = rand() % ns;
+
+ if (arc_direction == ANY_DIRECTION ||
+ (arc_direction == FORWARD_DIRECTION && arc.ilabel > arc.olabel) ||
+ (arc_direction == REVERSE_DIRECTION && arc.ilabel < arc.olabel))
+ fst->AddArc(s, arc);
+ }
+
+ StateId nf = rand() % (ns + 1);
+ for (StateId n = 0; n < nf; ++n) {
+ StateId s = rand() % ns;
+ Weight final = weight_generator_();
+ fst->SetFinal(s, final);
+ }
+ VLOG(1) << "Check FST for sanity (including property bits).";
+ CHECK(Verify(*fst));
+
+ // Get/compute all properties.
+ uint64 props = fst->Properties(kFstProperties, true);
+
+ // Select random set of properties to be unknown.
+ uint64 mask = 0;
+ for (int n = 0; n < 8; ++n) {
+ mask |= rand() & 0xff;
+ mask <<= 8;
+ }
+ mask &= ~kTrinaryProperties;
+ fst->SetProperties(props & ~mask, mask);
+ }
+
+ // Generates weights used in testing.
+ WeightGenerator weight_generator_;
+
+ // Random seed
+ int seed_;
+
+ // FST with no states
+ VectorFst<Arc> zero_fst_;
+
+ // FST with one state that accepts epsilon.
+ VectorFst<Arc> one_fst_;
+
+ // FST with one state that accepts all strings.
+ VectorFst<Arc> univ_fst_;
+
+ // Mapper to remove weights from an Fst
+ RmWeightMapper<Arc> rm_weight_mapper;
+
+ // Maximum number of states in random test Fst.
+ static const int kNumRandomStates;
+
+ // Maximum number of arcs in random test Fst.
+ static const int kNumRandomArcs;
+
+ // Number of alternative random labels.
+ static const int kNumRandomLabels;
+
+ // Probability to force an acyclic Fst
+ static const float kAcyclicProb;
+
+ // Maximum random path length.
+ static const int kRandomPathLength;
+
+ // Number of random paths to explore.
+ static const int kNumRandomPaths;
+
+ DISALLOW_COPY_AND_ASSIGN(AlgoTester);
+};
+
+template <class A, class G> const int AlgoTester<A, G>::kNumRandomStates = 10;
+
+template <class A, class G> const int AlgoTester<A, G>::kNumRandomArcs = 25;
+
+template <class A, class G> const int AlgoTester<A, G>::kNumRandomLabels = 5;
+
+template <class A, class G> const float AlgoTester<A, G>::kAcyclicProb = .25;
+
+template <class A, class G> const int AlgoTester<A, G>::kRandomPathLength = 25;
+
+template <class A, class G> const int AlgoTester<A, G>::kNumRandomPaths = 100;
+
+} // namespace fst
+
+#endif // FST_TEST_ALGO_TEST_H__
diff --git a/src/test/fst_test.cc b/src/test/fst_test.cc
new file mode 100644
index 0000000..7d8d600
--- /dev/null
+++ b/src/test/fst_test.cc
@@ -0,0 +1,228 @@
+// fst_test.cc
+
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Copyright 2005-2010 Google, Inc.
+// Author: riley@google.com (Michael Riley)
+//
+// \file
+// Regression test for FST classes.
+
+#include "./fst_test.h"
+
+#include <fst/compact-fst.h>
+#include <fst/const-fst.h>
+#include <fst/edit-fst.h>
+#include <fst/matcher-fst.h>
+
+
+namespace fst {
+
+// A user-defined arc type.
+struct CustomArc {
+ typedef short Label;
+ typedef ProductWeight<TropicalWeight, LogWeight> Weight;
+ typedef int64 StateId;
+
+ CustomArc(Label i, Label o, Weight w, StateId s) :
+ ilabel(i), olabel(o), weight(w), nextstate(s) {}
+ CustomArc() {}
+
+ static const string &Type() { // Arc type name
+ static const string type = "my";
+ return type;
+ }
+
+ Label ilabel; // Transition input label
+ Label olabel; // Transition output label
+ Weight weight; // Transition weight
+ StateId nextstate; // Transition destination state
+};
+
+
+// A user-defined compactor for test FST.
+template <class A>
+class CustomCompactor {
+ public:
+ typedef A Arc;
+ typedef typename A::Label Label;
+ typedef typename A::StateId StateId;
+ typedef typename A::Weight Weight;
+ typedef pair<Label, Weight> Element;
+
+ Element Compact(StateId s, const A &arc) const {
+ return make_pair(arc.ilabel, arc.weight);
+ }
+
+ Arc Expand(StateId s, const Element &p, uint32 f = kArcValueFlags) const {
+ return p.first == kNoLabel ?
+ Arc(kNoLabel, kNoLabel, p.second, kNoStateId) :
+ Arc(p.first, 0, p.second, s);
+ }
+
+ ssize_t Size() const { return -1;}
+
+ uint64 Properties() const { return 0ULL;}
+
+ bool Compatible(const Fst<A> &fst) const {
+ return true;
+ }
+
+ static const string &Type() {
+ static const string type = "my";
+ return type;
+ }
+
+ bool Write(ostream &strm) const { return true; }
+
+ static CustomCompactor *Read(istream &strm) {
+ return new CustomCompactor;
+ }
+};
+
+
+REGISTER_FST(VectorFst, CustomArc);
+REGISTER_FST(ConstFst, CustomArc);
+static fst::FstRegisterer<
+ CompactFst<StdArc, CustomCompactor<StdArc> > >
+CompactFst_StdArc_CustomCompactor_registerer;
+static fst::FstRegisterer<
+ CompactFst<CustomArc, CustomCompactor<CustomArc> > >
+CompactFst_CustomArc_CustomCompactor_registerer;
+static fst::FstRegisterer<ConstFst<StdArc, uint16> >
+ConstFst_StdArc_uint16_registerer;
+static fst::FstRegisterer<
+ CompactFst<StdArc, CustomCompactor<StdArc>, uint16> >
+CompactFst_StdArc_CustomCompactor_uint16_registerer;
+
+} // namespace fst
+
+
+using fst::FstTester;
+using fst::VectorFst;
+using fst::ConstFst;
+using fst::MatcherFst;
+using fst::CompactFst;
+using fst::Fst;
+using fst::StdArc;
+using fst::CustomArc;
+using fst::CustomCompactor;
+using fst::StdArcLookAheadFst;
+using fst::EditFst;
+
+int main(int argc, char **argv) {
+ FLAGS_fst_verify_properties = true;
+ std::set_new_handler(FailedNewHandler);
+ SetFlags(argv[0], &argc, &argv, true);
+
+ // VectorFst<StdArc> tests
+ {
+ FstTester< VectorFst<StdArc> > std_vector_tester;
+ std_vector_tester.TestBase();
+ std_vector_tester.TestExpanded();
+ std_vector_tester.TestAssign();
+ std_vector_tester.TestCopy();
+ std_vector_tester.TestIO();
+ std_vector_tester.TestMutable();
+ }
+
+ // ConstFst<StdArc> tests
+ {
+ FstTester< ConstFst<StdArc> > std_const_tester;
+ std_const_tester.TestBase();
+ std_const_tester.TestExpanded();
+ std_const_tester.TestCopy();
+ std_const_tester.TestIO();
+ }
+
+ // CompactFst<StdArc, CustomCompactor<StdArc> >
+ {
+ FstTester< CompactFst<StdArc, CustomCompactor<StdArc> > >
+ std_compact_tester;
+ std_compact_tester.TestBase();
+ std_compact_tester.TestExpanded();
+ std_compact_tester.TestCopy();
+ std_compact_tester.TestIO();
+ }
+
+ // VectorFst<CustomArc> tests
+ {
+ FstTester< VectorFst<CustomArc> > std_vector_tester;
+ std_vector_tester.TestBase();
+ std_vector_tester.TestExpanded();
+ std_vector_tester.TestAssign();
+ std_vector_tester.TestCopy();
+ std_vector_tester.TestIO();
+ std_vector_tester.TestMutable();
+ }
+
+ // ConstFst<CustomArc> tests
+ {
+ FstTester< ConstFst<CustomArc> > std_const_tester;
+ std_const_tester.TestBase();
+ std_const_tester.TestExpanded();
+ std_const_tester.TestCopy();
+ std_const_tester.TestIO();
+ }
+
+ // CompactFst<CustomArc, CustomCompactor<CustomArc> >
+ {
+ FstTester< CompactFst<CustomArc, CustomCompactor<CustomArc> > >
+ std_compact_tester;
+ std_compact_tester.TestBase();
+ std_compact_tester.TestExpanded();
+ std_compact_tester.TestCopy();
+ std_compact_tester.TestIO();
+ }
+
+ // ConstFst<StdArc, uint16> tests
+ {
+ FstTester< ConstFst<StdArc, uint16> > std_const_tester;
+ std_const_tester.TestBase();
+ std_const_tester.TestExpanded();
+ std_const_tester.TestCopy();
+ std_const_tester.TestIO();
+ }
+
+ // CompactFst<StdArc, CustomCompactor<StdArc>, uint16>
+ {
+ FstTester< CompactFst<StdArc, CustomCompactor<StdArc>, uint16> >
+ std_compact_tester;
+ std_compact_tester.TestBase();
+ std_compact_tester.TestExpanded();
+ std_compact_tester.TestCopy();
+ std_compact_tester.TestIO();
+ }
+
+ // FstTester<StdArcLookAheadFst>
+ {
+ FstTester<StdArcLookAheadFst> std_matcher_tester;
+ std_matcher_tester.TestBase();
+ std_matcher_tester.TestExpanded();
+ std_matcher_tester.TestCopy();
+ }
+
+ // EditFst<StdArc> tests
+ {
+ FstTester< EditFst<StdArc> > std_edit_tester;
+ std_edit_tester.TestBase();
+ std_edit_tester.TestExpanded();
+ std_edit_tester.TestAssign();
+ std_edit_tester.TestCopy();
+ std_edit_tester.TestMutable();
+ }
+
+ cout << "PASS" << endl;
+
+ return 0;
+}
diff --git a/src/test/fst_test.h b/src/test/fst_test.h
new file mode 100644
index 0000000..da16476
--- /dev/null
+++ b/src/test/fst_test.h
@@ -0,0 +1,299 @@
+// fst_test.h
+
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Copyright 2005-2010 Google, Inc.
+// Author: riley@google.com (Michael Riley)
+//
+// \file
+// Regression test for FST classes.
+
+#ifndef FST_TEST_FST_TEST_H_
+#define FST_TEST_FST_TEST_H_
+
+#include <fst/equal.h>
+#include <fst/matcher.h>
+#include <fst/vector-fst.h>
+#include <fst/verify.h>
+
+DECLARE_string(tmpdir);
+
+namespace fst {
+
+// This tests an Fst F that is assumed to have a copy method from an
+// arbitrary Fst. Some test functions make further assumptions mostly
+// obvious from their name. These tests are written as member temple
+// functions that take a test fst as its argument so that different
+// Fsts in the interface hierarchy can be tested separately and so
+// that we can instantiate only those tests that make sense for a
+// particular Fst.
+template <class F>
+class FstTester {
+ public:
+ typedef typename F::Arc Arc;
+ typedef typename Arc::StateId StateId;
+ typedef typename Arc::Weight Weight;
+ typedef typename Arc::Label Label;
+
+ FstTester() {
+ VectorFst<Arc> vfst;
+ InitFst(&vfst, 128);
+ testfst_ = new F(vfst);
+ }
+
+ ~FstTester() {
+ delete testfst_;
+ }
+
+ // This verifies the contents described in InitFst() using
+ // methods defined in a generic Fst.
+ template <class G>
+ void TestBase(const G &fst) const {
+ CHECK(Verify(fst));
+ CHECK_EQ(fst.Start(), 0);
+ StateId ns = 0;
+ StateIterator<G> siter(fst);
+ Matcher<G> matcher(fst, MATCH_INPUT);
+ MatchType match_type = matcher.Type(true);
+ for (; !siter.Done(); siter.Next());
+ for (siter.Reset(); !siter.Done(); siter.Next()) {
+ StateId s = siter.Value();
+ matcher.SetState(s);
+ CHECK_EQ(fst.Final(s), NthWeight(s));
+ size_t na = 0;
+ ArcIterator<G> aiter(fst, s);
+ for (; !aiter.Done(); aiter.Next());
+ for (aiter.Reset(); !aiter.Done(); aiter.Next()) {
+ ++na;
+ const Arc &arc = aiter.Value();
+ CHECK_EQ(arc.ilabel, na);
+ CHECK_EQ(arc.olabel, 0);
+ CHECK_EQ(arc.weight, NthWeight(na));
+ CHECK_EQ(arc.nextstate, s);
+ if (match_type == MATCH_INPUT) {
+ CHECK(matcher.Find(arc.ilabel));
+ CHECK_EQ(matcher.Value().ilabel, arc.ilabel);
+ }
+ }
+ CHECK_EQ(na, s);
+ CHECK_EQ(na, aiter.Position());
+ CHECK_EQ(fst.NumArcs(s), s);
+ CHECK_EQ(fst.NumInputEpsilons(s), 0);
+ CHECK_EQ(fst.NumOutputEpsilons(s), s);
+ CHECK(!matcher.Find(s + 1)); // out-of-range
+ CHECK(!matcher.Find(kNoLabel)); // no explicit epsilons
+ CHECK(matcher.Find(0));
+ CHECK_EQ(matcher.Value().ilabel, kNoLabel); // implicit epsilon loop
+ ++ns;
+ }
+ CHECK(fst.Properties(kNotAcceptor, true));
+ CHECK(fst.Properties(kOEpsilons, true));
+ }
+
+ void TestBase() const {
+ TestBase(*testfst_);
+ }
+
+ // This verifies methods specfic to an ExpandedFst.
+ template <class G>
+ void TestExpanded(const G &fst) const {
+ StateId ns = 0;
+ for (StateIterator<G> siter(fst);
+ !siter.Done();
+ siter.Next()) {
+ ++ns;
+ }
+ CHECK_EQ(fst.NumStates(), ns);
+ CHECK(fst.Properties(kExpanded, false));
+ }
+
+ void TestExpanded() const { TestExpanded(*testfst_); }
+
+ // This verifies methods specific to a MutableFst.
+ template <class G>
+ void TestMutable(G *fst) const {
+ for (StateIterator<G> siter(*fst);
+ !siter.Done();
+ siter.Next()) {
+ StateId s = siter.Value();
+ size_t na = 0;
+ size_t ni = fst->NumInputEpsilons(s);
+ MutableArcIterator<G> aiter(fst, s);
+ for (; !aiter.Done(); aiter.Next());
+ for (aiter.Reset(); !aiter.Done(); aiter.Next()) {
+ ++na;
+ Arc arc = aiter.Value();
+ arc.ilabel = 0;
+ aiter.SetValue(arc);
+ arc = aiter.Value();
+ CHECK_EQ(arc.ilabel, 0);
+ CHECK_EQ(fst->NumInputEpsilons(s), ni + 1);
+ arc.ilabel = na;
+ aiter.SetValue(arc);
+ CHECK_EQ(fst->NumInputEpsilons(s), ni);
+ }
+ }
+
+ G *cfst1 = fst->Copy();
+ cfst1->DeleteStates();
+ CHECK_EQ(cfst1->NumStates(), 0);
+ delete cfst1;
+
+ G *cfst2 = fst->Copy();
+ for (StateIterator<G> siter(*cfst2);
+ !siter.Done();
+ siter.Next()) {
+ StateId s = siter.Value();
+ cfst2->DeleteArcs(s);
+ CHECK_EQ(cfst2->NumArcs(s), 0);
+ CHECK_EQ(cfst2->NumInputEpsilons(s), 0);
+ CHECK_EQ(cfst2->NumOutputEpsilons(s), 0);
+ }
+ delete cfst2;
+ }
+
+ void TestMutable() { TestMutable(testfst_); }
+
+ // This verifies the copy methods.
+ template <class G>
+ void TestAssign(G *fst) const {
+ // Assignment from G
+ G afst1;
+ afst1 = *fst;
+ CHECK(Equal(*fst, afst1));
+
+ // Assignment from Fst
+ G afst2;
+ afst2 = *static_cast<const Fst<Arc> *>(fst);
+ CHECK(Equal(*fst, afst2));
+
+ // Assignment from self
+ afst2.operator=(afst2);
+ CHECK(Equal(*fst, afst2));
+ }
+
+ void TestAssign() { TestAssign(testfst_); }
+
+ // This verifies the copy methods.
+ template <class G>
+ void TestCopy(const G &fst) const {
+ // Copy from G
+ G c1fst(fst);
+ TestBase(c1fst);
+
+ // Copy from Fst
+ const G c2fst(static_cast<const Fst<Arc> &>(fst));
+ TestBase(c2fst);
+
+ // Copy from self
+ const G *c3fst = fst.Copy();
+ TestBase(*c3fst);
+ delete c3fst;
+ }
+
+ void TestCopy() const { TestCopy(*testfst_); }
+
+ // This verifies the read/write methods.
+ template <class G>
+ void TestIO(const G &fst) const {
+ const string filename = FLAGS_tmpdir + "/test.fst";
+ {
+ // write/read
+ CHECK(fst.Write(filename));
+ G *ffst = G::Read(filename);
+ CHECK(ffst);
+ TestBase(*ffst);
+ delete ffst;
+ }
+
+ {
+ // generic read/cast/test
+ Fst<Arc> *gfst = Fst<Arc>::Read(filename);
+ CHECK(gfst);
+ G *dfst = static_cast<G *>(gfst);
+ TestBase(*dfst);
+
+ // generic write/read/test
+ CHECK(gfst->Write(filename));
+ Fst<Arc> *hfst = Fst<Arc>::Read(filename);
+ CHECK(hfst);
+ TestBase(*hfst);
+ delete gfst;
+ delete hfst;
+ }
+
+ // expanded write/read/test
+ if (fst.Properties(kExpanded, false)) {
+ ExpandedFst<Arc> *efst = ExpandedFst<Arc>::Read(filename);
+ CHECK(efst);
+ TestBase(*efst);
+ TestExpanded(*efst);
+ delete efst;
+ }
+
+ // mutable write/read/test
+ if (fst.Properties(kMutable, false)) {
+ MutableFst<Arc> *mfst = MutableFst<Arc>::Read(filename);
+ CHECK(mfst);
+ TestBase(*mfst);
+ TestExpanded(*mfst);
+ TestMutable(mfst);
+ delete mfst;
+ }
+ }
+
+ void TestIO() const { TestIO(*testfst_); }
+
+ private:
+ // This constructs test FSTs. Given a mutable FST, will leave
+ // the FST as follows:
+ // (I) NumStates() = nstates
+ // (II) Start() = 0
+ // (III) Final(s) = NthWeight(s)
+ // (IV) For state s:
+ // (a) NumArcs(s) == s
+ // (b) For ith arc of s:
+ // (1) ilabel = i
+ // (2) olabel = 0
+ // (3) weight = NthWeight(i)
+ // (4) nextstate = s
+ void InitFst(MutableFst<Arc> *fst, size_t nstates) const {
+ fst->DeleteStates();
+ CHECK_GT(nstates, 0);
+
+ for (StateId s = 0; s < nstates; ++s) {
+ fst->AddState();
+ fst->SetFinal(s, NthWeight(s));
+ for (size_t i = 1; i <= s; ++i) {
+ Arc arc(i, 0, NthWeight(i), s);
+ fst->AddArc(s, arc);
+ }
+ }
+
+ fst->SetStart(0);
+ }
+
+ // Generates One() + ... + One() (n times)
+ Weight NthWeight(int n) const {
+ Weight w = Weight::Zero();
+ for (int i = 0; i < n; ++i)
+ w = Plus(w, Weight::One());
+ return w;
+ }
+
+ F *testfst_; // what we're testing
+};
+
+} // namespace fst
+
+#endif // FST_TEST_FST_TEST_H_
diff --git a/src/test/weight-tester.h b/src/test/weight-tester.h
new file mode 100644
index 0000000..751e7d6
--- /dev/null
+++ b/src/test/weight-tester.h
@@ -0,0 +1,225 @@
+// weight-tester.h
+
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Copyright 2005-2010 Google, Inc.
+// Author: riley@google.com (Michael Riley)
+//
+// \file
+// Utility class for regression testing of Fst weights.
+
+#ifndef FST_TEST_WEIGHT_TESTER_H_
+#define FST_TEST_WEIGHT_TESTER_H_
+
+#include <iostream>
+#include <sstream>
+
+#include <fst/random-weight.h>
+
+namespace fst {
+
+// This class tests a variety of identities and properties that must
+// hold for the Weight class to be well-defined. It calls function object
+// WEIGHT_GENERATOR to select weights that are used in the tests.
+template<class Weight, class WeightGenerator>
+class WeightTester {
+ public:
+ WeightTester(WeightGenerator generator) : weight_generator_(generator) {}
+
+ void Test(int iterations, bool test_division = true) {
+ for (int i = 0; i < iterations; ++i) {
+ // Selects the test weights.
+ Weight w1 = weight_generator_();
+ Weight w2 = weight_generator_();
+ Weight w3 = weight_generator_();
+
+ VLOG(1) << "weight type = " << Weight::Type();
+ VLOG(1) << "w1 = " << w1;
+ VLOG(1) << "w2 = " << w2;
+ VLOG(1) << "w3 = " << w3;
+
+ TestSemiring(w1, w2, w3);
+ if (test_division)
+ TestDivision(w1, w2);
+ TestReverse(w1, w2);
+ TestEquality(w1, w2, w3);
+ TestIO(w1);
+ TestCopy(w1);
+ }
+ }
+
+ private:
+ // Note in the tests below we use ApproxEqual rather than == and add
+ // kDelta to inequalities where the weights might be inexact.
+
+ // Tests (Plus, Times, Zero, One) defines a commutative semiring.
+ void TestSemiring(Weight w1, Weight w2, Weight w3) {
+ // Checks that the operations are closed.
+ CHECK(Plus(w1, w2).Member());
+ CHECK(Times(w1, w2).Member());
+
+ // Checks that the operations are associative.
+ CHECK(ApproxEqual(Plus(w1, Plus(w2, w3)), Plus(Plus(w1, w2), w3)));
+ CHECK(ApproxEqual(Times(w1, Times(w2, w3)), Times(Times(w1, w2), w3)));
+
+ // Checks the identity elements.
+ CHECK(Plus(w1, Weight::Zero()) == w1);
+ CHECK(Plus(Weight::Zero(), w1) == w1);
+ CHECK(Times(w1, Weight::One()) == w1);
+ CHECK(Times(Weight::One(), w1) == w1);
+
+ // Check the no weight element.
+ CHECK(!Weight::NoWeight().Member());
+ CHECK(!Plus(w1, Weight::NoWeight()).Member());
+ CHECK(!Plus(Weight::NoWeight(), w1).Member());
+ CHECK(!Times(w1, Weight::NoWeight()).Member());
+ CHECK(!Times(Weight::NoWeight(), w1).Member());
+
+ // Checks that the operations commute.
+ CHECK(ApproxEqual(Plus(w1, w2), Plus(w2, w1)));
+ if (Weight::Properties() & kCommutative)
+ CHECK(ApproxEqual(Times(w1, w2), Times(w2, w1)));
+
+ // Checks Zero() is the annihilator.
+ CHECK(Times(w1, Weight::Zero()) == Weight::Zero());
+ CHECK(Times(Weight::Zero(), w1) == Weight::Zero());
+
+ // Check Power(w, 0) is Weight::One()
+ CHECK(Power(w1, 0) == Weight::One());
+
+ // Check Power(w, 1) is w
+ CHECK(Power(w1, 1) == w1);
+
+ // Check Power(w, 3) is Times(w, Times(w, w))
+ CHECK(Power(w1, 3) == Times(w1, Times(w1, w1)));
+
+ // Checks distributivity.
+ if (Weight::Properties() & kLeftSemiring)
+ CHECK(ApproxEqual(Times(w1, Plus(w2, w3)),
+ Plus(Times(w1, w2), Times(w1, w3))));
+ if (Weight::Properties() & kRightSemiring)
+ CHECK(ApproxEqual(Times(Plus(w1, w2), w3),
+ Plus(Times(w1, w3), Times(w2, w3))));
+
+ if (Weight::Properties() & kIdempotent)
+ CHECK(Plus(w1, w1) == w1);
+
+ if (Weight::Properties() & kPath)
+ CHECK(Plus(w1, w2) == w1 || Plus(w1, w2) == w2);
+
+ // Ensure weights form a left or right semiring.
+ CHECK(Weight::Properties() & (kLeftSemiring | kRightSemiring));
+
+ // Check when Times() is commutative that it is marked as a semiring.
+ if (Weight::Properties() & kCommutative)
+ CHECK(Weight::Properties() & kSemiring);
+ }
+
+ // Tests division operation.
+ void TestDivision(Weight w1, Weight w2) {
+ Weight p = Times(w1, w2);
+
+ if (Weight::Properties() & kLeftSemiring) {
+ Weight d = Divide(p, w1, DIVIDE_LEFT);
+ if (d.Member())
+ CHECK(ApproxEqual(p, Times(w1, d)));
+ CHECK(!Divide(w1, Weight::NoWeight(), DIVIDE_LEFT).Member());
+ CHECK(!Divide(Weight::NoWeight(), w1, DIVIDE_LEFT).Member());
+ }
+
+ if (Weight::Properties() & kRightSemiring) {
+ Weight d = Divide(p, w2, DIVIDE_RIGHT);
+ if (d.Member())
+ CHECK(ApproxEqual(p, Times(d, w2)));
+ CHECK(!Divide(w1, Weight::NoWeight(), DIVIDE_RIGHT).Member());
+ CHECK(!Divide(Weight::NoWeight(), w1, DIVIDE_RIGHT).Member());
+ }
+
+ if (Weight::Properties() & kCommutative) {
+ Weight d = Divide(p, w1, DIVIDE_RIGHT);
+ if (d.Member())
+ CHECK(ApproxEqual(p, Times(d, w1)));
+ }
+ }
+
+ // Tests reverse operation.
+ void TestReverse(Weight w1, Weight w2) {
+ typedef typename Weight::ReverseWeight ReverseWeight;
+
+ ReverseWeight rw1 = w1.Reverse();
+ ReverseWeight rw2 = w2.Reverse();
+
+ CHECK(rw1.Reverse() == w1);
+ CHECK(Plus(w1, w2).Reverse() == Plus(rw1, rw2));
+ CHECK(Times(w1, w2).Reverse() == Times(rw2, rw1));
+ }
+
+ // Tests == is an equivalence relation.
+ void TestEquality(Weight w1, Weight w2, Weight w3) {
+ // Checks reflexivity.
+ CHECK(w1 == w1);
+
+ // Checks symmetry.
+ CHECK((w1 == w2) == (w2 == w1));
+
+ // Checks transitivity.
+ if (w1 == w2 && w2 == w3)
+ CHECK(w1 == w3);
+ }
+
+ // Tests binary serialization and textual I/O.
+ void TestIO(Weight w) {
+ // Tests binary I/O
+ {
+ ostringstream os;
+ w.Write(os);
+ os.flush();
+ istringstream is(os.str());
+ Weight v;
+ v.Read(is);
+ CHECK_EQ(w, v);
+ }
+
+ // Tests textual I/O.
+ {
+ ostringstream os;
+ os << w;
+ istringstream is(os.str());
+ Weight v(Weight::One());
+ is >> v;
+ CHECK(ApproxEqual(w, v));
+ }
+ }
+
+ // Tests copy constructor and assignment operator
+ void TestCopy(Weight w) {
+ Weight x = w;
+ CHECK(w == x);
+
+ x = Weight(w);
+ CHECK(w == x);
+
+ x.operator=(x);
+ CHECK(w == x);
+
+ }
+
+ // Generates weights used in testing.
+ WeightGenerator weight_generator_;
+
+ DISALLOW_COPY_AND_ASSIGN(WeightTester);
+};
+
+} // namespace fst
+
+#endif // FST_TEST_WEIGHT_TESTER_H_
diff --git a/src/test/weight_test.cc b/src/test/weight_test.cc
new file mode 100644
index 0000000..54ba85d
--- /dev/null
+++ b/src/test/weight_test.cc
@@ -0,0 +1,258 @@
+// weight_test.h
+
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+// Copyright 2005-2010 Google, Inc.
+// Author: riley@google.com (Michael Riley)
+//
+// \file
+// Regression test for Fst weights.
+
+#include <cstdlib>
+#include <ctime>
+
+#include <fst/expectation-weight.h>
+#include <fst/float-weight.h>
+#include <fst/random-weight.h>
+#include "./weight-tester.h"
+
+DEFINE_int32(seed, -1, "random seed");
+DEFINE_int32(repeat, 100000, "number of test repetitions");
+
+using fst::TropicalWeight;
+using fst::TropicalWeightGenerator;
+using fst::TropicalWeightTpl;
+using fst::TropicalWeightGenerator_;
+
+using fst::LogWeight;
+using fst::LogWeightGenerator;
+using fst::LogWeightTpl;
+using fst::LogWeightGenerator_;
+
+using fst::MinMaxWeight;
+using fst::MinMaxWeightGenerator;
+using fst::MinMaxWeightTpl;
+using fst::MinMaxWeightGenerator_;
+
+using fst::StringWeight;
+using fst::StringWeightGenerator;
+
+using fst::GallicWeight;
+using fst::GallicWeightGenerator;
+
+using fst::LexicographicWeight;
+using fst::LexicographicWeightGenerator;
+
+using fst::ProductWeight;
+using fst::ProductWeightGenerator;
+
+using fst::PowerWeight;
+using fst::PowerWeightGenerator;
+
+using fst::SignedLogWeightTpl;
+using fst::SignedLogWeightGenerator_;
+
+using fst::ExpectationWeight;
+
+using fst::SparsePowerWeight;
+using fst::SparsePowerWeightGenerator;
+
+using fst::STRING_LEFT;
+using fst::STRING_RIGHT;
+
+using fst::WeightTester;
+
+template <class T>
+void TestTemplatedWeights(int repeat, int seed) {
+ TropicalWeightGenerator_<T> tropical_generator(seed);
+ WeightTester<TropicalWeightTpl<T>, TropicalWeightGenerator_<T> >
+ tropical_tester(tropical_generator);
+ tropical_tester.Test(repeat);
+
+ LogWeightGenerator_<T> log_generator(seed);
+ WeightTester<LogWeightTpl<T>, LogWeightGenerator_<T> >
+ log_tester(log_generator);
+ log_tester.Test(repeat);
+
+ MinMaxWeightGenerator_<T> minmax_generator(seed);
+ WeightTester<MinMaxWeightTpl<T>, MinMaxWeightGenerator_<T> >
+ minmax_tester(minmax_generator);
+ minmax_tester.Test(repeat);
+
+ SignedLogWeightGenerator_<T> signedlog_generator(seed);
+ WeightTester<SignedLogWeightTpl<T>, SignedLogWeightGenerator_<T> >
+ signedlog_tester(signedlog_generator);
+ signedlog_tester.Test(repeat);
+}
+
+int main(int argc, char **argv) {
+ std::set_new_handler(FailedNewHandler);
+ SetFlags(argv[0], &argc, &argv, true);
+
+ int seed = FLAGS_seed >= 0 ? FLAGS_seed : time(0);
+ LOG(INFO) << "Seed = " << seed;
+
+ TestTemplatedWeights<float>(FLAGS_repeat, seed);
+ TestTemplatedWeights<double>(FLAGS_repeat, seed);
+ FLAGS_fst_weight_parentheses = "()";
+ TestTemplatedWeights<float>(FLAGS_repeat, seed);
+ TestTemplatedWeights<double>(FLAGS_repeat, seed);
+ FLAGS_fst_weight_parentheses = "";
+
+ // Make sure type names for templated weights are consistent
+ CHECK(TropicalWeight::Type() == "tropical");
+ CHECK(TropicalWeightTpl<double>::Type() != TropicalWeightTpl<float>::Type());
+ CHECK(LogWeight::Type() == "log");
+ CHECK(LogWeightTpl<double>::Type() != LogWeightTpl<float>::Type());
+ TropicalWeightTpl<double> w(15.0);
+ TropicalWeight tw(15.0);
+
+ StringWeightGenerator<int> left_string_generator(seed);
+ WeightTester<StringWeight<int>, StringWeightGenerator<int> >
+ left_string_tester(left_string_generator);
+ left_string_tester.Test(FLAGS_repeat);
+
+ StringWeightGenerator<int, STRING_RIGHT> right_string_generator(seed);
+ WeightTester<StringWeight<int, STRING_RIGHT>,
+ StringWeightGenerator<int, STRING_RIGHT> >
+ right_string_tester(right_string_generator);
+ right_string_tester.Test(FLAGS_repeat);
+
+ typedef GallicWeight<int, TropicalWeight> TropicalGallicWeight;
+ typedef GallicWeightGenerator<int, TropicalWeightGenerator>
+ TropicalGallicWeightGenerator;
+
+ TropicalGallicWeightGenerator tropical_gallic_generator(seed);
+ WeightTester<TropicalGallicWeight, TropicalGallicWeightGenerator>
+ tropical_gallic_tester(tropical_gallic_generator);
+ tropical_gallic_tester.Test(FLAGS_repeat);
+
+ typedef ProductWeight<TropicalWeight, TropicalWeight> TropicalProductWeight;
+ typedef ProductWeightGenerator<TropicalWeightGenerator,
+ TropicalWeightGenerator> TropicalProductWeightGenerator;
+
+ TropicalProductWeightGenerator tropical_product_generator(seed);
+ WeightTester<TropicalProductWeight, TropicalProductWeightGenerator>
+ tropical_product_weight_tester(tropical_product_generator);
+ tropical_product_weight_tester.Test(FLAGS_repeat);
+
+ typedef PowerWeight<TropicalWeight, 3> TropicalCubeWeight;
+ typedef PowerWeightGenerator<TropicalWeightGenerator, 3>
+ TropicalCubeWeightGenerator;
+
+ TropicalCubeWeightGenerator tropical_cube_generator(seed);
+ WeightTester<TropicalCubeWeight, TropicalCubeWeightGenerator>
+ tropical_cube_weight_tester(tropical_cube_generator);
+ tropical_cube_weight_tester.Test(FLAGS_repeat);
+
+ typedef ProductWeight<TropicalWeight, TropicalProductWeight>
+ SecondNestedProductWeight;
+ typedef ProductWeightGenerator<TropicalWeightGenerator,
+ TropicalProductWeightGenerator> SecondNestedProductWeightGenerator;
+
+ SecondNestedProductWeightGenerator second_nested_product_generator(seed);
+ WeightTester<SecondNestedProductWeight, SecondNestedProductWeightGenerator>
+ second_nested_product_weight_tester(second_nested_product_generator);
+ second_nested_product_weight_tester.Test(FLAGS_repeat);
+
+ // This only works with fst_weight_parentheses = "()"
+ typedef ProductWeight<TropicalProductWeight, TropicalWeight>
+ FirstNestedProductWeight;
+ typedef ProductWeightGenerator<TropicalProductWeightGenerator,
+ TropicalWeightGenerator> FirstNestedProductWeightGenerator;
+
+ FirstNestedProductWeightGenerator first_nested_product_generator(seed);
+ WeightTester<FirstNestedProductWeight, FirstNestedProductWeightGenerator>
+ first_nested_product_weight_tester(first_nested_product_generator);
+
+ typedef PowerWeight<FirstNestedProductWeight, 3> NestedProductCubeWeight;
+ typedef PowerWeightGenerator<FirstNestedProductWeightGenerator, 3>
+ NestedProductCubeWeightGenerator;
+
+ NestedProductCubeWeightGenerator nested_product_cube_generator(seed);
+ WeightTester<NestedProductCubeWeight, NestedProductCubeWeightGenerator>
+ nested_product_cube_weight_tester(nested_product_cube_generator);
+
+ typedef SparsePowerWeight<NestedProductCubeWeight,
+ size_t > SparseNestedProductCubeWeight;
+ typedef SparsePowerWeightGenerator<NestedProductCubeWeightGenerator,
+ size_t, 3> SparseNestedProductCubeWeightGenerator;
+
+ SparseNestedProductCubeWeightGenerator
+ sparse_nested_product_cube_generator(seed);
+ WeightTester<SparseNestedProductCubeWeight,
+ SparseNestedProductCubeWeightGenerator>
+ sparse_nested_product_cube_weight_tester(
+ sparse_nested_product_cube_generator);
+
+ typedef SparsePowerWeight<LogWeight, size_t > LogSparsePowerWeight;
+ typedef SparsePowerWeightGenerator<LogWeightGenerator,
+ size_t, 3> LogSparsePowerWeightGenerator;
+
+ LogSparsePowerWeightGenerator
+ log_sparse_power_weight_generator(seed);
+ WeightTester<LogSparsePowerWeight,
+ LogSparsePowerWeightGenerator>
+ log_sparse_power_weight_tester(
+ log_sparse_power_weight_generator);
+
+ typedef ExpectationWeight<LogWeight, LogWeight>
+ LogLogExpectWeight;
+ typedef ProductWeightGenerator<LogWeightGenerator, LogWeightGenerator,
+ LogLogExpectWeight> LogLogExpectWeightGenerator;
+
+ LogLogExpectWeightGenerator log_log_expect_weight_generator(seed);
+ WeightTester<LogLogExpectWeight, LogLogExpectWeightGenerator>
+ log_log_expect_weight_tester(log_log_expect_weight_generator);
+
+ typedef ExpectationWeight<LogWeight, LogSparsePowerWeight>
+ LogLogSparseExpectWeight;
+ typedef ProductWeightGenerator<
+ LogWeightGenerator,
+ LogSparsePowerWeightGenerator,
+ LogLogSparseExpectWeight> LogLogSparseExpectWeightGenerator;
+
+ LogLogSparseExpectWeightGenerator log_logsparse_expect_weight_generator(seed);
+ WeightTester<LogLogSparseExpectWeight, LogLogSparseExpectWeightGenerator>
+ log_logsparse_expect_weight_tester(log_logsparse_expect_weight_generator);
+
+ // Test all product weight I/O with parentheses
+ FLAGS_fst_weight_parentheses = "()";
+ first_nested_product_weight_tester.Test(FLAGS_repeat);
+ nested_product_cube_weight_tester.Test(FLAGS_repeat);
+ log_sparse_power_weight_tester.Test(1);
+ sparse_nested_product_cube_weight_tester.Test(1);
+ tropical_product_weight_tester.Test(5);
+ second_nested_product_weight_tester.Test(5);
+ tropical_gallic_tester.Test(5);
+ tropical_cube_weight_tester.Test(5);
+ FLAGS_fst_weight_parentheses = "";
+ log_sparse_power_weight_tester.Test(1);
+ log_log_expect_weight_tester.Test(1, false); // disables division
+ log_logsparse_expect_weight_tester.Test(1, false);
+
+ typedef LexicographicWeight<TropicalWeight, TropicalWeight>
+ TropicalLexicographicWeight;
+ typedef LexicographicWeightGenerator<TropicalWeightGenerator,
+ TropicalWeightGenerator> TropicalLexicographicWeightGenerator;
+
+ TropicalLexicographicWeightGenerator tropical_lexicographic_generator(seed);
+ WeightTester<TropicalLexicographicWeight,
+ TropicalLexicographicWeightGenerator>
+ tropical_lexicographic_tester(tropical_lexicographic_generator);
+ tropical_lexicographic_tester.Test(FLAGS_repeat);
+
+ cout << "PASS" << endl;
+
+ return 0;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-05 18:21:22 +0000