HfstTransducer.h

Go to the documentation of this file.

//       This program is free software: you can redistribute it and/or modify
//       it under the terms of the GNU General Publirmoc License as published by
//       the Free Software Foundation, version 3 of the License.
//
//       This program 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 General Public License for more details.
//
//       You should have received a copy of the GNU General Public License
//       along with this program.  If not, see <http://www.gnu.org/licenses/>.
#ifndef _HFST_TRANSDUCER_H_
#define _HFST_TRANSDUCER_H_

#if HAVE_CONFIG_H
#  include <config.h>
#endif

#include "FormatSpecifiers.h"

#include "HfstDataTypes.h"
#include "HfstSymbolDefs.h"
#include "implementations/HfstTransitionGraph.h"
#include "parsers/LexcCompiler.h"

#if HAVE_SFST
#include "implementations/SfstTransducer.h"
#endif

#if HAVE_OPENFST
#include "implementations/TropicalWeightTransducer.h"
#include "implementations/LogWeightTransducer.h"
#endif

#if HAVE_FOMA
#include "implementations/FomaTransducer.h"
#endif

/* Include here the header file of the files that take care 
   of the interaction between HFST and your transducer library. */
//#if HAVE_MY_TRANSDUCER_LIBRARY
//#include "implementations/MyTransducerLibraryTransducer.h"
//#endif

#include "implementations/HfstOlTransducer.h"
#include "HfstTokenizer.h"
#include "implementations/ConvertTransducerFormat.h"
#include "HfstExceptionDefs.h"
#include "HfstInputStream.h"
#include "HfstOutputStream.h"

#include <string>
#include <cassert>
#include <iostream>
#include <vector>
#include <map>
#include <set>

namespace hfst
{
  namespace implementations {    
    template <class T> class HfstTransitionGraph;
    class HfstTropicalTransducerTransitionData;
    typedef HfstTransitionGraph<HfstTropicalTransducerTransitionData> 
      HfstBasicTransducer; 
  }
  class HfstCompiler;
  class HfstTransducer;
  namespace xfst {
    class XfstCompiler;
  }
  namespace xeroxRules
  {
      class Rule;
      HfstTransducer bracketedReplace( const Rule &rule, bool optional);
  }

  using hfst::implementations::HfstOlTransducer;

#if HAVE_SFST
  using hfst::implementations::SfstTransducer;
#endif // #if HAVE_SFST

#if HAVE_OPENFST
  using hfst::implementations::TropicalWeightTransducer;
  using hfst::implementations::TropicalWeightState;
  using hfst::implementations::TropicalWeightStateIterator;
#if HAVE_OPENFST_LOG
  using hfst::implementations::LogWeightTransducer;
#endif // #if HAVE_OPENFST_LOG
#endif // #if HAVE_OPENFST

#if HAVE_FOMA
  using hfst::implementations::FomaTransducer;
#endif // #if HAVE_FOMA

  /* Add here the transducer class of your transducer library. */
  //#if HAVE_MY_TRANSDUCER_LIBRARY
  //  using hfst::implementations::MyTransducerLibraryTransducer;
  //#endif // #if HAVE_MY_TRANSDUCER_LIBRARY

  HfstFile hfst_open(const char * filename, const char * mode);
  HfstFile hfst_stdout();
  HfstFile hfst_stdin();

  // *** TESTING AND OPTIMIZATION...

  enum MinimizationAlgorithm { HOPCROFT, BRZOZOWSKI };
  /* Which minimization algorithm is used. 
     In foma, Hopcroft is always used. 
     In OpenFst and SFST, the default algorithm is Hopcroft. */
  void set_minimization_algorithm(MinimizationAlgorithm);
  MinimizationAlgorithm get_minimization_algorithm(); 

  void set_encode_weights(bool);
  bool get_encode_weights();

  /* Whether in harmonization the smaller transducer is always harmonized
     according to the bigger transducer. */
  void set_harmonize_smaller(bool);
  bool get_harmonize_smaller();

  /* Whether unknown and identity symbols are used. By default, they are used.
     These symbols are always reserved for use and included in alphabets 
     of transducers, but code optimization is possible if it is known 
     that they do not appear in transducer transitions. */
  void set_unknown_symbols_in_use(bool);
  bool get_unknown_symbols_in_use();

