X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;ds=inline;f=src%2Fstatic_bitsequence%2Ftable_offset.cpp;fp=src%2Fstatic_bitsequence%2Ftable_offset.cpp;h=e2350edb8013ad0eb81930d5cffab45546874d9b;hb=3fd4bcef236556c7f3bff1d2be8d3f4206245501;hp=0000000000000000000000000000000000000000;hpb=dc7a566a39187bfcea70737cda7278f858cd9842;p=SXSI%2Flibcds.git

diff --git a/src/static_bitsequence/table_offset.cpp b/src/static_bitsequence/table_offset.cpp
new file mode 100644
index 0000000..e2350ed
--- /dev/null
+++ b/src/static_bitsequence/table_offset.cpp
@@ -0,0 +1,123 @@
+/* table_offset.cpp
+ * Copyright (C) 2008, Francisco Claude, all rights reserved.
+ *
+ * Table for offsets.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ */
+ 
+ 
+#include "table_offset.h"
+
+
+// Interface for old implementation
+void genera(ushort * bch, uint u, ushort * F, uint lF);
+uint generaClase(ushort * bch, uint u, uint clase, uint puestos, uint pos_ini, uint generado);
+uint offset_func(uint u, uint busca);
+uint offsetRecursivo(uint u, uint busca, uint clase, uint puestos, uint pos_ini, uint generado);
+uint __indiceFunc;
+uint __indAcumulado;
+ushort * __Lis;
+// End interface old implementation
+
+
+table_offset::table_offset(uint u) {
+	this->u = u;
+	users_count = 0;
+	short_bitmaps = new ushort[((1<<u)+1)];
+	offset_class = new ushort[u+2];
+	binomial = new uint*[u+1];
+	log2binomial = new ushort*[u+1];
+	for(uint i=0;i<u+1;i++) {
+		binomial[i] = new uint[u+1];
+		log2binomial[i] = new ushort[u+1];
+		for(uint j=0;j<u+1;j++) {
+			binomial[i][j] = 0;
+			log2binomial[i][j] = 0;
+		}
+	}
+	for(uint i=0;i<u+1;i++) {
+		binomial[i][0] = 1;
+		binomial[i][1] = 1;
+		binomial[i][i] = 1;
+		log2binomial[i][0] = 0;
+		log2binomial[i][1] = 0;
+		log2binomial[i][i] = 0;
+	}
+	for(uint j=1;j<u+1;j++) {
+		for(uint i=j+1;i<u+1;i++) {
+			binomial[i][j] = binomial[i-1][j-1]+binomial[i-1][j];
+			log2binomial[i][j] = bits(binomial[i][j]-1);
+		}
+  }
+	fill_tables();
+}
+
+void table_offset::fill_tables() {
+	genera(short_bitmaps, u, offset_class, u);
+	rev_offset = __Lis;
+	//delete [] __Lis;
+}
+
+table_offset::~table_offset() {
+	delete [] short_bitmaps;
+	delete [] offset_class;
+	for(uint i=0;i<u+1;i++) {
+		delete [] binomial[i];
+		delete [] log2binomial[i];
+	}
+	delete [] binomial;
+	delete [] log2binomial;
+	delete [] rev_offset;
+}
+
+uint table_offset::size() {
+	uint ret = sizeof(ushort)*(((1<<u)+1)+u+1);
+	ret += (sizeof(uint)+sizeof(ushort))*((u+1)*(u+1));
+	ret += sizeof(ushort)*(2<<(u+1));
+  ret += sizeof(ushort)*(u+2);
+	return ret;
+}
+
+// OLD implementation, replace
+
+void genera(ushort * bch, uint u, ushort * F, uint lF) {
+    __indAcumulado=0;
+    __indiceFunc=0;
+    F[0]=0;
+    __Lis = new ushort[(2<<(u+1))]; //(uint *)malloc((2<<u+1)*sizeof(uint));
+    for (uint i=0;i<=u;i++) {
+        __indAcumulado += generaClase(bch, u, i, 0, 0, 0);
+        F[i+1] = __indiceFunc;
+    }
+}
+
+uint generaClase(ushort * bch, uint u, uint clase, uint puestos, uint pos_ini, uint generado) {
+    uint ret=0;
+    if (clase==puestos) {
+        bch[__indiceFunc] = generado;
+        __Lis[generado] = __indiceFunc-__indAcumulado;
+        __indiceFunc++;
+        return 1;
+    }
+    if (clase<puestos)
+        return 0;
+    for (uint i=pos_ini;i<u;i++) {
+        uint tmp = generado | (1<<i);
+        ret += generaClase(bch, u, clase, puestos+1, i+1, tmp);
+    }
+    return ret;
+}