From 450ba3c9c74665094fb8f6821d6cc92d2bf23011 Mon Sep 17 00:00:00 2001 From: fclaude Date: Tue, 25 Nov 2008 02:32:59 +0000 Subject: [PATCH] testing git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@11 3cdefd35-fc62-479d-8e8d-bae585ffb9ca --- .../src/static_sequence/static_sequence.cpp | 22 ++++- .../static_sequence_gmr_chunk.cpp | 87 +++++++++++++++++++ .../static_sequence_gmr_chunk.h | 48 ++++++++++ .../static_sequence_wvtree.cpp | 26 ++++-- .../static_sequence/static_sequence_wvtree.h | 32 ++++++- libcds/src/static_sequence/wt_coder.cpp | 23 ++++- libcds/src/static_sequence/wt_coder.h | 33 ++++++- .../src/static_sequence/wt_coder_binary.cpp | 42 ++++++++- libcds/src/static_sequence/wt_coder_binary.h | 30 +++++++ libcds/src/static_sequence/wt_coder_huff.cpp | 22 ++++- libcds/src/static_sequence/wt_coder_huff.h | 31 ++++++- libcds/src/static_sequence/wt_node.cpp | 2 +- libcds/src/static_sequence/wt_node.h | 6 +- .../src/static_sequence/wt_node_internal.cpp | 23 ++++- libcds/src/static_sequence/wt_node_internal.h | 27 +++++- libcds/src/static_sequence/wt_node_leaf.cpp | 20 +++++ libcds/src/static_sequence/wt_node_leaf.h | 25 +++++- libcds/tests/test_wvtree01.cpp | 54 +++++++++++- libcds/tests/test_wvtree02.cpp | 53 ++++++++++- 19 files changed, 576 insertions(+), 30 deletions(-) create mode 100644 libcds/src/static_sequence/static_sequence_gmr_chunk.cpp create mode 100644 libcds/src/static_sequence/static_sequence_gmr_chunk.h diff --git a/libcds/src/static_sequence/static_sequence.cpp b/libcds/src/static_sequence/static_sequence.cpp index 7f9fde2..0ba5c2a 100644 --- a/libcds/src/static_sequence/static_sequence.cpp +++ b/libcds/src/static_sequence/static_sequence.cpp @@ -1,4 +1,24 @@ - +/* static_sequence.cpp + * Copyright (C) 2008, Francisco Claude, all rights reserved. + * + * static_sequence definition + * + * 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 static_sequence::static_sequence() {} diff --git a/libcds/src/static_sequence/static_sequence_gmr_chunk.cpp b/libcds/src/static_sequence/static_sequence_gmr_chunk.cpp new file mode 100644 index 0000000..6705669 --- /dev/null +++ b/libcds/src/static_sequence/static_sequence_gmr_chunk.cpp @@ -0,0 +1,87 @@ + +#include "static_sequence_gmr_chunk.h" + +static_sequence_gmr_chunk::static_sequence_gmr_chunk(uint * sequence, uint chunk_length, static_bitsequence_builder *bmb, static_permutation_builder *pmb) { + sigma = 0; + for(uint i=0;iX = new BitRankW32Int(X_bitmap, X_pos, true,20); + assert(X!=NULL); + this->permutation = createPerm(pi, chunk_length, t); + assert(permutation!=NULL); + this->sigma = sigma; + this->chunk_length = chunk_length; + delete [] counter; +} + + +static_sequence_gmr_chunk::~static_sequence_gmr_chunk() { + delete X; + delete permutation; +} + + +uint static_sequence_gmr_chunk::caccess(uint j) { + uint invPerm = inversePerm(permutation, j); + uint rank_pos = X->select1(invPerm+1); + uint ret = rank_pos - X->rank(rank_pos);// - 1; + return ret; +} + + +uint static_sequence_gmr_chunk::cselect(uint i, uint j) { + uint pos = X->select0(i+1) + j - i -1; + return getelemPerm(permutation, pos); +} + + +uint static_sequence_gmr_chunk::crank(uint i, uint j) { + uint ini = X->select0(i+1)-i; + uint ini_o = ini; + uint fin = X->select0(i+2); + if(fin j) return 0; + if(getelemPerm(permutation,ini) == j) return 1; + if(ini==fin) return 1; + while(ini < fin-1) { + uint med = (ini+fin)/2; + uint elem = getelemPerm(permutation, med); + if(elem >= j) fin = med; + else ini = med; + } + while(fin>ini_o && getelemPerm(permutation, fin)>j) fin--; + return fin-ini_o+1; +} + + +uint static_sequence_gmr_chunk::size() { + return sizeof(BitRankW32Int*)+sizeof(perm*)+(X->SpaceRequirementInBits()/8+sizeofPerm(permutation)); +} diff --git a/libcds/src/static_sequence/static_sequence_gmr_chunk.h b/libcds/src/static_sequence/static_sequence_gmr_chunk.h new file mode 100644 index 0000000..a06b635 --- /dev/null +++ b/libcds/src/static_sequence/static_sequence_gmr_chunk.h @@ -0,0 +1,48 @@ + +#ifndef _STATIC_SEQUENCE_GMR_CHUNK_H +#define _STATIC_SEQUENCE_GMR_CHUNK_H + +#include +#include +#include +#include +#include +#include + +using namespace std; + +/** Implementation of the Chunk of Golynski et al's rank/select + * data structure [1]. + * + * [1] A. Golynski and I. Munro and S. Rao. + * Rank/select operations on large alphabets: a tool for text indexing. + * SODA 06. + * + * @author Francisco Claude + */ +class static_sequence_gmr_chunk: public static_sequence { + public: + /** Builds the structures needed for the chunk */ + static_sequence_gmr_chunk(uint * sequence, uint chunk_length, static_bitsequence_builder *bmb, static_permutation_builder *pmb); + + /** Destroy the chunk */ + ~static_sequence_gmr_chunk(); + + virtual uint access(uint j); + virtual uint select(uint i, uint j); + virtual uint rank(uint i, uint j); + virtual uint size(); + virtual uint save(FILE *fp); + static_sequence_gmr_chunk * load(FILE *fp); + + protected: + /** Bitmap */ + static_bitsequence * X; + /** Permutation */ + static_permutation permutation; + /** Size of the alphabet */ + uint sigma; + /** Length of the chunk */ + uint chunk_length; +}; +#endif diff --git a/libcds/src/static_sequence/static_sequence_wvtree.cpp b/libcds/src/static_sequence/static_sequence_wvtree.cpp index efdd8f7..b1353d4 100644 --- a/libcds/src/static_sequence/static_sequence_wvtree.cpp +++ b/libcds/src/static_sequence/static_sequence_wvtree.cpp @@ -1,4 +1,24 @@ - +/* static_sequence_wvtree.h + * Copyright (C) 2008, Francisco Claude, all rights reserved. + * + * static_sequence_wvtree definition + * + * 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 static_sequence_wvtree::static_sequence_wvtree(uint * symbols, uint n, wt_coder * c, static_bitsequence_builder * bmb, alphabet_mapper * am) { @@ -6,16 +26,13 @@ static_sequence_wvtree::static_sequence_wvtree(uint * symbols, uint n, wt_coder symbols[i] = am->map(symbols[i]); this->am = am; this->c=c; - cout << "Building..."; cout.flush(); root = new wt_node_internal(symbols, n, 0, c, bmb); - cout << "done" << endl; cout.flush(); for(uint i=0;iunmap(symbols[i]); } static_sequence_wvtree::static_sequence_wvtree() {} - static_sequence_wvtree::~static_sequence_wvtree() { delete root; delete am; @@ -68,4 +85,3 @@ static_sequence_wvtree * static_sequence_wvtree::load(FILE *fp) { ret->root = wt_node::load(fp); return ret; } - diff --git a/libcds/src/static_sequence/static_sequence_wvtree.h b/libcds/src/static_sequence/static_sequence_wvtree.h index b93caf2..f972648 100644 --- a/libcds/src/static_sequence/static_sequence_wvtree.h +++ b/libcds/src/static_sequence/static_sequence_wvtree.h @@ -1,6 +1,27 @@ - +/* static_sequence_wvtree.h + * Copyright (C) 2008, Francisco Claude, all rights reserved. + * + * static_sequence_wvtree definition + * + * 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 + * + */ + #ifndef STATIC_SEQUENCE_WVTREE_H #define STATIC_SEQUENCE_WVTREE_H + #include #include #include @@ -13,14 +34,16 @@ using namespace std; +/** Wavelet tree implementation using pointers. + * + * @author Francisco Claude + */ class static_sequence_wvtree : public static_sequence { public: /** Builds a Wavelet Tree for the string * pointed by symbols assuming its length - * equals n and the test flag allows to set - * if the structure must be tested for - * correctness after being created (this is very expensive). */ + * equals n */ static_sequence_wvtree(uint * symbols, uint n, wt_coder * coder, static_bitsequence_builder * bmb, alphabet_mapper * am); virtual ~static_sequence_wvtree(); @@ -37,6 +60,7 @@ class static_sequence_wvtree : public static_sequence { virtual uint save(FILE * fp); static static_sequence_wvtree * load(FILE *fp); + protected: static_sequence_wvtree(); diff --git a/libcds/src/static_sequence/wt_coder.cpp b/libcds/src/static_sequence/wt_coder.cpp index 1a8cd99..147e939 100644 --- a/libcds/src/static_sequence/wt_coder.cpp +++ b/libcds/src/static_sequence/wt_coder.cpp @@ -1,4 +1,24 @@ - +/* wt_coder.cpp + * Copyright (C) 2008, Francisco Claude, all rights reserved. + * + * wt_coder definition + * + * 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 wt_coder * wt_coder::load(FILE *fp) { @@ -7,6 +27,7 @@ wt_coder * wt_coder::load(FILE *fp) { fseek(fp,-sizeof(uint),SEEK_CUR); switch(rd) { case WT_CODER_HUFF_HDR: return wt_coder_huff::load(fp); + case WT_CODER_BINARY_HDR: return wt_coder_binary::load(fp); } return NULL; } diff --git a/libcds/src/static_sequence/wt_coder.h b/libcds/src/static_sequence/wt_coder.h index 4b7d4da..1a55397 100644 --- a/libcds/src/static_sequence/wt_coder.h +++ b/libcds/src/static_sequence/wt_coder.h @@ -1,4 +1,24 @@ - +/* wt_coder.h + * Copyright (C) 2008, Francisco Claude, all rights reserved. + * + * wt_coder definition + * + * 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 + * + */ + #ifndef wt_coder_h #define wt_coder_h @@ -8,14 +28,24 @@ using namespace std; #define WT_CODER_HUFF_HDR 2 +#define WT_CODER_BINARY_HDR 3 +/** Coder that defines the shape of a wavelet tree + * + * @author Francisco Claude + */ class wt_coder { public: virtual ~wt_coder() {}; + /** Tells if at level l the symbol is represented by a one or a zero */ virtual bool is_set(uint symbol, uint l)=0; + /** Tells if the path of symbol becomes unique at level l */ virtual bool done(uint symbol, uint l)=0; + /** Returns the size of the coder */ virtual uint size()=0; + /** Saves the coder to a file, returns 0 in case of success */ virtual uint save(FILE *fp)=0; + /** Loads a coder from a file, returns NULL in case of error */ static wt_coder * load(FILE *fp); }; @@ -23,4 +53,3 @@ class wt_coder { #include #endif - diff --git a/libcds/src/static_sequence/wt_coder_binary.cpp b/libcds/src/static_sequence/wt_coder_binary.cpp index 11ba4f5..cdbac13 100644 --- a/libcds/src/static_sequence/wt_coder_binary.cpp +++ b/libcds/src/static_sequence/wt_coder_binary.cpp @@ -1,4 +1,24 @@ - +/* wt_coder_binary.cpp + * Copyright (C) 2008, Francisco Claude, all rights reserved. + * + * wt_coder_binary definition + * + * 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 wt_coder_binary::wt_coder_binary(uint * seq, uint n, alphabet_mapper * am) { @@ -8,6 +28,8 @@ wt_coder_binary::wt_coder_binary(uint * seq, uint n, alphabet_mapper * am) { h=bits(max_v); } +wt_coder_binary::wt_coder_binary() {} + wt_coder_binary::~wt_coder_binary() {} bool wt_coder_binary::is_set(uint symbol, uint l) { @@ -24,3 +46,21 @@ uint wt_coder_binary::size() { return sizeof(wt_coder_binary); } +uint wt_coder_binary::save(FILE *fp) { + uint wr = WT_CODER_BINARY_HDR; + wr = fwrite(&wr,sizeof(uint),1,fp); + wr += fwrite(&h,sizeof(uint),1,fp); + return wr-2; +} + +wt_coder_binary * wt_coder_binary::load(FILE *fp) { + uint rd; + if(fread(&rd,sizeof(uint),1,fp)!=1) return NULL; + if(rd!=WT_CODER_BINARY_HDR) return NULL; + wt_coder_binary * ret = new wt_coder_binary(); + if(fread(&ret->h,sizeof(uint),1,fp)!=1) { + delete ret; + return NULL; + } + return ret; +} diff --git a/libcds/src/static_sequence/wt_coder_binary.h b/libcds/src/static_sequence/wt_coder_binary.h index e784281..2b87854 100644 --- a/libcds/src/static_sequence/wt_coder_binary.h +++ b/libcds/src/static_sequence/wt_coder_binary.h @@ -1,3 +1,24 @@ +/* wt_coder_binary.h + * Copyright (C) 2008, Francisco Claude, all rights reserved. + * + * wt_coder_binary definition + * + * 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 + * + */ + #ifndef wt_coder_binary_h #define wt_coder_binary_h @@ -6,15 +27,24 @@ #include #include +/** Considers the binary representation of the symbols as the code + * + * @author Francisco Claude + */ class wt_coder_binary: public wt_coder { public: + /** Buils a wt_coder_binary using the sequence of length n and the alphabet_mapper + * to determine the length of the binary codes */ wt_coder_binary(uint * seq, uint n, alphabet_mapper * am); virtual ~wt_coder_binary(); virtual bool is_set(uint symbol, uint l); virtual bool done(uint symbol, uint l); virtual uint size(); + virtual uint save(FILE *fp); + static wt_coder_binary * load(FILE *fp); protected: + wt_coder_binary(); uint h; }; diff --git a/libcds/src/static_sequence/wt_coder_huff.cpp b/libcds/src/static_sequence/wt_coder_huff.cpp index f5fafef..cf831dc 100644 --- a/libcds/src/static_sequence/wt_coder_huff.cpp +++ b/libcds/src/static_sequence/wt_coder_huff.cpp @@ -1,4 +1,24 @@ - +/* wt_coder_huff.cpp + * Copyright (C) 2008, Francisco Claude, all rights reserved. + * + * wt_coder_huff definition + * + * 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 wt_coder_huff::wt_coder_huff(uint * symbs, uint n, alphabet_mapper * am) { diff --git a/libcds/src/static_sequence/wt_coder_huff.h b/libcds/src/static_sequence/wt_coder_huff.h index cb05056..85fa2f7 100644 --- a/libcds/src/static_sequence/wt_coder_huff.h +++ b/libcds/src/static_sequence/wt_coder_huff.h @@ -1,4 +1,24 @@ - +/* wt_coder_huff.h + * Copyright (C) 2008, Francisco Claude, all rights reserved. + * + * wt_coder_huff definition + * + * 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 + * + */ + #ifndef wt_coder_huff_h #define wt_coder_huff_h @@ -7,8 +27,14 @@ #include #include +/** Uses huffman codes to determine the shape of the wavelet tree + * + * @author Francisco Claude + */ class wt_coder_huff: public wt_coder { public: + /** Buils a wt_coder_huff using the sequence of length n and the alphabet_mapper + * to determine the huffman codes */ wt_coder_huff(uint *symbs, uint n, alphabet_mapper * am); virtual ~wt_coder_huff(); virtual bool is_set(uint symbol, uint l); @@ -16,7 +42,7 @@ class wt_coder_huff: public wt_coder { virtual uint size(); virtual uint save(FILE *fp); static wt_coder_huff * load(FILE *fp); - uint * get_buffer(uint symbol, uint *n); + //uint * get_buffer(uint symbol, uint *n); protected: wt_coder_huff(); @@ -26,4 +52,3 @@ class wt_coder_huff: public wt_coder { }; #endif - diff --git a/libcds/src/static_sequence/wt_node.cpp b/libcds/src/static_sequence/wt_node.cpp index 8240a2a..5ab20ce 100644 --- a/libcds/src/static_sequence/wt_node.cpp +++ b/libcds/src/static_sequence/wt_node.cpp @@ -1,4 +1,4 @@ -/* wt_node.h +/* wt_node.cpp * Copyright (C) 2008, Francisco Claude, all rights reserved. * * wt_node diff --git a/libcds/src/static_sequence/wt_node.h b/libcds/src/static_sequence/wt_node.h index 14ea05c..9e758a3 100644 --- a/libcds/src/static_sequence/wt_node.h +++ b/libcds/src/static_sequence/wt_node.h @@ -29,7 +29,10 @@ #define WT_NODE_INTERNAL_HDR 2 #define WT_NODE_LEAF_HDR 3 - +/** Base clase for nodes in the wavelet tree + * + * @author Francisco Claude + */ class wt_node { public: virtual ~wt_node() {} @@ -45,4 +48,3 @@ class wt_node { #include #endif - diff --git a/libcds/src/static_sequence/wt_node_internal.cpp b/libcds/src/static_sequence/wt_node_internal.cpp index e741b6f..ce5de07 100644 --- a/libcds/src/static_sequence/wt_node_internal.cpp +++ b/libcds/src/static_sequence/wt_node_internal.cpp @@ -1,7 +1,26 @@ - +/* wt_node_internal.cpp + * Copyright (C) 2008, Francisco Claude, all rights reserved. + * + * wt_node_internal + * + * 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 - wt_node_internal::wt_node_internal(uint * symbols, uint n, uint l, wt_coder * c, static_bitsequence_builder * bmb) { uint * ibitmap = new uint[n/W+1]; for(uint i=0;i #include +/** Clase for representing internal nodes + * + * @author Francisco Claude + */ class wt_node_internal: public wt_node { public: wt_node_internal(uint * seq, uint n, uint l, wt_coder * c, static_bitsequence_builder * bmb); @@ -30,4 +54,3 @@ class wt_node_internal: public wt_node { }; #endif - diff --git a/libcds/src/static_sequence/wt_node_leaf.cpp b/libcds/src/static_sequence/wt_node_leaf.cpp index 6f6c887..e3b7c19 100644 --- a/libcds/src/static_sequence/wt_node_leaf.cpp +++ b/libcds/src/static_sequence/wt_node_leaf.cpp @@ -1,3 +1,23 @@ +/* wt_node_leaf.cpp + * Copyright (C) 2008, Francisco Claude, all rights reserved. + * + * wt_node_leaf + * + * 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 diff --git a/libcds/src/static_sequence/wt_node_leaf.h b/libcds/src/static_sequence/wt_node_leaf.h index a64c2a2..b8ff85e 100644 --- a/libcds/src/static_sequence/wt_node_leaf.h +++ b/libcds/src/static_sequence/wt_node_leaf.h @@ -1,3 +1,23 @@ +/* wt_node_leaf.h + * Copyright (C) 2008, Francisco Claude, all rights reserved. + * + * wt_node_leaf + * + * 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 + * + */ #ifndef wt_node_leaf_h #define wt_node_leaf_h @@ -7,6 +27,10 @@ #include #include +/** Class for representing leaves of the wavelet tree. + * + * @author Francisco Claude + */ class wt_node_leaf: public wt_node { public: wt_node_leaf(uint symbol, uint count); @@ -25,4 +49,3 @@ class wt_node_leaf: public wt_node { }; #endif - diff --git a/libcds/tests/test_wvtree01.cpp b/libcds/tests/test_wvtree01.cpp index 48f6951..ffd09c3 100644 --- a/libcds/tests/test_wvtree01.cpp +++ b/libcds/tests/test_wvtree01.cpp @@ -9,6 +9,53 @@ using namespace std; +void test_static_sequence(uint * symbols, uint n, static_sequence * ss) { + cout << "Size: " << ss->size() << endl; + uint max_v=0; + for(uint i=0;iaccess(i); + uint r = ss->rank(symbols[i],i); + uint s = ss->select(symbols[i],occ[symbols[i]]); + uint rM1 = (i==0)?0:ss->rank(symbols[i],i-1); + if(r!=occ[symbols[i]]) { + cout << "Error in rank for symbol " << symbols[i] << " at position " << i << endl; + cout << "value: " << r << endl; + cout << "Expected: " << occ[symbols[i]] << endl; + error = true; + } + if(s!=i) { + cout << "Error in select for symbol " << symbols[i] << " at position " << occ[symbols[i]] << endl; + cout << "value: " << s << endl; + cout << "Expected: " << i << endl; + error = true; + } + if(a!=symbols[i]) { + cout << "Error in access at position " << i << endl; + cout << "value: " << a << endl; + cout << "Expected: " << symbols[i] << endl; + error = true; + } + if(rM1!=occ[symbols[i]]-1) { + cout << "Error in rankM1 for symbol " << symbols[i] << " at position " << i-1 << endl; + cout << "value: " << rM1 << endl; + cout << "Expected: " << occ[symbols[i]]-1 << endl; + error = true; + } + } + if(!error) + cout << "Test OK! It works :)" << endl; + delete [] occ; +} + int main(int argc, char ** argv) { if(argc!=3) { cout << "usage: " << argv[0] << " " << endl; @@ -60,7 +107,9 @@ int main(int argc, char ** argv) { cout << "Building Huffman table..."; cout.flush(); wt_coder * wtc = new wt_coder_huff(text,n,am); cout << "done" << endl; cout.flush(); - static_sequence * wt = new static_sequence_wvtree(text,n,wtc,bmb,am,true); + cout << "Building static_sequence..."; cout.flush(); + static_sequence * wt = new static_sequence_wvtree(text,n,wtc,bmb,am); + cout << "done" << endl; cout.flush(); delete bmb; char * fname = new char[10+string(argv[1]).length()]; @@ -74,7 +123,8 @@ int main(int argc, char ** argv) { fclose(fp); delete [] fname; - + test_static_sequence(text,n,wt); + cout << "WT Size: " << wt->size() << endl; cout << "ft = " << 1.*wt->size()/(bits(max_symbol-1)*n/8) << endl; diff --git a/libcds/tests/test_wvtree02.cpp b/libcds/tests/test_wvtree02.cpp index 8a76c72..9b49aca 100644 --- a/libcds/tests/test_wvtree02.cpp +++ b/libcds/tests/test_wvtree02.cpp @@ -9,6 +9,53 @@ using namespace std; +void test_static_sequence(uint * symbols, uint n, static_sequence * ss) { + cout << "Size: " << ss->size() << endl; + uint max_v=0; + for(uint i=0;iaccess(i); + uint r = ss->rank(symbols[i],i); + uint s = ss->select(symbols[i],occ[symbols[i]]); + uint rM1 = (i==0)?0:ss->rank(symbols[i],i-1); + if(r!=occ[symbols[i]]) { + cout << "Error in rank for symbol " << symbols[i] << " at position " << i << endl; + cout << "value: " << r << endl; + cout << "Expected: " << occ[symbols[i]] << endl; + error = true; + } + if(s!=i) { + cout << "Error in select for symbol " << symbols[i] << " at position " << occ[symbols[i]] << endl; + cout << "value: " << s << endl; + cout << "Expected: " << i << endl; + error = true; + } + if(a!=symbols[i]) { + cout << "Error in access at position " << i << endl; + cout << "value: " << a << endl; + cout << "Expected: " << symbols[i] << endl; + error = true; + } + if(rM1!=occ[symbols[i]]-1) { + cout << "Error in rankM1 for symbol " << symbols[i] << " at position " << i-1 << endl; + cout << "value: " << rM1 << endl; + cout << "Expected: " << occ[symbols[i]]-1 << endl; + error = true; + } + } + if(!error) + cout << "Test OK! It works :)" << endl; + delete [] occ; +} + int main(int argc, char ** argv) { if(argc!=3) { cout << "usage: " << argv[0] << " " << endl; @@ -63,7 +110,9 @@ int main(int argc, char ** argv) { cout << "Building Huffman table..."; cout.flush(); wt_coder * wtc = new wt_coder_huff(text,n,am); cout << "done" << endl; cout.flush(); - static_sequence * wt = new static_sequence_wvtree(text,n,wtc,bmb,am,true); + cout << "Building static_sequence..."; cout.flush(); + static_sequence * wt = new static_sequence_wvtree(text,n,wtc,bmb,am); + cout << "done" << endl; cout.flush(); delete bmb; char * fname = new char[10+string(argv[1]).length()]; @@ -77,7 +126,7 @@ int main(int argc, char ** argv) { fclose(fp); delete [] fname; - ((static_sequence_wvtree*)wt)->test_structure(text,n); + test_static_sequence(text,n,wt); cout << "WT Size: " << wt->size() << endl; cout << "ft = " << 1.*wt->size()/n << endl; -- 2.17.1