  // *** ...TESTING AND OPTIMIZATION


  class HfstTransducer
  {

    // ***** PROTECTED VARIABLES AND INTERFACE *****

  protected:

    /* The backend implementation type of the transducer */
    ImplementationType type; 

    bool anonymous;    // currently not used
    bool is_trie;      // currently not used
    std::string name;  /* The name of the transducer */
    std::map<std::string,std::string> props;    // rest of fst metadata
    /* The union of possible backend implementations. */
    union TransducerImplementation
    {
#if HAVE_SFST
      hfst::implementations::Transducer * sfst;
#endif
#if HAVE_OPENFST
      hfst::implementations::StdVectorFst * tropical_ofst;
#if HAVE_OPENFST_LOG
      hfst::implementations::LogFst * log_ofst;
#endif
#endif
#if HAVE_FOMA
      fsm * foma;
#endif

      /* Add here your own transducer backend implementation. */
      //#if HAVE_MY_TRANSDUCER_LIBRARY
      //      hfst::implementations::MyFst * my_transducer_library;
      //#endif

      hfst_ol::Transducer * hfst_ol;

#if HAVE_OPENFST // is this needed?
      hfst::implementations::StdVectorFst * internal;
#endif 
    };

    /* The backend implementation */
    TransducerImplementation implementation;

    /* Interfaces through which the backend implementations can be accessed */
#if HAVE_SFST
    static hfst::implementations::SfstTransducer sfst_interface;
#endif
#if HAVE_OPENFST
    static hfst::implementations::TropicalWeightTransducer 
      tropical_ofst_interface;
#if HAVE_OPENFST_LOG
    static hfst::implementations::LogWeightTransducer log_ofst_interface;
#endif
#endif
#if HAVE_FOMA
    static hfst::implementations::FomaTransducer foma_interface;
#endif
    static hfst::implementations::HfstOlTransducer hfst_ol_interface;

    /* Add here the class that takes care of the interaction between
       HFST and your transducer library. */
    //#if HAVE_MY_TRANSDUCER_LIBRARY
    //static hfst::implementations::MyTransducerLibraryTransducer
    //  my_transducer_library_interface;
    //#endif

    /* The same as harmonize but does not change \a another but
       returns a harmonized version of that. If this and \a another 
       have type FOMA_TYPE, NULL is returned. */
    HfstTransducer * harmonize_(const HfstTransducer &another);

    HfstTransducer * harmonize_symbol_encodings(const HfstTransducer &another);

    /* Check if transducer \a another has in its alphabet flag diacritics
       that are not found in the alphabet of this transducer and insert
       all missing flag diacritics to \a missing_flags. 
       \a return_on_first_miss defines whether the function returns as soon as
       a missing flag is found so that only that flag is inserted to
       \a missing flags. */
    bool check_for_missing_flags_in(const HfstTransducer &another,
                                    StringSet &missing_flags,
                                    bool return_on_first_miss) const;

    /* Disjunct trie transducers efficiently so that the result is also
       a trie.
       Currently not implemented, TODO */
    HfstTransducer &disjunct_as_tries(HfstTransducer &another,
                                      ImplementationType type);  


    /* Remove paths where @..._2@ transitions immediately preceede 
       @..._1@ transitions, i.e. transitions resulting from incorrect
       ordering of flag diacritics. */
    HfstTransducer &remove_illegal_flag_paths(void);

    /* Whether the conversion requested can be done without losing 
       any information */
    static bool is_safe_conversion(ImplementationType original,
                                   ImplementationType conversion);


    /* For internal use */
    static HfstTransducer &read_in_att_format
      (FILE *ifile, ImplementationType type, const std::string &epsilon_symbol);

  public:
    /* whether HFST is linked to the transducer library 
       needed by implementation type \a type. */
    static bool is_implementation_type_available(ImplementationType type);

    unsigned int number_of_states() const;
    unsigned int number_of_arcs() const;

  protected:
    /* For internal use: Create a tokenizer that recognizes all symbols 
       that occur in the transducer. */
    HfstTokenizer create_tokenizer();

    /* For internal use. Implemented only for SFST_TYPE.
       Get all symbol pairs that occur in the transitions of the transducer. */
    StringPairSet get_symbol_pairs();

