1 /*M///////////////////////////////////////////////////////////////////////////////////////
2 //
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
4 //
5 // By downloading, copying, installing or using the software you agree to this license.
6 // If you do not agree to this license, do not download, install,
7 // copy or use the software.
8 //
9 //
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
12 //
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
15 //
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
18 //
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
21 //
22 // * Redistribution's in binary form must reproduce the above copyright notice,
23 // this list of conditions and the following disclaimer in the documentation
24 // and/or other materials provided with the distribution.
25 //
26 // * The name of Intel Corporation may not be used to endorse or promote products
27 // derived from this software without specific prior written permission.
28 //
29 // This software is provided by the copyright holders and contributors "as is" and
30 // any express or implied warranties, including, but not limited to, the implied
31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
32 // In no event shall the Intel Corporation or contributors be liable for any direct,
33 // indirect, incidental, special, exemplary, or consequential damages
34 // (including, but not limited to, procurement of substitute goods or services;
35 // loss of use, data, or profits; or business interruption) however caused
36 // and on any theory of liability, whether in contract, strict liability,
37 // or tort (including negligence or otherwise) arising in any way out of
38 // the use of this software, even if advised of the possibility of such damage.
39 //
40 //M*/
41 #include "precomp.hpp"
42
43 #ifndef OPENCV_EXCLUDE_C_API
44
45 /* default alignment for dynamic data strucutures, resided in storages. */
46 #define CV_STRUCT_ALIGN ((int)sizeof(double))
47
48 /* default storage block size */
49 #define CV_STORAGE_BLOCK_SIZE ((1<<16) - 128)
50
51 #define ICV_FREE_PTR(storage) \
52 ((schar*)(storage)->top + (storage)->block_size - (storage)->free_space)
53
54 #define ICV_ALIGNED_SEQ_BLOCK_SIZE \
55 (int)cvAlign(sizeof(CvSeqBlock), CV_STRUCT_ALIGN)
56
57 CV_INLINE int
cvAlignLeft(int size,int align)58 cvAlignLeft( int size, int align )
59 {
60 return size & -align;
61 }
62
63 #define CV_GET_LAST_ELEM( seq, block ) \
64 ((block)->data + ((block)->count - 1)*((seq)->elem_size))
65
66 #define CV_SWAP_ELEMS(a,b,elem_size) \
67 { \
68 int k; \
69 for( k = 0; k < elem_size; k++ ) \
70 { \
71 char t0 = (a)[k]; \
72 char t1 = (b)[k]; \
73 (a)[k] = t1; \
74 (b)[k] = t0; \
75 } \
76 }
77
78 #define ICV_SHIFT_TAB_MAX 32
79 static const schar icvPower2ShiftTab[] =
80 {
81 0, 1, -1, 2, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, 4,
82 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 5
83 };
84
85 /****************************************************************************************\
86 * Functions for manipulating memory storage - list of memory blocks *
87 \****************************************************************************************/
88
89 /* Initialize allocated storage: */
90 static void
icvInitMemStorage(CvMemStorage * storage,int block_size)91 icvInitMemStorage( CvMemStorage* storage, int block_size )
92 {
93 if( !storage )
94 CV_Error( CV_StsNullPtr, "" );
95
96 if( block_size <= 0 )
97 block_size = CV_STORAGE_BLOCK_SIZE;
98
99 block_size = cvAlign( block_size, CV_STRUCT_ALIGN );
100 assert( sizeof(CvMemBlock) % CV_STRUCT_ALIGN == 0 );
101
102 memset( storage, 0, sizeof( *storage ));
103 storage->signature = CV_STORAGE_MAGIC_VAL;
104 storage->block_size = block_size;
105 }
106
107
108 /* Create root memory storage: */
109 CV_IMPL CvMemStorage*
cvCreateMemStorage(int block_size)110 cvCreateMemStorage( int block_size )
111 {
112 CvMemStorage* storage = (CvMemStorage *)cvAlloc( sizeof( CvMemStorage ));
113 icvInitMemStorage( storage, block_size );
114 return storage;
115 }
116
117
118 /* Create child memory storage: */
119 CV_IMPL CvMemStorage *
cvCreateChildMemStorage(CvMemStorage * parent)120 cvCreateChildMemStorage( CvMemStorage * parent )
121 {
122 if( !parent )
123 CV_Error( CV_StsNullPtr, "" );
124
125 CvMemStorage* storage = cvCreateMemStorage(parent->block_size);
126 storage->parent = parent;
127
128 return storage;
129 }
130
131
132 /* Release all blocks of the storage (or return them to parent, if any): */
133 static void
icvDestroyMemStorage(CvMemStorage * storage)134 icvDestroyMemStorage( CvMemStorage* storage )
135 {
136 int k = 0;
137
138 CvMemBlock *block;
139 CvMemBlock *dst_top = 0;
140
141 if( !storage )
142 CV_Error( CV_StsNullPtr, "" );
143
144 if( storage->parent )
145 dst_top = storage->parent->top;
146
147 for( block = storage->bottom; block != 0; k++ )
148 {
149 CvMemBlock *temp = block;
150
151 block = block->next;
152 if( storage->parent )
153 {
154 if( dst_top )
155 {
156 temp->prev = dst_top;
157 temp->next = dst_top->next;
158 if( temp->next )
159 temp->next->prev = temp;
160 dst_top = dst_top->next = temp;
161 }
162 else
163 {
164 dst_top = storage->parent->bottom = storage->parent->top = temp;
165 temp->prev = temp->next = 0;
166 storage->free_space = storage->block_size - sizeof( *temp );
167 }
168 }
169 else
170 {
171 cvFree( &temp );
172 }
173 }
174
175 storage->top = storage->bottom = 0;
176 storage->free_space = 0;
177 }
178
179
180 /* Release memory storage: */
181 CV_IMPL void
cvReleaseMemStorage(CvMemStorage ** storage)182 cvReleaseMemStorage( CvMemStorage** storage )
183 {
184 if( !storage )
185 CV_Error( CV_StsNullPtr, "" );
186
187 CvMemStorage* st = *storage;
188 *storage = 0;
189 if( st )
190 {
191 icvDestroyMemStorage( st );
192 cvFree( &st );
193 }
194 }
195
196
197 /* Clears memory storage (return blocks to the parent, if any): */
198 CV_IMPL void
cvClearMemStorage(CvMemStorage * storage)199 cvClearMemStorage( CvMemStorage * storage )
200 {
201 if( !storage )
202 CV_Error( CV_StsNullPtr, "" );
203
204 if( storage->parent )
205 icvDestroyMemStorage( storage );
206 else
207 {
208 storage->top = storage->bottom;
209 storage->free_space = storage->bottom ? storage->block_size - sizeof(CvMemBlock) : 0;
210 }
211 }
212
213
214 /* Moves stack pointer to next block.
215 If no blocks, allocate new one and link it to the storage: */
216 static void
icvGoNextMemBlock(CvMemStorage * storage)217 icvGoNextMemBlock( CvMemStorage * storage )
218 {
219 if( !storage )
220 CV_Error( CV_StsNullPtr, "" );
221
222 if( !storage->top || !storage->top->next )
223 {
224 CvMemBlock *block;
225
226 if( !(storage->parent) )
227 {
228 block = (CvMemBlock *)cvAlloc( storage->block_size );
229 }
230 else
231 {
232 CvMemStorage *parent = storage->parent;
233 CvMemStoragePos parent_pos;
234
235 cvSaveMemStoragePos( parent, &parent_pos );
236 icvGoNextMemBlock( parent );
237
238 block = parent->top;
239 cvRestoreMemStoragePos( parent, &parent_pos );
240
241 if( block == parent->top ) /* the single allocated block */
242 {
243 assert( parent->bottom == block );
244 parent->top = parent->bottom = 0;
245 parent->free_space = 0;
246 }
247 else
248 {
249 /* cut the block from the parent's list of blocks */
250 parent->top->next = block->next;
251 if( block->next )
252 block->next->prev = parent->top;
253 }
254 }
255
256 /* link block */
257 block->next = 0;
258 block->prev = storage->top;
259
260 if( storage->top )
261 storage->top->next = block;
262 else
263 storage->top = storage->bottom = block;
264 }
265
266 if( storage->top->next )
267 storage->top = storage->top->next;
268 storage->free_space = storage->block_size - sizeof(CvMemBlock);
269 assert( storage->free_space % CV_STRUCT_ALIGN == 0 );
270 }
271
272
273 /* Remember memory storage position: */
274 CV_IMPL void
cvSaveMemStoragePos(const CvMemStorage * storage,CvMemStoragePos * pos)275 cvSaveMemStoragePos( const CvMemStorage * storage, CvMemStoragePos * pos )
276 {
277 if( !storage || !pos )
278 CV_Error( CV_StsNullPtr, "" );
279
280 pos->top = storage->top;
281 pos->free_space = storage->free_space;
282 }
283
284
285 /* Restore memory storage position: */
286 CV_IMPL void
cvRestoreMemStoragePos(CvMemStorage * storage,CvMemStoragePos * pos)287 cvRestoreMemStoragePos( CvMemStorage * storage, CvMemStoragePos * pos )
288 {
289 if( !storage || !pos )
290 CV_Error( CV_StsNullPtr, "" );
291 if( pos->free_space > storage->block_size )
292 CV_Error( CV_StsBadSize, "" );
293
294 /*
295 // this breaks icvGoNextMemBlock, so comment it off for now
296 if( storage->parent && (!pos->top || pos->top->next) )
297 {
298 CvMemBlock* save_bottom;
299 if( !pos->top )
300 save_bottom = 0;
301 else
302 {
303 save_bottom = storage->bottom;
304 storage->bottom = pos->top->next;
305 pos->top->next = 0;
306 storage->bottom->prev = 0;
307 }
308 icvDestroyMemStorage( storage );
309 storage->bottom = save_bottom;
310 }*/
311
312 storage->top = pos->top;
313 storage->free_space = pos->free_space;
314
315 if( !storage->top )
316 {
317 storage->top = storage->bottom;
318 storage->free_space = storage->top ? storage->block_size - sizeof(CvMemBlock) : 0;
319 }
320 }
321
322
323 /* Allocate continuous buffer of the specified size in the storage: */
324 CV_IMPL void*
cvMemStorageAlloc(CvMemStorage * storage,size_t size)325 cvMemStorageAlloc( CvMemStorage* storage, size_t size )
326 {
327 schar *ptr = 0;
328 if( !storage )
329 CV_Error( CV_StsNullPtr, "NULL storage pointer" );
330
331 if( size > INT_MAX )
332 CV_Error( CV_StsOutOfRange, "Too large memory block is requested" );
333
334 assert( storage->free_space % CV_STRUCT_ALIGN == 0 );
335
336 if( (size_t)storage->free_space < size )
337 {
338 size_t max_free_space = cvAlignLeft(storage->block_size - sizeof(CvMemBlock), CV_STRUCT_ALIGN);
339 if( max_free_space < size )
340 CV_Error( CV_StsOutOfRange, "requested size is negative or too big" );
341
342 icvGoNextMemBlock( storage );
343 }
344
345 ptr = ICV_FREE_PTR(storage);
346 assert( (size_t)ptr % CV_STRUCT_ALIGN == 0 );
347 storage->free_space = cvAlignLeft(storage->free_space - (int)size, CV_STRUCT_ALIGN );
348
349 return ptr;
350 }
351
352
353 /*CV_IMPL CvString
354 cvMemStorageAllocString( CvMemStorage* storage, const char* ptr, int len )
355 {
356 CvString str;
357 memset(&str, 0, sizeof(CvString));
358
359 str.len = len >= 0 ? len : (int)strlen(ptr);
360 str.ptr = (char*)cvMemStorageAlloc( storage, str.len + 1 );
361 memcpy( str.ptr, ptr, str.len );
362 str.ptr[str.len] = '\0';
363
364 return str;
365 }*/
366
367
368 /****************************************************************************************\
369 * Sequence implementation *
370 \****************************************************************************************/
371
372 /* Create empty sequence: */
373 CV_IMPL CvSeq *
cvCreateSeq(int seq_flags,size_t header_size,size_t elem_size,CvMemStorage * storage)374 cvCreateSeq( int seq_flags, size_t header_size, size_t elem_size, CvMemStorage* storage )
375 {
376 CvSeq *seq = 0;
377
378 if( !storage )
379 CV_Error( CV_StsNullPtr, "" );
380 if( header_size < sizeof( CvSeq ) || elem_size <= 0 )
381 CV_Error( CV_StsBadSize, "" );
382
383 /* allocate sequence header */
384 seq = (CvSeq*)cvMemStorageAlloc( storage, header_size );
385 memset( seq, 0, header_size );
386
387 seq->header_size = (int)header_size;
388 seq->flags = (seq_flags & ~CV_MAGIC_MASK) | CV_SEQ_MAGIC_VAL;
389 {
390 int elemtype = CV_MAT_TYPE(seq_flags);
391 int typesize = CV_ELEM_SIZE(elemtype);
392
393 if( elemtype != CV_SEQ_ELTYPE_GENERIC && elemtype != CV_SEQ_ELTYPE_PTR &&
394 typesize != 0 && typesize != (int)elem_size )
395 CV_Error( CV_StsBadSize,
396 "Specified element size doesn't match to the size of the specified element type "
397 "(try to use 0 for element type)" );
398 }
399 seq->elem_size = (int)elem_size;
400 seq->storage = storage;
401
402 cvSetSeqBlockSize( seq, (int)((1 << 10)/elem_size) );
403
404 return seq;
405 }
406
407
408 /* adjusts <delta_elems> field of sequence. It determines how much the sequence
409 grows if there are no free space inside the sequence buffers */
410 CV_IMPL void
cvSetSeqBlockSize(CvSeq * seq,int delta_elements)411 cvSetSeqBlockSize( CvSeq *seq, int delta_elements )
412 {
413 int elem_size;
414 int useful_block_size;
415
416 if( !seq || !seq->storage )
417 CV_Error( CV_StsNullPtr, "" );
418 if( delta_elements < 0 )
419 CV_Error( CV_StsOutOfRange, "" );
420
421 useful_block_size = cvAlignLeft(seq->storage->block_size - sizeof(CvMemBlock) -
422 sizeof(CvSeqBlock), CV_STRUCT_ALIGN);
423 elem_size = seq->elem_size;
424
425 if( delta_elements == 0 )
426 {
427 delta_elements = (1 << 10) / elem_size;
428 delta_elements = MAX( delta_elements, 1 );
429 }
430 if( delta_elements * elem_size > useful_block_size )
431 {
432 delta_elements = useful_block_size / elem_size;
433 if( delta_elements == 0 )
434 CV_Error( CV_StsOutOfRange, "Storage block size is too small "
435 "to fit the sequence elements" );
436 }
437
438 seq->delta_elems = delta_elements;
439 }
440
441
442 /* Find a sequence element by its index: */
443 CV_IMPL schar*
cvGetSeqElem(const CvSeq * seq,int index)444 cvGetSeqElem( const CvSeq *seq, int index )
445 {
446 CvSeqBlock *block;
447 int count, total = seq->total;
448
449 if( (unsigned)index >= (unsigned)total )
450 {
451 index += index < 0 ? total : 0;
452 index -= index >= total ? total : 0;
453 if( (unsigned)index >= (unsigned)total )
454 return 0;
455 }
456
457 block = seq->first;
458 if( index + index <= total )
459 {
460 while( index >= (count = block->count) )
461 {
462 block = block->next;
463 index -= count;
464 }
465 }
466 else
467 {
468 do
469 {
470 block = block->prev;
471 total -= block->count;
472 }
473 while( index < total );
474 index -= total;
475 }
476
477 return block->data + index * seq->elem_size;
478 }
479
480
481 /* Calculate index of a sequence element: */
482 CV_IMPL int
cvSeqElemIdx(const CvSeq * seq,const void * _element,CvSeqBlock ** _block)483 cvSeqElemIdx( const CvSeq* seq, const void* _element, CvSeqBlock** _block )
484 {
485 const schar *element = (const schar *)_element;
486 int elem_size;
487 int id = -1;
488 CvSeqBlock *first_block;
489 CvSeqBlock *block;
490
491 if( !seq || !element )
492 CV_Error( CV_StsNullPtr, "" );
493
494 block = first_block = seq->first;
495 elem_size = seq->elem_size;
496
497 for( ;; )
498 {
499 if( (unsigned)(element - block->data) < (unsigned) (block->count * elem_size) )
500 {
501 if( _block )
502 *_block = block;
503 if( elem_size <= ICV_SHIFT_TAB_MAX && (id = icvPower2ShiftTab[elem_size - 1]) >= 0 )
504 id = (int)((size_t)(element - block->data) >> id);
505 else
506 id = (int)((size_t)(element - block->data) / elem_size);
507 id += block->start_index - seq->first->start_index;
508 break;
509 }
510 block = block->next;
511 if( block == first_block )
512 break;
513 }
514
515 return id;
516 }
517
518
519 CV_IMPL int
cvSliceLength(CvSlice slice,const CvSeq * seq)520 cvSliceLength( CvSlice slice, const CvSeq* seq )
521 {
522 int total = seq->total;
523 int length = slice.end_index - slice.start_index;
524
525 if( length != 0 )
526 {
527 if( slice.start_index < 0 )
528 slice.start_index += total;
529 if( slice.end_index <= 0 )
530 slice.end_index += total;
531
532 length = slice.end_index - slice.start_index;
533 }
534
535 while( length < 0 )
536 length += total;
537 if( length > total )
538 length = total;
539
540 return length;
541 }
542
543
544 /* Copy all sequence elements into single continuous array: */
545 CV_IMPL void*
cvCvtSeqToArray(const CvSeq * seq,void * array,CvSlice slice)546 cvCvtSeqToArray( const CvSeq *seq, void *array, CvSlice slice )
547 {
548 int elem_size, total;
549 CvSeqReader reader;
550 char *dst = (char*)array;
551
552 if( !seq || !array )
553 CV_Error( CV_StsNullPtr, "" );
554
555 elem_size = seq->elem_size;
556 total = cvSliceLength( slice, seq )*elem_size;
557
558 if( total == 0 )
559 return 0;
560
561 cvStartReadSeq( seq, &reader, 0 );
562 cvSetSeqReaderPos( &reader, slice.start_index, 0 );
563
564 do
565 {
566 int count = (int)(reader.block_max - reader.ptr);
567 if( count > total )
568 count = total;
569
570 memcpy( dst, reader.ptr, count );
571 dst += count;
572 reader.block = reader.block->next;
573 reader.ptr = reader.block->data;
574 reader.block_max = reader.ptr + reader.block->count*elem_size;
575 total -= count;
576 }
577 while( total > 0 );
578
579 return array;
580 }
581
582
583 /* Construct a sequence from an array without copying any data.
584 NB: The resultant sequence cannot grow beyond its initial size: */
585 CV_IMPL CvSeq*
cvMakeSeqHeaderForArray(int seq_flags,int header_size,int elem_size,void * array,int total,CvSeq * seq,CvSeqBlock * block)586 cvMakeSeqHeaderForArray( int seq_flags, int header_size, int elem_size,
587 void *array, int total, CvSeq *seq, CvSeqBlock * block )
588 {
589 CvSeq* result = 0;
590
591 if( elem_size <= 0 || header_size < (int)sizeof( CvSeq ) || total < 0 )
592 CV_Error( CV_StsBadSize, "" );
593
594 if( !seq || ((!array || !block) && total > 0) )
595 CV_Error( CV_StsNullPtr, "" );
596
597 memset( seq, 0, header_size );
598
599 seq->header_size = header_size;
600 seq->flags = (seq_flags & ~CV_MAGIC_MASK) | CV_SEQ_MAGIC_VAL;
601 {
602 int elemtype = CV_MAT_TYPE(seq_flags);
603 int typesize = CV_ELEM_SIZE(elemtype);
604
605 if( elemtype != CV_SEQ_ELTYPE_GENERIC &&
606 typesize != 0 && typesize != elem_size )
607 CV_Error( CV_StsBadSize,
608 "Element size doesn't match to the size of predefined element type "
609 "(try to use 0 for sequence element type)" );
610 }
611 seq->elem_size = elem_size;
612 seq->total = total;
613 seq->block_max = seq->ptr = (schar *) array + total * elem_size;
614
615 if( total > 0 )
616 {
617 seq->first = block;
618 block->prev = block->next = block;
619 block->start_index = 0;
620 block->count = total;
621 block->data = (schar *) array;
622 }
623
624 result = seq;
625
626 return result;
627 }
628
629
630 /* The function allocates space for at least one more sequence element.
631 If there are free sequence blocks (seq->free_blocks != 0)
632 they are reused, otherwise the space is allocated in the storage: */
633 static void
icvGrowSeq(CvSeq * seq,int in_front_of)634 icvGrowSeq( CvSeq *seq, int in_front_of )
635 {
636 CvSeqBlock *block;
637
638 if( !seq )
639 CV_Error( CV_StsNullPtr, "" );
640 block = seq->free_blocks;
641
642 if( !block )
643 {
644 int elem_size = seq->elem_size;
645 int delta_elems = seq->delta_elems;
646 CvMemStorage *storage = seq->storage;
647
648 if( seq->total >= delta_elems*4 )
649 cvSetSeqBlockSize( seq, delta_elems*2 );
650
651 if( !storage )
652 CV_Error( CV_StsNullPtr, "The sequence has NULL storage pointer" );
653
654 /* If there is a free space just after last allocated block
655 and it is big enough then enlarge the last block.
656 This can happen only if the new block is added to the end of sequence: */
657 if( (size_t)(ICV_FREE_PTR(storage) - seq->block_max) < CV_STRUCT_ALIGN &&
658 storage->free_space >= seq->elem_size && !in_front_of )
659 {
660 int delta = storage->free_space / elem_size;
661
662 delta = MIN( delta, delta_elems ) * elem_size;
663 seq->block_max += delta;
664 storage->free_space = cvAlignLeft((int)(((schar*)storage->top + storage->block_size) -
665 seq->block_max), CV_STRUCT_ALIGN );
666 return;
667 }
668 else
669 {
670 int delta = elem_size * delta_elems + ICV_ALIGNED_SEQ_BLOCK_SIZE;
671
672 /* Try to allocate <delta_elements> elements: */
673 if( storage->free_space < delta )
674 {
675 int small_block_size = MAX(1, delta_elems/3)*elem_size +
676 ICV_ALIGNED_SEQ_BLOCK_SIZE;
677 /* try to allocate smaller part */
678 if( storage->free_space >= small_block_size + CV_STRUCT_ALIGN )
679 {
680 delta = (storage->free_space - ICV_ALIGNED_SEQ_BLOCK_SIZE)/seq->elem_size;
681 delta = delta*seq->elem_size + ICV_ALIGNED_SEQ_BLOCK_SIZE;
682 }
683 else
684 {
685 icvGoNextMemBlock( storage );
686 assert( storage->free_space >= delta );
687 }
688 }
689
690 block = (CvSeqBlock*)cvMemStorageAlloc( storage, delta );
691 block->data = (schar*)cvAlignPtr( block + 1, CV_STRUCT_ALIGN );
692 block->count = delta - ICV_ALIGNED_SEQ_BLOCK_SIZE;
693 block->prev = block->next = 0;
694 }
695 }
696 else
697 {
698 seq->free_blocks = block->next;
699 }
700
701 if( !(seq->first) )
702 {
703 seq->first = block;
704 block->prev = block->next = block;
705 }
706 else
707 {
708 block->prev = seq->first->prev;
709 block->next = seq->first;
710 block->prev->next = block->next->prev = block;
711 }
712
713 /* For free blocks the <count> field means
714 * total number of bytes in the block.
715 *
716 * For used blocks it means current number
717 * of sequence elements in the block:
718 */
719 assert( block->count % seq->elem_size == 0 && block->count > 0 );
720
721 if( !in_front_of )
722 {
723 seq->ptr = block->data;
724 seq->block_max = block->data + block->count;
725 block->start_index = block == block->prev ? 0 :
726 block->prev->start_index + block->prev->count;
727 }
728 else
729 {
730 int delta = block->count / seq->elem_size;
731 block->data += block->count;
732
733 if( block != block->prev )
734 {
735 assert( seq->first->start_index == 0 );
736 seq->first = block;
737 }
738 else
739 {
740 seq->block_max = seq->ptr = block->data;
741 }
742
743 block->start_index = 0;
744
745 for( ;; )
746 {
747 block->start_index += delta;
748 block = block->next;
749 if( block == seq->first )
750 break;
751 }
752 }
753
754 block->count = 0;
755 }
756
757 /* Recycle a sequence block: */
758 static void
icvFreeSeqBlock(CvSeq * seq,int in_front_of)759 icvFreeSeqBlock( CvSeq *seq, int in_front_of )
760 {
761 CvSeqBlock *block = seq->first;
762
763 assert( (in_front_of ? block : block->prev)->count == 0 );
764
765 if( block == block->prev ) /* single block case */
766 {
767 block->count = (int)(seq->block_max - block->data) + block->start_index * seq->elem_size;
768 block->data = seq->block_max - block->count;
769 seq->first = 0;
770 seq->ptr = seq->block_max = 0;
771 seq->total = 0;
772 }
773 else
774 {
775 if( !in_front_of )
776 {
777 block = block->prev;
778 assert( seq->ptr == block->data );
779
780 block->count = (int)(seq->block_max - seq->ptr);
781 seq->block_max = seq->ptr = block->prev->data +
782 block->prev->count * seq->elem_size;
783 }
784 else
785 {
786 int delta = block->start_index;
787
788 block->count = delta * seq->elem_size;
789 block->data -= block->count;
790
791 /* Update start indices of sequence blocks: */
792 for( ;; )
793 {
794 block->start_index -= delta;
795 block = block->next;
796 if( block == seq->first )
797 break;
798 }
799
800 seq->first = block->next;
801 }
802
803 block->prev->next = block->next;
804 block->next->prev = block->prev;
805 }
806
807 assert( block->count > 0 && block->count % seq->elem_size == 0 );
808 block->next = seq->free_blocks;
809 seq->free_blocks = block;
810 }
811
812
813 /****************************************************************************************\
814 * Sequence Writer implementation *
815 \****************************************************************************************/
816
817 /* Initialize sequence writer: */
818 CV_IMPL void
cvStartAppendToSeq(CvSeq * seq,CvSeqWriter * writer)819 cvStartAppendToSeq( CvSeq *seq, CvSeqWriter * writer )
820 {
821 if( !seq || !writer )
822 CV_Error( CV_StsNullPtr, "" );
823
824 memset( writer, 0, sizeof( *writer ));
825 writer->header_size = sizeof( CvSeqWriter );
826
827 writer->seq = seq;
828 writer->block = seq->first ? seq->first->prev : 0;
829 writer->ptr = seq->ptr;
830 writer->block_max = seq->block_max;
831 }
832
833
834 /* Initialize sequence writer: */
835 CV_IMPL void
cvStartWriteSeq(int seq_flags,int header_size,int elem_size,CvMemStorage * storage,CvSeqWriter * writer)836 cvStartWriteSeq( int seq_flags, int header_size,
837 int elem_size, CvMemStorage * storage, CvSeqWriter * writer )
838 {
839 if( !storage || !writer )
840 CV_Error( CV_StsNullPtr, "" );
841
842 CvSeq* seq = cvCreateSeq( seq_flags, header_size, elem_size, storage );
843 cvStartAppendToSeq( seq, writer );
844 }
845
846
847 /* Update sequence header: */
848 CV_IMPL void
cvFlushSeqWriter(CvSeqWriter * writer)849 cvFlushSeqWriter( CvSeqWriter * writer )
850 {
851 if( !writer )
852 CV_Error( CV_StsNullPtr, "" );
853
854 CvSeq* seq = writer->seq;
855 seq->ptr = writer->ptr;
856
857 if( writer->block )
858 {
859 int total = 0;
860 CvSeqBlock *first_block = writer->seq->first;
861 CvSeqBlock *block = first_block;
862
863 writer->block->count = (int)((writer->ptr - writer->block->data) / seq->elem_size);
864 assert( writer->block->count > 0 );
865
866 do
867 {
868 total += block->count;
869 block = block->next;
870 }
871 while( block != first_block );
872
873 writer->seq->total = total;
874 }
875 }
876
877
878 /* Calls icvFlushSeqWriter and finishes writing process: */
879 CV_IMPL CvSeq *
cvEndWriteSeq(CvSeqWriter * writer)880 cvEndWriteSeq( CvSeqWriter * writer )
881 {
882 if( !writer )
883 CV_Error( CV_StsNullPtr, "" );
884
885 cvFlushSeqWriter( writer );
886 CvSeq* seq = writer->seq;
887
888 /* Truncate the last block: */
889 if( writer->block && writer->seq->storage )
890 {
891 CvMemStorage *storage = seq->storage;
892 schar *storage_block_max = (schar *) storage->top + storage->block_size;
893
894 assert( writer->block->count > 0 );
895
896 if( (unsigned)((storage_block_max - storage->free_space)
897 - seq->block_max) < CV_STRUCT_ALIGN )
898 {
899 storage->free_space = cvAlignLeft((int)(storage_block_max - seq->ptr), CV_STRUCT_ALIGN);
900 seq->block_max = seq->ptr;
901 }
902 }
903
904 writer->ptr = 0;
905 return seq;
906 }
907
908
909 /* Create new sequence block: */
910 CV_IMPL void
cvCreateSeqBlock(CvSeqWriter * writer)911 cvCreateSeqBlock( CvSeqWriter * writer )
912 {
913 if( !writer || !writer->seq )
914 CV_Error( CV_StsNullPtr, "" );
915
916 CvSeq* seq = writer->seq;
917
918 cvFlushSeqWriter( writer );
919
920 icvGrowSeq( seq, 0 );
921
922 writer->block = seq->first->prev;
923 writer->ptr = seq->ptr;
924 writer->block_max = seq->block_max;
925 }
926
927
928 /****************************************************************************************\
929 * Sequence Reader implementation *
930 \****************************************************************************************/
931
932 /* Initialize sequence reader: */
933 CV_IMPL void
cvStartReadSeq(const CvSeq * seq,CvSeqReader * reader,int reverse)934 cvStartReadSeq( const CvSeq *seq, CvSeqReader * reader, int reverse )
935 {
936 CvSeqBlock *first_block;
937 CvSeqBlock *last_block;
938
939 if( reader )
940 {
941 reader->seq = 0;
942 reader->block = 0;
943 reader->ptr = reader->block_max = reader->block_min = 0;
944 }
945
946 if( !seq || !reader )
947 CV_Error( CV_StsNullPtr, "" );
948
949 reader->header_size = sizeof( CvSeqReader );
950 reader->seq = (CvSeq*)seq;
951
952 first_block = seq->first;
953
954 if( first_block )
955 {
956 last_block = first_block->prev;
957 reader->ptr = first_block->data;
958 reader->prev_elem = CV_GET_LAST_ELEM( seq, last_block );
959 reader->delta_index = seq->first->start_index;
960
961 if( reverse )
962 {
963 schar *temp = reader->ptr;
964
965 reader->ptr = reader->prev_elem;
966 reader->prev_elem = temp;
967
968 reader->block = last_block;
969 }
970 else
971 {
972 reader->block = first_block;
973 }
974
975 reader->block_min = reader->block->data;
976 reader->block_max = reader->block_min + reader->block->count * seq->elem_size;
977 }
978 else
979 {
980 reader->delta_index = 0;
981 reader->block = 0;
982
983 reader->ptr = reader->prev_elem = reader->block_min = reader->block_max = 0;
984 }
985 }
986
987
988 /* Change the current reading block
989 * to the previous or to the next:
990 */
991 CV_IMPL void
cvChangeSeqBlock(void * _reader,int direction)992 cvChangeSeqBlock( void* _reader, int direction )
993 {
994 CvSeqReader* reader = (CvSeqReader*)_reader;
995
996 if( !reader )
997 CV_Error( CV_StsNullPtr, "" );
998
999 if( direction > 0 )
1000 {
1001 reader->block = reader->block->next;
1002 reader->ptr = reader->block->data;
1003 }
1004 else
1005 {
1006 reader->block = reader->block->prev;
1007 reader->ptr = CV_GET_LAST_ELEM( reader->seq, reader->block );
1008 }
1009 reader->block_min = reader->block->data;
1010 reader->block_max = reader->block_min + reader->block->count * reader->seq->elem_size;
1011 }
1012
1013
1014 /* Return the current reader position: */
1015 CV_IMPL int
cvGetSeqReaderPos(CvSeqReader * reader)1016 cvGetSeqReaderPos( CvSeqReader* reader )
1017 {
1018 int elem_size;
1019 int index = -1;
1020
1021 if( !reader || !reader->ptr )
1022 CV_Error( CV_StsNullPtr, "" );
1023
1024 elem_size = reader->seq->elem_size;
1025 if( elem_size <= ICV_SHIFT_TAB_MAX && (index = icvPower2ShiftTab[elem_size - 1]) >= 0 )
1026 index = (int)((reader->ptr - reader->block_min) >> index);
1027 else
1028 index = (int)((reader->ptr - reader->block_min) / elem_size);
1029
1030 index += reader->block->start_index - reader->delta_index;
1031
1032 return index;
1033 }
1034
1035
1036 /* Set reader position to given position,
1037 * either absolute or relative to the
1038 * current one:
1039 */
1040 CV_IMPL void
cvSetSeqReaderPos(CvSeqReader * reader,int index,int is_relative)1041 cvSetSeqReaderPos( CvSeqReader* reader, int index, int is_relative )
1042 {
1043 CvSeqBlock *block;
1044 int elem_size, count, total;
1045
1046 if( !reader || !reader->seq )
1047 CV_Error( CV_StsNullPtr, "" );
1048
1049 total = reader->seq->total;
1050 elem_size = reader->seq->elem_size;
1051
1052 if( !is_relative )
1053 {
1054 if( index < 0 )
1055 {
1056 if( index < -total )
1057 CV_Error( CV_StsOutOfRange, "" );
1058 index += total;
1059 }
1060 else if( index >= total )
1061 {
1062 index -= total;
1063 if( index >= total )
1064 CV_Error( CV_StsOutOfRange, "" );
1065 }
1066
1067 block = reader->seq->first;
1068 if( index >= (count = block->count) )
1069 {
1070 if( index + index <= total )
1071 {
1072 do
1073 {
1074 block = block->next;
1075 index -= count;
1076 }
1077 while( index >= (count = block->count) );
1078 }
1079 else
1080 {
1081 do
1082 {
1083 block = block->prev;
1084 total -= block->count;
1085 }
1086 while( index < total );
1087 index -= total;
1088 }
1089 }
1090 reader->ptr = block->data + index * elem_size;
1091 if( reader->block != block )
1092 {
1093 reader->block = block;
1094 reader->block_min = block->data;
1095 reader->block_max = block->data + block->count * elem_size;
1096 }
1097 }
1098 else
1099 {
1100 schar* ptr = reader->ptr;
1101 index *= elem_size;
1102 block = reader->block;
1103
1104 if( index > 0 )
1105 {
1106 while( ptr + index >= reader->block_max )
1107 {
1108 int delta = (int)(reader->block_max - ptr);
1109 index -= delta;
1110 reader->block = block = block->next;
1111 reader->block_min = ptr = block->data;
1112 reader->block_max = block->data + block->count*elem_size;
1113 }
1114 reader->ptr = ptr + index;
1115 }
1116 else
1117 {
1118 while( ptr + index < reader->block_min )
1119 {
1120 int delta = (int)(ptr - reader->block_min);
1121 index += delta;
1122 reader->block = block = block->prev;
1123 reader->block_min = block->data;
1124 reader->block_max = ptr = block->data + block->count*elem_size;
1125 }
1126 reader->ptr = ptr + index;
1127 }
1128 }
1129 }
1130
1131
1132 /* Push element onto the sequence: */
1133 CV_IMPL schar*
cvSeqPush(CvSeq * seq,const void * element)1134 cvSeqPush( CvSeq *seq, const void *element )
1135 {
1136 schar *ptr = 0;
1137 size_t elem_size;
1138
1139 if( !seq )
1140 CV_Error( CV_StsNullPtr, "" );
1141
1142 elem_size = seq->elem_size;
1143 ptr = seq->ptr;
1144
1145 if( ptr >= seq->block_max )
1146 {
1147 icvGrowSeq( seq, 0 );
1148
1149 ptr = seq->ptr;
1150 assert( ptr + elem_size <= seq->block_max /*&& ptr == seq->block_min */ );
1151 }
1152
1153 if( element )
1154 memcpy( ptr, element, elem_size );
1155 seq->first->prev->count++;
1156 seq->total++;
1157 seq->ptr = ptr + elem_size;
1158
1159 return ptr;
1160 }
1161
1162
1163 /* Pop last element off of the sequence: */
1164 CV_IMPL void
cvSeqPop(CvSeq * seq,void * element)1165 cvSeqPop( CvSeq *seq, void *element )
1166 {
1167 schar *ptr;
1168 int elem_size;
1169
1170 if( !seq )
1171 CV_Error( CV_StsNullPtr, "" );
1172 if( seq->total <= 0 )
1173 CV_Error( CV_StsBadSize, "" );
1174
1175 elem_size = seq->elem_size;
1176 seq->ptr = ptr = seq->ptr - elem_size;
1177
1178 if( element )
1179 memcpy( element, ptr, elem_size );
1180 seq->ptr = ptr;
1181 seq->total--;
1182
1183 if( --(seq->first->prev->count) == 0 )
1184 {
1185 icvFreeSeqBlock( seq, 0 );
1186 assert( seq->ptr == seq->block_max );
1187 }
1188 }
1189
1190
1191 /* Push element onto the front of the sequence: */
1192 CV_IMPL schar*
cvSeqPushFront(CvSeq * seq,const void * element)1193 cvSeqPushFront( CvSeq *seq, const void *element )
1194 {
1195 schar* ptr = 0;
1196 int elem_size;
1197 CvSeqBlock *block;
1198
1199 if( !seq )
1200 CV_Error( CV_StsNullPtr, "" );
1201
1202 elem_size = seq->elem_size;
1203 block = seq->first;
1204
1205 if( !block || block->start_index == 0 )
1206 {
1207 icvGrowSeq( seq, 1 );
1208
1209 block = seq->first;
1210 assert( block->start_index > 0 );
1211 }
1212
1213 ptr = block->data -= elem_size;
1214
1215 if( element )
1216 memcpy( ptr, element, elem_size );
1217 block->count++;
1218 block->start_index--;
1219 seq->total++;
1220
1221 return ptr;
1222 }
1223
1224
1225 /* Shift out first element of the sequence: */
1226 CV_IMPL void
cvSeqPopFront(CvSeq * seq,void * element)1227 cvSeqPopFront( CvSeq *seq, void *element )
1228 {
1229 int elem_size;
1230 CvSeqBlock *block;
1231
1232 if( !seq )
1233 CV_Error( CV_StsNullPtr, "" );
1234 if( seq->total <= 0 )
1235 CV_Error( CV_StsBadSize, "" );
1236
1237 elem_size = seq->elem_size;
1238 block = seq->first;
1239
1240 if( element )
1241 memcpy( element, block->data, elem_size );
1242 block->data += elem_size;
1243 block->start_index++;
1244 seq->total--;
1245
1246 if( --(block->count) == 0 )
1247 icvFreeSeqBlock( seq, 1 );
1248 }
1249
1250 /* Insert new element in middle of sequence: */
1251 CV_IMPL schar*
cvSeqInsert(CvSeq * seq,int before_index,const void * element)1252 cvSeqInsert( CvSeq *seq, int before_index, const void *element )
1253 {
1254 int elem_size;
1255 int block_size;
1256 CvSeqBlock *block;
1257 int delta_index;
1258 int total;
1259 schar* ret_ptr = 0;
1260
1261 if( !seq )
1262 CV_Error( CV_StsNullPtr, "" );
1263
1264 total = seq->total;
1265 before_index += before_index < 0 ? total : 0;
1266 before_index -= before_index > total ? total : 0;
1267
1268 if( (unsigned)before_index > (unsigned)total )
1269 CV_Error( CV_StsOutOfRange, "" );
1270
1271 if( before_index == total )
1272 {
1273 ret_ptr = cvSeqPush( seq, element );
1274 }
1275 else if( before_index == 0 )
1276 {
1277 ret_ptr = cvSeqPushFront( seq, element );
1278 }
1279 else
1280 {
1281 elem_size = seq->elem_size;
1282
1283 if( before_index >= total >> 1 )
1284 {
1285 schar *ptr = seq->ptr + elem_size;
1286
1287 if( ptr > seq->block_max )
1288 {
1289 icvGrowSeq( seq, 0 );
1290
1291 ptr = seq->ptr + elem_size;
1292 assert( ptr <= seq->block_max );
1293 }
1294
1295 delta_index = seq->first->start_index;
1296 block = seq->first->prev;
1297 block->count++;
1298 block_size = (int)(ptr - block->data);
1299
1300 while( before_index < block->start_index - delta_index )
1301 {
1302 CvSeqBlock *prev_block = block->prev;
1303
1304 memmove( block->data + elem_size, block->data, block_size - elem_size );
1305 block_size = prev_block->count * elem_size;
1306 memcpy( block->data, prev_block->data + block_size - elem_size, elem_size );
1307 block = prev_block;
1308
1309 /* Check that we don't fall into an infinite loop: */
1310 assert( block != seq->first->prev );
1311 }
1312
1313 before_index = (before_index - block->start_index + delta_index) * elem_size;
1314 memmove( block->data + before_index + elem_size, block->data + before_index,
1315 block_size - before_index - elem_size );
1316
1317 ret_ptr = block->data + before_index;
1318
1319 if( element )
1320 memcpy( ret_ptr, element, elem_size );
1321 seq->ptr = ptr;
1322 }
1323 else
1324 {
1325 block = seq->first;
1326
1327 if( block->start_index == 0 )
1328 {
1329 icvGrowSeq( seq, 1 );
1330
1331 block = seq->first;
1332 }
1333
1334 delta_index = block->start_index;
1335 block->count++;
1336 block->start_index--;
1337 block->data -= elem_size;
1338
1339 while( before_index > block->start_index - delta_index + block->count )
1340 {
1341 CvSeqBlock *next_block = block->next;
1342
1343 block_size = block->count * elem_size;
1344 memmove( block->data, block->data + elem_size, block_size - elem_size );
1345 memcpy( block->data + block_size - elem_size, next_block->data, elem_size );
1346 block = next_block;
1347
1348 /* Check that we don't fall into an infinite loop: */
1349 assert( block != seq->first );
1350 }
1351
1352 before_index = (before_index - block->start_index + delta_index) * elem_size;
1353 memmove( block->data, block->data + elem_size, before_index - elem_size );
1354
1355 ret_ptr = block->data + before_index - elem_size;
1356
1357 if( element )
1358 memcpy( ret_ptr, element, elem_size );
1359 }
1360
1361 seq->total = total + 1;
1362 }
1363
1364 return ret_ptr;
1365 }
1366
1367
1368 /* Removes element from sequence: */
1369 CV_IMPL void
cvSeqRemove(CvSeq * seq,int index)1370 cvSeqRemove( CvSeq *seq, int index )
1371 {
1372 schar *ptr;
1373 int elem_size;
1374 int block_size;
1375 CvSeqBlock *block;
1376 int delta_index;
1377 int total, front = 0;
1378
1379 if( !seq )
1380 CV_Error( CV_StsNullPtr, "" );
1381
1382 total = seq->total;
1383
1384 index += index < 0 ? total : 0;
1385 index -= index >= total ? total : 0;
1386
1387 if( (unsigned) index >= (unsigned) total )
1388 CV_Error( CV_StsOutOfRange, "Invalid index" );
1389
1390 if( index == total - 1 )
1391 {
1392 cvSeqPop( seq, 0 );
1393 }
1394 else if( index == 0 )
1395 {
1396 cvSeqPopFront( seq, 0 );
1397 }
1398 else
1399 {
1400 block = seq->first;
1401 elem_size = seq->elem_size;
1402 delta_index = block->start_index;
1403 while( block->start_index - delta_index + block->count <= index )
1404 block = block->next;
1405
1406 ptr = block->data + (index - block->start_index + delta_index) * elem_size;
1407
1408 front = index < total >> 1;
1409 if( !front )
1410 {
1411 block_size = block->count * elem_size - (int)(ptr - block->data);
1412
1413 while( block != seq->first->prev ) /* while not the last block */
1414 {
1415 CvSeqBlock *next_block = block->next;
1416
1417 memmove( ptr, ptr + elem_size, block_size - elem_size );
1418 memcpy( ptr + block_size - elem_size, next_block->data, elem_size );
1419 block = next_block;
1420 ptr = block->data;
1421 block_size = block->count * elem_size;
1422 }
1423
1424 memmove( ptr, ptr + elem_size, block_size - elem_size );
1425 seq->ptr -= elem_size;
1426 }
1427 else
1428 {
1429 ptr += elem_size;
1430 block_size = (int)(ptr - block->data);
1431
1432 while( block != seq->first )
1433 {
1434 CvSeqBlock *prev_block = block->prev;
1435
1436 memmove( block->data + elem_size, block->data, block_size - elem_size );
1437 block_size = prev_block->count * elem_size;
1438 memcpy( block->data, prev_block->data + block_size - elem_size, elem_size );
1439 block = prev_block;
1440 }
1441
1442 memmove( block->data + elem_size, block->data, block_size - elem_size );
1443 block->data += elem_size;
1444 block->start_index++;
1445 }
1446
1447 seq->total = total - 1;
1448 if( --block->count == 0 )
1449 icvFreeSeqBlock( seq, front );
1450 }
1451 }
1452
1453
1454 /* Add several elements to the beginning or end of a sequence: */
1455 CV_IMPL void
cvSeqPushMulti(CvSeq * seq,const void * _elements,int count,int front)1456 cvSeqPushMulti( CvSeq *seq, const void *_elements, int count, int front )
1457 {
1458 char *elements = (char *) _elements;
1459
1460 if( !seq )
1461 CV_Error( CV_StsNullPtr, "NULL sequence pointer" );
1462 if( count < 0 )
1463 CV_Error( CV_StsBadSize, "number of removed elements is negative" );
1464
1465 int elem_size = seq->elem_size;
1466
1467 if( !front )
1468 {
1469 while( count > 0 )
1470 {
1471 int delta = (int)((seq->block_max - seq->ptr) / elem_size);
1472
1473 delta = MIN( delta, count );
1474 if( delta > 0 )
1475 {
1476 seq->first->prev->count += delta;
1477 seq->total += delta;
1478 count -= delta;
1479 delta *= elem_size;
1480 if( elements )
1481 {
1482 memcpy( seq->ptr, elements, delta );
1483 elements += delta;
1484 }
1485 seq->ptr += delta;
1486 }
1487
1488 if( count > 0 )
1489 icvGrowSeq( seq, 0 );
1490 }
1491 }
1492 else
1493 {
1494 CvSeqBlock* block = seq->first;
1495
1496 while( count > 0 )
1497 {
1498 int delta;
1499
1500 if( !block || block->start_index == 0 )
1501 {
1502 icvGrowSeq( seq, 1 );
1503
1504 block = seq->first;
1505 assert( block->start_index > 0 );
1506 }
1507
1508 delta = MIN( block->start_index, count );
1509 count -= delta;
1510 block->start_index -= delta;
1511 block->count += delta;
1512 seq->total += delta;
1513 delta *= elem_size;
1514 block->data -= delta;
1515
1516 if( elements )
1517 memcpy( block->data, elements + count*elem_size, delta );
1518 }
1519 }
1520 }
1521
1522
1523 /* Remove several elements from the end of sequence: */
1524 CV_IMPL void
cvSeqPopMulti(CvSeq * seq,void * _elements,int count,int front)1525 cvSeqPopMulti( CvSeq *seq, void *_elements, int count, int front )
1526 {
1527 char *elements = (char *) _elements;
1528
1529 if( !seq )
1530 CV_Error( CV_StsNullPtr, "NULL sequence pointer" );
1531 if( count < 0 )
1532 CV_Error( CV_StsBadSize, "number of removed elements is negative" );
1533
1534 count = MIN( count, seq->total );
1535
1536 if( !front )
1537 {
1538 if( elements )
1539 elements += count * seq->elem_size;
1540
1541 while( count > 0 )
1542 {
1543 int delta = seq->first->prev->count;
1544
1545 delta = MIN( delta, count );
1546 assert( delta > 0 );
1547
1548 seq->first->prev->count -= delta;
1549 seq->total -= delta;
1550 count -= delta;
1551 delta *= seq->elem_size;
1552 seq->ptr -= delta;
1553
1554 if( elements )
1555 {
1556 elements -= delta;
1557 memcpy( elements, seq->ptr, delta );
1558 }
1559
1560 if( seq->first->prev->count == 0 )
1561 icvFreeSeqBlock( seq, 0 );
1562 }
1563 }
1564 else
1565 {
1566 while( count > 0 )
1567 {
1568 int delta = seq->first->count;
1569
1570 delta = MIN( delta, count );
1571 assert( delta > 0 );
1572
1573 seq->first->count -= delta;
1574 seq->total -= delta;
1575 count -= delta;
1576 seq->first->start_index += delta;
1577 delta *= seq->elem_size;
1578
1579 if( elements )
1580 {
1581 memcpy( elements, seq->first->data, delta );
1582 elements += delta;
1583 }
1584
1585 seq->first->data += delta;
1586 if( seq->first->count == 0 )
1587 icvFreeSeqBlock( seq, 1 );
1588 }
1589 }
1590 }
1591
1592
1593 /* Remove all elements from a sequence: */
1594 CV_IMPL void
cvClearSeq(CvSeq * seq)1595 cvClearSeq( CvSeq *seq )
1596 {
1597 if( !seq )
1598 CV_Error( CV_StsNullPtr, "" );
1599 cvSeqPopMulti( seq, 0, seq->total );
1600 }
1601
1602
1603 CV_IMPL CvSeq*
cvSeqSlice(const CvSeq * seq,CvSlice slice,CvMemStorage * storage,int copy_data)1604 cvSeqSlice( const CvSeq* seq, CvSlice slice, CvMemStorage* storage, int copy_data )
1605 {
1606 CvSeq* subseq = 0;
1607 int elem_size, count, length;
1608 CvSeqReader reader;
1609 CvSeqBlock *block, *first_block = 0, *last_block = 0;
1610
1611 if( !CV_IS_SEQ(seq) )
1612 CV_Error( CV_StsBadArg, "Invalid sequence header" );
1613
1614 if( !storage )
1615 {
1616 storage = seq->storage;
1617 if( !storage )
1618 CV_Error( CV_StsNullPtr, "NULL storage pointer" );
1619 }
1620
1621 elem_size = seq->elem_size;
1622 length = cvSliceLength( slice, seq );
1623 if( slice.start_index < 0 )
1624 slice.start_index += seq->total;
1625 else if( slice.start_index >= seq->total )
1626 slice.start_index -= seq->total;
1627 if( (unsigned)length > (unsigned)seq->total ||
1628 ((unsigned)slice.start_index >= (unsigned)seq->total && length != 0) )
1629 CV_Error( CV_StsOutOfRange, "Bad sequence slice" );
1630
1631 subseq = cvCreateSeq( seq->flags, seq->header_size, elem_size, storage );
1632
1633 if( length > 0 )
1634 {
1635 cvStartReadSeq( seq, &reader, 0 );
1636 cvSetSeqReaderPos( &reader, slice.start_index, 0 );
1637 count = (int)((reader.block_max - reader.ptr)/elem_size);
1638
1639 do
1640 {
1641 int bl = MIN( count, length );
1642
1643 if( !copy_data )
1644 {
1645 block = (CvSeqBlock*)cvMemStorageAlloc( storage, sizeof(*block) );
1646 if( !first_block )
1647 {
1648 first_block = subseq->first = block->prev = block->next = block;
1649 block->start_index = 0;
1650 }
1651 else
1652 {
1653 block->prev = last_block;
1654 block->next = first_block;
1655 last_block->next = first_block->prev = block;
1656 block->start_index = last_block->start_index + last_block->count;
1657 }
1658 last_block = block;
1659 block->data = reader.ptr;
1660 block->count = bl;
1661 subseq->total += bl;
1662 }
1663 else
1664 cvSeqPushMulti( subseq, reader.ptr, bl, 0 );
1665 length -= bl;
1666 reader.block = reader.block->next;
1667 reader.ptr = reader.block->data;
1668 count = reader.block->count;
1669 }
1670 while( length > 0 );
1671 }
1672
1673 return subseq;
1674 }
1675
1676
1677 // Remove slice from the middle of the sequence.
1678 // !!! TODO !!! Implement more efficient algorithm
1679 CV_IMPL void
cvSeqRemoveSlice(CvSeq * seq,CvSlice slice)1680 cvSeqRemoveSlice( CvSeq* seq, CvSlice slice )
1681 {
1682 int total, length;
1683
1684 if( !CV_IS_SEQ(seq) )
1685 CV_Error( CV_StsBadArg, "Invalid sequence header" );
1686
1687 length = cvSliceLength( slice, seq );
1688 total = seq->total;
1689
1690 if( slice.start_index < 0 )
1691 slice.start_index += total;
1692 else if( slice.start_index >= total )
1693 slice.start_index -= total;
1694
1695 if( (unsigned)slice.start_index >= (unsigned)total )
1696 CV_Error( CV_StsOutOfRange, "start slice index is out of range" );
1697
1698 slice.end_index = slice.start_index + length;
1699
1700 if ( slice.start_index == slice.end_index )
1701 return;
1702
1703 if( slice.end_index < total )
1704 {
1705 CvSeqReader reader_to, reader_from;
1706 int elem_size = seq->elem_size;
1707
1708 cvStartReadSeq( seq, &reader_to );
1709 cvStartReadSeq( seq, &reader_from );
1710
1711 if( slice.start_index > total - slice.end_index )
1712 {
1713 int i, count = seq->total - slice.end_index;
1714 cvSetSeqReaderPos( &reader_to, slice.start_index );
1715 cvSetSeqReaderPos( &reader_from, slice.end_index );
1716
1717 for( i = 0; i < count; i++ )
1718 {
1719 memcpy( reader_to.ptr, reader_from.ptr, elem_size );
1720 CV_NEXT_SEQ_ELEM( elem_size, reader_to );
1721 CV_NEXT_SEQ_ELEM( elem_size, reader_from );
1722 }
1723
1724 cvSeqPopMulti( seq, 0, slice.end_index - slice.start_index );
1725 }
1726 else
1727 {
1728 int i, count = slice.start_index;
1729 cvSetSeqReaderPos( &reader_to, slice.end_index );
1730 cvSetSeqReaderPos( &reader_from, slice.start_index );
1731
1732 for( i = 0; i < count; i++ )
1733 {
1734 CV_PREV_SEQ_ELEM( elem_size, reader_to );
1735 CV_PREV_SEQ_ELEM( elem_size, reader_from );
1736
1737 memcpy( reader_to.ptr, reader_from.ptr, elem_size );
1738 }
1739
1740 cvSeqPopMulti( seq, 0, slice.end_index - slice.start_index, 1 );
1741 }
1742 }
1743 else
1744 {
1745 cvSeqPopMulti( seq, 0, total - slice.start_index );
1746 cvSeqPopMulti( seq, 0, slice.end_index - total, 1 );
1747 }
1748 }
1749
1750
1751 // Insert a sequence into the middle of another sequence:
1752 // !!! TODO !!! Implement more efficient algorithm
1753 CV_IMPL void
cvSeqInsertSlice(CvSeq * seq,int index,const CvArr * from_arr)1754 cvSeqInsertSlice( CvSeq* seq, int index, const CvArr* from_arr )
1755 {
1756 CvSeqReader reader_to, reader_from;
1757 int i, elem_size, total, from_total;
1758 CvSeq from_header, *from = (CvSeq*)from_arr;
1759 CvSeqBlock block;
1760
1761 if( !CV_IS_SEQ(seq) )
1762 CV_Error( CV_StsBadArg, "Invalid destination sequence header" );
1763
1764 if( !CV_IS_SEQ(from))
1765 {
1766 CvMat* mat = (CvMat*)from;
1767 if( !CV_IS_MAT(mat))
1768 CV_Error( CV_StsBadArg, "Source is not a sequence nor matrix" );
1769
1770 if( !CV_IS_MAT_CONT(mat->type) || (mat->rows != 1 && mat->cols != 1) )
1771 CV_Error( CV_StsBadArg, "The source array must be 1d continuous vector" );
1772
1773 from = cvMakeSeqHeaderForArray( CV_SEQ_KIND_GENERIC, sizeof(from_header),
1774 CV_ELEM_SIZE(mat->type),
1775 mat->data.ptr, mat->cols + mat->rows - 1,
1776 &from_header, &block );
1777 }
1778
1779 if( seq->elem_size != from->elem_size )
1780 CV_Error( CV_StsUnmatchedSizes,
1781 "Source and destination sequence element sizes are different." );
1782
1783 from_total = from->total;
1784
1785 if( from_total == 0 )
1786 return;
1787
1788 total = seq->total;
1789 index += index < 0 ? total : 0;
1790 index -= index > total ? total : 0;
1791
1792 if( (unsigned)index > (unsigned)total )
1793 CV_Error( CV_StsOutOfRange, "" );
1794
1795 elem_size = seq->elem_size;
1796
1797 if( index < (total >> 1) )
1798 {
1799 cvSeqPushMulti( seq, 0, from_total, 1 );
1800
1801 cvStartReadSeq( seq, &reader_to );
1802 cvStartReadSeq( seq, &reader_from );
1803 cvSetSeqReaderPos( &reader_from, from_total );
1804
1805 for( i = 0; i < index; i++ )
1806 {
1807 memcpy( reader_to.ptr, reader_from.ptr, elem_size );
1808 CV_NEXT_SEQ_ELEM( elem_size, reader_to );
1809 CV_NEXT_SEQ_ELEM( elem_size, reader_from );
1810 }
1811 }
1812 else
1813 {
1814 cvSeqPushMulti( seq, 0, from_total );
1815
1816 cvStartReadSeq( seq, &reader_to );
1817 cvStartReadSeq( seq, &reader_from );
1818 cvSetSeqReaderPos( &reader_from, total );
1819 cvSetSeqReaderPos( &reader_to, seq->total );
1820
1821 for( i = 0; i < total - index; i++ )
1822 {
1823 CV_PREV_SEQ_ELEM( elem_size, reader_to );
1824 CV_PREV_SEQ_ELEM( elem_size, reader_from );
1825 memcpy( reader_to.ptr, reader_from.ptr, elem_size );
1826 }
1827 }
1828
1829 cvStartReadSeq( from, &reader_from );
1830 cvSetSeqReaderPos( &reader_to, index );
1831
1832 for( i = 0; i < from_total; i++ )
1833 {
1834 memcpy( reader_to.ptr, reader_from.ptr, elem_size );
1835 CV_NEXT_SEQ_ELEM( elem_size, reader_to );
1836 CV_NEXT_SEQ_ELEM( elem_size, reader_from );
1837 }
1838 }
1839
1840 // Sort the sequence using user-specified comparison function.
1841 // The semantics is similar to qsort() function.
1842 // The code is based on BSD system qsort():
1843 // * Copyright (c) 1992, 1993
1844 // * The Regents of the University of California. All rights reserved.
1845 // *
1846 // * Redistribution and use in source and binary forms, with or without
1847 // * modification, are permitted provided that the following conditions
1848 // * are met:
1849 // * 1. Redistributions of source code must retain the above copyright
1850 // * notice, this list of conditions and the following disclaimer.
1851 // * 2. Redistributions in binary form must reproduce the above copyright
1852 // * notice, this list of conditions and the following disclaimer in the
1853 // * documentation and/or other materials provided with the distribution.
1854 // * 3. All advertising materials mentioning features or use of this software
1855 // * must display the following acknowledgement:
1856 // * This product includes software developed by the University of
1857 // * California, Berkeley and its contributors.
1858 // * 4. Neither the name of the University nor the names of its contributors
1859 // * may be used to endorse or promote products derived from this software
1860 // * without specific prior written permission.
1861 // *
1862 // * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
1863 // * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1864 // * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1865 // * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
1866 // * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
1867 // * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
1868 // * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
1869 // * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
1870 // * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
1871 // * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
1872 // * SUCH DAMAGE.
1873
1874 typedef struct CvSeqReaderPos
1875 {
1876 CvSeqBlock* block;
1877 schar* ptr;
1878 schar* block_min;
1879 schar* block_max;
1880 }
1881 CvSeqReaderPos;
1882
1883 #define CV_SAVE_READER_POS( reader, pos ) \
1884 { \
1885 (pos).block = (reader).block; \
1886 (pos).ptr = (reader).ptr; \
1887 (pos).block_min = (reader).block_min; \
1888 (pos).block_max = (reader).block_max; \
1889 }
1890
1891 #define CV_RESTORE_READER_POS( reader, pos )\
1892 { \
1893 (reader).block = (pos).block; \
1894 (reader).ptr = (pos).ptr; \
1895 (reader).block_min = (pos).block_min; \
1896 (reader).block_max = (pos).block_max; \
1897 }
1898
1899 inline schar*
icvMed3(schar * a,schar * b,schar * c,CvCmpFunc cmp_func,void * aux)1900 icvMed3( schar* a, schar* b, schar* c, CvCmpFunc cmp_func, void* aux )
1901 {
1902 return cmp_func(a, b, aux) < 0 ?
1903 (cmp_func(b, c, aux) < 0 ? b : cmp_func(a, c, aux) < 0 ? c : a)
1904 :(cmp_func(b, c, aux) > 0 ? b : cmp_func(a, c, aux) < 0 ? a : c);
1905 }
1906
1907 CV_IMPL void
cvSeqSort(CvSeq * seq,CvCmpFunc cmp_func,void * aux)1908 cvSeqSort( CvSeq* seq, CvCmpFunc cmp_func, void* aux )
1909 {
1910 int elem_size;
1911 int isort_thresh = 7;
1912 CvSeqReader left, right;
1913 int sp = 0;
1914
1915 struct
1916 {
1917 CvSeqReaderPos lb;
1918 CvSeqReaderPos ub;
1919 }
1920 stack[48];
1921
1922 if( !CV_IS_SEQ(seq) )
1923 CV_Error( !seq ? CV_StsNullPtr : CV_StsBadArg, "Bad input sequence" );
1924
1925 if( !cmp_func )
1926 CV_Error( CV_StsNullPtr, "Null compare function" );
1927
1928 if( seq->total <= 1 )
1929 return;
1930
1931 elem_size = seq->elem_size;
1932 isort_thresh *= elem_size;
1933
1934 cvStartReadSeq( seq, &left, 0 );
1935 right = left;
1936 CV_SAVE_READER_POS( left, stack[0].lb );
1937 CV_PREV_SEQ_ELEM( elem_size, right );
1938 CV_SAVE_READER_POS( right, stack[0].ub );
1939
1940 while( sp >= 0 )
1941 {
1942 CV_RESTORE_READER_POS( left, stack[sp].lb );
1943 CV_RESTORE_READER_POS( right, stack[sp].ub );
1944 sp--;
1945
1946 for(;;)
1947 {
1948 int i, n, m;
1949 CvSeqReader ptr, ptr2;
1950
1951 if( left.block == right.block )
1952 n = (int)(right.ptr - left.ptr) + elem_size;
1953 else
1954 {
1955 n = cvGetSeqReaderPos( &right );
1956 n = (n - cvGetSeqReaderPos( &left ) + 1)*elem_size;
1957 }
1958
1959 if( n <= isort_thresh )
1960 {
1961 insert_sort:
1962 ptr = ptr2 = left;
1963 CV_NEXT_SEQ_ELEM( elem_size, ptr );
1964 CV_NEXT_SEQ_ELEM( elem_size, right );
1965 while( ptr.ptr != right.ptr )
1966 {
1967 ptr2.ptr = ptr.ptr;
1968 if( ptr2.block != ptr.block )
1969 {
1970 ptr2.block = ptr.block;
1971 ptr2.block_min = ptr.block_min;
1972 ptr2.block_max = ptr.block_max;
1973 }
1974 while( ptr2.ptr != left.ptr )
1975 {
1976 schar* cur = ptr2.ptr;
1977 CV_PREV_SEQ_ELEM( elem_size, ptr2 );
1978 if( cmp_func( ptr2.ptr, cur, aux ) <= 0 )
1979 break;
1980 CV_SWAP_ELEMS( ptr2.ptr, cur, elem_size );
1981 }
1982 CV_NEXT_SEQ_ELEM( elem_size, ptr );
1983 }
1984 break;
1985 }
1986 else
1987 {
1988 CvSeqReader left0, left1, right0, right1;
1989 CvSeqReader tmp0, tmp1;
1990 schar *m1, *m2, *m3, *pivot;
1991 int swap_cnt = 0;
1992 int l, l0, l1, r, r0, r1;
1993
1994 left0 = tmp0 = left;
1995 right0 = right1 = right;
1996 n /= elem_size;
1997
1998 if( n > 40 )
1999 {
2000 int d = n / 8;
2001 schar *p1, *p2, *p3;
2002 p1 = tmp0.ptr;
2003 cvSetSeqReaderPos( &tmp0, d, 1 );
2004 p2 = tmp0.ptr;
2005 cvSetSeqReaderPos( &tmp0, d, 1 );
2006 p3 = tmp0.ptr;
2007 m1 = icvMed3( p1, p2, p3, cmp_func, aux );
2008 cvSetSeqReaderPos( &tmp0, (n/2) - d*3, 1 );
2009 p1 = tmp0.ptr;
2010 cvSetSeqReaderPos( &tmp0, d, 1 );
2011 p2 = tmp0.ptr;
2012 cvSetSeqReaderPos( &tmp0, d, 1 );
2013 p3 = tmp0.ptr;
2014 m2 = icvMed3( p1, p2, p3, cmp_func, aux );
2015 cvSetSeqReaderPos( &tmp0, n - 1 - d*3 - n/2, 1 );
2016 p1 = tmp0.ptr;
2017 cvSetSeqReaderPos( &tmp0, d, 1 );
2018 p2 = tmp0.ptr;
2019 cvSetSeqReaderPos( &tmp0, d, 1 );
2020 p3 = tmp0.ptr;
2021 m3 = icvMed3( p1, p2, p3, cmp_func, aux );
2022 }
2023 else
2024 {
2025 m1 = tmp0.ptr;
2026 cvSetSeqReaderPos( &tmp0, n/2, 1 );
2027 m2 = tmp0.ptr;
2028 cvSetSeqReaderPos( &tmp0, n - 1 - n/2, 1 );
2029 m3 = tmp0.ptr;
2030 }
2031
2032 pivot = icvMed3( m1, m2, m3, cmp_func, aux );
2033 left = left0;
2034 if( pivot != left.ptr )
2035 {
2036 CV_SWAP_ELEMS( pivot, left.ptr, elem_size );
2037 pivot = left.ptr;
2038 }
2039 CV_NEXT_SEQ_ELEM( elem_size, left );
2040 left1 = left;
2041
2042 for(;;)
2043 {
2044 while( left.ptr != right.ptr && (r = cmp_func(left.ptr, pivot, aux)) <= 0 )
2045 {
2046 if( r == 0 )
2047 {
2048 if( left1.ptr != left.ptr )
2049 CV_SWAP_ELEMS( left1.ptr, left.ptr, elem_size );
2050 swap_cnt = 1;
2051 CV_NEXT_SEQ_ELEM( elem_size, left1 );
2052 }
2053 CV_NEXT_SEQ_ELEM( elem_size, left );
2054 }
2055
2056 while( left.ptr != right.ptr && (r = cmp_func(right.ptr,pivot, aux)) >= 0 )
2057 {
2058 if( r == 0 )
2059 {
2060 if( right1.ptr != right.ptr )
2061 CV_SWAP_ELEMS( right1.ptr, right.ptr, elem_size );
2062 swap_cnt = 1;
2063 CV_PREV_SEQ_ELEM( elem_size, right1 );
2064 }
2065 CV_PREV_SEQ_ELEM( elem_size, right );
2066 }
2067
2068 if( left.ptr == right.ptr )
2069 {
2070 r = cmp_func(left.ptr, pivot, aux);
2071 if( r == 0 )
2072 {
2073 if( left1.ptr != left.ptr )
2074 CV_SWAP_ELEMS( left1.ptr, left.ptr, elem_size );
2075 swap_cnt = 1;
2076 CV_NEXT_SEQ_ELEM( elem_size, left1 );
2077 }
2078 if( r <= 0 )
2079 {
2080 CV_NEXT_SEQ_ELEM( elem_size, left );
2081 }
2082 else
2083 {
2084 CV_PREV_SEQ_ELEM( elem_size, right );
2085 }
2086 break;
2087 }
2088
2089 CV_SWAP_ELEMS( left.ptr, right.ptr, elem_size );
2090 CV_NEXT_SEQ_ELEM( elem_size, left );
2091 r = left.ptr == right.ptr;
2092 CV_PREV_SEQ_ELEM( elem_size, right );
2093 swap_cnt = 1;
2094 if( r )
2095 break;
2096 }
2097
2098 if( swap_cnt == 0 )
2099 {
2100 left = left0, right = right0;
2101 goto insert_sort;
2102 }
2103
2104 l = cvGetSeqReaderPos( &left );
2105 if( l == 0 )
2106 l = seq->total;
2107 l0 = cvGetSeqReaderPos( &left0 );
2108 l1 = cvGetSeqReaderPos( &left1 );
2109 if( l1 == 0 )
2110 l1 = seq->total;
2111
2112 n = MIN( l - l1, l1 - l0 );
2113 if( n > 0 )
2114 {
2115 tmp0 = left0;
2116 tmp1 = left;
2117 cvSetSeqReaderPos( &tmp1, 0-n, 1 );
2118 for( i = 0; i < n; i++ )
2119 {
2120 CV_SWAP_ELEMS( tmp0.ptr, tmp1.ptr, elem_size );
2121 CV_NEXT_SEQ_ELEM( elem_size, tmp0 );
2122 CV_NEXT_SEQ_ELEM( elem_size, tmp1 );
2123 }
2124 }
2125
2126 r = cvGetSeqReaderPos( &right );
2127 r0 = cvGetSeqReaderPos( &right0 );
2128 r1 = cvGetSeqReaderPos( &right1 );
2129 m = MIN( r0 - r1, r1 - r );
2130 if( m > 0 )
2131 {
2132 tmp0 = left;
2133 tmp1 = right0;
2134 cvSetSeqReaderPos( &tmp1, 1-m, 1 );
2135 for( i = 0; i < m; i++ )
2136 {
2137 CV_SWAP_ELEMS( tmp0.ptr, tmp1.ptr, elem_size );
2138 CV_NEXT_SEQ_ELEM( elem_size, tmp0 );
2139 CV_NEXT_SEQ_ELEM( elem_size, tmp1 );
2140 }
2141 }
2142
2143 n = l - l1;
2144 m = r1 - r;
2145 if( n > 1 )
2146 {
2147 if( m > 1 )
2148 {
2149 if( n > m )
2150 {
2151 sp++;
2152 CV_SAVE_READER_POS( left0, stack[sp].lb );
2153 cvSetSeqReaderPos( &left0, n - 1, 1 );
2154 CV_SAVE_READER_POS( left0, stack[sp].ub );
2155 left = right = right0;
2156 cvSetSeqReaderPos( &left, 1 - m, 1 );
2157 }
2158 else
2159 {
2160 sp++;
2161 CV_SAVE_READER_POS( right0, stack[sp].ub );
2162 cvSetSeqReaderPos( &right0, 1 - m, 1 );
2163 CV_SAVE_READER_POS( right0, stack[sp].lb );
2164 left = right = left0;
2165 cvSetSeqReaderPos( &right, n - 1, 1 );
2166 }
2167 }
2168 else
2169 {
2170 left = right = left0;
2171 cvSetSeqReaderPos( &right, n - 1, 1 );
2172 }
2173 }
2174 else if( m > 1 )
2175 {
2176 left = right = right0;
2177 cvSetSeqReaderPos( &left, 1 - m, 1 );
2178 }
2179 else
2180 break;
2181 }
2182 }
2183 }
2184 }
2185
2186
2187 CV_IMPL schar*
cvSeqSearch(CvSeq * seq,const void * _elem,CvCmpFunc cmp_func,int is_sorted,int * _idx,void * userdata)2188 cvSeqSearch( CvSeq* seq, const void* _elem, CvCmpFunc cmp_func,
2189 int is_sorted, int* _idx, void* userdata )
2190 {
2191 schar* result = 0;
2192 const schar* elem = (const schar*)_elem;
2193 int idx = -1;
2194 int i, j;
2195
2196 if( _idx )
2197 *_idx = idx;
2198
2199 if( !CV_IS_SEQ(seq) )
2200 CV_Error( !seq ? CV_StsNullPtr : CV_StsBadArg, "Bad input sequence" );
2201
2202 if( !elem )
2203 CV_Error( CV_StsNullPtr, "Null element pointer" );
2204
2205 int elem_size = seq->elem_size;
2206 int total = seq->total;
2207
2208 if( total == 0 )
2209 return 0;
2210
2211 if( !is_sorted )
2212 {
2213 CvSeqReader reader;
2214 cvStartReadSeq( seq, &reader, 0 );
2215
2216 if( cmp_func )
2217 {
2218 for( i = 0; i < total; i++ )
2219 {
2220 if( cmp_func( elem, reader.ptr, userdata ) == 0 )
2221 break;
2222 CV_NEXT_SEQ_ELEM( elem_size, reader );
2223 }
2224 }
2225 else if( (elem_size & (sizeof(int)-1)) == 0 )
2226 {
2227 for( i = 0; i < total; i++ )
2228 {
2229 for( j = 0; j < elem_size; j += sizeof(int) )
2230 {
2231 if( *(const int*)(reader.ptr + j) != *(const int*)(elem + j) )
2232 break;
2233 }
2234 if( j == elem_size )
2235 break;
2236 CV_NEXT_SEQ_ELEM( elem_size, reader );
2237 }
2238 }
2239 else
2240 {
2241 for( i = 0; i < total; i++ )
2242 {
2243 for( j = 0; j < elem_size; j++ )
2244 {
2245 if( reader.ptr[j] != elem[j] )
2246 break;
2247 }
2248 if( j == elem_size )
2249 break;
2250 CV_NEXT_SEQ_ELEM( elem_size, reader );
2251 }
2252 }
2253
2254 idx = i;
2255 if( i < total )
2256 result = reader.ptr;
2257 }
2258 else
2259 {
2260 if( !cmp_func )
2261 CV_Error( CV_StsNullPtr, "Null compare function" );
2262
2263 i = 0, j = total;
2264
2265 while( j > i )
2266 {
2267 int k = (i+j)>>1, code;
2268 schar* ptr = cvGetSeqElem( seq, k );
2269 code = cmp_func( elem, ptr, userdata );
2270 if( !code )
2271 {
2272 result = ptr;
2273 idx = k;
2274 if( _idx )
2275 *_idx = idx;
2276 return result;
2277 }
2278 if( code < 0 )
2279 j = k;
2280 else
2281 i = k+1;
2282 }
2283 idx = j;
2284 }
2285
2286 if( _idx )
2287 *_idx = idx;
2288
2289 return result;
2290 }
2291
2292
2293 CV_IMPL void
cvSeqInvert(CvSeq * seq)2294 cvSeqInvert( CvSeq* seq )
2295 {
2296 CvSeqReader left_reader, right_reader;
2297 int elem_size;
2298 int i, count;
2299
2300 cvStartReadSeq( seq, &left_reader, 0 );
2301 cvStartReadSeq( seq, &right_reader, 1 );
2302 elem_size = seq->elem_size;
2303 count = seq->total >> 1;
2304
2305 for( i = 0; i < count; i++ )
2306 {
2307 CV_SWAP_ELEMS( left_reader.ptr, right_reader.ptr, elem_size );
2308 CV_NEXT_SEQ_ELEM( elem_size, left_reader );
2309 CV_PREV_SEQ_ELEM( elem_size, right_reader );
2310 }
2311 }
2312
2313
2314 typedef struct CvPTreeNode
2315 {
2316 struct CvPTreeNode* parent;
2317 schar* element;
2318 int rank;
2319 }
2320 CvPTreeNode;
2321
2322
2323 // This function splits the input sequence or set into one or more equivalence classes.
2324 // is_equal(a,b,...) returns non-zero if the two sequence elements
2325 // belong to the same class. The function returns sequence of integers -
2326 // 0-based class indexes for each element.
2327 //
2328 // The algorithm is described in "Introduction to Algorithms"
2329 // by Cormen, Leiserson and Rivest, chapter "Data structures for disjoint sets"
2330 CV_IMPL int
cvSeqPartition(const CvSeq * seq,CvMemStorage * storage,CvSeq ** labels,CvCmpFunc is_equal,void * userdata)2331 cvSeqPartition( const CvSeq* seq, CvMemStorage* storage, CvSeq** labels,
2332 CvCmpFunc is_equal, void* userdata )
2333 {
2334 CvSeq* result = 0;
2335 CvMemStorage* temp_storage = 0;
2336 int class_idx = 0;
2337
2338 CvSeqWriter writer;
2339 CvSeqReader reader, reader0;
2340 CvSeq* nodes;
2341 int i, j;
2342 int is_set;
2343
2344 if( !labels )
2345 CV_Error( CV_StsNullPtr, "" );
2346
2347 if( !seq || !is_equal )
2348 CV_Error( CV_StsNullPtr, "" );
2349
2350 if( !storage )
2351 storage = seq->storage;
2352
2353 if( !storage )
2354 CV_Error( CV_StsNullPtr, "" );
2355
2356 is_set = CV_IS_SET(seq);
2357
2358 temp_storage = cvCreateChildMemStorage( storage );
2359
2360 nodes = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvPTreeNode), temp_storage );
2361
2362 cvStartReadSeq( seq, &reader );
2363 memset( &writer, 0, sizeof(writer));
2364 cvStartAppendToSeq( nodes, &writer );
2365
2366 // Initial O(N) pass. Make a forest of single-vertex trees.
2367 for( i = 0; i < seq->total; i++ )
2368 {
2369 CvPTreeNode node = { 0, 0, 0 };
2370 if( !is_set || CV_IS_SET_ELEM( reader.ptr ))
2371 node.element = reader.ptr;
2372 CV_WRITE_SEQ_ELEM( node, writer );
2373 CV_NEXT_SEQ_ELEM( seq->elem_size, reader );
2374 }
2375
2376 cvEndWriteSeq( &writer );
2377
2378 // Because in the next loop we will iterate
2379 // through all the sequence nodes each time,
2380 // we do not need to initialize reader every time:
2381 cvStartReadSeq( nodes, &reader );
2382 cvStartReadSeq( nodes, &reader0 );
2383
2384 // The main O(N^2) pass. Merge connected components.
2385 for( i = 0; i < nodes->total; i++ )
2386 {
2387 CvPTreeNode* node = (CvPTreeNode*)(reader0.ptr);
2388 CvPTreeNode* root = node;
2389 CV_NEXT_SEQ_ELEM( nodes->elem_size, reader0 );
2390
2391 if( !node->element )
2392 continue;
2393
2394 // find root
2395 while( root->parent )
2396 root = root->parent;
2397
2398 for( j = 0; j < nodes->total; j++ )
2399 {
2400 CvPTreeNode* node2 = (CvPTreeNode*)reader.ptr;
2401
2402 if( node2->element && node2 != node &&
2403 is_equal( node->element, node2->element, userdata ))
2404 {
2405 CvPTreeNode* root2 = node2;
2406
2407 // unite both trees
2408 while( root2->parent )
2409 root2 = root2->parent;
2410
2411 if( root2 != root )
2412 {
2413 if( root->rank > root2->rank )
2414 root2->parent = root;
2415 else
2416 {
2417 root->parent = root2;
2418 root2->rank += root->rank == root2->rank;
2419 root = root2;
2420 }
2421 assert( root->parent == 0 );
2422
2423 // Compress path from node2 to the root:
2424 while( node2->parent )
2425 {
2426 CvPTreeNode* temp = node2;
2427 node2 = node2->parent;
2428 temp->parent = root;
2429 }
2430
2431 // Compress path from node to the root:
2432 node2 = node;
2433 while( node2->parent )
2434 {
2435 CvPTreeNode* temp = node2;
2436 node2 = node2->parent;
2437 temp->parent = root;
2438 }
2439 }
2440 }
2441
2442 CV_NEXT_SEQ_ELEM( sizeof(*node), reader );
2443 }
2444 }
2445
2446 // Final O(N) pass (Enumerate classes)
2447 // Reuse reader one more time
2448 result = cvCreateSeq( 0, sizeof(CvSeq), sizeof(int), storage );
2449 cvStartAppendToSeq( result, &writer );
2450
2451 for( i = 0; i < nodes->total; i++ )
2452 {
2453 CvPTreeNode* node = (CvPTreeNode*)reader.ptr;
2454 int idx = -1;
2455
2456 if( node->element )
2457 {
2458 while( node->parent )
2459 node = node->parent;
2460 if( node->rank >= 0 )
2461 node->rank = ~class_idx++;
2462 idx = ~node->rank;
2463 }
2464
2465 CV_NEXT_SEQ_ELEM( sizeof(*node), reader );
2466 CV_WRITE_SEQ_ELEM( idx, writer );
2467 }
2468
2469 cvEndWriteSeq( &writer );
2470
2471 if( labels )
2472 *labels = result;
2473
2474 cvReleaseMemStorage( &temp_storage );
2475 return class_idx;
2476 }
2477
2478
2479 /****************************************************************************************\
2480 * Set implementation *
2481 \****************************************************************************************/
2482
2483 /* Creates empty set: */
2484 CV_IMPL CvSet*
cvCreateSet(int set_flags,int header_size,int elem_size,CvMemStorage * storage)2485 cvCreateSet( int set_flags, int header_size, int elem_size, CvMemStorage * storage )
2486 {
2487 if( !storage )
2488 CV_Error( CV_StsNullPtr, "" );
2489 if( header_size < (int)sizeof( CvSet ) ||
2490 elem_size < (int)sizeof(void*)*2 ||
2491 (elem_size & (sizeof(void*)-1)) != 0 )
2492 CV_Error( CV_StsBadSize, "" );
2493
2494 CvSet* set = (CvSet*) cvCreateSeq( set_flags, header_size, elem_size, storage );
2495 set->flags = (set->flags & ~CV_MAGIC_MASK) | CV_SET_MAGIC_VAL;
2496
2497 return set;
2498 }
2499
2500
2501 /* Add new element to the set: */
2502 CV_IMPL int
cvSetAdd(CvSet * set,CvSetElem * element,CvSetElem ** inserted_element)2503 cvSetAdd( CvSet* set, CvSetElem* element, CvSetElem** inserted_element )
2504 {
2505 int id = -1;
2506 CvSetElem *free_elem;
2507
2508 if( !set )
2509 CV_Error( CV_StsNullPtr, "" );
2510
2511 if( !(set->free_elems) )
2512 {
2513 int count = set->total;
2514 int elem_size = set->elem_size;
2515 schar *ptr;
2516 icvGrowSeq( (CvSeq *) set, 0 );
2517
2518 set->free_elems = (CvSetElem*) (ptr = set->ptr);
2519 for( ; ptr + elem_size <= set->block_max; ptr += elem_size, count++ )
2520 {
2521 ((CvSetElem*)ptr)->flags = count | CV_SET_ELEM_FREE_FLAG;
2522 ((CvSetElem*)ptr)->next_free = (CvSetElem*)(ptr + elem_size);
2523 }
2524 assert( count <= CV_SET_ELEM_IDX_MASK+1 );
2525 ((CvSetElem*)(ptr - elem_size))->next_free = 0;
2526 set->first->prev->count += count - set->total;
2527 set->total = count;
2528 set->ptr = set->block_max;
2529 }
2530
2531 free_elem = set->free_elems;
2532 set->free_elems = free_elem->next_free;
2533
2534 id = free_elem->flags & CV_SET_ELEM_IDX_MASK;
2535 if( element )
2536 memcpy( free_elem, element, set->elem_size );
2537
2538 free_elem->flags = id;
2539 set->active_count++;
2540
2541 if( inserted_element )
2542 *inserted_element = free_elem;
2543
2544 return id;
2545 }
2546
2547
2548 /* Remove element from a set given element index: */
2549 CV_IMPL void
cvSetRemove(CvSet * set,int index)2550 cvSetRemove( CvSet* set, int index )
2551 {
2552 CV_Assert(set != NULL);
2553 CvSetElem* elem = cvGetSetElem( set, index );
2554 if( elem )
2555 cvSetRemoveByPtr( set, elem );
2556 else if( !set )
2557 CV_Error( CV_StsNullPtr, "" );
2558 }
2559
2560
2561 /* Remove all elements from a set: */
2562 CV_IMPL void
cvClearSet(CvSet * set)2563 cvClearSet( CvSet* set )
2564 {
2565 cvClearSeq( (CvSeq*)set );
2566 set->free_elems = 0;
2567 set->active_count = 0;
2568 }
2569
2570
2571 /****************************************************************************************\
2572 * Graph implementation *
2573 \****************************************************************************************/
2574
2575 /* Create a new graph: */
2576 CV_IMPL CvGraph *
cvCreateGraph(int graph_type,int header_size,int vtx_size,int edge_size,CvMemStorage * storage)2577 cvCreateGraph( int graph_type, int header_size,
2578 int vtx_size, int edge_size, CvMemStorage * storage )
2579 {
2580 CvGraph *graph = 0;
2581 CvSet *edges = 0;
2582 CvSet *vertices = 0;
2583
2584 if( header_size < (int) sizeof( CvGraph )
2585 || edge_size < (int) sizeof( CvGraphEdge )
2586 || vtx_size < (int) sizeof( CvGraphVtx )
2587 ){
2588 CV_Error( CV_StsBadSize, "" );
2589 }
2590
2591 vertices = cvCreateSet( graph_type, header_size, vtx_size, storage );
2592 edges = cvCreateSet( CV_SEQ_KIND_GENERIC | CV_SEQ_ELTYPE_GRAPH_EDGE,
2593 sizeof( CvSet ), edge_size, storage );
2594
2595 graph = (CvGraph*)vertices;
2596 graph->edges = edges;
2597
2598 return graph;
2599 }
2600
2601
2602 /* Remove all vertices and edges from a graph: */
2603 CV_IMPL void
cvClearGraph(CvGraph * graph)2604 cvClearGraph( CvGraph * graph )
2605 {
2606 if( !graph )
2607 CV_Error( CV_StsNullPtr, "" );
2608
2609 cvClearSet( graph->edges );
2610 cvClearSet( (CvSet*)graph );
2611 }
2612
2613
2614 /* Add a vertex to a graph: */
2615 CV_IMPL int
cvGraphAddVtx(CvGraph * graph,const CvGraphVtx * _vertex,CvGraphVtx ** _inserted_vertex)2616 cvGraphAddVtx( CvGraph* graph, const CvGraphVtx* _vertex, CvGraphVtx** _inserted_vertex )
2617 {
2618 CvGraphVtx *vertex = 0;
2619 int index = -1;
2620
2621 if( !graph )
2622 CV_Error( CV_StsNullPtr, "" );
2623
2624 vertex = (CvGraphVtx*)cvSetNew((CvSet*)graph);
2625 if( vertex )
2626 {
2627 if( _vertex )
2628 memcpy( vertex + 1, _vertex + 1, graph->elem_size - sizeof(CvGraphVtx) );
2629 vertex->first = 0;
2630 index = vertex->flags;
2631 }
2632
2633 if( _inserted_vertex )
2634 *_inserted_vertex = vertex;
2635
2636 return index;
2637 }
2638
2639
2640 /* Remove a vertex from the graph together with its incident edges: */
2641 CV_IMPL int
cvGraphRemoveVtxByPtr(CvGraph * graph,CvGraphVtx * vtx)2642 cvGraphRemoveVtxByPtr( CvGraph* graph, CvGraphVtx* vtx )
2643 {
2644 int count = -1;
2645
2646 if( !graph || !vtx )
2647 CV_Error( CV_StsNullPtr, "" );
2648
2649 if( !CV_IS_SET_ELEM(vtx))
2650 CV_Error( CV_StsBadArg, "The vertex does not belong to the graph" );
2651
2652 count = graph->edges->active_count;
2653 for( ;; )
2654 {
2655 CvGraphEdge *edge = vtx->first;
2656 if( !edge )
2657 break;
2658 cvGraphRemoveEdgeByPtr( graph, edge->vtx[0], edge->vtx[1] );
2659 }
2660 count -= graph->edges->active_count;
2661 cvSetRemoveByPtr( (CvSet*)graph, vtx );
2662
2663 return count;
2664 }
2665
2666
2667 /* Remove a vertex from the graph together with its incident edges: */
2668 CV_IMPL int
cvGraphRemoveVtx(CvGraph * graph,int index)2669 cvGraphRemoveVtx( CvGraph* graph, int index )
2670 {
2671 int count = -1;
2672 CvGraphVtx *vtx = 0;
2673
2674 if( !graph )
2675 CV_Error( CV_StsNullPtr, "" );
2676
2677 vtx = cvGetGraphVtx( graph, index );
2678 if( !vtx )
2679 CV_Error( CV_StsBadArg, "The vertex is not found" );
2680
2681 count = graph->edges->active_count;
2682 for( ;; )
2683 {
2684 CvGraphEdge *edge = vtx->first;
2685 count++;
2686
2687 if( !edge )
2688 break;
2689 cvGraphRemoveEdgeByPtr( graph, edge->vtx[0], edge->vtx[1] );
2690 }
2691 count -= graph->edges->active_count;
2692 cvSetRemoveByPtr( (CvSet*)graph, vtx );
2693
2694 return count;
2695 }
2696
2697
2698 /* Find a graph edge given pointers to the ending vertices: */
2699 CV_IMPL CvGraphEdge*
cvFindGraphEdgeByPtr(const CvGraph * graph,const CvGraphVtx * start_vtx,const CvGraphVtx * end_vtx)2700 cvFindGraphEdgeByPtr( const CvGraph* graph,
2701 const CvGraphVtx* start_vtx,
2702 const CvGraphVtx* end_vtx )
2703 {
2704 int ofs = 0;
2705
2706 if( !graph || !start_vtx || !end_vtx )
2707 CV_Error( CV_StsNullPtr, "" );
2708
2709 if( start_vtx == end_vtx )
2710 return 0;
2711
2712 if( !CV_IS_GRAPH_ORIENTED( graph ) &&
2713 (start_vtx->flags & CV_SET_ELEM_IDX_MASK) > (end_vtx->flags & CV_SET_ELEM_IDX_MASK) )
2714 {
2715 const CvGraphVtx* t;
2716 CV_SWAP( start_vtx, end_vtx, t );
2717 }
2718
2719 CvGraphEdge* edge = start_vtx->first;
2720 for( ; edge; edge = edge->next[ofs] )
2721 {
2722 ofs = start_vtx == edge->vtx[1];
2723 assert( ofs == 1 || start_vtx == edge->vtx[0] );
2724 if( edge->vtx[1] == end_vtx )
2725 break;
2726 }
2727
2728 return edge;
2729 }
2730
2731
2732 /* Find an edge in the graph given indices of the ending vertices: */
2733 CV_IMPL CvGraphEdge *
cvFindGraphEdge(const CvGraph * graph,int start_idx,int end_idx)2734 cvFindGraphEdge( const CvGraph* graph, int start_idx, int end_idx )
2735 {
2736 CvGraphVtx *start_vtx;
2737 CvGraphVtx *end_vtx;
2738
2739 if( !graph )
2740 CV_Error( CV_StsNullPtr, "graph pointer is NULL" );
2741
2742 start_vtx = cvGetGraphVtx( graph, start_idx );
2743 end_vtx = cvGetGraphVtx( graph, end_idx );
2744
2745 return cvFindGraphEdgeByPtr( graph, start_vtx, end_vtx );
2746 }
2747
2748
2749 /* Given two vertices, return the edge
2750 * connecting them, creating it if it
2751 * did not already exist:
2752 */
2753 CV_IMPL int
cvGraphAddEdgeByPtr(CvGraph * graph,CvGraphVtx * start_vtx,CvGraphVtx * end_vtx,const CvGraphEdge * _edge,CvGraphEdge ** _inserted_edge)2754 cvGraphAddEdgeByPtr( CvGraph* graph,
2755 CvGraphVtx* start_vtx, CvGraphVtx* end_vtx,
2756 const CvGraphEdge* _edge,
2757 CvGraphEdge ** _inserted_edge )
2758 {
2759 CvGraphEdge *edge = 0;
2760 int result = -1;
2761 int delta;
2762
2763 if( !graph )
2764 CV_Error( CV_StsNullPtr, "graph pointer is NULL" );
2765
2766 if( !CV_IS_GRAPH_ORIENTED( graph ) &&
2767 (start_vtx->flags & CV_SET_ELEM_IDX_MASK) > (end_vtx->flags & CV_SET_ELEM_IDX_MASK) )
2768 {
2769 CvGraphVtx* t;
2770 CV_SWAP( start_vtx, end_vtx, t );
2771 }
2772
2773 edge = cvFindGraphEdgeByPtr( graph, start_vtx, end_vtx );
2774 if( edge )
2775 {
2776 result = 0;
2777 if( _inserted_edge )
2778 *_inserted_edge = edge;
2779 return result;
2780 }
2781
2782 if( start_vtx == end_vtx )
2783 CV_Error( start_vtx ? CV_StsBadArg : CV_StsNullPtr,
2784 "vertex pointers coincide (or set to NULL)" );
2785
2786 edge = (CvGraphEdge*)cvSetNew( (CvSet*)(graph->edges) );
2787 assert( edge->flags >= 0 );
2788
2789 edge->vtx[0] = start_vtx;
2790 edge->vtx[1] = end_vtx;
2791 edge->next[0] = start_vtx->first;
2792 edge->next[1] = end_vtx->first;
2793 start_vtx->first = end_vtx->first = edge;
2794
2795 delta = graph->edges->elem_size - sizeof(*edge);
2796 if( _edge )
2797 {
2798 if( delta > 0 )
2799 memcpy( edge + 1, _edge + 1, delta );
2800 edge->weight = _edge->weight;
2801 }
2802 else
2803 {
2804 if( delta > 0 )
2805 memset( edge + 1, 0, delta );
2806 edge->weight = 1.f;
2807 }
2808
2809 result = 1;
2810
2811 if( _inserted_edge )
2812 *_inserted_edge = edge;
2813
2814 return result;
2815 }
2816
2817 /* Given two vertices, return the edge
2818 * connecting them, creating it if it
2819 * did not already exist:
2820 */
2821 CV_IMPL int
cvGraphAddEdge(CvGraph * graph,int start_idx,int end_idx,const CvGraphEdge * _edge,CvGraphEdge ** _inserted_edge)2822 cvGraphAddEdge( CvGraph* graph,
2823 int start_idx, int end_idx,
2824 const CvGraphEdge* _edge,
2825 CvGraphEdge ** _inserted_edge )
2826 {
2827 CvGraphVtx *start_vtx;
2828 CvGraphVtx *end_vtx;
2829
2830 if( !graph )
2831 CV_Error( CV_StsNullPtr, "" );
2832
2833 start_vtx = cvGetGraphVtx( graph, start_idx );
2834 end_vtx = cvGetGraphVtx( graph, end_idx );
2835
2836 return cvGraphAddEdgeByPtr( graph, start_vtx, end_vtx, _edge, _inserted_edge );
2837 }
2838
2839
2840 /* Remove the graph edge connecting two given vertices: */
2841 CV_IMPL void
cvGraphRemoveEdgeByPtr(CvGraph * graph,CvGraphVtx * start_vtx,CvGraphVtx * end_vtx)2842 cvGraphRemoveEdgeByPtr( CvGraph* graph, CvGraphVtx* start_vtx, CvGraphVtx* end_vtx )
2843 {
2844 int ofs, prev_ofs;
2845 CvGraphEdge *edge, *next_edge, *prev_edge;
2846
2847 if( !graph || !start_vtx || !end_vtx )
2848 CV_Error( CV_StsNullPtr, "" );
2849
2850 if( start_vtx == end_vtx )
2851 return;
2852
2853 if( !CV_IS_GRAPH_ORIENTED( graph ) &&
2854 (start_vtx->flags & CV_SET_ELEM_IDX_MASK) > (end_vtx->flags & CV_SET_ELEM_IDX_MASK) )
2855 {
2856 CvGraphVtx* t;
2857 CV_SWAP( start_vtx, end_vtx, t );
2858 }
2859
2860 for( ofs = prev_ofs = 0, prev_edge = 0, edge = start_vtx->first; edge != 0;
2861 prev_ofs = ofs, prev_edge = edge, edge = edge->next[ofs] )
2862 {
2863 ofs = start_vtx == edge->vtx[1];
2864 assert( ofs == 1 || start_vtx == edge->vtx[0] );
2865 if( edge->vtx[1] == end_vtx )
2866 break;
2867 }
2868
2869 if( !edge )
2870 return;
2871
2872 next_edge = edge->next[ofs];
2873 if( prev_edge )
2874 prev_edge->next[prev_ofs] = next_edge;
2875 else
2876 start_vtx->first = next_edge;
2877
2878 for( ofs = prev_ofs = 0, prev_edge = 0, edge = end_vtx->first; edge != 0;
2879 prev_ofs = ofs, prev_edge = edge, edge = edge->next[ofs] )
2880 {
2881 ofs = end_vtx == edge->vtx[1];
2882 assert( ofs == 1 || end_vtx == edge->vtx[0] );
2883 if( edge->vtx[0] == start_vtx )
2884 break;
2885 }
2886
2887 CV_Assert( edge != 0 );
2888
2889 next_edge = edge->next[ofs];
2890 if( prev_edge )
2891 prev_edge->next[prev_ofs] = next_edge;
2892 else
2893 end_vtx->first = next_edge;
2894
2895 cvSetRemoveByPtr( graph->edges, edge );
2896 }
2897
2898
2899 /* Remove the graph edge connecting two given vertices: */
2900 CV_IMPL void
cvGraphRemoveEdge(CvGraph * graph,int start_idx,int end_idx)2901 cvGraphRemoveEdge( CvGraph* graph, int start_idx, int end_idx )
2902 {
2903 CvGraphVtx *start_vtx;
2904 CvGraphVtx *end_vtx;
2905
2906 if( !graph )
2907 CV_Error( CV_StsNullPtr, "" );
2908
2909 start_vtx = cvGetGraphVtx( graph, start_idx );
2910 end_vtx = cvGetGraphVtx( graph, end_idx );
2911
2912 cvGraphRemoveEdgeByPtr( graph, start_vtx, end_vtx );
2913 }
2914
2915
2916 /* Count number of edges incident to a given vertex: */
2917 CV_IMPL int
cvGraphVtxDegreeByPtr(const CvGraph * graph,const CvGraphVtx * vertex)2918 cvGraphVtxDegreeByPtr( const CvGraph* graph, const CvGraphVtx* vertex )
2919 {
2920 CvGraphEdge *edge;
2921 int count;
2922
2923 if( !graph || !vertex )
2924 CV_Error( CV_StsNullPtr, "" );
2925
2926 for( edge = vertex->first, count = 0; edge; )
2927 {
2928 count++;
2929 edge = CV_NEXT_GRAPH_EDGE( edge, vertex );
2930 }
2931
2932 return count;
2933 }
2934
2935
2936 /* Count number of edges incident to a given vertex: */
2937 CV_IMPL int
cvGraphVtxDegree(const CvGraph * graph,int vtx_idx)2938 cvGraphVtxDegree( const CvGraph* graph, int vtx_idx )
2939 {
2940 CvGraphVtx *vertex;
2941 CvGraphEdge *edge;
2942 int count;
2943
2944 if( !graph )
2945 CV_Error( CV_StsNullPtr, "" );
2946
2947 vertex = cvGetGraphVtx( graph, vtx_idx );
2948 if( !vertex )
2949 CV_Error( CV_StsObjectNotFound, "" );
2950
2951 for( edge = vertex->first, count = 0; edge; )
2952 {
2953 count++;
2954 edge = CV_NEXT_GRAPH_EDGE( edge, vertex );
2955 }
2956
2957 return count;
2958 }
2959
2960
2961 typedef struct CvGraphItem
2962 {
2963 CvGraphVtx* vtx;
2964 CvGraphEdge* edge;
2965 }
2966 CvGraphItem;
2967
2968
2969 static void
icvSeqElemsClearFlags(CvSeq * seq,int offset,int clear_mask)2970 icvSeqElemsClearFlags( CvSeq* seq, int offset, int clear_mask )
2971 {
2972 CvSeqReader reader;
2973 int i, total, elem_size;
2974
2975 if( !seq )
2976 CV_Error( CV_StsNullPtr, "" );
2977
2978 elem_size = seq->elem_size;
2979 total = seq->total;
2980
2981 if( (unsigned)offset > (unsigned)elem_size )
2982 CV_Error( CV_StsBadArg, "" );
2983
2984 cvStartReadSeq( seq, &reader );
2985
2986 for( i = 0; i < total; i++ )
2987 {
2988 int* flag_ptr = (int*)(reader.ptr + offset);
2989 *flag_ptr &= ~clear_mask;
2990
2991 CV_NEXT_SEQ_ELEM( elem_size, reader );
2992 }
2993 }
2994
2995
2996 static schar*
icvSeqFindNextElem(CvSeq * seq,int offset,int mask,int value,int * start_index)2997 icvSeqFindNextElem( CvSeq* seq, int offset, int mask,
2998 int value, int* start_index )
2999 {
3000 schar* elem_ptr = 0;
3001
3002 CvSeqReader reader;
3003 int total, elem_size, index;
3004
3005 if( !seq || !start_index )
3006 CV_Error( CV_StsNullPtr, "" );
3007
3008 elem_size = seq->elem_size;
3009 total = seq->total;
3010 index = *start_index;
3011
3012 if( (unsigned)offset > (unsigned)elem_size )
3013 CV_Error( CV_StsBadArg, "" );
3014
3015 if( total == 0 )
3016 return 0;
3017
3018 if( (unsigned)index >= (unsigned)total )
3019 {
3020 index %= total;
3021 index += index < 0 ? total : 0;
3022 }
3023
3024 cvStartReadSeq( seq, &reader );
3025
3026 if( index != 0 )
3027 cvSetSeqReaderPos( &reader, index );
3028
3029 for( index = 0; index < total; index++ )
3030 {
3031 int* flag_ptr = (int*)(reader.ptr + offset);
3032 if( (*flag_ptr & mask) == value )
3033 break;
3034
3035 CV_NEXT_SEQ_ELEM( elem_size, reader );
3036 }
3037
3038 if( index < total )
3039 {
3040 elem_ptr = reader.ptr;
3041 *start_index = index;
3042 }
3043
3044 return elem_ptr;
3045 }
3046
3047 #define CV_FIELD_OFFSET( field, structtype ) ((int)(size_t)&((structtype*)0)->field)
3048
3049 CV_IMPL CvGraphScanner*
cvCreateGraphScanner(CvGraph * graph,CvGraphVtx * vtx,int mask)3050 cvCreateGraphScanner( CvGraph* graph, CvGraphVtx* vtx, int mask )
3051 {
3052 if( !graph )
3053 CV_Error( CV_StsNullPtr, "Null graph pointer" );
3054
3055 CV_Assert( graph->storage != 0 );
3056
3057 CvGraphScanner* scanner = (CvGraphScanner*)cvAlloc( sizeof(*scanner) );
3058 memset( scanner, 0, sizeof(*scanner));
3059
3060 scanner->graph = graph;
3061 scanner->mask = mask;
3062 scanner->vtx = vtx;
3063 scanner->index = vtx == 0 ? 0 : -1;
3064
3065 CvMemStorage* child_storage = cvCreateChildMemStorage( graph->storage );
3066
3067 scanner->stack = cvCreateSeq( 0, sizeof(CvSet),
3068 sizeof(CvGraphItem), child_storage );
3069
3070 icvSeqElemsClearFlags( (CvSeq*)graph,
3071 CV_FIELD_OFFSET( flags, CvGraphVtx),
3072 CV_GRAPH_ITEM_VISITED_FLAG|
3073 CV_GRAPH_SEARCH_TREE_NODE_FLAG );
3074
3075 icvSeqElemsClearFlags( (CvSeq*)(graph->edges),
3076 CV_FIELD_OFFSET( flags, CvGraphEdge),
3077 CV_GRAPH_ITEM_VISITED_FLAG );
3078
3079 return scanner;
3080 }
3081
3082
3083 CV_IMPL void
cvReleaseGraphScanner(CvGraphScanner ** scanner)3084 cvReleaseGraphScanner( CvGraphScanner** scanner )
3085 {
3086 if( !scanner )
3087 CV_Error( CV_StsNullPtr, "Null double pointer to graph scanner" );
3088
3089 if( *scanner )
3090 {
3091 if( (*scanner)->stack )
3092 cvReleaseMemStorage( &((*scanner)->stack->storage));
3093 cvFree( scanner );
3094 }
3095 }
3096
3097
3098 CV_IMPL int
cvNextGraphItem(CvGraphScanner * scanner)3099 cvNextGraphItem( CvGraphScanner* scanner )
3100 {
3101 int code = -1;
3102 CvGraphVtx* vtx;
3103 CvGraphVtx* dst;
3104 CvGraphEdge* edge;
3105 CvGraphItem item;
3106
3107 if( !scanner || !(scanner->stack))
3108 CV_Error( CV_StsNullPtr, "Null graph scanner" );
3109
3110 dst = scanner->dst;
3111 vtx = scanner->vtx;
3112 edge = scanner->edge;
3113
3114 for(;;)
3115 {
3116 for(;;)
3117 {
3118 if( dst && !CV_IS_GRAPH_VERTEX_VISITED(dst) )
3119 {
3120 scanner->vtx = vtx = dst;
3121 edge = vtx->first;
3122 dst->flags |= CV_GRAPH_ITEM_VISITED_FLAG;
3123
3124 if((scanner->mask & CV_GRAPH_VERTEX))
3125 {
3126 scanner->vtx = vtx;
3127 scanner->edge = vtx->first;
3128 scanner->dst = 0;
3129 code = CV_GRAPH_VERTEX;
3130 return code;
3131 }
3132 }
3133
3134 while( edge )
3135 {
3136 dst = edge->vtx[vtx == edge->vtx[0]];
3137
3138 if( !CV_IS_GRAPH_EDGE_VISITED(edge) )
3139 {
3140 // Check that the edge is outgoing:
3141 if( !CV_IS_GRAPH_ORIENTED( scanner->graph ) || dst != edge->vtx[0] )
3142 {
3143 edge->flags |= CV_GRAPH_ITEM_VISITED_FLAG;
3144
3145 if( !CV_IS_GRAPH_VERTEX_VISITED(dst) )
3146 {
3147 item.vtx = vtx;
3148 item.edge = edge;
3149
3150 vtx->flags |= CV_GRAPH_SEARCH_TREE_NODE_FLAG;
3151
3152 cvSeqPush( scanner->stack, &item );
3153
3154 if( scanner->mask & CV_GRAPH_TREE_EDGE )
3155 {
3156 code = CV_GRAPH_TREE_EDGE;
3157 scanner->vtx = vtx;
3158 scanner->dst = dst;
3159 scanner->edge = edge;
3160 return code;
3161 }
3162 break;
3163 }
3164 else
3165 {
3166 if( scanner->mask & (CV_GRAPH_BACK_EDGE|
3167 CV_GRAPH_CROSS_EDGE|
3168 CV_GRAPH_FORWARD_EDGE) )
3169 {
3170 code = (dst->flags & CV_GRAPH_SEARCH_TREE_NODE_FLAG) ?
3171 CV_GRAPH_BACK_EDGE :
3172 (edge->flags & CV_GRAPH_FORWARD_EDGE_FLAG) ?
3173 CV_GRAPH_FORWARD_EDGE : CV_GRAPH_CROSS_EDGE;
3174 edge->flags &= ~CV_GRAPH_FORWARD_EDGE_FLAG;
3175 if( scanner->mask & code )
3176 {
3177 scanner->vtx = vtx;
3178 scanner->dst = dst;
3179 scanner->edge = edge;
3180 return code;
3181 }
3182 }
3183 }
3184 }
3185 else if( (dst->flags & (CV_GRAPH_ITEM_VISITED_FLAG|
3186 CV_GRAPH_SEARCH_TREE_NODE_FLAG)) ==
3187 (CV_GRAPH_ITEM_VISITED_FLAG|
3188 CV_GRAPH_SEARCH_TREE_NODE_FLAG))
3189 {
3190 edge->flags |= CV_GRAPH_FORWARD_EDGE_FLAG;
3191 }
3192 }
3193
3194 edge = CV_NEXT_GRAPH_EDGE( edge, vtx );
3195 }
3196
3197 if( !edge ) /* need to backtrack */
3198 {
3199 if( scanner->stack->total == 0 )
3200 {
3201 if( scanner->index >= 0 )
3202 vtx = 0;
3203 else
3204 scanner->index = 0;
3205 break;
3206 }
3207 cvSeqPop( scanner->stack, &item );
3208 vtx = item.vtx;
3209 vtx->flags &= ~CV_GRAPH_SEARCH_TREE_NODE_FLAG;
3210 edge = item.edge;
3211 dst = 0;
3212
3213 if( scanner->mask & CV_GRAPH_BACKTRACKING )
3214 {
3215 scanner->vtx = vtx;
3216 scanner->edge = edge;
3217 scanner->dst = edge->vtx[vtx == edge->vtx[0]];
3218 code = CV_GRAPH_BACKTRACKING;
3219 return code;
3220 }
3221 }
3222 }
3223
3224 if( !vtx )
3225 {
3226 vtx = (CvGraphVtx*)icvSeqFindNextElem( (CvSeq*)(scanner->graph),
3227 CV_FIELD_OFFSET( flags, CvGraphVtx ), CV_GRAPH_ITEM_VISITED_FLAG|INT_MIN,
3228 0, &(scanner->index) );
3229
3230 if( !vtx )
3231 {
3232 code = CV_GRAPH_OVER;
3233 break;
3234 }
3235 }
3236
3237 dst = vtx;
3238 if( scanner->mask & CV_GRAPH_NEW_TREE )
3239 {
3240 scanner->dst = dst;
3241 scanner->edge = 0;
3242 scanner->vtx = 0;
3243 code = CV_GRAPH_NEW_TREE;
3244 break;
3245 }
3246 }
3247
3248 return code;
3249 }
3250
3251
3252 CV_IMPL CvGraph*
cvCloneGraph(const CvGraph * graph,CvMemStorage * storage)3253 cvCloneGraph( const CvGraph* graph, CvMemStorage* storage )
3254 {
3255 int* flag_buffer = 0;
3256 CvGraphVtx** ptr_buffer = 0;
3257 CvGraph* result = 0;
3258
3259 int i, k;
3260 int vtx_size, edge_size;
3261 CvSeqReader reader;
3262
3263 if( !CV_IS_GRAPH(graph))
3264 CV_Error( CV_StsBadArg, "Invalid graph pointer" );
3265
3266 if( !storage )
3267 storage = graph->storage;
3268
3269 if( !storage )
3270 CV_Error( CV_StsNullPtr, "NULL storage pointer" );
3271
3272 vtx_size = graph->elem_size;
3273 edge_size = graph->edges->elem_size;
3274
3275 flag_buffer = (int*)cvAlloc( graph->total*sizeof(flag_buffer[0]));
3276 ptr_buffer = (CvGraphVtx**)cvAlloc( graph->total*sizeof(ptr_buffer[0]));
3277 result = cvCreateGraph( graph->flags, graph->header_size,
3278 vtx_size, edge_size, storage );
3279 memcpy( result + sizeof(CvGraph), graph + sizeof(CvGraph),
3280 graph->header_size - sizeof(CvGraph));
3281
3282 // Pass 1. Save flags, copy vertices:
3283 cvStartReadSeq( (CvSeq*)graph, &reader );
3284 for( i = 0, k = 0; i < graph->total; i++ )
3285 {
3286 if( CV_IS_SET_ELEM( reader.ptr ))
3287 {
3288 CvGraphVtx* vtx = (CvGraphVtx*)reader.ptr;
3289 CvGraphVtx* dstvtx = 0;
3290 cvGraphAddVtx( result, vtx, &dstvtx );
3291 flag_buffer[k] = dstvtx->flags = vtx->flags;
3292 vtx->flags = k;
3293 ptr_buffer[k++] = dstvtx;
3294 }
3295 CV_NEXT_SEQ_ELEM( vtx_size, reader );
3296 }
3297
3298 // Pass 2. Copy edges:
3299 cvStartReadSeq( (CvSeq*)graph->edges, &reader );
3300 for( i = 0; i < graph->edges->total; i++ )
3301 {
3302 if( CV_IS_SET_ELEM( reader.ptr ))
3303 {
3304 CvGraphEdge* edge = (CvGraphEdge*)reader.ptr;
3305 CvGraphEdge* dstedge = 0;
3306 CvGraphVtx* new_org = ptr_buffer[edge->vtx[0]->flags];
3307 CvGraphVtx* new_dst = ptr_buffer[edge->vtx[1]->flags];
3308 cvGraphAddEdgeByPtr( result, new_org, new_dst, edge, &dstedge );
3309 dstedge->flags = edge->flags;
3310 }
3311 CV_NEXT_SEQ_ELEM( edge_size, reader );
3312 }
3313
3314 // Pass 3. Restore flags:
3315 cvStartReadSeq( (CvSeq*)graph, &reader );
3316 for( i = 0, k = 0; i < graph->edges->total; i++ )
3317 {
3318 if( CV_IS_SET_ELEM( reader.ptr ))
3319 {
3320 CvGraphVtx* vtx = (CvGraphVtx*)reader.ptr;
3321 vtx->flags = flag_buffer[k++];
3322 }
3323 CV_NEXT_SEQ_ELEM( vtx_size, reader );
3324 }
3325
3326 cvFree( &flag_buffer );
3327 cvFree( &ptr_buffer );
3328
3329 if( cvGetErrStatus() < 0 )
3330 result = 0;
3331
3332 return result;
3333 }
3334
3335
3336 /****************************************************************************************\
3337 * Working with sequence tree *
3338 \****************************************************************************************/
3339
3340 // Gather pointers to all the sequences, accessible from the <first>, to the single sequence.
3341 CV_IMPL CvSeq*
cvTreeToNodeSeq(const void * first,int header_size,CvMemStorage * storage)3342 cvTreeToNodeSeq( const void* first, int header_size, CvMemStorage* storage )
3343 {
3344 CvSeq* allseq = 0;
3345 CvTreeNodeIterator iterator;
3346
3347 if( !storage )
3348 CV_Error( CV_StsNullPtr, "NULL storage pointer" );
3349
3350 allseq = cvCreateSeq( 0, header_size, sizeof(first), storage );
3351
3352 if( first )
3353 {
3354 cvInitTreeNodeIterator( &iterator, first, INT_MAX );
3355
3356 for(;;)
3357 {
3358 void* node = cvNextTreeNode( &iterator );
3359 if( !node )
3360 break;
3361 cvSeqPush( allseq, &node );
3362 }
3363 }
3364
3365
3366
3367 return allseq;
3368 }
3369
3370
3371 typedef struct CvTreeNode
3372 {
3373 int flags; /* miscellaneous flags */
3374 int header_size; /* size of sequence header */
3375 struct CvTreeNode* h_prev; /* previous sequence */
3376 struct CvTreeNode* h_next; /* next sequence */
3377 struct CvTreeNode* v_prev; /* 2nd previous sequence */
3378 struct CvTreeNode* v_next; /* 2nd next sequence */
3379 }
3380 CvTreeNode;
3381
3382
3383
3384 // Insert contour into tree given certain parent sequence.
3385 // If parent is equal to frame (the most external contour),
3386 // then added contour will have null pointer to parent:
3387 CV_IMPL void
cvInsertNodeIntoTree(void * _node,void * _parent,void * _frame)3388 cvInsertNodeIntoTree( void* _node, void* _parent, void* _frame )
3389 {
3390 CvTreeNode* node = (CvTreeNode*)_node;
3391 CvTreeNode* parent = (CvTreeNode*)_parent;
3392
3393 if( !node || !parent )
3394 CV_Error( CV_StsNullPtr, "" );
3395
3396 node->v_prev = _parent != _frame ? parent : 0;
3397 node->h_next = parent->v_next;
3398
3399 assert( parent->v_next != node );
3400
3401 if( parent->v_next )
3402 parent->v_next->h_prev = node;
3403 parent->v_next = node;
3404 }
3405
3406
3407 // Remove contour from tree, together with the contour's children:
3408 CV_IMPL void
cvRemoveNodeFromTree(void * _node,void * _frame)3409 cvRemoveNodeFromTree( void* _node, void* _frame )
3410 {
3411 CvTreeNode* node = (CvTreeNode*)_node;
3412 CvTreeNode* frame = (CvTreeNode*)_frame;
3413
3414 if( !node )
3415 CV_Error( CV_StsNullPtr, "" );
3416
3417 if( node == frame )
3418 CV_Error( CV_StsBadArg, "frame node could not be deleted" );
3419
3420 if( node->h_next )
3421 node->h_next->h_prev = node->h_prev;
3422
3423 if( node->h_prev )
3424 node->h_prev->h_next = node->h_next;
3425 else
3426 {
3427 CvTreeNode* parent = node->v_prev;
3428 if( !parent )
3429 parent = frame;
3430
3431 if( parent )
3432 {
3433 assert( parent->v_next == node );
3434 parent->v_next = node->h_next;
3435 }
3436 }
3437 }
3438
3439
3440 CV_IMPL void
cvInitTreeNodeIterator(CvTreeNodeIterator * treeIterator,const void * first,int max_level)3441 cvInitTreeNodeIterator( CvTreeNodeIterator* treeIterator,
3442 const void* first, int max_level )
3443 {
3444 if( !treeIterator || !first )
3445 CV_Error( CV_StsNullPtr, "" );
3446
3447 if( max_level < 0 )
3448 CV_Error( CV_StsOutOfRange, "" );
3449
3450 treeIterator->node = (void*)first;
3451 treeIterator->level = 0;
3452 treeIterator->max_level = max_level;
3453 }
3454
3455
3456 CV_IMPL void*
cvNextTreeNode(CvTreeNodeIterator * treeIterator)3457 cvNextTreeNode( CvTreeNodeIterator* treeIterator )
3458 {
3459 CvTreeNode* prevNode = 0;
3460 CvTreeNode* node;
3461 int level;
3462
3463 if( !treeIterator )
3464 CV_Error( CV_StsNullPtr, "NULL iterator pointer" );
3465
3466 prevNode = node = (CvTreeNode*)treeIterator->node;
3467 level = treeIterator->level;
3468
3469 if( node )
3470 {
3471 if( node->v_next && level+1 < treeIterator->max_level )
3472 {
3473 node = node->v_next;
3474 level++;
3475 }
3476 else
3477 {
3478 while( node->h_next == 0 )
3479 {
3480 node = node->v_prev;
3481 if( --level < 0 )
3482 {
3483 node = 0;
3484 break;
3485 }
3486 }
3487 node = node && treeIterator->max_level != 0 ? node->h_next : 0;
3488 }
3489 }
3490
3491 treeIterator->node = node;
3492 treeIterator->level = level;
3493 return prevNode;
3494 }
3495
3496
3497 CV_IMPL void*
cvPrevTreeNode(CvTreeNodeIterator * treeIterator)3498 cvPrevTreeNode( CvTreeNodeIterator* treeIterator )
3499 {
3500 CvTreeNode* prevNode = 0;
3501 CvTreeNode* node;
3502 int level;
3503
3504 if( !treeIterator )
3505 CV_Error( CV_StsNullPtr, "" );
3506
3507 prevNode = node = (CvTreeNode*)treeIterator->node;
3508 level = treeIterator->level;
3509
3510 if( node )
3511 {
3512 if( !node->h_prev )
3513 {
3514 node = node->v_prev;
3515 if( --level < 0 )
3516 node = 0;
3517 }
3518 else
3519 {
3520 node = node->h_prev;
3521
3522 while( node->v_next && level < treeIterator->max_level )
3523 {
3524 node = node->v_next;
3525 level++;
3526
3527 while( node->h_next )
3528 node = node->h_next;
3529 }
3530 }
3531 }
3532
3533 treeIterator->node = node;
3534 treeIterator->level = level;
3535 return prevNode;
3536 }
3537
3538 namespace cv
3539 {
3540
3541 ////////////////////////////////////////////////////////////////////////////////
3542
seqPush(CvSeq * seq,const void * element)3543 schar* seqPush( CvSeq* seq, const void* element )
3544 {
3545 return cvSeqPush(seq, element);
3546 }
3547
seqPushFront(CvSeq * seq,const void * element)3548 schar* seqPushFront( CvSeq* seq, const void* element )
3549 {
3550 return cvSeqPushFront(seq, element);
3551 }
3552
seqPop(CvSeq * seq,void * element)3553 void seqPop( CvSeq* seq, void* element )
3554 {
3555 cvSeqPop(seq, element);
3556 }
3557
seqPopFront(CvSeq * seq,void * element)3558 void seqPopFront( CvSeq* seq, void* element )
3559 {
3560 cvSeqPopFront(seq, element);
3561 }
3562
seqRemove(CvSeq * seq,int index)3563 void seqRemove( CvSeq* seq, int index )
3564 {
3565 cvSeqRemove(seq, index);
3566 }
3567
clearSeq(CvSeq * seq)3568 void clearSeq( CvSeq* seq )
3569 {
3570 cvClearSeq(seq);
3571 }
3572
getSeqElem(const CvSeq * seq,int index)3573 schar* getSeqElem( const CvSeq* seq, int index )
3574 {
3575 return cvGetSeqElem(seq, index);
3576 }
3577
seqRemoveSlice(CvSeq * seq,CvSlice slice)3578 void seqRemoveSlice( CvSeq* seq, CvSlice slice )
3579 {
3580 return cvSeqRemoveSlice(seq, slice);
3581 }
3582
seqInsertSlice(CvSeq * seq,int before_index,const CvArr * from_arr)3583 void seqInsertSlice( CvSeq* seq, int before_index, const CvArr* from_arr )
3584 {
3585 cvSeqInsertSlice(seq, before_index, from_arr);
3586 }
3587
3588 }
3589
3590 #endif // OPENCV_EXCLUDE_C_API
3591 /* End of file. */
3592