Hufman-Shaped Integer Wavelet Tree with fixed-size Alphabet

[Jabro]

Hello,

When construction a huffman-shaped integer wavelet tree from a fixed-width integer, the result seems to be wrong:

wt_huff_int<> wt;
int_vector<8> vec = {3,12,4,4,5,1,6,4,2};
construct_im(wt, vec);
cout << "wt.sigma : " << wt.sigma << endl; //5
cout << wt << endl; //4 1 0 2 0 0 1 0 5 0 4 0 0 4 1 0 4 0 0 1 0 0 0 0

I noticed a similar issue #145 which is already closed. Unfortunately the supposed fix won't compile on recent versions of the sdsl (no matching function for call to ‘serialize(const sdsl::int_vector<64u>::raw_wrapper&, sdsl::osfstream&)’)

Regards & Thanks,
Jan

[Jabro]

Unfortunately #340 doesn't fix the issue.

The above code still leads to the same output.
The code suggested in #145 now compiles, but leads to an empty wavelet tree.

[Jabro]

When using the patch and the third parameter of the construct_im method to set the amount of bytes of the alphabet, the construction works!

    wt_huff_int<> wt;
    int_vector<8> vec = {3,12,4,4,5,1,6,4,2};
    construct_im(wt, vec.raw, 1);
    cout << "wt.sigma : " << wt.sigma << endl;
    cout << wt << endl;

Is this intended behavior?

[simongog]

Yes, of course ;)

[Jabro]

Unfortunately when using a non byte-sized alphabet the construction fails, because there seems to be a bug when serializing raw int_vectors which are not byte sized.

When I run the following code and look at the file with a hex editor, it only contains the first 2 numbers encoded as 32 Bit.

    int_vector<32> vec = {3,12,4,4,5,1,6,4,2};
    store_to_file(vec.raw, "file");

Storing to file also happens during the construction in construct.hpp:70

[Jabro]

When I change back line include/sdsl/int_vector.hpp:612 to write_data instead of raw_data, everything works like a charm.

It seems that the provided pull request breaks the serialization of the raw_int_vector.
Without it the program won't compile, but adding the following line (as in the pull request) in int_vector.hpp:604 seems to fix the problems:

typedef int_vector::size_type size_type;