  protected:

    /* Get the number used to represent the symbol \a symbol. */
    unsigned int get_symbol_number(const std::string &symbol);
    
    /* For internal use, implemented only for SFST_TYPE. */          
    std::vector<HfstTransducer*> extract_path_transducers();

    /* For internal use:
       Create a new transducer equivalent to \a t in format \a type. */
    static HfstTransducer &convert
      (const HfstTransducer &t, ImplementationType type);

    /* For internal use:
       Create an HfstBasicTransducer equivalent to \a t end delete
       the backend implementation of \a t. */
    implementations::HfstBasicTransducer * convert_to_basic_transducer();

    /* For internal use:
       Create an HfstBasicTransducer equivalent to \a t. */
    implementations::HfstBasicTransducer * get_basic_transducer() const;

    /* For internal use:
       Create a backend implementation of the same type that this transducer
       has and that is equivalent to \a t and delete \a t. Assign the 
       backend implementation as the value of the implementation of this
       transducer. */
    HfstTransducer &convert_to_hfst_transducer
      (implementations::HfstBasicTransducer *t);

    /* \brief For internal use: Create a transducer of type \a type as 
       defined in AT&T format in file named \a filename.
       \a epsilon_symbol defines how epsilons are represented.

        NOTE: If the transition symbols contain space characters
        they must be represented as "@_SPACE_@" because
        whitespace characters are used as field separators 
        in AT&T format.

       @pre The file exists, otherwise an exception is thrown.
       @see HfstTransducer(FILE, ImplementationType, const std::string&)
       @throws StreamNotReadableException 
       @throws NotValidAttFormatException 
    */
    static HfstTransducer &read_in_att_format
      (const std::string &filename, ImplementationType type, 
       const std::string &epsilon_symbol);


    /* For debugging */
  public:
    void print_alphabet();
  protected:
    static float get_profile_seconds(ImplementationType type);

#include "hfst_apply_schemas.h"



    // ***** THE PUBLIC INTERFACE *****

  public:


    // ------------------------------------------------
    // ----- Constructors, destructor, assignment -----
    // ------------------------------------------------

    HfstTransducer();

    HfstTransducer(ImplementationType type);

    HfstTransducer(const std::string& utf8_str, 
           const HfstTokenizer &multichar_symbol_tokenizer,
                   ImplementationType type);

    HfstTransducer(const std::string& input_utf8_str,
                   const std::string& output_utf8_str,
                   const HfstTokenizer &multichar_symbol_tokenizer,
                   ImplementationType type);

    /* @brief Create a transducer that recognizes the union of string pairs in 
       \a sps. The type of the transducer is defined by \a type. \a cyclic
       defines whether the transducer recognizes any number (from zero to
       infinity, inclusive) of consecutive string pairs in \s sps. */
    HfstTransducer(const StringPairSet & sps, ImplementationType type, 
                   bool cyclic=false);

    /* \brief Create a transducer that recognizes the concatenation of
       string pairs in \a spv. The type of the transducer is defined
       by \a type. */
    HfstTransducer(const StringPairVector & spv, ImplementationType type);

    /* \brief Create a transducer that recognizes the concatenation of the 
       unions of string pairs in string pair sets in \a spsv. The type of
       the transducer is defined by \a type. */
    HfstTransducer(const std::vector<StringPairSet> & spsv, 
                   ImplementationType type);

    HfstTransducer(HfstInputStream &in);

    HfstTransducer(const HfstTransducer &another);

    HfstTransducer(const hfst::implementations::HfstBasicTransducer &t, 
                   ImplementationType type);

    HfstTransducer(const std::string &symbol, ImplementationType type);

    HfstTransducer(const std::string &isymbol, const std::string &osymbol, 
                   ImplementationType type);

    HfstTransducer(FILE * ifile, ImplementationType type, 
                   const std::string &epsilon_symbol, unsigned int & linecount);

    HfstTransducer(FILE * ifile, ImplementationType type, 
                   const std::string &epsilon_symbol);

    HfstTransducer(HfstFile &ifile, ImplementationType type, 
                   const std::string &epsilon_symbol);


    virtual ~HfstTransducer(void);

