BitString< CHAR_T, CHAR_SIZE_BITS > Class Template Reference

A class to store strings compactly into integers, packing multiple characters into a single word. More...

Classes
class	Iterator
	An iterator class for traversing the characters within a BitString. More...
struct	ResultLCP
	Structure to hold the result of a comparison, including the ordering and the length of the common prefix. More...

Public Member Functions
	BitString (const CHAR_T *data, size_t size)
	Constructs a BitString object from a raw character array.
template<typename Container >
	BitString (const Container &data)
	Constructs a BitString object from a container of characters.
	BitString (const std::string &data)
	Constructs a BitString object from a std::string.
	BitString ()=default
	Default constructor.
void	push_back (CHAR_T c) noexcept
	Appends a single character to the end of the BitString.
CHAR_T	operator[] (size_t index) const
	Accesses the character at a specific index.
size_t	size () const noexcept
	Returns the number of characters stored in the BitString.
size_t	word_count () const noexcept
	Returns the number of uintmax_t words used for storage.
void	clear () noexcept
	Clears the contents of the BitString, making it empty.
ResultLCP	seq_k_compare (const BitString &other, size_t lcp, size_t max_compare) const noexcept
	Performs sequential comparison with another BitString, starting from a given LCP offset, up to a maximum length.
ResultLCP	seq_k_compare (const BitString &other, size_t lcp) const noexcept
	Performs sequential comparison with another BitString, starting from a given LCP offset.
ResultLCP	par_k_compare (const BitString &other, size_t lcp, size_t max_compare, uintmax_t *d_a, uintmax_t *d_largeblock, size_t &max_copied) const noexcept
	Performs parallel comparison (potentially using CUDA) with another BitString, starting from a given LCP offset, up to a maximum length.
ResultLCP	par_k_compare (const BitString &other, size_t lcp, uintmax_t *d_a, uintmax_t *d_largeblock, size_t &max_copied) const noexcept
	Performs parallel comparison (potentially using CUDA) with another BitString, starting from a given LCP offset.
const uintmax_t *	data () const noexcept
	Provides direct access to the underlying packed data array.
void	print_bytes (std::ostream &os) const
	Prints the raw byte representation of the BitString to an output stream.
void	to_file (const std::string &filename) const
	Writes the BitString contents to a file in binary format.
void	to_file (std::ofstream &file) const
	Writes the BitString contents to an already open output file stream.
std::string	to_string () const noexcept
	Converts the BitString back to a standard std::string.
Iterator	begin () const noexcept
	Returns an iterator pointing to the beginning of the BitString.
Iterator	end () const noexcept
	Returns an iterator pointing past the end of the BitString.

Static Public Member Functions
static BitString	from_file (const std::string &filename)
	Reads a BitString from a file in binary format.
static BitString	from_file (std::ifstream &file)
	Reads a BitString from an already open input file stream.

Static Public Attributes
static constexpr unsigned	WORD_SIZE_BITS = sizeof(uintmax_t) * 8
	Size of the underlying storage word (uintmax_t) in bits.
static constexpr unsigned	ALPHA = WORD_SIZE_BITS / CHAR_SIZE_BITS
	Number of characters that can be packed into a single storage word.
static constexpr size_t	MIN_PAR_COMPARE_CHAR_SIZE = MIN_PAR_COMPARE_WORD_SIZE * ALPHA
	Minimum number of characters required to trigger parallel comparison. Derived from MIN_PAR_COMPARE_WORD_SIZE.

Static Private Member Functions
static constexpr std::array< unsigned, ALPHA >	GET_SHIFTS ()
	Generates the bit shift amounts needed for character extraction/insertion at compile time.
static constexpr std::array< uintmax_t, ALPHA >	GET_MASKS ()
	Generates the bit masks needed for character extraction at compile time.
static constexpr CHAR_T	GET_CHAR (uintmax_t word, unsigned bit_index)
	Extracts a single character from a given word at a specific bit index (sub-word position).

Private Attributes
std::vector< uintmax_t >	m_data
	Internal storage vector holding the packed character data.
