Container for intervals. More...

#include <interval_container.h>

Inheritance diagram for mysql::sets::Interval_container< Boundary_container_tp >:

Public Types
using	Boundary_container_t = Boundary_container_tp

using	This_t = Interval_container< Boundary_container_t >

using	Memory_resource_t = mysql::allocators::Memory_resource

using	Allocator_t = typename Boundary_container_t::Allocator_t

using	Boundary_iterator_t = typename Boundary_container_t::Iterator_t

using	Interval_t = Interval< Set_traits_t >

using	Storage_t = Storage_or_void< Boundary_container_t >

Public Types inherited from mysql::sets::Interval_set_interface< Interval_container< Boundary_container_tp >, Boundary_container_tp >
using	Boundary_set_t = Boundary_container_tp

using	This_t = Interval_set_interface< Self_t, Boundary_set_t >

using	Set_category_t = Interval_set_category_tag

using	Set_traits_t = Boundary_set_t::Set_traits_t

using	Element_t = typename Set_traits_t::Element_t

using	Make_interval_t = detail::Make_interval< Set_traits_t >

using	Boundary_iterator_t = mysql::ranges::Range_iterator_type< Boundary_container_tp >

using	Boundary_const_iterator_t = mysql::ranges::Range_const_iterator_type< Boundary_container_tp >

using	Iterator_t = mysql::ranges::Disjoint_pairs_iterator< Boundary_iterator_t, Make_interval_t >

using	Const_iterator_t = mysql::ranges::Disjoint_pairs_iterator< Boundary_const_iterator_t, Make_interval_t >

Public Types inherited from mysql::ranges::Disjoint_pairs_interface< Self_tp, Make_pair_tp >
using	Make_pair_t = Make_pair_tp

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

	Interval_container (const Interval_container &source)=default
	Copy constructor. More...

	Interval_container (Interval_container &&source) noexcept=default
	Move constructor, defaulted. More...

Interval_container &	operator= (const Interval_container &source)=default
	Copy assignment operator. More...

Interval_container &	operator= (Interval_container &&source) noexcept=default
	Move assignment operator, defaulted. More...

	~Interval_container () noexcept=default
	Destructor. More...

	Interval_container (const Memory_resource_t &memory_resource) noexcept
	Construct an empty container using the specified Memory_resource. More...

	Interval_container (const Is_interval_set_over_traits< Set_traits_t > auto &source)
	Construct by copying any other Interval_set over the same boundary traits. More...

	Interval_container (const Is_interval_set_over_traits< Set_traits_t > auto &source, const Memory_resource_t &memory_resource)
	Construct by copying any other Interval_set over the same boundary traits. More...

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

template<Is_interval_set_over_traits_unqualified< Set_traits_t > Source_t>
auto	assign (Source_t &&source)
	Overwrite this object with `source` (copy-assigned). More...

decltype(auto)	get_memory_resource () const noexcept
	Return the Memory_resource object that manages memory in this object, or a default-constructed Memory_resource if there is none. More...

void	clear () noexcept
	Make this container empty. More...

auto &	boundaries () &noexcept
	Return an lvalue reference to the underlying boundary container. More...

const auto &	boundaries () const &noexcept
	Return a const lvalue reference to the underlying boundary container. More...

auto &&	boundaries () &&noexcept
	Return an rvalue reference to the underlying boundary container. More...

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

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

auto	inplace_union (const Interval_t &interval)
	Insert the given interval (inplace union). More...

auto	inplace_union (Boundary_iterator_t &cursor, const Interval_t &interval)
	Insert the given interval (inplace union), reading and updating the given cursor. More...

template<Is_interval_set_over_traits_unqualified< Set_traits_t > Interval_set_t>
auto	inplace_union (Interval_set_t &&interval_set)
	In-place insert the intervals of the given set into this container (inplace union). More...

auto	inplace_subtract (const Interval_t &interval)
	Subtract the given interval. More...

auto	inplace_subtract (Boundary_iterator_t &cursor, const Interval_t &interval)
	Subtract the given interval, reading and updating the given cursor. More...

