Container that stores boundaries. More...

#include <boundary_container.h>

Inheritance diagram for mysql::sets::throwing::Boundary_container< Storage_tp >:

Public Types
using	Storage_t = Storage_tp

using	Iterator_t = mysql::ranges::Range_iterator_type< Storage_t >

using	Const_iterator_t = mysql::ranges::Range_const_iterator_type< Storage_t >

using	Set_traits_t = Storage_t::Set_traits_t

using	Element_t = Set_traits_t::Element_t

using	Memory_resource_t = mysql::allocators::Memory_resource

using	Allocator_t = typename Storage_t::Allocator_t

using	This_t = Boundary_container< Storage_t >

using	Base_t = Basic_boundary_container_wrapper< This_t, Storage_t >

Public Types inherited from mysql::containers::Basic_container_wrapper< Self_tp, Wrapped_tp, mysql::utils::Shall_catch::no >
using	Wrapped_t = Wrapped_tp

Public Types inherited from mysql::sets::detail::Boundary_set_interface< Self_tp, Iterator_tp, Const_iterator_tp, Set_traits_tp >
using	Iterator_t = Iterator_tp

using	Const_iterator_t = Const_iterator_tp

using	Set_category_t = Boundary_set_category_tag

using	Set_traits_t = Set_traits_tp

using	Element_t = typename Set_traits_tp::Element_t

Public Types inherited from mysql::sets::Upper_lower_bound_interface< Self_tp, Set_traits_tp, Iterator_tp, Const_iterator_tp, Iterator_get_value >
using	Iterator_t = Iterator_tp

using	Const_iterator_t = Const_iterator_tp

using	Set_traits_t = Set_traits_tp

using	Iterator_getter_t = Iterator_getter_tp

using	Element_t = typename Set_traits_t::Element_t

Public Member Functions
	Boundary_container () noexcept=default
	Default constructor. More...

	Boundary_container (const Boundary_container &source)=default

	Boundary_container (Boundary_container &&source) noexcept=default

Boundary_container &	operator= (const Boundary_container &source)=default

Boundary_container &	operator= (Boundary_container &&source) noexcept=default

	~Boundary_container ()=default

	Boundary_container (const Memory_resource_t &memory_resource) noexcept
	Construct using the given Memory_resource. More...

	Boundary_container (const Is_boundary_set_over_traits< Set_traits_t > auto &source, const Memory_resource_t &memory_resource)
	Construct from any other Boundary_set over the same Set traits. More...

	Boundary_container (const Is_boundary_set_over_traits< Set_traits_t > auto &source)
	Construct from any other Boundary_set over the same Set traits. More...

template<Is_boundary_iterator_over_type< Element_t > First_iterator_t>
	Boundary_container (const First_iterator_t &first, const std::sentinel_for< First_iterator_t > auto &last, const Memory_resource_t &memory_resource)
	Construct from iterators. More...

template<Is_boundary_iterator_over_type< Element_t > First_iterator_t>
	Boundary_container (const First_iterator_t &first, const std::sentinel_for< First_iterator_t > auto &last)
	Construct from iterators. More...

This_t &	operator= (const Is_boundary_set_over_traits< Set_traits_t > auto &source)
	Assign from any other Boundary_set over the same Set traits. More...

template<Is_boundary_set_over_traits_unqualified< Set_traits_t > Source_t> requires (Can_donate_set<Source_t &&, This_t>)
void	assign (Source_t &&source)

const Storage_t &	storage () const noexcept
	Return a const reference to the underlying storage. More...

Storage_t &	storage () noexcept
	Return a const reference to the underlying storage. More...

void	insert (const Element_t &element)
	Insert the given element (inplace union). More...

void	remove (const Element_t &element)
	Remove the given element (inplace subtraction). More...

void	inplace_union (const Element_t &start, const Element_t &exclusive_end)
	Insert the given interval (inplace union). More...

void	inplace_union (Iterator_t &cursor, const Element_t &start, const Element_t &exclusive_end)
	Insert the given interval (inplace union), reading and updating the given cursor. More...

template<Is_boundary_set_over_traits_unqualified< Set_traits_t > Input_set_t>
void	inplace_union (Input_set_t &&input_set)
	In-place insert the intervals of the given set into this container (inplace union). More...

void	inplace_subtract (const Element_t &start, const Element_t &exclusive_end)
	Subtract the given interval. More...

void	inplace_subtract (Iterator_t &cursor, const Element_t &start, const Element_t &exclusive_end)
	Subtract the given interval, reading and updating the given cursor. More...

template<Is_boundary_set_over_traits_unqualified< Set_traits_t > Input_set_t>
void	inplace_subtract (Input_set_t &&input_set)
	In-place subtract intervals of the given container from this container. More...

