Sorted, compressed, indexed set of numbers. More...

#include <plask/utils/numbers_set.hpp>

Collaboration diagram for plask::CompressedSetOfNumbers< number_t >:

Classes
class	const_iterator

struct	ConstIteratorFacade
	Facade which help to develop iterators over CompressedSetOfNumbers. More...

struct	Segment

Public Types
enum	: std::size_t { NOT_INCLUDED = std::numeric_limits<std::size_t>::max() }
	Constant returned by indexOf method for numbers not included in the set. More...

typedef const_iterator	iterator

Public Member Functions
	CompressedSetOfNumbers ()=default

	CompressedSetOfNumbers (const std::initializer_list< number_t > &sorted_list)

number_t	sizeOfSegment (typename std::vector< Segment >::const_iterator it) const

number_t	firstIndex (typename std::vector< Segment >::const_iterator it) const
	Get the first index in the segment pointed by `it`.

number_t	firstNumber (typename std::vector< Segment >::const_iterator it) const
	Get the first number in the segment pointed by `it`.

const_iterator	begin () const

const_iterator	end () const

std::size_t	size () const
	Get number of items (numbers) included in the set.

void	shrink_to_fit ()
	Requests the vector of segments to reduce its capacity to fit its size.

void	reserve (std::size_t n)
	Requests that the vector of segments capacity be at least enough to contain `n` elements.

void	clear ()
	Removes all numbers from the set, leaving it empty.

std::size_t	segmentsCount () const
	Get number of segments, which is usable only for informative purposes and tests.

bool	empty () const
	Check if the set is empty.

number_t	operator[] (std::size_t index) const
	Get number at a given `index` in the set, without checking if the `index` is valid.

number_t	at (std::size_t index) const
	Get number at a given `index` or throw exception if the `index` is not valid.

std::size_t	indexOf (number_t number) const
	Get index of a given `number` in the set.

bool	includes (number_t number) const
	Check if given `number` is included in the set.

void	push_back (number_t number)
	Quickly append a number to the end of the set.

void	push_back_segment (number_t num_beg, number_t num_end)
	Quickly append a segment to the end of the set.

void	push_back_range (number_t num_beg, number_t num_end)
	Append range [num_beg, num_end) to the end of the set.

void	assignRange (number_t num_beg, number_t num_end)
	Assign a range [num_beg, num_end) to *this.

void	assignRange (number_t num_end)
	Assign a range [0, num_end) to *this.

void	insert (number_t number)
	Insert `number` to the set.

bool	operator== (const CompressedSetOfNumbers< number_t > &other) const

bool	operator!= (const CompressedSetOfNumbers< number_t > &other) const

CompressedSetOfNumbers< number_t >	intersection (const CompressedSetOfNumbers< number_t > &other) const
	Calculate an intersection of this and the `other`.

template<typename F >
void	forEachSegment (F f) const
	Call f(first, last) for each segment [first, last).

CompressedSetOfNumbers< number_t >	shiftedLeft (number_t positions_count) const
	Calculate a set with numbers of `this` decreased by `positions_count`.

template<typename F >
CompressedSetOfNumbers< number_t >	transformed (F f) const
	Calculate a transformed version of `this`.

Public Attributes
std::vector< Segment >	segments

Friends
std::ostream &	operator<< (std::ostream &out, const CompressedSetOfNumbers< number_t > &set)

Detailed Description

template<typename number_t = std::size_t>
struct plask::CompressedSetOfNumbers< number_t >

Sorted, compressed, indexed set of numbers.

Set is stored as a sorted vector of segments, each represents a sequence of successive numbers.

Definition at line 32 of file numbers_set.hpp.

Member Typedef Documentation

◆ iterator

template<typename number_t = std::size_t>

typedef const_iterator plask::CompressedSetOfNumbers< number_t >::iterator

Definition at line 183 of file numbers_set.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<typename number_t = std::size_t>

anonymous enum : std::size_t

