cvdatastructs.cpp.svn-base

来自「非结构化路识别」· SVN-BASE 代码 · 共 2,404 行 · 第 1/5 页

        {
            int i, count = seq->total - slice.endIndex;
            cvSetSeqReaderPos( &reader_to, slice.startIndex );
            cvSetSeqReaderPos( &reader_from, slice.endIndex );

            for( i = 0; i < count; i++ )
            {
                memcpy( reader_to.ptr, reader_from.ptr, elem_size );
                CV_NEXT_SEQ_ELEM( elem_size, reader_to );
                CV_NEXT_SEQ_ELEM( elem_size, reader_from );
            }

            cvSeqPopMulti( seq, 0, slice.endIndex - slice.startIndex );
        }
        else
        {
            int i, count = slice.startIndex;
            cvSetSeqReaderPos( &reader_to, slice.endIndex );
            cvSetSeqReaderPos( &reader_from, slice.startIndex );

            for( i = 0; i < count; i++ )
            {
                CV_PREV_SEQ_ELEM( elem_size, reader_to );
                CV_PREV_SEQ_ELEM( elem_size, reader_from );

                memcpy( reader_to.ptr, reader_from.ptr, elem_size );
            }

            cvSeqPopMulti( seq, 0, slice.endIndex - slice.startIndex, 1 );
        }
    }
    else
    {
        cvSeqPopMulti( seq, 0, total - slice.startIndex );
        cvSeqPopMulti( seq, 0, slice.endIndex - total, 1 );
    }

    __END__;
}


// Inserts a new sequence into the middle of another sequence
// !!! TODO !!! Implement more efficient algorithm
CV_IMPL void
cvSeqInsertSlice( CvSeq* seq, int index, const CvArr* from_arr )
{
    CvSeqReader reader_to, reader_from;
    int i, elem_size, total, from_total;
    
    CV_FUNCNAME("cvSeqInsertSlice");

    __BEGIN__;

    CvSeq from_header, *from = (CvSeq*)from_arr;
    CvSeqBlock block;

    if( !CV_IS_SEQ(seq) )
        CV_ERROR( CV_StsBadArg, "Invalid destination sequence header" );

    if( !CV_IS_SEQ(from))
    {
        CvMat* mat = (CvMat*)from;
        if( !CV_IS_MAT(mat))
            CV_ERROR( CV_StsBadArg, "Source is not a sequence nor matrix" );

        if( !CV_IS_MAT_CONT(mat->type) || mat->rows != 1 || mat->cols != 1 )
            CV_ERROR( CV_StsBadArg, "The source array must be 1d coninuous vector" );

        CV_CALL( from = cvMakeSeqHeaderForArray( CV_SEQ_KIND_GENERIC, sizeof(from_header),
                                                 icvPixSize[CV_MAT_TYPE(mat->type)],
                                                 mat->data.ptr, mat->cols + mat->rows - 1,
                                                 &from_header, &block ));
    }

    if( seq->elem_size != from->elem_size )
        CV_ERROR( CV_StsUnmatchedSizes,
        "Sizes of source and destination sequences' elements are different" );

    from_total = from->total;

    if( from_total == 0 )
        EXIT;

    total = seq->total;
    index += index < 0 ? total : 0;
    index -= index > total ? total : 0;

    if( (unsigned)index > (unsigned)total )
        CV_ERROR_FROM_STATUS( CV_BADRANGE_ERR );

    elem_size = seq->elem_size;

    if( index < (total >> 1) )
    {
        cvSeqPushMulti( seq, 0, from_total, 1 );

        cvStartReadSeq( seq, &reader_to );
        cvStartReadSeq( seq, &reader_from );
        cvSetSeqReaderPos( &reader_from, from_total );

        for( i = 0; i < index; i++ )
        {
            memcpy( reader_to.ptr, reader_from.ptr, elem_size );
            CV_NEXT_SEQ_ELEM( elem_size, reader_to );
            CV_NEXT_SEQ_ELEM( elem_size, reader_from );
        }
    }
    else
    {
        cvSeqPushMulti( seq, 0, from_total );

        cvStartReadSeq( seq, &reader_to );
        cvStartReadSeq( seq, &reader_from );
        cvSetSeqReaderPos( &reader_from, total );
        cvSetSeqReaderPos( &reader_to, seq->total );

        for( i = 0; i < total - index; i++ )
        {
            CV_PREV_SEQ_ELEM( elem_size, reader_to );
            CV_PREV_SEQ_ELEM( elem_size, reader_from );
            memcpy( reader_to.ptr, reader_from.ptr, elem_size );
        }
    }

    cvStartReadSeq( from, &reader_from );
    cvSetSeqReaderPos( &reader_to, index );

    for( i = 0; i < from_total; i++ )
    {
        memcpy( reader_to.ptr, reader_from.ptr, elem_size );
        CV_NEXT_SEQ_ELEM( elem_size, reader_to );
        CV_NEXT_SEQ_ELEM( elem_size, reader_from );
    }

    __END__;
}


