bin64.h

   1 /*
   2  *  bin64.h
   3  *  bin numbers (binaty tree enumeration/navigation)
   4  *
   5  *  Created by Victor Grishchenko on ??/09/09 in Karlovy Vary
   6  *  Copyright 2009 Delft University of Technology. All rights reserved.
   7  *
   8  */
   9 #ifndef BIN64_H
  10 #define BIN64_H
  11 #include <assert.h>
  12 #include "compat.h"
  13
  14
  15 /** Numbering for (aligned) logarithmical bins.
  16     Each number stands for an interval
  17     [o*2^l,(o+1)*2^l), where l is the layer and o
  18     is the offset.
  19     Bin numbers in the tail111 encoding: meaningless
  20     bits in the tail are set to 0111...11, while the
  21     head denotes the offset. Thus, 1101 is the bin
  22     at layer 1, offset 3 (i.e. fourth).
  23     Obviously, bins form a binary tree. All navigation
  24     is made in terms of binary trees: left, right,
  25     sibling, parent, etc.
  26  */
  27 struct bin64_t {
  28     uint64_t v;
  29     static const uint64_t NONE;
  30     static const uint64_t ALL;
  31     static const uint32_t NONE32;
  32     static const uint32_t ALL32;
  33
  34     bin64_t() : v(NONE) {}
  35     bin64_t(const bin64_t&b) : v(b.v) {}
  36     bin64_t(const uint32_t val) ;
  37     bin64_t(const uint64_t val) : v(val) {}
  38     bin64_t(uint8_t layer, uint64_t offset) :
  39         v( (offset<<(layer+1)) | ((1ULL<<layer)-1) ) {}
  40     operator uint64_t () const { return v; }
  41     uint32_t to32() const ;
  42     bool operator == (bin64_t& b) const { return v==b.v; }
  43
  44     static bin64_t none () { return NONE; }
  45     static bin64_t all () { return ALL; }
  46
  47     uint64_t tail_bits () const {
  48         return v ^ (v+1);
  49     }
  50
  51     uint64_t tail_bit () const {
  52         return (tail_bits()+1)>>1;
  53     }
  54
  55     /** Get the sibling interval in the binary tree. */
  56     bin64_t sibling () const {
  57         // if (v==ALL) return NONE;
  58         return bin64_t(v^(tail_bit()<<1));
  59     }
  60
  61     int layer () const {
  62         int r = 0;
  63         uint64_t tail = ((v^(v+1))+1)>>1;
  64         if (tail>0xffffffffULL) {
  65             r = 32;
  66             tail>>=32;
  67         }
  68         // courtesy of Sean Eron Anderson
  69         // http://graphics.stanford.edu/~seander/bithacks.html
  70         static const int DeBRUIJN[32] = {
  71           0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
  72           31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  73         };
  74         r += DeBRUIJN[((uint32_t)(tail*0x077CB531U))>>27];
  75         return r;
  76     }
  77
  78     /** Get the bin's offset in base units, i.e. 4 for (1,2). */
  79     uint64_t base_offset () const {
  80         return (v&~(tail_bits()))>>1;
  81     }
  82
  83     /** Get the bin's offset at its own layer, e.g. 2 for (1,2). */
  84     uint64_t offset () const {
  85         return v >> (layer()+1);
  86     }
  87
  88     /** Get a child bin; either right(true) or left(false). */
  89     bin64_t to (bool right) const {
  90         if (!(v&1))
  91             return NONE;
  92         uint64_t tb = ((tail_bits() >> 1) + 1) >> 1;
  93         if (right)
  94             return bin64_t(v + tb);
  95         return bin64_t(v ^ tb);
  96     }
  97
  98     /** Get the left child bin. */
  99     bin64_t left () const {
 100         return to(false);
 101     }
 102
 103     /** Get the right child bin. */
 104     bin64_t right () const {
 105         return to(true);
 106     }
 107
 108     /** Check whether this bin is within the specified bin. */
 109     bool    within (bin64_t maybe_asc) {
 110         if (maybe_asc==bin64_t::NONE)
 111             return false;
 112         uint64_t short_tail = maybe_asc.tail_bits();
 113         if (tail_bits()>short_tail)
 114             return false;
 115         return (v&~short_tail) == (maybe_asc.v&~short_tail) ;
 116     }
 117
 118     /** Left or right, depending whether the destination is. */
 119     bin64_t towards (bin64_t dest) const {
 120         if (!dest.within(*this))
 121             return NONE;
 122         if (dest.within(left()))
 123             return left();
 124         else
 125             return right();
 126     }
 127
 128     /** Twist/untwist a bin number according to the mask. */
 129     bin64_t twisted (uint64_t mask) const {
 130         return bin64_t( v ^ ((mask<<1)&~tail_bits()) );
 131     }
 132
 133     /** Get the paretn bin. */
 134     bin64_t parent () const {
 135         uint64_t tbs = tail_bits(), ntbs = (tbs+1)|tbs;
 136         return bin64_t( (v&~ntbs) | tbs );
 137     }
 138
 139     /** Check whether this bin is the left sibling. */
 140     inline bool is_left () const {
 141         uint64_t tb = tail_bit();
 142         return !(v&(tb<<1));
 143     }
 144
 145     /** Check whether this bin is the right sibling. */
 146     inline bool is_right() const { return !is_left(); }
 147
 148     /** Get the leftmost basic bin within this bin. */
 149     bin64_t left_foot () const {
 150         if (v==NONE)
 151             return NONE;
 152         return bin64_t(0,base_offset());
 153     }
 154
 155     /** Whether layer is 0. */
 156     bool    is_base () const {
 157         return !(v & 1);
 158     }
 159
 160     /** Depth-first in-order binary tree traversal. */
 161     bin64_t next_dfsio (uint8_t floor);
 162
 163     /** Return the number of basic bins within this bin. */
 164     bin64_t width () const {
 165         return (tail_bits()+1)>>1;
 166     }
 167
 168     /** Get the standard-form null-terminated string
 169         representation of this bin, e.g. "(2,1)".
 170         The string is statically allocated, must
 171         not be reused or released. */
 172     const char* str () const;
 173
 174     /** The array must have 64 cells, as it is the max
 175      number of peaks possible +1 (and there are no reason
 176      to assume there will be less in any given case. */
 177     static int peaks (uint64_t length, bin64_t* peaks) ;
 178
 179 };
 180
 181
 182 #endif
 183
 184 /**
 185                  00111
 186        0011                    1011
 187   001      101         1001          1101
 188 0   10  100  110    1000  1010   1100   1110
 189
 190                   7
 191       3                         11
 192   1        5             9             13
 193 0   2    4    6       8    10      12     14
 194
 195 once we have peak hashes, this struture is more natural than bin-v1
 196
 197 */