/Users/dbr/ma/src/bas/lml/tarjanTable.c

Go to the documentation of this file.

#include "base.h"

#define NUM_OF_POS_TO_LOOK_BACK_IN_TARJAN_TABLE (10000)

typedef struct tTarjanTableBuildHelp{
    UINT alphabetSize;
    UINT lastPos;
    UINT symbolSize;
    const Automaton * aut;
} TarjanTableBuildHelp;

static UINT Add( TarjanTable * tt, TarjanTableBuildHelp * help, UINT state ){
    UINT numberOfTransitions, i, j, code, tr, maxCode;
    boolean posFound;
    const void * label;

    numberOfTransitions = help->aut->statesNumberOfTransitions->seq[state];
    if( numberOfTransitions == 0 ){
        return 0;
    }
    if( NUM_OF_POS_TO_LOOK_BACK_IN_TARJAN_TABLE < 0 || help->lastPos - 1 < NUM_OF_POS_TO_LOOK_BACK_IN_TARJAN_TABLE ){
        i = 1;
    }
    else{
        i = help->lastPos - NUM_OF_POS_TO_LOOK_BACK_IN_TARJAN_TABLE;
    }
    tr = help->aut->statesTransitions->seq[state];
    posFound = bFALSE;
    for( ; i + help->alphabetSize < tt->table->seqAlloced; i++ ){
        for( j = 0; j < numberOfTransitions; j++ ){
            label = mVoidSequenceElement( help->aut->transitionsLabel, tr + j );
            code = SymbolToUINT( label, help->symbolSize );
            code = mAlphabetGetCode( tt->alph, code );
            if( tt->table->seq[i + code] != NO ){
                break;
            }
        }
        if( j < numberOfTransitions ){
            continue;
        }
        posFound = bTRUE;
        break;
    }
    if( !posFound ){
        i = help->lastPos + help->alphabetSize;
        i += (i/4);

        tt->table->seq = Realloc( tt->table->seq, i, sizeof(UINT) );

        for( j = tt->table->seqAlloced; j < i; j++ ){
            tt->table->seq[j] = NO;
        }
        tt->table->seqAlloced = i;
        i = help->lastPos;
    }
    maxCode = 0;
    for( j = 0; j < numberOfTransitions; j++ ){
        label = mVoidSequenceElement( help->aut->transitionsLabel, tr + j );
        code = SymbolToUINT( label, help->symbolSize );
        code = mAlphabetGetCode( tt->alph, code );
        if( maxCode < code ){
            maxCode = code;
        }
        tt->table->seq[i+code] = tr + j;
    }
    if( tt->table->seqStored < i + help->alphabetSize ){
        tt->table->seqStored = i + help->alphabetSize;
    }
    if( help->lastPos <= i + maxCode ){
        help->lastPos = i + maxCode + 1;
    }
    return i;
}

TarjanTable * TarjanTableInit( Alphabet * alph, const Automaton * aut ){
    TarjanTableBuildHelp help;
    TarjanTable * tt;
    UINT i;


    tt = Malloc( 1, sizeof(TarjanTable) );
    tt->alph = alph;
    tt->statesTransitions = UINTSequenceInit2( mAutomatonGetStatesStored(aut), 1 );
    help.alphabetSize = mAlphabetGetSize(alph);
    if(help.alphabetSize == 0 ){
        help.alphabetSize = 1;
    }
    help.lastPos = 1;
    help.symbolSize = NO;
    switch( aut->type ){
        case AUTOMATON_TYPE_SYMBOL:
            help.symbolSize = mAutomatonGetLabelSize( aut );
            break;
        case AUTOMATON_TYPE_SYMBOL_UINT:
            help.symbolSize = mAutomatonGetLabelSize( aut ) - sizeof(UINT);
            break;
    }
    help.aut = aut;
    tt->table = UINTSequenceInit2( 4*help.alphabetSize, 1 );
    for( i = 0; i < tt->table->seqAlloced; i++ ){
        tt->table->seq[i] = NO;
    }
    tt->table->seqStored = help.alphabetSize;
    for( i = 0; i < mAutomatonGetStatesStored(aut); i++ ){
        tt->statesTransitions->seq[i] = Add( tt, &help, i );
    }
    tt->statesTransitions->seqStored = i;
    UINTSequenceShrink( tt->table );
    return tt;
}

void TarjanTableFree( TarjanTable * tt ){
    UINTSequenceFree( tt->statesTransitions );
    UINTSequenceFree( tt->table );
    Free( tt );
}

void TarjanTableWrite( const TarjanTable * tt, FILE * fp ){
    UINTSequenceWrite( tt->statesTransitions, fp );
    UINTSequenceWrite( tt->table, fp );
    AlphabetWrite( tt->alph, fp );
}

TarjanTable * TarjanTableRead( FILE * fp ){
    TarjanTable * tt;

    tt = Malloc( 1, sizeof(TarjanTable) );
    tt->statesTransitions = UINTSequenceRead( fp );
    tt->table = UINTSequenceRead( fp );
    tt->alph = AlphabetRead( fp );
    return tt;
}