size_t	m_size = 0
	The number of characters stored in the BitString.

Static Private Attributes
static constexpr std::array< unsigned, ALPHA >	m_shifts = GET_SHIFTS()
	Compile-time generated array of bit shift amounts.
static constexpr std::array< uintmax_t, ALPHA >	m_masks = GET_MASKS()
	Compile-time generated array of bit masks.

Friends
template<typename CT , unsigned CSB>
std::ostream &	operator<< (std::ostream &os, const BitString< CT, CSB > &bs)

Detailed Description

template<typename CHAR_T, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>
class BitString< CHAR_T, CHAR_SIZE_BITS >

A class to store strings compactly into integers, packing multiple characters into a single word.

This class allows for space-efficient storage of character strings by packing them into an array of uintmax_t integers. It focuses on optimizing storage and comparison operations. Comparisons leverage bitwise operations and can identify the longest common prefix (LCP) efficiently. Parallel comparison using CUDA is supported for large strings.

Template Parameters

CHAR_T	The character type to be stored (e.g., char, uint8_t, wchar_t).
CHAR_SIZE_BITS	The number of bits representing relevant data within CHAR_T. Defaults to the full size of CHAR_T in bits. This allows handling types where only a subset of bits are meaningful (e.g., 7-bit ASCII in an 8-bit char, or 2-bit nucleotides for DNA strings).

Definition at line 57 of file BitString.cuh.

Constructor & Destructor Documentation

BitString() [1/4]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

BitString< CHAR_T, CHAR_SIZE_BITS >::BitString ( const CHAR_T *  data, size_t  size  )

explicit

Constructs a BitString object from a raw character array.

Packs the input characters into the internal uintmax_t vector.

Parameters

data	Pointer to the beginning of the character array. Must not be null if size > 0.
size	The number of characters in the array.

Definition at line 491 of file BitString.cuh.

    : m_size(data_size)
{
    const size_t word_count = (size() + ALPHA - 1) / ALPHA;
    m_data.resize(word_count, 0);
 
    for (size_t i = 0; i < size(); ++i)
    {
        const size_t word_index = i / ALPHA;
        const size_t bit_index = i % ALPHA;
        const uintmax_t mask = static_cast<uintmax_t>(data[i]) << m_shifts[bit_index];
        m_data[word_index] |= mask;
    }
}

BitString() [2/4]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

template<typename Container >

BitString< CHAR_T, CHAR_SIZE_BITS >::BitString ( const Container &  data )

explicit

Constructs a BitString object from a container of characters.

Packs characters from the container into the internal vector.

The container must support size() and random access via operator[]. Examples include std::vector<CHAR_T>, std::basic_string<CHAR_T>, std::array<CHAR_T, N>.

Template Parameters

Container

Type of the container holding the character data.

Parameters

data	The container instance.

Definition at line 508 of file BitString.cuh.

    : m_size(data.size()) // Get size from the container
{
    const size_t word_count = (size() + ALPHA - 1) / ALPHA;
    m_data.resize(word_count, 0);
 
    for (size_t i = 0; i < size(); ++i)
    {
        const size_t word_index = i / ALPHA;
        const size_t bit_index = i % ALPHA;
        const uintmax_t mask = static_cast<uintmax_t>(data[i]) << m_shifts[bit_index];
        m_data[word_index] |= mask;
    }
}

BitString() [3/4]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

BitString< CHAR_T, CHAR_SIZE_BITS >::BitString ( const std::string &  data )

inlineexplicit

Constructs a BitString object from a std::string.

Note

This constructor assumes CHAR_T is compatible with char.

Parameters

data	The std::string used to initialize the BitString object.

Definition at line 93 of file BitString.cuh.

        : BitString(reinterpret_cast<const CHAR_T*>(data.c_str()), data.size()) // Reinterpret cast assumes CHAR_T layout matches char
    {
        // Body intentionally empty
    }

BitString() [4/4]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

BitString< CHAR_T, CHAR_SIZE_BITS >::BitString ( )

default

Default constructor.

Note

Creates an empty BitString. Primarily intended for use by the from_file static method.