Constant returned by indexOf method for numbers not included in the set.

Enumerator
NOT_INCLUDED

Definition at line 1 of file numbers_set.hpp.

Constructor & Destructor Documentation

◆ CompressedSetOfNumbers() [1/2]

template<typename number_t = std::size_t>

plask::CompressedSetOfNumbers< number_t >::CompressedSetOfNumbers ( )

default

◆ CompressedSetOfNumbers() [2/2]

template<typename number_t = std::size_t>

plask::CompressedSetOfNumbers< number_t >::CompressedSetOfNumbers ( const std::initializer_list< number_t > & sorted_list )

inline

Definition at line 62 of file numbers_set.hpp.

Member Function Documentation

◆ assignRange() [1/2]

template<typename number_t = std::size_t>

void plask::CompressedSetOfNumbers< number_t >::assignRange	(	number_t	num_beg,
		number_t	num_end
	)

inline

Assign a range [num_beg, num_end) to *this.

Parameters

num_beg,num_end the range to assign

Definition at line 340 of file numbers_set.hpp.

◆ assignRange() [2/2]

template<typename number_t = std::size_t>

void plask::CompressedSetOfNumbers< number_t >::assignRange ( number_t num_end )

inline

Assign a range [0, num_end) to *this.

Parameters

num_end end of the range to assign

Definition at line 350 of file numbers_set.hpp.

◆ at()

template<typename number_t = std::size_t>

number_t plask::CompressedSetOfNumbers< number_t >::at ( std::size_t index ) const

inline

Get number at a given index or throw exception if the index is not valid.

Time complexity: logarithmic in number of segments (which never exceed the size of the set).

Parameters

index index in the set, it is valid if it is included in range [0, size())

Returns: number at index

Definition at line 255 of file numbers_set.hpp.

◆ begin()

template<typename number_t = std::size_t>

const_iterator plask::CompressedSetOfNumbers< number_t >::begin ( ) const

inline

Definition at line 185 of file numbers_set.hpp.

◆ clear()

template<typename number_t = std::size_t>

void plask::CompressedSetOfNumbers< number_t >::clear ( )

inline

Removes all numbers from the set, leaving it empty.

Definition at line 216 of file numbers_set.hpp.

◆ empty()

template<typename number_t = std::size_t>

bool plask::CompressedSetOfNumbers< number_t >::empty ( ) const

inline

Check if the set is empty.

Time complexity: constant.

Returns: true only if the set is empty

Definition at line 232 of file numbers_set.hpp.

◆ end()

template<typename number_t = std::size_t>

const_iterator plask::CompressedSetOfNumbers< number_t >::end ( ) const

inline

Definition at line 186 of file numbers_set.hpp.

◆ firstIndex()

template<typename number_t = std::size_t>

number_t plask::CompressedSetOfNumbers< number_t >::firstIndex ( typename std::vector< Segment >::const_iterator it ) const

inline

Get the first index in the segment pointed by it.

Parameters

it	iterator to segment

Returns: the first index in the segment *it

Definition at line 79 of file numbers_set.hpp.

◆ firstNumber()

template<typename number_t = std::size_t>

number_t plask::CompressedSetOfNumbers< number_t >::firstNumber ( typename std::vector< Segment >::const_iterator it ) const

inline

Get the first number in the segment pointed by it.

Parameters

it	iterator to segment

Returns: first number in the segment *it

Definition at line 88 of file numbers_set.hpp.

◆ forEachSegment()

template<typename number_t = std::size_t>

template<typename F >

void plask::CompressedSetOfNumbers< number_t >::forEachSegment ( F f ) const

inline

Call f(first, last) for each segment [first, last).

Parameters

f	two-argument functor

Definition at line 472 of file numbers_set.hpp.

◆ includes()

template<typename number_t = std::size_t>

bool plask::CompressedSetOfNumbers< number_t >::includes ( number_t number ) const

inline

Check if given number is included in the set.

