src/libswift_udp/tests/binstest3.cpp

   1 /*
   2  *  binstest3.cpp
   3  *  serp++
   4  *
   5  *  Created by Victor Grishchenko on 3/22/09.
   6  *  Copyright 2009-2012 TECHNISCHE UNIVERSITEIT DELFT. All rights reserved.
   7  *
   8  *  ==========================
   9  *  Extended by Arno and Riccardo to hunt a bug in find_complement() with
  10  *  a range parameter.
  11  */
  12 #include "binmap.h"
  13 #include "binheap.h"
  14
  15 #include <time.h>
  16 #include <set>
  17 #include <gtest/gtest.h>
  18
  19
  20 using namespace swift;
  21
  22
  23 TEST(BinsTest,FindFiltered) {
  24
  25     binmap_t data, filter;
  26     data.set(bin_t(2,0));
  27     data.set(bin_t(2,2));
  28     data.set(bin_t(1,7));
  29     filter.set(bin_t(4,0));
  30     filter.reset(bin_t(2,1));
  31     filter.reset(bin_t(1,4));
  32     filter.reset(bin_t(0,13));
  33
  34     bin_t x = binmap_t::find_complement(data, filter, bin_t(4,0), 0);
  35     EXPECT_EQ(bin_t(0,12),x);
  36
  37 }
  38
  39 TEST(BinsTest,FindFiltered1b) {
  40
  41     binmap_t data, filter;
  42     data.set(bin_t(2,0));
  43     data.set(bin_t(2,2));
  44     data.set(bin_t(1,7));
  45     filter.set(bin_t(4,0));
  46     filter.reset(bin_t(2,1));
  47     filter.reset(bin_t(1,4));
  48     filter.reset(bin_t(0,13));
  49
  50     char binstr[32];
  51
  52     bin_t s = bin_t(3,1);
  53     fprintf(stderr,"Searching 0,12 from %s ", s.base_left().str(binstr ) );
  54     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
  55
  56     bin_t x = binmap_t::find_complement(data, filter, s, 0);
  57     EXPECT_EQ(bin_t(0,12),x);
  58
  59 }
  60
  61
  62 TEST(BinsTest,FindFiltered1c) {
  63
  64     binmap_t data, filter;
  65     data.set(bin_t(2,0));
  66     data.set(bin_t(2,2));
  67     data.set(bin_t(1,7));
  68
  69     filter.set(bin_t(4,0));
  70     filter.reset(bin_t(2,1));
  71     filter.reset(bin_t(1,4));
  72     //filter.reset(bin_t(0,13));
  73
  74     char binstr[32];
  75
  76     bin_t s = bin_t(3,1);
  77     fprintf(stderr,"Searching 0,12x from %s ", s.base_left().str(binstr ) );
  78     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
  79
  80     bin_t x = binmap_t::find_complement(data, filter, s, 0);
  81     EXPECT_EQ(bin_t(0,12),x);
  82
  83 }
  84
  85
  86 TEST(BinsTest,FindFiltered2) {
  87
  88     binmap_t data, filter;
  89     for(int i=0; i<1024; i+=2)
  90         data.set(bin_t(0,i));
  91     for(int j=0; j<1024; j+=2)
  92         filter.set(bin_t(0,j));
  93
  94     fprintf(stderr,"test: width %d\n", filter.cells_number() );
  95     fprintf(stderr,"test: empty %llu\n", filter.find_empty().toUInt() );
  96
  97
  98     data.reset(bin_t(0,500));
  99     EXPECT_EQ(bin_t(0,500),binmap_t::find_complement(data, filter, bin_t(10,0), 0).base_left());
 100     data.set(bin_t(0,500));
 101     EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(10,0), 0).base_left());
 102
 103 }
 104
 105
 106 // Range is strict subtree
 107 TEST(BinsTest,FindFiltered3) {
 108
 109     binmap_t data, filter;
 110     for(int i=0; i<1024; i+=2)
 111         data.set(bin_t(0,i));
 112     for(int j=0; j<1024; j+=2)
 113         filter.set(bin_t(0,j));
 114     data.reset(bin_t(0,500));
 115     EXPECT_EQ(bin_t(0,500),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
 116     data.set(bin_t(0,500));
 117     EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
 118
 119 }
 120
 121 // 1036 leaf tree
 122
 123 TEST(BinsTest,FindFiltered4) {
 124
 125     binmap_t data, filter;
 126     for(int i=0; i<1036; i+=2)
 127         data.set(bin_t(0,i));
 128     for(int j=0; j<1036; j+=2)
 129         filter.set(bin_t(0,j));
 130     data.reset(bin_t(0,500));
 131     EXPECT_EQ(bin_t(0,500),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
 132     data.set(bin_t(0,500));
 133     EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
 134
 135 }
 136
 137 // Make 8 bin hole in 1036 tree
 138
 139 TEST(BinsTest,FindFiltered5) {
 140
 141     binmap_t data, filter;
 142     for(int i=0; i<1036; i++) //completely full
 143         data.set(bin_t(0,i));
 144     for(int j=0; j<1036; j++)
 145         filter.set(bin_t(0,j));
 146
 147     for (int j=496; j<=503; j++)
 148         data.reset(bin_t(0,j));
 149
 150     EXPECT_EQ(bin_t(3,62),binmap_t::find_complement(data, filter, bin_t(9,0), 0) );
 151     EXPECT_EQ(bin_t(0,496),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
 152 }
 153
 154
 155 // Use simple example tree from RFC
 156 TEST(BinsTest,FindFiltered6) {
 157
 158     binmap_t data, filter;
 159     for(int i=0; i<14; i+=2)  //completely full example tree
 160         data.set(bin_t(i));
 161     for(int j=0; j<14; j+=2)
 162         filter.set(bin_t(j));
 163
 164     for (int j=4; j<=6; j+=2) // reset leaves 4 and 6 (int)
 165         data.reset(bin_t(j));
 166
 167     EXPECT_EQ(bin_t(1,1),binmap_t::find_complement(data, filter, bin_t(2,0), 0) );
 168     EXPECT_EQ(bin_t(0,2),binmap_t::find_complement(data, filter, bin_t(2,0), 0).base_left());
 169 }
 170
 171
 172 // diff in right tree, range is left tree
 173 TEST(BinsTest,FindFiltered7) {
 174
 175     binmap_t data, filter;
 176     for(int i=0; i<14; i+=2)  //completely full example tree
 177         data.set(bin_t(i));
 178     data.reset(bin_t(4));         // clear 4
 179     for(int j=0; j<14; j+=2)
 180         filter.set(bin_t(j));
 181     filter.reset(bin_t(4));
 182
 183     for (int j=8; j<=10; j+=2)  // make diff out of range
 184         data.reset(bin_t(j));
 185
 186     EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(2,0), 0) );
 187     EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(2,0), 0).base_left());
 188 }
 189
 190
 191
 192 // diff in left tree, range is right tree
 193 TEST(BinsTest,FindFiltered8) {
 194
 195     binmap_t data, filter;
 196     for(int i=0; i<14; i+=2)  //completely full example tree
 197         data.set(bin_t(i));
 198     data.reset(bin_t(4));         // clear 4
 199     for(int j=0; j<14; j+=2)
 200         filter.set(bin_t(j));
 201     filter.reset(bin_t(4));
 202
 203     for (int j=4; j<=6; j+=2)   // make diff out of range
 204         data.reset(bin_t(j));
 205
 206     EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(2,1), 0) );
 207     EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(2,1), 0).base_left());
 208 }
 209
 210
 211 // reverse empty/full
 212 TEST(BinsTest,FindFiltered9) {
 213
 214     binmap_t data, filter;
 215     for(int i=0; i<14; i+=2)  //completely empty example tree
 216         data.reset(bin_t(i));
 217     data.set(bin_t(4));   // clear 4
 218     for(int j=0; j<14; j+=2)
 219         filter.reset(bin_t(j));
 220     filter.set(bin_t(4));
 221
 222     for (int j=4; j<=6; j+=2)   // make diff out of range
 223         data.set(bin_t(j));
 224
 225     EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(2,1), 0) );
 226     EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(2,1), 0).base_left());
 227 }
 228
 229
 230 // Make 8 bin hole in 999 tree, left subtree
 231
 232 TEST(BinsTest,FindFiltered10) {
 233
 234     binmap_t data, filter;
 235     for(int i=0; i<999; i++) //completely full
 236         data.set(bin_t(0,i));
 237     for(int j=0; j<999; j++)
 238         filter.set(bin_t(0,j));
 239
 240     for (int j=496; j<=503; j++)
 241         data.reset(bin_t(0,j));
 242
 243     EXPECT_EQ(bin_t(3,62),binmap_t::find_complement(data, filter, bin_t(9,0), 0) );
 244     EXPECT_EQ(bin_t(0,496),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
 245 }
 246
 247
 248 // Make 8 bin hole in 999 tree, right subtree, does not start a 8-bin substree
 249 TEST(BinsTest,FindFiltered11) {
 250
 251     binmap_t data, filter;
 252     for(int i=0; i<999; i++) //completely full
 253         data.set(bin_t(0,i));
 254     for(int j=0; j<999; j++)
 255         filter.set(bin_t(0,j));
 256
 257     for (int j=514; j<=521; j++)
 258         data.reset(bin_t(0,j));
 259
 260     EXPECT_EQ(bin_t(1,257),binmap_t::find_complement(data, filter, bin_t(9,1), 0) );
 261     EXPECT_EQ(bin_t(0,514),binmap_t::find_complement(data, filter, bin_t(9,1), 0).base_left());
 262 }
 263
 264 // Make 8 bin hole in 999 tree, move hole
 265 TEST(BinsTest,FindFiltered12) {
 266
 267     binmap_t data, filter;
 268     for(int i=0; i<999; i++) //completely full
 269         data.set(bin_t(0,i));
 270     for(int j=0; j<999; j++)
 271         filter.set(bin_t(0,j));
 272
 273     for (int x=0; x<999-8; x++)
 274     {
 275         fprintf(stderr,"x%u ", x);
 276         for (int j=x; j<=x+7; j++)
 277                 data.reset(bin_t(0,j));
 278
 279         int subtree = (x <= 511) ? 0 : 1;
 280         EXPECT_EQ(bin_t(0,x),binmap_t::find_complement(data, filter, bin_t(9,subtree), 0).base_left());
 281
 282         // Restore
 283         for (int j=x; j<=x+7; j++) {
 284                 data.set(bin_t(0,j));
 285         }
 286     }
 287 }
 288
 289
 290 // Make 8 bin hole in sparse 999 tree, move hole
 291 TEST(BinsTest,FindFiltered13) {
 292
 293     binmap_t data, filter;
 294     for(int i=0; i<999; i+=2) // sparse
 295         data.set(bin_t(0,i));
 296     for(int j=0; j<999; j+=2)
 297         filter.set(bin_t(0,j));
 298
 299     for (int x=0; x<999-8; x++)
 300     {
 301         fprintf(stderr,"x%u ", x);
 302         for (int j=x; j<=x+7; j++)
 303                 data.reset(bin_t(0,j));
 304
 305         int y = (x % 2) ? x+1 : x;
 306         int subtree = (x <= 511) ? 0 : 1;
 307         if (x < 511)
 308                 EXPECT_EQ(bin_t(0,y),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
 309         else if (x == 511) // sparse bitmap 101010101..., so actual diff in next subtree
 310                 EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
 311         else
 312                 EXPECT_EQ(bin_t(0,y),binmap_t::find_complement(data, filter, bin_t(9,1), 0).base_left());
 313
 314
 315         for(int i=0; i<999; i+=2) // sparse
 316             data.set(bin_t(0,i));
 317     }
 318 }
 319
 320
 321 // Make 8 bin hole in sparse 999 tree, move hole
 322 TEST(BinsTest,FindFiltered14) {
 323
 324     binmap_t data, filter;
 325     for(int i=0; i<999; i+=2) // sparse
 326         data.set(bin_t(0,i));
 327     for(int j=0; j<999; j+=2)
 328         filter.set(bin_t(0,j));
 329
 330     // Add other diff
 331     filter.set(bin_t(0,995));
 332
 333     for (int x=0; x<999-8; x++)
 334     {
 335         fprintf(stderr,"x%u ", x);
 336         for (int j=x; j<=x+7; j++)
 337                 data.reset(bin_t(0,j));
 338
 339         int y = (x % 2) ? x+1 : x;
 340         int subtree = (x <= 511) ? 0 : 1;
 341         if (x < 511)
 342                 EXPECT_EQ(bin_t(0,y),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
 343         else if (x == 511) // sparse bitmap 101010101..., so actual diff in next subtree
 344                 EXPECT_EQ(bin_t::NONE,binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
 345         else
 346                 EXPECT_EQ(bin_t(0,y),binmap_t::find_complement(data, filter, bin_t(9,1), 0).base_left());
 347
 348
 349         for(int i=0; i<999; i+=2) // sparse
 350             data.set(bin_t(0,i));
 351     }
 352 }
 353
 354
 355
 356 // Make holes at 292, problematic in a specific experiment
 357 TEST(BinsTest,FindFiltered15) {
 358
 359     binmap_t data, filter;
 360     for(int i=0; i<999; i++) // completely full
 361         data.set(bin_t(0,i));
 362     for(int j=0; j<999; j++)
 363         filter.set(bin_t(0,j));
 364
 365     data.reset(bin_t(292));
 366     data.reset(bin_t(296));
 367     data.reset(bin_t(514));
 368     data.reset(bin_t(998));
 369
 370         EXPECT_EQ(bin_t(292),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
 371 }
 372
 373
 374
 375 // VOD like. Make first hole at 292.
 376 TEST(BinsTest,FindFiltered16) {
 377
 378     binmap_t data, filter;
 379     for(int i=0; i<292/2; i++) // prefix full
 380         data.set(bin_t(0,i));
 381     for(int i=147; i<999; i+=21) // postfix sparse
 382     {
 383         for (int x=0; x<8; x++)
 384                 data.set(bin_t(0,i+x));
 385     }
 386
 387     for(int j=0; j<999; j++)
 388         filter.set(bin_t(0,j));
 389
 390         EXPECT_EQ(bin_t(292),binmap_t::find_complement(data, filter, bin_t(9,0), 0).base_left());
 391 }
 392
 393
 394 // VOD like. Make first hole at 292.
 395 TEST(BinsTest,FindFiltered17) {
 396
 397     binmap_t offer, ack_hint_out;
 398     for(int i=0; i<999; i++) // offer completely full
 399         offer.set(bin_t(0,i));
 400
 401     for(int i=0; i<292/2; i++) // request prefix full
 402         ack_hint_out.set(bin_t(0,i));
 403     for(int i=147; i<999; i+=21) // request postfix sparse
 404     {
 405         for (int x=0; x<8; x++)
 406                 ack_hint_out.set(bin_t(0,i+x));
 407     }
 408
 409         binmap_t binmap;
 410
 411         // report the first bin we find
 412         int layer = 0;
 413         bin_t::uint_t twist = 0;
 414         bin_t hint = bin_t::NONE;
 415         while (hint.is_none() && layer <10)
 416         {
 417                 char binstr[32];
 418
 419                 bin_t curr = bin_t(layer++,0);
 420                 binmap.fill(offer);
 421                 binmap_t::copy(binmap, ack_hint_out, curr);
 422                 hint = binmap_t::find_complement(binmap, offer, twist);
 423                 binmap.clear();
 424         }
 425
 426         EXPECT_EQ(bin_t(292),hint);
 427 }
 428
 429
 430 // VOD like. Make first hole at 292. Twisting + patching holes
 431 TEST(BinsTest,FindFiltered19) {
 432
 433     binmap_t offer, ack_hint_out;
 434     for(int i=0; i<999; i++) // offer completely full
 435         offer.set(bin_t(0,i));
 436
 437     for(int i=0; i<292/2; i++) // request prefix full
 438         ack_hint_out.set(bin_t(0,i));
 439     for(int i=147; i<999; i+=21) // request postfix sparse
 440     {
 441         for (int x=0; x<8; x++)
 442                 ack_hint_out.set(bin_t(0,i+x));
 443     }
 444
 445         binmap_t binmap;
 446
 447         int layer = 0;
 448         bin_t::uint_t twist = 0;
 449         bin_t hint = bin_t::NONE;
 450         while (!hint.contains(bin_t(292)))
 451         {
 452                 char binstr[32];
 453
 454                 twist = rand();
 455
 456                 bin_t curr = bin_t(layer,0);
 457                 if (layer < 10)
 458                         layer++;
 459
 460                 binmap.fill(offer);
 461                 binmap_t::copy(binmap, ack_hint_out, curr);
 462                 hint = binmap_t::find_complement(binmap, offer, twist);
 463
 464                 if (!hint.is_none())
 465                         fprintf(stderr,"Found alt ");
 466                 binmap.clear();
 467
 468                 //patch hole
 469                 ack_hint_out.set(hint);
 470         }
 471
 472         char binstr[32],binstr2[32];
 473         EXPECT_EQ(bin_t(292),hint);
 474 }
 475
 476
 477 void create_ack_hint_out(binmap_t &ack_hint_out)
 478 {
 479         ack_hint_out.clear();
 480     for(int i=0; i<292/2; i++) // request prefix full
 481         ack_hint_out.set(bin_t(0,i));
 482     for(int i=147; i<999; i+=21) // request postfix sparse
 483     {
 484         for (int x=0; x<8; x++)
 485                 ack_hint_out.set(bin_t(0,i+x));
 486     }
 487 }
 488
 489
 490
 491 // VOD like. Make first hole at 292. Twisting + patching holes. Stalled
 492 // at Playbackpos, looking increasingly higher layers.
 493 TEST(BinsTest,FindFiltered20) {
 494
 495     binmap_t offer, ack_hint_out;
 496     for(int i=0; i<999; i++) // offer completely full
 497         offer.set(bin_t(0,i));
 498
 499     create_ack_hint_out(ack_hint_out);
 500
 501         binmap_t binmap;
 502
 503         int layer = 0;
 504         bin_t::uint_t twist = 0;
 505         bin_t hint = bin_t::NONE;
 506
 507         for (layer=0; layer<=9; layer++)
 508         {
 509                 fprintf(stderr,"Layer %d\n", layer );
 510                 while (!hint.contains(bin_t(292)))
 511                 {
 512                         char binstr[32];
 513
 514                         twist = rand();
 515
 516                         bin_t curr = bin_t(0,292/2);
 517                         for (int p=0; p<layer; p++)
 518                                 curr = curr.parent();
 519
 520                         binmap.fill(offer);
 521                         binmap_t::copy(binmap, ack_hint_out, curr);
 522                         hint = binmap_t::find_complement(binmap, offer, twist);
 523
 524                         if (!hint.is_none())
 525                                 fprintf(stderr,"Found alt %s ", hint.str(binstr) );
 526                         binmap.clear();
 527
 528                         //patch hole
 529                         ack_hint_out.set(hint);
 530                 }
 531                 create_ack_hint_out(ack_hint_out);
 532         }
 533
 534         EXPECT_EQ(bin_t(292),hint);
 535 }
 536
 537
 538 void DoFindFilteredRiccardo(bin_t::uint_t twist)
 539 {
 540     binmap_t data, filter;
 541
 542     for(int i=0; i<1024; i+=2)
 543         filter.set(bin_t(0,i));
 544
 545     char binstr[32];
 546
 547     // Case 1
 548     bin_t s(1,2);
 549     data.set(s);
 550
 551     fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
 552     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 553
 554     s = bin_t(2,1);
 555     fprintf(stderr,"Searching 0,6 from %s ", s.base_left().str(binstr ) );
 556     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 557
 558     bin_t got = binmap_t::find_complement(data, filter, s, twist).base_left();
 559     EXPECT_EQ(bin_t(0,6),got);
 560     EXPECT_EQ(true,s.contains(got));
 561
 562
 563     // Case 2
 564     s = bin_t(1,8);
 565     data.set(s);
 566
 567     fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
 568     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 569
 570     s = bin_t(2,4);
 571     fprintf(stderr,"Searching 0,18 from %s ", s.base_left().str(binstr ) );
 572     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 573
 574     got = binmap_t::find_complement(data, filter, s, twist).base_left();
 575     EXPECT_EQ(bin_t(0,18),got);
 576     EXPECT_EQ(true,s.contains(got));
 577
 578
 579     // Case 5
 580     s = bin_t(1,80);
 581     data.set(s);
 582
 583     fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
 584     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 585
 586     s = bin_t(2,40);
 587     fprintf(stderr,"Searching 0,162 from %s ", s.base_left().str(binstr ) );
 588     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 589
 590     got = binmap_t::find_complement(data, filter, s, twist).base_left();
 591     EXPECT_EQ(bin_t(0,162),got);
 592     EXPECT_EQ(true,s.contains(got));
 593
 594     // Case 6
 595
 596     s = bin_t(1,84);
 597     data.set(s);
 598
 599     fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
 600     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 601
 602     s = bin_t(2,42);
 603     fprintf(stderr,"Searching 0,168 from %s ", s.base_left().str(binstr ) );
 604     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 605
 606     got = binmap_t::find_complement(data, filter, s, twist).base_left();
 607     EXPECT_EQ(bin_t(0,170),got);
 608     EXPECT_EQ(true,s.contains(got));
 609
 610
 611     // Case 3
 612     s = bin_t(1,86);
 613     data.set(s);
 614
 615     fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
 616     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 617
 618     s = bin_t(2,43);
 619     fprintf(stderr,"Searching 0,174 from %s ", s.base_left().str(binstr ) );
 620     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 621
 622     got = binmap_t::find_complement(data, filter, s, twist).base_left();
 623     EXPECT_EQ(bin_t(0,174),got);
 624     EXPECT_EQ(true,s.contains(got));
 625
 626
 627     // Case 7
 628     s = bin_t(1,90);
 629     data.set(s);
 630
 631     fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
 632     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 633
 634
 635     s = bin_t(2,45);
 636     fprintf(stderr,"Searching 0,182 from %s ", s.base_left().str(binstr ) );
 637     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 638
 639     got = binmap_t::find_complement(data, filter, s, twist).base_left();
 640     EXPECT_EQ(bin_t(0,182),got);
 641     EXPECT_EQ(true,s.contains(got));
 642
 643
 644     // Case 4
 645     s = bin_t(1,92);
 646     data.set(s);
 647
 648     fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
 649     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 650
 651     s = bin_t(2,46);
 652     fprintf(stderr,"Searching 0,184 from %s ", s.base_left().str(binstr ) );
 653     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 654
 655     got = binmap_t::find_complement(data, filter, s, twist).base_left();
 656     EXPECT_EQ(bin_t(0,186),got);
 657     EXPECT_EQ(true,s.contains(got));
 658
 659
 660     // Case 8
 661     s = bin_t(1,94);
 662     data.set(s);
 663
 664     fprintf(stderr,"Setting from %s ", s.base_left().str(binstr ) );
 665     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 666
 667     s = bin_t(2,47);
 668     fprintf(stderr,"Searching 0,188 from %s ", s.base_left().str(binstr ) );
 669     fprintf(stderr,"to %s\n", s.base_right().str(binstr ) );
 670
 671     got = binmap_t::find_complement(data, filter, s, twist).base_left();
 672     EXPECT_EQ(bin_t(0,190),got);
 673     EXPECT_EQ(true,s.contains(got));
 674 }
 675
 676
 677 TEST(BinsTest,FindFilteredRiccardo3) {
 678
 679         DoFindFilteredRiccardo(0);
 680 }
 681
 682
 683 TEST(BinsTest,FindFilteredRiccardo3Twist) {
 684
 685         DoFindFilteredRiccardo( rand() );
 686 }
 687
 688
 689
 690
 691
 692
 693 int main (int argc, char** argv) {
 694         testing::InitGoogleTest(&argc, argv);
 695         return RUN_ALL_TESTS();
 696 }