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

Go to the documentation of this file.

#include "base.h"

CompressedAutomaton * CompressedAutomatonInit( UINT symbolSize ){
    CompressedAutomaton * aut;

    aut = Malloc( 1, sizeof(CompressedAutomaton) );
    aut->initialState = NO;
    aut->statesTransitions = UINTSequenceInit2( 1024, 1024 );
    aut->statesNumberOfTransitions = UINTSequenceInit2( 1024, 1024 );
    aut->statesEnd = UINTSequenceInit2( 1024, 1024 );
    aut->transitionsStart = UINTSequenceInit2( 1024, 1024 );
    aut->transitionsTo = UINTSequenceInit2( 1024, 1024 );
    aut->data = VoidSequenceInit2( symbolSize, 1024, 1024 );
    aut->tt = NULL;
    return aut;
}

void CompressedAutomatonAddState( CompressedAutomaton * aut, UINT state ){
    UINT statesStored;

    statesStored = mCompressedAutomatonGetStatesStored( aut );
    if( statesStored <= state ){
        UINT i;

        for( i = statesStored; i <= state; i++ ){
            UINTSequenceAdd( aut->statesTransitions, NO );
            UINTSequenceAdd( aut->statesNumberOfTransitions, 0 );
            UINTSequenceAdd( aut->statesEnd, NO );
        }
    }
}

void CompressedAutomatonAddTransition( CompressedAutomaton * aut, UINT stateFrom, UINT start, UINT stateTo ){
    UINT transitionsStored;

    transitionsStored = mCompressedAutomatonGetTransitionsStored( aut );
    CompressedAutomatonAddState( aut, mMAX( stateFrom, stateTo ) );
    UINTSequenceAdd( aut->transitionsStart, start );
    UINTSequenceAdd( aut->transitionsTo, stateTo );
    aut->statesNumberOfTransitions->seq[stateFrom]++;
    if( aut->statesTransitions->seq[stateFrom] == NO ){
        aut->statesTransitions->seq[stateFrom] = transitionsStored;
    }
}

void CompressedAutomatonFree( CompressedAutomaton * aut ){
    UINTSequenceFree( aut->statesTransitions );
    UINTSequenceFree( aut->statesNumberOfTransitions );
    UINTSequenceFree( aut->statesEnd );
    UINTSequenceFree( aut->transitionsStart );
    UINTSequenceFree( aut->transitionsTo );
    if( aut->data != NULL ){
        VoidSequenceFree( aut->data );
    }
    if( aut->tt != NULL ){
        if( aut->tt->alph != NULL ){
            AlphabetFree( aut->tt->alph );
        }
        TarjanTableFree( aut->tt );
    }
    Free( aut );
}

void CompressedAutomatonWrite( const CompressedAutomaton * aut, FILE * fp ){
    U8 * element;
    U8 tt;

    if( endiannessOfThisMachine != endiannessOnWrite ){
        element = (U8 *)(&(aut->initialState)); mReverseBytes( element, sizeof(UINT) )
    }
    mWriteEndianness( fp, endiannessOnWrite )
    Fwrite( &(aut->initialState), sizeof(UINT), 1, fp );
    if( endiannessOfThisMachine != endiannessOnWrite ){
        element = (U8 *)(&(aut->initialState)); mReverseBytes( element, sizeof(UINT) )
    }
    UINTSequenceWrite( aut->statesTransitions, fp );
    UINTSequenceWrite( aut->statesNumberOfTransitions, fp );
    UINTSequenceWrite( aut->statesEnd, fp );
    UINTSequenceWrite( aut->transitionsStart, fp );
    UINTSequenceWrite( aut->transitionsTo, fp );
    if( aut->data == NULL ){
        tt = 0;
        Fwrite( &tt, sizeof(U8), 1, fp );
    }
    else{
        UINT sizes[1];

        sizes[0] = aut->data->elementSize;
        tt = 1;
        Fwrite( &tt, sizeof(U8), 1, fp );
        VoidSequenceWrite( aut->data, fp, sizes, 1 );
    }
    if( aut->tt != NULL ){
        tt = 1;
        Fwrite( &tt, sizeof(U8), 1, fp );
        TarjanTableWrite( aut->tt, fp );
    }
    else{
        tt = 0;
        Fwrite( &tt, sizeof(U8), 1, fp );
    }
}

