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

Go to the documentation of this file.

#include "base.h"

static UINT GetIndexOfTransition( void * ptr, const void * object ){
    SuffixTreeBuildHelp * help;
    TransitionFromStartTo * tr;
    UINT index;

    help = (SuffixTreeBuildHelp *)(ptr);
    index = mCompressedAutomatonGetTransitionsStored( help->aut );
    tr = (TransitionFromStartTo *)(object);
    UINTSequenceAdd( help->transitionsFrom, tr->from );
    CompressedAutomatonAddTransition( help->aut, tr->from, tr->start, tr->to );
    return index;
}

static UINT GetFirstIndex( void * ptr ){
    SuffixTreeBuildHelp * help;

    help = (SuffixTreeBuildHelp *)(ptr);
    if( mCompressedAutomatonGetTransitionsStored( help->aut ) == 0 ){
        return NO;
    }
    return 0;
}

static UINT GetNextIndex( void * ptr, UINT index ){
    SuffixTreeBuildHelp * help;

    help = (SuffixTreeBuildHelp *)(ptr);
    index++;
    if( index < mCompressedAutomatonGetTransitionsStored( help->aut ) ){
        return index;
    }
    return NO;
}

static boolean Equals( void * ptr, const void * object, UINT index ){
    SuffixTreeBuildHelp * help;
    TransitionFromStartTo * tr;

    help = (SuffixTreeBuildHelp *)(ptr);
    tr = (TransitionFromStartTo *)(object);
    return( help->transitionsFrom->seq[index] == tr->from &&
            CmpSymbols( mVoidSequenceElement(help->aut->data, help->aut->transitionsStart->seq[index]), tr->symbol, help->aut->data->elementSize ) == 0 );
}

static UINT HashCode( void * ptr, const void * object, UINT hashSize ){
    SuffixTreeBuildHelp * help;
    TransitionFromStartTo * tr;

    help = (SuffixTreeBuildHelp *)(ptr);
    tr = (TransitionFromStartTo *)(object);
    return CodeBytes( CodeUINT( 0, tr->from, hashSize ), tr->symbol, help->aut->data->elementSize, hashSize );
}

static UINT HashCode2( void * ptr, UINT index, UINT hashSize ){
    SuffixTreeBuildHelp * help;

    help = (SuffixTreeBuildHelp *)(ptr);
    return CodeBytes( CodeUINT( 0, help->transitionsFrom->seq[index], hashSize ),
                      mVoidSequenceElement( help->aut->data, help->aut->transitionsStart->seq[index] ),
                      help->aut->data->elementSize,
                      hashSize );
}

SuffixTreeBuildHelp * SuffixTreeBuildHelpInit( CompressedAutomaton * aut ){
    SuffixTreeBuildHelp * help;

    help = Malloc( 1, sizeof(SuffixTreeBuildHelp) );
    help->aut = aut;
    help->statesSuffixLink = UINTSequenceInit2( aut->statesTransitions->seqAlloced, 1024 );
    help->transitionsFrom = UINTSequenceInit2( aut->transitionsStart->seqAlloced, 1024 );
    help->hash = HashInit( help, GetIndexOfTransition, GetFirstIndex, GetNextIndex, Equals, HashCode, HashCode2 );
    help->symbol = Malloc( 1, aut->data->elementSize );
    return help;
}

void SuffixTreeBuildHelpFree( SuffixTreeBuildHelp * help ){
    UINTSequenceFree( help->statesSuffixLink );
    UINTSequenceFree( help->transitionsFrom );
    HashFree( help->hash );
    Free( help->symbol );
    Free( help );
}

