X-Git-Url: http://vcs.maemo.org/git/?a=blobdiff_plain;f=cxcore%2Fsrc%2Fcxdatastructs.cpp;fp=cxcore%2Fsrc%2Fcxdatastructs.cpp;h=0000000000000000000000000000000000000000;hb=e4c14cdbdf2fe805e79cd96ded236f57e7b89060;hp=b31b06f177a114713680e46d78ade9937eab89e7;hpb=454138ff8a20f6edb9b65a910101403d8b520643;p=opencv diff --git a/cxcore/src/cxdatastructs.cpp b/cxcore/src/cxdatastructs.cpp deleted file mode 100644 index b31b06f..0000000 --- a/cxcore/src/cxdatastructs.cpp +++ /dev/null @@ -1,4009 +0,0 @@ -/*M/////////////////////////////////////////////////////////////////////////////////////// -// -// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. -// -// By downloading, copying, installing or using the software you agree to this license. -// If you do not agree to this license, do not download, install, -// copy or use the software. -// -// -// Intel License Agreement -// For Open Source Computer Vision Library -// -// Copyright (C) 2000, Intel Corporation, all rights reserved. -// Third party copyrights are property of their respective owners. -// -// Redistribution and use in source and binary forms, with or without modification, -// are permitted provided that the following conditions are met: -// -// * Redistribution's of source code must retain the above copyright notice, -// this list of conditions and the following disclaimer. -// -// * Redistribution's in binary form must reproduce the above copyright notice, -// this list of conditions and the following disclaimer in the documentation -// and/or other materials provided with the distribution. -// -// * The name of Intel Corporation may not be used to endorse or promote products -// derived from this software without specific prior written permission. -// -// This software is provided by the copyright holders and contributors "as is" and -// any express or implied warranties, including, but not limited to, the implied -// warranties of merchantability and fitness for a particular purpose are disclaimed. -// In no event shall the Intel Corporation or contributors be liable for any direct, -// indirect, incidental, special, exemplary, or consequential damages -// (including, but not limited to, procurement of substitute goods or services; -// loss of use, data, or profits; or business interruption) however caused -// and on any theory of liability, whether in contract, strict liability, -// or tort (including negligence or otherwise) arising in any way out of -// the use of this software, even if advised of the possibility of such damage. -// -//M*/ -#include "_cxcore.h" - -#define ICV_FREE_PTR(storage) \ - ((schar*)(storage)->top + (storage)->block_size - (storage)->free_space) - -#define ICV_ALIGNED_SEQ_BLOCK_SIZE \ - (int)cvAlign(sizeof(CvSeqBlock), CV_STRUCT_ALIGN) - -CV_INLINE int -cvAlignLeft( int size, int align ) -{ - return size & -align; -} - -#define CV_GET_LAST_ELEM( seq, block ) \ - ((block)->data + ((block)->count - 1)*((seq)->elem_size)) - -#define CV_SWAP_ELEMS(a,b,elem_size) \ -{ \ - int k; \ - for( k = 0; k < elem_size; k++ ) \ - { \ - char t0 = (a)[k]; \ - char t1 = (b)[k]; \ - (a)[k] = t1; \ - (b)[k] = t0; \ - } \ -} - -#define ICV_SHIFT_TAB_MAX 32 -static const schar icvPower2ShiftTab[] = -{ - 0, 1, -1, 2, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, 4, - -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 5 -}; - -/****************************************************************************************\ -* Functions for manipulating memory storage - list of memory blocks * -\****************************************************************************************/ - -/* Initialize allocated storage: */ -static void -icvInitMemStorage( CvMemStorage* storage, int block_size ) -{ - CV_FUNCNAME( "icvInitMemStorage " ); - - __BEGIN__; - - if( !storage ) - CV_ERROR( CV_StsNullPtr, "" ); - - if( block_size <= 0 ) - block_size = CV_STORAGE_BLOCK_SIZE; - - block_size = cvAlign( block_size, CV_STRUCT_ALIGN ); - assert( sizeof(CvMemBlock) % CV_STRUCT_ALIGN == 0 ); - - memset( storage, 0, sizeof( *storage )); - storage->signature = CV_STORAGE_MAGIC_VAL; - storage->block_size = block_size; - - __END__; -} - - -/* Create root memory storage: */ -CV_IMPL CvMemStorage* -cvCreateMemStorage( int block_size ) -{ - CvMemStorage *storage = 0; - - CV_FUNCNAME( "cvCreateMemStorage" ); - - __BEGIN__; - - CV_CALL( storage = (CvMemStorage *)cvAlloc( sizeof( CvMemStorage ))); - CV_CALL( icvInitMemStorage( storage, block_size )); - - __END__; - - if( cvGetErrStatus() < 0 ) - cvFree( &storage ); - - return storage; -} - - -/* Create child memory storage: */ -CV_IMPL CvMemStorage * -cvCreateChildMemStorage( CvMemStorage * parent ) -{ - CvMemStorage *storage = 0; - CV_FUNCNAME( "cvCreateChildMemStorage" ); - - __BEGIN__; - - if( !parent ) - CV_ERROR( CV_StsNullPtr, "" ); - - CV_CALL( storage = cvCreateMemStorage(parent->block_size)); - storage->parent = parent; - - __END__; - - if( cvGetErrStatus() < 0 ) - cvFree( &storage ); - - return storage; -} - - -/* Release all blocks of the storage (or return them to parent, if any): */ -static void -icvDestroyMemStorage( CvMemStorage* storage ) -{ - CV_FUNCNAME( "icvDestroyMemStorage" ); - - __BEGIN__; - - int k = 0; - - CvMemBlock *block; - CvMemBlock *dst_top = 0; - - if( !storage ) - CV_ERROR( CV_StsNullPtr, "" ); - - if( storage->parent ) - dst_top = storage->parent->top; - - for( block = storage->bottom; block != 0; k++ ) - { - CvMemBlock *temp = block; - - block = block->next; - if( storage->parent ) - { - if( dst_top ) - { - temp->prev = dst_top; - temp->next = dst_top->next; - if( temp->next ) - temp->next->prev = temp; - dst_top = dst_top->next = temp; - } - else - { - dst_top = storage->parent->bottom = storage->parent->top = temp; - temp->prev = temp->next = 0; - storage->free_space = storage->block_size - sizeof( *temp ); - } - } - else - { - cvFree( &temp ); - } - } - - storage->top = storage->bottom = 0; - storage->free_space = 0; - - __END__; -} - - -/* Release memory storage: */ -CV_IMPL void -cvReleaseMemStorage( CvMemStorage** storage ) -{ - CvMemStorage *st; - CV_FUNCNAME( "cvReleaseMemStorage" ); - - __BEGIN__; - - if( !storage ) - CV_ERROR( CV_StsNullPtr, "" ); - - st = *storage; - *storage = 0; - - if( st ) - { - CV_CALL( icvDestroyMemStorage( st )); - cvFree( &st ); - } - - __END__; -} - - -/* Clears memory storage (return blocks to the parent, if any): */ -CV_IMPL void -cvClearMemStorage( CvMemStorage * storage ) -{ - CV_FUNCNAME( "cvClearMemStorage" ); - - __BEGIN__; - - if( !storage ) - CV_ERROR( CV_StsNullPtr, "" ); - - if( storage->parent ) - { - icvDestroyMemStorage( storage ); - } - else - { - storage->top = storage->bottom; - storage->free_space = storage->bottom ? storage->block_size - sizeof(CvMemBlock) : 0; - } - - __END__; -} - - -/* Moves stack pointer to next block. - If no blocks, allocate new one and link it to the storage: */ -static void -icvGoNextMemBlock( CvMemStorage * storage ) -{ - CV_FUNCNAME( "icvGoNextMemBlock" ); - - __BEGIN__; - - if( !storage ) - CV_ERROR( CV_StsNullPtr, "" ); - - if( !storage->top || !storage->top->next ) - { - CvMemBlock *block; - - if( !(storage->parent) ) - { - CV_CALL( block = (CvMemBlock *)cvAlloc( storage->block_size )); - } - else - { - CvMemStorage *parent = storage->parent; - CvMemStoragePos parent_pos; - - cvSaveMemStoragePos( parent, &parent_pos ); - CV_CALL( icvGoNextMemBlock( parent )); - - block = parent->top; - cvRestoreMemStoragePos( parent, &parent_pos ); - - if( block == parent->top ) /* the single allocated block */ - { - assert( parent->bottom == block ); - parent->top = parent->bottom = 0; - parent->free_space = 0; - } - else - { - /* cut the block from the parent's list of blocks */ - parent->top->next = block->next; - if( block->next ) - block->next->prev = parent->top; - } - } - - /* link block */ - block->next = 0; - block->prev = storage->top; - - if( storage->top ) - storage->top->next = block; - else - storage->top = storage->bottom = block; - } - - if( storage->top->next ) - storage->top = storage->top->next; - storage->free_space = storage->block_size - sizeof(CvMemBlock); - assert( storage->free_space % CV_STRUCT_ALIGN == 0 ); - - __END__; -} - - -/* Remember memory storage position: */ -CV_IMPL void -cvSaveMemStoragePos( const CvMemStorage * storage, CvMemStoragePos * pos ) -{ - CV_FUNCNAME( "cvSaveMemStoragePos" ); - - __BEGIN__; - - if( !storage || !pos ) - CV_ERROR( CV_StsNullPtr, "" ); - - pos->top = storage->top; - pos->free_space = storage->free_space; - - __END__; -} - - -/* Restore memory storage position: */ -CV_IMPL void -cvRestoreMemStoragePos( CvMemStorage * storage, CvMemStoragePos * pos ) -{ - CV_FUNCNAME( "cvRestoreMemStoragePos" ); - - __BEGIN__; - - if( !storage || !pos ) - CV_ERROR( CV_StsNullPtr, "" ); - if( pos->free_space > storage->block_size ) - CV_ERROR( CV_StsBadSize, "" ); - - /* - // this breaks icvGoNextMemBlock, so comment it off for now - if( storage->parent && (!pos->top || pos->top->next) ) - { - CvMemBlock* save_bottom; - if( !pos->top ) - save_bottom = 0; - else - { - save_bottom = storage->bottom; - storage->bottom = pos->top->next; - pos->top->next = 0; - storage->bottom->prev = 0; - } - icvDestroyMemStorage( storage ); - storage->bottom = save_bottom; - }*/ - - storage->top = pos->top; - storage->free_space = pos->free_space; - - if( !storage->top ) - { - storage->top = storage->bottom; - storage->free_space = storage->top ? storage->block_size - sizeof(CvMemBlock) : 0; - } - - __END__; -} - - -/* Allocate continuous buffer of the specified size in the storage: */ -CV_IMPL void* -cvMemStorageAlloc( CvMemStorage* storage, size_t size ) -{ - schar *ptr = 0; - - CV_FUNCNAME( "cvMemStorageAlloc" ); - - __BEGIN__; - - if( !storage ) - CV_ERROR( CV_StsNullPtr, "NULL storage pointer" ); - - if( size > INT_MAX ) - CV_ERROR( CV_StsOutOfRange, "Too large memory block is requested" ); - - assert( storage->free_space % CV_STRUCT_ALIGN == 0 ); - - if( (size_t)storage->free_space < size ) - { - size_t max_free_space = cvAlignLeft(storage->block_size - sizeof(CvMemBlock), CV_STRUCT_ALIGN); - if( max_free_space < size ) - CV_ERROR( CV_StsOutOfRange, "requested size is negative or too big" ); - - CV_CALL( icvGoNextMemBlock( storage )); - } - - ptr = ICV_FREE_PTR(storage); - assert( (size_t)ptr % CV_STRUCT_ALIGN == 0 ); - storage->free_space = cvAlignLeft(storage->free_space - (int)size, CV_STRUCT_ALIGN ); - - __END__; - - return ptr; -} - - -CV_IMPL CvString -cvMemStorageAllocString( CvMemStorage* storage, const char* ptr, int len ) -{ - CvString str; - CV_FUNCNAME( "cvMemStorageAllocString" ); - - __BEGIN__; - - str.len = len >= 0 ? len : (int)strlen(ptr); - CV_CALL( str.ptr = (char*)cvMemStorageAlloc( storage, str.len + 1 )); - memcpy( str.ptr, ptr, str.len ); - str.ptr[str.len] = '\0'; - - __END__; - - return str; -} - - -/****************************************************************************************\ -* Sequence implementation * -\****************************************************************************************/ - -/* Create empty sequence: */ -CV_IMPL CvSeq * -cvCreateSeq( int seq_flags, int header_size, int elem_size, CvMemStorage * storage ) -{ - CvSeq *seq = 0; - - CV_FUNCNAME( "cvCreateSeq" ); - - __BEGIN__; - - if( !storage ) - CV_ERROR( CV_StsNullPtr, "" ); - if( header_size < (int)sizeof( CvSeq ) || elem_size <= 0 ) - CV_ERROR( CV_StsBadSize, "" ); - - /* allocate sequence header */ - CV_CALL( seq = (CvSeq*)cvMemStorageAlloc( storage, header_size )); - memset( seq, 0, header_size ); - - seq->header_size = header_size; - seq->flags = (seq_flags & ~CV_MAGIC_MASK) | CV_SEQ_MAGIC_VAL; - { - int elemtype = CV_MAT_TYPE(seq_flags); - int typesize = CV_ELEM_SIZE(elemtype); - - if( elemtype != CV_SEQ_ELTYPE_GENERIC && - typesize != 0 && typesize != elem_size ) - CV_ERROR( CV_StsBadSize, - "Specified element size doesn't match to the size of the specified element type " - "(try to use 0 for element type)" ); - } - seq->elem_size = elem_size; - seq->storage = storage; - - CV_CALL( cvSetSeqBlockSize( seq, (1 << 10)/elem_size )); - - __END__; - - return seq; -} - - -/* adjusts field of sequence. It determines how much the sequence - grows if there are no free space inside the sequence buffers */ -CV_IMPL void -cvSetSeqBlockSize( CvSeq *seq, int delta_elements ) -{ - int elem_size; - int useful_block_size; - - CV_FUNCNAME( "cvSetSeqBlockSize" ); - - __BEGIN__; - - if( !seq || !seq->storage ) - CV_ERROR( CV_StsNullPtr, "" ); - if( delta_elements < 0 ) - CV_ERROR( CV_StsOutOfRange, "" ); - - useful_block_size = cvAlignLeft(seq->storage->block_size - sizeof(CvMemBlock) - - sizeof(CvSeqBlock), CV_STRUCT_ALIGN); - elem_size = seq->elem_size; - - if( delta_elements == 0 ) - { - delta_elements = (1 << 10) / elem_size; - delta_elements = MAX( delta_elements, 1 ); - } - if( delta_elements * elem_size > useful_block_size ) - { - delta_elements = useful_block_size / elem_size; - if( delta_elements == 0 ) - CV_ERROR( CV_StsOutOfRange, "Storage block size is too small " - "to fit the sequence elements" ); - } - - seq->delta_elems = delta_elements; - - __END__; -} - - -/* Find a sequence element by its index: */ -CV_IMPL schar* -cvGetSeqElem( const CvSeq *seq, int index ) -{ - CvSeqBlock *block; - int count, total = seq->total; - - if( (unsigned)index >= (unsigned)total ) - { - index += index < 0 ? total : 0; - index -= index >= total ? total : 0; - if( (unsigned)index >= (unsigned)total ) - return 0; - } - - block = seq->first; - if( index + index <= total ) - { - while( index >= (count = block->count) ) - { - block = block->next; - index -= count; - } - } - else - { - do - { - block = block->prev; - total -= block->count; - } - while( index < total ); - index -= total; - } - - return block->data + index * seq->elem_size; -} - - -/* Calculate index of a sequence element: */ -CV_IMPL int -cvSeqElemIdx( const CvSeq* seq, const void* _element, CvSeqBlock** _block ) -{ - const schar *element = (const schar *)_element; - int elem_size; - int id = -1; - CvSeqBlock *first_block; - CvSeqBlock *block; - - CV_FUNCNAME( "cvSeqElemIdx" ); - - __BEGIN__; - - if( !seq || !element ) - CV_ERROR( CV_StsNullPtr, "" ); - - block = first_block = seq->first; - elem_size = seq->elem_size; - - for( ;; ) - { - if( (unsigned)(element - block->data) < (unsigned) (block->count * elem_size) ) - { - if( _block ) - *_block = block; - if( elem_size <= ICV_SHIFT_TAB_MAX && (id = icvPower2ShiftTab[elem_size - 1]) >= 0 ) - id = (int)((size_t)(element - block->data) >> id); - else - id = (int)((size_t)(element - block->data) / elem_size); - id += block->start_index - seq->first->start_index; - break; - } - block = block->next; - if( block == first_block ) - break; - } - - __END__; - - return id; -} - - -CV_IMPL int -cvSliceLength( CvSlice slice, const CvSeq* seq ) -{ - int total = seq->total; - int length = slice.end_index - slice.start_index; - - if( length != 0 ) - { - if( slice.start_index < 0 ) - slice.start_index += total; - if( slice.end_index <= 0 ) - slice.end_index += total; - - length = slice.end_index - slice.start_index; - } - - if( length < 0 ) - { - length += total; - /*if( length < 0 ) - length += total;*/ - } - else if( length > total ) - length = total; - - return length; -} - - -/* Copy all sequence elements into single continuous array: */ -CV_IMPL void* -cvCvtSeqToArray( const CvSeq *seq, void *array, CvSlice slice ) -{ - CV_FUNCNAME( "cvCvtSeqToArray" ); - - __BEGIN__; - - int elem_size, total; - CvSeqReader reader; - char *dst = (char*)array; - - if( !seq || !array ) - CV_ERROR( CV_StsNullPtr, "" ); - - elem_size = seq->elem_size; - total = cvSliceLength( slice, seq )*elem_size; - - if( total == 0 ) - EXIT; - - cvStartReadSeq( seq, &reader, 0 ); - CV_CALL( cvSetSeqReaderPos( &reader, slice.start_index, 0 )); - - do - { - int count = (int)(reader.block_max - reader.ptr); - if( count > total ) - count = total; - - memcpy( dst, reader.ptr, count ); - dst += count; - reader.block = reader.block->next; - reader.ptr = reader.block->data; - reader.block_max = reader.ptr + reader.block->count*elem_size; - total -= count; - } - while( total > 0 ); - - __END__; - - return array; -} - - -/* Construct a sequence from an array without copying any data. - NB: The resultant sequence cannot grow beyond its initial size: */ -CV_IMPL CvSeq* -cvMakeSeqHeaderForArray( int seq_flags, int header_size, int elem_size, - void *array, int total, CvSeq *seq, CvSeqBlock * block ) -{ - CvSeq* result = 0; - - CV_FUNCNAME( "cvMakeSeqHeaderForArray" ); - - __BEGIN__; - - if( elem_size <= 0 || header_size < (int)sizeof( CvSeq ) || total < 0 ) - CV_ERROR( CV_StsBadSize, "" ); - - if( !seq || ((!array || !block) && total > 0) ) - CV_ERROR( CV_StsNullPtr, "" ); - - memset( seq, 0, header_size ); - - seq->header_size = header_size; - seq->flags = (seq_flags & ~CV_MAGIC_MASK) | CV_SEQ_MAGIC_VAL; - { - int elemtype = CV_MAT_TYPE(seq_flags); - int typesize = CV_ELEM_SIZE(elemtype); - - if( elemtype != CV_SEQ_ELTYPE_GENERIC && - typesize != 0 && typesize != elem_size ) - CV_ERROR( CV_StsBadSize, - "Element size doesn't match to the size of predefined element type " - "(try to use 0 for sequence element type)" ); - } - seq->elem_size = elem_size; - seq->total = total; - seq->block_max = seq->ptr = (schar *) array + total * elem_size; - - if( total > 0 ) - { - seq->first = block; - block->prev = block->next = block; - block->start_index = 0; - block->count = total; - block->data = (schar *) array; - } - - result = seq; - - __END__; - - return result; -} - - -/* The function allocates space for at least one more sequence element. - If there are free sequence blocks (seq->free_blocks != 0) - they are reused, otherwise the space is allocated in the storage: */ -static void -icvGrowSeq( CvSeq *seq, int in_front_of ) -{ - CV_FUNCNAME( "icvGrowSeq" ); - - __BEGIN__; - - CvSeqBlock *block; - - if( !seq ) - CV_ERROR( CV_StsNullPtr, "" ); - block = seq->free_blocks; - - if( !block ) - { - int elem_size = seq->elem_size; - int delta_elems = seq->delta_elems; - CvMemStorage *storage = seq->storage; - - if( seq->total >= delta_elems*4 ) - cvSetSeqBlockSize( seq, delta_elems*2 ); - - if( !storage ) - CV_ERROR( CV_StsNullPtr, "The sequence has NULL storage pointer" ); - - /* If there is a free space just after last allocated block - and it is big enough then enlarge the last block. - This can happen only if the new block is added to the end of sequence: */ - if( (unsigned)(ICV_FREE_PTR(storage) - seq->block_max) < CV_STRUCT_ALIGN && - storage->free_space >= seq->elem_size && !in_front_of ) - { - int delta = storage->free_space / elem_size; - - delta = MIN( delta, delta_elems ) * elem_size; - seq->block_max += delta; - storage->free_space = cvAlignLeft((int)(((schar*)storage->top + storage->block_size) - - seq->block_max), CV_STRUCT_ALIGN ); - EXIT; - } - else - { - int delta = elem_size * delta_elems + ICV_ALIGNED_SEQ_BLOCK_SIZE; - - /* Try to allocate elements: */ - if( storage->free_space < delta ) - { - int small_block_size = MAX(1, delta_elems/3)*elem_size + - ICV_ALIGNED_SEQ_BLOCK_SIZE; - /* try to allocate smaller part */ - if( storage->free_space >= small_block_size + CV_STRUCT_ALIGN ) - { - delta = (storage->free_space - ICV_ALIGNED_SEQ_BLOCK_SIZE)/seq->elem_size; - delta = delta*seq->elem_size + ICV_ALIGNED_SEQ_BLOCK_SIZE; - } - else - { - CV_CALL( icvGoNextMemBlock( storage )); - assert( storage->free_space >= delta ); - } - } - - CV_CALL( block = (CvSeqBlock*)cvMemStorageAlloc( storage, delta )); - block->data = (schar*)cvAlignPtr( block + 1, CV_STRUCT_ALIGN ); - block->count = delta - ICV_ALIGNED_SEQ_BLOCK_SIZE; - block->prev = block->next = 0; - } - } - else - { - seq->free_blocks = block->next; - } - - if( !(seq->first) ) - { - seq->first = block; - block->prev = block->next = block; - } - else - { - block->prev = seq->first->prev; - block->next = seq->first; - block->prev->next = block->next->prev = block; - } - - /* For free blocks the field means - * total number of bytes in the block. - * - * For used blocks it means current number - * of sequence elements in the block: - */ - assert( block->count % seq->elem_size == 0 && block->count > 0 ); - - if( !in_front_of ) - { - seq->ptr = block->data; - seq->block_max = block->data + block->count; - block->start_index = block == block->prev ? 0 : - block->prev->start_index + block->prev->count; - } - else - { - int delta = block->count / seq->elem_size; - block->data += block->count; - - if( block != block->prev ) - { - assert( seq->first->start_index == 0 ); - seq->first = block; - } - else - { - seq->block_max = seq->ptr = block->data; - } - - block->start_index = 0; - - for( ;; ) - { - block->start_index += delta; - block = block->next; - if( block == seq->first ) - break; - } - } - - block->count = 0; - - __END__; -} - -/* Recycle a sequence block: */ -static void -icvFreeSeqBlock( CvSeq *seq, int in_front_of ) -{ - /*CV_FUNCNAME( "icvFreeSeqBlock" );*/ - - __BEGIN__; - - CvSeqBlock *block = seq->first; - - assert( (in_front_of ? block : block->prev)->count == 0 ); - - if( block == block->prev ) /* single block case */ - { - block->count = (int)(seq->block_max - block->data) + block->start_index * seq->elem_size; - block->data = seq->block_max - block->count; - seq->first = 0; - seq->ptr = seq->block_max = 0; - seq->total = 0; - } - else - { - if( !in_front_of ) - { - block = block->prev; - assert( seq->ptr == block->data ); - - block->count = (int)(seq->block_max - seq->ptr); - seq->block_max = seq->ptr = block->prev->data + - block->prev->count * seq->elem_size; - } - else - { - int delta = block->start_index; - - block->count = delta * seq->elem_size; - block->data -= block->count; - - /* Update start indices of sequence blocks: */ - for( ;; ) - { - block->start_index -= delta; - block = block->next; - if( block == seq->first ) - break; - } - - seq->first = block->next; - } - - block->prev->next = block->next; - block->next->prev = block->prev; - } - - assert( block->count > 0 && block->count % seq->elem_size == 0 ); - block->next = seq->free_blocks; - seq->free_blocks = block; - - __END__; -} - - -/****************************************************************************************\ -* Sequence Writer implementation * -\****************************************************************************************/ - -/* Initialize sequence writer: */ -CV_IMPL void -cvStartAppendToSeq( CvSeq *seq, CvSeqWriter * writer ) -{ - CV_FUNCNAME( "cvStartAppendToSeq" ); - - __BEGIN__; - - if( !seq || !writer ) - CV_ERROR( CV_StsNullPtr, "" ); - - memset( writer, 0, sizeof( *writer )); - writer->header_size = sizeof( CvSeqWriter ); - - writer->seq = seq; - writer->block = seq->first ? seq->first->prev : 0; - writer->ptr = seq->ptr; - writer->block_max = seq->block_max; - - __END__; -} - - -/* Initialize sequence writer: */ -CV_IMPL void -cvStartWriteSeq( int seq_flags, int header_size, - int elem_size, CvMemStorage * storage, CvSeqWriter * writer ) -{ - CvSeq *seq = 0; - - CV_FUNCNAME( "cvStartWriteSeq" ); - - __BEGIN__; - - if( !storage || !writer ) - CV_ERROR( CV_StsNullPtr, "" ); - - CV_CALL( seq = cvCreateSeq( seq_flags, header_size, elem_size, storage )); - cvStartAppendToSeq( seq, writer ); - - __END__; -} - - -/* Update sequence header: */ -CV_IMPL void -cvFlushSeqWriter( CvSeqWriter * writer ) -{ - CvSeq *seq = 0; - - CV_FUNCNAME( "cvFlushSeqWriter" ); - - __BEGIN__; - - if( !writer ) - CV_ERROR( CV_StsNullPtr, "" ); - - seq = writer->seq; - seq->ptr = writer->ptr; - - if( writer->block ) - { - int total = 0; - CvSeqBlock *first_block = writer->seq->first; - CvSeqBlock *block = first_block; - - writer->block->count = (int)((writer->ptr - writer->block->data) / seq->elem_size); - assert( writer->block->count > 0 ); - - do - { - total += block->count; - block = block->next; - } - while( block != first_block ); - - writer->seq->total = total; - } - - __END__; -} - - -/* Calls icvFlushSeqWriter and finishes writing process: */ -CV_IMPL CvSeq * -cvEndWriteSeq( CvSeqWriter * writer ) -{ - CvSeq *seq = 0; - - CV_FUNCNAME( "cvEndWriteSeq" ); - - __BEGIN__; - - if( !writer ) - CV_ERROR( CV_StsNullPtr, "" ); - - CV_CALL( cvFlushSeqWriter( writer )); - seq = writer->seq; - - /* Truncate the last block: */ - if( writer->block && writer->seq->storage ) - { - CvMemStorage *storage = seq->storage; - schar *storage_block_max = (schar *) storage->top + storage->block_size; - - assert( writer->block->count > 0 ); - - if( (unsigned)((storage_block_max - storage->free_space) - - seq->block_max) < CV_STRUCT_ALIGN ) - { - storage->free_space = cvAlignLeft((int)(storage_block_max - seq->ptr), CV_STRUCT_ALIGN); - seq->block_max = seq->ptr; - } - } - - writer->ptr = 0; - - __END__; - - return seq; -} - - -/* Create new sequence block: */ -CV_IMPL void -cvCreateSeqBlock( CvSeqWriter * writer ) -{ - CV_FUNCNAME( "cvCreateSeqBlock" ); - - __BEGIN__; - - CvSeq *seq; - - if( !writer || !writer->seq ) - CV_ERROR( CV_StsNullPtr, "" ); - - seq = writer->seq; - - cvFlushSeqWriter( writer ); - - CV_CALL( icvGrowSeq( seq, 0 )); - - writer->block = seq->first->prev; - writer->ptr = seq->ptr; - writer->block_max = seq->block_max; - - __END__; -} - - -/****************************************************************************************\ -* Sequence Reader implementation * -\****************************************************************************************/ - -/* Initialize sequence reader: */ -CV_IMPL void -cvStartReadSeq( const CvSeq *seq, CvSeqReader * reader, int reverse ) -{ - CvSeqBlock *first_block; - CvSeqBlock *last_block; - - CV_FUNCNAME( "cvStartReadSeq" ); - - if( reader ) - { - reader->seq = 0; - reader->block = 0; - reader->ptr = reader->block_max = reader->block_min = 0; - } - - __BEGIN__; - - if( !seq || !reader ) - CV_ERROR( CV_StsNullPtr, "" ); - - reader->header_size = sizeof( CvSeqReader ); - reader->seq = (CvSeq*)seq; - - first_block = seq->first; - - if( first_block ) - { - last_block = first_block->prev; - reader->ptr = first_block->data; - reader->prev_elem = CV_GET_LAST_ELEM( seq, last_block ); - reader->delta_index = seq->first->start_index; - - if( reverse ) - { - schar *temp = reader->ptr; - - reader->ptr = reader->prev_elem; - reader->prev_elem = temp; - - reader->block = last_block; - } - else - { - reader->block = first_block; - } - - reader->block_min = reader->block->data; - reader->block_max = reader->block_min + reader->block->count * seq->elem_size; - } - else - { - reader->delta_index = 0; - reader->block = 0; - - reader->ptr = reader->prev_elem = reader->block_min = reader->block_max = 0; - } - - __END__; -} - - -/* Change the current reading block - * to the previous or to the next: - */ -CV_IMPL void -cvChangeSeqBlock( void* _reader, int direction ) -{ - CV_FUNCNAME( "cvChangeSeqBlock" ); - - __BEGIN__; - - CvSeqReader* reader = (CvSeqReader*)_reader; - - if( !reader ) - CV_ERROR( CV_StsNullPtr, "" ); - - if( direction > 0 ) - { - reader->block = reader->block->next; - reader->ptr = reader->block->data; - } - else - { - reader->block = reader->block->prev; - reader->ptr = CV_GET_LAST_ELEM( reader->seq, reader->block ); - } - reader->block_min = reader->block->data; - reader->block_max = reader->block_min + reader->block->count * reader->seq->elem_size; - - __END__; -} - - -/* Return the current reader position: */ -CV_IMPL int -cvGetSeqReaderPos( CvSeqReader* reader ) -{ - int elem_size; - int index = -1; - - CV_FUNCNAME( "cvGetSeqReaderPos" ); - - __BEGIN__; - - if( !reader || !reader->ptr ) - CV_ERROR( CV_StsNullPtr, "" ); - - elem_size = reader->seq->elem_size; - if( elem_size <= ICV_SHIFT_TAB_MAX && (index = icvPower2ShiftTab[elem_size - 1]) >= 0 ) - index = (int)((reader->ptr - reader->block_min) >> index); - else - index = (int)((reader->ptr - reader->block_min) / elem_size); - - index += reader->block->start_index - reader->delta_index; - - __END__; - - return index; -} - - -/* Set reader position to given position, - * either absolute or relative to the - * current one: - */ -CV_IMPL void -cvSetSeqReaderPos( CvSeqReader* reader, int index, int is_relative ) -{ - CV_FUNCNAME( "cvSetSeqReaderPos" ); - - __BEGIN__; - - CvSeqBlock *block; - int elem_size, count, total; - - if( !reader || !reader->seq ) - CV_ERROR( CV_StsNullPtr, "" ); - - total = reader->seq->total; - elem_size = reader->seq->elem_size; - - if( !is_relative ) - { - if( index < 0 ) - { - if( index < -total ) - CV_ERROR( CV_StsOutOfRange, "" ); - index += total; - } - else if( index >= total ) - { - index -= total; - if( index >= total ) - CV_ERROR( CV_StsOutOfRange, "" ); - } - - block = reader->seq->first; - if( index >= (count = block->count) ) - { - if( index + index <= total ) - { - do - { - block = block->next; - index -= count; - } - while( index >= (count = block->count) ); - } - else - { - do - { - block = block->prev; - total -= block->count; - } - while( index < total ); - index -= total; - } - } - reader->ptr = block->data + index * elem_size; - if( reader->block != block ) - { - reader->block = block; - reader->block_min = block->data; - reader->block_max = block->data + block->count * elem_size; - } - } - else - { - schar* ptr = reader->ptr; - index *= elem_size; - block = reader->block; - - if( index > 0 ) - { - while( ptr + index >= reader->block_max ) - { - int delta = (int)(reader->block_max - ptr); - index -= delta; - reader->block = block = block->next; - reader->block_min = ptr = block->data; - reader->block_max = block->data + block->count*elem_size; - } - reader->ptr = ptr + index; - } - else - { - while( ptr + index < reader->block_min ) - { - int delta = (int)(ptr - reader->block_min); - index += delta; - reader->block = block = block->prev; - reader->block_min = block->data; - reader->block_max = ptr = block->data + block->count*elem_size; - } - reader->ptr = ptr + index; - } - } - - __END__; -} - - -/* Push element onto the sequence: */ -CV_IMPL schar* -cvSeqPush( CvSeq *seq, void *element ) -{ - schar *ptr = 0; - size_t elem_size; - - CV_FUNCNAME( "cvSeqPush" ); - - __BEGIN__; - - if( !seq ) - CV_ERROR( CV_StsNullPtr, "" ); - - elem_size = seq->elem_size; - ptr = seq->ptr; - - if( ptr >= seq->block_max ) - { - CV_CALL( icvGrowSeq( seq, 0 )); - - ptr = seq->ptr; - assert( ptr + elem_size <= seq->block_max /*&& ptr == seq->block_min */ ); - } - - if( element ) - CV_MEMCPY_AUTO( ptr, element, elem_size ); - seq->first->prev->count++; - seq->total++; - seq->ptr = ptr + elem_size; - - __END__; - - return ptr; -} - - -/* Pop last element off of the sequence: */ -CV_IMPL void -cvSeqPop( CvSeq *seq, void *element ) -{ - schar *ptr; - int elem_size; - - CV_FUNCNAME( "cvSeqPop" ); - - __BEGIN__; - - if( !seq ) - CV_ERROR( CV_StsNullPtr, "" ); - if( seq->total <= 0 ) - CV_ERROR( CV_StsBadSize, "" ); - - elem_size = seq->elem_size; - seq->ptr = ptr = seq->ptr - elem_size; - - if( element ) - CV_MEMCPY_AUTO( element, ptr, elem_size ); - seq->ptr = ptr; - seq->total--; - - if( --(seq->first->prev->count) == 0 ) - { - icvFreeSeqBlock( seq, 0 ); - assert( seq->ptr == seq->block_max ); - } - - __END__; -} - - -/* Push element onto the front of the sequence: */ -CV_IMPL schar* -cvSeqPushFront( CvSeq *seq, void *element ) -{ - schar* ptr = 0; - int elem_size; - CvSeqBlock *block; - - CV_FUNCNAME( "cvSeqPushFront" ); - - __BEGIN__; - - if( !seq ) - CV_ERROR( CV_StsNullPtr, "" ); - - elem_size = seq->elem_size; - block = seq->first; - - if( !block || block->start_index == 0 ) - { - CV_CALL( icvGrowSeq( seq, 1 )); - - block = seq->first; - assert( block->start_index > 0 ); - } - - ptr = block->data -= elem_size; - - if( element ) - CV_MEMCPY_AUTO( ptr, element, elem_size ); - block->count++; - block->start_index--; - seq->total++; - - __END__; - - return ptr; -} - - -/* Shift out first element of the sequence: */ -CV_IMPL void -cvSeqPopFront( CvSeq *seq, void *element ) -{ - int elem_size; - CvSeqBlock *block; - - CV_FUNCNAME( "cvSeqPopFront" ); - - __BEGIN__; - - if( !seq ) - CV_ERROR( CV_StsNullPtr, "" ); - if( seq->total <= 0 ) - CV_ERROR( CV_StsBadSize, "" ); - - elem_size = seq->elem_size; - block = seq->first; - - if( element ) - CV_MEMCPY_AUTO( element, block->data, elem_size ); - block->data += elem_size; - block->start_index++; - seq->total--; - - if( --(block->count) == 0 ) - { - icvFreeSeqBlock( seq, 1 ); - } - - __END__; -} - -/* Insert new element in middle of sequence: */ -CV_IMPL schar* -cvSeqInsert( CvSeq *seq, int before_index, void *element ) -{ - int elem_size; - int block_size; - CvSeqBlock *block; - int delta_index; - int total; - schar* ret_ptr = 0; - - CV_FUNCNAME( "cvSeqInsert" ); - - __BEGIN__; - - if( !seq ) - CV_ERROR( CV_StsNullPtr, "" ); - - total = seq->total; - before_index += before_index < 0 ? total : 0; - before_index -= before_index > total ? total : 0; - - if( (unsigned)before_index > (unsigned)total ) - CV_ERROR( CV_StsOutOfRange, "" ); - - if( before_index == total ) - { - CV_CALL( ret_ptr = cvSeqPush( seq, element )); - } - else if( before_index == 0 ) - { - CV_CALL( ret_ptr = cvSeqPushFront( seq, element )); - } - else - { - elem_size = seq->elem_size; - - if( before_index >= total >> 1 ) - { - schar *ptr = seq->ptr + elem_size; - - if( ptr > seq->block_max ) - { - CV_CALL( icvGrowSeq( seq, 0 )); - - ptr = seq->ptr + elem_size; - assert( ptr <= seq->block_max ); - } - - delta_index = seq->first->start_index; - block = seq->first->prev; - block->count++; - block_size = (int)(ptr - block->data); - - while( before_index < block->start_index - delta_index ) - { - CvSeqBlock *prev_block = block->prev; - - memmove( block->data + elem_size, block->data, block_size - elem_size ); - block_size = prev_block->count * elem_size; - memcpy( block->data, prev_block->data + block_size - elem_size, elem_size ); - block = prev_block; - - /* Check that we don't fall into an infinite loop: */ - assert( block != seq->first->prev ); - } - - before_index = (before_index - block->start_index + delta_index) * elem_size; - memmove( block->data + before_index + elem_size, block->data + before_index, - block_size - before_index - elem_size ); - - ret_ptr = block->data + before_index; - - if( element ) - memcpy( ret_ptr, element, elem_size ); - seq->ptr = ptr; - } - else - { - block = seq->first; - - if( block->start_index == 0 ) - { - CV_CALL( icvGrowSeq( seq, 1 )); - - block = seq->first; - } - - delta_index = block->start_index; - block->count++; - block->start_index--; - block->data -= elem_size; - - while( before_index > block->start_index - delta_index + block->count ) - { - CvSeqBlock *next_block = block->next; - - block_size = block->count * elem_size; - memmove( block->data, block->data + elem_size, block_size - elem_size ); - memcpy( block->data + block_size - elem_size, next_block->data, elem_size ); - block = next_block; - - /* Check that we don't fall into an infinite loop: */ - assert( block != seq->first ); - } - - before_index = (before_index - block->start_index + delta_index) * elem_size; - memmove( block->data, block->data + elem_size, before_index - elem_size ); - - ret_ptr = block->data + before_index - elem_size; - - if( element ) - memcpy( ret_ptr, element, elem_size ); - } - - seq->total = total + 1; - } - - __END__; - - return ret_ptr; -} - - -/* Removes element from sequence: */ -CV_IMPL void -cvSeqRemove( CvSeq *seq, int index ) -{ - schar *ptr; - int elem_size; - int block_size; - CvSeqBlock *block; - int delta_index; - int total, front = 0; - - CV_FUNCNAME( "cvSeqRemove" ); - - __BEGIN__; - - if( !seq ) - CV_ERROR( CV_StsNullPtr, "" ); - - total = seq->total; - - index += index < 0 ? total : 0; - index -= index >= total ? total : 0; - - if( (unsigned) index >= (unsigned) total ) - CV_ERROR( CV_StsOutOfRange, "Invalid index" ); - - if( index == total - 1 ) - { - cvSeqPop( seq, 0 ); - } - else if( index == 0 ) - { - cvSeqPopFront( seq, 0 ); - } - else - { - block = seq->first; - elem_size = seq->elem_size; - delta_index = block->start_index; - while( block->start_index - delta_index + block->count <= index ) - block = block->next; - - ptr = block->data + (index - block->start_index + delta_index) * elem_size; - - front = index < total >> 1; - if( !front ) - { - block_size = block->count * elem_size - (int)(ptr - block->data); - - while( block != seq->first->prev ) /* while not the last block */ - { - CvSeqBlock *next_block = block->next; - - memmove( ptr, ptr + elem_size, block_size - elem_size ); - memcpy( ptr + block_size - elem_size, next_block->data, elem_size ); - block = next_block; - ptr = block->data; - block_size = block->count * elem_size; - } - - memmove( ptr, ptr + elem_size, block_size - elem_size ); - seq->ptr -= elem_size; - } - else - { - ptr += elem_size; - block_size = (int)(ptr - block->data); - - while( block != seq->first ) - { - CvSeqBlock *prev_block = block->prev; - - memmove( block->data + elem_size, block->data, block_size - elem_size ); - block_size = prev_block->count * elem_size; - memcpy( block->data, prev_block->data + block_size - elem_size, elem_size ); - block = prev_block; - } - - memmove( block->data + elem_size, block->data, block_size - elem_size ); - block->data += elem_size; - block->start_index++; - } - - seq->total = total - 1; - if( --block->count == 0 ) - icvFreeSeqBlock( seq, front ); - } - - __END__; -} - - -/* Add several elements to the beginning or end of a sequence: */ -CV_IMPL void -cvSeqPushMulti( CvSeq *seq, void *_elements, int count, int front ) -{ - char *elements = (char *) _elements; - - CV_FUNCNAME( "cvSeqPushMulti" ); - - __BEGIN__; - int elem_size; - - if( !seq ) - CV_ERROR( CV_StsNullPtr, "NULL sequence pointer" ); - if( count < 0 ) - CV_ERROR( CV_StsBadSize, "number of removed elements is negative" ); - - elem_size = seq->elem_size; - - if( !front ) - { - while( count > 0 ) - { - int delta = (int)((seq->block_max - seq->ptr) / elem_size); - - delta = MIN( delta, count ); - if( delta > 0 ) - { - seq->first->prev->count += delta; - seq->total += delta; - count -= delta; - delta *= elem_size; - if( elements ) - { - memcpy( seq->ptr, elements, delta ); - elements += delta; - } - seq->ptr += delta; - } - - if( count > 0 ) - CV_CALL( icvGrowSeq( seq, 0 )); - } - } - else - { - CvSeqBlock* block = seq->first; - - while( count > 0 ) - { - int delta; - - if( !block || block->start_index == 0 ) - { - CV_CALL( icvGrowSeq( seq, 1 )); - - block = seq->first; - assert( block->start_index > 0 ); - } - - delta = MIN( block->start_index, count ); - count -= delta; - block->start_index -= delta; - block->count += delta; - seq->total += delta; - delta *= elem_size; - block->data -= delta; - - if( elements ) - memcpy( block->data, elements + count*elem_size, delta ); - } - } - - __END__; -} - - -/* Remove several elements from the end of sequence: */ -CV_IMPL void -cvSeqPopMulti( CvSeq *seq, void *_elements, int count, int front ) -{ - char *elements = (char *) _elements; - - CV_FUNCNAME( "cvSeqPopMulti" ); - - __BEGIN__; - - if( !seq ) - CV_ERROR( CV_StsNullPtr, "NULL sequence pointer" ); - if( count < 0 ) - CV_ERROR( CV_StsBadSize, "number of removed elements is negative" ); - - count = MIN( count, seq->total ); - - if( !front ) - { - if( elements ) - elements += count * seq->elem_size; - - while( count > 0 ) - { - int delta = seq->first->prev->count; - - delta = MIN( delta, count ); - assert( delta > 0 ); - - seq->first->prev->count -= delta; - seq->total -= delta; - count -= delta; - delta *= seq->elem_size; - seq->ptr -= delta; - - if( elements ) - { - elements -= delta; - memcpy( elements, seq->ptr, delta ); - } - - if( seq->first->prev->count == 0 ) - icvFreeSeqBlock( seq, 0 ); - } - } - else - { - while( count > 0 ) - { - int delta = seq->first->count; - - delta = MIN( delta, count ); - assert( delta > 0 ); - - seq->first->count -= delta; - seq->total -= delta; - count -= delta; - seq->first->start_index += delta; - delta *= seq->elem_size; - - if( elements ) - { - memcpy( elements, seq->first->data, delta ); - elements += delta; - } - - seq->first->data += delta; - if( seq->first->count == 0 ) - icvFreeSeqBlock( seq, 1 ); - } - } - - __END__; -} - - -/* Remove all elements from a sequence: */ -CV_IMPL void -cvClearSeq( CvSeq *seq ) -{ - CV_FUNCNAME( "cvClearSeq" ); - - __BEGIN__; - - if( !seq ) - CV_ERROR( CV_StsNullPtr, "" ); - cvSeqPopMulti( seq, 0, seq->total ); - - __END__; -} - - -CV_IMPL CvSeq* -cvSeqSlice( const CvSeq* seq, CvSlice slice, CvMemStorage* storage, int copy_data ) -{ - CvSeq* subseq = 0; - - CV_FUNCNAME("cvSeqSlice"); - - __BEGIN__; - - int elem_size, count, length; - CvSeqReader reader; - CvSeqBlock *block, *first_block = 0, *last_block = 0; - - if( !CV_IS_SEQ(seq) ) - CV_ERROR( CV_StsBadArg, "Invalid sequence header" ); - - if( !storage ) - { - storage = seq->storage; - if( !storage ) - CV_ERROR( CV_StsNullPtr, "NULL storage pointer" ); - } - - elem_size = seq->elem_size; - length = cvSliceLength( slice, seq ); - if( slice.start_index < 0 ) - slice.start_index += seq->total; - else if( slice.start_index >= seq->total ) - slice.start_index -= seq->total; - if( (unsigned)length > (unsigned)seq->total || - ((unsigned)slice.start_index >= (unsigned)seq->total && length != 0) ) - CV_ERROR( CV_StsOutOfRange, "Bad sequence slice" ); - - CV_CALL( subseq = cvCreateSeq( seq->flags, seq->header_size, elem_size, storage )); - - if( length > 0 ) - { - cvStartReadSeq( seq, &reader, 0 ); - cvSetSeqReaderPos( &reader, slice.start_index, 0 ); - count = (int)((reader.block_max - reader.ptr)/elem_size); - - do - { - int bl = MIN( count, length ); - - if( !copy_data ) - { - block = (CvSeqBlock*)cvMemStorageAlloc( storage, sizeof(*block) ); - if( !first_block ) - { - first_block = subseq->first = block->prev = block->next = block; - block->start_index = 0; - } - else - { - block->prev = last_block; - block->next = first_block; - last_block->next = first_block->prev = block; - block->start_index = last_block->start_index + last_block->count; - } - last_block = block; - block->data = reader.ptr; - block->count = bl; - subseq->total += bl; - } - else - cvSeqPushMulti( subseq, reader.ptr, bl, 0 ); - length -= bl; - reader.block = reader.block->next; - reader.ptr = reader.block->data; - count = reader.block->count; - } - while( length > 0 ); - } - - __END__; - - return subseq; -} - - -// Remove slice from the middle of the sequence. -// !!! TODO !!! Implement more efficient algorithm -CV_IMPL void -cvSeqRemoveSlice( CvSeq* seq, CvSlice slice ) -{ - CV_FUNCNAME("cvSeqRemoveSlice"); - - __BEGIN__; - - int total, length; - - if( !CV_IS_SEQ(seq) ) - CV_ERROR( CV_StsBadArg, "Invalid sequence header" ); - - length = cvSliceLength( slice, seq ); - total = seq->total; - - if( slice.start_index < 0 ) - slice.start_index += total; - else if( slice.start_index >= total ) - slice.start_index -= total; - - if( (unsigned)slice.start_index >= (unsigned)total ) - CV_ERROR( CV_StsOutOfRange, "start slice index is out of range" ); - - slice.end_index = slice.start_index + length; - - if( slice.end_index < total ) - { - CvSeqReader reader_to, reader_from; - int elem_size = seq->elem_size; - - cvStartReadSeq( seq, &reader_to ); - cvStartReadSeq( seq, &reader_from ); - - if( slice.start_index > total - slice.end_index ) - { - int i, count = seq->total - slice.end_index; - cvSetSeqReaderPos( &reader_to, slice.start_index ); - cvSetSeqReaderPos( &reader_from, slice.end_index ); - - for( i = 0; i < count; i++ ) - { - CV_MEMCPY_AUTO( 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.end_index - slice.start_index ); - } - else - { - int i, count = slice.start_index; - cvSetSeqReaderPos( &reader_to, slice.end_index ); - cvSetSeqReaderPos( &reader_from, slice.start_index ); - - for( i = 0; i < count; i++ ) - { - CV_PREV_SEQ_ELEM( elem_size, reader_to ); - CV_PREV_SEQ_ELEM( elem_size, reader_from ); - - CV_MEMCPY_AUTO( reader_to.ptr, reader_from.ptr, elem_size ); - } - - cvSeqPopMulti( seq, 0, slice.end_index - slice.start_index, 1 ); - } - } - else - { - cvSeqPopMulti( seq, 0, total - slice.start_index ); - cvSeqPopMulti( seq, 0, slice.end_index - total, 1 ); - } - - __END__; -} - - -// Insert a 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), - CV_ELEM_SIZE(mat->type), - mat->data.ptr, mat->cols + mat->rows - 1, - &from_header, &block )); - } - - if( seq->elem_size != from->elem_size ) - CV_ERROR( CV_StsUnmatchedSizes, - "Source and destination sequence element sizes 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( CV_StsOutOfRange, "" ); - - 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++ ) - { - CV_MEMCPY_AUTO( 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 ); - CV_MEMCPY_AUTO( reader_to.ptr, reader_from.ptr, elem_size ); - } - } - - cvStartReadSeq( from, &reader_from ); - cvSetSeqReaderPos( &reader_to, index ); - - for( i = 0; i < from_total; i++ ) - { - CV_MEMCPY_AUTO( 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. -// The semantics is similar to qsort() function. -// The code is based on BSD system qsort(): -// * Copyright (c) 1992, 1993 -// * The Regents of the University of California. All rights reserved. -// * -// * Redistribution and use in source and binary forms, with or without -// * modification, are permitted provided that the following conditions -// * are met: -// * 1. Redistributions of source code must retain the above copyright -// * notice, this list of conditions and the following disclaimer. -// * 2. Redistributions in binary form must reproduce the above copyright -// * notice, this list of conditions and the following disclaimer in the -// * documentation and/or other materials provided with the distribution. -// * 3. All advertising materials mentioning features or use of this software -// * must display the following acknowledgement: -// * This product includes software developed by the University of -// * California, Berkeley and its contributors. -// * 4. Neither the name of the University nor the names of its contributors -// * may be used to endorse or promote products derived from this software -// * without specific prior written permission. -// * -// * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND -// * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE -// * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE -// * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE -// * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -// * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS -// * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) -// * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT -// * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY -// * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF -// * SUCH DAMAGE. - -typedef struct CvSeqReaderPos -{ - CvSeqBlock* block; - schar* ptr; - schar* block_min; - schar* block_max; -} -CvSeqReaderPos; - -#define CV_SAVE_READER_POS( reader, pos ) \ -{ \ - (pos).block = (reader).block; \ - (pos).ptr = (reader).ptr; \ - (pos).block_min = (reader).block_min; \ - (pos).block_max = (reader).block_max; \ -} - -#define CV_RESTORE_READER_POS( reader, pos )\ -{ \ - (reader).block = (pos).block; \ - (reader).ptr = (pos).ptr; \ - (reader).block_min = (pos).block_min; \ - (reader).block_max = (pos).block_max; \ -} - -inline schar* -icvMed3( schar* a, schar* b, schar* c, CvCmpFunc cmp_func, void* aux ) -{ - return cmp_func(a, b, aux) < 0 ? - (cmp_func(b, c, aux) < 0 ? b : cmp_func(a, c, aux) < 0 ? c : a) - :(cmp_func(b, c, aux) > 0 ? b : cmp_func(a, c, aux) < 0 ? a : c); -} - -CV_IMPL void -cvSeqSort( CvSeq* seq, CvCmpFunc cmp_func, void* aux ) -{ - int elem_size; - int isort_thresh = 7; - CvSeqReader left, right; - int sp = 0; - - struct - { - CvSeqReaderPos lb; - CvSeqReaderPos ub; - } - stack[48]; - - CV_FUNCNAME( "cvSeqSort" ); - - __BEGIN__; - - if( !CV_IS_SEQ(seq) ) - CV_ERROR( !seq ? CV_StsNullPtr : CV_StsBadArg, "Bad input sequence" ); - - if( !cmp_func ) - CV_ERROR( CV_StsNullPtr, "Null compare function" ); - - if( seq->total <= 1 ) - EXIT; - - elem_size = seq->elem_size; - isort_thresh *= elem_size; - - cvStartReadSeq( seq, &left, 0 ); - right = left; - CV_SAVE_READER_POS( left, stack[0].lb ); - CV_PREV_SEQ_ELEM( elem_size, right ); - CV_SAVE_READER_POS( right, stack[0].ub ); - - while( sp >= 0 ) - { - CV_RESTORE_READER_POS( left, stack[sp].lb ); - CV_RESTORE_READER_POS( right, stack[sp].ub ); - sp--; - - for(;;) - { - int i, n, m; - CvSeqReader ptr, ptr2; - - if( left.block == right.block ) - n = (int)(right.ptr - left.ptr) + elem_size; - else - { - n = cvGetSeqReaderPos( &right ); - n = (n - cvGetSeqReaderPos( &left ) + 1)*elem_size; - } - - if( n <= isort_thresh ) - { - insert_sort: - ptr = ptr2 = left; - CV_NEXT_SEQ_ELEM( elem_size, ptr ); - CV_NEXT_SEQ_ELEM( elem_size, right ); - while( ptr.ptr != right.ptr ) - { - ptr2.ptr = ptr.ptr; - if( ptr2.block != ptr.block ) - { - ptr2.block = ptr.block; - ptr2.block_min = ptr.block_min; - ptr2.block_max = ptr.block_max; - } - while( ptr2.ptr != left.ptr ) - { - schar* cur = ptr2.ptr; - CV_PREV_SEQ_ELEM( elem_size, ptr2 ); - if( cmp_func( ptr2.ptr, cur, aux ) <= 0 ) - break; - CV_SWAP_ELEMS( ptr2.ptr, cur, elem_size ); - } - CV_NEXT_SEQ_ELEM( elem_size, ptr ); - } - break; - } - else - { - CvSeqReader left0, left1, right0, right1; - CvSeqReader tmp0, tmp1; - schar *m1, *m2, *m3, *pivot; - int swap_cnt = 0; - int l, l0, l1, r, r0, r1; - - left0 = tmp0 = left; - right0 = right1 = right; - n /= elem_size; - - if( n > 40 ) - { - int d = n / 8; - schar *p1, *p2, *p3; - p1 = tmp0.ptr; - cvSetSeqReaderPos( &tmp0, d, 1 ); - p2 = tmp0.ptr; - cvSetSeqReaderPos( &tmp0, d, 1 ); - p3 = tmp0.ptr; - m1 = icvMed3( p1, p2, p3, cmp_func, aux ); - cvSetSeqReaderPos( &tmp0, (n/2) - d*3, 1 ); - p1 = tmp0.ptr; - cvSetSeqReaderPos( &tmp0, d, 1 ); - p2 = tmp0.ptr; - cvSetSeqReaderPos( &tmp0, d, 1 ); - p3 = tmp0.ptr; - m2 = icvMed3( p1, p2, p3, cmp_func, aux ); - cvSetSeqReaderPos( &tmp0, n - 1 - d*3 - n/2, 1 ); - p1 = tmp0.ptr; - cvSetSeqReaderPos( &tmp0, d, 1 ); - p2 = tmp0.ptr; - cvSetSeqReaderPos( &tmp0, d, 1 ); - p3 = tmp0.ptr; - m3 = icvMed3( p1, p2, p3, cmp_func, aux ); - } - else - { - m1 = tmp0.ptr; - cvSetSeqReaderPos( &tmp0, n/2, 1 ); - m2 = tmp0.ptr; - cvSetSeqReaderPos( &tmp0, n - 1 - n/2, 1 ); - m3 = tmp0.ptr; - } - - pivot = icvMed3( m1, m2, m3, cmp_func, aux ); - left = left0; - if( pivot != left.ptr ) - { - CV_SWAP_ELEMS( pivot, left.ptr, elem_size ); - pivot = left.ptr; - } - CV_NEXT_SEQ_ELEM( elem_size, left ); - left1 = left; - - for(;;) - { - while( left.ptr != right.ptr && (r = cmp_func(left.ptr, pivot, aux)) <= 0 ) - { - if( r == 0 ) - { - if( left1.ptr != left.ptr ) - CV_SWAP_ELEMS( left1.ptr, left.ptr, elem_size ); - swap_cnt = 1; - CV_NEXT_SEQ_ELEM( elem_size, left1 ); - } - CV_NEXT_SEQ_ELEM( elem_size, left ); - } - - while( left.ptr != right.ptr && (r = cmp_func(right.ptr,pivot, aux)) >= 0 ) - { - if( r == 0 ) - { - if( right1.ptr != right.ptr ) - CV_SWAP_ELEMS( right1.ptr, right.ptr, elem_size ); - swap_cnt = 1; - CV_PREV_SEQ_ELEM( elem_size, right1 ); - } - CV_PREV_SEQ_ELEM( elem_size, right ); - } - - if( left.ptr == right.ptr ) - { - r = cmp_func(left.ptr, pivot, aux); - if( r == 0 ) - { - if( left1.ptr != left.ptr ) - CV_SWAP_ELEMS( left1.ptr, left.ptr, elem_size ); - swap_cnt = 1; - CV_NEXT_SEQ_ELEM( elem_size, left1 ); - } - if( r <= 0 ) - { - CV_NEXT_SEQ_ELEM( elem_size, left ); - } - else - { - CV_PREV_SEQ_ELEM( elem_size, right ); - } - break; - } - - CV_SWAP_ELEMS( left.ptr, right.ptr, elem_size ); - CV_NEXT_SEQ_ELEM( elem_size, left ); - r = left.ptr == right.ptr; - CV_PREV_SEQ_ELEM( elem_size, right ); - swap_cnt = 1; - if( r ) - break; - } - - if( swap_cnt == 0 ) - { - left = left0, right = right0; - goto insert_sort; - } - - l = cvGetSeqReaderPos( &left ); - if( l == 0 ) - l = seq->total; - l0 = cvGetSeqReaderPos( &left0 ); - l1 = cvGetSeqReaderPos( &left1 ); - if( l1 == 0 ) - l1 = seq->total; - - n = MIN( l - l1, l1 - l0 ); - if( n > 0 ) - { - tmp0 = left0; - tmp1 = left; - cvSetSeqReaderPos( &tmp1, 0-n, 1 ); - for( i = 0; i < n; i++ ) - { - CV_SWAP_ELEMS( tmp0.ptr, tmp1.ptr, elem_size ); - CV_NEXT_SEQ_ELEM( elem_size, tmp0 ); - CV_NEXT_SEQ_ELEM( elem_size, tmp1 ); - } - } - - r = cvGetSeqReaderPos( &right ); - r0 = cvGetSeqReaderPos( &right0 ); - r1 = cvGetSeqReaderPos( &right1 ); - m = MIN( r0 - r1, r1 - r ); - if( m > 0 ) - { - tmp0 = left; - tmp1 = right0; - cvSetSeqReaderPos( &tmp1, 1-m, 1 ); - for( i = 0; i < m; i++ ) - { - CV_SWAP_ELEMS( tmp0.ptr, tmp1.ptr, elem_size ); - CV_NEXT_SEQ_ELEM( elem_size, tmp0 ); - CV_NEXT_SEQ_ELEM( elem_size, tmp1 ); - } - } - - n = l - l1; - m = r1 - r; - if( n > 1 ) - { - if( m > 1 ) - { - if( n > m ) - { - sp++; - CV_SAVE_READER_POS( left0, stack[sp].lb ); - cvSetSeqReaderPos( &left0, n - 1, 1 ); - CV_SAVE_READER_POS( left0, stack[sp].ub ); - left = right = right0; - cvSetSeqReaderPos( &left, 1 - m, 1 ); - } - else - { - sp++; - CV_SAVE_READER_POS( right0, stack[sp].ub ); - cvSetSeqReaderPos( &right0, 1 - m, 1 ); - CV_SAVE_READER_POS( right0, stack[sp].lb ); - left = right = left0; - cvSetSeqReaderPos( &right, n - 1, 1 ); - } - } - else - { - left = right = left0; - cvSetSeqReaderPos( &right, n - 1, 1 ); - } - } - else if( m > 1 ) - { - left = right = right0; - cvSetSeqReaderPos( &left, 1 - m, 1 ); - } - else - break; - } - } - } - - __END__; -} - - -CV_IMPL schar* -cvSeqSearch( CvSeq* seq, const void* _elem, CvCmpFunc cmp_func, - int is_sorted, int* _idx, void* userdata ) -{ - schar* result = 0; - const schar* elem = (const schar*)_elem; - int idx = -1; - - CV_FUNCNAME("cvSeqSearch"); - - __BEGIN__; - - int elem_size, i, j, total; - - if( !CV_IS_SEQ(seq) ) - CV_ERROR( !seq ? CV_StsNullPtr : CV_StsBadArg, "Bad input sequence" ); - - if( !elem ) - CV_ERROR( CV_StsNullPtr, "Null element pointer" ); - - elem_size = seq->elem_size; - total = seq->total; - - if( total == 0 ) - EXIT; - - if( !is_sorted ) - { - CvSeqReader reader; - cvStartReadSeq( seq, &reader, 0 ); - - if( cmp_func ) - { - for( i = 0; i < total; i++ ) - { - if( cmp_func( elem, reader.ptr, userdata ) == 0 ) - break; - CV_NEXT_SEQ_ELEM( elem_size, reader ); - } - } - else if( (elem_size & (sizeof(int)-1)) == 0 ) - { - for( i = 0; i < total; i++ ) - { - for( j = 0; j < elem_size; j += sizeof(int) ) - { - if( *(const int*)(reader.ptr + j) != *(const int*)(elem + j) ) - break; - } - if( j == elem_size ) - break; - CV_NEXT_SEQ_ELEM( elem_size, reader ); - } - } - else - { - for( i = 0; i < total; i++ ) - { - for( j = 0; j < elem_size; j++ ) - { - if( reader.ptr[j] != elem[j] ) - break; - } - if( j == elem_size ) - break; - CV_NEXT_SEQ_ELEM( elem_size, reader ); - } - } - - idx = i; - if( i < total ) - result = reader.ptr; - } - else - { - if( !cmp_func ) - CV_ERROR( CV_StsNullPtr, "Null compare function" ); - - i = 0, j = total; - - while( j > i ) - { - int k = (i+j)>>1, code; - schar* ptr = cvGetSeqElem( seq, k ); - code = cmp_func( elem, ptr, userdata ); - if( !code ) - { - result = ptr; - idx = k; - EXIT; - } - if( code < 0 ) - j = k; - else - i = k+1; - } - idx = j; - } - - __END__; - - if( _idx ) - *_idx = idx; - - return result; -} - - -CV_IMPL void -cvSeqInvert( CvSeq* seq ) -{ - CV_FUNCNAME( "cvSeqInvert" ); - - __BEGIN__; - - CvSeqReader left_reader, right_reader; - int elem_size; - int i, count; - - CV_CALL( cvStartReadSeq( seq, &left_reader, 0 )); - CV_CALL( cvStartReadSeq( seq, &right_reader, 1 )); - elem_size = seq->elem_size; - count = seq->total >> 1; - - for( i = 0; i < count; i++ ) - { - CV_SWAP_ELEMS( left_reader.ptr, right_reader.ptr, elem_size ); - CV_NEXT_SEQ_ELEM( elem_size, left_reader ); - CV_PREV_SEQ_ELEM( elem_size, right_reader ); - } - - __END__; -} - - -typedef struct CvPTreeNode -{ - struct CvPTreeNode* parent; - schar* element; - int rank; -} -CvPTreeNode; - - -// This function splits the input sequence or set into one or more equivalence classes. -// is_equal(a,b,...) returns non-zero if the two sequence elements -// belong to the same class. The function returns sequence of integers - -// 0-based class indexes for each element. -// -// The algorithm is described in "Introduction to Algorithms" -// by Cormen, Leiserson and Rivest, chapter "Data structures for disjoint sets" -CV_IMPL int -cvSeqPartition( const CvSeq* seq, CvMemStorage* storage, CvSeq** labels, - CvCmpFunc is_equal, void* userdata ) -{ - CvSeq* result = 0; - CvMemStorage* temp_storage = 0; - int class_idx = 0; - - CV_FUNCNAME( "cvSeqPartition" ); - - __BEGIN__; - - CvSeqWriter writer; - CvSeqReader reader, reader0; - CvSeq* nodes; - int i, j; - int is_set; - - if( !labels ) - CV_ERROR( CV_StsNullPtr, "" ); - - if( !seq || !is_equal ) - CV_ERROR( CV_StsNullPtr, "" ); - - if( !storage ) - storage = seq->storage; - - if( !storage ) - CV_ERROR( CV_StsNullPtr, "" ); - - is_set = CV_IS_SET(seq); - - 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 in the next loop we will iterate - // through all the sequence nodes each time, - // we do not need to initialize reader every time: - cvStartReadSeq( nodes, &reader ); - cvStartReadSeq( nodes, &reader0 ); - - // The main O(N^2) pass. Merge connected components. - for( i = 0; i < nodes->total; i++ ) - { - CvPTreeNode* node = (CvPTreeNode*)(reader0.ptr); - CvPTreeNode* root = node; - CV_NEXT_SEQ_ELEM( nodes->elem_size, reader0 ); - - 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( labels ) - *labels = result; - - cvReleaseMemStorage( &temp_storage ); - return class_idx; -} - - -/****************************************************************************************\ -* Set implementation * -\****************************************************************************************/ - -/* Creates empty set: */ -CV_IMPL CvSet* -cvCreateSet( int set_flags, int header_size, int elem_size, CvMemStorage * storage ) -{ - CvSet *set = 0; - - CV_FUNCNAME( "cvCreateSet" ); - - __BEGIN__; - - if( !storage ) - CV_ERROR( CV_StsNullPtr, "" ); - if( header_size < (int)sizeof( CvSet ) || - elem_size < (int)sizeof(void*)*2 || - (elem_size & (sizeof(void*)-1)) != 0 ) - CV_ERROR( CV_StsBadSize, "" ); - - set = (CvSet*) cvCreateSeq( set_flags, header_size, elem_size, storage ); - set->flags = (set->flags & ~CV_MAGIC_MASK) | CV_SET_MAGIC_VAL; - - __END__; - - return set; -} - - -/* Add new element to the set: */ -CV_IMPL int -cvSetAdd( CvSet* set, CvSetElem* element, CvSetElem** inserted_element ) -{ - int id = -1; - - CV_FUNCNAME( "cvSetAdd" ); - - __BEGIN__; - - CvSetElem *free_elem; - - if( !set ) - CV_ERROR( CV_StsNullPtr, "" ); - - if( !(set->free_elems) ) - { - int count = set->total; - int elem_size = set->elem_size; - schar *ptr; - CV_CALL( icvGrowSeq( (CvSeq *) set, 0 )); - - set->free_elems = (CvSetElem*) (ptr = set->ptr); - for( ; ptr + elem_size <= set->block_max; ptr += elem_size, count++ ) - { - ((CvSetElem*)ptr)->flags = count | CV_SET_ELEM_FREE_FLAG; - ((CvSetElem*)ptr)->next_free = (CvSetElem*)(ptr + elem_size); - } - assert( count <= CV_SET_ELEM_IDX_MASK+1 ); - ((CvSetElem*)(ptr - elem_size))->next_free = 0; - set->first->prev->count += count - set->total; - set->total = count; - set->ptr = set->block_max; - } - - free_elem = set->free_elems; - set->free_elems = free_elem->next_free; - - id = free_elem->flags & CV_SET_ELEM_IDX_MASK; - if( element ) - CV_MEMCPY_INT( free_elem, element, (size_t)set->elem_size/sizeof(int) ); - - free_elem->flags = id; - set->active_count++; - - if( inserted_element ) - *inserted_element = free_elem; - - __END__; - - return id; -} - - -/* Remove element from a set given element index: */ -CV_IMPL void -cvSetRemove( CvSet* set, int index ) -{ - CV_FUNCNAME( "cvSetRemove" ); - - __BEGIN__; - - CvSetElem* elem = cvGetSetElem( set, index ); - if( elem ) - cvSetRemoveByPtr( set, elem ); - else if( !set ) - CV_ERROR( CV_StsNullPtr, "" ); - - __END__; -} - - -/* Remove all elements from a set: */ -CV_IMPL void -cvClearSet( CvSet* set ) -{ - CV_FUNCNAME( "cvClearSet" ); - - __BEGIN__; - - CV_CALL( cvClearSeq( (CvSeq*)set )); - set->free_elems = 0; - set->active_count = 0; - - __END__; -} - - -/****************************************************************************************\ -* Graph implementation * -\****************************************************************************************/ - -/* Create a new graph: */ -CV_IMPL CvGraph * -cvCreateGraph( int graph_type, int header_size, - int vtx_size, int edge_size, CvMemStorage * storage ) -{ - CvGraph *graph = 0; - CvSet *edges = 0; - - CV_FUNCNAME( "cvCleateGraph" ); - - __BEGIN__; - - CvSet *vertices = 0; - - if( header_size < (int) sizeof( CvGraph ) - || edge_size < (int) sizeof( CvGraphEdge ) - || vtx_size < (int) sizeof( CvGraphVtx ) - ){ - CV_ERROR( CV_StsBadSize, "" ); - } - - CV_CALL( vertices = cvCreateSet( graph_type, header_size, vtx_size, storage )); - CV_CALL( edges = cvCreateSet( CV_SEQ_KIND_GENERIC | CV_SEQ_ELTYPE_GRAPH_EDGE, - sizeof( CvSet ), edge_size, storage )); - - graph = (CvGraph*)vertices; - graph->edges = edges; - - __END__; - - return graph; -} - - -/* Remove all vertices and edges from a graph: */ -CV_IMPL void -cvClearGraph( CvGraph * graph ) -{ - CV_FUNCNAME( "cvClearGraph" ); - - __BEGIN__; - - if( !graph ) - CV_ERROR( CV_StsNullPtr, "" ); - - cvClearSet( graph->edges ); - cvClearSet( (CvSet*)graph ); - - __END__; -} - - -/* Add a vertex to a graph: */ -CV_IMPL int -cvGraphAddVtx( CvGraph* graph, const CvGraphVtx* _vertex, CvGraphVtx** _inserted_vertex ) -{ - CvGraphVtx *vertex = 0; - int index = -1; - - CV_FUNCNAME( "cvGraphAddVtx" ); - - __BEGIN__; - - if( !graph ) - CV_ERROR( CV_StsNullPtr, "" ); - - vertex = (CvGraphVtx*)cvSetNew((CvSet*)graph); - if( vertex ) - { - if( _vertex ) - CV_MEMCPY_INT( vertex + 1, _vertex + 1, - (size_t)(graph->elem_size - sizeof(CvGraphVtx))/sizeof(int) ); - vertex->first = 0; - index = vertex->flags; - } - - if( _inserted_vertex ) - *_inserted_vertex = vertex; - - __END__; - - return index; -} - - -/* Remove a vertex from the graph together with its incident edges: */ -CV_IMPL int -cvGraphRemoveVtxByPtr( CvGraph* graph, CvGraphVtx* vtx ) -{ - int count = -1; - - CV_FUNCNAME( "cvGraphRemoveVtxByPtr" ); - - __BEGIN__; - - if( !graph || !vtx ) - CV_ERROR( CV_StsNullPtr, "" ); - - if( !CV_IS_SET_ELEM(vtx)) - CV_ERROR( CV_StsBadArg, "The vertex does not belong to the graph" ); - - count = graph->edges->active_count; - for( ;; ) - { - CvGraphEdge *edge = vtx->first; - if( !edge ) - break; - cvGraphRemoveEdgeByPtr( graph, edge->vtx[0], edge->vtx[1] ); - } - count -= graph->edges->active_count; - cvSetRemoveByPtr( (CvSet*)graph, vtx ); - - __END__; - - return count; -} - - -/* Remove a vertex from the graph together with its incident edges: */ -CV_IMPL int -cvGraphRemoveVtx( CvGraph* graph, int index ) -{ - int count = -1; - CvGraphVtx *vtx = 0; - - CV_FUNCNAME( "cvGraphRemoveVtx" ); - - __BEGIN__; - - if( !graph ) - CV_ERROR( CV_StsNullPtr, "" ); - - vtx = cvGetGraphVtx( graph, index ); - if( !vtx ) - CV_ERROR( CV_StsBadArg, "The vertex is not found" ); - - count = graph->edges->active_count; - for( ;; ) - { - CvGraphEdge *edge = vtx->first; - count++; - - if( !edge ) - break; - cvGraphRemoveEdgeByPtr( graph, edge->vtx[0], edge->vtx[1] ); - } - count -= graph->edges->active_count; - cvSetRemoveByPtr( (CvSet*)graph, vtx ); - - __END__; - - return count; -} - - -/* Find a graph edge given pointers to the ending vertices: */ -CV_IMPL CvGraphEdge* -cvFindGraphEdgeByPtr( const CvGraph* graph, - const CvGraphVtx* start_vtx, - const CvGraphVtx* end_vtx ) -{ - CvGraphEdge *edge = 0; - CV_FUNCNAME( "cvFindGraphEdgeByPtr" ); - - __BEGIN__; - - int ofs = 0; - - if( !graph || !start_vtx || !end_vtx ) - CV_ERROR( CV_StsNullPtr, "" ); - - if( start_vtx == end_vtx ) - EXIT; - - if( !CV_IS_GRAPH_ORIENTED( graph ) && - (start_vtx->flags & CV_SET_ELEM_IDX_MASK) > (end_vtx->flags & CV_SET_ELEM_IDX_MASK) ) - { - const CvGraphVtx* t; - CV_SWAP( start_vtx, end_vtx, t ); - } - - edge = start_vtx->first; - for( ; edge; edge = edge->next[ofs] ) - { - ofs = start_vtx == edge->vtx[1]; - assert( ofs == 1 || start_vtx == edge->vtx[0] ); - if( edge->vtx[1] == end_vtx ) - break; - } - - __END__; - - return edge; -} - - -/* Find an edge in the graph given indices of the ending vertices: */ -CV_IMPL CvGraphEdge * -cvFindGraphEdge( const CvGraph* graph, int start_idx, int end_idx ) -{ - CvGraphEdge *edge = 0; - CvGraphVtx *start_vtx; - CvGraphVtx *end_vtx; - - CV_FUNCNAME( "cvFindGraphEdge" ); - - __BEGIN__; - - if( !graph ) - CV_ERROR( CV_StsNullPtr, "graph pointer is NULL" ); - - start_vtx = cvGetGraphVtx( graph, start_idx ); - end_vtx = cvGetGraphVtx( graph, end_idx ); - - edge = cvFindGraphEdgeByPtr( graph, start_vtx, end_vtx ); - - __END__; - - return edge; -} - - -/* Given two vertices, return the edge - * connecting them, creating it if it - * did not already exist: - */ -CV_IMPL int -cvGraphAddEdgeByPtr( CvGraph* graph, - CvGraphVtx* start_vtx, CvGraphVtx* end_vtx, - const CvGraphEdge* _edge, - CvGraphEdge ** _inserted_edge ) -{ - CvGraphEdge *edge = 0; - int result = -1; - - CV_FUNCNAME( "cvGraphAddEdgeByPtr" ); - - __BEGIN__; - - int delta; - - if( !graph ) - CV_ERROR( CV_StsNullPtr, "graph pointer is NULL" ); - - if( !CV_IS_GRAPH_ORIENTED( graph ) && - (start_vtx->flags & CV_SET_ELEM_IDX_MASK) > (end_vtx->flags & CV_SET_ELEM_IDX_MASK) ) - { - CvGraphVtx* t; - CV_SWAP( start_vtx, end_vtx, t ); - } - - CV_CALL( edge = cvFindGraphEdgeByPtr( graph, start_vtx, end_vtx )); - if( edge ) - { - result = 0; - EXIT; - } - - if( start_vtx == end_vtx ) - CV_ERROR( start_vtx ? CV_StsBadArg : CV_StsNullPtr, - "vertex pointers coinside (or set to NULL)" ); - - CV_CALL( edge = (CvGraphEdge*)cvSetNew( (CvSet*)(graph->edges) )); - assert( edge->flags >= 0 ); - - edge->vtx[0] = start_vtx; - edge->vtx[1] = end_vtx; - edge->next[0] = start_vtx->first; - edge->next[1] = end_vtx->first; - start_vtx->first = end_vtx->first = edge; - - delta = (graph->edges->elem_size - sizeof(*edge))/sizeof(int); - if( _edge ) - { - if( delta > 0 ) - CV_MEMCPY_INT( edge + 1, _edge + 1, delta ); - edge->weight = _edge->weight; - } - else - { - if( delta > 0 ) - CV_ZERO_INT( edge + 1, delta ); - edge->weight = 1.f; - } - - result = 1; - - __END__; - - if( _inserted_edge ) - *_inserted_edge = edge; - - return result; -} - -/* Given two vertices, return the edge - * connecting them, creating it if it - * did not already exist: - */ -CV_IMPL int -cvGraphAddEdge( CvGraph* graph, - int start_idx, int end_idx, - const CvGraphEdge* _edge, - CvGraphEdge ** _inserted_edge ) -{ - CvGraphVtx *start_vtx; - CvGraphVtx *end_vtx; - int result = -1; - - CV_FUNCNAME( "cvGraphAddEdge" ); - - __BEGIN__; - - if( !graph ) - CV_ERROR( CV_StsNullPtr, "" ); - - start_vtx = cvGetGraphVtx( graph, start_idx ); - end_vtx = cvGetGraphVtx( graph, end_idx ); - - result = cvGraphAddEdgeByPtr( graph, start_vtx, end_vtx, _edge, _inserted_edge ); - - __END__; - - return result; -} - - -/* Remove the graph edge connecting two given vertices: */ -CV_IMPL void -cvGraphRemoveEdgeByPtr( CvGraph* graph, CvGraphVtx* start_vtx, CvGraphVtx* end_vtx ) -{ - CV_FUNCNAME( "cvGraphRemoveEdgeByPtr" ); - - __BEGIN__; - - int ofs, prev_ofs; - CvGraphEdge *edge, *next_edge, *prev_edge; - - if( !graph || !start_vtx || !end_vtx ) - CV_ERROR( CV_StsNullPtr, "" ); - - if( start_vtx == end_vtx ) - EXIT; - - if( !CV_IS_GRAPH_ORIENTED( graph ) && - (start_vtx->flags & CV_SET_ELEM_IDX_MASK) > (end_vtx->flags & CV_SET_ELEM_IDX_MASK) ) - { - CvGraphVtx* t; - CV_SWAP( start_vtx, end_vtx, t ); - } - - for( ofs = prev_ofs = 0, prev_edge = 0, edge = start_vtx->first; edge != 0; - prev_ofs = ofs, prev_edge = edge, edge = edge->next[ofs] ) - { - ofs = start_vtx == edge->vtx[1]; - assert( ofs == 1 || start_vtx == edge->vtx[0] ); - if( edge->vtx[1] == end_vtx ) - break; - } - - if( !edge ) - EXIT; - - next_edge = edge->next[ofs]; - if( prev_edge ) - prev_edge->next[prev_ofs] = next_edge; - else - start_vtx->first = next_edge; - - for( ofs = prev_ofs = 0, prev_edge = 0, edge = end_vtx->first; edge != 0; - prev_ofs = ofs, prev_edge = edge, edge = edge->next[ofs] ) - { - ofs = end_vtx == edge->vtx[1]; - assert( ofs == 1 || end_vtx == edge->vtx[0] ); - if( edge->vtx[0] == start_vtx ) - break; - } - - assert( edge != 0 ); - - next_edge = edge->next[ofs]; - if( prev_edge ) - prev_edge->next[prev_ofs] = next_edge; - else - end_vtx->first = next_edge; - - cvSetRemoveByPtr( graph->edges, edge ); - - __END__; -} - - -/* Remove the graph edge connecting two given vertices: */ -CV_IMPL void -cvGraphRemoveEdge( CvGraph* graph, int start_idx, int end_idx ) -{ - CvGraphVtx *start_vtx; - CvGraphVtx *end_vtx; - - CV_FUNCNAME( "cvGraphRemoveEdge" ); - - __BEGIN__; - - if( !graph ) - CV_ERROR( CV_StsNullPtr, "" ); - - start_vtx = cvGetGraphVtx( graph, start_idx ); - end_vtx = cvGetGraphVtx( graph, end_idx ); - - cvGraphRemoveEdgeByPtr( graph, start_vtx, end_vtx ); - - __END__; -} - - -/* Count number of edges incident to a given vertex: */ -CV_IMPL int -cvGraphVtxDegreeByPtr( const CvGraph* graph, const CvGraphVtx* vertex ) -{ - CvGraphEdge *edge; - int count = -1; - - CV_FUNCNAME( "cvGraphVtxDegreeByPtr" ); - - __BEGIN__; - - if( !graph || !vertex ) - CV_ERROR( CV_StsNullPtr, "" ); - - for( edge = vertex->first, count = 0; edge; ) - { - count++; - edge = CV_NEXT_GRAPH_EDGE( edge, vertex ); - } - - __END__; - - return count; -} - - -/* Count number of edges incident to a given vertex: */ -CV_IMPL int -cvGraphVtxDegree( const CvGraph* graph, int vtx_idx ) -{ - CvGraphVtx *vertex; - CvGraphEdge *edge; - int count = -1; - - CV_FUNCNAME( "cvGraphVtxDegree" ); - - __BEGIN__; - - if( !graph ) - CV_ERROR( CV_StsNullPtr, "" ); - - vertex = cvGetGraphVtx( graph, vtx_idx ); - if( !vertex ) - CV_ERROR( CV_StsObjectNotFound, "" ); - - for( edge = vertex->first, count = 0; edge; ) - { - count++; - edge = CV_NEXT_GRAPH_EDGE( edge, vertex ); - } - - __END__; - - return count; -} - - -typedef struct CvGraphItem -{ - CvGraphVtx* vtx; - CvGraphEdge* edge; -} -CvGraphItem; - - -static void -icvSeqElemsClearFlags( CvSeq* seq, int offset, int clear_mask ) -{ - CV_FUNCNAME("icvStartScanGraph"); - - __BEGIN__; - - CvSeqReader reader; - int i, total, elem_size; - - if( !seq ) - CV_ERROR( CV_StsNullPtr, "" ); - - elem_size = seq->elem_size; - total = seq->total; - - if( (unsigned)offset > (unsigned)elem_size ) - CV_ERROR( CV_StsBadArg, "" ); - - CV_CALL( cvStartReadSeq( seq, &reader )); - - for( i = 0; i < total; i++ ) - { - int* flag_ptr = (int*)(reader.ptr + offset); - *flag_ptr &= ~clear_mask; - - CV_NEXT_SEQ_ELEM( elem_size, reader ); - } - - __END__; -} - - -static schar* -icvSeqFindNextElem( CvSeq* seq, int offset, int mask, - int value, int* start_index ) -{ - schar* elem_ptr = 0; - - CV_FUNCNAME("icvStartScanGraph"); - - __BEGIN__; - - CvSeqReader reader; - int total, elem_size, index; - - if( !seq || !start_index ) - CV_ERROR( CV_StsNullPtr, "" ); - - elem_size = seq->elem_size; - total = seq->total; - index = *start_index; - - if( (unsigned)offset > (unsigned)elem_size ) - CV_ERROR( CV_StsBadArg, "" ); - - if( total == 0 ) - EXIT; - - if( (unsigned)index >= (unsigned)total ) - { - index %= total; - index += index < 0 ? total : 0; - } - - CV_CALL( cvStartReadSeq( seq, &reader )); - - if( index != 0 ) - CV_CALL( cvSetSeqReaderPos( &reader, index )); - - for( index = 0; index < total; index++ ) - { - int* flag_ptr = (int*)(reader.ptr + offset); - if( (*flag_ptr & mask) == value ) - break; - - CV_NEXT_SEQ_ELEM( elem_size, reader ); - } - - if( index < total ) - { - elem_ptr = reader.ptr; - *start_index = index; - } - - __END__; - - return elem_ptr; -} - -#define CV_FIELD_OFFSET( field, structtype ) ((int)(size_t)&((structtype*)0)->field) - -CV_IMPL CvGraphScanner* -cvCreateGraphScanner( CvGraph* graph, CvGraphVtx* vtx, int mask ) -{ - CvGraphScanner* scanner = 0; - CvMemStorage* child_storage = 0; - - CV_FUNCNAME("cvCreateGraphScanner"); - - __BEGIN__; - - if( !graph ) - CV_ERROR( CV_StsNullPtr, "Null graph pointer" ); - - CV_ASSERT( graph->storage != 0 ); - - CV_CALL( scanner = (CvGraphScanner*)cvAlloc( sizeof(*scanner) )); - memset( scanner, 0, sizeof(*scanner)); - - scanner->graph = graph; - scanner->mask = mask; - scanner->vtx = vtx; - scanner->index = vtx == 0 ? 0 : -1; - - CV_CALL( child_storage = cvCreateChildMemStorage( graph->storage )); - - CV_CALL( scanner->stack = cvCreateSeq( 0, sizeof(CvSet), - sizeof(CvGraphItem), child_storage )); - - CV_CALL( icvSeqElemsClearFlags( (CvSeq*)graph, - CV_FIELD_OFFSET( flags, CvGraphVtx), - CV_GRAPH_ITEM_VISITED_FLAG| - CV_GRAPH_SEARCH_TREE_NODE_FLAG )); - - CV_CALL( icvSeqElemsClearFlags( (CvSeq*)(graph->edges), - CV_FIELD_OFFSET( flags, CvGraphEdge), - CV_GRAPH_ITEM_VISITED_FLAG )); - - __END__; - - if( cvGetErrStatus() < 0 ) - { - cvReleaseMemStorage( &child_storage ); - cvFree( &scanner ); - } - - return scanner; -} - - -CV_IMPL void -cvReleaseGraphScanner( CvGraphScanner** scanner ) -{ - CV_FUNCNAME("cvReleaseGraphScanner"); - - __BEGIN__; - - if( !scanner ) - CV_ERROR( CV_StsNullPtr, "Null double pointer to graph scanner" ); - - if( *scanner ) - { - if( (*scanner)->stack ) - CV_CALL( cvReleaseMemStorage( &((*scanner)->stack->storage))); - cvFree( scanner ); - } - - __END__; -} - - -CV_IMPL int -cvNextGraphItem( CvGraphScanner* scanner ) -{ - int code = -1; - - CV_FUNCNAME("cvNextGraphItem"); - - __BEGIN__; - - CvGraphVtx* vtx; - CvGraphVtx* dst; - CvGraphEdge* edge; - CvGraphItem item; - - if( !scanner || !(scanner->stack)) - CV_ERROR( CV_StsNullPtr, "Null graph scanner" ); - - dst = scanner->dst; - vtx = scanner->vtx; - edge = scanner->edge; - - for(;;) - { - for(;;) - { - if( dst && !CV_IS_GRAPH_VERTEX_VISITED(dst) ) - { - scanner->vtx = vtx = dst; - edge = vtx->first; - dst->flags |= CV_GRAPH_ITEM_VISITED_FLAG; - - if((scanner->mask & CV_GRAPH_VERTEX)) - { - scanner->vtx = vtx; - scanner->edge = vtx->first; - scanner->dst = 0; - code = CV_GRAPH_VERTEX; - EXIT; - } - } - - while( edge ) - { - dst = edge->vtx[vtx == edge->vtx[0]]; - - if( !CV_IS_GRAPH_EDGE_VISITED(edge) ) - { - // Check that the edge is outgoing: - if( !CV_IS_GRAPH_ORIENTED( scanner->graph ) || dst != edge->vtx[0] ) - { - edge->flags |= CV_GRAPH_ITEM_VISITED_FLAG; - - if( !CV_IS_GRAPH_VERTEX_VISITED(dst) ) - { - item.vtx = vtx; - item.edge = edge; - - vtx->flags |= CV_GRAPH_SEARCH_TREE_NODE_FLAG; - - cvSeqPush( scanner->stack, &item ); - - if( scanner->mask & CV_GRAPH_TREE_EDGE ) - { - code = CV_GRAPH_TREE_EDGE; - scanner->vtx = vtx; - scanner->dst = dst; - scanner->edge = edge; - EXIT; - } - break; - } - else - { - if( scanner->mask & (CV_GRAPH_BACK_EDGE| - CV_GRAPH_CROSS_EDGE| - CV_GRAPH_FORWARD_EDGE) ) - { - code = (dst->flags & CV_GRAPH_SEARCH_TREE_NODE_FLAG) ? - CV_GRAPH_BACK_EDGE : - (edge->flags & CV_GRAPH_FORWARD_EDGE_FLAG) ? - CV_GRAPH_FORWARD_EDGE : CV_GRAPH_CROSS_EDGE; - edge->flags &= ~CV_GRAPH_FORWARD_EDGE_FLAG; - if( scanner->mask & code ) - { - scanner->vtx = vtx; - scanner->dst = dst; - scanner->edge = edge; - EXIT; - } - } - } - } - else if( (dst->flags & (CV_GRAPH_ITEM_VISITED_FLAG| - CV_GRAPH_SEARCH_TREE_NODE_FLAG)) == - (CV_GRAPH_ITEM_VISITED_FLAG| - CV_GRAPH_SEARCH_TREE_NODE_FLAG)) - { - edge->flags |= CV_GRAPH_FORWARD_EDGE_FLAG; - } - } - - edge = CV_NEXT_GRAPH_EDGE( edge, vtx ); - } - - if( !edge ) /* need to backtrack */ - { - if( scanner->stack->total == 0 ) - { - if( scanner->index >= 0 ) - vtx = 0; - else - scanner->index = 0; - break; - } - cvSeqPop( scanner->stack, &item ); - vtx = item.vtx; - vtx->flags &= ~CV_GRAPH_SEARCH_TREE_NODE_FLAG; - edge = item.edge; - dst = 0; - - if( scanner->mask & CV_GRAPH_BACKTRACKING ) - { - scanner->vtx = vtx; - scanner->edge = edge; - scanner->dst = edge->vtx[vtx == edge->vtx[0]]; - code = CV_GRAPH_BACKTRACKING; - EXIT; - } - } - } - - if( !vtx ) - { - vtx = (CvGraphVtx*)icvSeqFindNextElem( (CvSeq*)(scanner->graph), - CV_FIELD_OFFSET( flags, CvGraphVtx ), CV_GRAPH_ITEM_VISITED_FLAG|INT_MIN, - 0, &(scanner->index) ); - - if( !vtx ) - { - code = CV_GRAPH_OVER; - break; - } - } - - dst = vtx; - if( scanner->mask & CV_GRAPH_NEW_TREE ) - { - scanner->dst = dst; - scanner->edge = 0; - scanner->vtx = 0; - code = CV_GRAPH_NEW_TREE; - break; - } - } - - __END__; - - return code; -} - - -CV_IMPL CvGraph* -cvCloneGraph( const CvGraph* graph, CvMemStorage* storage ) -{ - int* flag_buffer = 0; - CvGraphVtx** ptr_buffer = 0; - CvGraph* result = 0; - - CV_FUNCNAME( "cvCloneGraph" ); - - __BEGIN__; - - int i, k; - int vtx_size, edge_size; - CvSeqReader reader; - - if( !CV_IS_GRAPH(graph)) - CV_ERROR( CV_StsBadArg, "Invalid graph pointer" ); - - if( !storage ) - storage = graph->storage; - - if( !storage ) - CV_ERROR( CV_StsNullPtr, "NULL storage pointer" ); - - vtx_size = graph->elem_size; - edge_size = graph->edges->elem_size; - - CV_CALL( flag_buffer = (int*)cvAlloc( graph->total*sizeof(flag_buffer[0]))); - CV_CALL( ptr_buffer = (CvGraphVtx**)cvAlloc( graph->total*sizeof(ptr_buffer[0]))); - CV_CALL( result = cvCreateGraph( graph->flags, graph->header_size, - vtx_size, edge_size, storage )); - memcpy( result + sizeof(CvGraph), graph + sizeof(CvGraph), - graph->header_size - sizeof(CvGraph)); - - // Pass 1. Save flags, copy vertices: - cvStartReadSeq( (CvSeq*)graph, &reader ); - for( i = 0, k = 0; i < graph->total; i++ ) - { - if( CV_IS_SET_ELEM( reader.ptr )) - { - CvGraphVtx* vtx = (CvGraphVtx*)reader.ptr; - CvGraphVtx* dstvtx = 0; - CV_CALL( cvGraphAddVtx( result, vtx, &dstvtx )); - flag_buffer[k] = dstvtx->flags = vtx->flags; - vtx->flags = k; - ptr_buffer[k++] = dstvtx; - } - CV_NEXT_SEQ_ELEM( vtx_size, reader ); - } - - // Pass 2. Copy edges: - cvStartReadSeq( (CvSeq*)graph->edges, &reader ); - for( i = 0; i < graph->edges->total; i++ ) - { - if( CV_IS_SET_ELEM( reader.ptr )) - { - CvGraphEdge* edge = (CvGraphEdge*)reader.ptr; - CvGraphEdge* dstedge = 0; - CvGraphVtx* new_org = ptr_buffer[edge->vtx[0]->flags]; - CvGraphVtx* new_dst = ptr_buffer[edge->vtx[1]->flags]; - CV_CALL( cvGraphAddEdgeByPtr( result, new_org, new_dst, edge, &dstedge )); - dstedge->flags = edge->flags; - } - CV_NEXT_SEQ_ELEM( edge_size, reader ); - } - - // Pass 3. Restore flags: - cvStartReadSeq( (CvSeq*)graph, &reader ); - for( i = 0, k = 0; i < graph->edges->total; i++ ) - { - if( CV_IS_SET_ELEM( reader.ptr )) - { - CvGraphVtx* vtx = (CvGraphVtx*)reader.ptr; - vtx->flags = flag_buffer[k++]; - } - CV_NEXT_SEQ_ELEM( vtx_size, reader ); - } - - __END__; - - cvFree( &flag_buffer ); - cvFree( &ptr_buffer ); - - if( cvGetErrStatus() < 0 ) - result = 0; - - return result; -} - - -/****************************************************************************************\ -* Working with sequence tree * -\****************************************************************************************/ - -// Gather pointers to all the sequences, accessible from the , to the single sequence. -CV_IMPL CvSeq* -cvTreeToNodeSeq( const void* first, int header_size, CvMemStorage* storage ) -{ - CvSeq* allseq = 0; - - CV_FUNCNAME("cvTreeToNodeSeq"); - - __BEGIN__; - - CvTreeNodeIterator iterator; - - if( !storage ) - CV_ERROR( CV_StsNullPtr, "NULL storage pointer" ); - - CV_CALL( allseq = cvCreateSeq( 0, header_size, sizeof(first), storage )); - - if( first ) - { - CV_CALL( cvInitTreeNodeIterator( &iterator, first, INT_MAX )); - - for(;;) - { - void* node = cvNextTreeNode( &iterator ); - if( !node ) - break; - cvSeqPush( allseq, &node ); - } - } - - __END__; - - return allseq; -} - - -typedef struct CvTreeNode -{ - int flags; /* micsellaneous flags */ - int header_size; /* size of sequence header */ - struct CvTreeNode* h_prev; /* previous sequence */ - struct CvTreeNode* h_next; /* next sequence */ - struct CvTreeNode* v_prev; /* 2nd previous sequence */ - struct CvTreeNode* v_next; /* 2nd next sequence */ -} -CvTreeNode; - - - -// Insert contour into tree given certain parent sequence. -// If parent is equal to frame (the most external contour), -// then added contour will have null pointer to parent: -CV_IMPL void -cvInsertNodeIntoTree( void* _node, void* _parent, void* _frame ) -{ - CV_FUNCNAME( "cvInsertNodeIntoTree" ); - - __BEGIN__; - - CvTreeNode* node = (CvTreeNode*)_node; - CvTreeNode* parent = (CvTreeNode*)_parent; - - if( !node || !parent ) - CV_ERROR( CV_StsNullPtr, "" ); - - node->v_prev = _parent != _frame ? parent : 0; - node->h_next = parent->v_next; - - assert( parent->v_next != node ); - - if( parent->v_next ) - parent->v_next->h_prev = node; - parent->v_next = node; - - __END__; -} - - -// Remove contour from tree, together with the contour's children: -CV_IMPL void -cvRemoveNodeFromTree( void* _node, void* _frame ) -{ - CV_FUNCNAME( "cvRemoveNodeFromTree" ); - - __BEGIN__; - - CvTreeNode* node = (CvTreeNode*)_node; - CvTreeNode* frame = (CvTreeNode*)_frame; - - if( !node ) - CV_ERROR_FROM_CODE( CV_StsNullPtr ); - - if( node == frame ) - CV_ERROR( CV_StsBadArg, "frame node could not be deleted" ); - - if( node->h_next ) - node->h_next->h_prev = node->h_prev; - - if( node->h_prev ) - node->h_prev->h_next = node->h_next; - else - { - CvTreeNode* parent = node->v_prev; - if( !parent ) - parent = frame; - - if( parent ) - { - assert( parent->v_next == node ); - parent->v_next = node->h_next; - } - } - - __END__; -} - - -CV_IMPL void -cvInitTreeNodeIterator( CvTreeNodeIterator* treeIterator, - const void* first, int max_level ) -{ - CV_FUNCNAME("icvInitTreeNodeIterator"); - - __BEGIN__; - - if( !treeIterator || !first ) - CV_ERROR( CV_StsNullPtr, "" ); - - if( max_level < 0 ) - CV_ERROR( CV_StsOutOfRange, "" ); - - treeIterator->node = (void*)first; - treeIterator->level = 0; - treeIterator->max_level = max_level; - - __END__; -} - - -CV_IMPL void* -cvNextTreeNode( CvTreeNodeIterator* treeIterator ) -{ - CvTreeNode* prevNode = 0; - - CV_FUNCNAME("cvNextTreeNode"); - - __BEGIN__; - - CvTreeNode* node; - int level; - - if( !treeIterator ) - CV_ERROR( CV_StsNullPtr, "NULL iterator pointer" ); - - prevNode = node = (CvTreeNode*)treeIterator->node; - level = treeIterator->level; - - if( node ) - { - if( node->v_next && level+1 < treeIterator->max_level ) - { - node = node->v_next; - level++; - } - else - { - while( node->h_next == 0 ) - { - node = node->v_prev; - if( --level < 0 ) - { - node = 0; - break; - } - } - node = node && treeIterator->max_level != 0 ? node->h_next : 0; - } - } - - treeIterator->node = node; - treeIterator->level = level; - - __END__; - - return prevNode; -} - - -CV_IMPL void* -cvPrevTreeNode( CvTreeNodeIterator* treeIterator ) -{ - CvTreeNode* prevNode = 0; - - CV_FUNCNAME("cvPrevTreeNode"); - - __BEGIN__; - - CvTreeNode* node; - int level; - - if( !treeIterator ) - CV_ERROR( CV_StsNullPtr, "" ); - - prevNode = node = (CvTreeNode*)treeIterator->node; - level = treeIterator->level; - - if( node ) - { - if( !node->h_prev ) - { - node = node->v_prev; - if( --level < 0 ) - node = 0; - } - else - { - node = node->h_prev; - - while( node->v_next && level < treeIterator->max_level ) - { - node = node->v_next; - level++; - - while( node->h_next ) - node = node->h_next; - } - } - } - - treeIterator->node = node; - treeIterator->level = level; - - __END__; - - return prevNode; -} - -/* End of file. */