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