signet::forge::z_order Namespace Reference

Z-order curve (Morton code) utilities for spatial sort keys. More...

Classes
struct	ZOrderColumn
	Descriptor for a single column of raw typed data used by ZOrderSorter. More...
struct	ZOrderSorter
	Computes a permutation vector that reorders rows by Z-order (Morton) key. More...

Functions
uint32_t	normalize_int32 (int32_t v)
	Normalize a signed 32-bit integer to an unsigned 32-bit integer that preserves the original sort order (flip the sign bit).
uint64_t	normalize_int64 (int64_t v)
	Normalize a signed 64-bit integer to uint64_t (flip sign bit).
uint32_t	normalize_float (float v)
	Normalize a 32-bit float to uint32_t preserving total order.
uint64_t	normalize_double (double v)
	Normalize a 64-bit double to uint64_t preserving total order.
uint32_t	normalize_string (std::string_view v)
	Normalize a string to uint32_t by taking the first 4 bytes in big-endian order.
uint32_t	truncate_to_32 (uint64_t v)
	Truncate a uint64_t to uint32_t by extracting the upper 32 bits.
uint64_t	morton_2d (uint32_t x, uint32_t y)
	Interleave bits of two uint32_t values into a single uint64_t Morton code (2D).
void	deinterleave_2d (uint64_t code, uint32_t &x, uint32_t &y)
	Deinterleave a 2D Morton code back into its two uint32_t components.
std::vector< uint8_t >	morton_nd (const std::vector< uint32_t > &normalized, size_t bits_per_col=32)
	Generalized N-column Morton code via round-robin bit interleaving (MSB-first).

Detailed Description

Z-order curve (Morton code) utilities for spatial sort keys.

Function Documentation

deinterleave_2d()

void signet::forge::z_order::deinterleave_2d ( uint64_t  code, uint32_t &  x, uint32_t &  y  )

inline

Deinterleave a 2D Morton code back into its two uint32_t components.

Inverse of morton_2d(): extracts even-positioned bits into x and odd-positioned bits into y.

Parameters

	code	64-bit Morton code produced by morton_2d().
[out]	x	First column value (even bit positions).
[out]	y	Second column value (odd bit positions).

Definition at line 155 of file z_order.hpp.

morton_2d()

uint64_t signet::forge::z_order::morton_2d ( uint32_t  x, uint32_t  y  )

inline

Interleave bits of two uint32_t values into a single uint64_t Morton code (2D).

This is the fast path for 2-column Z-ordering. Uses the parallel bit-deposit "magic bits" technique to spread each 32-bit input across alternating bit positions in the 64-bit result.

Parameters

x	First column's normalized uint32_t value (occupies even bit positions).
y	Second column's normalized uint32_t value (occupies odd bit positions).

Returns

64-bit Morton code with bits interleaved as: y31 x31 y30 x30 ... y0 x0.

Definition at line 134 of file z_order.hpp.

morton_nd()

std::vector< uint8_t > signet::forge::z_order::morton_nd ( const std::vector< uint32_t > &  normalized, size_t  bits_per_col = 32  )

inline

Generalized N-column Morton code via round-robin bit interleaving (MSB-first).

Supports 2-8 columns, each providing a uint32_t normalized value. Bits are interleaved in round-robin order starting from the most significant bit of each column, producing a byte-array sort key suitable for lexicographic comparison.

The output length is ceil(N * bits_per_col / 8) bytes.

Parameters

normalized	Vector of N normalized uint32_t values (one per column).
bits_per_col	Number of bits to interleave per column (default 32).

Returns

Byte array sort key with MSB first. Empty if normalized is empty.

Note

For exactly 2 columns, prefer morton_2d() which returns a uint64_t and avoids heap allocation.

Definition at line 183 of file z_order.hpp.

normalize_double()

uint64_t signet::forge::z_order::normalize_double ( double  v )

inline

Normalize a 64-bit double to uint64_t preserving total order.

Same IEEE 754 sign-magnitude trick as normalize_float(), but for doubles.

Parameters

v	Double input value.

Returns

Order-preserving unsigned 64-bit representation.

Definition at line 83 of file z_order.hpp.

normalize_float()

uint32_t signet::forge::z_order::normalize_float ( float  v )

inline

Normalize a 32-bit float to uint32_t preserving total order.

Uses the IEEE 754 sign-magnitude trick: negative floats have all bits flipped; non-negative floats have only the sign bit flipped. The result sorts identically to the original float values when compared as unsigned.

Parameters

v	Float input value.

Returns

Order-preserving unsigned 32-bit representation.

Definition at line 70 of file z_order.hpp.

normalize_int32()

uint32_t signet::forge::z_order::normalize_int32 ( int32_t  v )

inline

Normalize a signed 32-bit integer to an unsigned 32-bit integer that preserves the original sort order (flip the sign bit).

Parameters

v	Signed input value.

Returns

Order-preserving unsigned representation.

Definition at line 51 of file z_order.hpp.

normalize_int64()

uint64_t signet::forge::z_order::normalize_int64 ( int64_t  v )

inline

Normalize a signed 64-bit integer to uint64_t (flip sign bit).

Parameters

v	Signed input value.

Returns

Order-preserving unsigned representation.

Definition at line 58 of file z_order.hpp.

normalize_string()

uint32_t signet::forge::z_order::normalize_string ( std::string_view  v )

inline

Normalize a string to uint32_t by taking the first 4 bytes in big-endian order.

Strings shorter than 4 bytes are zero-padded on the right, so "AB" becomes 0x41420000. This provides a coarse sort-preserving key suitable for Morton interleaving (lexicographic order is preserved for the first 4 chars).

Note

L16: Only uses first 4 bytes – strings with shared prefixes will have identical Morton keys. Consider using xxhash32() for better distribution if lexicographic order is not required.

Parameters

v	String input (only the first 4 bytes are used).

Returns

32-bit sort key derived from the string prefix.

Definition at line 102 of file z_order.hpp.

truncate_to_32()

uint32_t signet::forge::z_order::truncate_to_32 ( uint64_t  v )

inline

Truncate a uint64_t to uint32_t by extracting the upper 32 bits.

Used to reduce 64-bit normalized values (int64, double) to 32-bit Morton inputs. The upper bits carry the most significant information for sorting.

Parameters

v	64-bit normalized value.

Returns

Upper 32 bits of v.

Definition at line 117 of file z_order.hpp.