src/static_bitsequence/table_offset.cpp

   1 /* table_offset.cpp
   2  * Copyright (C) 2008, Francisco Claude, all rights reserved.
   3  *
   4  * Table for offsets.
   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
  23 #include "table_offset.h"
  24
  25
  26 // Interface for old implementation
  27 void genera(ushort * bch, uint u, ushort * F, uint lF);
  28 uint generaClase(ushort * bch, uint u, uint clase, uint puestos, uint pos_ini, uint generado);
  29 uint offset_func(uint u, uint busca);
  30 uint offsetRecursivo(uint u, uint busca, uint clase, uint puestos, uint pos_ini, uint generado);
  31 uint __indiceFunc;
  32 uint __indAcumulado;
  33 ushort * __Lis;
  34 // End interface old implementation
  35
  36
  37 table_offset::table_offset(uint u) {
  38         this->u = u;
  39         users_count = 0;
  40         short_bitmaps = new ushort[((1<<u)+1)];
  41         offset_class = new ushort[u+2];
  42         binomial = new uint*[u+1];
  43         log2binomial = new ushort*[u+1];
  44         for(uint i=0;i<u+1;i++) {
  45                 binomial[i] = new uint[u+1];
  46                 log2binomial[i] = new ushort[u+1];
  47                 for(uint j=0;j<u+1;j++) {
  48                         binomial[i][j] = 0;
  49                         log2binomial[i][j] = 0;
  50                 }
  51         }
  52         for(uint i=0;i<u+1;i++) {
  53                 binomial[i][0] = 1;
  54                 binomial[i][1] = 1;
  55                 binomial[i][i] = 1;
  56                 log2binomial[i][0] = 0;
  57                 log2binomial[i][1] = 0;
  58                 log2binomial[i][i] = 0;
  59         }
  60         for(uint j=1;j<u+1;j++) {
  61                 for(uint i=j+1;i<u+1;i++) {
  62                         binomial[i][j] = binomial[i-1][j-1]+binomial[i-1][j];
  63                         log2binomial[i][j] = bits(binomial[i][j]-1);
  64                 }
  65   }
  66         fill_tables();
  67 }
  68
  69 void table_offset::fill_tables() {
  70         genera(short_bitmaps, u, offset_class, u);
  71         rev_offset = __Lis;
  72         //delete [] __Lis;
  73 }
  74
  75 table_offset::~table_offset() {
  76         delete [] short_bitmaps;
  77         delete [] offset_class;
  78         for(uint i=0;i<u+1;i++) {
  79                 delete [] binomial[i];
  80                 delete [] log2binomial[i];
  81         }
  82         delete [] binomial;
  83         delete [] log2binomial;
  84         delete [] rev_offset;
  85 }
  86
  87 uint table_offset::size() {
  88         uint ret = sizeof(ushort)*(((1<<u)+1)+u+1);
  89         ret += (sizeof(uint)+sizeof(ushort))*((u+1)*(u+1));
  90         ret += sizeof(ushort)*(2<<(u+1));
  91   ret += sizeof(ushort)*(u+2);
  92         return ret;
  93 }
  94
  95 // OLD implementation, replace
  96
  97 void genera(ushort * bch, uint u, ushort * F, uint lF) {
  98     __indAcumulado=0;
  99     __indiceFunc=0;
 100     F[0]=0;
 101     __Lis = new ushort[(2<<(u+1))]; //(uint *)malloc((2<<u+1)*sizeof(uint));
 102     for (uint i=0;i<=u;i++) {
 103         __indAcumulado += generaClase(bch, u, i, 0, 0, 0);
 104         F[i+1] = __indiceFunc;
 105     }
 106 }
 107
 108 uint generaClase(ushort * bch, uint u, uint clase, uint puestos, uint pos_ini, uint generado) {
 109     uint ret=0;
 110     if (clase==puestos) {
 111         bch[__indiceFunc] = generado;
 112         __Lis[generado] = __indiceFunc-__indAcumulado;
 113         __indiceFunc++;
 114         return 1;
 115     }
 116     if (clase<puestos)
 117         return 0;
 118     for (uint i=pos_ini;i<u;i++) {
 119         uint tmp = generado | (1<<i);
 120         ret += generaClase(bch, u, clase, puestos+1, i+1, tmp);
 121     }
 122     return ret;
 123 }