void	inplace_intersect (const Element_t &start, const Element_t &exclusive_end) noexcept
	In-place intersect this container with the given interval. More...

template<Is_boundary_set_over_traits_unqualified< Set_traits_t > Input_set_t>
void	inplace_intersect (Input_set_t &&input_set)
	In-place intersect this container with intervals of the given container. More...

template<std::input_iterator First_iterator_t, std::sentinel_for< First_iterator_t > Sentinel_t> requires requires(Wrapped_t w, First_iterator_t f, Sentinel_t s) { w.assign(f, s); }
auto	assign (const First_iterator_t &first, const Sentinel_t &last) noexcept(shall_catch==mysql::utils::Shall_catch::yes\|\|noexcept(std::declval< Wrapped_t >().assign(first, last)))
	Assign a range defined by the two iterators to the wrapped object. More...

template<class Other_t >
auto	assign (const Other_t &other) noexcept(shall_catch==mysql::utils::Shall_catch::yes\|\|noexcept(std::declval< Self_t >().assign(other.begin(), other.end())))
	Copy-assign the other object to the wrapped object. More...

void	assign (Self_t &&other) noexcept
	Move-assign the other object to the wrapped object. More...

Public Member Functions inherited from mysql::sets::Basic_boundary_container_wrapper< Boundary_container< Storage_tp >, Storage_tp >
	Basic_boundary_container_wrapper (Args_t &&...args)

	Basic_boundary_container_wrapper (const Basic_boundary_container_wrapper &source)=default

	Basic_boundary_container_wrapper (Basic_boundary_container_wrapper &&source) noexcept=default

Basic_boundary_container_wrapper &	operator= (const Basic_boundary_container_wrapper &source)=default

Basic_boundary_container_wrapper &	operator= (Basic_boundary_container_wrapper &&source) noexcept=default

	~Basic_boundary_container_wrapper ()=default

Public Member Functions inherited from mysql::sets::Basic_set_container_wrapper< Self_tp, Wrapped_tp, shall_catch_tp >
template<class... Args_t>
	Basic_set_container_wrapper (Args_t &&...args)

template<class Source_t > requires Can_donate_set<decltype(std::declval<Source_t &&>().wrapped()), Wrapped_tp>
void	assign (Source_t &&source)
	Enable move-assign from any Basic_set_container_wrapper for a compatible set type (not necessarily for a derived class). More...

template<std::input_iterator First_iterator_t, std::sentinel_for< First_iterator_t > Sentinel_t> requires requires(Wrapped_t w, First_iterator_t f, Sentinel_t s) { w.assign(f, s); }
auto	assign (const First_iterator_t &first, const Sentinel_t &last) noexcept(shall_catch==mysql::utils::Shall_catch::yes\|\|noexcept(std::declval< Wrapped_t >().assign(first, last)))
	Assign a range defined by the two iterators to the wrapped object. More...

template<class Other_t >
auto	assign (const Other_t &other) noexcept(shall_catch==mysql::utils::Shall_catch::yes\|\|noexcept(std::declval< Self_t >().assign(other.begin(), other.end())))
	Copy-assign the other object to the wrapped object. More...

void	assign (Self_t &&other) noexcept
	Move-assign the other object to the wrapped object. More...

Public Member Functions inherited from mysql::containers::Basic_container_wrapper< Self_tp, Wrapped_tp, mysql::utils::Shall_catch::no >
	Basic_container_wrapper (Args_t &&...args) noexcept(noexcept(Wrapped_t(std::forward< Args_t >(args)...)))
	Constructor that delegates all parameters to the constructor of the wrapped class. More...

auto	assign (const First_iterator_t &first, const Sentinel_t &last) noexcept(shall_catch==mysql::utils::Shall_catch::yes\|\|noexcept(std::declval< Wrapped_t >().assign(first, last)))
	Assign a range defined by the two iterators to the wrapped object. More...

auto	assign (const Other_t &other) noexcept(shall_catch==mysql::utils::Shall_catch::yes\|\|noexcept(std::declval< Self_t >().assign(other.begin(), other.end())))
	Copy-assign the other object to the wrapped object. More...

void	assign (Self_t &&other) noexcept
	Move-assign the other object to the wrapped object. More...

void	clear () noexcept
	Clear the wrapped object. More...

auto	get_memory_resource () const noexcept
	Return the memory resource used by the wrapped object. More...

auto	get_allocator () const noexcept
	Return the allocator used by the wrapped object. More...

auto	begin () noexcept

auto	begin () const noexcept

auto	end () noexcept

auto	end () const noexcept

auto	empty () const noexcept

auto	size () const noexcept

Public Member Functions inherited from mysql::ranges::Collection_interface< Self_tp >
constexpr auto	cbegin () const
	Return constant iterator to the beginning. More...

constexpr auto	cend () const
	Return constant iterator to the end. More...