CompressedAutomaton * CompressedAutomatonRead( FILE * fp ){
    CompressedAutomaton * aut;
    U8 * element;
    UINT endianness;
    U8 tt;

    aut = (CompressedAutomaton *)Malloc( 1, sizeof(CompressedAutomaton) );
    mReadEndianness( fp, endianness )
    Fread( &(aut->initialState), sizeof(UINT), 1, fp );
    if( endiannessOfThisMachine != endianness ){
        element = (U8 *)(&(aut->initialState)); mReverseBytes( element, sizeof(UINT) )
    }
    aut->statesTransitions = UINTSequenceRead( fp );
    aut->statesNumberOfTransitions = UINTSequenceRead( fp );
    aut->statesEnd = UINTSequenceRead( fp );
    aut->transitionsStart = UINTSequenceRead( fp );
    aut->transitionsTo = UINTSequenceRead( fp );
    Fread( &tt, sizeof(U8), 1, fp );
    if( tt == 1 ){
        aut->data = VoidSequenceRead( fp );
    }
    else{
        aut->data = NULL;
    }
    Fread( &tt, sizeof(U8), 1, fp );
    if( tt == 1 ){
        aut->tt = TarjanTableRead( fp );
    }
    else{
        aut->tt = NULL;
    }
    return aut;
}

void CompressedAutomatonDumpStat( const CompressedAutomaton * aut, FILE * fp ){
    double size;

    if( aut->data != NULL ){
        fprintf( fp, "number of data symbols: %llu\n", (U64)(aut->data->seqStored) );
        fprintf( fp, "symbol size: %llu\n", (U64)(aut->data->elementSize) );
        size = aut->data->seqStored;
        size *= aut->data->elementSize;
        size /= 1024.0;
        size /= 1024.0;
        fprintf( fp, "data size: %.2f MB\n", size );
    }
    fprintf( fp, "number of states: %llu\n", (U64)mCompressedAutomatonGetStatesStored(aut) );
    fprintf( fp, "number of transitions: %llu\n", (U64)mCompressedAutomatonGetTransitionsStored(aut) );
}

void CompressedAutomatonShrink( CompressedAutomaton * aut ){
    UINTSequenceShrink( aut->statesTransitions );
    UINTSequenceShrink( aut->statesNumberOfTransitions );
    UINTSequenceShrink( aut->statesEnd );
    UINTSequenceShrink( aut->transitionsStart );
    UINTSequenceShrink( aut->transitionsTo );
    if( aut->data != NULL ){
        VoidSequenceShrink( aut->data );
    }
}

void GenerateLanguage( const CompressedAutomaton * aut, UINT state, VoidSequence * line, FILE * fp, void (*DumpSequenceOfLabels)(FILE *, const VoidSequence *, UINT), UINT encoding ){
    UINT i, j, tr, end, seqStored;

    if( aut->statesNumberOfTransitions->seq[state] == 0 ){
        DumpSequenceOfLabels( fp, line, encoding );
    }
    tr = aut->statesTransitions->seq[state];
    seqStored = line->seqStored;
    for( i = 0; i < aut->statesNumberOfTransitions->seq[state]; i++ ){
        end = aut->statesEnd->seq[aut->transitionsTo->seq[tr+i]];
        for( j = aut->transitionsStart->seq[tr+i]; j <= end; j++ ){
            VoidSequenceAdd( line, mVoidSequenceElement(aut->data, j) );
        }
        GenerateLanguage( aut, aut->transitionsTo->seq[tr+i], line, fp, DumpSequenceOfLabels, encoding );
        line->seqStored = seqStored;
    }
}

void CompressedAutomatonGenerateLanguage( const CompressedAutomaton * aut, FILE * fp, void (*DumpSequenceOfLabels)(FILE *, const VoidSequence *, UINT), UINT encoding ){
    VoidSequence * line;

    if( aut->initialState == NO ){
        return;
    }
    line = VoidSequenceInit( aut->data->elementSize );
    GenerateLanguage( aut, aut->initialState, line, fp, DumpSequenceOfLabels, encoding );
    VoidSequenceFree( line );
}

static void GenerateLeftLanguage( const CompressedAutomaton * aut,
                                  UINT state,
                                  VoidSequence * line,
                                  FILE * fp,
                                  void (*DumpSequenceOfLabels)(FILE *, const VoidSequence *, UINT),
                                  UINT encoding ){
    UINT i, j, tr, end, seqStored;

    if( aut->statesNumberOfTransitions->seq[state] == 0 ){
        DumpSequenceOfLabels( fp, line, encoding );
    }
    tr = aut->statesTransitions->seq[state];
    seqStored = line->seqStored;
    for( i = 0; i < aut->statesNumberOfTransitions->seq[state]; i++ ){
        end = aut->statesEnd->seq[aut->transitionsTo->seq[tr+i]];
        for( j = aut->transitionsStart->seq[tr+i]+1; j > end; j-- ){
            VoidSequenceAdd( line, mVoidSequenceElement(aut->data, j-1) );
        }
        GenerateLeftLanguage( aut, aut->transitionsTo->seq[tr+i], line, fp, DumpSequenceOfLabels, encoding );
        line->seqStored = seqStored;
    }
}

