What changed between two view orders, as list-model operations. More...

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <span>
#include <vector>

Classes
struct	morph::table::ViewOp
	One list-model operation. More...
struct	morph::table::ViewChange
	The operations that turn one view order into another. More...
class	morph::table::detail::SlotCounter
	A Fenwick tree of slot occupancy: how many occupied slots precede a slot. More...
struct	morph::table::detail::ViewPositions
	Where each identity sits in each view. More...

Functions
std::vector< bool >	morph::table::detail::longestIncreasing (std::span< std::uint32_t const > values)
	Marks the elements of a longest strictly increasing subsequence.
bool	morph::table::detail::appendRemovals (std::span< std::uint32_t const > before, ViewPositions const &positions, std::vector< ViewOp > &out, std::size_t limit)
	Appends the removals, back to front, coalesced into runs.
bool	morph::table::detail::appendMoves (std::span< std::uint32_t const > ranks, std::vector< ViewOp > &out, std::size_t limit)
	Appends the moves that put the kept rows in their new order.
bool	morph::table::detail::appendInsertions (std::span< std::uint32_t const > after, ViewPositions const &positions, std::vector< ViewOp > &out, std::size_t limit)
	Appends the insertions, front to back, coalesced into runs.
void	morph::table::detail::appendChanges (std::span< std::uint32_t const > changed, ViewPositions const &positions, std::vector< ViewOp > &out)
	Appends the changes of rows in both views, in new positions, coalesced into runs.
ViewChange	morph::table::diffViews (std::span< std::uint32_t const > before, std::span< std::uint32_t const > after, std::span< std::uint32_t const > changed, std::size_t identityLimit, std::size_t resetThreshold)
	Computes the operations that turn `before` into `after`.
template<typename T>
void	morph::table::applyViewChange (std::vector< T > &list, ViewChange const &change, std::span< T const > after)
	Applies `change` to `list`, following the replay contract.

Variables
constexpr auto	morph::table::detail::kAbsent = std::numeric_limits<std::uint32_t>::max()
	Marks an identity absent from a view.

Detailed Description

What changed between two view orders, as list-model operations.

A renderer's list model applies a ViewChange as keyed operations, so selection, focus and scroll position survive a sort or a filter. The change is computed from the old and new view orders and is minimal in moves: rows on a longest increasing subsequence of the new order stay where they are and only the rest move.

Replay contract. Apply the operations in order to the old list:

Removed{first, count} erases count rows at first;
Moved{first, to} erases the row at first, then inserts it at to (an index into the list after the erase);
Inserted{first, count} inserts the new view's rows [first, first + count) at first;
Changed{first, count} marks rows [first, first + count) of the new view as having new content, and changes no order;
Reset replaces the whole list with the new view.

All removals come first (back to front), then moves, then insertions (front to back), then changes. The result is the new view.

See docs/spec/table/engine.md.

Definition in file view_change.hpp.

Function Documentation

◆ longestIncreasing()

std::vector< bool > morph::table::detail::longestIncreasing ( std::span< std::uint32_t const > values )

inlinenodiscard

Marks the elements of a longest strictly increasing subsequence.

Parameters

values The sequence.

Returns: One flag per element; true on the subsequence.

Definition at line 121 of file view_change.hpp.

◆ appendRemovals()

bool morph::table::detail::appendRemovals	(	std::span< std::uint32_t const >	before,
		ViewPositions const &	positions,
		std::vector< ViewOp > &	out,
		std::size_t	limit )

inlinenodiscard

Appends the removals, back to front, coalesced into runs.

Parameters

before	The old view.
positions	Where identities sit.
out	Receives the operations.
limit	Most operations `out` may hold; past it the scan stops.

Returns: false when the removals take out past limit.

Definition at line 164 of file view_change.hpp.

◆ appendMoves()

bool morph::table::detail::appendMoves	(	std::span< std::uint32_t const >	ranks,
		std::vector< ViewOp > &	out,
		std::size_t	limit )

inlinenodiscard

Appends the moves that put the kept rows in their new order.

ranks lists the kept rows in old order, as their rank in the new order. Rows on a longest increasing subsequence stay. Between two stationary rows is a gap; each moving row leaves a slot in the gap it was in and takes a slot in the gap it belongs to. Within a gap, rows already moved (by rank) sit before rows not yet moved (by old position), so every row's index is a count of occupied slots before its own.

Parameters

ranks	The kept rows, in old order, as new-order ranks.
out	Receives the operations.
limit	Most operations `out` may hold; past it no move is computed.

Returns: false when the moves would take out past limit.

Definition at line 196 of file view_change.hpp.

◆ appendInsertions()

bool morph::table::detail::appendInsertions	(	std::span< std::uint32_t const >	after,
		ViewPositions const &	positions,
		std::vector< ViewOp > &	out,
		std::size_t	limit )

inlinenodiscard

Appends the insertions, front to back, coalesced into runs.

Parameters

after	The new view.
positions	Where identities sit.
out	Receives the operations.
limit	Most operations `out` may hold; past it the scan stops.

Returns: false when the insertions take out past limit.

Definition at line 269 of file view_change.hpp.

◆ appendChanges()

void morph::table::detail::appendChanges	(	std::span< std::uint32_t const >	changed,
		ViewPositions const &	positions,
		std::vector< ViewOp > &	out )

inline

Appends the changes of rows in both views, in new positions, coalesced into runs.

Parameters

changed	Identities whose content changed.
positions	Where identities sit.
out	Receives the operations.

Definition at line 293 of file view_change.hpp.

◆ diffViews()

ViewChange morph::table::diffViews	(	std::span< std::uint32_t const >	before,
		std::span< std::uint32_t const >	after,
		std::span< std::uint32_t const >	changed,
		std::size_t	identityLimit,
		std::size_t	resetThreshold )

inlinenodiscard

Computes the operations that turn before into after.

Rows are identified by integers below identityLimit, the same in both orders: a source row index when both views come from one snapshot, or a mapping through RowId when they do not.

Parameters

before	The old view order.
after	The new view order.
changed	Identities whose content changed; those in both views are reported as Changed in their new position.
identityLimit	One more than the largest identity.
resetThreshold	More operations than this give one Reset.

Returns: The change.

Definition at line 330 of file view_change.hpp.

◆ applyViewChange()

template<typename T>

void morph::table::applyViewChange	(	std::vector< T > &	list,
		ViewChange const &	change,
		std::span< T const >	after )

Applies change to list, following the replay contract.

The reference implementation of what a renderer's list model does; the tests replay every change through it.

Template Parameters

T	Element type.

Parameters

list	The old view's elements; becomes the new view's.
change	The change.
after	The new view's elements, where inserted and reset rows come from.

Definition at line 383 of file view_change.hpp.

Variable Documentation

◆ kAbsent

auto morph::table::detail::kAbsent = std::numeric_limits<std::uint32_t>::max()

inlineconstexpr

Marks an identity absent from a view.

Definition at line 148 of file view_change.hpp.

Classes

Functions

Variables

Detailed Description

Function Documentation

◆ longestIncreasing()

◆ appendRemovals()

◆ appendMoves()

◆ appendInsertions()

◆ appendChanges()

◆ diffViews()

◆ applyViewChange()

Variable Documentation

◆ kAbsent