Member Function Documentation

begin()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

Iterator BitString< CHAR_T, CHAR_SIZE_BITS >::begin ( ) const

inlinenoexcept

Returns an iterator pointing to the beginning of the BitString.

Returns

Iterator An iterator to the first character.

Definition at line 437 of file BitString.cuh.

    {
        return Iterator(*this, 0);
    }

clear()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

void BitString< CHAR_T, CHAR_SIZE_BITS >::clear ( )

inlinenoexcept

Clears the contents of the BitString, making it empty.

Note

Resets size to 0 and clears the internal data vector.

Definition at line 141 of file BitString.cuh.

    {
        m_data.clear();
        m_size = 0;
    }

data()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

const uintmax_t * BitString< CHAR_T, CHAR_SIZE_BITS >::data ( ) const

inlinenoexcept

Provides direct access to the underlying packed data array.

Returns

const uintmax_t* A pointer to the beginning of the internal uintmax_t data array. Returns nullptr if the BitString is empty.

Warning

Modifying the data through this pointer may invalidate the BitString's state. Use with caution.

Definition at line 246 of file BitString.cuh.

{ return m_data.data(); }

end()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

Iterator BitString< CHAR_T, CHAR_SIZE_BITS >::end ( ) const

inlinenoexcept

Returns an iterator pointing past the end of the BitString.

Returns

Iterator An iterator representing the end sentinel.

Definition at line 446 of file BitString.cuh.

    {
        return Iterator(*this, size());
    }

from_file() [1/2]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

BitString< CHAR_T, CHAR_SIZE_BITS > BitString< CHAR_T, CHAR_SIZE_BITS >::from_file ( const std::string &  filename )

static

Reads a BitString from a file in binary format.

Opens the file, calls the stream version of from_file, and closes the file.

Deserializes the size and packed data from the specified file.

Parameters

filename

The path to the input file.

Returns

BitString The BitString object reconstructed from the file data.

Exceptions

std::runtime_error

If the file cannot be opened for reading.

Definition at line 763 of file BitString.cuh.

{
    std::ifstream file(filename, std::ios::binary);
    if (!file)
    {
        throw std::runtime_error("Failed to open file for reading: " + filename);
    }
    return from_file(file);
    // file automatically closed by destructor
}

from_file() [2/2]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

BitString< CHAR_T, CHAR_SIZE_BITS > BitString< CHAR_T, CHAR_SIZE_BITS >::from_file ( std::ifstream &  file )

static

Reads a BitString from an already open input file stream.

Reads the size, calculates words needed, resizes, then reads raw data. Does not perform error checking on reads.

Deserializes the size and packed data from the stream.

Parameters

file	The std::ifstream object, opened in binary mode.

Returns

BitString The BitString object reconstructed from the stream data.

Definition at line 739 of file BitString.cuh.

{
    BitString<CHAR_T, CHAR_SIZE_BITS> bs;
 
    file.read(reinterpret_cast<char*>(&bs.m_size), sizeof(size_t));
    if (!file) { // Check read success
        throw std::runtime_error("Failed to read size from file stream.");
    }
 
    const size_t word_count = (bs.size() + ALPHA - 1) / ALPHA;
    bs.m_data.resize(word_count, 0); // Resize before reading into it
 
    if (word_count > 0) { // Only read if there's data expected
        file.read(reinterpret_cast<char*>(bs.m_data.data()), word_count * sizeof(uintmax_t));
        if (!file) { // Check read success
            throw std::runtime_error("Failed to read data from file stream.");
        }
    }
 
 
    return bs;
}

GET_CHAR()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

constexpr CHAR_T BitString< CHAR_T, CHAR_SIZE_BITS >::GET_CHAR ( uintmax_t  word, unsigned  bit_index  )

staticconstexprprivate

Extracts a single character from a given word at a specific bit index (sub-word position).

Applies the appropriate mask and shift to isolate and retrieve the character.

Template Parameters

CHAR_T	Character type.
CHAR_SIZE_BITS	Bits per character.

Parameters