constexpr auto	rbegin ()
	Return reverse iterator to the beginning. More...

constexpr auto	rend ()
	Return reverse iterator to the end. More...

constexpr auto	rbegin () const
	Return const reverse iterator to the beginning. More...

constexpr auto	rend () const
	Return const reverse iterator to the end. More...

constexpr auto	crbegin () const
	Return const reverse iterator to the beginning. More...

constexpr auto	crend () const
	Return const reverse iterator to the end. More...

constexpr bool	empty () const
	Return true if the range is empty, i.e., begin() == end(). More...

constexpr	operator bool () const
	Return true if the range is non-empty, i.e., begin() != end(). More...

constexpr bool	operator! () const
	Return true if the range is empty, i.e., begin() == end(). More...

constexpr auto	size () const
	Return the number of elements in this view, unsigned (size_t), by computing std::ranges::distance(begin, end) More...

constexpr auto	ssize () const
	Return the number of elements in this view, signed (ptrdiff_t). More...

constexpr decltype(auto)	front () const
	Return the first element. More...

constexpr decltype(auto)	back () const
	Return the last element. Enabled if we have bidirectional iterators. More...

constexpr decltype(auto)	operator[] (std::ptrdiff_t n)
	Return the n'th element, possibly mutable. More...

constexpr decltype(auto)	operator[] (std::ptrdiff_t n) const
	Return the n'th element, const. More...

constexpr auto *	data ()
	Return pointer to underlying contiguous memory. More...

constexpr auto *	data () const
	Return const pointer to underlying contiguous memory. More...

Public Member Functions inherited from mysql::sets::Upper_lower_bound_interface< Self_tp, Set_traits_tp, Iterator_tp, Const_iterator_tp, Iterator_get_value >
constexpr Iterator_t	lower_bound (const Iterator_t &hint, const Element_t &element)
	Return the lower bound for `element`, using an iterator `hint` known to be less than or equal to the correct result. More...

constexpr Const_iterator_t	lower_bound (const Const_iterator_t &hint, const Element_t &element) const
	Return the lower bound for `element`, using an iterator `hint` known to be less than or equal to the correct result. More...

constexpr Iterator_t	lower_bound (const Element_t &element)
	Return the lower bound for `element`. More...

constexpr Const_iterator_t	lower_bound (const Element_t &element) const
	Return the lower bound for `element`. More...

constexpr Iterator_t	upper_bound (const Iterator_t &hint, const Element_t &element)
	Return the upper bound for `element`, using an iterator `hint` known to be less than or equal to the correct result. More...

constexpr Const_iterator_t	upper_bound (const Const_iterator_t &hint, const Element_t &element) const
	Return the upper bound for `element`, using an iterator `hint` known to be less than or equal to the correct result. More...

constexpr Iterator_t	upper_bound (const Element_t &element)
	Return the upper bound for `element`. More...

constexpr Const_iterator_t	upper_bound (const Element_t &element) const
	Return the upper bound for `element`. More...

Static Public Member Functions
static auto	upper_bound_impl (mysql::meta::Is_same_ignore_const< This_t > auto &self, const auto &hint, const Element_t &element) noexcept
	Return iterator to the leftmost boundary at or after `hint` that is greater than the given element. More...

static auto	lower_bound_impl (mysql::meta::Is_same_ignore_const< This_t > auto &self, const auto &hint, const Element_t &element) noexcept
	Return iterator to the leftmost boundary at or after `hint` that is greater than or equal to the given element. More...

Static Public Member Functions inherited from mysql::sets::Upper_lower_bound_interface< Self_tp, Set_traits_tp, Iterator_tp, Const_iterator_tp, Iterator_get_value >
static constexpr Iter_t	lower_bound_dispatch (Self_arg_t &self_arg, const Iter_t &hint, const Element_t &element)
	Implements the lower_bound functions with hint defined above, checking if the hint is already the correct answer, and otherwise delegating to the implementing class. More...

static constexpr auto	lower_bound_dispatch (Self_arg_t &self_arg, const Element_t &element)
	Implements the lower_bound functions without hint defined above. More...

static constexpr Iter_t	upper_bound_dispatch (Self_arg_t &self_arg, const Iter_t &hint, const Element_t &element)
	Implements the upper_bound functions with hint defined above, checking if the hint is already the correct answer, and otherwise delegating to the implementing class. More...

static constexpr auto	upper_bound_dispatch (Self_arg_t &self_arg, const Element_t &element)
	Implements the upper_bound functions without hint defined above. More...

Static Public Attributes
static constexpr bool	has_fast_insertion = Storage_t::has_fast_insertion

Private Types
enum class	Hint_guaranteed { no , yes }
	Whether a `hint` parameter is guaranteed to satisfy the precondition that of being a lower bound. More...

