_cvdatastructs.h.svn-base

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

            else                                                                 \
            {                                                                    \
                /* select pivot and exchange with 1st element */                 \
                int  m = lb + (diff >> 1);                                       \
                int  i = lb + 1, j = ub;                                         \
                                                                                 \
                cvSetSeqReaderPos( &r_i, lb );                                   \
                T* lb_ptr = (T*)r_i.ptr;                                         \
                                                                                 \
                cvSetSeqReaderPos( &r_j, m );                                    \
                                                                                 \
                T lb_val = *(T*)(r_j.ptr);                                       \
                *(T*)(r_j.ptr) = *(T*)(r_i.ptr);                                 \
                                                                                 \
                CV_NEXT_SEQ_ELEM( elem_size, r_i );                              \
                cvSetSeqReaderPos( &r_j, ub );                                   \
                                                                                 \
                /* partition into two segments */                                \
                for(;;)                                                          \
                {                                                                \
                    for( ; i < j && less_than( *(T*)(r_i.ptr), lb_val ); i++ )   \
                    {                                                            \
                        CV_NEXT_SEQ_ELEM( elem_size, r_i );                      \
                    }                                                            \
                                                                                 \
                    for( ; j >= i && less_than( lb_val, *(T*)(r_j.ptr) ); j-- )  \
                    {                                                            \
                        CV_PREV_SEQ_ELEM( elem_size, r_j );                      \
                    }                                                            \
                                                                                 \
                    if( i >= j ) break;                                          \
                    CV_SWAP( *(T*)(r_i.ptr), *(T*)(r_j.ptr), t );                \
                    CV_NEXT_SEQ_ELEM( elem_size, r_i );                          \
                    CV_PREV_SEQ_ELEM( elem_size, r_j );                          \
                    i++, j--;                                                    \
                }                                                                \
                                                                                 \
                /* pivot belongs in A[j] */                                      \
                *lb_ptr = *(T*)(r_j.ptr);                                        \
                *(T*)(r_j.ptr) = lb_val;                                         \
                                                                                 \
                /* 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;                                                  \
                }                                                                \
            }                                                                    \
        }                                                                        \
    }                                                                            \
}


#define CV_IMPLEMENT_SEQ_QSORT( func_name, T, less_than )  \
    CV_IMPLEMENT2_SEQ_QSORT( func_name, T, less_than, int )

/*
  Single-connected list, based on CvSet.
*/
#define CV_LIST_ELEM_FIELDS() \
    struct CvSListNode* next;

typedef struct CvSListNode
{
    CV_LIST_ELEM_FIELDS()
}
CvSListNode;

#define CV_LIST_FIELDS() \
    CV_SEQUENCE_FIELDS() \
    int  nodes;          \
    CvSListNode* head;

typedef struct CvSList
{
    CV_LIST_FIELDS()
}
CvSList;

CvSList* icvCreateSList( int list_flags, int header_size, int elem_size, CvMemStorage* storage );
CvSListNode* icvSListGetNode( CvSList* list, int index, CvSListNode** prevNode CV_DEFAULT(0));
int  icvSListGetIndex( CvSList* list, CvSListNode* node, CvSListNode** prevNode CV_DEFAULT(0) );
void icvSListRemoveAfter( CvSList* list, CvSListNode* node );
CvSListNode* icvSListInsertAfter( CvSList* list, CvSListNode* node,
                                CvSListNode* newNode CV_DEFAULT(0));
void icvClearSList( CvSList* list );

#define icvSListAddHead( list, newNode )  icvSListInsertAfter( (list), 0, (newNode))

/*
  Double-connected list, based on CvSList.
*/
#define CV_DBLIST_ELEM_FIELDS() \
    struct CvListNode* next;  \
    struct CvListNode* prev;

typedef struct CvListNode
{
    CV_DBLIST_ELEM_FIELDS()
}
CvListNode;

#define CV_DBLIST_FIELDS() \
    CV_SEQUENCE_FIELDS()   \
    int  nodes;            \
    CvListNode* head;    \
    CvListNode* tail;

typedef struct CvList
{
    CV_DBLIST_FIELDS()
}
CvList;

CvList* icvCreateList( int list_flags, int header_size, int elem_size, CvMemStorage* storage );
CvListNode* icvListGetNode( CvSList* list, int index );
int  icvListGetIndex( CvList* list, CvListNode* node );
void icvListRemoveAfter( CvList* list, CvListNode* node );
void icvListRemoveBefore( CvList* list, CvListNode* node );
CvListNode* icvListInsertAfter( CvList* list, CvListNode* node,
                                    CvListNode* newNode CV_DEFAULT(0) );
CvListNode* icvListInsertBefore( CvList* list, CvListNode* node,
                                     CvListNode* newNode CV_DEFAULT(0) );
void icvClearList( CvList* list );

#define  icvListAddHead( list, newNode )  icvSListInsertAfter( (list), 0, (newNode))
#define  icvListAddTail( list, newNode )  icvSListInsertBefore( (list), 0, (newNode))

#endif/*_CVDATASTRUCTS_H_*/

/* End of file. */