From 625918be5caac9ef29a55886bac64623011bbe84 Mon Sep 17 00:00:00 2001
From: Victor Grishchenko <victor.grishchenko@gmail.com>
Date: Mon, 10 May 2010 15:36:50 +0200
Subject: [PATCH] Now, produces coarse bitmaps

---
 bins.cpp            | 67 ++++++++++++++++++++++++++++++++++++++-------
 bins.h              | 25 +++++++++++++++--
 tests/binstest2.cpp | 49 ++++++++++++++++++++++++++++++++-
 3 files changed, 128 insertions(+), 13 deletions(-)

diff --git a/bins.cpp b/bins.cpp
index 510b4a0..22d8798 100644
--- a/bins.cpp
+++ b/bins.cpp
@@ -179,15 +179,15 @@ uint16_t    binmap_t::alloc_cell () {
 }
 
 
-bin64_t iterator::next (bool need_solid) {
-    assert(!deep());
+bin64_t iterator::next (bool need_solid, uint8_t min_layer) {
+    assert( (!deep()) || (layer()==min_layer));
     while (pos.is_right())
         parent();
     //parent();
     //if (need_solid ? !solid() : deep())
     //    right();
     sibling();
-    while (need_solid ? !solid() : deep())
+    while ( (need_solid ? !solid() : deep()) && layer()>min_layer )
         left();
     return pos;
 }
@@ -403,7 +403,8 @@ bin64_t     binmap_t::find_filtered
         while ( 
                 fi.deep() ?
                 (ti.deep() || *ti!=stop)  :
-                (ti.deep() ? *fi!=FILLED : ( ((*ti^stop)&~*fi) && (*ti!=seek || *fi!=EMPTY) ) ) 
+                (ti.deep() ? *fi!=FILLED : 
+                    ( ((*ti^stop)&~*fi) && (*ti!=seek || *fi!=EMPTY) ) ) 
               ) 
         {
             ti.left(); fi.left();                
@@ -419,17 +420,28 @@ bin64_t     binmap_t::find_filtered
     return bin64_t::NONE;    
 }
 
-// FIXME unite with remove(); do bitwise()
-void        binmap_t::copy_range (binmap_t& origin, bin64_t range) { 
+void        binmap_t::range_op (binmap_t& mask, bin64_t range, bin_op_t op) {
     if (range==bin64_t::ALL)
-        range = bin64_t ( height>origin.height ? height : origin.height, 0 );
-    iterator zis(this,range,true), zat(&origin,range,true);
+        range = bin64_t ( height>mask.height ? height : mask.height, 0 );
+    iterator zis(this,range,true), zat(&mask,range,true);
     while (zis.pos.within(range)) {
         while (zis.deep() || zat.deep()) {
             zis.left(); zat.left();
         }
-        
-        *zis = *zat;
+
+        switch (op) {
+            case REMOVE_OP:
+                *zis &= ~*zat;
+                break;
+            case AND_OP:
+                *zis &= *zat;
+                break;
+            case COPY_OP:
+                *zis = *zat;
+                break;
+            case OR_OP:
+                *zis |= *zat;
+        }
         
         while (zis.pos.is_right()) {
             zis.parent(); zat.parent();
@@ -462,6 +474,40 @@ bool        binmap_t::is_solid (bin64_t range, fill_t val)  {
 }
 
 
+void    binmap_t::map16 (uint16_t* target, bin64_t range, iterator& lead) {
+    while (!range.within(lead.pos))
+        lead.parent();
+    while (lead.pos!=range)
+        lead.towards(range);
+    if (!lead.deep()) {
+        *target = *lead;
+        return;
+    }
+    lead.left();
+    lead.left();
+    lead.left();
+    lead.left();
+    uint16_t shift = 1;
+    for(int i=0; i<16; i++) {
+        if (!lead.deep() && *lead==FILLED)
+            *target |= shift;
+        shift<<=1;
+        lead.next(false,range.layer()-4);
+    }
+}
+
+
+void    binmap_t::to_coarse_bitmap (void* bits, bin64_t range, uint8_t height) {
+    uint16_t* bits16 = (uint16_t*) bits;
+    iterator iter(this,range,true);
+    int height16 = range.layer()-height-4;
+    int wordwidth = 1 << height16;
+    int offset = range.offset() << height16;
+    for(int i=offset; i<offset+wordwidth; i++) 
+        map16(bits16+i,bin64_t(height+4,i),iter);
+}
+
+
 binheap::binheap() {
     size_ = 32;
     heap_ = (bin64_t*) malloc(size_*sizeof(bin64_t));
@@ -517,3 +563,4 @@ void    binheap::push(bin64_t val) {
 binheap::~binheap() {
     free(heap_);
 }
+
diff --git a/bins.h b/bins.h
index d0192ab..2068e28 100644
--- a/bins.h
+++ b/bins.h
@@ -10,6 +10,8 @@
 #define BINS_H
 #include "bin64.h"
 
+class iterator; // FIXME shame
+
 /** A binmap covering 2^64 range. Binmap is a hybrid of a bitmap (aka
     bit vector) and a binary tree. The key ability of a binmap is
     the aggregation of solid (all-0 or all-1) ranges. */
@@ -39,8 +41,23 @@ public:
     /** Set value for the bin. */
     void        set (bin64_t bin, fill_t val=FILLED); 
     
+    typedef enum {
+        OR_OP,
+        AND_OP,
+        REMOVE_OP,
+        COPY_OP
+    } bin_op_t;
+    
     /** Copy a range from another binmap. */
-    void        copy_range (binmap_t& origin, bin64_t range);
+    void        range_op (binmap_t& mask, bin64_t range, bin_op_t op);
+    void        range_copy (binmap_t& mask, bin64_t range)
+        {   range_op(mask, range, COPY_OP);   }
+    void        range_remove (binmap_t& mask, bin64_t range)
+        {   range_op(mask, range, REMOVE_OP);   }
+    void        range_or (binmap_t& mask, bin64_t range)
+        {   range_op(mask, range, OR_OP);   }
+    void        range_and (binmap_t& mask, bin64_t range)
+        {   range_op(mask, range, AND_OP);   }
     
     /** Find the leftmost bin within the specified range which is
         either filled or empty. */
@@ -96,6 +113,8 @@ public:
         right change places. Twisting is mostly needed for randomization.  */
     void        twist (uint64_t mask);
     
+    void        to_coarse_bitmap (void* bits, bin64_t range, uint8_t height);
+    
 private:
     
     /** Every 16th uint32 is a flag field denoting whether
@@ -143,6 +162,8 @@ private:
     
     static uint32_t split16to32(uint16_t half);
     static int join32to16(uint32_t cell);
+
+    void        map16 (uint16_t* target, bin64_t range, iterator& lead);
     
     friend class iterator;
 #ifdef FRIEND_TEST
@@ -177,7 +198,7 @@ public:
     void right() {to(1);}
     /** Move to the next defined (non-deep, flat) cell.
         If solid==true, move to a solid (0xffff/0x0) cell. */
-    bin64_t next (bool solid=false);
+    bin64_t next (bool solid=false, uint8_t min_layer=0);
     bin64_t bin() { return pos; }
     void towards(bin64_t bin) {
         bin64_t next = pos.towards(bin);
diff --git a/tests/binstest2.cpp b/tests/binstest2.cpp
index 0b42936..3cd0d0c 100644
--- a/tests/binstest2.cpp
+++ b/tests/binstest2.cpp
@@ -265,7 +265,7 @@ TEST(BinsTest,CopyRange) {
     add.set(bin64_t(1,4));
     add.set(bin64_t(0,13));
     add.set(bin64_t(5,118));
-    data.copy_range(add, bin64_t(3,0));
+    data.range_copy(add, bin64_t(3,0));
     EXPECT_TRUE(binmap_t::is_mixed(data.get(bin64_t(3,0))));
     EXPECT_EQ(binmap_t::EMPTY,data.get(bin64_t(2,0)));
     EXPECT_EQ(binmap_t::FILLED,data.get(bin64_t(2,1)));
@@ -371,6 +371,53 @@ TEST(BinheapTest,Eat) {
         
 }
 
+TEST(BinsTest,RangeOpTest) {
+    binmap_t a, b;
+    a.set(bin64_t(0,0));
+    a.set(bin64_t(0,2));
+    b.set(bin64_t(0,1));
+    b.set(bin64_t(0,3));
+    a.range_or(b,bin64_t(1,0));
+    EXPECT_TRUE(a.is_filled(bin64_t(1,0)));
+    EXPECT_FALSE(a.is_filled(bin64_t(1,1)));
+    
+    binmap_t f, s;
+    f.set(bin64_t(3,0));
+    s.set(bin64_t(0,1));
+    s.set(bin64_t(0,4));
+    f.range_remove(s,bin64_t(2,1));
+    
+    EXPECT_TRUE(f.is_filled(bin64_t(2,0)));
+    EXPECT_FALSE(f.is_filled(bin64_t(0,4)));
+    EXPECT_TRUE(f.is_filled(bin64_t(0,5)));
+    
+    binmap_t z, x;
+    z.set(bin64_t(1,0));
+    z.set(bin64_t(1,2));
+    x.set(bin64_t(0,1));
+    x.set(bin64_t(0,1));
+}
+
+TEST(BinsTest,CoarseBitmap) {
+    binmap_t b;
+    b.set(bin64_t(4,0));
+    uint32_t i32;
+    b.to_coarse_bitmap(&i32,bin64_t(5,0),0);
+    EXPECT_EQ((1<<16)-1,i32);
+    
+    b.set(bin64_t(14,0));
+    i32=0;
+    b.to_coarse_bitmap(&i32,bin64_t(15,0),10);
+    EXPECT_EQ((1<<16)-1,i32);
+    
+    binmap_t rough;
+    rough.set(bin64_t(1,0));
+    rough.set(bin64_t(0,2));
+    i32=0;
+    rough.to_coarse_bitmap(&i32,bin64_t(6,0),1);
+    EXPECT_EQ(1,i32);
+}
+
 /*TEST(BinsTest,AddSub) {
 	binmap_t b;
 	b|=15;
-- 
2.20.1