enum class	Can_donate { no , yes }
	Indicates to a function that it may steal elements from a source object, rather than allocate new elements. More...

Private Member Functions
template<Binary_operation operation, Is_boundary_set_over_traits_unqualified< Set_traits_t > Source_t>
void	inplace_op (Source_t &&source)
	Worker for either in-place union or in-place subtraction, adding or removing all intervals from another Boundary_set. More...

template<Binary_operation operation, Hint_guaranteed hint_guaranteed, Can_donate can_donate = Can_donate::no, Is_boundary_set_over_traits_unqualified< Set_traits_t > Source_t = This_t>
void	inplace_union_or_subtract (Iterator_t &cursor, const Element_t &start, const Element_t &exclusive_end, Source_t *source=nullptr)
	Either add or remove the interval, reading and updating the given cursor. More...

Additional Inherited Members
Protected Member Functions inherited from mysql::containers::Basic_container_wrapper< Self_tp, Wrapped_tp, mysql::utils::Shall_catch::no >
auto &	wrapped () &noexcept

const auto &	wrapped () const &noexcept

auto &&	wrapped () &&noexcept

Detailed Description

template<Is_boundary_storage Storage_tp>
class mysql::sets::throwing::Boundary_container< Storage_tp >

Container that stores boundaries.

This implements the Is_boundary_set concept, and additionally has functionality for in-place union, intersection, and subtraction, as well as copy from another Boundary_set and making this container empty.

All members provide basic exception safety guarantee, as defined at https://en.cppreference.com/w/cpp/language/exceptions#Exception_safety . Some additionally provide strong exception safety guarantee or nothrow exception guarantee: see documentation of each member for details.

Member Typedef Documentation

◆ Allocator_t

template<Is_boundary_storage Storage_tp>

using mysql::sets::throwing::Boundary_container< Storage_tp >::Allocator_t = typename Storage_t::Allocator_t

◆ Base_t

template<Is_boundary_storage Storage_tp>

using mysql::sets::throwing::Boundary_container< Storage_tp >::Base_t = Basic_boundary_container_wrapper<This_t, Storage_t>

◆ Const_iterator_t

template<Is_boundary_storage Storage_tp>

using mysql::sets::throwing::Boundary_container< Storage_tp >::Const_iterator_t = mysql::ranges::Range_const_iterator_type<Storage_t>

◆ Element_t

template<Is_boundary_storage Storage_tp>

using mysql::sets::throwing::Boundary_container< Storage_tp >::Element_t = Set_traits_t::Element_t

◆ Iterator_t

template<Is_boundary_storage Storage_tp>

using mysql::sets::throwing::Boundary_container< Storage_tp >::Iterator_t = mysql::ranges::Range_iterator_type<Storage_t>

◆ Memory_resource_t

template<Is_boundary_storage Storage_tp>

using mysql::sets::throwing::Boundary_container< Storage_tp >::Memory_resource_t = mysql::allocators::Memory_resource

◆ Set_traits_t

template<Is_boundary_storage Storage_tp>

using mysql::sets::throwing::Boundary_container< Storage_tp >::Set_traits_t = Storage_t::Set_traits_t

◆ Storage_t

template<Is_boundary_storage Storage_tp>

using mysql::sets::throwing::Boundary_container< Storage_tp >::Storage_t = Storage_tp

◆ This_t

template<Is_boundary_storage Storage_tp>

using mysql::sets::throwing::Boundary_container< Storage_tp >::This_t = Boundary_container<Storage_t>

Member Enumeration Documentation

◆ Can_donate

template<Is_boundary_storage Storage_tp>

enum class mysql::sets::throwing::Boundary_container::Can_donate

strongprivate

Indicates to a function that it may steal elements from a source object, rather than allocate new elements.

Enumerator
no
yes

◆ Hint_guaranteed

template<Is_boundary_storage Storage_tp>

enum class mysql::sets::throwing::Boundary_container::Hint_guaranteed

strongprivate

Whether a hint parameter is guaranteed to satisfy the precondition that of being a lower bound.

Enumerator
no
yes

Constructor & Destructor Documentation

◆ Boundary_container() [1/8]

template<Is_boundary_storage Storage_tp>

mysql::sets::throwing::Boundary_container< Storage_tp >::Boundary_container ( )

defaultnoexcept

Default constructor.

◆ Boundary_container() [2/8]

template<Is_boundary_storage Storage_tp>

mysql::sets::throwing::Boundary_container< Storage_tp >::Boundary_container ( const Boundary_container< Storage_tp > & source )

default

◆ Boundary_container() [3/8]

template<Is_boundary_storage Storage_tp>

mysql::sets::throwing::Boundary_container< Storage_tp >::Boundary_container ( Boundary_container< Storage_tp > && source )

defaultnoexcept

◆ ~Boundary_container()

template<Is_boundary_storage Storage_tp>

