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         table_offset(uint u);
  45         ~table_offset();
  46
  47         /** Increments the counter of users for the table */
  48         inline void use() {
  49                 users_count++;
  50         }
  51
  52         /** Tells the object that the user is not going to need the table anymore. */
  53         inline table_offset * unuse() {
  54                 users_count--;
  55                 if(!users_count) {
  56                         delete this;
  57       return NULL;
  58     }
  59     return this;
  60         }
  61
  62         /** Computes binomial(n,k) for n,k<=u */
  63         inline uint get_binomial(uint n, uint k) {
  64                 return binomial[n][k];
  65         }
  66
  67         /** Computes ceil(log2(binomial(n,k))) for n,k<=u */
  68         inline ushort get_log2binomial(uint n, uint k) {
  69                 return log2binomial[n][k];
  70         }
  71
  72         /** Returns the bitmap represented by the given class and inclass offsets */
  73         inline ushort short_bitmap(uint class_offset, uint inclass_offset) {
  74                 if(class_offset==0) return 0;
  75                 if(class_offset==u) return (ushort)(((uint)1<<u)-1);
  76                 return short_bitmaps[offset_class[class_offset]+inclass_offset];
  77         }
  78
  79         /** Returns u */
  80         inline uint get_u() {
  81                 return u;
  82         }
  83
  84         /** Computes the offset of the first u bits of a given bitstring */
  85         inline ushort compute_offset(ushort v) {
  86                 return rev_offset[v];
  87         }
  88
  89         /** Returns the size of the bitmap in bytes */
  90         uint size();
  91
  92 protected:
  93         int users_count;
  94         uint u;
  95         uint ** binomial;
  96         ushort * rev_offset;
  97         ushort ** log2binomial;
  98         ushort * offset_class;
  99         ushort * short_bitmaps;
 100
 101         void fill_tables();
 102 };
 103
 104 #endif
 105