add .gitignore

[swift-upb.git] / bin64.h

diff --git a/bin64.h b/bin64.h
index 8ca1d6f..fb88c99 100644 (file)
--- a/bin64.h
+++ b/bin64.h
@@ -1,11 +1,15 @@
+/*
+ *  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 _WIN32
-    #include "compat/stdint.h"
-#else
-    #include <stdint.h>
-#endif
+#include "compat.h"
 
 
 /** Numbering for (aligned) logarithmical bins.
@@ -15,7 +19,11 @@
     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;
@@ -25,6 +33,7 @@ struct bin64_t {
 
     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) ) {}
@@ -43,6 +52,7 @@ struct bin64_t {
         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));
@@ -65,32 +75,40 @@ struct bin64_t {
         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;
@@ -107,18 +125,30 @@ struct bin64_t {
             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());
     }
 
@@ -130,9 +160,16 @@ struct bin64_t {
     /** 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