UT/UT_FSA.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * Produced by:
 *      Side Effects Software Inc
 *      123 Front Street West, Suite 1401
 *      Toronto, Ontario
 *      Canada   M5J 2M2
 *      416-504-9876
 *
 * NAME:        UT_FSA.h ( UT Library, C++)
 *
 * COMMENTS:    Finite State Automata String Table
 *      This table takes a fixed set of strings and creates a FSA which is used
 *      for scanning the table.  The integer value associated with each string
 *      can be found quite quickly.  As well, a search for a string not in the
 *      table is especially efficient.
 *      
 *      The string table used to build the FSA can be destroyed after the table
 *      is constructed, unless, on the odd chance, you want to find out what
 *      strings are stored in the table.
 */

#ifndef __UT_FSA__
#define __UT_FSA__

#include "UT_API.h"
#include <SYS/SYS_Types.h>

class UT_StringArray;
class UT_IntArray;
class UT_WorkBuffer;
class ut_fsa_node;

class UT_API ut_FSA_Token {
public:
    ut_FSA_Token(int id=0, const char *token=0)
    {
         myId = id;
         myToken = token;
    }
    ~ut_FSA_Token() { }

    void         set(int id, const char *token)
                 {
                     myToken = token;
                     myId = id;
                 }
    int          getId() const          { return myId; }
    const char  *getToken() const       { return myToken; }
private:
    const char  *myToken;
    int          myId;
};

class UT_API UT_FSA {
public:
     UT_FSA();
    ~UT_FSA();

    bool        build(const UT_StringArray &strings, const UT_IntArray &indices,
                        int notfound_index = -1);
    bool        build(int ntokens, const ut_FSA_Token tokens[],
                        int notfound_index=-1);
    void        clear();

    int         findSymbol(const char *symbol) const;
    int         getNotFound() const     { return myNotFound; }

    int64       getMemUsage() const;

    void        dumpTables() const;

    // This method is used for validation.  It is kind of expensive since it
    // iterates over the entire space of the FSA for extraction.
    void        extractStrings(UT_StringArray &list) const;

private:
    void         resolveTree(ut_fsa_node *head);

    int         *myAccept;                      // Acceptance states
    int         *myNexts;                       // Transition table
    int         *myValidate;                    // Verification states
    int          myNSize, myVSize, myASize;     // Sizes of arrays
    int          myNotFound;
};

#endif

---