    HfstTransducer &operator=(const HfstTransducer &another);

    HfstTransducer &assign(const HfstTransducer &another);

    // ------------------------------------------------------------
    // ----------- Properties, comparison, conversion -------------
    // ------------------------------------------------------------

    void set_name(const std::string &name);

    std::string get_name() const;

    void set_property(const std::string& property, const std::string& value);
    
    std::string get_property(const std::string& property) const;
    const std::map<std::string,std::string>& get_properties() const;
    StringSet get_alphabet() const;

    StringSet get_first_input_symbols() const;

    void harmonize(HfstTransducer &another);

    void insert_to_alphabet(const std::string &symbol); 
    void insert_to_alphabet(const std::set<std::string> &symbols); 

    void remove_from_alphabet(const std::string &symbol);
    void remove_from_alphabet(const std::set<std::string> &symbols);

    HfstTransducer &prune_alphabet(bool force=true);

    bool is_cyclic(void) const;

    bool is_automaton(void) const;

    ImplementationType get_type(void) const;

    bool compare(const HfstTransducer &another, bool harmonize=true) const;

    HfstTransducer &convert(ImplementationType type, std::string options="");


    // --------------------------------------------------------
    // --- String lookup and conversion to/from AT&T format ---
    // --------------------------------------------------------

    void write_in_att_format(FILE * ofile, bool write_weights=true) const;

    void write_in_att_format(HfstFile & ofile, bool write_weights=true) const;

    void write_in_att_format(char * buffer, bool write_weights=true) const;

    void write_in_att_format_number
      (FILE * ofile, bool write_weights=true) const;


    void write_in_att_format(const std::string &filename, 
                             bool write_weights=true) const;

  public:
    /* \brief Call \a callback with some or all string pairs recognized 
       by the transducer?

        If the callback returns false the search will be terminated. 
        The \a cycles parameter
        indicates how many times a cycle will be followed, with negative numbers
        indicating unlimited. Note that if the transducer is cyclic and 
        cycles aren't capped,
        the search will not end until the callback returns false. */
    void extract_paths(ExtractStringsCb& callback, int cycles=-1) const;

    void extract_paths
      (HfstTwoLevelPaths &results, int max_num=-1, int cycles=-1) const;

    void extract_random_paths
      (HfstTwoLevelPaths &results, int max_num) const;

    void extract_random_paths_fd
      (HfstTwoLevelPaths &results, int max_num, bool filter_fd) const;

    /* \brief Call \a callback with extracted strings that are not 
       invalidated by flag diacritic rules.

       @see extract_paths(HfstTwoLevelPaths&, int, int) */
    void extract_paths_fd
      (ExtractStringsCb& callback, int cycles=-1, bool filter_fd=true) const;

    // todo: handle flag diacritics
    // todo: throw TransducerIsCyclicException, if cyclic
    void extract_shortest_paths
      (HfstTwoLevelPaths &results) const;
    
    bool extract_longest_paths
      (HfstTwoLevelPaths &results, bool obey_flags=true /*,bool show_flags=false*/) const;

    int longest_path_size(bool obey_flags=true) const;

  public:
    void extract_paths_fd
      (HfstTwoLevelPaths &results, int max_num=-1, int cycles=-1, 
       bool filter_fd=true) const;

    HfstOneLevelPaths * lookup(const StringVector& s,
                   ssize_t limit = -1) const;

    HfstOneLevelPaths * lookup(const std::string & s,
                   ssize_t limit = -1) const;

    HfstOneLevelPaths * lookup_fd(const StringVector& s,
                  ssize_t limit = -1) const;

    HfstOneLevelPaths * lookup_fd(const std::string& s,
                  ssize_t limit = -1) const;

    HfstOneLevelPaths * lookup(const HfstTokenizer& tok,
                   const std::string &s, ssize_t limit = -1) const;

    HfstOneLevelPaths * lookup_fd(
    const HfstTokenizer& tok,
    const std::string &s, ssize_t limit = -1) const;

    HfstOneLevelPaths * lookdown(const StringVector& s,
                 ssize_t limit = -1) const;

    HfstOneLevelPaths * lookdown(const std::string& s,
                 ssize_t limit = -1) const;

    HfstOneLevelPaths * lookdown_fd(StringVector& s,
                    ssize_t limit = -1) const;