void CompressedLeftAutomatonGenerateLanguage( const CompressedAutomaton * aut, FILE * fp,
void (*DumpSequenceOfLabels)(FILE *, const VoidSequence *, UINT), UINT encoding ){
    VoidSequence * line;

    if( aut->initialState == NO ){
        return;
    }
    line = VoidSequenceInit( aut->data->elementSize );
    GenerateLeftLanguage( aut, aut->initialState, line, fp, DumpSequenceOfLabels, encoding );
    VoidSequenceFree( line );
}

typedef struct tCompressedAutomatonTransitionsFrom{
    CompressedAutomaton * aut;
    UINTSequence * transitionsFrom;
} CompressedAutomatonTransitionsFrom;

static SINT CmpTransitions( void * ptr, UINT t1, UINT t2 ){
    CompressedAutomatonTransitionsFrom * catf;
    SINT labelCmp;

    catf = (CompressedAutomatonTransitionsFrom *)(ptr);
    if( catf->transitionsFrom->seq[t1] < catf->transitionsFrom->seq[t2] ){
        return -1;
    }
    if( catf->transitionsFrom->seq[t1] > catf->transitionsFrom->seq[t2] ){
        return 1;
    }
    labelCmp = CmpSymbols( mVoidSequenceElement(catf->aut->data, catf->aut->transitionsStart->seq[t1]),
                           mVoidSequenceElement(catf->aut->data, catf->aut->transitionsStart->seq[t2]),
                           catf->aut->data->elementSize );
    if( labelCmp != 0 ){
        return labelCmp;
    }
    if( catf->aut->transitionsTo->seq[t1] < catf->aut->transitionsTo->seq[t2] ){
        return -1;
    }
    if( catf->aut->transitionsTo->seq[t1] > catf->aut->transitionsTo->seq[t2] ){
        return 1;
    }
    return 0;
}

static void SwapTransitions( void * ptr, UINT t1, UINT t2 ){
    CompressedAutomatonTransitionsFrom * catf;
    UINT tmp;

    catf = (CompressedAutomatonTransitionsFrom *)(ptr);
    mSwapVariables( catf->transitionsFrom->seq[t1], catf->transitionsFrom->seq[t2], tmp );
    mSwapVariables( catf->aut->transitionsStart->seq[t1], catf->aut->transitionsStart->seq[t2], tmp );
    mSwapVariables( catf->aut->transitionsTo->seq[t1], catf->aut->transitionsTo->seq[t2], tmp );
}

void CompressedAutomatonSortTransitions( CompressedAutomaton * aut, UINTSequence * transitionsFrom ){
    CompressedAutomatonTransitionsFrom catf;
    UINT i, j, q, transitionsStored;

    for( i = 0; i < mCompressedAutomatonGetStatesStored(aut); i++ ){
        aut->statesTransitions->seq[i] = NO;
        aut->statesNumberOfTransitions->seq[i] = 0;
    }
    transitionsStored = mCompressedAutomatonGetTransitionsStored( aut );
    if( transitionsStored == 0 ){
        return;
    }
    catf.aut = aut;
    catf.transitionsFrom = transitionsFrom;
    Sort( &catf, transitionsStored, CmpTransitions, SwapTransitions );
    j = 1;
    q = transitionsFrom->seq[0];
    aut->statesTransitions->seq[q] = 0;
    aut->statesNumberOfTransitions->seq[q] = 1;
    for( i = 1; i < transitionsStored; i++ ){
        if( CmpTransitions( &catf, j-1, i ) != 0 ){
            if( j != i ){
                transitionsFrom->seq[j] = transitionsFrom->seq[i];
                aut->transitionsStart->seq[j] = aut->transitionsStart->seq[i];
                aut->transitionsTo->seq[j] = aut->transitionsTo->seq[i];
            }
            if( transitionsFrom->seq[j] == q ){
                aut->statesNumberOfTransitions->seq[q]++;
            }
            else{
                q = transitionsFrom->seq[j];
                aut->statesTransitions->seq[q] = j;
                aut->statesNumberOfTransitions->seq[q] = 1;
            }
            j++;
        }
    }
    if( j < transitionsStored ){
        transitionsFrom->seqStored = j;
        aut->transitionsStart->seqStored = j;
        aut->transitionsTo->seqStored = j;
        UINTSequenceShrink( transitionsFrom );
        UINTSequenceShrink( aut->transitionsStart );
        UINTSequenceShrink( aut->transitionsTo );
    }
}

static SINT Cmp( const void * set, UINT tr, const void * object ){
    const CompressedAutomaton * a;

    a = (const CompressedAutomaton *)(set);
    return CmpSymbols( mVoidSequenceElement(a->data, a->transitionsStart->seq[tr]), object, a->data->elementSize );
}