static PairState Delta( SuffixTreeBuildHelp * help, const PairState * state, const void * symbol ){
    PairState nextState;
    CompressedAutomaton * a;

    a = help->aut;
    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{
        TransitionFromStartTo tfst;
        UINT tr;

        tfst.from = state->index;
        tfst.symbol = symbol;
        tr = HashGetIndex( help->hash, &tfst );
        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;
}

static UINT NewState( SuffixTreeBuildHelp * help ){
    UINT newState;

    newState = mCompressedAutomatonGetStatesStored( help->aut );
    CompressedAutomatonAddState( help->aut, newState );
    UINTSequenceAdd( help->statesSuffixLink, NO );
    return newState;
}

static boolean TestAndSplit( SuffixTreeBuildHelp * help, const PairState * state, UINT i, UINT * r ){
    PairState nextState;
    UINT newState, to;
    TransitionFromStartTo tfst;

    nextState = Delta( help, state, mVoidSequenceElement(help->aut->data, i) );
    if( nextState.index != NO ){
        return bTRUE;
    }
    if( state->transition == NO ){
        (*r) = state->index;
        return bFALSE;
    }
    newState = NewState( help );
    help->aut->statesEnd->seq[newState] = state->index - 1;
    to = help->aut->transitionsTo->seq[state->transition];
    help->aut->transitionsTo->seq[state->transition] = newState;
    tfst.from = newState;
    tfst.start = state->index;
    tfst.to = to;
    memcpy( help->symbol, mVoidSequenceElement(help->aut->data, state->index), help->aut->data->elementSize );
    tfst.symbol = help->symbol;
    HashAdd( help->hash, &tfst );
    (*r) = newState;
    return bFALSE;
}

static PairState SuffixLink( SuffixTreeBuildHelp * help, const PairState * state ){
    PairState fState;
    TransitionFromStartTo tfst;
    UINT s, start, end, tr, startTr, endTr;

    if( state->transition == NO ){
        fState.transition = NO;
        fState.index = help->statesSuffixLink->seq[state->index];
        return fState;
    }
    s = help->transitionsFrom->seq[state->transition];
    start = help->aut->transitionsStart->seq[state->transition];
    end = state->index - 1;
    if( s == help->aut->initialState ){
        start++;
        if( start > end ){
            return CompressedAutomatonGetInitialPairState( help->aut );
        }
    }
    else{
        s = help->statesSuffixLink->seq[s];
    }
    while( bTRUE ){
        tfst.from = s;
        tfst.symbol = mVoidSequenceElement( help->aut->data, start );
        tr = HashGetIndex( help->hash, &tfst );
        startTr = help->aut->transitionsStart->seq[tr];
        endTr = help->aut->statesEnd->seq[help->aut->transitionsTo->seq[tr]];
        if( end - start < endTr - startTr ){
            fState.index = startTr + end - start + 1;
            fState.transition = tr;
            break;
        }
        if( end - start == endTr - startTr ){
            fState.index = help->aut->transitionsTo->seq[tr];
            fState.transition = NO;
            break;
        }
        s = help->aut->transitionsTo->seq[tr];
        start += (endTr - startTr + 1);
    }
    return fState;
}

static PairState Update( SuffixTreeBuildHelp * help, const PairState * state, UINT i ){
    PairState state_with_i;
    UINT r, newState, prevr;
    TransitionFromStartTo tfst;

    state_with_i = (*state);
    prevr = help->aut->initialState;
    while( !TestAndSplit( help, &state_with_i, i, &r ) ){
        newState = NewState( help );
        help->aut->statesEnd->seq[newState] = help->aut->data->seqStored - 1;
        tfst.from = r;
        tfst.start = i;
        tfst.to = newState;
        memcpy( help->symbol, mVoidSequenceElement(help->aut->data, i), help->aut->data->elementSize );
        tfst.symbol = help->symbol;
        HashAdd( help->hash, &tfst );
        if( prevr != help->aut->initialState ){
            help->statesSuffixLink->seq[prevr] = r;
        }
        if( state_with_i.transition == NO && state_with_i.index == help->aut->initialState ){
            return state_with_i;
        }
        prevr = r;
        state_with_i = SuffixLink( help, &state_with_i );
    }
    if( prevr != help->aut->initialState ){
        help->statesSuffixLink->seq[prevr] = state_with_i.index;
    }
    return Delta( help, &state_with_i, mVoidSequenceElement(help->aut->data, i) );
}

void SuffixTreeAdd( SuffixTreeBuildHelp * help, const VoidSequence * documentDollar ){
    PairState state, nextState;
    UINT i;

    i = help->aut->data->seqStored;
    VoidSequenceAppend( help->aut->data, documentDollar );
    if( help->aut->initialState == NO ){
        UINT newState;

        newState = NewState( help );
        help->aut->initialState = newState;
        state = CompressedAutomatonGetInitialPairState( help->aut );
    }
    else{
        state = CompressedAutomatonGetInitialPairState( help->aut );
        for( ; i < help->aut->data->seqStored; i++ ){
            nextState = Delta( help, &state, mVoidSequenceElement(help->aut->data, i) );
            if( nextState.index == NO ){
                break;
            }
            state = nextState;
        }
    }
    for( ; i < help->aut->data->seqStored; i++ ){
        state = Update( help, &state, i );
    }
}