    HfstOneLevelPaths * lookdown_fd(const std::string& s,
                    ssize_t limit = -1) const;

    bool is_lookup_infinitely_ambiguous(const StringVector & s) const;
    bool is_lookup_infinitely_ambiguous(const std::string & s) const;

    bool is_lookdown_infinitely_ambiguous(const StringVector& s) const;

    bool is_infinitely_ambiguous() const ;


    // -------------------------------------------
    // --------- Optimization operations ---------
    // -------------------------------------------

    HfstTransducer &eliminate_flags();
    HfstTransducer &eliminate_flag(const std::string &flag);

    HfstTransducer &remove_epsilons();

    HfstTransducer &prune();

    HfstTransducer &determinize();

    HfstTransducer &minimize();

    HfstTransducer &n_best(unsigned int n);


    // ------------------------------------------------
    // ------------- Algebraic operations -------------
    // ------------------------------------------------

    HfstTransducer &repeat_star();

    HfstTransducer &repeat_plus();

    HfstTransducer &repeat_n(unsigned int n);

    HfstTransducer &repeat_n_minus(unsigned int n);

    HfstTransducer &repeat_n_plus(unsigned int n);

    HfstTransducer& repeat_n_to_k(unsigned int n, unsigned int k);

    HfstTransducer &optionalize();

    HfstTransducer &invert();

    HfstTransducer &reverse();

    HfstTransducer &input_project();

    HfstTransducer &output_project();

    HfstTransducer &compose(const HfstTransducer &another, 
                            bool harmonize=true);

    HfstTransducer &compose_intersect(const HfstTransducerVector &v,
                                      bool invert=false, bool harmonize=true);

    HfstTransducer &concatenate(const HfstTransducer &another, bool harmonize=true);

    HfstTransducer &disjunct(const HfstTransducer &another, bool harmonize=true);

    HfstTransducer &priority_union(const HfstTransducer &another, bool harmonize=true);


    HfstTransducer &lenient_composition(const HfstTransducer &another, bool harmonize=true);

    HfstTransducer &cross_product(const HfstTransducer &another, bool harmonize=true);


    /*
     *  \brief Shuffle this transducer with transducer \@ another.
     *
     *  If transducer A accepts string "foo" and transducer B string "bar",
     *  the transducer that results from shuffling A and B accepts all strings
     *  [(f|b)(o|a)(o|r)].
     *  
     *  @pre Both transducers must be automata, i.e. map strings onto themselves.
     *
     */
    HfstTransducer &shuffle(const HfstTransducer &another, bool harmonize=true);

    static HfstTransducer universal_pair ( ImplementationType type );

    static HfstTransducer identity_pair ( ImplementationType type );





    /* For HfstCompiler: Optimized disjunction function. */
    HfstTransducer &disjunct(const StringPairVector &spv);

    HfstTransducer &intersect(const HfstTransducer &another, bool harmonize=true);

    HfstTransducer &subtract(const HfstTransducer &another, bool harmonize=true);


    // ------------------------------------------------
    // ---------- Insertion and substitution ----------
    // ------------------------------------------------

    HfstTransducer &insert_freely(const StringPair &symbol_pair, bool harmonize=true);

    HfstTransducer &insert_freely(const HfstTransducer &tr, bool harmonize=true);

  HfstTransducer &substitute
  (bool (*func)(const StringPair &sp, StringPairSet &sps));

    HfstTransducer &substitute(const std::string &old_symbol,
                               const std::string &new_symbol,
                               bool input_side=true,
                               bool output_side=true);
                                                      
    HfstTransducer &substitute(const StringPair &old_symbol_pair,
                               const StringPair &new_symbol_pair);

    HfstTransducer &substitute(const StringPair &old_symbol_pair,
                               const StringPairSet &new_symbol_pair_set);

    HfstTransducer &substitute(const HfstSymbolSubstitutions &substitutions);

    HfstTransducer &substitute_symbols(const HfstSymbolSubstitutions &substitutions);

    HfstTransducer &substitute(const HfstSymbolPairSubstitutions &substitutions);

    HfstTransducer &substitute_symbol_pairs(const HfstSymbolPairSubstitutions &substitutions);