template<Is_interval_set_over_traits_unqualified< Set_traits_t > Interval_set_t>
auto	inplace_subtract (Interval_set_t &&interval_set)
	In-place subtract intervals of the given set from this container. More...

void	inplace_intersect (const Interval_t &interval) noexcept
	In-place intersect this container with the given interval. More...

template<Is_interval_set_over_traits_unqualified< Set_traits_t > Interval_set_t>
auto	inplace_intersect (Interval_set_t &&interval_set)
	In-place intersect this container with the given set. More...

Public Member Functions inherited from mysql::sets::Interval_set_interface< Interval_container< Boundary_container_tp >, Boundary_container_tp >
const auto &	disjoint_pairs_source () const

auto &	disjoint_pairs_source ()

Public Member Functions inherited from mysql::ranges::Disjoint_pairs_interface< Self_tp, Make_pair_tp >
auto	begin () const
	Return const iterator to the beginning. More...

auto	end () const
	Return const iterator to sentinel. More...

auto	begin ()
	Return iterator to the beginning. More...

auto	end ()
	Return iterator to sentinel. More...

bool	empty () const
	Return true if the range is empty. More...

bool	empty () const
	Return true if the range is empty. More...

auto	size () const
	Return the number of pairs, i.e., half the size of the source. More...

auto	size () const
	Return the number of pairs, i.e., half the size of the source. More...

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...

Static Public Attributes
static constexpr bool	has_fast_insertion

Private Types
using	Base_t = Interval_set_interface< This_t, Boundary_container_t >

Private Attributes
Boundary_container_t	m_boundaries

Static Private Attributes
static constexpr bool	noexcept_insertions

Detailed Description

template<Is_boundary_container Boundary_container_tp>
class mysql::sets::Interval_container< Boundary_container_tp >

Container for intervals.

Template Parameters

Boundary_container_tp Boundary container, i.e., a Boundary set capable of storing the data, and computing inplace operations.

Member Typedef Documentation

◆ Allocator_t

template<Is_boundary_container Boundary_container_tp>

using mysql::sets::Interval_container< Boundary_container_tp >::Allocator_t = typename Boundary_container_t::Allocator_t

◆ Base_t

template<Is_boundary_container Boundary_container_tp>

using mysql::sets::Interval_container< Boundary_container_tp >::Base_t = Interval_set_interface<This_t, Boundary_container_t>

private

◆ Boundary_container_t

template<Is_boundary_container Boundary_container_tp>

using mysql::sets::Interval_container< Boundary_container_tp >::Boundary_container_t = Boundary_container_tp

◆ Boundary_iterator_t

template<Is_boundary_container Boundary_container_tp>

using mysql::sets::Interval_container< Boundary_container_tp >::Boundary_iterator_t = typename Boundary_container_t::Iterator_t

◆ Interval_t

template<Is_boundary_container Boundary_container_tp>

using mysql::sets::Interval_container< Boundary_container_tp >::Interval_t = Interval<Set_traits_t>

◆ Memory_resource_t

template<Is_boundary_container Boundary_container_tp>

using mysql::sets::Interval_container< Boundary_container_tp >::Memory_resource_t = mysql::allocators::Memory_resource

◆ Storage_t

template<Is_boundary_container Boundary_container_tp>

using mysql::sets::Interval_container< Boundary_container_tp >::Storage_t = Storage_or_void<Boundary_container_t>

◆ This_t

template<Is_boundary_container Boundary_container_tp>

using mysql::sets::Interval_container< Boundary_container_tp >::This_t = Interval_container<Boundary_container_t>

Constructor & Destructor Documentation

◆ Interval_container() [1/6]

template<Is_boundary_container Boundary_container_tp>

mysql::sets::Interval_container< Boundary_container_tp >::Interval_container ( )

defaultnoexcept

Default constructor.

◆ Interval_container() [2/6]

template<Is_boundary_container Boundary_container_tp>

mysql::sets::Interval_container< Boundary_container_tp >::Interval_container ( const Interval_container< Boundary_container_tp > & source )

default

Copy constructor.

This copy constructor is only enabled when the underlying boundary container is throwing. For non-throwing containers, use the default constructor followed by the assign member function instead.

