Typed sort keys and the chunked, stoppable merge sort over them. More...

#include <algorithm>
#include <array>
#include <cctype>
#include <charconv>
#include <chrono>
#include <cmath>
#include <compare>
#include <core/async/StopToken.hpp>
#include <cstddef>
#include <cstdint>
#include <ios>
#include <locale>
#include <memory>
#include <morph/table/data_source.hpp>
#include <optional>
#include <span>
#include <sstream>
#include <string>
#include <string_view>
#include <system_error>
#include <utility>
#include <variant>
#include <vector>
#include <version>

Classes
struct	morph::table::SortKey
	One key of a sort chain. More...
struct	morph::table::KeyColumn
	One column's keys, built once and shared, immutable, between jobs. More...
class	morph::table::RowOrder
	A sort chain resolved to key columns: the comparator of a sort. More...
struct	morph::table::RowOrder::Key
	One resolved key. More...
class	morph::table::ChunkedMergeSort
	A bottom-up merge sort over row indices that can stop and resume. More...

Typedefs
using	morph::table::SortChain = std::vector<SortKey>
	A multi-key sort, most significant key first. Empty means source order.
using	morph::table::Deadline = std::chrono::steady_clock::time_point
	A deadline for one step of work; kNoDeadline runs to completion.

Enumerations
enum class	morph::table::SortDirection : std::uint8_t { Ascending , Descending }
	A sort key's direction. More...
enum class	morph::table::CellState : std::uint8_t { Valid , Empty , Invalid }
	Whether a cell has a key. More...

Functions
bool	morph::table::detail::shouldYield (Deadline deadline, ::core::async::StopToken const &stop)
	Whether a step should return now.
TextCollator const &	morph::table::detail::collatorOf (Services const &services)
	The collator to use: the service's, or the default.
DateParser const &	morph::table::detail::datesOf (Services const &services)
	The date parser to use: the service's, or the default.
std::optional< std::int64_t >	morph::table::detail::parseInteger (std::string_view text)
	Parses a whole decimal integer, all of `text`.
std::optional< double >	morph::table::detail::parseRealClassic (std::string_view text)
	Parses a floating-point number, all of `text`, through a stream in the classic locale: the fallback of parseReal for a standard library without floating-point from_chars.
std::optional< double >	morph::table::detail::parseReal (std::string_view text)
	Parses a floating-point number, all of `text`.
void	morph::table::buildKeys (RowSnapshot const &snapshot, std::size_t column, ColumnInfo const &info, Services const &services, std::size_t first, std::size_t last, KeyColumn &out)
	Builds the keys of rows [first, last) of one column into `out`.
int	morph::table::compareKeys (KeyColumn const &keys, std::uint32_t left, std::uint32_t right, SortDirection dir)
	Compares two rows' keys in one column, valid before invalid in either direction.
std::vector< std::uint32_t >	morph::table::sortRows (std::vector< std::uint32_t > rows, RowOrder order)
	Sorts `rows` by `order` in one call.

Variables
constexpr Deadline	morph::table::kNoDeadline = Deadline::max()
	The deadline that never passes.
constexpr std::size_t	morph::table::detail::kCheckEvery = 2048
	Elements of work between two looks at the clock and the stop token: often enough to keep an owner step near its budget, rarely enough that the clock read is noise.

Detailed Description

Typed sort keys and the chunked, stoppable merge sort over them.

Each column a sort or filter uses gets a KeyColumn: one typed array of keys plus a CellState per cell, built once from a snapshot. Comparing two rows is then a direct compare of two keys, with no parsing and no allocation. Exact kinds stay exact: integers, dates and booleans compare as int64, decimals and quantities as Rational (128-bit cross products); only a Number column holds a double.

Ordering rules, normative for every client and server (spec 7 §5):

an empty or invalid cell sorts after every valid one, in either direction;
each key of a chain has its own direction;
ties break by source row, so the sort is stable.

See docs/spec/table/engine.md.

Definition in file sort.hpp.

Typedef Documentation

◆ SortChain

using morph::table::SortChain = std::vector<SortKey>

A multi-key sort, most significant key first. Empty means source order.

Definition at line 71 of file sort.hpp.

◆ Deadline

using morph::table::Deadline = std::chrono::steady_clock::time_point

A deadline for one step of work; kNoDeadline runs to completion.

Definition at line 81 of file sort.hpp.

Enumeration Type Documentation

◆ SortDirection

enum class morph::table::SortDirection : std::uint8_t

strong

A sort key's direction.

Enumerator
Ascending	Smallest first.
Descending	Largest first. Invalid cells still come last.

Definition at line 52 of file sort.hpp.

◆ CellState

