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

Go to the documentation of this file.

#include "base.h"

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

    help = (CDAWGBuildHelp *)(ptr);
    index = mCompressedAutomatonGetTransitionsStored( help->aut );
    tr = (TransitionFromStartTo *)(object);
    UINTSequenceAdd( help->transitionsFrom, tr->from );
    CompressedAutomatonAddTransition( help->aut, tr->from, tr->start, tr->to );
    if( help->aut->statesTransitions->seq[tr->from] == index ){
        UINTSequenceAdd( help->transitionsNext, NO );
    }
    else{
        UINTSequenceAdd( help->transitionsNext, help->aut->statesTransitions->seq[tr->from] );
        help->aut->statesTransitions->seq[tr->from] = index;
    }
    return index;
}

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

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

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

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

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

    help = (CDAWGBuildHelp *)(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 ){
    CDAWGBuildHelp * help;
    TransitionFromStartTo * tr;

    help = (CDAWGBuildHelp *)(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 ){
    CDAWGBuildHelp * help;

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

CDAWGBuildHelp * CDAWGBuildHelpInit( CompressedAutomaton * aut ){
    CDAWGBuildHelp * help;

    help = Malloc( 1, sizeof(CDAWGBuildHelp) );
    help->aut = aut;
    help->statesSuffixLink = UINTSequenceInit2( aut->statesTransitions->seqAlloced, 1024 );
    help->statesLength = UINTSequenceInit2( aut->statesTransitions->seqAlloced, 1024 );
    help->transitionsFrom = UINTSequenceInit2( aut->transitionsStart->seqAlloced, 1024 );
    help->transitionsNext = 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 CDAWGBuildHelpFree( CDAWGBuildHelp * help ){
    UINTSequenceFree( help->statesSuffixLink );
    UINTSequenceFree( help->statesLength );
    UINTSequenceFree( help->transitionsFrom );
    UINTSequenceFree( help->transitionsNext );
    HashFree( help->hash );
    Free( help->symbol );
    Free( help );
}

PairState Delta( CDAWGBuildHelp * help, const PairState * state, const void * symbol, UINT * tr ){
    PairState nextState;
    CompressedAutomaton * a;

    a = help->aut;
    nextState.transition = NO;
    nextState.index = NO;
    if( state->transition != NO ){
        (*tr) = state->transition;
        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;

        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( CDAWGBuildHelp * help ){
    UINT newState;

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

static UINT Split( CDAWGBuildHelp * help, const PairState * state ){
    UINT newState, from, to;
    TransitionFromStartTo tfst;

    newState = NewState( help );
    help->aut->statesEnd->seq[newState] = state->index - 1;
    from = help->transitionsFrom->seq[state->transition];
    to = help->aut->transitionsTo->seq[state->transition];
    help->statesLength->seq[newState] = help->statesLength->seq[from] + (state->index - help->aut->transitionsStart->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 );
    return newState;
}

static PairState SuffixLink( CDAWGBuildHelp * 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 Separate( CDAWGBuildHelp * help, const PairState * state, UINT i ){
    TransitionFromStartTo tfst;
    PairState nextState, st, q;
    UINT length, newState, tr, t;

    nextState = Delta( help, state, mVoidSequenceElement(help->aut->data, i), &t );
    if( nextState.transition != NO ){
        return nextState;
    }
    if( state->transition != NO ){
        UINT from, to;

        from = help->transitionsFrom->seq[state->transition];
        to = help->aut->transitionsTo->seq[state->transition];
        length = help->statesLength->seq[from] + help->aut->statesEnd->seq[to] - help->aut->transitionsStart->seq[state->transition] + 1;
    }
    else{
        length = help->statesLength->seq[state->index] + 1;
    }
    if( help->statesLength->seq[nextState.index] == length ){
        return nextState;
    }
    newState = NewState( help );
    help->statesLength->seq[newState] = length;
    help->aut->statesEnd->seq[newState] = help->aut->statesEnd->seq[nextState.index];
    help->statesSuffixLink->seq[newState] = help->statesSuffixLink->seq[nextState.index];
    help->statesSuffixLink->seq[nextState.index] = newState;
    tfst.from = newState;
    for( tr = help->aut->statesTransitions->seq[nextState.index]; tr != NO; tr = help->transitionsNext->seq[tr] ){
        tfst.start = help->aut->transitionsStart->seq[tr];
        tfst.to = help->aut->transitionsTo->seq[tr];
        memcpy( help->symbol, mVoidSequenceElement(help->aut->data, tfst.start), help->aut->data->elementSize );
        tfst.symbol = help->symbol;
        HashAdd( help->hash, &tfst );
    }
    st = (*state);
    while( bTRUE ){
        help->aut->transitionsTo->seq[t] = newState;
        if( st.transition == NO && st.index == help->aut->initialState ){
            break;
        }
        st = SuffixLink( help, &st );
        q = Delta( help, &st, mVoidSequenceElement(help->aut->data, i), &t );
        if( q.transition != nextState.transition || q.index != nextState.index ){
            break;
        }
    }
    nextState.transition = NO;
    nextState.index = newState;
    return nextState;
}


static PairState Update( CDAWGBuildHelp * help, const PairState * state, UINT i, UINT * sink, UINT infinity, boolean * slink ){
/*
    function update(s, (k, p)): returns pair of integers;
    // (s, (k, p − 1)) is the canonical reference pair for the active point.

    c := w[p]; 
    oldr := nil;

    while not check_end_point(s,(k,p−1),c) do
        if k ≤ p−1 then
            r := split_edge(s,(k,p−1)); 
        else 
            r := s; // explicit case.

    create node r′; 
    create edge (r, (p, ∞), r′);
    
    if oldr != nil then 
        suf(oldr) := r;
        
    oldr := r;
    
    (s, k) := canonize(suf (s), (k, p − 1)); 
    
    if oldr != nil then 
        suf(oldr) := s; 
        
    return canonize(s, (k, p));
*/
    PairState state_with_i;
    UINT r, prevr, succ, t;
    TransitionFromStartTo tfst;

    r = succ = NO;
    state_with_i = (*state);
    prevr = help->aut->initialState;
    while( bTRUE ){
        (*slink) = ( Delta( help, &state_with_i, mVoidSequenceElement(help->aut->data, i), &t ).index != NO );
        if( *slink ){
            break;
        }
        if( state_with_i.transition != NO ){
            if( succ == help->aut->transitionsTo->seq[state_with_i.transition] ){
                help->aut->transitionsTo->seq[state_with_i.transition] = r;
                state_with_i = SuffixLink( help, &state_with_i );
                continue;
            }
            else{
                succ = help->aut->transitionsTo->seq[state_with_i.transition];
                r = Split( help, &state_with_i );
            }
        }
        else{
            r = state_with_i.index;
        }
        tfst.from = r;
        tfst.start = i;
        if( (*sink) == NO ){
            (*sink) = NewState( help );
            help->statesLength->seq[(*sink)] = infinity;
            help->aut->statesEnd->seq[(*sink)] = help->aut->data->seqStored - 1;
        }
        tfst.to = (*sink);
        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 Separate( help, &state_with_i, i );
}

UINT CDAWGAdd( CDAWGBuildHelp * help, const VoidSequence * documentDollar ){
    PairState state;
    UINT i, sink;
    boolean slink;
    
    i = help->aut->data->seqStored; // WTF?

    // make sure there is a dollar at the end
    VoidSequenceAppend( help->aut->data, documentDollar );


    // create_nodes root and ⊥;
    if( help->aut->initialState == NO ){
        UINT newState;

        newState = NewState( help );
        help->statesLength->seq[newState] = 0;
        help->aut->initialState = newState;
    }
    state = CompressedAutomatonGetInitialPairState( help->aut );

    // Not doing this step?
    // for j := 1 to m do 
        //create_edge (⊥, (−j, −j), root); 


    sink = NO;
    for( ; i < help->aut->data->seqStored; i++ ){
        state = Update( help, &state, i, &sink, documentDollar->seqStored, &slink );
    }
    if( sink != NO ){
        if( slink ){
            help->statesSuffixLink->seq[sink] = state.index;
        }
        else{
            help->statesSuffixLink->seq[sink] = help->aut->initialState;
        }
    }
    return sink;
}