Exceptions

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

◆ Interval_container() [3/6]

template<Is_boundary_container Boundary_container_tp>

mysql::sets::Interval_container< Boundary_container_tp >::Interval_container ( Interval_container< Boundary_container_tp > && source )

defaultnoexcept

Move constructor, defaulted.

◆ ~Interval_container()

template<Is_boundary_container Boundary_container_tp>

mysql::sets::Interval_container< Boundary_container_tp >::~Interval_container ( )

defaultnoexcept

Destructor.

This is defaulted, so it will just invoke the destructor for m_boundaries.

◆ Interval_container() [4/6]

template<Is_boundary_container Boundary_container_tp>

mysql::sets::Interval_container< Boundary_container_tp >::Interval_container ( const Memory_resource_t & memory_resource )

inlineexplicitnoexcept

Construct an empty container using the specified Memory_resource.

◆ Interval_container() [5/6]

template<Is_boundary_container Boundary_container_tp>

mysql::sets::Interval_container< Boundary_container_tp >::Interval_container ( const Is_interval_set_over_traits< Set_traits_t > auto & source )

inlineexplicit

Construct by copying any other Interval_set over the same boundary traits.

This copy constructor is only enabled when the underlying boundary container is copy-constructible, i.e., when it is throwing. For non-throwing containers, use the default constructor followed by the assign member function instead.

Exceptions

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

◆ Interval_container() [6/6]

template<Is_boundary_container Boundary_container_tp>

mysql::sets::Interval_container< Boundary_container_tp >::Interval_container	(	const Is_interval_set_over_traits< Set_traits_t > auto &	source,
		const Memory_resource_t &	memory_resource
	)

inlineexplicit

Construct by copying any other Interval_set over the same boundary traits.

This copy constructor is only enabled when the underlying boundary container is copy-constructible, i.e., when it is throwing. For non-throwing containers, use the default constructor followed by the assign member function instead.

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()

template<Is_boundary_container Boundary_container_tp>

template<Is_interval_set_over_traits_unqualified< Set_traits_t > Source_t>

auto mysql::sets::Interval_container< Boundary_container_tp >::assign ( Source_t && source )

Overwrite this object with source (copy-assigned).

This is equivalent to the copy assignment operator, and provided only in order for uniformity of this API and the non-throwing API.

If the boundary underlying set cannot fail (e.g. the argument is an rvalue reference to a type satisfying Can_donate_set), this returns void and does not throw. Otherwise, out-of-memory conditions may be possible. Then, if an out-of-memory condition occurred while inserting the interval, this returns error or throws bad_alloc according to the underlying boundary container. If the out-of-memory condition occurs when the operation is half-completed, it may leave the container as a subset of source.

◆ boundaries() [1/3]

template<Is_boundary_container Boundary_container_tp>

auto && mysql::sets::Interval_container< Boundary_container_tp >::boundaries ( ) &&

inlinenoexcept

Return an rvalue reference to the underlying boundary container.

The caller may modify the container through that reference, which will affect this interval container.

◆ boundaries() [2/3]

template<Is_boundary_container Boundary_container_tp>

auto & mysql::sets::Interval_container< Boundary_container_tp >::boundaries ( ) &

inlinenoexcept

Return an lvalue reference to the underlying boundary container.

The caller may modify the container through that reference, which will affect this interval container.

◆ boundaries() [3/3]

template<Is_boundary_container Boundary_container_tp>

const auto & mysql::sets::Interval_container< Boundary_container_tp >::boundaries ( ) const &

inlinenoexcept

Return a const lvalue reference to the underlying boundary container.

◆ clear()

template<Is_boundary_container Boundary_container_tp>

void mysql::sets::Interval_container< Boundary_container_tp >::clear ( )

inlinenoexcept

Make this container empty.

This function cannot fail.

◆ get_memory_resource()

template<Is_boundary_container Boundary_container_tp>

decltype(auto) mysql::sets::Interval_container< Boundary_container_tp >::get_memory_resource ( ) const

inlinenoexcept

