← Back to branch summary

~paparazzi-uav/paparazzi/v5.0-manual

« back to all changes in this revision

Viewing changes to sw/ext/opencv_bebop/opencv/modules/core/test/test_ds.cpp

  • Committer: Paparazzi buildbot
  • Date: 2016-05-18 15:00:29 UTC
  • Revision ID: felix.ruess+docbot@gmail.com-20160518150029-e8lgzi5kvb4p7un9
Manual import commit 4b8bbb730080dac23cf816b98908dacfabe2a8ec from v5.0 branch.

Show diffs side-by-side

added added

removed removed

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