    HfstTransducer &substitute(const StringPair &symbol_pair,
                               HfstTransducer &transducer, bool harmonize=true);

    // -----------------------------------------------
    // --------------- Weight handling --------------- 
    // -----------------------------------------------

    HfstTransducer &set_final_weights(float weight, bool increment=false);

    HfstTransducer &transform_weights(float (*func)(float));

    HfstTransducer &push_weights(PushType type);


    static HfstTransducer * read_lexc_ptr(const std::string &filename,
                                          ImplementationType type,
                                          bool verbose);

    static HfstTransducer read_lexc(const std::string &filename,
                                    ImplementationType type,
                                    bool verbose);

    // *** For commandline programs. ***

    /* For each flag diacritic fd that is included in the alphabet of
       transducer \a another but not in the alphabet of this transducer,
       insert freely a transition fd:fd in this transducer. */
    void insert_freely_missing_flags_from
      (const HfstTransducer &another);

    /*
      If both \a this and \a another contain flag diacritics, replace flag
      diacritic @X.Y.(.Z)@ by @X.Y_1(.Z)@ in \a this and replace it by
      @X.Y_2(.Z)@ in \a another. 
      
      If \a insert_renamed_flags is true, then the flags from \a this are 
      inserted freely in \a another and vice versa after replacing.
     */
    void harmonize_flag_diacritics(HfstTransducer &another,
                                   bool insert_renamed_flags=true);
    
    void insert_missing_symbols_to_alphabet_from(const HfstTransducer &another, bool only_special_symbols=false);

    static bool is_special_symbol(const std::string & symbol);
    
    /* Whether the alphabet of transducer \a another includes flag diacritics
       that are not included in the alphabet of this transducer. */
    bool check_for_missing_flags_in(const HfstTransducer &another) const;

    /* Return true if \a this has flag diacritics in the alphabet. */
    bool has_flag_diacritics(void) const;

    

    // *** Friends **** //

    friend std::ostream& operator<<(std::ostream &out, const HfstTransducer &t);
    friend std::ostream& redirect(std::ostream &out, const HfstTransducer &t);
    friend class HfstInputStream;
    friend class HfstOutputStream;
    friend class hfst::implementations::HfstTransitionGraph<class C>;
    friend class HfstCompiler;
    friend class hfst::implementations::ConversionFunctions;
    friend class HfstGrammar;
    friend class xfst::XfstCompiler;
    //friend HfstTransducer bracketedReplace( const hfst::xeroxRules::Rule &rule, bool optional);
    friend hfst::HfstTransducer hfst::xeroxRules::bracketedReplace(const hfst::xeroxRules::Rule&, bool);
  };

  std::ostream &operator<<(std::ostream &out,const HfstTransducer &t);

  std::ostream &redirect(std::ostream &out,const HfstTransducer &t);

  namespace rules
  {
    enum ReplaceType {REPL_UP, REPL_DOWN, REPL_RIGHT, REPL_LEFT,
              REPL_DOWN_KARTTUNEN};
    enum TwolType {twol_right, twol_left, twol_both};

    /* helping methods */
    HfstTransducer universal_fst
      (const StringPairSet &alphabet, ImplementationType type);
    HfstTransducer negation_fst
      (const HfstTransducer &t, const StringPairSet &alphabet);

    HfstTransducer replace
      (HfstTransducer &t, ReplaceType repl_type, bool optional, 
       StringPairSet &alphabet);
    HfstTransducer replace_transducer
      (HfstTransducer &t, std::string lm, std::string rm, 
       ReplaceType repl_type, StringPairSet &alphabet);
    HfstTransducer replace_context
      (HfstTransducer &t, std::string m1, std::string m2, 
       StringPairSet &alphabet);
    HfstTransducer replace_in_context
      (HfstTransducerPair &context, ReplaceType repl_type, 
       HfstTransducer &t, bool optional, StringPairSet &alphabet);

    /* Used by hfst-calculate. */
    HfstTransducer restriction
      (HfstTransducerPairVector &contexts, HfstTransducer &mapping, 
       StringPairSet &alphabet,        TwolType twol_type, int direction ); 



    // ***** THE PUBLIC INTERFACE *****

