#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. */
/** 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. */
right change places. Twisting is mostly needed for randomization. */
void twist (uint64_t mask);
+ /** Convert binmap to a conventional flat bitmap; only bits corresponding
+ to solid filled bins are set to 1.
+ @param range the bin (the range) to cover
+ @param height aggregation level; use 2**height bins (2**height base
+ layer bits per one bitmap bit).
+ @param bits uint16_t array to put bitmap into; must have enough
+ of space, i.e. 2**(range.layer()-height-4) cells. */
+ void to_coarse_bitmap (uint16_t* bits, bin64_t range, uint8_t height);
+
private:
/** Every 16th uint32 is a flag field denoting whether
static uint32_t split16to32(uint16_t half);
static int join32to16(uint32_t cell);
+
+ void map16 (uint16_t* target, bin64_t range);
friend class iterator;
#ifdef FRIEND_TEST
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 stop_undeep=true, bool stop_solid=false, uint8_t stop_layer=0);
+ bin64_t next_solid () { return next(false, true,0); }
bin64_t bin() { return pos; }
void towards(bin64_t bin) {
bin64_t next = pos.towards(bin);