PLaSK library

Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Public Attributes | Friends | List of all members
plask::CompressedSetOfNumbers< number_t > Struct Template Reference

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

`#include <plask/utils/numbers_set.hpp>`

Collaboration diagram for plask::CompressedSetOfNumbers< number_t >:
[legend]

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