Return the Memory_resource object that manages memory in this object, or a default-constructed Memory_resource if there is none.

◆ inplace_intersect() [1/2]

template<Is_boundary_container Boundary_container_tp>

void mysql::sets::Interval_container< Boundary_container_tp >::inplace_intersect ( const Interval_t & interval )

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.

Algorithm and complexity:

See also: inplace_union.

Parameters

interval The interval to intersect with.

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

◆ inplace_intersect() [2/2]

template<Is_boundary_container Boundary_container_tp>

template<Is_interval_set_over_traits_unqualified< Set_traits_t > Interval_set_t>

auto mysql::sets::Interval_container< Boundary_container_tp >::inplace_intersect ( Interval_set_t && interval_set )

In-place intersect this container with the given set.

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

interval_set The interval set.

If an out-of-memory condition occurred while splitting an interval, this returns error or throws bad_alloc according to the underlying boundary container. 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_subtract() [1/3]

template<Is_boundary_container Boundary_container_tp>

auto mysql::sets::Interval_container< Boundary_container_tp >::inplace_subtract	(	Boundary_iterator_t &	cursor,
		const Interval_t &	interval
	)

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 position.

See also: Boundary_container::inplace_subtract.

Parameters

interval The interval to remove.

If an out-of-memory condition occurred while splitting an interval, this returns error or throws bad_alloc according to the underlying boundary container. This leaves the container unmodified.

◆ inplace_subtract() [2/3]

template<Is_boundary_container Boundary_container_tp>

auto mysql::sets::Interval_container< Boundary_container_tp >::inplace_subtract ( const Interval_t & interval )

Subtract the given interval.

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

interval The interval to remove.

If an out-of-memory condition occurred while splitting an interval, this returns error or throws bad_alloc according to the underlying boundary container. This leaves the container unmodified.

◆ inplace_subtract() [3/3]

template<Is_boundary_container Boundary_container_tp>

template<Is_interval_set_over_traits_unqualified< Set_traits_t > Interval_set_t>

auto mysql::sets::Interval_container< Boundary_container_tp >::inplace_subtract ( Interval_set_t && interval_set )

In-place subtract intervals of the given set 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

interval_set The interval set.

If an out-of-memory condition occurred while splitting an interval, this returns error or throws bad_alloc according to the underlying boundary container. 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_union() [1/3]

template<Is_boundary_container Boundary_container_tp>

auto mysql::sets::Interval_container< Boundary_container_tp >::inplace_union	(	Boundary_iterator_t &	cursor,
		const Interval_t &	interval
	)

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

This may merge intervals that are overlapping or adjacent with the given interval.

Parameters

[in,out] cursor Hint for the position.

See also: Boundary_container::inplace_union.

Parameters

interval The interval to insert.

If an out-of-memory condition occurred while inserting an interval, this returns error or throws bad_alloc according to the underlying boundary container. This leaves the container unmodified.

◆ inplace_union() [2/3]

template<Is_boundary_container Boundary_container_tp>

auto mysql::sets::Interval_container< Boundary_container_tp >::inplace_union ( const Interval_t & interval )

Insert the given interval (inplace union).

This may merge intervals that are overlapping or adjacent with the given interval.

Parameters

interval The interval to insert.

If an out-of-memory condition occurred while inserting an interval, this returns error or throws bad_alloc according to the underlying boundary container. This leaves the container unmodified.

◆ inplace_union() [3/3]

template<Is_boundary_container Boundary_container_tp>

template<Is_interval_set_over_traits_unqualified< Set_traits_t > Interval_set_t>

auto mysql::sets::Interval_container< Boundary_container_tp >::inplace_union ( Interval_set_t && interval_set )

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

This may merge intervals that are overlapping or adjacent.

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

If the underlying storage supports fast insertion in the middle (e.g. set or list), then it uses a true in-place algorithm, possibly adjusting 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 storage:

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

Parameters

interval_set The interval set.

If an out-of-memory condition occurred while inserting an interval, this returns error or throws bad_alloc according to the underlying boundary container. 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.

◆ insert()

template<Is_boundary_container Boundary_container_tp>