Parameters

number item to find

Returns: true only if the set includes the number

Definition at line 286 of file numbers_set.hpp.

◆ indexOf()

template<typename number_t = std::size_t>

std::size_t plask::CompressedSetOfNumbers< number_t >::indexOf ( number_t number ) const

inline

Get index of a given number in the set.

Time complexity: logarithmic in number of segments (which never exceed the size of the set).

Parameters

number item to find

Returns: either index of number in the set or NOT_INCLUDED if it is not included

Definition at line 272 of file numbers_set.hpp.

◆ insert()

template<typename number_t = std::size_t>

void plask::CompressedSetOfNumbers< number_t >::insert ( number_t number )

inline

Insert number to the set.

Time complexity: logarithmic (optimistic, e.g. if number is already in the set or is inserted near the end) or linear (pesymistic) in number of segments.

Parameters

number number to insert

Definition at line 362 of file numbers_set.hpp.

◆ intersection()

template<typename number_t = std::size_t>

CompressedSetOfNumbers< number_t > plask::CompressedSetOfNumbers< number_t >::intersection ( const CompressedSetOfNumbers< number_t > & other ) const

inline

Calculate an intersection of this and the other.

Time complexity: O(number of segments in this + number of segments in other)

Parameters

other set

Returns: intersection of this and the other

Definition at line 448 of file numbers_set.hpp.

◆ operator!=()

template<typename number_t = std::size_t>

bool plask::CompressedSetOfNumbers< number_t >::operator!= ( const CompressedSetOfNumbers< number_t > & other ) const

inline

Definition at line 416 of file numbers_set.hpp.

◆ operator==()

template<typename number_t = std::size_t>

bool plask::CompressedSetOfNumbers< number_t >::operator== ( const CompressedSetOfNumbers< number_t > & other ) const

inline

Definition at line 412 of file numbers_set.hpp.

◆ operator[]()

template<typename number_t = std::size_t>

number_t plask::CompressedSetOfNumbers< number_t >::operator[] ( std::size_t index ) const

inline

Get number at a given index in the set, without checking if the index is valid.

Time complexity: logarithmic in number of segments (which never exceed the size of the set).

Parameters

index index in the set, must be in range [0, size())

Returns: number at index

Definition at line 241 of file numbers_set.hpp.

◆ push_back()

template<typename number_t = std::size_t>

void plask::CompressedSetOfNumbers< number_t >::push_back ( number_t number )

inline

Quickly append a number to the end of the set.

Time complexity: amortized constant.

Parameters

number number to add, must be larger than all numbers already included in the set

Definition at line 296 of file numbers_set.hpp.

◆ push_back_range()

template<typename number_t = std::size_t>

void plask::CompressedSetOfNumbers< number_t >::push_back_range	(	number_t	num_beg,
		number_t	num_end
	)

inline

Append range [num_beg, num_end) to the end of the set.

Time complexity: amortized constant.

Parameters

num_beg,num_end range [num_beg, num_end) to append; num_beg must be larger than all numbers already included in the set

Definition at line 325 of file numbers_set.hpp.

◆ push_back_segment()

template<typename number_t = std::size_t>

void plask::CompressedSetOfNumbers< number_t >::push_back_segment	(	number_t	num_beg,
		number_t	num_end
	)

inline

Quickly append a segment to the end of the set.

Time complexity: amortized constant.

Parameters

num_beg,num_end range [num_beg, num_end) to append; must be non-empty; num_beg-1 must be larger than all numbers already included in the set

Definition at line 312 of file numbers_set.hpp.

◆ reserve()

template<typename number_t = std::size_t>

void plask::CompressedSetOfNumbers< number_t >::reserve ( std::size_t n )

inline

Requests that the vector of segments capacity be at least enough to contain n elements.

If n is greater than the current vector capacity, the function causes the container to reallocate its storage increasing its capacity to n (or greater). In all other cases, the function call does not cause a reallocation and the vector capacity is not affected.

