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

Go to the documentation of this file.

#ifndef SCDAWG_C
#define SCDAWG_C

#include "base.h"

#define mRight (help->aut->right)
#define mLeft (help->aut->left)

SCDAWG * SCDAWGInit( UINT symbolSize ){
    SCDAWG * aut;

    aut = Malloc( 1, sizeof(SCDAWG) );
    aut->right = CompressedAutomatonInit( symbolSize );
    aut->left = CompressedAutomatonInit( symbolSize );
    return aut;
}

void SCDAWGFree( SCDAWG * aut ){
    CompressedAutomatonFree( aut->right );
    CompressedAutomatonFree( aut->left );
    Free( aut );
}

void SCDAWGClose( SCDAWGBuildHelp * help ){
    UINT i, j, s;

    CompressedAutomatonSortTransitions( mRight, help->right->transitionsFrom );
    for( i = 0; i < mCompressedAutomatonGetTransitionsStored(mLeft); i++ ){
        s = mLeft->transitionsTo->seq[i];
        j = mLeft->statesEnd->seq[s] - mLeft->transitionsStart->seq[i];
        s = help->leftToRight->seq[s];
        mLeft->transitionsStart->seq[i] = (mRight->statesEnd->seq[s] + 1) - help->right->statesLength->seq[s] + j;
    }
    for( i = 0; i < mCompressedAutomatonGetTransitionsStored(mLeft); i++ ){
        help->left->transitionsFrom->seq[i] = help->leftToRight->seq[help->left->transitionsFrom->seq[i]];
        mLeft->transitionsTo->seq[i] = help->leftToRight->seq[mLeft->transitionsTo->seq[i]];
    }
    for( i = 0; i < mCompressedAutomatonGetStatesStored(mLeft); i++ ){
        if( help->right->statesLength->seq[i] != 0 ){
            mLeft->statesEnd->seq[i] = (mRight->statesEnd->seq[i] + 1) - help->right->statesLength->seq[i];
        }
    }
    VoidSequenceFree( mLeft->data ); mLeft->data = mRight->data;
    CompressedAutomatonSortTransitions( mLeft, help->left->transitionsFrom );
    mLeft->data = NULL;
}

void SCDAWGShrink( SCDAWG * aut ){
    CompressedAutomatonShrink( aut->right );
    CompressedAutomatonShrink( aut->left );
}

void SCDAWGAddTarjanTable( SCDAWG * aut ){
    CompressedAutomatonAddTarjanTable( aut->right );
    aut->left->data = aut->right->data;
    CompressedAutomatonAddTarjanTable( aut->left );
    aut->left->data = NULL;
}

void SCDAWGWrite( SCDAWG * aut, FILE * fp ){
    CompressedAutomatonWrite( aut->right, fp );
    CompressedAutomatonWrite( aut->left, fp );
}

SCDAWG * SCDAWGRead( FILE * fp ){
    SCDAWG * aut;

    aut = (SCDAWG *)Malloc( 1, sizeof(SCDAWG) );
    aut->right = CompressedAutomatonRead( fp );
    aut->left = CompressedAutomatonRead( fp );
    return aut;
}

void SCDAWGDumpStat( const SCDAWG * aut, FILE * fp ){
    fprintf( fp, "right automaton:\n" );
    CompressedAutomatonDumpStat( aut->right, fp );
    fprintf( fp, "left automaton:\n" );
    CompressedAutomatonDumpStat( aut->left, fp );
    fprintf( fp, "total number of transitions: %llu\n",
    (U64)(mCompressedAutomatonGetTransitionsStored(aut->right) + mCompressedAutomatonGetTransitionsStored(aut->left)) );
}

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

    symbolSize = aut->right->data->elementSize;
    PrintString( fp, "Digraph A{ \n", symbolSize, encoding );
    PrintString( fp, "rankdir=LR;\n", symbolSize, encoding );
    statesStored = mCompressedAutomatonGetStatesStored( aut->right );
    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->right->initialState) );
    PrintString( fp, tmp, symbolSize, encoding );
    for( s = 0; s < statesStored; s++ ){
        for( i = 0; i < aut->right->statesNumberOfTransitions->seq[s]; i++ ){
            tr = aut->right->statesTransitions->seq[s] + i;
            sprintf( tmp, "%llu -> %llu [ label = \"", (U64)(s), (U64)(aut->right->transitionsTo->seq[tr]) );
            PrintString( fp, tmp, symbolSize, encoding );
            DumpLabel( aut, fp, tr, bTRUE, encoding );
            PrintString( fp, "\" ];\n", symbolSize, encoding );
        }
        for( i = 0; i < aut->left->statesNumberOfTransitions->seq[s]; i++ ){
            tr = aut->left->statesTransitions->seq[s] + i;
            sprintf( tmp, "%llu -> %llu [ style = dashed, label = \"", (U64)(s), (U64)(aut->left->transitionsTo->seq[tr]) );
            PrintString( fp, tmp, symbolSize, encoding );
            DumpLabel( aut, fp, tr, bFALSE, encoding );
            PrintString( fp, "\" ];\n", symbolSize, encoding );
        }
    }
    PrintString( fp, "}\n", symbolSize, encoding );
}

SCDAWGBuildHelp * SCDAWGBuildHelpInit( SCDAWG * aut ){
    SCDAWGBuildHelp * help;

    help = Malloc( 1, sizeof(SCDAWGBuildHelp) );
    help->aut = aut;
    help->left = CDAWGBuildHelpInit( aut->left );
    help->right = CDAWGBuildHelpInit( aut->right );
    help->leftToRight = UINTSequenceInit();
    return help;
}

void SCDAWGBuildHelpFree( SCDAWGBuildHelp * help ){
    CDAWGBuildHelpFree( help->left );
    CDAWGBuildHelpFree( help->right );
    UINTSequenceFree( help->leftToRight );
    Free( help );
}

UINT FindRightState( SCDAWGBuildHelp * help, UINT l ){
    TransitionFromStartTo tfst;
    UINT q, tr;

    q = help->left->statesSuffixLink->seq[l];
    if( help->leftToRight->seq[q] == NO ){
        help->leftToRight->seq[q] = FindRightState( help, q );
    }
    tfst.from = help->leftToRight->seq[q];
    tfst.symbol = mVoidSequenceElement( mLeft->data, mLeft->statesEnd->seq[l] - help->left->statesLength->seq[q] );
    tr = HashGetIndex( help->right->hash, &tfst );
    return mRight->transitionsTo->seq[tr];
}

void SCDAWGAdd( SCDAWGBuildHelp * help, VoidSequence * sharpDocumentDollar ){
    UINT i, numberOfStates, numberOfNewStates;

    numberOfStates = mCompressedAutomatonGetStatesStored( help->left->aut );
    CDAWGAdd( help->right, sharpDocumentDollar );
    VoidSequenceReverse( sharpDocumentDollar );
    CDAWGAdd( help->left, sharpDocumentDollar );
    
    numberOfNewStates = mCompressedAutomatonGetStatesStored( help->left->aut );
    for( i = numberOfStates; i < numberOfNewStates; i++ ){
        UINTSequenceAdd( help->leftToRight, NO );
    }
    help->leftToRight->seq[help->left->aut->initialState] = help->right->aut->initialState;
    for( i = numberOfStates; i < numberOfNewStates; i++ ){
        if( help->leftToRight->seq[i] == NO ){
            help->leftToRight->seq[i] = FindRightState( help, i );
        }
    }
}

#endif /* end of include guard: SCDAWG_C */