mysql::sets::throwing::Boundary_container< Storage_tp >::~Boundary_container ( )

default

◆ Boundary_container() [4/8]

template<Is_boundary_storage Storage_tp>

mysql::sets::throwing::Boundary_container< Storage_tp >::Boundary_container ( const Memory_resource_t & memory_resource )

inlineexplicitnoexcept

Construct using the given Memory_resource.

◆ Boundary_container() [5/8]

template<Is_boundary_storage Storage_tp>

mysql::sets::throwing::Boundary_container< Storage_tp >::Boundary_container	(	const Is_boundary_set_over_traits< Set_traits_t > auto &	source,
		const Memory_resource_t &	memory_resource
	)

inlineexplicit

Construct from any other Boundary_set over the same Set traits.

Exceptions

bad_alloc This may occur when the operation is half-completed, which may leave the container as a subset of source.

◆ Boundary_container() [6/8]

template<Is_boundary_storage Storage_tp>

mysql::sets::throwing::Boundary_container< Storage_tp >::Boundary_container ( const Is_boundary_set_over_traits< Set_traits_t > auto & source )

inlineexplicit

Construct from any other Boundary_set over the same Set traits.

Exceptions

bad_alloc This may occur when the operation is half-completed, which may leave the container as a subset of source.

◆ Boundary_container() [7/8]

template<Is_boundary_storage Storage_tp>

template<Is_boundary_iterator_over_type< Element_t > First_iterator_t>

mysql::sets::throwing::Boundary_container< Storage_tp >::Boundary_container	(	const First_iterator_t &	first,
		const std::sentinel_for< First_iterator_t > auto &	last,
		const Memory_resource_t &	memory_resource
	)

inlineexplicit

Construct from iterators.

Exceptions

bad_alloc This may occur when the operation is half-completed, which may leave the container as a subset of source.

◆ Boundary_container() [8/8]

template<Is_boundary_storage Storage_tp>

template<Is_boundary_iterator_over_type< Element_t > First_iterator_t>

mysql::sets::throwing::Boundary_container< Storage_tp >::Boundary_container	(	const First_iterator_t &	first,
		const std::sentinel_for< First_iterator_t > auto &	last
	)

inlineexplicit

Construct from iterators.

Exceptions

bad_alloc This may occur when the operation is half-completed, which may leave the container as a subset of source.

Member Function Documentation

◆ assign() [1/4]

template<Is_boundary_storage Storage_tp>

template<std::input_iterator First_iterator_t, std::sentinel_for< First_iterator_t > Sentinel_t>
requires requires(Wrapped_t w, First_iterator_t f, Sentinel_t s) { w.assign(f, s); }

auto mysql::containers::Basic_container_wrapper< Self_tp, Wrapped_tp, shall_catch >::assign	(	const First_iterator_t &	first,
		const Sentinel_t &	last
	)

inlinenoexcept

Assign a range defined by the two iterators to the wrapped object.

This is enabled provided that the wrapped class defines an assign member taking two iterators.

◆ assign() [2/4]

template<Is_boundary_storage Storage_tp>

template<class Other_t >

auto mysql::containers::Basic_container_wrapper< Self_tp, Wrapped_tp, shall_catch >::assign ( const Other_t & other )

inlinenoexcept

Copy-assign the other object to the wrapped object.

This is enabled provided that the subclass defines an assign member taking two iterators.

◆ assign() [3/4]

template<Is_boundary_storage Storage_tp>

void mysql::containers::Basic_container_wrapper< Self_tp, Wrapped_tp, shall_catch >::assign ( Self_t && other )

inlinenoexcept

Move-assign the other object to the wrapped object.

This is enabled provided that the wrapped class is nothrow-move-assignable.

◆ assign() [4/4]

template<Is_boundary_storage Storage_tp>

template<Is_boundary_set_over_traits_unqualified< Set_traits_t > Source_t>
requires (Can_donate_set<Source_t &&, This_t>)

void mysql::sets::throwing::Boundary_container< Storage_tp >::assign ( Source_t && source )

inline

◆ inplace_intersect() [1/2]

template<Is_boundary_storage Storage_tp>

void mysql::sets::throwing::Boundary_container< Storage_tp >::inplace_intersect	(	const Element_t &	start,
		const Element_t &	exclusive_end
	)

inlinenoexcept

In-place intersect this container with the given interval.

This may truncate intervals that overlap partially with the given interval, and remove intervals that are disjoint from the given interval.

Parameters

start	The left boundary of the interval, inclusive.
exclusive_end	The right boundary of the interval, exclusive.

Since this cannot increase the number of intervals, it never throws.

◆ inplace_intersect() [2/2]

template<Is_boundary_storage Storage_tp>

template<Is_boundary_set_over_traits_unqualified< Set_traits_t > Input_set_t>