word	The uintmax_t word containing the packed characters.
bit_index	The index within the word (0 to ALPHA-1) corresponding to the desired character.

Returns

CHAR_T The extracted character.

Definition at line 483 of file BitString.cuh.

{
    const uintmax_t masked_word = word & m_masks[bit_index];
    const uintmax_t shifted_word = masked_word >> m_shifts[bit_index];
    return static_cast<CHAR_T>(shifted_word);
}

GET_MASKS()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

constexpr std::array< uintmax_t, BitString< CHAR_T, CHAR_SIZE_BITS >::ALPHA > BitString< CHAR_T, CHAR_SIZE_BITS >::GET_MASKS ( )

staticconstexprprivate

Generates the bit masks needed for character extraction at compile time.

Creates a mask for each character position within a word.

Template Parameters

CHAR_T	Character type.
CHAR_SIZE_BITS	Bits per character.

Returns

std::array<uintmax_t, ALPHA> An array where each element i is a mask that isolates the bits corresponding to the character at sub-word index i.

Definition at line 466 of file BitString.cuh.

{
    uintmax_t mask = 0;
    for (unsigned i = 0; i < CHAR_SIZE_BITS; ++i)
    {
        mask |= static_cast<uintmax_t>(1) << i;
    }
 
    std::array<uintmax_t, ALPHA> masks;
    for (unsigned i = 0; i < ALPHA; ++i)
    {
        masks[i] = mask << m_shifts[i];
    }
    return masks;
}

GET_SHIFTS()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

constexpr std::array< unsigned, BitString< CHAR_T, CHAR_SIZE_BITS >::ALPHA > BitString< CHAR_T, CHAR_SIZE_BITS >::GET_SHIFTS ( )

staticconstexprprivate

Generates the bit shift amounts needed for character extraction/insertion at compile time.

Calculates the left shift amount needed for each character position within a word.

Template Parameters

CHAR_T	Character type.
CHAR_SIZE_BITS	Bits per character.

Returns

std::array<unsigned, ALPHA> An array where each element i contains the left-shift amount required to position the character at sub-word index i correctly within a uintmax_t.

Definition at line 455 of file BitString.cuh.

{
    std::array<unsigned, ALPHA> shifts;
    for (unsigned i = 0; i < ALPHA; ++i)
    {
        shifts[ALPHA - i - 1] = i * CHAR_SIZE_BITS;
    }
    return shifts;
}

operator[]()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

CHAR_T BitString< CHAR_T, CHAR_SIZE_BITS >::operator[]

(

size_t

index

)

const

Accesses the character at a specific index.

Calculates the word and sub-index, then uses GET_CHAR for extraction. Behavior undefined if index is out of bounds.

Behavior is undefined for out-of-bounds access.

Parameters

index

The zero-based index of the character to access. Must be less than size().

Returns

CHAR_T The character at the specified index.

Note

This operation involves bitwise extraction and may be slower than direct array access.

Definition at line 540 of file BitString.cuh.

{
    return GET_CHAR(m_data[index / ALPHA], index % ALPHA);
}

par_k_compare() [1/2]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

auto BitString< CHAR_T, CHAR_SIZE_BITS >::par_k_compare ( const BitString< CHAR_T, CHAR_SIZE_BITS > &  other, size_t  lcp, size_t  max_compare, uintmax_t *  d_a, uintmax_t *  d_largeblock, size_t &  max_copied  ) const

noexcept

Performs parallel comparison (potentially using CUDA) with another BitString, starting from a given LCP offset, up to a maximum length.

Checks size, copies data to GPU if necessary, calls parallel mismatch kernel, then refines LCP. Falls back to sequential if too small.

Compares this BitString with other, assuming the first lcp characters are equal. If the number of words to compare exceeds MIN_PAR_COMPARE_WORD_SIZE, this function attempts to use a parallel CUDA kernel (par_find_mismatch) for faster mismatch detection. Otherwise, it falls back to seq_k_compare. The comparison stops strictly at lcp + max_compare characters or the end of the shorter string, whichever comes first.

