+/*
+ * bin64.h
+ * bin numbers (binaty tree enumeration/navigation)
+ *
+ * Created by Victor Grishchenko on ??/09/09 in Karlovy Vary
+ * Copyright 2009 Delft University of Technology. All rights reserved.
+ *
+ */
#ifndef BIN64_H
#define BIN64_H
#include <assert.h>
-#ifdef _MSC_VER
- #include "compat/stdint.h"
-#else
- #include <stdint.h>
-#endif
+#include "compat.h"
/** Numbering for (aligned) logarithmical bins.
Bin numbers in the tail111 encoding: meaningless
bits in the tail are set to 0111...11, while the
head denotes the offset. Thus, 1101 is the bin
- at layer 1, offset 3 (i.e. fourth). */
+ at layer 1, offset 3 (i.e. fourth).
+ Obviously, bins form a binary tree. All navigation
+ is made in terms of binary trees: left, right,
+ sibling, parent, etc.
+ */
struct bin64_t {
uint64_t v;
static const uint64_t NONE;
bin64_t() : v(NONE) {}
bin64_t(const bin64_t&b) : v(b.v) {}
+ bin64_t(const uint32_t val) ;
bin64_t(const uint64_t val) : v(val) {}
bin64_t(uint8_t layer, uint64_t offset) :
v( (offset<<(layer+1)) | ((1ULL<<layer)-1) ) {}
return (tail_bits()+1)>>1;
}
+ /** Get the sibling interval in the binary tree. */
bin64_t sibling () const {
// if (v==ALL) return NONE;
return bin64_t(v^(tail_bit()<<1));
return r;
}
+ /** Get the bin's offset in base units, i.e. 4 for (1,2). */
uint64_t base_offset () const {
return (v&~(tail_bits()))>>1;
}
+ /** Get the bin's offset at its own layer, e.g. 2 for (1,2). */
uint64_t offset () const {
return v >> (layer()+1);
}
+ /** Get a child bin; either right(true) or left(false). */
bin64_t to (bool right) const {
if (!(v&1))
return NONE;
- uint64_t tb = tail_bit()>>1;
+ uint64_t tb = ((tail_bits() >> 1) + 1) >> 1;
if (right)
- tb |= (tb<<1);
- return bin64_t(v^tb);
+ return bin64_t(v + tb);
+ return bin64_t(v ^ tb);
}
+ /** Get the left child bin. */
bin64_t left () const {
return to(false);
}
+ /** Get the right child bin. */
bin64_t right () const {
return to(true);
}
+ /** Check whether this bin is within the specified bin. */
bool within (bin64_t maybe_asc) {
+ if (maybe_asc==bin64_t::NONE)
+ return false;
uint64_t short_tail = maybe_asc.tail_bits();
if (tail_bits()>short_tail)
return false;
return right();
}
+ /** Twist/untwist a bin number according to the mask. */
+ bin64_t twisted (uint64_t mask) const {
+ return bin64_t( v ^ ((mask<<1)&~tail_bits()) );
+ }
+
+ /** Get the paretn bin. */
bin64_t parent () const {
uint64_t tbs = tail_bits(), ntbs = (tbs+1)|tbs;
return bin64_t( (v&~ntbs) | tbs );
}
- bool is_left () const {
+ /** Check whether this bin is the left sibling. */
+ inline bool is_left () const {
uint64_t tb = tail_bit();
return !(v&(tb<<1));
}
- bool is_right() const { return !is_left(); }
+
+ /** Check whether this bin is the right sibling. */
+ inline bool is_right() const { return !is_left(); }
+ /** Get the leftmost basic bin within this bin. */
bin64_t left_foot () const {
+ if (v==NONE)
+ return NONE;
return bin64_t(0,base_offset());
}
/** Depth-first in-order binary tree traversal. */
bin64_t next_dfsio (uint8_t floor);
+ /** Return the number of basic bins within this bin. */
bin64_t width () const {
return (tail_bits()+1)>>1;
}
+
+ /** Get the standard-form null-terminated string
+ representation of this bin, e.g. "(2,1)".
+ The string is statically allocated, must
+ not be reused or released. */
+ const char* str () const;
/** The array must have 64 cells, as it is the max
number of peaks possible +1 (and there are no reason