enum class morph::table::CellState : std::uint8_t

strong

Whether a cell has a key.

Enumerator
Valid	The cell has a key.
Empty	The cell is empty; it sorts with invalid cells.
Invalid	The cell could not be read for its column's kind.

Definition at line 74 of file sort.hpp.

Function Documentation

◆ shouldYield()

bool morph::table::detail::shouldYield	(	Deadline	deadline,
		::core::async::StopToken const &	stop )

inlinenodiscard

Whether a step should return now.

Parameters

deadline	When the step must end; kNoDeadline never passes.
stop	A stop request ends the step.

Returns: true when stop is requested or the deadline has passed.

Definition at line 97 of file sort.hpp.

◆ collatorOf()

TextCollator const & morph::table::detail::collatorOf ( Services const & services )

inlinenodiscard

The collator to use: the service's, or the default.

Parameters

services The services.

Returns: The collator; the default outlives every caller.

Definition at line 104 of file sort.hpp.

◆ datesOf()

DateParser const & morph::table::detail::datesOf ( Services const & services )

inlinenodiscard

The date parser to use: the service's, or the default.

Parameters

services The services.

Returns: The parser; the default outlives every caller.

Definition at line 111 of file sort.hpp.

◆ parseInteger()

std::optional< std::int64_t > morph::table::detail::parseInteger ( std::string_view text )

inlinenodiscard

Parses a whole decimal integer, all of text.

Parameters

text The text.

Returns: The value, or nothing when text is not exactly an integer.

Definition at line 118 of file sort.hpp.

◆ parseRealClassic()

std::optional< double > morph::table::detail::parseRealClassic ( std::string_view text )

inlinenodiscard

Parses a floating-point number, all of text, through a stream in the classic locale: the fallback of parseReal for a standard library without floating-point from_chars.

The classic locale, not the global one: a filter value is the wire's text, so its decimal point is . whatever locale the process runs in.

Parameters

text The text.

Returns: The value, or nothing when text is not exactly a number or is NaN.

Definition at line 136 of file sort.hpp.

◆ parseReal()

std::optional< double > morph::table::detail::parseReal ( std::string_view text )

inlinenodiscard

Parses a floating-point number, all of text.

Parameters

text The text.

Returns: The value, or nothing when text is not exactly a number or is NaN.

Definition at line 153 of file sort.hpp.

◆ buildKeys()

void morph::table::buildKeys	(	RowSnapshot const &	snapshot,
		std::size_t	column,
		ColumnInfo const &	info,
		Services const &	services,
		std::size_t	first,
		std::size_t	last,
		KeyColumn &	out )

inline

Builds the keys of rows [first, last) of one column into out.

Parameters

snapshot	The rows.
column	Column index in the snapshot.
info	The column.
services	Collator and date parser; a null member means its default.
first	First row.
last	One past the last row.
out	A column from KeyColumn::forColumn sized for the snapshot.

Definition at line 409 of file sort.hpp.

◆ compareKeys()

int morph::table::compareKeys	(	KeyColumn const &	keys,
		std::uint32_t	left,
		std::uint32_t	right,
		SortDirection	dir )

inlinenodiscard

Compares two rows' keys in one column, valid before invalid in either direction.

Parameters

keys	The column's keys.
left	One row.
right	Another row.
dir	The key's direction; it does not move invalid cells.

Returns: Negative, zero or positive as row left orders before, with, or after right.

Definition at line 434 of file sort.hpp.

◆ sortRows()

std::vector< std::uint32_t > morph::table::sortRows	(	std::vector< std::uint32_t >	rows,
		RowOrder	order )

inlinenodiscard

Sorts rows by order in one call.

Parameters

rows	Row indices.
order	The comparator.

Returns: The sorted rows.

Definition at line 648 of file sort.hpp.

Variable Documentation

◆ kNoDeadline

Deadline morph::table::kNoDeadline = Deadline::max()

inlineconstexpr

The deadline that never passes.

Definition at line 84 of file sort.hpp.

◆ kCheckEvery

std::size_t morph::table::detail::kCheckEvery = 2048

inlineconstexpr

Elements of work between two looks at the clock and the stop token: often enough to keep an owner step near its budget, rarely enough that the clock read is noise.

Definition at line 91 of file sort.hpp.

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

◆ SortChain

◆ Deadline

Enumeration Type Documentation

◆ SortDirection

◆ CellState

Function Documentation

◆ shouldYield()

◆ collatorOf()

◆ datesOf()

◆ parseInteger()

◆ parseRealClassic()

◆ parseReal()

◆ buildKeys()

◆ compareKeys()

◆ sortRows()

Variable Documentation

◆ kNoDeadline

◆ kCheckEvery