// Sort the sequence using user-specified comparison function.
// Semantics is the same as in qsort function
CV_IMPL void
cvSeqSort( CvSeq* seq, CvCmpFunc cmp_func, void* userdata )
{
    const int bubble_level = 16;

    struct
    {
        int lb, ub;
    }
    stack[48];

    int sp = 0;

    int elem_size;
    CvSeqReader left_reader, right_reader;

    CV_FUNCNAME("cvSeqSort");

    __BEGIN__;

    if( !seq || !cmp_func )
        CV_ERROR_FROM_STATUS( CV_NULLPTR_ERR );

    if( seq->total <= 1 )
        EXIT;

    stack[0].lb = 0;
    stack[0].ub = seq->total - 1;

    elem_size = seq->elem_size;

    CV_CALL( cvStartReadSeq( seq, &left_reader ));
    CV_CALL( cvStartReadSeq( seq, &right_reader ));

    while( sp >= 0 )
    {
        int lb = stack[sp].lb;
        int ub = stack[sp--].ub;

        for(;;)
        {
            int diff = ub - lb;
            if( diff < bubble_level )
            {
                int i, j;
                cvSetSeqReaderPos( &left_reader, lb );

                for( i = diff; i > 0; i-- )
                {
                    int f = 0;

                    right_reader.block = left_reader.block;
                    right_reader.ptr = left_reader.ptr;
                    right_reader.block_min = left_reader.block_min;
                    right_reader.block_max = left_reader.block_max;
                    
                    for( j = 0; j < i; j++ )
                    {
                        char* ptr = right_reader.ptr;
                        CV_NEXT_SEQ_ELEM( elem_size, right_reader );
                        if( cmp_func( ptr, right_reader.ptr, userdata ) > 0 )
                        {
                            CV_SWAP_ELEMS( ptr, right_reader.ptr );
                            f = 1;
                        }
                    }
                    if( !f ) break;
                }
                break;
            }
            else
            {
                /* select pivot and exchange with 1st element */
                int  m = lb + (diff >> 1);
                int  i = lb, j = ub + 1;
                char* pivot_ptr;

                cvSetSeqReaderPos( &left_reader, lb );
                cvSetSeqReaderPos( &right_reader, m );
                pivot_ptr = right_reader.ptr;
                cvSetSeqReaderPos( &right_reader, ub );

                /* choose median among seq[lb], seq[m], seq[ub] */
                int a = cmp_func( pivot_ptr, left_reader.ptr, userdata ) < 0;
                int b = cmp_func( pivot_ptr, right_reader.ptr, userdata ) < 0;

                if( a == b )
                {
                    b = cmp_func( left_reader.ptr, right_reader.ptr, userdata ) < 0;
                    pivot_ptr = a == b ? left_reader.ptr : right_reader.ptr;
                }

                if( pivot_ptr != left_reader.ptr )
                {
                    CV_SWAP_ELEMS( left_reader.ptr, pivot_ptr );
                    pivot_ptr = left_reader.ptr;
                }
                    
                CV_NEXT_SEQ_ELEM( elem_size, left_reader );

                /* partition into two segments */
                for(;;)
                {
                    for( ; ++i < j && cmp_func( left_reader.ptr, pivot_ptr, userdata ) <= 0; )
                    {
                        CV_NEXT_SEQ_ELEM( elem_size, left_reader );
                    }

                    for( ; --j >= i && cmp_func( pivot_ptr, right_reader.ptr, userdata ) <= 0; )
                    {
                        CV_PREV_SEQ_ELEM( elem_size, right_reader );
                    }

                    if( i >= j ) break;
                    CV_SWAP_ELEMS( left_reader.ptr, right_reader.ptr );
                    CV_NEXT_SEQ_ELEM( elem_size, left_reader );
                    CV_PREV_SEQ_ELEM( elem_size, right_reader );
                }

                /* pivot belongs in A[j] */
                CV_SWAP_ELEMS( right_reader.ptr, pivot_ptr );

                /* keep processing smallest segment, and stack largest*/
                if( j - lb <= ub - j )
                {
                    if( j + 1 < ub )
                    {
                        stack[++sp].lb   = j + 1;
                        stack[sp].ub = ub;
                    }
                    ub = j - 1;
                }
                else
                {
                    if( j - 1 > lb)
                    {
                        stack[++sp].lb = lb;
                        stack[sp].ub = j - 1;
                    }
                    lb = j + 1;
                }
            }
        }
    }

    __END__;
}