Parameters

	other	The BitString to compare against.
	lcp	The starting offset (longest common prefix length) for the comparison, in characters.
	max_compare	The maximum number of additional characters to compare beyond the initial lcp. The comparison will not proceed beyond lcp + max_compare total characters from the start.
	d_a	Pointer to device (GPU) memory allocated for this BitString's data. Data might be copied here if needed.
	d_largeblock	Pointer to auxiliary device (GPU) memory required by the parallel kernel.
[in,out]	max_copied	Tracks the amount of data already copied to d_a to avoid redundant transfers. Updated by this function.

Returns

ResultLCP A struct containing the comparison result (std::strong_ordering) of the substrings up to the comparison limit and the final calculated LCP length (which will not exceed the limit). Returns std::strong_ordering::equal if the substrings match up to the limit, even if the full strings might differ later.

See also

seq_k_compare

MIN_PAR_COMPARE_WORD_SIZE

Note

Requires properly allocated CUDA device memory (d_a, d_largeblock) and a valid CUDA context.

The other BitString's data is assumed to be accessible directly (e.g., host pinned memory or already on device if applicable to par_find_mismatch).

Uses std::bit_ceil and std::countl_zero.

Definition at line 587 of file BitString.cuh.

{
    // Fallback for small comparisons
    if (max_compare <= MIN_PAR_COMPARE_CHAR_SIZE)
    {
        return seq_k_compare(other, lcp, max_compare);
    }
 
    const size_t min_size = std::min(size(), other.size());
    const size_t min_word_count = std::min(word_count(), other.word_count());
    size_t word_index = lcp / ALPHA;
 
    // Calculate how many full words remain to potentially compare
    const size_t num_remaining_words = (min_word_count > word_index) ? (min_word_count - word_index) : 0;
 
    // Calculate max words to compare based on max_compare characters
    // Need to compare up to the word containing character (lcp + max_compare - 1)
    const size_t end_char_index = lcp + max_compare;
    const size_t end_word_index = (end_char_index + ALPHA - 1) / ALPHA; // Word index containing the last char to check
    const size_t max_compare_words = (end_word_index > word_index) ? (end_word_index - word_index) : 0;
 
 
    const size_t actual_max_compare_words = std::min(max_compare_words, num_remaining_words);
 
    // Fallback if the actual number of words to compare is too small
    if (actual_max_compare_words <= MIN_PAR_COMPARE_WORD_SIZE)
    {
        return seq_k_compare(other, lcp, max_compare);
    }
 
    // Ensure data is on the device
    if (max_copied < word_index + actual_max_compare_words)
    {
        size_t end_copy_index = word_index + actual_max_compare_words;
        
        // get next power of 2 greater than or equal to end_copy_index
        size_t end_copy = std::min(std::bit_ceil(end_copy_index), word_count());
        if (end_copy > max_copied) {
            copy_to_device(d_a + max_copied, data() + max_copied, end_copy - max_copied);
            max_copied = end_copy;
        }
    }
 
    lcp -= lcp % ALPHA; // Reset LCP to the start of the current word boundary for parallel comparison
 
    // Perform parallel mismatch search
    auto msw = par_find_mismatch(d_a + word_index, other.data() + word_index, d_largeblock, actual_max_compare_words);
 
    // Calculate LCP based on mismatch word index (msw)
    lcp += msw * ALPHA;
 
    // If no mismatch found within the compared words
    if (msw == actual_max_compare_words)
    {
        // Check if the comparison reached the end of either string
        if (lcp >= min_size)
        {
            return { size() <=> other.size(), min_size };
        }
 
        return { std::strong_ordering::equal, lcp };
    }
 
    // Mismatch found by parallel kernel. Refine LCP within the mismatch word.
    word_index = lcp / ALPHA; // Update word_index to the mismatch word
 
    // Find exact mismatch character within the word
    const uintmax_t XOR = m_data[word_index] ^ other.m_data[word_index];
    const size_t l_zero = std::countl_zero(XOR);
 
    lcp += l_zero / CHAR_SIZE_BITS;
 
    const size_t bit_index = lcp % ALPHA;
 
    // Mismatch is within the limit
    const CHAR_T lhs = GET_CHAR(m_data[word_index], bit_index);
    const CHAR_T rhs = GET_CHAR(other.m_data[word_index], bit_index);
 
    return { lhs <=> rhs, lcp };
}

