+++ /dev/null
-/*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 <delta_elems> 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 <delta_elements> 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 <count> 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 <first>, 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. */
projects / opencv / blobdiff