auto mysql::sets::Interval_container< Boundary_container_tp >::insert ( const Element_t & element )

Insert the given element (inplace union).

This may merge adjacent intervals.

Parameters

element The element to insert.

If an out-of-memory condition occurred while inserting the interval, this returns error or throws bad_alloc according to the underlying boundary container. This leaves the container unmodified.

We use [[nodiscard]] rather than [[nodiscard]], because nodiscard gives a warning even if auto resolves to void, whereas nodiscard does not.

◆ operator=() [1/3]

template<Is_boundary_container Boundary_container_tp>

Interval_container & mysql::sets::Interval_container< Boundary_container_tp >::operator= ( const Interval_container< Boundary_container_tp > & source )

default

Copy assignment operator.

This copy assignment operator is only enabled when the underlying boundary container is throwing. For non-throwing containers, use assign instead.

Exceptions

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

◆ operator=() [2/3]

template<Is_boundary_container Boundary_container_tp>

Interval_container & mysql::sets::Interval_container< Boundary_container_tp >::operator= ( const Is_interval_set_over_traits< Set_traits_t > auto & source )

inline

Assign from any other Boundary_set over the same Set traits.

This copy assignment operator is only enabled when the underlying boundary container is copy-constructible, i.e., when it is throwing. For non-throwing containers, use assign instead.

Exceptions

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

◆ operator=() [3/3]

template<Is_boundary_container Boundary_container_tp>

Interval_container & mysql::sets::Interval_container< Boundary_container_tp >::operator= ( Interval_container< Boundary_container_tp > && source )

defaultnoexcept

Move assignment operator, defaulted.

◆ remove()

template<Is_boundary_container Boundary_container_tp>

auto mysql::sets::Interval_container< Boundary_container_tp >::remove ( const Element_t & element )

Remove the given element (inplace subtraction).

This may truncate and/or split an interval that overlaps with the subtracted interval.

Parameters

element The element to remove.

If an out-of-memory condition occurred while splitting an interval, this returns error or throws bad_alloc according to the underlying boundary container. This leaves the container unmodified.

Member Data Documentation

◆ has_fast_insertion

template<Is_boundary_container Boundary_container_tp>

constexpr bool mysql::sets::Interval_container< Boundary_container_tp >::has_fast_insertion

staticconstexpr

Initial value:

=

Boundary_container_t::has_fast_insertion

◆ m_boundaries

template<Is_boundary_container Boundary_container_tp>

Boundary_container_t mysql::sets::Interval_container< Boundary_container_tp >::m_boundaries

private

◆ noexcept_insertions

template<Is_boundary_container Boundary_container_tp>

constexpr bool mysql::sets::Interval_container< Boundary_container_tp >::noexcept_insertions

staticconstexprprivate

Initial value:

= noexcept(

std::declval<Boundary_container_t>().insert(std::declval<Element_t>()))

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

libs/mysql/sets/interval_container.h

Public Types

Public Member Functions

Static Public Attributes

Private Types

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Allocator_t

◆ Base_t

◆ Boundary_container_t

◆ Boundary_iterator_t

◆ Interval_t

◆ Memory_resource_t

◆ Storage_t

◆ This_t

Constructor & Destructor Documentation

◆ Interval_container() [1/6]

◆ Interval_container() [2/6]

◆ Interval_container() [3/6]

◆ ~Interval_container()

◆ Interval_container() [4/6]

◆ Interval_container() [5/6]

◆ Interval_container() [6/6]

Member Function Documentation

◆ assign()

◆ boundaries() [1/3]

◆ boundaries() [2/3]

◆ boundaries() [3/3]

◆ clear()

◆ get_memory_resource()

◆ inplace_intersect() [1/2]

◆ inplace_intersect() [2/2]

◆ inplace_subtract() [1/3]

◆ inplace_subtract() [2/3]

◆ inplace_subtract() [3/3]

◆ inplace_union() [1/3]

◆ inplace_union() [2/3]

◆ inplace_union() [3/3]

◆ insert()

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ remove()

Member Data Documentation

◆ has_fast_insertion

◆ m_boundaries

◆ noexcept_insertions