par_k_compare() [2/2]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

ResultLCP BitString< CHAR_T, CHAR_SIZE_BITS >::par_k_compare ( const BitString< CHAR_T, CHAR_SIZE_BITS > &  other, size_t  lcp, uintmax_t *  d_a, uintmax_t *  d_largeblock, size_t &  max_copied  ) const

inlinenoexcept

Performs parallel comparison (potentially using CUDA) with another BitString, starting from a given LCP offset.

Compares this BitString with other, assuming the first lcp characters are equal. Compares up to the end of the shorter string using parallel methods if applicable.

Parameters

	other	The BitString to compare against.
	lcp	The starting offset (longest common prefix length) for the comparison, in characters.
	d_a	Pointer to device (GPU) memory for this BitString's data.
	d_largeblock	Pointer to auxiliary device (GPU) memory.
[in,out]	max_copied	Tracks the amount of data copied to d_a.

Returns

ResultLCP A struct containing the comparison result and the final LCP length.

Note

Equivalent to par_k_compare(other, lcp, size(), d_a, d_largeblock, max_copied).

See also

par_k_compare(const BitString&, size_t, size_t, uintmax_t*, uintmax_t*, size_t&)

Definition at line 236 of file BitString.cuh.

    {
        return par_k_compare(other, lcp, size(), d_a, d_largeblock, max_copied);
    }

print_bytes()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

void BitString< CHAR_T, CHAR_SIZE_BITS >::print_bytes

(

std::ostream &

os

)

const

Prints the raw byte representation of the BitString to an output stream.

Iterates through words and extracts bytes based on WORD_SIZE_BITS. Handles the last partial word correctly.

Writes the packed uintmax_t data to the stream byte by byte, respecting the actual number of characters (size()). Handles partial final words correctly.

Parameters

os	The output stream (e.g., std::cout, std::ofstream) to write to.

Definition at line 669 of file BitString.cuh.

{
    static constexpr unsigned shift = WORD_SIZE_BITS - 8;
 
    for (size_t i = 0, a = 0; i + ALPHA <= size(); i += ALPHA, ++a)
    {
        uintmax_t word = m_data[a];
        
        for (unsigned c = 0; c < WORD_SIZE_BITS / 8; c++, word <<= 8)
        {
            os << static_cast<uint8_t>(word >> shift);
        }
    }
 
    // Handle last partial word if it exists
    if (size() % ALPHA != 0 && !m_data.empty())
    {
        uintmax_t word = m_data.back();
        unsigned remaining_chars = size() % ALPHA;
        unsigned remaining_bits = remaining_chars * CHAR_SIZE_BITS;
        unsigned bytes_to_print = (remaining_bits + 7) / 8; // Round up bytes
 
        // Process the required bytes from the most significant side
        for (unsigned byte_idx = 0; byte_idx < bytes_to_print; ++byte_idx)
        {
            os << static_cast<uint8_t>(word >> (shift - byte_idx * 8));
        }
    }
}

push_back()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

void BitString< CHAR_T, CHAR_SIZE_BITS >::push_back ( CHAR_T  c )

noexcept

Appends a single character to the end of the BitString.

Adds the character to the last word, potentially allocating a new word if needed.

Parameters

c	The character to append.

Note

This operation may reallocate the underlying storage if capacity is exceeded.

Definition at line 524 of file BitString.cuh.

{
    const size_t word_index = size() / ALPHA;
    const size_t bit_index = size() % ALPHA;
    const uintmax_t mask = static_cast<uintmax_t>(c) << m_shifts[bit_index];
 
    if (word_index >= m_data.size())
    {
        m_data.push_back(0);
    }
 
    m_data[word_index] |= mask;
    ++m_size;
}

seq_k_compare() [1/2]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