void mysql::sets::throwing::Boundary_container< Storage_tp >::inplace_intersect ( Input_set_t && input_set )

inline

In-place intersect this container with intervals of the given container.

This may truncate intervals that overlap partially with one interval from the given set, split intervals that overlap partially with more than one interval from the given set, and remove intervals that are disjoint from the given interval set.

Algorithm and complexity:

See also: inplace_union.

Parameters

input_set The input set.

Exceptions

bad_alloc If an out-of-memory condition occurred while splitting an interval. This may occur when the operation is half-completed, which may leave the container as a subset of the previous set and a superset of the intersection.

◆ inplace_op()

template<Is_boundary_storage Storage_tp>

template<Binary_operation operation, Is_boundary_set_over_traits_unqualified< Set_traits_t > Source_t>

void mysql::sets::throwing::Boundary_container< Storage_tp >::inplace_op ( Source_t && source )

inlineprivate

Worker for either in-place union or in-place subtraction, adding or removing all intervals from another Boundary_set.

Algorithm and complexity:

See also: inplace_union.

Template Parameters

operation The set operation to compute.

Parameters

source The container whose elements will be added or removed in this container.

Exceptions

bad_alloc This may occur when the operation is half-completed, so that a subset of source has been added or removed from this set.

◆ inplace_subtract() [1/3]

template<Is_boundary_storage Storage_tp>

void mysql::sets::throwing::Boundary_container< Storage_tp >::inplace_subtract	(	const Element_t &	start,
		const Element_t &	exclusive_end
	)

inline

Subtract the given interval.

This may split an interval into two parts, shorten an existing interval in one end, remove a one-element interval, or, if the element was not in this container, do nothing.

This may truncate and/or split intervals that overlap partially with the subtracted interval, and remove intervals that overlap completely with the subtracted interval.

Parameters

start	The left boundary of the interval, inclusive.
exclusive_end	The right boundary of the interval, exclusive.

Exceptions

bad_alloc If an out-of-memory condition occurred while splitting an interval. This leaves the container unmodified.

◆ inplace_subtract() [2/3]

template<Is_boundary_storage Storage_tp>

template<Is_boundary_set_over_traits_unqualified< Set_traits_t > Input_set_t>

void mysql::sets::throwing::Boundary_container< Storage_tp >::inplace_subtract ( Input_set_t && input_set )

inline

In-place subtract intervals of the given container from this container.

This may truncate and/or split intervals that overlap partially with subtracted intervals, and remove intervals that overlap completely with subtracted intervals.

Algorithm and complexity:

See also: inplace_union.

Parameters

input_set The input set.

Exceptions

bad_alloc If an out-of-memory condition occurred while splitting an interval. This may occur when the operation is half-completed, which may leave the container as a subset of the previous set and a superset of the difference.

◆ inplace_subtract() [3/3]

template<Is_boundary_storage Storage_tp>

void mysql::sets::throwing::Boundary_container< Storage_tp >::inplace_subtract	(	Iterator_t &	cursor,
		const Element_t &	start,
		const Element_t &	exclusive_end
	)

inline

Subtract the given interval, reading and updating the given cursor.

This may truncate and/or split intervals that overlap partially with the subtracted interval, and remove intervals that overlap completely with the subtracted interval.

Parameters

[in,out]	cursor	Hint for the insertion position. If it refers to `lower_bound(start)`, this function finds the insertion position in O(1); if it refers to a boundary less than `lower_bound(start)`, it may reduce the search space when finding the insertion position; otherwise, the hint is ignored and the entire set has to be searched. It will be updated to `upper_bound(exclusive_end)`, which makes it good to reuse for future calls to this function, with intervals following this one.
	start	The left boundary of the interval, inclusive.
	exclusive_end	The right boundary of the interval, exclusive.

Exceptions

bad_alloc If an out-of-memory condition occurred while splitting an interval. This leaves the container unmodified.

◆ inplace_union() [1/3]

template<Is_boundary_storage Storage_tp>

void mysql::sets::throwing::Boundary_container< Storage_tp >::inplace_union	(	const Element_t &	start,
		const Element_t &	exclusive_end
	)

inline

Insert the given interval (inplace union).

This may merge intervals that overlap or are adjacent to the given interval, or insert the interval between existing intervals, or, if the interval was a subset of this container, do nothing.

Parameters

start	The left boundary of the interval, inclusive.
exclusive_end	The right boundary of the interval, exclusive.

Exceptions

bad_alloc If an out-of-memory condition occurred while inserting the interval. This leaves the container unmodified.

◆ inplace_union() [2/3]

template<Is_boundary_storage Storage_tp>

template<Is_boundary_set_over_traits_unqualified< Set_traits_t > Input_set_t>

void mysql::sets::throwing::Boundary_container< Storage_tp >::inplace_union ( Input_set_t && input_set )

