git.maemo.org Git - opencv/blob - tests/cxcore/src/adatastruct.cpp

   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
  42 //////////////////////////////////////////////////////////////////////////////////////////
  43 //////////////////// tests for operations on dynamic data structures /////////////////////
  44 //////////////////////////////////////////////////////////////////////////////////////////
  45
  46 #include "cxcoretest.h"
  47
  48 /****************************************************************************************\
  49 *                           simple sequence implementation                               *
  50 \****************************************************************************************/
  51
  52 typedef  struct  CvTsSimpleSeq
  53 {
  54     schar* array;
  55     int   count;
  56     int   max_count;
  57     int   elem_size;
  58 }
  59 CvTsSimpleSeq;
  60
  61
  62 static CvTsSimpleSeq*  cvTsCreateSimpleSeq( int max_count, int elem_size )
  63 {
  64     CvTsSimpleSeq* seq = (CvTsSimpleSeq*)cvAlloc( sizeof(*seq) + max_count * elem_size );
  65     seq->elem_size = elem_size;
  66     seq->max_count = max_count;
  67     seq->count = 0;
  68     seq->array = (schar*)(seq + 1);
  69     return seq;
  70 }
  71
  72
  73 static void cvTsReleaseSimpleSeq( CvTsSimpleSeq** seq )
  74 {
  75     cvFree( seq );
  76 }
  77
  78
  79 static schar*  cvTsSimpleSeqElem( CvTsSimpleSeq* seq, int index )
  80 {
  81     assert( 0 <= index && index < seq->count );
  82     return seq->array + index * seq->elem_size;
  83 }
  84
  85
  86 static void  cvTsClearSimpleSeq( CvTsSimpleSeq* seq )
  87 {
  88     seq->count = 0;
  89 }
  90
  91
  92 static void cvTsSimpleSeqShiftAndCopy( CvTsSimpleSeq* seq, int from_idx, int to_idx, void* elem=0 )
  93 {
  94     int elem_size = seq->elem_size;
  95
  96     if( from_idx == to_idx )
  97         return;
  98     assert( from_idx > to_idx && !elem || from_idx < to_idx && elem );
  99
 100     if( from_idx < seq->count )
 101     {
 102         memmove( seq->array + to_idx*elem_size, seq->array + from_idx*elem_size,
 103                  (seq->count - from_idx)*elem_size );
 104     }
 105     seq->count += to_idx - from_idx;
 106     if( elem && to_idx > from_idx )
 107         memcpy( seq->array + from_idx*elem_size, elem, (to_idx - from_idx)*elem_size );
 108 }
 109
 110 static void cvTsSimpleSeqInvert( CvTsSimpleSeq* seq )
 111 {
 112     int i, k, len = seq->count, elem_size = seq->elem_size;
 113     schar *data = seq->array, t;
 114
 115     for( i = 0; i < len/2; i++ )
 116     {
 117         schar* a = data + i*elem_size;
 118         schar* b = data + (len - i - 1)*elem_size;
 119         for( k = 0; k < elem_size; k++ )
 120             CV_SWAP( a[k], b[k], t );
 121     }
 122 }
 123
 124 /****************************************************************************************\
 125 *                                simple cvset implementation                               *
 126 \****************************************************************************************/
 127
 128 typedef  struct  CvTsSimpleSet
 129 {
 130     schar* array;
 131     int   count, max_count;
 132     int   elem_size;
 133     int*  free_stack;
 134     int   free_count;
 135 }
 136 CvTsSimpleSet;
 137
 138
 139 static void  cvTsClearSimpleSet( CvTsSimpleSet* set_header )
 140 {
 141     int i;
 142     int elem_size = set_header->elem_size;
 143
 144     for( i = 0; i < set_header->max_count; i++ )
 145     {
 146         set_header->array[i*elem_size] = 0;
 147         set_header->free_stack[i] = set_header->max_count - i - 1;
 148     }
 149     set_header->free_count = set_header->max_count;
 150     set_header->count = 0;
 151 }
 152
 153
 154 static CvTsSimpleSet*  cvTsCreateSimpleSet( int max_count, int elem_size )
 155 {
 156     CvTsSimpleSet* set_header = (CvTsSimpleSet*)cvAlloc( sizeof(*set_header) + max_count *
 157                                         (elem_size + 1 + sizeof(int)));
 158     set_header->elem_size = elem_size + 1;
 159     set_header->max_count = max_count;
 160     set_header->free_stack = (int*)(set_header + 1);
 161     set_header->array = (schar*)(set_header->free_stack + max_count);
 162
 163     cvTsClearSimpleSet( set_header );
 164     return set_header;
 165 }
 166
 167
 168 static void cvTsReleaseSimpleSet( CvTsSimpleSet** set_header )
 169 {
 170     cvFree( set_header );
 171 }
 172
 173
 174 static schar*  cvTsSimpleSetFind( CvTsSimpleSet* set_header, int index )
 175 {
 176     int idx = index * set_header->elem_size;
 177     assert( 0 <= index && index < set_header->max_count );
 178     return set_header->array[idx] ? set_header->array + idx + 1 : 0;
 179 }
 180
 181
 182 static int  cvTsSimpleSetAdd( CvTsSimpleSet* set_header, void* elem )
 183 {
 184     int idx, idx2;
 185     assert( set_header->free_count > 0 );
 186
 187     idx = set_header->free_stack[--set_header->free_count];
 188     idx2 = idx * set_header->elem_size;
 189     assert( set_header->array[idx2] == 0 );
 190     set_header->array[idx2] = 1;
 191     if( set_header->elem_size > 1 )
 192         memcpy( set_header->array + idx2 + 1, elem, set_header->elem_size - 1 );
 193     set_header->count = MAX( set_header->count, idx + 1 );
 194
 195     return idx;
 196 }
 197
 198
 199 static void  cvTsSimpleSetRemove( CvTsSimpleSet* set_header, int index )
 200 {
 201     assert( set_header->free_count < set_header->max_count &&
 202             0 <= index && index < set_header->max_count );
 203     assert( set_header->array[index * set_header->elem_size] == 1 );
 204
 205     set_header->free_stack[set_header->free_count++] = index;
 206     set_header->array[index * set_header->elem_size] = 0;
 207 }
 208
 209
 210 /****************************************************************************************\
 211 *                              simple graph implementation                               *
 212 \****************************************************************************************/
 213
 214 typedef  struct  CvTsSimpleGraph
 215 {
 216     char* matrix;
 217     int   edge_size;
 218     int   oriented;
 219     CvTsSimpleSet* vtx;
 220 }
 221 CvTsSimpleGraph;
 222
 223
 224 static void  cvTsClearSimpleGraph( CvTsSimpleGraph* graph )
 225 {
 226     int max_vtx_count = graph->vtx->max_count;
 227     cvTsClearSimpleSet( graph->vtx );
 228     memset( graph->matrix, 0, max_vtx_count * max_vtx_count * graph->edge_size );
 229 }
 230
 231
 232 static CvTsSimpleGraph*  cvTsCreateSimpleGraph( int max_vtx_count, int vtx_size,
 233                                                 int edge_size, int oriented )
 234 {
 235     CvTsSimpleGraph* graph;
 236
 237     assert( max_vtx_count > 1 && vtx_size >= 0 && edge_size >= 0 );
 238     graph = (CvTsSimpleGraph*)cvAlloc( sizeof(*graph) +
 239                   max_vtx_count * max_vtx_count * (edge_size + 1));
 240     graph->vtx = cvTsCreateSimpleSet( max_vtx_count, vtx_size );
 241     graph->edge_size = edge_size + 1;
 242     graph->matrix = (char*)(graph + 1);
 243     graph->oriented = oriented;
 244
 245     cvTsClearSimpleGraph( graph );
 246     return graph;
 247 }
 248
 249
 250 static void cvTsReleaseSimpleGraph( CvTsSimpleGraph** graph )
 251 {
 252     if( *graph )
 253     {
 254         cvTsReleaseSimpleSet( &(graph[0]->vtx) );
 255         cvFree( graph );
 256     }
 257 }
 258
 259
 260 static int  cvTsSimpleGraphAddVertex( CvTsSimpleGraph* graph, void* vertex )
 261 {
 262     return cvTsSimpleSetAdd( graph->vtx, vertex );
 263 }
 264
 265
 266 static void  cvTsSimpleGraphRemoveVertex( CvTsSimpleGraph* graph, int index )
 267 {
 268     int i, max_vtx_count = graph->vtx->max_count;
 269     int edge_size = graph->edge_size;
 270     cvTsSimpleSetRemove( graph->vtx, index );
 271
 272     /* remove all the corresponding edges */
 273     for( i = 0; i < max_vtx_count; i++ )
 274     {
 275         graph->matrix[(i*max_vtx_count + index)*edge_size] =
 276         graph->matrix[(index*max_vtx_count + i)*edge_size] = 0;
 277     }
 278 }
 279
 280
 281 static void cvTsSimpleGraphAddEdge( CvTsSimpleGraph* graph, int idx1, int idx2, void* edge )
 282 {
 283     int i, t, n = graph->oriented ? 1 : 2;
 284
 285     assert( cvTsSimpleSetFind( graph->vtx, idx1 ) &&
 286             cvTsSimpleSetFind( graph->vtx, idx2 ));
 287
 288     for( i = 0; i < n; i++ )
 289     {
 290         int ofs = (idx1*graph->vtx->max_count + idx2)*graph->edge_size;
 291         assert( graph->matrix[ofs] == 0 );
 292         graph->matrix[ofs] = 1;
 293         if( graph->edge_size > 1 )
 294             memcpy( graph->matrix + ofs + 1, edge, graph->edge_size - 1 );
 295
 296         CV_SWAP( idx1, idx2, t );
 297     }
 298 }
 299
 300
 301 static void  cvTsSimpleGraphRemoveEdge( CvTsSimpleGraph* graph, int idx1, int idx2 )
 302 {
 303     int i, t, n = graph->oriented ? 1 : 2;
 304
 305     assert( cvTsSimpleSetFind( graph->vtx, idx1 ) &&
 306             cvTsSimpleSetFind( graph->vtx, idx2 ));
 307
 308     for( i = 0; i < n; i++ )
 309     {
 310         int ofs = (idx1*graph->vtx->max_count + idx2)*graph->edge_size;
 311         assert( graph->matrix[ofs] == 1 );
 312         graph->matrix[ofs] = 0;
 313         CV_SWAP( idx1, idx2, t );
 314     }
 315 }
 316
 317
 318 static schar*  cvTsSimpleGraphFindVertex( CvTsSimpleGraph* graph, int index )
 319 {
 320     return cvTsSimpleSetFind( graph->vtx, index );
 321 }
 322
 323
 324 static char*  cvTsSimpleGraphFindEdge( CvTsSimpleGraph* graph, int idx1, int idx2 )
 325 {
 326     if( cvTsSimpleGraphFindVertex( graph, idx1 ) &&
 327         cvTsSimpleGraphFindVertex( graph, idx2 ))
 328     {
 329         char* edge = graph->matrix + (idx1 * graph->vtx->max_count + idx2)*graph->edge_size;
 330         if( edge[0] ) return edge + 1;
 331     }
 332     return 0;
 333 }
 334
 335
 336 static int  cvTsSimpleGraphVertexDegree( CvTsSimpleGraph* graph, int index )
 337 {
 338     int i, count = 0;
 339     int edge_size = graph->edge_size;
 340     int max_vtx_count = graph->vtx->max_count;
 341     assert( cvTsSimpleGraphFindVertex( graph, index ) != 0 );
 342
 343     for( i = 0; i < max_vtx_count; i++ )
 344     {
 345         count += graph->matrix[(i*max_vtx_count + index)*edge_size] +
 346                  graph->matrix[(index*max_vtx_count + i)*edge_size];
 347     }
 348
 349     if( !graph->oriented )
 350     {
 351         assert( count % 2 == 0 );
 352         count /= 2;
 353     }
 354     return count;
 355 }
 356
 357
 358 ///////////////////////////////////// the tests //////////////////////////////////
 359
 360 #define CV_TS_SEQ_CHECK_CONDITION( expr, err_msg )              \
 361     if( !(expr) )                                               \
 362     {                                                           \
 363         set_error_context( #expr, err_msg, cvFuncName );        \
 364         ts->set_failed_test_info( CvTS::FAIL_INVALID_OUTPUT );  \
 365         EXIT;                                                   \
 366     }
 367
 368 class CxCore_DynStructBaseTest : public CvTest
 369 {
 370 public:
 371     CxCore_DynStructBaseTest( const char* test_name, const char* test_funcs );
 372     virtual ~CxCore_DynStructBaseTest();
 373     int write_default_params(CvFileStorage* fs);
 374     bool can_do_fast_forward();
 375     void clear();
 376
 377 protected:
 378     int read_params( CvFileStorage* fs );
 379     void run_func(void);
 380     void set_error_context( const char* condition,
 381                            const char* err_msg,
 382                            const char* func_name );
 383     int test_seq_block_consistence( int _struct_idx, CvSeq* seq, int total );
 384     void update_progressbar();
 385
 386     int struct_count, max_struct_size, iterations, generations;
 387     int min_log_storage_block_size, max_log_storage_block_size;
 388     int min_log_elem_size, max_log_elem_size;
 389     int gen, struct_idx, iter;
 390     int test_progress;
 391     int64 start_time;
 392     double cpu_freq;
 393     void** cxcore_struct;
 394     void** simple_struct;
 395     CvMemStorage* storage;
 396 };
 397
 398
 399 CxCore_DynStructBaseTest::CxCore_DynStructBaseTest( const char* test_name, const char* test_funcs ):
 400     CvTest( test_name, test_funcs )
 401 {
 402     struct_count = 2;
 403     max_struct_size = 2000;
 404     min_log_storage_block_size = 7;
 405     max_log_storage_block_size = 12;
 406     min_log_elem_size = 0;
 407     max_log_elem_size = 8;
 408     generations = 10;
 409     iterations = max_struct_size*2;
 410     gen = struct_idx = iter = -1;
 411     test_progress = -1;
 412
 413     storage = 0;
 414     cxcore_struct = 0;
 415     simple_struct = 0;
 416 }
 417
 418
 419 CxCore_DynStructBaseTest::~CxCore_DynStructBaseTest()
 420 {
 421     clear();
 422 }
 423
 424
 425 void CxCore_DynStructBaseTest::run_func()
 426 {
 427 }
 428
 429 bool CxCore_DynStructBaseTest::can_do_fast_forward()
 430 {
 431     return false;
 432 }
 433
 434
 435 void CxCore_DynStructBaseTest::clear()
 436 {
 437     CvTest::clear();
 438     cvReleaseMemStorage( &storage );
 439     cvFree( &cxcore_struct );
 440     cvFree( &simple_struct );
 441 }
 442
 443
 444 int CxCore_DynStructBaseTest::write_default_params( CvFileStorage* fs )
 445 {
 446     write_param( fs, "struct_count", struct_count );
 447     write_param( fs, "max_struct_size", max_struct_size );
 448     write_param( fs, "generations", generations );
 449     write_param( fs, "iterations", iterations );
 450     write_param( fs, "min_log_storage_block_size", min_log_storage_block_size );
 451     write_param( fs, "max_log_storage_block_size", max_log_storage_block_size );
 452     write_param( fs, "min_log_elem_size", min_log_elem_size );
 453     write_param( fs, "max_log_elem_size", max_log_elem_size );
 454     return 0;
 455 }
 456
 457
 458 int CxCore_DynStructBaseTest::read_params( CvFileStorage* fs )
 459 {
 460     int code = CvTest::read_params( fs );
 461     double sqrt_scale = sqrt(ts->get_test_case_count_scale());
 462     if( code < 0 )
 463         return code;
 464
 465     struct_count = cvReadInt( find_param( fs, "struct_count" ), struct_count );
 466     max_struct_size = cvReadInt( find_param( fs, "max_struct_size" ), max_struct_size );
 467     generations = cvReadInt( find_param( fs, "generations" ), generations );
 468     iterations = cvReadInt( find_param( fs, "iterations" ), iterations );
 469     generations = cvRound(generations*sqrt_scale);
 470     iterations = cvRound(iterations*sqrt_scale);
 471
 472     min_log_storage_block_size = cvReadInt( find_param( fs, "min_log_storage_block_size" ),
 473                                             min_log_storage_block_size );
 474     max_log_storage_block_size = cvReadInt( find_param( fs, "max_log_storage_block_size" ),
 475                                             max_log_storage_block_size );
 476     min_log_elem_size = cvReadInt( find_param( fs, "min_log_elem_size" ), min_log_elem_size );
 477     max_log_elem_size = cvReadInt( find_param( fs, "max_log_elem_size" ), max_log_elem_size );
 478
 479     struct_count = cvTsClipInt( struct_count, 1, 100 );
 480     max_struct_size = cvTsClipInt( max_struct_size, 1, 1<<20 );
 481     generations = cvTsClipInt( generations, 1, 100 );
 482     iterations = cvTsClipInt( iterations, 100, 1<<20 );
 483
 484     min_log_storage_block_size = cvTsClipInt( min_log_storage_block_size, 7, 20 );
 485     max_log_storage_block_size = cvTsClipInt( max_log_storage_block_size,
 486                                               min_log_storage_block_size, 20 );
 487
 488     min_log_elem_size = cvTsClipInt( min_log_elem_size, 0, 8 );
 489     max_log_elem_size = cvTsClipInt( max_log_elem_size, min_log_elem_size, 10 );
 490
 491     return 0;
 492 }
 493
 494
 495 void CxCore_DynStructBaseTest::update_progressbar()
 496 {
 497     int64 t;
 498
 499     if( test_progress < 0 )
 500     {
 501         test_progress = 0;
 502         cpu_freq = cvGetTickFrequency();
 503         start_time = cvGetTickCount();
 504     }
 505
 506     t = cvGetTickCount();
 507     test_progress = update_progress( test_progress, 0, 0, ((double)(t - start_time))/(cpu_freq*1000) );
 508 }
 509
 510
 511 void CxCore_DynStructBaseTest::set_error_context( const char* condition,
 512                                             const char* err_msg,
 513                                             const char* func_name )
 514 {
 515     ts->printf( CvTS::LOG, "%s: %s\n(\"%s\" failed).\n"
 516                 "generation = %d, struct_idx = %d, iter = %d\n",
 517                 func_name, err_msg, condition, gen, struct_idx, iter );
 518     ts->set_failed_test_info( CvTS::FAIL_INVALID_OUTPUT );
 519 }
 520
 521
 522 int CxCore_DynStructBaseTest::test_seq_block_consistence( int _struct_idx, CvSeq* seq, int total )
 523 {
 524     int sum = 0, code = -1;
 525     CV_FUNCNAME( "CxCore_DynStructBaseTest::test_seq_block_consistence" );
 526
 527     struct_idx = _struct_idx;
 528
 529     __BEGIN__;
 530
 531     CV_TS_SEQ_CHECK_CONDITION( seq != 0, "Null sequence pointer" );
 532
 533     if( seq->first )
 534     {
 535         CvSeqBlock* block = seq->first;
 536         CvSeqBlock* prev_block = block->prev;
 537
 538         int delta_idx = seq->first->start_index;
 539
 540         for( ;; )
 541         {
 542             CV_TS_SEQ_CHECK_CONDITION( sum == block->start_index - delta_idx &&
 543                              block->count > 0 && block->prev == prev_block &&
 544                              prev_block->next == block,
 545                              "sequence blocks are inconsistent" );
 546             sum += block->count;
 547             prev_block = block;
 548             block = block->next;
 549             if( block == seq->first ) break;
 550         }
 551
 552         CV_TS_SEQ_CHECK_CONDITION( block->prev->count * seq->elem_size +
 553                          block->prev->data <= seq->block_max,
 554                          "block->data or block_max pointer are incorrect" );
 555     }
 556
 557     CV_TS_SEQ_CHECK_CONDITION( seq->total == sum && sum == total,
 558                                "total number of elements is incorrect" );
 559
 560     code = 0;
 561
 562     __END__;
 563
 564     return code;
 565 }
 566
 567
 568 CxCore_DynStructBaseTest ds_test( "ds", "" );
 569
 570 /////////////////////////////////// sequence tests ////////////////////////////////////
 571
 572 class CxCore_SeqBaseTest : public CxCore_DynStructBaseTest
 573 {
 574 public:
 575     CxCore_SeqBaseTest( const char* test_name, const char* test_funcs );
 576     void clear();
 577     void run( int );
 578
 579 protected:
 580     int test_multi_create();
 581     int test_get_seq_elem( int _struct_idx, int iters );
 582     int test_get_seq_reading( int _struct_idx, int iters );
 583     int test_seq_ops( int iters );
 584 };
 585
 586
 587 CxCore_SeqBaseTest::CxCore_SeqBaseTest( const char* test_name, const char* test_funcs ) :
 588     CxCore_DynStructBaseTest( test_name, test_funcs )
 589 {
 590 }
 591
 592
 593 void CxCore_SeqBaseTest::clear()
 594 {
 595     int i;
 596     if( simple_struct )
 597     {
 598         for( i = 0; i < struct_count; i++ )
 599             cvTsReleaseSimpleSeq( (CvTsSimpleSeq**)&simple_struct[i] );
 600     }
 601     CxCore_DynStructBaseTest::clear();
 602 }
 603
 604
 605 int CxCore_SeqBaseTest::test_multi_create()
 606 {
 607     CvSeqWriter* writer = (CvSeqWriter*)cvStackAlloc( struct_count*sizeof(writer[0]) );
 608     int* pos = (int*)cvStackAlloc( struct_count*sizeof(pos[0]) );
 609     int* index = (int*)cvStackAlloc( struct_count*sizeof(index[0]) );
 610     int  i, cur_count, elem_size;
 611     int  code = -1;
 612     CvRNG* rng = ts->get_rng();
 613
 614     CV_FUNCNAME( "CxCore_SeqBaseTest::test_multi_create" );
 615
 616     __BEGIN__;
 617
 618     for( i = 0; i < struct_count; i++ )
 619     {
 620         double t;
 621         CvMat m;
 622         CvTsSimpleSeq* sseq;
 623
 624         pos[i] = -1;
 625         index[i] = i;
 626
 627         t = cvTsRandReal(rng)*(max_log_elem_size - min_log_elem_size) + min_log_elem_size;
 628         elem_size = cvRound( exp(t * CV_LOG2) );
 629         elem_size = MIN( elem_size, (int)(storage->block_size - sizeof(void*) -
 630                         sizeof(CvSeqBlock) - sizeof(CvMemBlock)) );
 631
 632         cvTsReleaseSimpleSeq( (CvTsSimpleSeq**)&simple_struct[i] );
 633         simple_struct[i] = sseq = cvTsCreateSimpleSeq( max_struct_size, elem_size );
 634         cxcore_struct[i] = 0;
 635         sseq->count = cvTsRandInt( rng ) % max_struct_size;
 636         m = cvMat( 1, MAX(sseq->count,1)*elem_size, CV_8UC1, sseq->array );
 637         cvRandArr( rng, &m, CV_RAND_UNI, cvScalarAll(0), cvScalarAll(256) );
 638     }
 639
 640     for( cur_count = struct_count; cur_count > 0; cur_count-- )
 641     {
 642         for(;;)
 643         {
 644             int k = cvTsRandInt( rng ) % cur_count;
 645             struct_idx = index[k];
 646             CvTsSimpleSeq* sseq = (CvTsSimpleSeq*)simple_struct[struct_idx];
 647
 648             if( pos[struct_idx] < 0 )
 649             {
 650                 int hdr_size = (cvTsRandInt(rng) % 10)*4 + sizeof(CvSeq);
 651                 hdr_size = MIN( hdr_size, (int)(storage->block_size - sizeof(CvMemBlock)) );
 652                 elem_size = sseq->elem_size;
 653
 654                 if( cvTsRandInt(rng) % 2 )
 655                 {
 656                     CV_CALL( cvStartWriteSeq( 0, hdr_size, elem_size, storage, writer + struct_idx ));
 657                 }
 658                 else
 659                 {
 660                     CvSeq* s;
 661                     CV_CALL( s = cvCreateSeq( 0, hdr_size, elem_size, storage ));
 662                     CV_CALL( cvStartAppendToSeq( s, writer + struct_idx ));
 663                 }
 664
 665                 CV_CALL( cvSetSeqBlockSize( writer[struct_idx].seq, cvTsRandInt( rng ) % 10000 ));
 666                 pos[struct_idx] = 0;
 667             }
 668
 669             update_progressbar();
 670             if( pos[struct_idx] == sseq->count )
 671             {
 672                 CV_CALL( cxcore_struct[struct_idx] = cvEndWriteSeq( writer + struct_idx ));
 673                 /* del index */
 674                 for( ; k < cur_count-1; k++ )
 675                     index[k] = index[k+1];
 676                 break;
 677             }
 678
 679             {
 680                 schar* el = cvTsSimpleSeqElem( sseq, pos[struct_idx] );
 681                 CV_WRITE_SEQ_ELEM_VAR( el, writer[struct_idx] );
 682             }
 683             pos[struct_idx]++;
 684         }
 685     }
 686
 687     code = 0;
 688
 689     __END__;
 690
 691     return code;
 692 }
 693
 694
 695 int  CxCore_SeqBaseTest::test_get_seq_elem( int _struct_idx, int iters )
 696 {
 697     int i, code = -1;
 698     CvRNG* rng = ts->get_rng();
 699
 700     CV_FUNCNAME( "CxCore_SeqBaseTest::test_get_seq_elem" );
 701
 702     __BEGIN__;
 703
 704     CvSeq* seq = (CvSeq*)cxcore_struct[_struct_idx];
 705     CvTsSimpleSeq* sseq = (CvTsSimpleSeq*)simple_struct[_struct_idx];
 706     struct_idx = _struct_idx;
 707
 708     assert( seq->total == sseq->count );
 709
 710     if( sseq->count == 0 )
 711         return 0;
 712
 713     for( i = 0; i < iters; i++ )
 714     {
 715         int idx = cvTsRandInt(rng) % (sseq->count*3) - sseq->count*3/2;
 716         int idx0 = (unsigned)idx < (unsigned)(sseq->count) ? idx : idx < 0 ?
 717                    idx + sseq->count : idx - sseq->count;
 718         int bad_range = (unsigned)idx0 >= (unsigned)(sseq->count);
 719         schar* elem;
 720         CV_CALL( elem = cvGetSeqElem( seq, idx ));
 721
 722         if( bad_range )
 723         {
 724             CV_TS_SEQ_CHECK_CONDITION( elem == 0,
 725                              "cvGetSeqElem doesn't "
 726                              "handle \"out of range\" properly" );
 727         }
 728         else
 729         {
 730             CV_TS_SEQ_CHECK_CONDITION( elem != 0 &&
 731                              !memcmp( elem, cvTsSimpleSeqElem(sseq, idx0), sseq->elem_size ),
 732                              "cvGetSeqElem returns wrong element" );
 733
 734             CV_CALL( idx = cvSeqElemIdx(seq, elem ));
 735             CV_TS_SEQ_CHECK_CONDITION( idx >= 0 && idx == idx0,
 736                                        "cvSeqElemIdx is incorrect" );
 737         }
 738     }
 739
 740     code = 0;
 741
 742     __END__;
 743
 744     return code;
 745 }
 746
 747
 748 int  CxCore_SeqBaseTest::test_get_seq_reading( int _struct_idx, int iters )
 749 {
 750     const int max_val = 3*5 + 2;
 751     int code = -1, pos;
 752     CvSeq* seq = (CvSeq*)cxcore_struct[_struct_idx];
 753     CvTsSimpleSeq* sseq = (CvTsSimpleSeq*)simple_struct[_struct_idx];
 754     int total = seq->total;
 755     CvRNG* rng = ts->get_rng();
 756     CvSeqReader reader;
 757     schar* elem;
 758
 759     CV_FUNCNAME( "CxCore_SeqBaseTest::test_get_seq_reading" );
 760
 761     __BEGIN__;
 762
 763     assert( total == sseq->count );
 764     this->struct_idx = _struct_idx;
 765     elem = (schar*)alloca( sseq->elem_size );
 766
 767     pos = cvTsRandInt(rng) % 2;
 768     CV_CALL( cvStartReadSeq( seq, &reader, pos ));
 769
 770     if( total == 0 )
 771     {
 772         CV_TS_SEQ_CHECK_CONDITION( reader.ptr == 0, "Empty sequence reader pointer is not NULL" );
 773         code = 0;
 774         EXIT;
 775     }
 776
 777     pos = pos ? seq->total - 1 : 0;
 778
 779     CV_TS_SEQ_CHECK_CONDITION( pos == cvGetSeqReaderPos(&reader),
 780                                "initial reader position is wrong" );
 781
 782     for( iter = 0; iter < iters; iter++ )
 783     {
 784         int op = cvTsRandInt(rng) % max_val;
 785
 786         if( op >= max_val - 2 )
 787         {
 788             int new_pos, new_pos0;
 789             int bad_range;
 790             int is_relative = op == max_val - 1;
 791
 792             new_pos = cvTsRandInt(rng) % (total*2) - total;
 793             new_pos0 = new_pos + (is_relative ? pos : 0 );
 794
 795             if( new_pos0 < 0 ) new_pos0 += total;
 796             if( new_pos0 >= total ) new_pos0 -= total;
 797
 798             bad_range = (unsigned)new_pos0 >= (unsigned)total;
 799             CV_CALL( cvSetSeqReaderPos( &reader, new_pos, is_relative ));
 800
 801             if( !bad_range )
 802             {
 803                 CV_TS_SEQ_CHECK_CONDITION( new_pos0 == cvGetSeqReaderPos( &reader ),
 804                                  "cvset reader position doesn't work" );
 805                 pos = new_pos0;
 806             }
 807             else
 808             {
 809                 CV_TS_SEQ_CHECK_CONDITION( pos == cvGetSeqReaderPos( &reader ),
 810                    "reader doesn't stay at the current position after wrong positioning" );
 811             }
 812         }
 813         else
 814         {
 815             int direction = (op % 3) - 1;
 816             memcpy( elem, reader.ptr, sseq->elem_size );
 817
 818             if( direction > 0 )
 819             {
 820                 CV_NEXT_SEQ_ELEM( sseq->elem_size, reader );
 821             }
 822             else if( direction < 0 )
 823             {
 824                 CV_PREV_SEQ_ELEM( sseq->elem_size, reader );
 825             }
 826
 827             CV_TS_SEQ_CHECK_CONDITION( memcmp(elem, cvTsSimpleSeqElem(sseq, pos),
 828                                        sseq->elem_size) == 0, "reading is incorrect" );
 829             pos += direction;
 830             if( pos < 0 ) pos += total;
 831             if( pos >= total ) pos -= total;
 832
 833             CV_TS_SEQ_CHECK_CONDITION( pos == cvGetSeqReaderPos( &reader ),
 834                    "reader doesn't move correctly after reading" );
 835         }
 836     }
 837
 838     code = 0;
 839
 840     __END__;
 841
 842     return code;
 843 }
 844
 845
 846 int  CxCore_SeqBaseTest::test_seq_ops( int iters )
 847 {
 848     const int max_op = 14;
 849     int i, code = -1;
 850     int max_elem_size = 0;
 851     schar *elem = 0, *elem2 = 0;
 852     CvMat* elem_mat = 0;
 853     CvRNG* rng = ts->get_rng();
 854
 855     CV_FUNCNAME( "CxCore_SeqBaseTest::test_seq_ops" );
 856
 857     __BEGIN__;
 858
 859     for( i = 0; i < struct_count; i++ )
 860         max_elem_size = MAX( max_elem_size, ((CvSeq*)cxcore_struct[i])->elem_size );
 861
 862     CV_CALL( elem_mat = cvCreateMat( 1, max_struct_size*max_elem_size, CV_8UC1 ));
 863     elem = (schar*)elem_mat->data.ptr;
 864
 865     for( iter = 0; iter < iters; iter++ )
 866     {
 867         struct_idx = cvTsRandInt(rng) % struct_count;
 868         int op = cvTsRandInt(rng) % max_op;
 869         CvSeq* seq = (CvSeq*)cxcore_struct[struct_idx];
 870         CvTsSimpleSeq* sseq = (CvTsSimpleSeq*)simple_struct[struct_idx];
 871         int elem_size = sseq->elem_size;
 872         int whence = 0, pos = 0, count = 0;
 873
 874         switch( op )
 875         {
 876         case 0:
 877         case 1:
 878         case 2:  // push/pushfront/insert
 879             if( sseq->count == sseq->max_count )
 880                 break;
 881
 882             elem_mat->cols = elem_size;
 883             cvRandArr( rng, elem_mat, CV_RAND_UNI, cvScalarAll(0), cvScalarAll(255) );
 884
 885             whence = op - 1;
 886             if( whence < 0 )
 887             {
 888                 pos = 0;
 889                 CV_CALL(cvSeqPushFront( seq, elem ));
 890             }
 891             else if( whence > 0 )
 892             {
 893                 pos = sseq->count;
 894                 CV_CALL(cvSeqPush( seq, elem ));
 895             }
 896             else
 897             {
 898                 pos = cvTsRandInt(rng) % (sseq->count + 1);
 899                 CV_CALL(cvSeqInsert( seq, pos, elem ));
 900             }
 901
 902             cvTsSimpleSeqShiftAndCopy( sseq, pos, pos + 1, elem );
 903             elem2 = cvGetSeqElem( seq, pos );
 904             CV_TS_SEQ_CHECK_CONDITION( elem2 != 0, "The inserted element could not be retrieved" );
 905             CV_TS_SEQ_CHECK_CONDITION( seq->total == sseq->count &&
 906                              memcmp(elem2, cvTsSimpleSeqElem(sseq,pos), elem_size) == 0,
 907                              "The inserted sequence element is wrong" );
 908             break;
 909
 910         case 3:
 911         case 4:
 912         case 5: // pop/popfront/remove
 913             if( sseq->count == 0 )
 914                 break;
 915
 916             whence = op - 4;
 917             if( whence < 0 )
 918             {
 919                 pos = 0;
 920                 CV_CALL( cvSeqPopFront( seq, elem ));
 921             }
 922             else if( whence > 0 )
 923             {
 924                 pos = sseq->count-1;
 925                 CV_CALL( cvSeqPop( seq, elem ));
 926             }
 927             else
 928             {
 929                 pos = cvTsRandInt(rng) % sseq->count;
 930                 CV_CALL( cvSeqRemove( seq, pos ));
 931             }
 932
 933             if( whence != 0 )
 934                 CV_TS_SEQ_CHECK_CONDITION( seq->total == sseq->count - 1 &&
 935                         memcmp( elem, cvTsSimpleSeqElem(sseq,pos), elem_size) == 0,
 936                        "The popped sequence element isn't correct" );
 937
 938             cvTsSimpleSeqShiftAndCopy( sseq, pos + 1, pos );
 939
 940             if( sseq->count > 0 )
 941             {
 942                 CV_CALL( elem2 = cvGetSeqElem( seq, pos < sseq->count ? pos : -1 ));
 943                 CV_TS_SEQ_CHECK_CONDITION( elem2 != 0, "GetSeqElem fails after removing the element" );
 944
 945                 CV_TS_SEQ_CHECK_CONDITION( memcmp( elem2,
 946                     cvTsSimpleSeqElem(sseq, pos - (pos == sseq->count)), elem_size) == 0,
 947                     "The first shifted element is not correct after removing another element" );
 948             }
 949             else
 950             {
 951                 CV_TS_SEQ_CHECK_CONDITION( seq->first == 0,
 952                                  "The sequence doesn't become empty after the final remove" );
 953             }
 954             break;
 955
 956         case 6:
 957         case 7:
 958         case 8: // push [front] multi/insert slice
 959             if( sseq->count == sseq->max_count )
 960                 break;
 961
 962             count = cvTsRandInt( rng ) % (sseq->max_count - sseq->count + 1);
 963             elem_mat->cols = MAX(count,1) * elem_size;
 964             cvRandArr( rng, elem_mat, CV_RAND_UNI, cvScalarAll(0), cvScalarAll(255) );
 965
 966             whence = op - 7;
 967             pos = whence < 0 ? 0 : whence > 0 ? sseq->count : cvTsRandInt(rng) % (sseq->count+1);
 968             if( whence != 0 )
 969             {
 970                 CV_CALL( cvSeqPushMulti( seq, elem, count, whence < 0 ));
 971             }
 972             else
 973             {
 974                 CvSeq header;
 975                 CvSeqBlock block;
 976                 CV_CALL( cvMakeSeqHeaderForArray( CV_SEQ_KIND_GENERIC, sizeof(CvSeq),
 977                                          sseq->elem_size,
 978                                          elem_mat->data.ptr, count,
 979                                          &header, &block ));
 980
 981                 CV_CALL( cvSeqInsertSlice( seq, pos, &header ));
 982             }
 983             cvTsSimpleSeqShiftAndCopy( sseq, pos, pos + count, elem );
 984
 985             if( sseq->count > 0 )
 986             {
 987                 // choose the random element among the added
 988                 pos = count > 0 ? cvTsRandInt(rng) % count + pos : MAX(pos-1,0);
 989                 CV_CALL( elem2 = cvGetSeqElem( seq, pos ));
 990                 CV_TS_SEQ_CHECK_CONDITION( elem2 != 0, "multi push operation doesn't add elements" );
 991                 CV_TS_SEQ_CHECK_CONDITION( seq->total == sseq->count &&
 992                                  memcmp( elem2, cvTsSimpleSeqElem(sseq,pos), elem_size) == 0,
 993                                  "One of the added elements is wrong" );
 994             }
 995             else
 996             {
 997                 CV_TS_SEQ_CHECK_CONDITION( seq->total == 0 && seq->first == 0,
 998                                  "Adding no elements to empty sequence fails" );
 999             }
1000             break;
1001
1002         case 9:
1003         case 10:
1004         case 11: // pop [front] multi
1005             if( sseq->count == 0 )
1006                 break;
1007
1008             count = cvTsRandInt(rng) % (sseq->count+1);
1009             whence = op - 10;
1010             pos = whence < 0 ? 0 : whence > 0 ? sseq->count - count :
1011                 cvTsRandInt(rng) % (sseq->count - count + 1);
1012
1013             if( whence != 0 )
1014             {
1015                 CV_CALL( cvSeqPopMulti( seq, elem, count, whence < 0 ));
1016
1017                 if( count > 0 )
1018                 {
1019                     CV_TS_SEQ_CHECK_CONDITION( memcmp(elem,
1020                         cvTsSimpleSeqElem(sseq,pos), elem_size) == 0,
1021                         "The first (in the sequence order) removed element is wrong after popmulti" );
1022                 }
1023             }
1024             else
1025             {
1026                 CV_CALL( cvSeqRemoveSlice( seq, cvSlice(pos, pos + count) ));
1027             }
1028
1029             CV_TS_SEQ_CHECK_CONDITION( seq->total == sseq->count - count,
1030                        "The popmulti left a wrong number of elements in the sequence" );
1031
1032             cvTsSimpleSeqShiftAndCopy( sseq, pos + count, pos, 0 );
1033             if( sseq->count > 0 )
1034             {
1035                 pos = whence < 0 ? 0 : MIN( pos, sseq->count - 1 );
1036                 elem2 = cvGetSeqElem( seq, pos );
1037                 CV_TS_SEQ_CHECK_CONDITION( elem2 &&
1038                     memcmp( elem2, cvTsSimpleSeqElem(sseq,pos), elem_size) == 0,
1039                     "The last sequence element is wrong after POP" );
1040             }
1041             else
1042             {
1043                 CV_TS_SEQ_CHECK_CONDITION( seq->total == 0 && seq->first == 0,
1044                                  "The sequence doesn't become empty after final POP" );
1045             }
1046             break;
1047         case 12: // seqslice
1048             {
1049                 CvMemStoragePos storage_pos;
1050                 cvSaveMemStoragePos( storage, &storage_pos );
1051
1052                 int copy_data = cvTsRandInt(rng) % 2;
1053                 count = cvTsRandInt(rng) % (seq->total + 1);
1054                 pos = cvTsRandInt(rng) % (seq->total - count + 1);
1055                 CvSeq* seq_slice = cvSeqSlice( seq, cvSlice(pos, pos + count), storage, copy_data );
1056
1057                 CV_TS_SEQ_CHECK_CONDITION( seq_slice && seq_slice->total == count,
1058                                            "cvSeqSlice returned incorrect slice" );
1059
1060                 if( count > 0 )
1061                 {
1062                     int test_idx = cvTsRandInt(rng) % count;
1063                     elem2 = cvGetSeqElem( seq_slice, test_idx );
1064                     schar* elem3 = cvGetSeqElem( seq, pos + test_idx );
1065                     CV_TS_SEQ_CHECK_CONDITION( elem2 &&
1066                         memcmp( elem2, cvTsSimpleSeqElem(sseq,pos + test_idx), elem_size) == 0,
1067                         "The extracted slice elements are not correct" );
1068                     CV_TS_SEQ_CHECK_CONDITION( (elem2 == elem3) ^ copy_data,
1069                         "copy_data flag is handled incorrectly" );
1070                 }
1071
1072                 cvRestoreMemStoragePos( storage, &storage_pos );
1073             }
1074             break;
1075         case 13: // clear
1076             cvTsClearSimpleSeq( sseq );
1077             cvClearSeq( seq );
1078             CV_TS_SEQ_CHECK_CONDITION( seq->total == 0 && seq->first == 0,
1079                                     "The sequence doesn't become empty after clear" );
1080             break;
1081         default:
1082             assert(0);
1083             EXIT;
1084         }
1085
1086         if( test_seq_block_consistence(struct_idx, seq, sseq->count) < 0 )
1087             EXIT;
1088
1089         if( test_get_seq_elem(struct_idx, 7) < 0 )
1090             EXIT;
1091
1092         update_progressbar();
1093     }
1094
1095     code = 0;
1096
1097     __END__;
1098
1099     if( elem_mat )
1100         elem_mat->cols = 1; // just to skip a consistency check
1101     cvReleaseMat( &elem_mat );
1102
1103     return code;
1104 }
1105
1106
1107 void CxCore_SeqBaseTest::run( int )
1108 {
1109     CvRNG* rng = ts->get_rng();
1110     int i;
1111     double t;
1112
1113     //CV_FUNCNAME( "CxCore_SeqBaseTest::run" );
1114
1115     __BEGIN__;
1116
1117     clear();
1118     test_progress = -1;
1119
1120     simple_struct = (void**)cvAlloc( struct_count * sizeof(simple_struct[0]) );
1121     memset( simple_struct, 0, struct_count * sizeof(simple_struct[0]) );
1122     cxcore_struct = (void**)cvAlloc( struct_count * sizeof(cxcore_struct[0]) );
1123     memset( cxcore_struct, 0, struct_count * sizeof(cxcore_struct[0]) );
1124
1125     for( gen = 0; gen < generations; gen++ )
1126     {
1127         struct_idx = iter = -1;
1128
1129         if( !storage )
1130         {
1131             t = cvTsRandReal(rng)*(max_log_storage_block_size - min_log_storage_block_size)
1132                 + min_log_storage_block_size;
1133             storage = cvCreateMemStorage( cvRound( exp(t * CV_LOG2) ) );
1134         }
1135
1136         iter = struct_idx = -1;
1137         test_multi_create();
1138
1139         for( i = 0; i < struct_count; i++ )
1140         {
1141             if( test_seq_block_consistence(i, (CvSeq*)cxcore_struct[i],
1142                     ((CvTsSimpleSeq*)simple_struct[i])->count) < 0 )
1143                 EXIT;
1144
1145             if( test_get_seq_elem( i, MAX(iterations/3,7) ) < 0 )
1146                 EXIT;
1147
1148             if( test_get_seq_reading( i, MAX(iterations/3,7) ) < 0 )
1149                 EXIT;
1150             update_progressbar();
1151         }
1152
1153         if( test_seq_ops( iterations ) < 0 )
1154             EXIT;
1155
1156         if( cvTsRandInt(rng) % 2 )
1157             cvReleaseMemStorage( &storage );
1158         else
1159             cvClearMemStorage( storage );
1160     }
1161
1162     __END__;
1163 }
1164
1165 CxCore_SeqBaseTest seqbase_test( "ds-seq-base", "cvCreateSeq, cvClearSeq, cvSeqSlice, "
1166                        "cvStartAppendToSeq, cvStartWriteSeq, cvEndWriteSeq, CV_WRITE_SEQ_ELEM_VAR, "
1167                        "cvGetSeqElem, cvSeqElemIdx, cvStartReadSeq, CV_NEXT_SEQ_ELEM, CV_PREV_SEQ_ELEM, "
1168                        "cvSetSeqReaderPos, cvGetSeqReaderPos, cvSeqPush, cvSeqPushFront, cvSeqPop, "
1169                        "cvSeqPopFront, cvSeqPushMulti, cvSeqPopMulti, cvSeqInsert, cvSeqRemove, "
1170                        "cvSeqInsertSlice, cvSeqRemoveSlice, cvMakeSeqHeaderForArray" );
1171
1172 ////////////////////////////// more sequence tests //////////////////////////////////////
1173
1174 class CxCore_SeqSortInvTest : public CxCore_SeqBaseTest
1175 {
1176 public:
1177     CxCore_SeqSortInvTest( const char* test_name, const char* test_funcs );
1178     void run( int );
1179
1180 protected:
1181 };
1182
1183
1184 CxCore_SeqSortInvTest::CxCore_SeqSortInvTest( const char* test_name, const char* test_funcs ) :
1185     CxCore_SeqBaseTest( test_name, test_funcs )
1186 {
1187 }
1188
1189
1190 static int icvCmpSeqElems( const void* a, const void* b, void* userdata )
1191 {
1192     return memcmp( a, b, ((CvSeq*)userdata)->elem_size );
1193 }
1194
1195 static int icvCmpSeqElems2_elem_size = 0;
1196 static int icvCmpSeqElems2( const void* a, const void* b )
1197 {
1198     return memcmp( a, b, icvCmpSeqElems2_elem_size );
1199 }
1200
1201
1202 void CxCore_SeqSortInvTest::run( int )
1203 {
1204     CvRNG* rng = ts->get_rng();
1205     int i, k;
1206     double t;
1207     schar *elem0, *elem, *elem2;
1208     CvMat* buffer = 0;
1209
1210     CV_FUNCNAME( "CxCore_SeqSortInvTest::run" );
1211
1212     __BEGIN__;
1213
1214     clear();
1215     test_progress = -1;
1216
1217     simple_struct = (void**)cvAlloc( struct_count * sizeof(simple_struct[0]) );
1218     memset( simple_struct, 0, struct_count * sizeof(simple_struct[0]) );
1219     cxcore_struct = (void**)cvAlloc( struct_count * sizeof(cxcore_struct[0]) );
1220     memset( cxcore_struct, 0, struct_count * sizeof(cxcore_struct[0]) );
1221
1222     for( gen = 0; gen < generations; gen++ )
1223     {
1224         struct_idx = iter = -1;
1225
1226         if( !storage )
1227         {
1228             t = cvTsRandReal(rng)*(max_log_storage_block_size - min_log_storage_block_size)
1229                 + min_log_storage_block_size;
1230             storage = cvCreateMemStorage( cvRound( exp(t * CV_LOG2) ) );
1231         }
1232
1233         for( iter = 0; iter < iterations/10; iter++ )
1234         {
1235             int max_size = 0;
1236             test_multi_create();
1237
1238             for( i = 0; i < struct_count; i++ )
1239             {
1240                 CvTsSimpleSeq* sseq = (CvTsSimpleSeq*)simple_struct[i];
1241                 max_size = MAX( max_size, sseq->count*sseq->elem_size );
1242             }
1243
1244             if( !buffer || buffer->cols < max_size )
1245             {
1246                 cvReleaseMat( &buffer );
1247                 CV_CALL( buffer = cvCreateMat( 1, max_size, CV_8UC1 ));
1248             }
1249
1250             for( i = 0; i < struct_count; i++ )
1251             {
1252                 CvSeq* seq = (CvSeq*)cxcore_struct[i];
1253                 CvTsSimpleSeq* sseq = (CvTsSimpleSeq*)simple_struct[i];
1254                 CvSlice slice = CV_WHOLE_SEQ;
1255
1256                 //printf("%d. %d. %d-th size = %d\n", gen, iter, i, sseq->count );
1257
1258                 CV_CALL( cvSeqInvert( seq ));
1259                 cvTsSimpleSeqInvert( sseq );
1260
1261                 if( test_seq_block_consistence( i, seq, sseq->count ) < 0 )
1262                     EXIT;
1263
1264                 if( sseq->count > 0 && cvTsRandInt(rng) % 2 == 0 )
1265                 {
1266                     slice.end_index = cvTsRandInt(rng) % sseq->count + 1;
1267                     slice.start_index = cvTsRandInt(rng) % (sseq->count - slice.end_index + 1);
1268                     slice.end_index += slice.start_index;
1269                 }
1270
1271                 CV_CALL( cvCvtSeqToArray( seq, buffer->data.ptr, slice ));
1272
1273                 slice.end_index = MIN( slice.end_index, sseq->count );
1274                 CV_TS_SEQ_CHECK_CONDITION( sseq->count == 0 || memcmp( buffer->data.ptr,
1275                         sseq->array + slice.start_index*sseq->elem_size,
1276                         (slice.end_index - slice.start_index)*sseq->elem_size ) == 0,
1277                         "cvSeqInvert returned wrong result" );
1278
1279                 for( k = 0; k < (sseq->count > 0 ? 10 : 0); k++ )
1280                 {
1281                     int idx0 = cvTsRandInt(rng) % sseq->count, idx = 0;
1282                     CV_CALL( elem0 = cvTsSimpleSeqElem( sseq, idx0 ));
1283                     CV_CALL( elem = cvGetSeqElem( seq, idx0 ));
1284                     elem2 = cvSeqSearch( seq, elem0, k % 2 ? icvCmpSeqElems : 0, 0, &idx, seq );
1285
1286                     CV_TS_SEQ_CHECK_CONDITION( elem != 0 &&
1287                         memcmp( elem0, elem, seq->elem_size ) == 0,
1288                         "cvSeqInvert gives incorrect result" );
1289                     CV_TS_SEQ_CHECK_CONDITION( elem2 != 0 &&
1290                         memcmp( elem0, elem2, seq->elem_size ) == 0 &&
1291                         elem2 == cvGetSeqElem( seq, idx ),
1292                         "cvSeqSearch failed (linear search)" );
1293                 }
1294
1295                 CV_CALL( cvSeqSort( seq, icvCmpSeqElems, seq ));
1296
1297                 if( test_seq_block_consistence( i, seq, sseq->count ) < 0 )
1298                     EXIT;
1299
1300                 if( sseq->count > 0 )
1301                 {
1302                     // !!! This is not thread-safe !!!
1303                     icvCmpSeqElems2_elem_size = sseq->elem_size;
1304                     qsort( sseq->array, sseq->count, sseq->elem_size, icvCmpSeqElems2 );
1305
1306                     if( cvTsRandInt(rng) % 2 == 0 )
1307                     {
1308                         slice.end_index = cvTsRandInt(rng) % sseq->count + 1;
1309                         slice.start_index = cvTsRandInt(rng) % (sseq->count - slice.end_index + 1);
1310                         slice.end_index += slice.start_index;
1311                     }
1312                 }
1313
1314                 CV_CALL( cvCvtSeqToArray( seq, buffer->data.ptr, slice ));
1315                 CV_TS_SEQ_CHECK_CONDITION( sseq->count == 0 || memcmp( buffer->data.ptr,
1316                         sseq->array + slice.start_index*sseq->elem_size,
1317                         (slice.end_index - slice.start_index)*sseq->elem_size ) == 0,
1318                         "cvSeqSort returned wrong result" );
1319
1320                 for( k = 0; k < (sseq->count > 0 ? 10 : 0); k++ )
1321                 {
1322                     int idx0 = cvTsRandInt(rng) % sseq->count, idx = 0;
1323                     CV_CALL( elem0 = cvTsSimpleSeqElem( sseq, idx0 ));
1324                     CV_CALL( elem = cvGetSeqElem( seq, idx0 ));
1325                     elem2 = cvSeqSearch( seq, elem0, icvCmpSeqElems, 1, &idx, seq );
1326
1327                     CV_TS_SEQ_CHECK_CONDITION( elem != 0 &&
1328                         memcmp( elem0, elem, seq->elem_size ) == 0,
1329                         "cvSeqSort gives incorrect result" );
1330                     CV_TS_SEQ_CHECK_CONDITION( elem2 != 0 &&
1331                         memcmp( elem0, elem2, seq->elem_size ) == 0 &&
1332                         elem2 == cvGetSeqElem( seq, idx ),
1333                         "cvSeqSearch failed (binary search)" );
1334                 }
1335             }
1336
1337             cvClearMemStorage( storage );
1338         }
1339
1340         cvReleaseMemStorage( &storage );
1341     }
1342
1343     __END__;
1344
1345     cvReleaseMat( &buffer );
1346 }
1347
1348
1349 CxCore_SeqSortInvTest seqsortinv_test( "ds-seq-sortinv",
1350                     "cvCreateSeq, cvStartAppendToSeq, cvStartWriteSeq, "
1351                     "cvEndWriteSeq, CV_WRITE_SEQ_ELEM_VAR, "
1352                     "cvSeqSort, cvSeqSearch, cvSeqInvert, "
1353                     "cvCvtSeqToArray, cvGetSeqElem" );
1354
1355 /////////////////////////////////////// set tests ///////////////////////////////////////
1356
1357 class CxCore_SetTest : public CxCore_DynStructBaseTest
1358 {
1359 public:
1360     CxCore_SetTest();
1361     void clear();
1362     void run( int );
1363
1364 protected:
1365     //int test_seq_block_consistence( int struct_idx );
1366     int test_set_ops( int iters );
1367 };
1368
1369
1370 CxCore_SetTest::CxCore_SetTest():
1371     CxCore_DynStructBaseTest( "ds-set", "cvCreateSet, cvClearSet, "
1372                        "cvSetAdd, cvSetRemove, cvSetNew, cvSetRemoveByPtr, cvGetSetElem" )
1373 {
1374 }
1375
1376
1377 void CxCore_SetTest::clear()
1378 {
1379     int i;
1380     if( simple_struct )
1381         for( i = 0; i < struct_count; i++ )
1382             cvTsReleaseSimpleSet( (CvTsSimpleSet**)&simple_struct[i] );
1383     CxCore_DynStructBaseTest::clear();
1384 }
1385
1386
1387 int  CxCore_SetTest::test_set_ops( int iters )
1388 {
1389     const int max_op = 4;
1390     int i, code = -1;
1391     int max_elem_size = 0;
1392     int idx, idx0;
1393     CvSetElem *elem = 0, *elem2 = 0, *elem3 = 0;
1394     schar* elem_data = 0;
1395     CvMat* elem_mat = 0;
1396     CvRNG* rng = ts->get_rng();
1397     //int max_active_count = 0, mean_active_count = 0;
1398
1399     CV_FUNCNAME( "CxCore_SetTest::test_set_ops" );
1400
1401     __BEGIN__;
1402
1403     for( i = 0; i < struct_count; i++ )
1404         max_elem_size = MAX( max_elem_size, ((CvSeq*)cxcore_struct[i])->elem_size );
1405
1406     CV_CALL( elem_mat = cvCreateMat( 1, max_elem_size, CV_8UC1 ));
1407
1408     for( iter = 0; iter < iters; iter++ )
1409     {
1410         struct_idx = cvTsRandInt(rng) % struct_count;
1411
1412         CvSet* cvset = (CvSet*)cxcore_struct[struct_idx];
1413         CvTsSimpleSet* sset = (CvTsSimpleSet*)simple_struct[struct_idx];
1414         int pure_elem_size = sset->elem_size - 1;
1415         int prev_total = cvset->total, prev_count = cvset->active_count;
1416         int op = cvTsRandInt(rng) % (iter <= iters/10 ? 2 : max_op);
1417         int by_ptr = op % 2 == 0;
1418         CvSetElem* first_free = cvset->free_elems;
1419         CvSetElem* next_free = first_free ? first_free->next_free : 0;
1420         int pass_data = 0;
1421
1422         if( iter > iters/10 && cvTsRandInt(rng)%200 == 0 ) // clear set
1423         {
1424             int prev_count = cvset->total;
1425             cvClearSet( cvset );
1426             cvTsClearSimpleSet( sset );
1427
1428             CV_TS_SEQ_CHECK_CONDITION( cvset->active_count == 0 && cvset->total == 0 &&
1429                                        cvset->first == 0 && cvset->free_elems == 0 &&
1430                                        (cvset->free_blocks != 0 || prev_count == 0),
1431                                        "cvClearSet doesn't remove all the elements" );
1432             continue;
1433         }
1434         else if( op == 0 || op == 1 ) // add element
1435         {
1436             if( sset->free_count == 0 )
1437                 continue;
1438
1439             elem_mat->cols = cvset->elem_size;
1440             cvRandArr( rng, elem_mat, CV_RAND_UNI, cvScalarAll(0), cvScalarAll(255) );
1441             elem = (CvSetElem*)elem_mat->data.ptr;
1442
1443             if( by_ptr )
1444             {
1445                 CV_CALL( elem2 = cvSetNew( cvset ));
1446                 CV_TS_SEQ_CHECK_CONDITION( elem2 != 0, "cvSetNew returned NULL pointer" );
1447             }
1448             else
1449             {
1450                 pass_data = cvTsRandInt(rng) % 2;
1451                 CV_CALL( idx = cvSetAdd( cvset, pass_data ? elem : 0, &elem2 ));
1452                 CV_TS_SEQ_CHECK_CONDITION( elem2 != 0 && elem2->flags == idx,
1453                     "cvSetAdd returned NULL pointer or a wrong index" );
1454             }
1455
1456             elem_data = (schar*)elem + sizeof(int);
1457
1458             if( !pass_data )
1459                 memcpy( (schar*)elem2 + sizeof(int), elem_data, pure_elem_size );
1460
1461             idx = elem2->flags;
1462             idx0 = cvTsSimpleSetAdd( sset, elem_data );
1463             CV_CALL( elem3 = cvGetSetElem( cvset, idx ));
1464
1465             CV_TS_SEQ_CHECK_CONDITION( CV_IS_SET_ELEM(elem3) &&
1466                 idx == idx0 && elem3 == elem2 && (!pass_data ||
1467                 memcmp( (char*)elem3 + sizeof(int), elem_data, pure_elem_size) == 0),
1468                 "The added element is not correct" );
1469
1470             CV_TS_SEQ_CHECK_CONDITION( (!first_free || elem3 == first_free) &&
1471                                        (!next_free || cvset->free_elems == next_free) &&
1472                                        cvset->active_count == prev_count + 1,
1473                                        "The free node list is modified incorrectly" );
1474         }
1475         else if( op == 2 || op == 3 ) // remove element
1476         {
1477             idx = cvTsRandInt(rng) % sset->max_count;
1478
1479             if( sset->free_count == sset->max_count || idx >= sset->count )
1480                 continue;
1481
1482             elem_data = cvTsSimpleSetFind(sset, idx);
1483             if( elem_data == 0 )
1484                 continue;
1485
1486             CV_CALL( elem = cvGetSetElem( cvset, idx ));
1487             CV_TS_SEQ_CHECK_CONDITION( CV_IS_SET_ELEM(elem) && elem->flags == idx &&
1488                     memcmp((char*)elem + sizeof(int), elem_data, pure_elem_size) == 0,
1489                     "cvGetSetElem returned wrong element" );
1490
1491             if( by_ptr )
1492             {
1493                 CV_CALL( cvSetRemoveByPtr( cvset, elem ));
1494             }
1495             else
1496             {
1497                 CV_CALL( cvSetRemove( cvset, idx ));
1498             }
1499
1500             cvTsSimpleSetRemove( sset, idx );
1501
1502             CV_TS_SEQ_CHECK_CONDITION( !CV_IS_SET_ELEM(elem) && !cvGetSetElem(cvset, idx) &&
1503                                        (elem->flags & CV_SET_ELEM_IDX_MASK) == idx,
1504                                        "cvSetRemove[ByPtr] didn't release the element properly" );
1505
1506             CV_TS_SEQ_CHECK_CONDITION( elem->next_free == first_free &&
1507                                        cvset->free_elems == elem &&
1508                                        cvset->active_count == prev_count - 1,
1509                                        "The free node list has not been updated properly" );
1510         }
1511
1512         //max_active_count = MAX( max_active_count, cvset->active_count );
1513         //mean_active_count += cvset->active_count;
1514         CV_TS_SEQ_CHECK_CONDITION( cvset->active_count == sset->max_count - sset->free_count &&
1515                                    cvset->total >= cvset->active_count &&
1516                                    (cvset->total == 0 || cvset->total >= prev_total),
1517                                    "The total number of cvset elements is not correct" );
1518
1519         // CvSet and simple set do not neccessary have the same "total" (active & free) number,
1520         // so pass "set->total" to skip that check
1521         test_seq_block_consistence( struct_idx, (CvSeq*)cvset, cvset->total );
1522         update_progressbar();
1523     }
1524
1525     code = 0;
1526     //ts->printf( CvTS::LOG, "\ngeneration %d. max_active_count = %d,\n\tmean_active_count = %d\n",
1527     //            gen, max_active_count, mean_active_count/iters );
1528
1529     __END__;
1530
1531     if( elem_mat )
1532         elem_mat->cols = 1; // just to skip a consistency check
1533     cvReleaseMat( &elem_mat );
1534
1535     return code;
1536 }
1537
1538
1539 void CxCore_SetTest::run( int )
1540 {
1541     CvRNG* rng = ts->get_rng();
1542     int i;
1543     double t;
1544
1545     CV_FUNCNAME( "CxCore_SetTest::run" );
1546
1547     __BEGIN__;
1548
1549     clear();
1550     test_progress = -1;
1551
1552     simple_struct = (void**)cvAlloc( struct_count * sizeof(simple_struct[0]) );
1553     memset( simple_struct, 0, struct_count * sizeof(simple_struct[0]) );
1554     cxcore_struct = (void**)cvAlloc( struct_count * sizeof(cxcore_struct[0]) );
1555     memset( cxcore_struct, 0, struct_count * sizeof(cxcore_struct[0]) );
1556
1557     for( gen = 0; gen < generations; gen++ )
1558     {
1559         struct_idx = iter = -1;
1560         t = cvTsRandReal(rng)*(max_log_storage_block_size - min_log_storage_block_size) + min_log_storage_block_size;
1561         storage = cvCreateMemStorage( cvRound( exp(t * CV_LOG2) ) );
1562
1563         for( i = 0; i < struct_count; i++ )
1564         {
1565             t = cvTsRandReal(rng)*(max_log_elem_size - min_log_elem_size) + min_log_elem_size;
1566             int pure_elem_size = cvRound( exp(t * CV_LOG2) );
1567             int elem_size = pure_elem_size + sizeof(int);
1568             elem_size = (elem_size + sizeof(size_t) - 1) & ~(sizeof(size_t)-1);
1569             elem_size = MAX( elem_size, (int)sizeof(CvSetElem) );
1570             elem_size = MIN( elem_size, (int)(storage->block_size - sizeof(void*) - sizeof(CvMemBlock) - sizeof(CvSeqBlock)) );
1571             pure_elem_size = MIN( pure_elem_size, elem_size-(int)sizeof(CvSetElem) );
1572
1573             cvTsReleaseSimpleSet( (CvTsSimpleSet**)&simple_struct[i] );
1574             simple_struct[i] = cvTsCreateSimpleSet( max_struct_size, pure_elem_size );
1575             CV_CALL( cxcore_struct[i] = cvCreateSet( 0, sizeof(CvSet), elem_size, storage ));
1576         }
1577
1578         if( test_set_ops( iterations*100 ) < 0 )
1579             EXIT;
1580
1581         cvReleaseMemStorage( &storage );
1582     }
1583
1584     __END__;
1585 }
1586
1587 CxCore_SetTest set_test;
1588
1589
1590 /////////////////////////////////////// graph tests //////////////////////////////////
1591
1592 class CxCore_GraphTest : public CxCore_DynStructBaseTest
1593 {
1594 public:
1595     CxCore_GraphTest();
1596     void clear();
1597     void run( int );
1598
1599 protected:
1600     //int test_seq_block_consistence( int struct_idx );
1601     int test_graph_ops( int iters );
1602 };
1603
1604
1605 CxCore_GraphTest::CxCore_GraphTest():
1606     CxCore_DynStructBaseTest( "ds-graph", "cvCreateGraph, cvClearGraph, "
1607                        "cvGraphAddVtx, cvGraphRemoveVtx, cvGraphRemoveVtxByPtr, "
1608                        "cvGraphAddEdge, cvGraphAddEdgeByPtr, "
1609                        "cvGraphRemoveEdge, cvGraphRemoveEdgeByPtr, "
1610                        "cvGraphVtxDegree, cvGraphVtxDegreeByPtr, "
1611                        "cvGetGraphVtx, cvFindGraphEdge, cvFindGraphEdgeByPtr " )
1612 {
1613 }
1614
1615
1616 void CxCore_GraphTest::clear()
1617 {
1618     int i;
1619     if( simple_struct )
1620         for( i = 0; i < struct_count; i++ )
1621             cvTsReleaseSimpleGraph( (CvTsSimpleGraph**)&simple_struct[i] );
1622     CxCore_DynStructBaseTest::clear();
1623 }
1624
1625
1626 int  CxCore_GraphTest::test_graph_ops( int iters )
1627 {
1628     const int max_op = 4;
1629     int i, k, code = -1;
1630     int max_elem_size = 0;
1631     int idx, idx0;
1632     CvGraphVtx *vtx = 0, *vtx2 = 0, *vtx3 = 0;
1633     CvGraphEdge* edge = 0, *edge2 = 0;
1634     CvMat* elem_mat = 0;
1635     CvRNG* rng = ts->get_rng();
1636     //int max_active_count = 0, mean_active_count = 0;
1637
1638     CV_FUNCNAME( "CxCore_GraphTest::test_graph_ops" );
1639
1640     __BEGIN__;
1641
1642     for( i = 0; i < struct_count; i++ )
1643     {
1644         CvGraph* graph = (CvGraph*)cxcore_struct[i];
1645         max_elem_size = MAX( max_elem_size, graph->elem_size );
1646         max_elem_size = MAX( max_elem_size, graph->edges->elem_size );
1647     }
1648
1649     CV_CALL( elem_mat = cvCreateMat( 1, max_elem_size, CV_8UC1 ));
1650
1651     for( iter = 0; iter < iters; iter++ )
1652     {
1653         struct_idx = cvTsRandInt(rng) % struct_count;
1654         CvGraph* graph = (CvGraph*)cxcore_struct[struct_idx];
1655         CvTsSimpleGraph* sgraph = (CvTsSimpleGraph*)simple_struct[struct_idx];
1656         CvSet* edges = graph->edges;
1657         schar *vtx_data;
1658         char *edge_data;
1659         int pure_vtx_size = sgraph->vtx->elem_size - 1,
1660             pure_edge_size = sgraph->edge_size - 1;
1661         int prev_vtx_total = graph->total,
1662             prev_edge_total = graph->edges->total,
1663             prev_vtx_count = graph->active_count,
1664             prev_edge_count = graph->edges->active_count;
1665         int op = cvTsRandInt(rng) % max_op;
1666         int pass_data = 0, vtx_degree0 = 0, vtx_degree = 0;
1667         CvSetElem *first_free, *next_free;
1668
1669         if( cvTsRandInt(rng) % 200 == 0 ) // clear graph
1670         {
1671             int prev_vtx_count = graph->total, prev_edge_count = graph->edges->total;
1672
1673             cvClearGraph( graph );
1674             cvTsClearSimpleGraph( sgraph );
1675
1676             CV_TS_SEQ_CHECK_CONDITION( graph->active_count == 0 && graph->total == 0 &&
1677                     graph->first == 0 && graph->free_elems == 0 &&
1678                      (graph->free_blocks != 0 || prev_vtx_count == 0),
1679                      "The graph is not empty after clearing" );
1680
1681             CV_TS_SEQ_CHECK_CONDITION( edges->active_count == 0 && edges->total == 0 &&
1682                                        edges->first == 0 && edges->free_elems == 0 &&
1683                                        (edges->free_blocks != 0 || prev_edge_count == 0),
1684                                        "The graph is not empty after clearing" );
1685         }
1686         else if( op == 0 ) // add vertex
1687         {
1688             if( sgraph->vtx->free_count == 0 )
1689                 continue;
1690
1691             first_free = graph->free_elems;
1692             next_free = first_free ? first_free->next_free : 0;
1693
1694             if( pure_vtx_size )
1695             {
1696                 elem_mat->cols = graph->elem_size;
1697                 cvRandArr( rng, elem_mat, CV_RAND_UNI, cvScalarAll(0), cvScalarAll(255) );
1698             }
1699
1700             vtx = (CvGraphVtx*)elem_mat->data.ptr;
1701             idx0 = cvTsSimpleGraphAddVertex( sgraph, vtx + 1 );
1702
1703             pass_data = cvTsRandInt(rng) % 2;
1704             CV_CALL( idx = cvGraphAddVtx( graph, pass_data ? vtx : 0, &vtx2 ));
1705
1706             if( !pass_data && pure_vtx_size > 0 )
1707                 memcpy( vtx2 + 1, vtx + 1, pure_vtx_size );
1708
1709             vtx3 = cvGetGraphVtx( graph, idx );
1710
1711             CV_TS_SEQ_CHECK_CONDITION( CV_IS_SET_ELEM(vtx3) && vtx3->flags == idx &&
1712                 vtx3->first == 0 || idx == idx0 && vtx3 == vtx2 &&
1713                 (!pass_data || pure_vtx_size == 0 ||
1714                 memcmp(vtx3 + 1, vtx + 1, pure_vtx_size) == 0),
1715                 "The added element is not correct" );
1716
1717             CV_TS_SEQ_CHECK_CONDITION( (!first_free || first_free == (CvSetElem*)vtx3) &&
1718                                        (!next_free || graph->free_elems == next_free) &&
1719                                        graph->active_count == prev_vtx_count + 1,
1720                                        "The free node list is modified incorrectly" );
1721         }
1722         else if( op == 1 ) // remove vertex
1723         {
1724             idx = cvTsRandInt(rng) % sgraph->vtx->max_count;
1725             if( sgraph->vtx->free_count == sgraph->vtx->max_count || idx >= sgraph->vtx->count )
1726                 continue;
1727
1728             vtx_data = cvTsSimpleGraphFindVertex(sgraph, idx);
1729             if( vtx_data == 0 )
1730                 continue;
1731
1732             vtx_degree0 = cvTsSimpleGraphVertexDegree( sgraph, idx );
1733             first_free = graph->free_elems;
1734
1735             CV_CALL( vtx = cvGetGraphVtx( graph, idx ));
1736             CV_TS_SEQ_CHECK_CONDITION( CV_IS_SET_ELEM(vtx) && vtx->flags == idx &&
1737                     (pure_vtx_size == 0 || memcmp( vtx + 1, vtx_data, pure_vtx_size) == 0),
1738                     "cvGetGraphVtx returned wrong element" );
1739
1740             if( cvTsRandInt(rng) % 2 )
1741             {
1742                 CV_CALL( vtx_degree = cvGraphVtxDegreeByPtr( graph, vtx ));
1743                 CV_CALL( cvGraphRemoveVtxByPtr( graph, vtx ));
1744             }
1745             else
1746             {
1747                 CV_CALL( vtx_degree = cvGraphVtxDegree( graph, idx ));
1748                 CV_CALL( cvGraphRemoveVtx( graph, idx ));
1749             }
1750
1751             cvTsSimpleGraphRemoveVertex( sgraph, idx );
1752
1753             CV_TS_SEQ_CHECK_CONDITION( vtx_degree == vtx_degree0,
1754                 "Number of incident edges is different in two graph representations" );
1755
1756             CV_TS_SEQ_CHECK_CONDITION( !CV_IS_SET_ELEM(vtx) && !cvGetGraphVtx(graph, idx) &&
1757                                        (vtx->flags & CV_SET_ELEM_IDX_MASK) == idx,
1758                                        "cvGraphRemoveVtx[ByPtr] didn't release the vertex properly" );
1759
1760             CV_TS_SEQ_CHECK_CONDITION( graph->edges->active_count == prev_edge_count - vtx_degree,
1761                                        "cvGraphRemoveVtx[ByPtr] didn't remove all the incident edges "
1762                                        "(or removed some extra)" );
1763
1764             CV_TS_SEQ_CHECK_CONDITION( ((CvSetElem*)vtx)->next_free == first_free &&
1765                                        graph->free_elems == (CvSetElem*)vtx &&
1766                                        graph->active_count == prev_vtx_count - 1,
1767                                        "The free node list has not been updated properly" );
1768         }
1769         else if( op == 2 ) // add edge
1770         {
1771             int v_idx[2] = {0,0}, res = 0;
1772             int v_prev_degree[2] = {0,0}, v_degree[2] = {0,0};
1773
1774             if( sgraph->vtx->free_count >= sgraph->vtx->max_count-1 )
1775                 continue;
1776
1777             for( i = 0, k = 0; i < 10; i++ )
1778             {
1779                 int j = cvTsRandInt(rng) % sgraph->vtx->count;
1780                 vtx_data = cvTsSimpleGraphFindVertex( sgraph, j );
1781                 if( vtx_data )
1782                 {
1783                     v_idx[k] = j;
1784                     if( k == 0 )
1785                         k++;
1786                     else if( v_idx[0] != v_idx[1] &&
1787                         cvTsSimpleGraphFindEdge( sgraph, v_idx[0], v_idx[1] ) == 0 )
1788                     {
1789                         k++;
1790                         break;
1791                     }
1792                 }
1793             }
1794
1795             if( k < 2 )
1796                 continue;
1797
1798             first_free = graph->edges->free_elems;
1799             next_free = first_free ? first_free->next_free : 0;
1800
1801             CV_CALL( edge = cvFindGraphEdge( graph, v_idx[0], v_idx[1] ));
1802             CV_TS_SEQ_CHECK_CONDITION( edge == 0, "Extra edge appeared in the graph" );
1803
1804             if( pure_edge_size > 0 )
1805             {
1806                 elem_mat->cols = graph->edges->elem_size;
1807                 cvRandArr( rng, elem_mat, CV_RAND_UNI, cvScalarAll(0), cvScalarAll(255) );
1808             }
1809             edge = (CvGraphEdge*)elem_mat->data.ptr;
1810
1811             // assign some default weight that is easy to check for
1812             // consistensy, 'cause an edge weight is not stored
1813             // in the simple graph
1814             edge->weight = (float)(v_idx[0] + v_idx[1]);
1815             pass_data = cvTsRandInt(rng) % 2;
1816
1817             CV_CALL( vtx = cvGetGraphVtx( graph, v_idx[0] ));
1818             CV_CALL( vtx2 = cvGetGraphVtx( graph, v_idx[1] ));
1819             CV_TS_SEQ_CHECK_CONDITION( vtx != 0 && vtx2 != 0 && vtx->flags == v_idx[0] &&
1820                                 vtx2->flags == v_idx[1], "Some of the vertices are missing" );
1821
1822             if( cvTsRandInt(rng) % 2 )
1823             {
1824                 CV_CALL( v_prev_degree[0] = cvGraphVtxDegreeByPtr( graph, vtx ));
1825                 CV_CALL( v_prev_degree[1] = cvGraphVtxDegreeByPtr( graph, vtx2 ));
1826                 CV_CALL( res = cvGraphAddEdgeByPtr(graph, vtx, vtx2, pass_data ? edge : 0, &edge2));
1827                 CV_CALL( v_degree[0] = cvGraphVtxDegreeByPtr( graph, vtx ));
1828                 CV_CALL( v_degree[1] = cvGraphVtxDegreeByPtr( graph, vtx2 ));
1829             }
1830             else
1831             {
1832                 CV_CALL( v_prev_degree[0] = cvGraphVtxDegree( graph, v_idx[0] ));
1833                 CV_CALL( v_prev_degree[1] = cvGraphVtxDegree( graph, v_idx[1] ));
1834                 CV_CALL( res = cvGraphAddEdge(graph, v_idx[0], v_idx[1], pass_data ? edge : 0, &edge2));
1835                 CV_CALL( v_degree[0] = cvGraphVtxDegree( graph, v_idx[0] ));
1836                 CV_CALL( v_degree[1] = cvGraphVtxDegree( graph, v_idx[1] ));
1837             }
1838
1839             //edge3 = (CvGraphEdge*)cvGetSetElem( graph->edges, idx );
1840             CV_TS_SEQ_CHECK_CONDITION( res == 1 && edge2 != 0 && CV_IS_SET_ELEM(edge2) &&
1841                 (edge2->vtx[0] == vtx && edge2->vtx[1] == vtx2 ||
1842                 !CV_IS_GRAPH_ORIENTED(graph) && edge2->vtx[0] == vtx2 && edge2->vtx[1] == vtx) &&
1843                 (!pass_data || pure_edge_size == 0 || memcmp( edge2 + 1, edge + 1, pure_edge_size ) == 0),
1844                 "The edge has been added incorrectly" );
1845
1846             if( !pass_data )
1847             {
1848                 if( pure_edge_size > 0 )
1849                     memcpy( edge2 + 1, edge + 1, pure_edge_size );
1850                 edge2->weight = edge->weight;
1851             }
1852
1853             CV_TS_SEQ_CHECK_CONDITION( v_degree[0] == v_prev_degree[0] + 1 &&
1854                                        v_degree[1] == v_prev_degree[1] + 1,
1855                                        "The vertices lists have not been updated properly" );
1856
1857             cvTsSimpleGraphAddEdge( sgraph, v_idx[0], v_idx[1], edge + 1 );
1858
1859             CV_TS_SEQ_CHECK_CONDITION( (!first_free || first_free == (CvSetElem*)edge2) &&
1860                                        (!next_free || graph->edges->free_elems == next_free) &&
1861                                        graph->edges->active_count == prev_edge_count + 1,
1862                                        "The free node list is modified incorrectly" );
1863         }
1864         else if( op == 3 ) // find & remove edge
1865         {
1866             int v_idx[2] = {0,0}, by_ptr;
1867             int v_prev_degree[2] = {0,0}, v_degree[2] = {0,0};
1868
1869             if( sgraph->vtx->free_count >= sgraph->vtx->max_count-1 )
1870                 continue;
1871
1872             edge_data = 0;
1873             for( i = 0, k = 0; i < 10; i++ )
1874             {
1875                 int j = cvTsRandInt(rng) % sgraph->vtx->count;
1876                 vtx_data = cvTsSimpleGraphFindVertex( sgraph, j );
1877                 if( vtx_data )
1878                 {
1879                     v_idx[k] = j;
1880                     if( k == 0 )
1881                         k++;
1882                     else
1883                     {
1884                         edge_data = cvTsSimpleGraphFindEdge( sgraph, v_idx[0], v_idx[1] );
1885                         if( edge_data )
1886                         {
1887                             k++;
1888                             break;
1889                         }
1890                     }
1891                 }
1892             }
1893
1894             if( k < 2 )
1895                 continue;
1896
1897             by_ptr = cvTsRandInt(rng) % 2;
1898             first_free = graph->edges->free_elems;
1899
1900             CV_CALL( vtx = cvGetGraphVtx( graph, v_idx[0] ));
1901             CV_CALL( vtx2 = cvGetGraphVtx( graph, v_idx[1] ));
1902             CV_TS_SEQ_CHECK_CONDITION( vtx != 0 && vtx2 != 0 && vtx->flags == v_idx[0] &&
1903                                 vtx2->flags == v_idx[1], "Some of the vertices are missing" );
1904
1905             if( by_ptr )
1906             {
1907                 CV_CALL( edge = cvFindGraphEdgeByPtr( graph, vtx, vtx2 ));
1908                 CV_CALL( v_prev_degree[0] = cvGraphVtxDegreeByPtr( graph, vtx ));
1909                 CV_CALL( v_prev_degree[1] = cvGraphVtxDegreeByPtr( graph, vtx2 ));
1910             }
1911             else
1912             {
1913                 CV_CALL( edge = cvFindGraphEdge( graph, v_idx[0], v_idx[1] ));
1914                 CV_CALL( v_prev_degree[0] = cvGraphVtxDegree( graph, v_idx[0] ));
1915                 CV_CALL( v_prev_degree[1] = cvGraphVtxDegree( graph, v_idx[1] ));
1916             }
1917
1918             idx = edge->flags;
1919
1920             CV_TS_SEQ_CHECK_CONDITION( edge != 0 && edge->weight == v_idx[0] + v_idx[1] &&
1921                 (edge->vtx[0] == vtx && edge->vtx[1] == vtx2 ||
1922                 !CV_IS_GRAPH_ORIENTED(graph) && edge->vtx[1] == vtx && edge->vtx[0] == vtx2) &&
1923                 (pure_edge_size == 0 || memcmp(edge + 1, edge_data, pure_edge_size) == 0),
1924                 "An edge is missing or incorrect" );
1925
1926             if( by_ptr )
1927             {
1928                 CV_CALL( cvGraphRemoveEdgeByPtr( graph, vtx, vtx2 ));
1929                 CV_CALL( edge2 = cvFindGraphEdgeByPtr( graph, vtx, vtx2 ));
1930                 CV_CALL( v_degree[0] = cvGraphVtxDegreeByPtr( graph, vtx ));
1931                 CV_CALL( v_degree[1] = cvGraphVtxDegreeByPtr( graph, vtx2 ));
1932             }
1933             else
1934             {
1935                 CV_CALL( cvGraphRemoveEdge(graph, v_idx[0], v_idx[1] ));
1936                 CV_CALL( edge2 = cvFindGraphEdge( graph, v_idx[0], v_idx[1] ));
1937                 CV_CALL( v_degree[0] = cvGraphVtxDegree( graph, v_idx[0] ));
1938                 CV_CALL( v_degree[1] = cvGraphVtxDegree( graph, v_idx[1] ));
1939             }
1940
1941             CV_TS_SEQ_CHECK_CONDITION( !edge2 && !CV_IS_SET_ELEM(edge),
1942                                        "The edge has not been removed from the edge set" );
1943
1944             CV_TS_SEQ_CHECK_CONDITION( v_degree[0] == v_prev_degree[0] - 1 &&
1945                                        v_degree[1] == v_prev_degree[1] - 1,
1946                                        "The vertices lists have not been updated properly" );
1947
1948             cvTsSimpleGraphRemoveEdge( sgraph, v_idx[0], v_idx[1] );
1949
1950             CV_TS_SEQ_CHECK_CONDITION( graph->edges->free_elems == (CvSetElem*)edge &&
1951                                        graph->edges->free_elems->next_free == first_free &&
1952                                        graph->edges->active_count == prev_edge_count - 1,
1953                                        "The free edge list has not been modified properly" );
1954         }
1955
1956         //max_active_count = MAX( max_active_count, graph->active_count );
1957         //mean_active_count += graph->active_count;
1958
1959         CV_TS_SEQ_CHECK_CONDITION( graph->active_count == sgraph->vtx->max_count - sgraph->vtx->free_count &&
1960                                    graph->total >= graph->active_count &&
1961                                    (graph->total == 0 || graph->total >= prev_vtx_total),
1962                                    "The total number of graph vertices is not correct" );
1963
1964         CV_TS_SEQ_CHECK_CONDITION( graph->edges->total >= graph->edges->active_count &&
1965                                    (graph->edges->total == 0 || graph->edges->total >= prev_edge_total),
1966                                    "The total number of graph vertices is not correct" );
1967
1968         // CvGraph and simple graph do not neccessary have the same "total" (active & free) number,
1969         // so pass "graph->total" (or "graph->edges->total") to skip that check
1970         test_seq_block_consistence( struct_idx, (CvSeq*)graph, graph->total );
1971         test_seq_block_consistence( struct_idx, (CvSeq*)graph->edges, graph->edges->total );
1972         update_progressbar();
1973     }
1974
1975     code = 0;
1976     //ts->printf( CvTS::LOG, "\ngeneration %d. max_active_count = %d,\n\tmean_active_count = %d\n",
1977     //            gen, max_active_count, mean_active_count/iters );
1978
1979     __END__;
1980
1981     if( elem_mat )
1982         elem_mat->cols = 1; // just to skip a consistency check
1983     cvReleaseMat( &elem_mat );
1984
1985     return code;
1986 }
1987
1988
1989 void CxCore_GraphTest::run( int )
1990 {
1991     CvRNG* rng = ts->get_rng();
1992     int i, k;
1993     double t;
1994
1995     CV_FUNCNAME( "CxCore_GraphTest::run" );
1996
1997     __BEGIN__;
1998
1999     clear();
2000     test_progress = -1;
2001
2002     simple_struct = (void**)cvAlloc( struct_count * sizeof(simple_struct[0]) );
2003     memset( simple_struct, 0, struct_count * sizeof(simple_struct[0]) );
2004     cxcore_struct = (void**)cvAlloc( struct_count * sizeof(cxcore_struct[0]) );
2005     memset( cxcore_struct, 0, struct_count * sizeof(cxcore_struct[0]) );
2006
2007     for( gen = 0; gen < generations; gen++ )
2008     {
2009         struct_idx = iter = -1;
2010         t = cvTsRandReal(rng)*(max_log_storage_block_size - min_log_storage_block_size) + min_log_storage_block_size;
2011         storage = cvCreateMemStorage( cvRound( exp(t * CV_LOG2) ) );
2012
2013         for( i = 0; i < struct_count; i++ )
2014         {
2015             int pure_elem_size[2], elem_size[2];
2016             int is_oriented = (gen + i) % 2;
2017             for( k = 0; k < 2; k++ )
2018             {
2019                 t = cvTsRandReal(rng)*(max_log_elem_size - min_log_elem_size) + min_log_elem_size;
2020                 int pe = cvRound( exp(t * CV_LOG2) ) - 1; // pure_elem_size==0 does also make sense
2021                 int delta = k == 0 ? sizeof(CvGraphVtx) : sizeof(CvGraphEdge);
2022                 int e = pe + delta;
2023                 e = (e + sizeof(size_t) - 1) & ~(sizeof(size_t)-1);
2024                 e = MIN( e, (int)(storage->block_size - sizeof(CvMemBlock) -
2025                             sizeof(CvSeqBlock) - sizeof(void*)) );
2026                 pe = MIN(pe, e - delta);
2027                 pure_elem_size[k] = pe;
2028                 elem_size[k] = e;
2029             }
2030
2031             cvTsReleaseSimpleGraph( (CvTsSimpleGraph**)&simple_struct[i] );
2032             simple_struct[i] = cvTsCreateSimpleGraph( max_struct_size/4, pure_elem_size[0],
2033                                     pure_elem_size[1], is_oriented );
2034             CV_CALL( cxcore_struct[i] = cvCreateGraph( is_oriented ? CV_ORIENTED_GRAPH : CV_GRAPH,
2035                                                        sizeof(CvGraph), elem_size[0], elem_size[1],
2036                                                        storage ));
2037         }
2038
2039         if( test_graph_ops( iterations*10 ) < 0 )
2040             EXIT;
2041
2042         cvReleaseMemStorage( &storage );
2043     }
2044
2045     __END__;
2046 }
2047
2048 CxCore_GraphTest graph_test;
2049
2050
2051
2052 //////////// graph scan test //////////////
2053
2054 class CxCore_GraphScanTest : public CxCore_DynStructBaseTest
2055 {
2056 public:
2057     CxCore_GraphScanTest();
2058     void run( int );
2059
2060 protected:
2061     //int test_seq_block_consistence( int struct_idx );
2062     int create_random_graph( int );
2063 };
2064
2065
2066 CxCore_GraphScanTest::CxCore_GraphScanTest():
2067     CxCore_DynStructBaseTest( "ds-graphscan", "cvCreateGraph, "
2068                        "cvGraphAddVtx, cvGraphAddEdge, cvNextGraphItem, "
2069                        "cvCreateGraphScanner, cvReleaseGraphScanner" )
2070 {
2071     iterations = 100;
2072     struct_count = 1;
2073 }
2074
2075
2076 int CxCore_GraphScanTest::create_random_graph( int _struct_idx )
2077 {
2078     CvRNG* rng = ts->get_rng();
2079     int is_oriented = cvTsRandInt(rng) % 2;
2080     int i, vtx_count = cvTsRandInt(rng) % max_struct_size;
2081     int edge_count = cvTsRandInt(rng) % MAX(vtx_count*20, 1);
2082     CvGraph* graph;
2083
2084     CV_FUNCNAME( "CxCore_GraphScanTest::create_random_graph" );
2085
2086     __BEGIN__;
2087
2088     struct_idx = _struct_idx;
2089
2090     CV_CALL( cxcore_struct[_struct_idx] = graph = cvCreateGraph(
2091         is_oriented ? CV_ORIENTED_GRAPH : CV_GRAPH,
2092         sizeof(CvGraph), sizeof(CvGraphVtx), sizeof(CvGraphEdge), storage ));
2093
2094     for( i = 0; i < vtx_count; i++ )
2095         CV_CALL( cvGraphAddVtx( graph ));
2096
2097     assert( graph->active_count == vtx_count );
2098
2099     for( i = 0; i < edge_count; i++ )
2100     {
2101         int j = cvTsRandInt(rng) % vtx_count;
2102         int k = cvTsRandInt(rng) % vtx_count;
2103
2104         if( j != k )
2105             CV_CALL( cvGraphAddEdge( graph, j, k ));
2106     }
2107
2108     assert( graph->active_count == vtx_count && graph->edges->active_count <= edge_count );
2109
2110     __END__;
2111
2112     return 0;
2113 }
2114
2115
2116 void CxCore_GraphScanTest::run( int )
2117 {
2118     CvRNG* rng = ts->get_rng();
2119     CvGraphScanner* scanner = 0;
2120     CvMat* vtx_mask = 0, *edge_mask = 0;
2121     double t;
2122     int i;
2123
2124     CV_FUNCNAME( "CxCore_GraphTest::run" );
2125
2126     __BEGIN__;
2127
2128     clear();
2129     test_progress = -1;
2130
2131     cxcore_struct = (void**)cvAlloc( struct_count * sizeof(cxcore_struct[0]) );
2132     memset( cxcore_struct, 0, struct_count * sizeof(cxcore_struct[0]) );
2133
2134     for( gen = 0; gen < generations; gen++ )
2135     {
2136         struct_idx = iter = -1;
2137         t = cvTsRandReal(rng)*(max_log_storage_block_size - min_log_storage_block_size) + min_log_storage_block_size;
2138         storage = cvCreateMemStorage( cvRound( exp(t * CV_LOG2) ) );
2139
2140         if( gen == 0 )
2141         {
2142             // special regression test for one sample graph.
2143             // !!! ATTENTION !!! The test relies on the particular order of the inserted edges
2144             // (LIFO: the edge inserted last goes first in the list of incident edges).
2145             // if it is changed, the test will have to be modified.
2146
2147             int vtx_count = -1, edge_count = 0, edges[][3] =
2148             {
2149                 {0,4,'f'}, {0,1,'t'}, {1,4,'t'}, {1,2,'t'}, {2,3,'t'}, {4,3,'c'}, {3,1,'b'},
2150                 {5,7,'t'}, {7,5,'b'}, {5,6,'t'}, {6,0,'c'}, {7,6,'c'}, {6,4,'c'}, {-1,-1,0}
2151             };
2152
2153             CvGraph* graph;
2154             CV_CALL( graph = cvCreateGraph( CV_ORIENTED_GRAPH, sizeof(CvGraph),
2155                             sizeof(CvGraphVtx), sizeof(CvGraphEdge), storage ));
2156
2157             for( i = 0; edges[i][0] >= 0; i++ )
2158             {
2159                 vtx_count = MAX( vtx_count, edges[i][0] );
2160                 vtx_count = MAX( vtx_count, edges[i][1] );
2161             }
2162             vtx_count++;
2163
2164             for( i = 0; i < vtx_count; i++ )
2165                 CV_CALL( cvGraphAddVtx( graph ));
2166
2167             for( i = 0; edges[i][0] >= 0; i++ )
2168             {
2169                 CvGraphEdge* edge;
2170                 CV_CALL( cvGraphAddEdge( graph, edges[i][0], edges[i][1], 0, &edge ));
2171                 edge->weight = (float)edges[i][2];
2172             }
2173
2174             edge_count = i;
2175             CV_CALL( scanner = cvCreateGraphScanner( graph, 0, CV_GRAPH_ALL_ITEMS ));
2176
2177             for(;;)
2178             {
2179                 int code, a = -1, b = -1;
2180                 char* event = "";
2181                 CV_CALL( code = cvNextGraphItem( scanner ));
2182
2183                 switch( code )
2184                 {
2185                 case CV_GRAPH_VERTEX:
2186                     event = "Vertex";
2187                     vtx_count--;
2188                     a = cvGraphVtxIdx( graph, scanner->vtx );
2189                     break;
2190                 case CV_GRAPH_TREE_EDGE:
2191                     event = "Tree Edge";
2192                     edge_count--;
2193                     CV_TS_SEQ_CHECK_CONDITION( scanner->edge->weight == (float)'t',
2194                                                "Invalid edge type" );
2195                     a = cvGraphVtxIdx( graph, scanner->vtx );
2196                     b = cvGraphVtxIdx( graph, scanner->dst );
2197                     break;
2198                 case CV_GRAPH_BACK_EDGE:
2199                     event = "Back Edge";
2200                     edge_count--;
2201                     CV_TS_SEQ_CHECK_CONDITION( scanner->edge->weight == (float)'b',
2202                                                "Invalid edge type" );
2203                     a = cvGraphVtxIdx( graph, scanner->vtx );
2204                     b = cvGraphVtxIdx( graph, scanner->dst );
2205                     break;
2206                 case CV_GRAPH_CROSS_EDGE:
2207                     event = "Cross Edge";
2208                     edge_count--;
2209                     CV_TS_SEQ_CHECK_CONDITION( scanner->edge->weight == (float)'c',
2210                                                "Invalid edge type" );
2211                     a = cvGraphVtxIdx( graph, scanner->vtx );
2212                     b = cvGraphVtxIdx( graph, scanner->dst );
2213                     break;
2214                 case CV_GRAPH_FORWARD_EDGE:
2215                     event = "Forward Edge";
2216                     edge_count--;
2217                     CV_TS_SEQ_CHECK_CONDITION( scanner->edge->weight == (float)'f',
2218                                                "Invalid edge type" );
2219                     a = cvGraphVtxIdx( graph, scanner->vtx );
2220                     b = cvGraphVtxIdx( graph, scanner->dst );
2221                     break;
2222                 case CV_GRAPH_BACKTRACKING:
2223                     event = "Backtracking";
2224                     a = cvGraphVtxIdx( graph, scanner->vtx );
2225                     break;
2226                 case CV_GRAPH_NEW_TREE:
2227                     event = "New search tree";
2228                     break;
2229                 case CV_GRAPH_OVER:
2230                     event = "End of procedure";
2231                     break;
2232                 default:
2233                     CV_TS_SEQ_CHECK_CONDITION( 0, "Invalid code appeared during graph scan" );
2234                 }
2235
2236                 ts->printf( CvTS::LOG, "%s", event );
2237                 if( a >= 0 )
2238                 {
2239                     if( b >= 0 )
2240                         ts->printf( CvTS::LOG, ": (%d,%d)", a, b );
2241                     else
2242                         ts->printf( CvTS::LOG, ": %d", a );
2243                 }
2244
2245                 ts->printf( CvTS::LOG, "\n" );
2246
2247                 if( code < 0 )
2248                     break;
2249             }
2250
2251             CV_TS_SEQ_CHECK_CONDITION( vtx_count == 0 && edge_count == 0,
2252                 "Not every vertex/edge has been visited" );
2253             update_progressbar();
2254         }
2255
2256         // for a random graph the test just checks that every graph vertex and
2257         // every edge is vitisted during the scan
2258         for( iter = 0; iter < iterations; iter++ )
2259         {
2260             create_random_graph(0);
2261             CvGraph* graph = (CvGraph*)cxcore_struct[0];
2262
2263             // iterate twice to check that scanner doesn't damage the graph
2264             for( i = 0; i < 2; i++ )
2265             {
2266                 CvGraphVtx* start_vtx = cvTsRandInt(rng) % 2 || graph->active_count == 0 ? 0 :
2267                     cvGetGraphVtx( graph, cvTsRandInt(rng) % graph->active_count );
2268
2269                 CV_CALL( scanner = cvCreateGraphScanner( graph, start_vtx, CV_GRAPH_ALL_ITEMS ));
2270
2271                 if( !vtx_mask || vtx_mask->cols < graph->active_count )
2272                 {
2273                     cvReleaseMat( &vtx_mask );
2274                     CV_CALL( vtx_mask = cvCreateMat( 1, graph->active_count, CV_8UC1 ));
2275                 }
2276
2277                 if( !edge_mask || edge_mask->cols < graph->edges->active_count )
2278                 {
2279                     cvReleaseMat( &edge_mask );
2280                     CV_CALL( edge_mask = cvCreateMat( 1, graph->edges->active_count, CV_8UC1 ));
2281                 }
2282
2283                 cvZero( vtx_mask );
2284                 cvZero( edge_mask );
2285
2286                 for(;;)
2287                 {
2288                     int code;
2289                     CV_CALL( code = cvNextGraphItem( scanner ));
2290
2291                     if( code == CV_GRAPH_OVER )
2292                         break;
2293                     else if( code & CV_GRAPH_ANY_EDGE )
2294                     {
2295                         int edge_idx = scanner->edge->flags & CV_SET_ELEM_IDX_MASK;
2296
2297                         CV_TS_SEQ_CHECK_CONDITION( edge_idx < graph->edges->active_count &&
2298                                                    edge_mask->data.ptr[edge_idx] == 0,
2299                                                    "The edge is not found or visited for the second time" );
2300                         edge_mask->data.ptr[edge_idx] = 1;
2301                     }
2302                     else if( code & CV_GRAPH_VERTEX )
2303                     {
2304                         int vtx_idx = scanner->vtx->flags & CV_SET_ELEM_IDX_MASK;
2305
2306                         CV_TS_SEQ_CHECK_CONDITION( vtx_idx < graph->active_count &&
2307                                                    vtx_mask->data.ptr[vtx_idx] == 0,
2308                                                    "The vtx is not found or visited for the second time" );
2309                         vtx_mask->data.ptr[vtx_idx] = 1;
2310                     }
2311                 }
2312
2313                 cvReleaseGraphScanner( &scanner );
2314
2315                 CV_TS_SEQ_CHECK_CONDITION( cvNorm(vtx_mask,0,CV_L1) == graph->active_count &&
2316                                            cvNorm(edge_mask,0,CV_L1) == graph->edges->active_count,
2317                                            "Some vertices or edges have not been visited" );
2318                 update_progressbar();
2319             }
2320             cvClearMemStorage( storage );
2321         }
2322
2323         cvReleaseMemStorage( &storage );
2324     }
2325
2326     __END__;
2327
2328     cvReleaseGraphScanner( &scanner );
2329     cvReleaseMat( &vtx_mask );
2330     cvReleaseMat( &edge_mask );
2331 }
2332
2333 CxCore_GraphScanTest graphscan_test;
2334
2335 /* End of file. */