ResultLCP BitString< CHAR_T, CHAR_SIZE_BITS >::seq_k_compare ( const BitString< CHAR_T, CHAR_SIZE_BITS > &  other, size_t  lcp  ) const

inlinenoexcept

Performs sequential comparison with another BitString, starting from a given LCP offset.

Compares this BitString with other, assuming the first lcp characters are equal. Compares up to the end of the shorter string.

Parameters

other	The BitString to compare against.
lcp	The starting offset (longest common prefix length) for the comparison, in characters.

Returns

ResultLCP A struct containing the comparison result and the final LCP length.

Note

This comparison is performed entirely on the CPU. Equivalent to seq_k_compare(other, lcp, size()).

Definition at line 187 of file BitString.cuh.

    {
        return seq_k_compare(other, lcp, size());
    }

seq_k_compare() [2/2]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

auto BitString< CHAR_T, CHAR_SIZE_BITS >::seq_k_compare ( const BitString< CHAR_T, CHAR_SIZE_BITS > &  other, size_t  lcp, size_t  max_compare  ) const

noexcept

Performs sequential comparison with another BitString, starting from a given LCP offset, up to a maximum length.

Iterates word by word, finds the first mismatch using XOR and countl_zero.

Compares this BitString with other, assuming the first lcp characters are already known to be equal. The comparison proceeds character by character (packed within words) sequentially, but stops strictly at lcp + max_compare characters or the end of the shorter string, whichever comes first.

Parameters

other	The BitString to compare against.
lcp	The starting offset (longest common prefix length) for the comparison, in characters.
max_compare	The maximum number of additional characters to compare beyond the initial lcp. The comparison will not proceed beyond lcp + max_compare total characters from the start.

Returns

ResultLCP A struct containing the comparison result (std::strong_ordering) of the substrings up to the comparison limit and the final calculated LCP length (which will not exceed the limit). Returns std::strong_ordering::equal if the substrings match up to the limit, even if the full strings might differ later.

Note

This comparison is performed entirely on the CPU. Uses std::countl_zero.

Definition at line 546 of file BitString.cuh.

{
    const size_t min_size = std::min(size(), other.size());
    const size_t max_compare_until = lcp + max_compare;
    size_t word_index = lcp / ALPHA;
 
    lcp -= lcp % ALPHA; // Reset to word boundary
 
    while (lcp < min_size && lcp < max_compare_until)
    {
        const uintmax_t XOR = m_data[word_index] ^ other.m_data[word_index];
 
        if (XOR == 0)
        {
            lcp += ALPHA;
            ++word_index;
            continue;
        }
 
        const size_t l_zero = std::countl_zero(XOR);
 
        lcp += l_zero / CHAR_SIZE_BITS;
 
        const size_t bit_index = lcp % ALPHA;
 
        // Mismatch found within limit
        const CHAR_T lhs = GET_CHAR(m_data[word_index], bit_index);
        const CHAR_T rhs = GET_CHAR(other.m_data[word_index], bit_index);
 
        return { lhs <=> rhs, lcp };
    }
 
    if (lcp >= min_size)
    {
        return { size() <=> other.size(), min_size };
    }
 
    return { std::strong_ordering::equal, lcp };
}

size()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

size_t BitString< CHAR_T, CHAR_SIZE_BITS >::size ( ) const

inlinenoexcept

Returns the number of characters stored in the BitString.

Returns

size_t The total number of characters.

Definition at line 129 of file BitString.cuh.

{ return m_size; }

to_file() [1/2]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

void BitString< CHAR_T, CHAR_SIZE_BITS >::to_file

(

const std::string &

filename

)

const

Writes the BitString contents to a file in binary format.

Opens the file, calls the stream version of to_file, and closes the file.

Serializes the size and the packed data array to the specified file.

Parameters

filename

The path to the output file.

Exceptions

std::runtime_error

If the file cannot be opened for writing.

Definition at line 727 of file BitString.cuh.

{
    std::ofstream file(filename, std::ios::binary);
    if (!file)
    {
        throw std::runtime_error("Failed to open file for writing: " + filename);
    }
    to_file(file);
    // file automatically closed by destructor
}