Parameters

n	minimum capacity for the vector of segments

Definition at line 213 of file numbers_set.hpp.

◆ segmentsCount()

template<typename number_t = std::size_t>

std::size_t plask::CompressedSetOfNumbers< number_t >::segmentsCount ( ) const

inline

Get number of segments, which is usable only for informative purposes and tests.

Time complexity: constant.

Returns: number of segments

Definition at line 224 of file numbers_set.hpp.

◆ shiftedLeft()

template<typename number_t = std::size_t>

CompressedSetOfNumbers< number_t > plask::CompressedSetOfNumbers< number_t >::shiftedLeft ( number_t positions_count ) const

inline

Calculate a set with numbers of this decreased by positions_count.

Skip numbers which became negative.

Time complexity: linear in number of segments.

Parameters

positions_count number of positions to shift

Returns: set with numbers of this decreased by positions_count (numbers which became negative are skipped)

Definition at line 484 of file numbers_set.hpp.

◆ shrink_to_fit()

template<typename number_t = std::size_t>

void plask::CompressedSetOfNumbers< number_t >::shrink_to_fit ( )

inline

Requests the vector of segments to reduce its capacity to fit its size.

The request is non-binding, and the container implementation is free to optimize otherwise and leave the vector with a capacity greater than its size.

Definition at line 203 of file numbers_set.hpp.

◆ size()

template<typename number_t = std::size_t>

std::size_t plask::CompressedSetOfNumbers< number_t >::size ( ) const

inline

Get number of items (numbers) included in the set.

Time complexity: constant.

Returns: number of numbers included in the set

Definition at line 196 of file numbers_set.hpp.

◆ sizeOfSegment()

template<typename number_t = std::size_t>

number_t plask::CompressedSetOfNumbers< number_t >::sizeOfSegment ( typename std::vector< Segment >::const_iterator it ) const

inline

Definition at line 70 of file numbers_set.hpp.

◆ transformed()

template<typename number_t = std::size_t>

template<typename F >

CompressedSetOfNumbers< number_t > plask::CompressedSetOfNumbers< number_t >::transformed ( F f ) const

inline

Calculate a transformed version of this.

Call f(first, last) for each successive segment [first, last) of this. Function f can change its arguments and this changed range is appended to the end of the resulted set.

Time complexity: linear in number of segments.

Parameters

f	functor which take two number_t& as arguments

Returns: the transformed version of this

Definition at line 506 of file numbers_set.hpp.

Friends And Related Symbol Documentation

◆ operator<<

template<typename number_t = std::size_t>

std::ostream & operator<<	(	std::ostream &	out,
		const CompressedSetOfNumbers< number_t > &	set
	)

friend

Definition at line 395 of file numbers_set.hpp.

Member Data Documentation

◆ segments

template<typename number_t = std::size_t>

std::vector<Segment> plask::CompressedSetOfNumbers< number_t >::segments

Definition at line 58 of file numbers_set.hpp.

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

plask/utils/numbers_set.hpp

Classes

Public Types

Public Member Functions

Public Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ iterator

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ CompressedSetOfNumbers() [1/2]

◆ CompressedSetOfNumbers() [2/2]

Member Function Documentation

◆ assignRange() [1/2]

◆ assignRange() [2/2]

◆ at()

◆ begin()

◆ clear()

◆ empty()

◆ end()

◆ firstIndex()

◆ firstNumber()

◆ forEachSegment()

◆ includes()

◆ indexOf()

◆ insert()

◆ intersection()

◆ operator!=()

◆ operator==()

◆ operator[]()

◆ push_back()

◆ push_back_range()

◆ push_back_segment()

◆ reserve()

◆ segmentsCount()

◆ shiftedLeft()

◆ shrink_to_fit()

◆ size()

◆ sizeOfSegment()

◆ transformed()

Friends And Related Symbol Documentation

◆ operator<<

Member Data Documentation

◆ segments