PairState CompressedAutomatonDelta( const CompressedAutomaton * a, const PairState * state, const void * symbol ){
    PairState nextState;

    nextState.transition = NO;
    nextState.index = NO;
    if( state->transition != NO ){
        if( CmpSymbols( mVoidSequenceElement(a->data, state->index), symbol, a->data->elementSize ) != 0 ){
            return nextState;
        }
        nextState.index = state->index + 1;
        nextState.transition = state->transition;
        if( nextState.index > a->statesEnd->seq[a->transitionsTo->seq[state->transition]] ){
            nextState.transition = NO;
            nextState.index = a->transitionsTo->seq[state->transition];
        }
    }
    else{
        UINT tr;

        if( a->tt != NULL ){
            UINT code;

            code = SymbolToUINT( symbol, a->data->elementSize );
            code = mAlphabetGetCode( a->tt->alph, code );
            if( code == NO_CODE ){
                return nextState;
            }
            tr = a->tt->table->seq[a->tt->statesTransitions->seq[state->index] + code];
            if( tr == NO || a->statesNumberOfTransitions->seq[state->index] == 0 ||
                tr < a->statesTransitions->seq[state->index] || a->statesTransitions->seq[state->index] + a->statesNumberOfTransitions->seq[state->index] <= tr ){
                return nextState;
            }
        }
        else{
            tr = BinarySearch( a, a->statesTransitions->seq[state->index], a->statesNumberOfTransitions->seq[state->index], symbol, Cmp );
            if( tr == NO ){
                return nextState;
            }
        }
        nextState.index = a->transitionsStart->seq[tr] + 1;
        nextState.transition = tr;
        if( nextState.index > a->statesEnd->seq[a->transitionsTo->seq[tr]] ){
            nextState.transition = NO;
            nextState.index = a->transitionsTo->seq[tr];
        }
    }
    return nextState;
}

void CompressedAutomatonAddTarjanTable( CompressedAutomaton * aut ){
    Alphabet * alph;
    Automaton a;
    UINT i;

    a.type = AUTOMATON_TYPE_SYMBOL;
    a.statesTransitions = aut->statesTransitions;
    a.statesNumberOfTransitions = aut->statesNumberOfTransitions;
    a.transitionsTo = aut->transitionsTo;
    a.transitionsLabel = VoidSequenceInit2( aut->data->elementSize, mCompressedAutomatonGetTransitionsStored(aut), 1 );
    for( i = 0; i < mCompressedAutomatonGetTransitionsStored(aut); i++ ){
        VoidSequenceAdd( a.transitionsLabel, mVoidSequenceElement(aut->data, aut->transitionsStart->seq[i]) );
    }
    alph = AlphabetInit();
    AlphabetAdd( alph, &a );
    aut->tt = TarjanTableInit( alph, &a );
    VoidSequenceFree( a.transitionsLabel );
}

PairState CompressedAutomatonGetInitialPairState( const CompressedAutomaton * aut ){
    PairState state;

    state.transition = NO;
    state.index = aut->initialState;
    return state;
}

void CompressedAutomatonDumpGV( CompressedAutomaton * aut, FILE * fp, void (*DumpLabel)(const CompressedAutomaton *, FILE *, UINT, UINT), UINT encoding ){
    S8 tmp[MAX_INPUT_STRING_SIZE];
    UINT i, s, tr, statesStored, symbolSize;

    symbolSize = aut->data->elementSize;
    PrintString( fp, "Digraph A{ \n", symbolSize, encoding );
    PrintString( fp, "rankdir=LR;\n", symbolSize, encoding );
    statesStored = mCompressedAutomatonGetStatesStored( aut );
    PrintString( fp, "node[shape = point, color = white]; \"\";\n", symbolSize, encoding );
    PrintString( fp, "node [shape = circle, color = black];\n", symbolSize, encoding );
    sprintf( tmp, "\"\" -> %llu;\n", (U64)(aut->initialState) );
    PrintString( fp, tmp, symbolSize, encoding );
    for( s = 0; s < statesStored; s++ ){
        for( i = 0; i < aut->statesNumberOfTransitions->seq[s]; i++ ){
            tr = aut->statesTransitions->seq[s] + i;
            sprintf( tmp, "%llu -> %llu [ label = \"", (U64)(s), (U64)(aut->transitionsTo->seq[tr]) );
            PrintString( fp, tmp, symbolSize, encoding );
            DumpLabel( aut, fp, tr, encoding );
            PrintString( fp, "\" ];\n", symbolSize, encoding );
        }
    }
    PrintString( fp, "}\n", symbolSize, encoding );
}