to_file() [2/2]

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

void BitString< CHAR_T, CHAR_SIZE_BITS >::to_file

(

std::ofstream &

file

)

const

Writes the BitString contents to an already open output file stream.

Writes the size, then the raw uintmax_t data. Does not perform error checking on writes.

Serializes the size and the packed data array to the stream.

Parameters

file	The std::ofstream object, opened in binary mode.

Definition at line 720 of file BitString.cuh.

{
    file.write(reinterpret_cast<const char*>(&m_size), sizeof(size_t));
    file.write(reinterpret_cast<const char*>(m_data.data()), m_data.size() * sizeof(uintmax_t));
}

to_string()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

std::string BitString< CHAR_T, CHAR_SIZE_BITS >::to_string ( ) const

noexcept

Converts the BitString back to a standard std::string.

Iterates through characters using iterators and appends them to a string. Assumes CHAR_T is convertible to char.

Returns

std::string A string containing the characters stored in the BitString.

Note

This assumes CHAR_T is convertible to char.

Definition at line 775 of file BitString.cuh.

{
    std::string str;
    str.reserve(size());
 
    for (CHAR_T c : *this)
    {
        // Assumes CHAR_T is convertible to char, potential truncation if wider.
        str.push_back(static_cast<char>(c));
    }
 
    return str;
}

word_count()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

size_t BitString< CHAR_T, CHAR_SIZE_BITS >::word_count ( ) const

inlinenoexcept

Returns the number of uintmax_t words used for storage.

Returns

size_t The number of words in the internal data vector.

Definition at line 135 of file BitString.cuh.

{ return m_data.size(); }

Friends And Related Symbol Documentation

operator<<

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

template<typename CT , unsigned CSB>

std::ostream & operator<< ( std::ostream &  os, const BitString< CT, CSB > &  bs  )

friend

Member Data Documentation

ALPHA

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

constexpr unsigned BitString< CHAR_T, CHAR_SIZE_BITS >::ALPHA = WORD_SIZE_BITS / CHAR_SIZE_BITS

staticconstexpr

Number of characters that can be packed into a single storage word.

Definition at line 63 of file BitString.cuh.

m_data

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

std::vector<uintmax_t> BitString< CHAR_T, CHAR_SIZE_BITS >::m_data

private

Internal storage vector holding the packed character data.

Definition at line 250 of file BitString.cuh.

m_masks

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

constexpr std::array<uintmax_t, ALPHA> BitString< CHAR_T, CHAR_SIZE_BITS >::m_masks = GET_MASKS()

staticconstexprprivate

Compile-time generated array of bit masks.

Definition at line 276 of file BitString.cuh.

m_shifts

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

constexpr std::array<unsigned, ALPHA> BitString< CHAR_T, CHAR_SIZE_BITS >::m_shifts = GET_SHIFTS()

staticconstexprprivate

Compile-time generated array of bit shift amounts.

Definition at line 264 of file BitString.cuh.

m_size

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

size_t BitString< CHAR_T, CHAR_SIZE_BITS >::m_size = 0

private

The number of characters stored in the BitString.

Definition at line 252 of file BitString.cuh.

MIN_PAR_COMPARE_CHAR_SIZE

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

constexpr size_t BitString< CHAR_T, CHAR_SIZE_BITS >::MIN_PAR_COMPARE_CHAR_SIZE = MIN_PAR_COMPARE_WORD_SIZE * ALPHA

staticconstexpr

Minimum number of characters required to trigger parallel comparison. Derived from MIN_PAR_COMPARE_WORD_SIZE.

Definition at line 65 of file BitString.cuh.

WORD_SIZE_BITS

template<typename CHAR_T , unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

constexpr unsigned BitString< CHAR_T, CHAR_SIZE_BITS >::WORD_SIZE_BITS = sizeof(uintmax_t) * 8

staticconstexpr

Size of the underlying storage word (uintmax_t) in bits.

Definition at line 61 of file BitString.cuh.

---

The documentation for this class was generated from the following file:

• src/BitString.cuh