tests/binstest2.cpp

   1 /*
   2  *  binstest.cpp
   3  *  serp++
   4  *
   5  *  Created by Victor Grishchenko on 3/22/09.
   6  *  Copyright 2009 Delft University of Technology. All rights reserved.
   7  *
   8  */
   9 #include <time.h>
  10 #include <set>
  11 #include <gtest/gtest.h>
  12 #include "bins.h"
  13
  14
  15 TEST(BinsTest,Routines) {
  16
  17     uint32_t cell = (3<<10) | (3<<14) | (3<<0);
  18     uint16_t correct = (1<<5) | (1<<7) | (1<<0);
  19     uint16_t joined  = binmap_t::join32to16(cell);
  20     EXPECT_EQ(correct,joined);
  21
  22     uint32_t split = binmap_t::split16to32(correct);
  23     EXPECT_EQ(cell,split);
  24
  25     EXPECT_EQ(binmap_t::NOJOIN,binmap_t::join32to16(cell|4));
  26
  27 }
  28
  29 TEST(BinsTest,SetGet) {
  30
  31     binmap_t bs;
  32     bin64_t b3(1,0), b2(0,1), b4(0,2), b6(1,1), b7(2,0);
  33     bs.set(b3);
  34     //bs.dump("set done");
  35     EXPECT_EQ(binmap_t::FILLED,bs.get(b3));
  36     //bs.dump("set checkd");
  37     EXPECT_EQ(binmap_t::FILLED,bs.get(b2));
  38     //bs.dump("get b2 done");
  39     EXPECT_EQ(binmap_t::FILLED,bs.get(b3));
  40     //bs.dump("get b3 done");
  41     EXPECT_EQ(binmap_t::EMPTY,bs.get(b4));
  42     EXPECT_EQ(binmap_t::EMPTY,bs.get(b6));
  43     EXPECT_NE(binmap_t::FILLED,bs.get(b7));
  44     EXPECT_NE(binmap_t::EMPTY,bs.get(b7));
  45     EXPECT_EQ(binmap_t::FILLED,bs.get(b3));
  46     bs.set(bin64_t(1,1));
  47     EXPECT_EQ(binmap_t::FILLED,bs.get(bin64_t(2,0)));
  48
  49 }
  50
  51 TEST(BinsTest,Iterator) {
  52     binmap_t b;
  53     b.set(bin64_t(3,1));
  54     iterator i(&b,bin64_t(0,0),false);
  55     while (!i.solid())
  56         i.left();
  57     EXPECT_EQ(bin64_t(3,0),i.bin());
  58     EXPECT_EQ(false,i.deep());
  59     EXPECT_EQ(true,i.solid());
  60     EXPECT_EQ(binmap_t::EMPTY,*i);
  61     i.next();
  62     EXPECT_EQ(bin64_t(3,1),i.bin());
  63     EXPECT_EQ(false,i.deep());
  64     EXPECT_EQ(true,i.solid());
  65     EXPECT_EQ(binmap_t::FILLED,*i);
  66     i.next();
  67     EXPECT_TRUE(i.end());
  68 }
  69
  70 TEST(BinsTest,Chess) {
  71     binmap_t chess16;
  72     for(int i=0; i<15; i++)
  73         chess16.set(bin64_t(0,i), (i&1)?binmap_t::FILLED:binmap_t::EMPTY);
  74     chess16.set(bin64_t(0,15), binmap_t::FILLED);
  75     for(int i=0; i<16; i++)
  76         EXPECT_EQ((i&1)?binmap_t::FILLED:binmap_t::EMPTY, chess16.get(bin64_t(0,i)));
  77     EXPECT_NE(binmap_t::FILLED,chess16.get(bin64_t(4,0)));
  78     EXPECT_NE(binmap_t::EMPTY,chess16.get(bin64_t(4,0)));
  79     for(int i=0; i<16; i+=2)
  80         chess16.set(bin64_t(0,i), binmap_t::FILLED);
  81     EXPECT_EQ(binmap_t::FILLED,chess16.get(bin64_t(4,0)));
  82     EXPECT_EQ(binmap_t::FILLED,chess16.get(bin64_t(2,3)));
  83
  84     chess16.set(bin64_t(4,1),binmap_t::FILLED);
  85     EXPECT_EQ(binmap_t::FILLED,chess16.get(bin64_t(5,0)));
  86 }
  87
  88 TEST(BinsTest,Staircase) {
  89
  90     const int TOPLAYR = 44;
  91     binmap_t staircase;
  92     for(int i=0;i<TOPLAYR;i++)
  93         staircase.set(bin64_t(i,1),binmap_t::FILLED);
  94
  95     EXPECT_NE(binmap_t::FILLED,staircase.get(bin64_t(TOPLAYR,0)));
  96     EXPECT_NE(binmap_t::EMPTY,staircase.get(bin64_t(TOPLAYR,0)));
  97
  98     staircase.set(bin64_t(0,0),binmap_t::FILLED);
  99     EXPECT_EQ(binmap_t::FILLED,staircase.get(bin64_t(TOPLAYR,0)));
 100
 101 }
 102
 103 TEST(BinsTest,Hole) {
 104
 105     binmap_t hole;
 106     hole.set(bin64_t(8,0),binmap_t::FILLED);
 107     hole.set(bin64_t(6,1),binmap_t::EMPTY);
 108     hole.set(bin64_t(6,2),binmap_t::EMPTY);
 109     EXPECT_EQ(binmap_t::FILLED,hole.get(bin64_t(6,0)));
 110     EXPECT_EQ(binmap_t::FILLED,hole.get(bin64_t(6,3)));
 111     EXPECT_NE(binmap_t::FILLED,hole.get(bin64_t(8,0)));
 112     EXPECT_NE(binmap_t::EMPTY,hole.get(bin64_t(8,0)));
 113     EXPECT_EQ(binmap_t::EMPTY,hole.get(bin64_t(6,1)));
 114
 115 }
 116
 117 TEST(BinsTest,Find){
 118
 119     binmap_t hole;
 120     hole.set(bin64_t(4,0),binmap_t::FILLED);
 121     hole.set(bin64_t(1,1),binmap_t::EMPTY);
 122     hole.set(bin64_t(0,7),binmap_t::EMPTY);
 123     bin64_t f = hole.find(bin64_t(4,0)).left_foot();
 124     EXPECT_EQ(bin64_t(0,2),f);
 125
 126 }
 127
 128 TEST(BinsTest,Stripes) {
 129
 130     binmap_t zebra;
 131     zebra.set(bin64_t(5,0));
 132     zebra.set(bin64_t(3,1),binmap_t::EMPTY);
 133     zebra.set(bin64_t(1,12),binmap_t::EMPTY);
 134     zebra.set(bin64_t(1,14),binmap_t::EMPTY);
 135     int count;
 136     uint64_t *stripes = zebra.get_stripes(count);
 137     EXPECT_EQ(9,count);
 138     EXPECT_EQ(0,stripes[0]);
 139     EXPECT_EQ(0,stripes[1]);
 140     EXPECT_EQ(8,stripes[2]);
 141     EXPECT_EQ(16,stripes[3]);
 142     EXPECT_EQ(24,stripes[4]);
 143     EXPECT_EQ(26,stripes[5]);
 144     EXPECT_EQ(28,stripes[6]);
 145     EXPECT_EQ(30,stripes[7]);
 146     EXPECT_EQ(32,stripes[8]);
 147     free(stripes);
 148
 149 }
 150
 151 TEST(BinsTest,StripesAgg) {
 152
 153     binmap_t zebra;
 154     zebra.set(bin64_t(0,1));
 155     zebra.set(bin64_t(0,2));
 156     int count;
 157     uint64_t *stripes = zebra.get_stripes(count);
 158     EXPECT_EQ(3,count);
 159     EXPECT_EQ(0,stripes[0]);
 160     EXPECT_EQ(1,stripes[1]);
 161     EXPECT_EQ(3,stripes[2]);
 162     free(stripes);
 163
 164 }
 165
 166 TEST(BinsTest,Alloc) {
 167
 168     binmap_t b;
 169     b.set(bin64_t(1,0));
 170     b.set(bin64_t(1,1));
 171     b.set(bin64_t(1,0),binmap_t::EMPTY);
 172     b.set(bin64_t(1,1),binmap_t::EMPTY);
 173     EXPECT_EQ(1,b.size());
 174
 175 }
 176
 177 TEST(BinsTest,Remove) {
 178
 179     binmap_t b;
 180     b.set(bin64_t(5,0));
 181     binmap_t c;
 182     c.set(bin64_t(2,0));
 183     c.set(bin64_t(2,2));
 184     b.remove(c);
 185     EXPECT_EQ(binmap_t::EMPTY,b.get(bin64_t(2,0)));
 186     EXPECT_EQ(binmap_t::FILLED,b.get(bin64_t(2,1)));
 187     EXPECT_EQ(binmap_t::EMPTY,b.get(bin64_t(2,2)));
 188     EXPECT_EQ(binmap_t::FILLED,b.get(bin64_t(2,3)));
 189     EXPECT_EQ(binmap_t::FILLED,b.get(bin64_t(4,1)));
 190
 191     binmap_t b16, b1024, b8192;
 192     b16.set(bin64_t(3,1));
 193     b1024.set(bin64_t(3,1));
 194     b1024.set(bin64_t(4,2));
 195     b1024.set(bin64_t(8,3));
 196     b8192.set(bin64_t(8,3));
 197     b8192.set(bin64_t(10,7));
 198
 199     b1024.remove(b16);
 200     b1024.remove(b8192);
 201
 202     EXPECT_EQ(binmap_t::EMPTY,b1024.get(bin64_t(3,1)));
 203     EXPECT_EQ(binmap_t::EMPTY,b1024.get(bin64_t(5,0)));
 204     EXPECT_EQ(binmap_t::EMPTY,b1024.get(bin64_t(9,1)));
 205     EXPECT_EQ(binmap_t::EMPTY,b1024.get(bin64_t(12,1)));
 206     EXPECT_EQ(binmap_t::FILLED,b1024.get(bin64_t(4,2)));
 207
 208     b8192.set(bin64_t(2,3));
 209     b16.remove(b8192);
 210     EXPECT_EQ(binmap_t::EMPTY,b16.get(bin64_t(2,3)));
 211     EXPECT_EQ(binmap_t::FILLED,b16.get(bin64_t(2,2)));
 212
 213 }
 214
 215 TEST(BinsTest,FindFiltered) {
 216
 217     binmap_t data, filter;
 218     data.set(bin64_t(2,0));
 219     data.set(bin64_t(2,2));
 220     data.set(bin64_t(1,7));
 221     filter.set(bin64_t(2,1));
 222     filter.set(bin64_t(1,4));
 223     filter.set(bin64_t(0,13));
 224
 225     bin64_t x = data.find_filtered(filter,bin64_t(4,0)).left_foot();
 226     EXPECT_EQ(bin64_t(0,12),x);
 227
 228 }
 229
 230
 231 TEST(BinsTest, Cover) {
 232
 233     binmap_t b;
 234     b.set(bin64_t(2,0));
 235     b.set(bin64_t(4,1));
 236     EXPECT_EQ(bin64_t(4,1),b.cover(bin64_t(0,30)));
 237     EXPECT_EQ(bin64_t(2,0),b.cover(bin64_t(0,3)));
 238     EXPECT_EQ(bin64_t(2,0),b.cover(bin64_t(2,0)));
 239     //binmap_t c;
 240     //EXPECT_EQ(bin64_t::ALL,b.cover(bin64_t(0,30)));
 241
 242 }
 243
 244
 245 TEST(BinsTest,FindFiltered2) {
 246
 247     binmap_t data, filter;
 248     for(int i=0; i<1024; i+=2)
 249         data.set(bin64_t(0,i));
 250     for(int j=1; j<1024; j+=2)
 251         filter.set(bin64_t(0,j));
 252     filter.set(bin64_t(0,501),binmap_t::EMPTY);
 253     EXPECT_EQ(bin64_t(0,501),data.find_filtered(filter,bin64_t(10,0)).left_foot());
 254     data.set(bin64_t(0,501));
 255     EXPECT_EQ(bin64_t::NONE,data.find_filtered(filter,bin64_t(10,0)).left_foot());
 256
 257 }
 258
 259 TEST(BinsTest,CopyRange) {
 260     binmap_t data, add;
 261     data.set(bin64_t(2,0));
 262     data.set(bin64_t(2,2));
 263     data.set(bin64_t(1,7));
 264     add.set(bin64_t(2,1));
 265     add.set(bin64_t(1,4));
 266     add.set(bin64_t(0,13));
 267     add.set(bin64_t(5,118));
 268     data.range_copy(add, bin64_t(3,0));
 269     EXPECT_TRUE(binmap_t::is_mixed(data.get(bin64_t(3,0))));
 270     EXPECT_EQ(binmap_t::EMPTY,data.get(bin64_t(2,0)));
 271     EXPECT_EQ(binmap_t::FILLED,data.get(bin64_t(2,1)));
 272     EXPECT_EQ(binmap_t::EMPTY,data.get(bin64_t(1,6)));
 273     EXPECT_EQ(binmap_t::FILLED,data.get(bin64_t(1,7)));
 274 }
 275
 276 TEST(BinsTest, Mass) {
 277     binmap_t b;
 278     b.set(bin64_t(6,0),binmap_t::FILLED);
 279     b.set(bin64_t(0,0),binmap_t::EMPTY);
 280     EXPECT_EQ(63,b.mass());
 281     EXPECT_FALSE(b.is_empty());
 282     b.clear();
 283     EXPECT_TRUE(b.is_empty());
 284     EXPECT_EQ(0,b.mass());
 285
 286     binmap_t b50;
 287     for(int i=0; i<50; i++)
 288         b50.set(bin64_t(4,i*2));
 289     EXPECT_EQ(50<<4,b50.mass());
 290 }
 291
 292 TEST(BinsTest,Twist) {
 293     binmap_t b;
 294     b.set(bin64_t(3,2));
 295     EXPECT_EQ(binmap_t::FILLED,b.get(bin64_t(3,2)));
 296     EXPECT_EQ(binmap_t::EMPTY,b.get(bin64_t(3,3)));
 297     b.twist(1<<3);
 298     EXPECT_EQ(binmap_t::FILLED,b.get(bin64_t(3,3)));
 299     EXPECT_EQ(binmap_t::EMPTY,b.get(bin64_t(3,2)));
 300     bin64_t tw = b.find(bin64_t(5,0),binmap_t::FILLED);
 301     while (tw.width()>(1<<3))
 302         tw = tw.left();
 303     tw = tw.twisted(1<<3);
 304     EXPECT_EQ(bin64_t(3,2),tw);
 305     b.twist(0);
 306     EXPECT_EQ(binmap_t::FILLED,b.get(bin64_t(3,2)));
 307     EXPECT_EQ(binmap_t::EMPTY,b.get(bin64_t(3,3)));
 308 }
 309
 310 TEST(BinsTest,SeqLength) {
 311     binmap_t b;
 312     b.set(bin64_t(3,0));
 313     b.set(bin64_t(1,4));
 314     b.set(bin64_t(0,10));
 315     b.set(bin64_t(3,2));
 316     EXPECT_EQ(11,b.seq_length());
 317 }
 318
 319 TEST(BinsTest,EmptyFilled) {
 320     // 1112 3312  2111 ....
 321     binmap_t b;
 322
 323     EXPECT_TRUE(b.is_empty(bin64_t::ALL));
 324
 325     b.set(bin64_t(1,0));
 326     b.set(bin64_t(0,2));
 327     b.set(bin64_t(0,6));
 328     b.set(bin64_t(1,5));
 329     b.set(bin64_t(0,9));
 330
 331     EXPECT_FALSE(b.is_empty(bin64_t::ALL));
 332
 333     EXPECT_TRUE(b.is_empty(bin64_t(2,3)));
 334     EXPECT_FALSE(b.is_filled(bin64_t(2,3)));
 335     EXPECT_TRUE(b.is_solid(bin64_t(2,3),binmap_t::MIXED));
 336     EXPECT_TRUE(b.is_filled(bin64_t(1,0)));
 337     EXPECT_TRUE(b.is_filled(bin64_t(1,5)));
 338     EXPECT_FALSE(b.is_filled(bin64_t(1,3)));
 339
 340     b.set(bin64_t(0,3));
 341     b.set(bin64_t(0,7));
 342     b.set(bin64_t(0,8));
 343
 344     EXPECT_TRUE(b.is_filled(bin64_t(2,0)));
 345     EXPECT_TRUE(b.is_filled(bin64_t(2,2)));
 346     EXPECT_FALSE(b.is_filled(bin64_t(2,1)));
 347
 348     b.set(bin64_t(1,2));
 349     EXPECT_TRUE(b.is_filled(bin64_t(2,1)));
 350 }
 351
 352 TEST(BinheapTest,Eat) {
 353
 354     binheap b;
 355     b.push(bin64_t(0,1));
 356     b.push(bin64_t(0,3));
 357     b.push(bin64_t(2,0));
 358     b.push(bin64_t(2,4));
 359
 360     EXPECT_EQ(bin64_t(2,0),b.pop());
 361     EXPECT_EQ(bin64_t(2,4),b.pop());
 362     EXPECT_EQ(bin64_t::none(),b.pop());
 363
 364     for (int i=0; i<64; i++) {
 365         b.push(bin64_t(0,i));
 366     }
 367     b.push(bin64_t(5,0));
 368     EXPECT_EQ(bin64_t(5,0),b.pop());
 369     for (int i=32; i<64; i++)
 370         EXPECT_EQ(bin64_t(0,i),b.pop());
 371
 372 }
 373
 374 TEST(BinsTest,RangeOpTest) {
 375     binmap_t a, b;
 376     a.set(bin64_t(0,0));
 377     a.set(bin64_t(0,2));
 378     b.set(bin64_t(0,1));
 379     b.set(bin64_t(0,3));
 380     a.range_or(b,bin64_t(1,0));
 381     EXPECT_TRUE(a.is_filled(bin64_t(1,0)));
 382     EXPECT_FALSE(a.is_filled(bin64_t(1,1)));
 383
 384     binmap_t f, s;
 385     f.set(bin64_t(3,0));
 386     s.set(bin64_t(0,1));
 387     s.set(bin64_t(0,4));
 388     f.range_remove(s,bin64_t(2,1));
 389
 390     EXPECT_TRUE(f.is_filled(bin64_t(2,0)));
 391     EXPECT_FALSE(f.is_filled(bin64_t(0,4)));
 392     EXPECT_TRUE(f.is_filled(bin64_t(0,5)));
 393
 394     binmap_t z, x;
 395     z.set(bin64_t(1,0));
 396     z.set(bin64_t(1,2));
 397     x.set(bin64_t(0,1));
 398     x.set(bin64_t(0,1));
 399 }
 400
 401 TEST(BinsTest,CoarseBitmap) {
 402     binmap_t b;
 403     b.set(bin64_t(4,0));
 404     union {uint16_t i16[2]; uint32_t i32;};
 405     b.to_coarse_bitmap(i16,bin64_t(5,0),0);
 406     EXPECT_EQ((1<<16)-1,i32);
 407
 408     b.set(bin64_t(14,0));
 409     i32=0;
 410     b.to_coarse_bitmap(i16,bin64_t(15,0),10);
 411     EXPECT_EQ((1<<16)-1,i32);
 412
 413     binmap_t rough;
 414     rough.set(bin64_t(1,0));
 415     rough.set(bin64_t(0,2));
 416     i32=0;
 417     rough.to_coarse_bitmap(i16,bin64_t(6,0),1);
 418     EXPECT_EQ(1,i32);
 419
 420     binmap_t ladder;
 421     ladder.set(bin64_t(6,2));
 422     ladder.set(bin64_t(5,2));
 423     ladder.set(bin64_t(4,2));
 424     ladder.set(bin64_t(3,2));
 425     ladder.set(bin64_t(2,2));
 426     ladder.set(bin64_t(1,2));
 427     ladder.set(bin64_t(0,2));
 428     i32=0;
 429     ladder.to_coarse_bitmap(i16,bin64_t(8,0),3);
 430     EXPECT_EQ(0x00ff0f34,i32);
 431
 432     binmap_t bin;
 433     bin.set(bin64_t(3,0));
 434     bin.set(bin64_t(0,8));
 435     i32 = 0;
 436     bin.to_coarse_bitmap(i16,bin64_t(4,0),0);
 437     EXPECT_EQ((1<<9)-1,i32);
 438
 439     i32 = 0;
 440     bin.to_coarse_bitmap(i16,bin64_t(7,0),3);
 441     EXPECT_EQ(1,i32);
 442
 443     i32 = 0;
 444     bin.to_coarse_bitmap(i16,bin64_t(4,0),3);
 445     EXPECT_EQ(1,i32);
 446
 447     i32 = 0;
 448     bin.to_coarse_bitmap(i16,bin64_t(2,0),1);
 449     EXPECT_EQ(3,i32&3);
 450
 451     uint64_t bigint;
 452     bigint = 0;
 453     binmap_t bm;
 454     bm.set(bin64_t(6,0));
 455     bm.to_coarse_bitmap((uint16_t*)&bigint,bin64_t(6,0),0);
 456     EXPECT_EQ( 0xffffffffffffffffULL, bigint );
 457
 458 }
 459
 460 /*TEST(BinsTest,AddSub) {
 461         binmap_t b;
 462         b|=15;
 463         b-=1;
 464         ASSERT_TRUE(b.contains(2));
 465         ASSERT_TRUE(b.contains(14));
 466         ASSERT_FALSE(b.contains(3));
 467         ASSERT_FALSE(b.contains(22));
 468         ASSERT_TRUE(b.contains(12));
 469         b-=13;
 470         ASSERT_FALSE(b.contains(12));
 471         ASSERT_FALSE(b.contains(14));
 472         ASSERT_FALSE(b.contains(11));
 473         ASSERT_TRUE(b.contains(10));
 474 }
 475
 476
 477 TEST(BinsTest,Peaks) {
 478         bin::vec peaks = bin::peaks(11);
 479         ASSERT_EQ(3,peaks.size());
 480         ASSERT_EQ(15,peaks[0]);
 481         ASSERT_EQ(18,peaks[1]);
 482         ASSERT_EQ(19,peaks[2]);
 483 }
 484
 485 TEST(BinsTest,Performance) {
 486         binmap_t b;
 487         std::set<int> s;
 488         clock_t start, end;
 489         double b_time, s_time;
 490         int b_size, s_size;
 491
 492         start = clock();
 493         for(int i=1; i<(1<<20); i++)
 494                 b |= bin(i);
 495         //b_size = b.bits.size();
 496         end = clock();
 497         b_time = ((double) (end - start)) / CLOCKS_PER_SEC;
 498         //ASSERT_EQ(1,b.bits.size());
 499
 500         start = clock();
 501         for(int i=1; i<(1<<20); i++)
 502                 s.insert(i);
 503         s_size = s.size();
 504         end = clock();
 505         s_time = ((double) (end - start)) / CLOCKS_PER_SEC;
 506
 507         printf("bins: %f (%i), set: %f (%i)\n",b_time,b_size,s_time,s_size);
 508 }*/
 509
 510 int main (int argc, char** argv) {
 511         testing::InitGoogleTest(&argc, argv);
 512         return RUN_ALL_TESTS();
 513 }