1 /* static_sequence_wvtree_noptrs.h
2 * Copyright (C) 2008, Francisco Claude, all rights reserved.
4 * static_sequence_wvtree_noptrs definition
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.
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.
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
22 #ifndef _STATIC_SEQUENCE_WVTREE_NOPTRS_H
23 #define _STATIC_SEQUENCE_WVTREE_NOPTRS_H
28 #include <static_bitsequence.h>
29 #include <static_bitsequence_builder.h>
30 #include <static_sequence.h>
31 #include <alphabet_mapper.h>
35 class static_sequence_wvtree_noptrs : public static_sequence {
38 /** Builds a Wavelet Tree for the string
39 * pointed by symbols assuming its length
40 * equals n and uses bmb to build the bitsequence */
41 static_sequence_wvtree_noptrs(uint * symbols, uint n, static_bitsequence_builder * bmb, alphabet_mapper * am);
43 /** Destroys the Wavelet Tree */
44 virtual ~static_sequence_wvtree_noptrs();
46 virtual uint rank(uint symbol, uint pos);
47 virtual uint select(uint symbol, uint i);
48 virtual uint access(uint pos);
51 virtual uint save(FILE *fp);
52 static static_sequence_wvtree_noptrs * load(FILE *fp);
56 static_sequence_wvtree_noptrs();
59 /** Only one bit-string for the Wavelet Tree. */
60 static_bitsequence **bitstring, *occ;
62 /** Length of the string. */
65 /** Height of the Wavelet Tree. */
68 /** Obtains the maximum value from the string
69 * symbols of length n */
70 uint max_value(uint * symbols, uint n);
72 /** How many bits are needed to represent val */
75 /** Returns true if val has its ind-th bit set
77 bool is_set(uint val, uint ind);
79 /** Sets the ind-th bit in val */
80 uint set(uint val, uint ind);
82 /** Recursive function for building the Wavelet Tree. */
83 void build_level(uint **bm, uint *symbols, uint level, uint length, uint offset);