inline

In-place insert the intervals of the given set into this container (inplace union).

This may merge intervals that overlap or are adjacent to a given interval, and/or insert intervals between existing intervals, or, if the set was a subset of this container, do nothing.

This uses one of two algorithms, depending on the nature of the underlying container:

If the underlying container supports fast insertion in the middle (e.g. set or list), then it uses a true in-place algorithm, possibly adjusting endpoints of existing intervals, and reusing memory as much as possible.
Otherwise (e.g. sorted vector), it uses an out-of-place algorithm that computes the result in a new container and then move-assigns the new container to the current container.

The complexity depends on the underlying container:

set: O(number_of_removed_intervals + input.size() * log(this->size()))
list: Normally, O(input.size() + this->size()); or O(input.size()) if input_set.front() >= this->back().
vector: Normally, O(input.size() + this->size()); or O(input.size()) if input_set.front() >= this->back().

Parameters

input_set The input set.

Exceptions

bad_alloc If an out-of-memory condition occurred while inserting an interval. This may occur when the operation is half-completed, which may leave the container as a superset of the previous set and a subset of the union.

◆ inplace_union() [3/3]

template<Is_boundary_storage Storage_tp>

void mysql::sets::throwing::Boundary_container< Storage_tp >::inplace_union	(	Iterator_t &	cursor,
		const Element_t &	start,
		const Element_t &	exclusive_end
	)

inline

Insert the given interval (inplace union), reading and updating the given cursor.

This may merge intervals that overlap or are adjacent to the given interval, or insert the interval between existing intervals, or, if the interval was a subset of this container, do nothing.

Parameters

[in,out]	cursor	Hint for the insertion position. If it refers to `lower_bound(start)`, this function finds the insertion position in O(1); if it refers to a boundary less than `lower_bound(start)`, it may reduce the search space when finding the insertion position; otherwise, the hint is ignored and the entire set has to be searched. It will be updated to `upper_bound(exclusive_end)`, which makes it perfect to reuse for future calls to this function, with intervals following this one.
	start	The left boundary of the interval, inclusive.
	exclusive_end	The right boundary of the interval, exclusive.

Exceptions

bad_alloc If an out-of-memory condition occurred while inserting the interval. This leaves the container unmodified.

◆ inplace_union_or_subtract()

template<Is_boundary_storage Storage_tp>

template<Binary_operation operation, Hint_guaranteed hint_guaranteed, Can_donate can_donate = Can_donate::no, Is_boundary_set_over_traits_unqualified< Set_traits_t > Source_t = This_t>

void mysql::sets::throwing::Boundary_container< Storage_tp >::inplace_union_or_subtract	(	Iterator_t &	cursor,
		const Element_t &	start,
		const Element_t &	exclusive_end,
		Source_t *	source = `nullptr`
	)

inlineprivate

Either add or remove the interval, reading and updating the given cursor.

Complexity:

list: O(number_of_removed_intervals + std::distance(cursor, first_removed_interval).
set: O(1) if it doesn't change the number of intervals; O(log(size()) + number_of_removed_intervals) otherwise.
Ordered_vector: constant if it doesn't change the number of intervals; linear in the distance from the first removed element to end() otherwise

Template Parameters

operation	The operation: op_union or op_subtraction
hint_guaranteed	If yes, raise an assertion if `hint` does not satisfy the requirements. If no, ignore `hint` if it does not satisfy the requirements. See below.
can_donate	If no, allocate new elements when needed; if yes, steal elements from `source` when needed.

Parameters

[in,out]	cursor	Hint for the insertion position. If it refers to `upper_bound(start)`, this function finds the insertion position in O(1). If it refers to a boundary less than `upper_bound(start)`, it may reduce the search space when finding the insertion position. If it refers to a boundary greater than `upper_bound(start)`, the behavior depends on `hint_guaranteed` : If `hint_guaranteed` is yes, the behavior is undefined (an assertion is raised in debug mode); otherwise, the hint is ignored and the entire set has to be searched. `cursor` will be updated to `upper_bound(exclusive_end)`, which makes it good to reuse in future calls to this function, with intervals following this one.
	start	The left boundary of the interval, inclusive.
	exclusive_end	The right boundary of the interval, exclusive.
	source	Container from which elements may be stolen.

Exceptions

bad_alloc This leaves the container unmodified.

◆ insert()

template<Is_boundary_storage Storage_tp>

void mysql::sets::throwing::Boundary_container< Storage_tp >::insert ( const Element_t & element )

inline

Insert the given element (inplace union).

This may insert a new one-element interval, extend an existing interval at one end, merge two intervals that were separated by only the given element, or, if the element was already in this container, do nothing.

Parameters

element The element to insert.

Exceptions

bad_alloc If an out-of-memory condition occurred while inserting the interval. This leaves the container unmodified.

◆ lower_bound_impl()

template<Is_boundary_storage Storage_tp>

static auto mysql::sets::throwing::Boundary_container< Storage_tp >::lower_bound_impl	(	mysql::meta::Is_same_ignore_const< This_t > auto &	self,
		const auto &	hint,
		const Element_t &	element
	)

inlinestaticnoexcept

Return iterator to the leftmost boundary at or after hint that is greater than or equal to the given element.

Complexity:

O(1) if the return element is end() or hint;
the complexity of Storage_t::upper_bound, otherwise.

(We override the Boundary_set_interface member because this is faster.)

◆ operator=() [1/3]

template<Is_boundary_storage Storage_tp>

Boundary_container & mysql::sets::throwing::Boundary_container< Storage_tp >::operator= ( Boundary_container< Storage_tp > && source )

defaultnoexcept

◆ operator=() [2/3]

template<Is_boundary_storage Storage_tp>

Boundary_container & mysql::sets::throwing::Boundary_container< Storage_tp >::operator= ( const Boundary_container< Storage_tp > & source )

default

◆ operator=() [3/3]

template<Is_boundary_storage Storage_tp>

This_t & mysql::sets::throwing::Boundary_container< Storage_tp >::operator= ( const Is_boundary_set_over_traits< Set_traits_t > auto & source )

inline

Assign from any other Boundary_set over the same Set traits.

Exceptions

bad_alloc This may occur when the operation is half-completed, which may leave the container as a subset of source.

◆ remove()

template<Is_boundary_storage Storage_tp>

void mysql::sets::throwing::Boundary_container< Storage_tp >::remove ( const Element_t & element )

inline

Remove the given element (inplace subtraction).

This may split an interval into two parts, shorten an existing interval in one end, remove a one-element interval, or, if the element was not in this container, do nothing.

Parameters

element The element to remove.

Exceptions

bad_alloc If an out-of-memory condition occurred while splitting an interval. This leaves the container unmodified.

◆ storage() [1/2]

template<Is_boundary_storage Storage_tp>

const Storage_t & mysql::sets::throwing::Boundary_container< Storage_tp >::storage ( ) const

inlinenoexcept

Return a const reference to the underlying storage.

◆ storage() [2/2]

template<Is_boundary_storage Storage_tp>

Storage_t & mysql::sets::throwing::Boundary_container< Storage_tp >::storage ( )

inlinenoexcept

Return a const reference to the underlying storage.

◆ upper_bound_impl()

template<Is_boundary_storage Storage_tp>

static auto mysql::sets::throwing::Boundary_container< Storage_tp >::upper_bound_impl	(	mysql::meta::Is_same_ignore_const< This_t > auto &	self,
		const auto &	hint,
		const Element_t &	element
	)

inlinestaticnoexcept

Return iterator to the leftmost boundary at or after hint that is greater than the given element.

Complexity:

O(1) if the return element is end() or hint;
the complexity of Storage_t::upper_bound, otherwise.

(We override the Boundary_set_interface member because this is faster.)

Member Data Documentation

◆ has_fast_insertion

template<Is_boundary_storage Storage_tp>

constexpr bool mysql::sets::throwing::Boundary_container< Storage_tp >::has_fast_insertion = Storage_t::has_fast_insertion

staticconstexpr

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

libs/mysql/sets/throwing/boundary_container.h

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Allocator_t

◆ Base_t

◆ Const_iterator_t

◆ Element_t

◆ Iterator_t

◆ Memory_resource_t

◆ Set_traits_t

◆ Storage_t

◆ This_t

Member Enumeration Documentation

◆ Can_donate

◆ Hint_guaranteed

Constructor & Destructor Documentation

◆ Boundary_container() [1/8]

◆ Boundary_container() [2/8]

◆ Boundary_container() [3/8]

◆ ~Boundary_container()

◆ Boundary_container() [4/8]

◆ Boundary_container() [5/8]

◆ Boundary_container() [6/8]

◆ Boundary_container() [7/8]

◆ Boundary_container() [8/8]

Member Function Documentation

◆ assign() [1/4]

◆ assign() [2/4]

◆ assign() [3/4]

◆ assign() [4/4]

◆ inplace_intersect() [1/2]

◆ inplace_intersect() [2/2]

◆ inplace_op()

◆ inplace_subtract() [1/3]

◆ inplace_subtract() [2/3]

◆ inplace_subtract() [3/3]

◆ inplace_union() [1/3]

◆ inplace_union() [2/3]

◆ inplace_union() [3/3]

◆ inplace_union_or_subtract()

◆ insert()

◆ lower_bound_impl()

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ remove()

◆ storage() [1/2]

◆ storage() [2/2]

◆ upper_bound_impl()

Member Data Documentation

◆ has_fast_insertion