wavelet_partition.h File Reference

Bulk direction-mask and stable-partition primitives. More...

#include <pixie/bits.h>
#include <pixie/packed_bit_builder.h>
#include <algorithm>
#include <array>
#include <bit>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <limits>
#include <span>
#include <stdexcept>

Go to the source code of this file.

Functions
template<std::unsigned_integral Symbol>
std::uint64_t	pixie::detail::wavelet_direction_mask (std::span< const Symbol > ranks, Symbol middle)
template<bool WriteLeft, bool WriteRight, std::unsigned_integral Symbol>
void	pixie::detail::partition_wavelet_ranks_scalar (std::span< const Symbol > input, Symbol middle, std::span< Symbol > output, PackedBitBuilder &directions, std::size_t &left, std::size_t &right)
template<bool WriteLeft, bool WriteRight, std::unsigned_integral Symbol>
void	pixie::detail::partition_wavelet_ranks_impl (std::span< const Symbol > input, Symbol middle, std::span< Symbol > output, PackedBitBuilder &directions, std::size_t &left, std::size_t &right)
template<std::unsigned_integral Symbol>
void	pixie::detail::partition_wavelet_ranks (std::span< const Symbol > input, Symbol middle, std::span< Symbol > output, std::size_t expected_left, bool write_left, bool write_right, PackedBitBuilder &directions)
	Build packed node directions and stably partition ranks.
void	pixie::detail::map_wavelet_byte_ranks (std::span< const std::uint8_t > symbols, std::span< std::uint8_t > ranks, const std::array< std::uint8_t, 256 > &symbol_to_rank, const std::array< std::uint16_t, 256 > &symbol_to_high_rank)
void	pixie::detail::map_wavelet_byte_ranks (std::span< std::uint8_t > symbols, const std::array< std::uint8_t, 256 > &symbol_to_rank, const std::array< std::uint16_t, 256 > &symbol_to_high_rank)
template<bool WriteLeft, bool WriteRight>
std::size_t	pixie::detail::partition_wavelet_byte_block_scalar (std::span< std::uint8_t > ranks, std::uint8_t first_right, std::span< std::uint8_t > right_output, PackedBitBuilder &directions)
std::size_t	pixie::detail::partition_wavelet_byte_block (std::span< std::uint8_t > ranks, std::uint8_t first_right, std::span< std::uint8_t > right_output, bool write_left, bool write_right, PackedBitBuilder &directions)
	Emit a cache-sized byte block's directions and live child ranks.

Detailed Description

Bulk direction-mask and stable-partition primitives.

Function Documentation

map_wavelet_byte_ranks() [1/2]

void pixie::detail::map_wavelet_byte_ranks ( std::span< const std::uint8_t > symbols, std::span< std::uint8_t > ranks, const std::array< std::uint8_t, 256 > & symbol_to_rank, const std::array< std::uint16_t, 256 > & symbol_to_high_rank )

inline

Convert byte symbols to in-order leaf ranks.

map_wavelet_byte_ranks() [2/2]

void pixie::detail::map_wavelet_byte_ranks ( std::span< std::uint8_t > symbols, const std::array< std::uint8_t, 256 > & symbol_to_rank, const std::array< std::uint16_t, 256 > & symbol_to_high_rank )

inline

Convert one byte block to in-order leaf ranks in place.

partition_wavelet_byte_block()

std::size_t pixie::detail::partition_wavelet_byte_block ( std::span< std::uint8_t > ranks, std::uint8_t first_right, std::span< std::uint8_t > right_output, bool write_left, bool write_right, PackedBitBuilder & directions )

inline

Emit a cache-sized byte block's directions and live child ranks.

The left child is compacted in place and the right child is written to disjoint scratch. Node streams are appended bit-contiguously across blocks; PivCo's wire framing and per-block bitmap padding are not retained.

partition_wavelet_ranks()

template<std::unsigned_integral Symbol>

void pixie::detail::partition_wavelet_ranks	(	std::span< const Symbol >	input,
		Symbol	middle,
		std::span< Symbol >	output,
		std::size_t	expected_left,
		bool	write_left,
		bool	write_right,
		PackedBitBuilder &	directions )

Build packed node directions and stably partition ranks.

Parameters

input	Ranks in the node's original subsequence order.
middle	First rank belonging to the right child.
output	Destination split into left then right subsequences.
expected_left	Number of ranks expected in the left child.
write_left	Whether the left subsequence is needed by a child node.
write_right	Whether the right subsequence is needed by a child node.
directions	Packed destination for one direction bit per input rank.