CV_IMPL void
cvSeqInvert( CvSeq* seq )
{
    CV_FUNCNAME( "cvSeqInvert" );

    __BEGIN__;

    CvSeqReader left_reader, right_reader;
    int elem_size = seq->elem_size;
    int i, count;

    CV_CALL( cvStartReadSeq( seq, &left_reader, 0 ));
    CV_CALL( cvStartReadSeq( seq, &right_reader, 1 ));
    count = seq->total >> 1;

    for( i = 0; i < count; i++ )
    {
        CV_SWAP_ELEMS( left_reader.ptr, right_reader.ptr );
        CV_NEXT_SEQ_ELEM( elem_size, left_reader );
        CV_PREV_SEQ_ELEM( elem_size, right_reader );
    }

    __END__;
}


typedef struct CvPTreeNode
{
    struct CvPTreeNode* parent;
    char* element;
    int rank;
}
CvPTreeNode;


// split the input seq/set into one or more connected components.
// is_equal returns 1 if two elements belong to the same component
// the function returns sequence of integers - 0-based class indices for
// each element.  
CV_IMPL  int
cvPartitionSeq( CvSeq* seq, CvMemStorage* storage, CvSeq** comps,
                CvCmpFunc is_equal, void* userdata, int is_set )
{
    CvSeq* result = 0;
    CvMemStorage* temp_storage = 0;
    int class_idx = 0;
    
    CV_FUNCNAME( "icvSeqPartition" );

    __BEGIN__;

    CvSeqWriter writer;
    CvSeqReader reader;
    CvSeq* nodes;
    int i, j;

    if( !comps )
        CV_ERROR( CV_StsNullPtr, "" );

    if( !seq || !is_equal )
        CV_ERROR( CV_StsNullPtr, "" );

    if( !storage )
        storage = seq->storage;

    if( !storage )
        CV_ERROR( CV_StsNullPtr, "" );

    temp_storage = cvCreateChildMemStorage( storage );

    nodes = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvPTreeNode), temp_storage );

    cvStartReadSeq( seq, &reader );
    memset( &writer, 0, sizeof(writer));
    cvStartAppendToSeq( nodes, &writer ); 

    // Initial O(N) pass. Make a forest of single-vertex trees.
    for( i = 0; i < seq->total; i++ )
    {
        CvPTreeNode node = { 0, 0, 0 };
        if( !is_set || CV_IS_SET_ELEM( reader.ptr ))
            node.element = reader.ptr;
        CV_WRITE_SEQ_ELEM( node, writer );
        CV_NEXT_SEQ_ELEM( seq->elem_size, reader );
    }

    cvEndWriteSeq( &writer );

    // because every time we made a full cycle through the node sequence,
    // we do not need to initialize reader every time
    cvStartReadSeq( nodes, &reader );

    // The main O(N^2) pass. Merge connected components.
    for( i = 0; i < nodes->total; i++ )
    {
        CvPTreeNode* node = (CvPTreeNode*)cvGetSeqElem( nodes, i );
        CvPTreeNode* root = node;

        if( !node->element )
            continue;

        // find root
        while( root->parent )
            root = root->parent;

        for( j = 0; j < nodes->total; j++ )
        {
            CvPTreeNode* node2 = (CvPTreeNode*)reader.ptr;
            
            if( node2->element && node2 != node &&
                is_equal( node->element, node2->element, userdata ))
            {
                CvPTreeNode* root2 = node2;
                
                // unite both trees
                while( root2->parent )
                    root2 = root2->parent;

                if( root2 != root )
                {
                    if( root->rank > root2->rank )
                        root2->parent = root;
                    else
                    {
                        root->parent = root2;
                        root2->rank += root->rank == root2->rank;
                        root = root2;
                    }
                    assert( root->parent == 0 );

                    // compress path from node2 to the root
                    while( node2->parent )
                    {
                        CvPTreeNode* temp = node2;
                        node2 = node2->parent;
                        temp->parent = root;
                    }

                    // compress path from node to the root
                    node2 = node;
                    while( node2->parent )
                    {
                        CvPTreeNode* temp = node2;
                        node2 = node2->parent;
                        temp->parent = root;
                    }
                }
            }

            CV_NEXT_SEQ_ELEM( sizeof(*node), reader );
        }
    }

    // Final O(N) pass (Enumerate classes)
    // Reuse reader one more time
    result = cvCreateSeq( 0, sizeof(CvSeq), sizeof(int), storage );
    cvStartAppendToSeq( result, &writer );

    for( i = 0; i < nodes->total; i++ )
    {
        CvPTreeNode* node = (CvPTreeNode*)reader.ptr;
        int idx = -1;
        
        if( node->element )
        {
            while( node->parent )
                node = node->parent;
            if( node->rank >= 0 )
                node->rank = ~class_idx++;
            idx = ~node->rank;
        }

        CV_NEXT_SEQ_ELEM( sizeof(*node), reader );
        CV_WRITE_SEQ_ELEM( idx, writer );
    }

    cvEndWriteSeq( &writer );

    __END__;

    if( comps )
        *comps = result;

    cvReleaseMemStorage( &temp_storage );
    return class_idx;
}


/****************************************************************************************\
*                                      Set implementation                                *
\*********************