    HfstTransducer two_level_if(HfstTransducerPair &context, 
                                StringPairSet &mappings, 
                                StringPairSet &alphabet);
    
    HfstTransducer two_level_only_if(HfstTransducerPair &context, 
                                     StringPairSet &mappings, 
                                     StringPairSet &alphabet);

    HfstTransducer two_level_if_and_only_if(HfstTransducerPair &context, 
                                            StringPairSet &mappings, 
                                            StringPairSet &alphabet);


    HfstTransducer replace_up(HfstTransducerPair &context, 
                              HfstTransducer &mapping, 
                              bool optional, 
                              StringPairSet &alphabet);

    HfstTransducer replace_down(HfstTransducerPair &context, 
                                HfstTransducer &mapping, 
                                bool optional, 
                                StringPairSet &alphabet);

    HfstTransducer replace_down_karttunen(HfstTransducerPair &context, 
                      HfstTransducer &mapping, 
                      bool optional, 
                      StringPairSet &alphabet);

    HfstTransducer replace_right(HfstTransducerPair &context, 
                                 HfstTransducer &mapping, 
                                 bool optional, 
                                 StringPairSet &alphabet);

    HfstTransducer replace_left(HfstTransducerPair &context, 
                                HfstTransducer &mapping, 
                                bool optional, 
                                StringPairSet &alphabet);


    HfstTransducer replace_up(HfstTransducer &mapping, 
                              bool optional, 
                              StringPairSet &alphabet);

    HfstTransducer replace_down(HfstTransducer &mapping, 
                                bool optional, 
                                StringPairSet &alphabet);

    HfstTransducer left_replace_up(     HfstTransducer          &mapping,
                                    bool                optional,
                                    StringPairSet       &alphabet);

    HfstTransducer left_replace_up( HfstTransducerPair  &context,
                                    HfstTransducer      &mapping,
                                    bool                optional,
                                    StringPairSet       &alphabet);
    HfstTransducer left_replace_down(HfstTransducerPair &context,
                                         HfstTransducer         &mapping,
                                         bool                           optional,
                                         StringPairSet          &alphabet);

    HfstTransducer left_replace_down_karttunen( HfstTransducerPair      &context,
                                                                                HfstTransducer          &mapping,
                                                                                bool                            optional,
                                                                                StringPairSet           &alphabet);

    HfstTransducer left_replace_left(HfstTransducerPair &context,
                                         HfstTransducer         &mapping,
                                         bool                           optional,
                                         StringPairSet          &alphabet);

    HfstTransducer left_replace_right(HfstTransducerPair        &context,
                                          HfstTransducer                &mapping,
                                          bool                          optional,
                                          StringPairSet         &alphabet);





    HfstTransducer restriction(HfstTransducerPairVector &contexts, 
                               HfstTransducer &mapping, 
                               StringPairSet &alphabet);

    HfstTransducer coercion(HfstTransducerPairVector &contexts, 
                            HfstTransducer &mapping, 
                            StringPairSet &alphabet);

    HfstTransducer restriction_and_coercion(HfstTransducerPairVector &contexts,
                                            HfstTransducer &mapping, 
                                            StringPairSet &alphabet);

    HfstTransducer surface_restriction(HfstTransducerPairVector &contexts, 
                                       HfstTransducer &mapping, 
                                       StringPairSet &alphabet);

    HfstTransducer surface_coercion(HfstTransducerPairVector &contexts, 
                                    HfstTransducer &mapping, 
                                    StringPairSet &alphabet);

    HfstTransducer surface_restriction_and_coercion
      (HfstTransducerPairVector &contexts, 
       HfstTransducer &mapping, 
       StringPairSet &alphabet);

    HfstTransducer deep_restriction(HfstTransducerPairVector &contexts, 
                                    HfstTransducer &mapping, 
                                    StringPairSet &alphabet);

    HfstTransducer deep_coercion(HfstTransducerPairVector &contexts, 
                                 HfstTransducer &mapping, 
                                 StringPairSet &alphabet);

    HfstTransducer deep_restriction_and_coercion
      (HfstTransducerPairVector &contexts, 
       HfstTransducer &mapping, 
       StringPairSet &alphabet);
  }

}


// vim: set ft=cpp.doxygen:
#endif // #ifndef _HFST_TRANSDUCER_H_