libcds/src/static_bitsequence/table_offset.h

   1 /* table_offset.h
   2  * Copyright (C) 2008, Francisco Claude, all rights reserved.
   3  *
   4  * Table for offsets definition.
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  */
  21
  22 #ifndef _TABLE_OFFSET_H
  23 #define _TABLE_OFFSET_H
  24
  25 #include <basics.h>
  26 #include <iostream>
  27
  28 //using namespace std;
  29
  30 /** Universal table required for static_bitsequence_rrr02, Raman, Raman and Rao's [1]
  31  *  proposal for rank/select capable data structures, it achieves space nH_0,
  32  *  O(sample_rate) time for rank and O(log len) for select. The practial implementation
  33  *  is based on [2]
  34  *
  35  *  [1] R. Raman, V. Raman and S. Rao. Succinct indexable dictionaries with applications
  36  *     to encoding $k$-ary trees and multisets. SODA02.
  37  *  [2] F. Claude and G. Navarro. Practical Rank/Select over Arbitrary Sequences. SPIRE08.
  38  *
  39  *  @author Francisco Claude
  40  */
  41 class table_offset {
  42
  43 public:
  44   /** builds a universal table, designed for u<=15 */
  45         table_offset(uint u);
  46         ~table_offset();
  47
  48         /** Increments the counter of users for the table */
  49         inline void use() {
  50                 users_count++;
  51         }
  52
  53         /** Tells the object that the user is not going to need the table anymore. */
  54         inline table_offset * unuse() {
  55                 users_count--;
  56                 if(!users_count) {
  57                         delete this;
  58       return NULL;
  59     }
  60     return this;
  61         }
  62
  63         /** Computes binomial(n,k) for n,k<=u */
  64         inline uint get_binomial(uint n, uint k) {
  65                 return binomial[n][k];
  66         }
  67
  68         /** Computes ceil(log2(binomial(n,k))) for n,k<=u */
  69         inline ushort get_log2binomial(uint n, uint k) {
  70                 return log2binomial[n][k];
  71         }
  72
  73         /** Returns the bitmap represented by the given class and inclass offsets */
  74         inline ushort short_bitmap(uint class_offset, uint inclass_offset) {
  75                 if(class_offset==0) return 0;
  76                 if(class_offset==u) return (ushort)(((uint)1<<u)-1);
  77                 return short_bitmaps[offset_class[class_offset]+inclass_offset];
  78         }
  79
  80         /** Returns u */
  81         inline uint get_u() {
  82                 return u;
  83         }
  84
  85         /** Computes the offset of the first u bits of a given bitstring */
  86         inline ushort compute_offset(ushort v) {
  87                 return rev_offset[v];
  88         }
  89
  90         /** Returns the size of the bitmap in bytes */
  91         uint size();
  92
  93 protected:
  94         int users_count;
  95         uint u;
  96         uint ** binomial;
  97         ushort * rev_offset;
  98         ushort ** log2binomial;
  99         ushort * offset_class;
 100         ushort * short_bitmaps;
 101
 102         void fill_tables();
 103 };
 104
 105 #endif