lar::sparse_vector< T > Class Template Reference

A sparse vector. More...

#include <sparse_vector.h>

Classes
class	const_datarange_t
	A constant reference to a data range. More...
class	const_iterator
	Iterator to the sparse vector values. More...
class	const_reference
	Special little box to allow void elements to be treated as references. More...
class	datarange_t
	Range class, with range and data. More...
class	iterator
	Iterator to the sparse vector values. More...
class	reference
	A class representing a cell in a sparse vector. More...

Public Types
typedef T	value_type
	type of the stored values More...
typedef std::vector< value_type >	vector_t
	type of STL vector holding this data More...
typedef vector_t::size_type	size_type
	size type More...
typedef vector_t::difference_type	difference_type
	index difference type More...
typedef vector_t::pointer	pointer
typedef vector_t::const_pointer	const_pointer
typedef std::vector< datarange_t >	range_list_t
	type of sparse vector data More...
typedef range_list_t::iterator	range_iterator
	type of iterator over ranges More...
typedef range_list_t::const_iterator	range_const_iterator
	type of constant iterator over ranges More...

Public Member Functions
	sparse_vector ()
	Default constructor: an empty vector. More...
	sparse_vector (size_type new_size)
	Constructor: a vector with new_size elements in the void. More...
	sparse_vector (const vector_t &from, size_type offset=0)
	Constructor: a solid vector from an existing STL vector. More...
	sparse_vector (sparse_vector const &)=default
	Copy constructor: default. More...
	sparse_vector (sparse_vector &&from)
	Move constructor. More...
sparse_vector &	operator= (sparse_vector const &)=default
	Copy assignment: default. More...
sparse_vector &	operator= (sparse_vector &&from)
	Move assignment. More...
	sparse_vector (vector_t &&from, size_type offset=0)
	Constructor: a solid vector from an existing STL vector. More...
	~sparse_vector ()=default
	Destructor: default. More...
void	clear ()
	Removes all the data, making the vector empty. More...
size_type	size () const
	Returns the size of the vector. More...
bool	empty () const
	Returns whether the vector is empty. More...
size_type	capacity () const
	Returns the capacity of the vector (compatibility only) More...
value_type	operator[] (size_type index) const
	Access to an element (read only) More...
reference	operator[] (size_type index)
	Access to an element (read/write for non-void elements only!) More...
auto	range_const_data (std::size_t i) const
	Like range_data() but with explicitly read-only access to data. More...
range_const_iterator	begin_range () const
	Returns a constant iterator to the first data range. More...
range_const_iterator	end_range () const
	Returns a constant iterator to after the last data range. More...
std::size_t	find_range_number (size_type index) const
	Returns the number (0-based) of range containing index. More...
datarange_t	make_void_around (size_type index)
	Casts the whole range with the specified item into the void. More...
bool	is_valid () const
	Returns if the vector is in a valid state. More...
void	make_void (iterator first, iterator last)
	Makes all the elements from first and before last void. More...
template<typename ITER >
const lar::sparse_vector< T > ::datarange_t &	add_range (size_type offset, ITER first, ITER last)
template<typename ITER , typename OP >
auto	combine_range (size_type offset, ITER first, ITER last, OP &&op, value_type void_value) -> const datarange_t &
void	resize (size_type new_size)
	Resizes the vector to the specified size, adding void. More...
void	resize (size_type new_size, value_type def_value)
	Resizes the vector to the specified size, adding def_value. More...
iterator	begin ()
	Standard iterators interface. More...
iterator	end ()
const_iterator	begin () const
const_iterator	end () const
const_iterator	cbegin () const
const_iterator	cend () const
Cell test
The methods in this group test the single vector cells.
bool	is_void (size_type index) const
	Returns whether the specified position is void. More...
bool	back_is_void () const
	Returns whether the sparse vector ends with void. More...
size_type	count () const
	Returns the number of non-void cells. More...
Cell set
The methods in this group access and/or change the cell values.
value_type &	set_at (size_type index, value_type value)
	Writes into an element (creating or expanding a range if needed) More...
void	unset_at (size_type index)
	Casts the element with the specified index into the void. More...
void	push_back (value_type value)
void	push_back (value_type value, value_type thr)
	Adds one element to the end of the vector (if zero, just adds void) More...
template<typename ITER >
void	assign (ITER first, ITER last)
	Copies data from a sequence between two iterators. More...
template<typename CONT >
void	assign (const CONT &new_data)
	Copies data from a container. More...
void	assign (vector_t &&new_data)
	Moves data from a vector. More...
Ranges
A range is a contiguous region of the sparse vector which contains all non-void values. A sparse vector is effectively a sorted collection of ranges. This interface allows: iteration through all ranges (read only) random access to a range by index (read only) access to the data of a selected range (read/write) look-up of the range containing a specified index (read/write; use write with care!) addition (and more generically, combination with existing data) of a new range extension of the sparse vector by appending a range at the end of it remove the data of a range, making it void
const range_list_t &	get_ranges () const
	Returns the internal list of non-void ranges. More...
auto	iterate_ranges () -> decltype(auto)
size_type	n_ranges () const
	Returns the internal list of non-void ranges. More...
const datarange_t &	range (size_t i) const
	Returns the i-th non-void range (zero-based) More...
auto	range_data (std::size_t i)
	Provides direct access to data of i-th non-void range (zero-based) More...
auto	range_data (std::size_t const i) const
range_const_iterator	find_range_iterator (size_type index) const
	Returns an iterator to the range containing the specified index. More...
range_iterator	find_range_iterator (size_type index)
const datarange_t &	find_range (size_type index) const
	Returns the range containing the specified index. More...
datarange_t &	find_range (size_type index)
template<typename ITER >
const datarange_t &	add_range (size_type offset, ITER first, ITER last)
	Adds a sequence of elements as a range with specified offset. More...
template<typename CONT >
const datarange_t &	add_range (size_type offset, const CONT &new_data)
	Copies the elements in container to a range with specified offset. More...
const datarange_t &	add_range (size_type offset, vector_t &&new_data)
	Adds a sequence of elements as a range with specified offset. More...
template<typename ITER , typename OP >
const datarange_t &	combine_range (size_type offset, ITER first, ITER last, OP &&op, value_type void_value=value_zero)
	Combines a sequence of elements as a range with data at offset. More...
template<typename CONT , typename OP >
const datarange_t &	combine_range (size_type offset, const CONT &other, OP &&op, value_type void_value=value_zero)
	Combines the elements in container with the data at offset. More...
template<typename ITER >
const datarange_t &	append (ITER first, ITER last)
	Adds a sequence of elements as a range at the end of the vector. More...
template<typename CONT >
const datarange_t &	append (const CONT &range_data)
	Adds a sequence of elements as a range at the end of the vector. More...
const datarange_t &	append (vector_t &&range_data)
	Adds a sequence of elements as a range at the end of the vector. More...
datarange_t	void_range (range_iterator const iRange)
	Turns the specified range into void. More...
datarange_t	void_range (std::size_t const iRange)
bool	optimize ()
	Performs internal optimization, returns whether the object was changed. More...
bool	optimize (size_t)

Static Public Member Functions
Static members related to data size and optimization
static size_t	expected_vector_size (size_t size)
	Returns the expected size taken by a vector of specified size. More...
static size_t	min_gap ()
	Minimum optimal gap between ranges (a guess) More...
static bool	should_merge (const typename datarange_t::base_t &a, const typename datarange_t::base_t &b)
	Returns if merging the two specified ranges would save memory. More...

Protected Member Functions
size_type	minimum_size () const
	Returns the size determined by the ranges already present. More...
const datarange_t &	add_range_before (size_type offset, vector_t &&new_data, range_iterator nextRange)
	Implementation detail of add_range(), with where to add the range. More...
range_iterator	eat_range_head (range_iterator iRange, size_t index)
	Voids the starting elements up to index (excluded) of a given range. More...
datarange_t &	merge_ranges (range_iterator iRange)
	Merges all the following contiguous ranges. More...
size_type	fix_size ()
	Extends the vector size according to the last range. More...
range_iterator	find_next_range_iter (size_type index)
	Returns an iterator to the range after index. More...
range_const_iterator	find_next_range_iter (size_type index) const
range_iterator	find_next_range_iter (size_type index, range_iterator rbegin)
	Returns an iterator to the range after index, or ranges.end() if none. More...
range_const_iterator	find_next_range_iter (size_type index, range_const_iterator rbegin) const
range_iterator	find_range_iter_at_or_after (size_type index)
	Returns an iterator to the range at or after index. More...
range_const_iterator	find_range_iter_at_or_after (size_type index) const
range_iterator	find_extending_range_iter (size_type index)
	Returns an iterator to the range no earlier than index, or end() if none. More...
range_const_iterator	find_extending_range_iter (size_type index) const
range_iterator	find_extending_range_iter (size_type index, range_iterator rbegin)
	Returns an iterator to the range that contains the first non-void element after index, or end() if none. More...
range_const_iterator	find_extending_range_iter (size_type index, range_const_iterator rbegin) const
range_iterator	insert_range (range_iterator iInsert, const datarange_t &data)
	Plug a new data range in the specified position; no check performed. More...
range_iterator	insert_range (range_iterator iInsert, datarange_t &&data)

Protected Attributes
size_type	nominal_size
	current size More...
range_list_t	ranges
	list of ranges More...

Private Types
typedef sparse_vector< T >	this_t

Static members for dealing with this type of value
static constexpr value_type	value_zero {0}
	a representation of 0 More...
static value_type	abs (value_type v)
	Returns the module of the specified value. More...
static value_type	is_zero (value_type v)
	Returns whether the value is exactly zero. More...
static value_type	is_zero (value_type v, value_type thr)
	Returns whether the value is zero below a given threshold. More...
static value_type	is_equal (value_type a, value_type b)
	Returns whether two values are the same. More...
static value_type	is_equal (value_type a, value_type b, value_type thr)
	Returns whether two values are the same below a given threshold. More...

Detailed Description

template<typename T>
class lar::sparse_vector< T >

A sparse vector.

---

Template Parameters

T	type of data stored in the vector

Todo:

backward iteration; reverse iterators; iterator on non-void elements only; iterator on non-void elements only, returning a pair (index;value)

A sparse_vector is a container of items marked by consecutive indices (that is, a vector like std::vector), where only non-zero elements are actually stored. The implementation is a container of ranges of non-zero consecutive values; the zero elements are effectively not stored in the object, and a zero is returned whenever they are accessed. In the following, the regions of zeros between the non-zero ranges are collectively called "the void".

See sparse_vector_test.cc for examples of usage.

Although some level of dynamic assignment is present, the class is not very flexible and it is best assigned just once, by adding ranges (add_range(); or by push_back(), which is less efficient). While this class mimics a good deal of the STL vector interface, it is not a std::vector and it does not support all the tricks of it.

For the following, let's assume:

lar::sparse_vector<double> sv;
std::vector<double> buffer;

Supported usage

for (const auto& value: sv) std::cout << " " << value;

lar::sparse_vector<double>::const_iterator iValue = sv.cbegin(), vend = sv.cend();
while (iSV != sv.end()) std::cout << " " << *(iSV++);

for (auto value: sv) { ... }

Common iteration on all elements. Better to do a constant one. The first two examples print the full content of the sparse vector, void included.

---

sv[10] = 3.;

Assign to an existing (not void) element. Assigning to void elements is not supported, and there is no way to make an existing element to become void (assigning 0 will yield to an existing element with value 0).

---

sv.set_at(10, 3.);

Assign a value to an element. The element could be in the void; in any case, after this call the element will not be in the void anymore (even if the assigned value is zero; to cast a cell into the void, use unset_at()).

---

sv.add_range(20, buffer)

sv.add_range(20, buffer.begin(), buffer.end())

sv.add_range(20, std::move(buffer))

Add the content of buffer starting at the specified position. The last line will attempt to use the buffer directly (only happens if the start of the new range – 20 in the example – is in the void and therefore a new range will be added). The new range is merged with the existing ones when needed, and it overwrites their content in case of overlap. If the specified position is beyond the current end of the sparse vector, the gap will be filled by void.

---

sv.append(buffer)

sv.append(buffer.begin(), buffer.end())

sv.append(std::move(buffer))

Add the content of buffer at the end of the sparse vector. The last line will attempt to use the buffer directly (only happens if the end of the sparse vector is in the void and therefore a new range will be added).

---

sv.resize(30)

Resizes the sparse vector to the specified size. Truncation may occur, in which case the data beyond the new size is removed. If an extension occurs instead, the new area is void.

---

for (const lar::sparse_vector<double>::datarange_t& range: sv.get_ranges()) {
  size_t first_item = range.begin_index(); // index of the first item
  size_t nItems = range.size(); // number of items in this range
  for (double value: range) { ... }
}

A sparse vector can be parsed range by range, skipping the void. Each range object itself supports iteration. Neither the content nor the shape of the ranges can be changed this way.

Possible future improvements

sv[10] = 3.;

is not supported if the vector is shorter than 11 (similarly to a std::vector too), and not even if the item #10 is currently in the void. This latter could be changed to create a new element/range; this would require to ship the pointer to the container with the reference (the return value of "sv[10]"), just in case an assignment will occur, or to create the element regardless, like for std::map (but this would provoke a disaster if the caller uses the non-constant operator[] for iteration). So far, set_at() is the closest thing to it.

Non-supported usage

sv.reserve(20);

This has no clear meaning. A usage analogous to STL would precede a sequence of push_back's. In that case, we should create a new empty range at the end of the vector, and reserve that. Empty ranges are currently not allowed. A replacement of this pattern is to create a new std::vector, reserve space for it and fill it, and finally use sparse_vector::append(). If the end of the vector is void, there will be no performance penalty, otherwise a reserve + copy will happen.

---

for (auto& value: sv) { ... }

In order to allow for assignment in an item which is currently not void, the non-constant iterators do not dereference directly into a reference to the vector element (which would be non-existent if in the void), but instead into a lightweight object (still called "reference"). These objects are semantically working as references, but they are formally rvalues (i.e., just values, not C++ references), so they can't be assigned to references (like "auto&"). Nevertheless they work as references and assigning to them does change the original value. Currently assigning to void cells is not supported (see above).

Definition at line 289 of file sparse_vector.h.

Member Typedef Documentation

template<typename T>

typedef vector_t::const_pointer lar::sparse_vector< T >::const_pointer

Definition at line 480 of file sparse_vector.h.

template<typename T>

typedef vector_t::difference_type lar::sparse_vector< T >::difference_type

index difference type

Definition at line 477 of file sparse_vector.h.

template<typename T>

typedef vector_t::pointer lar::sparse_vector< T >::pointer

Definition at line 479 of file sparse_vector.h.

template<typename T>

typedef range_list_t::const_iterator lar::sparse_vector< T >::range_const_iterator

type of constant iterator over ranges

Definition at line 498 of file sparse_vector.h.

template<typename T>

typedef range_list_t::iterator lar::sparse_vector< T >::range_iterator

type of iterator over ranges

Definition at line 496 of file sparse_vector.h.

template<typename T>

typedef std::vector<datarange_t> lar::sparse_vector< T >::range_list_t

type of sparse vector data

Definition at line 491 of file sparse_vector.h.

template<typename T>

typedef vector_t::size_type lar::sparse_vector< T >::size_type

size type

Definition at line 476 of file sparse_vector.h.

template<typename T>

typedef sparse_vector<T> lar::sparse_vector< T >::this_t

private

Definition at line 468 of file sparse_vector.h.

template<typename T>

typedef T lar::sparse_vector< T >::value_type

type of the stored values

Definition at line 473 of file sparse_vector.h.

template<typename T>

typedef std::vector<value_type> lar::sparse_vector< T >::vector_t

type of STL vector holding this data

Definition at line 474 of file sparse_vector.h.

Constructor & Destructor Documentation

template<typename T>

lar::sparse_vector< T >::sparse_vector ( )

inline

Default constructor: an empty vector.

Definition at line 505 of file sparse_vector.h.

: nominal_size(0), ranges() {}

template<typename T>

lar::sparse_vector< T >::sparse_vector ( size_type  new_size )

inline

Constructor: a vector with new_size elements in the void.

Definition at line 509 of file sparse_vector.h.

                                   : nominal_size(0), ranges()
    { resize(new_size); }

template<typename T>

lar::sparse_vector< T >::sparse_vector ( const vector_t &  from, size_type  offset = 0  )

inline

Constructor: a solid vector from an existing STL vector.

Parameters

from	vector to copy data from
offset	(default: 0) index the data starts from (preceeded by void)

Definition at line 517 of file sparse_vector.h.

                                                           :
    nominal_size(0), ranges()
    { add_range(offset, from.begin(), from.end()); }

template<typename T>

lar::sparse_vector< T >::sparse_vector ( sparse_vector< T > const &  )

default

Copy constructor: default.

template<typename T>

lar::sparse_vector< T >::sparse_vector ( sparse_vector< T > &&  from )

inline

Move constructor.

Definition at line 525 of file sparse_vector.h.

    : nominal_size(from.nominal_size)
    , ranges(std::move(from.ranges))
    { from.nominal_size = 0; }

template<typename T>

lar::sparse_vector< T >::sparse_vector ( vector_t &&  from, size_type  offset = 0  )

inline

Constructor: a solid vector from an existing STL vector.

Parameters

from	vector to move data from
offset	(default: 0) index the data starts from (preceeded by void)

Definition at line 547 of file sparse_vector.h.

                                                      :
    nominal_size(0), ranges()
    { add_range(offset, std::move(from)); }

template<typename T>

lar::sparse_vector< T >::~sparse_vector ( )

default

Destructor: default.

Member Function Documentation

template<typename T>

static value_type lar::sparse_vector< T >::abs ( value_type  v )

inlinestatic

Returns the module of the specified value.

Definition at line 1010 of file sparse_vector.h.

{ return (v < value_zero)? -v: v; }

template<typename T>

template<typename ITER >

const datarange_t& lar::sparse_vector< T >::add_range	(	size_type	offset,
		ITER	first,
		ITER	last
	)

Adds a sequence of elements as a range with specified offset.

Template Parameters

ITER	type of iterator

Parameters

offset	where to add the elements
first	iterator to the first element to be added
last	iterator after the last element to be added

Returns

the range where the new data was added

If the offset is beyond the current end of the sparse vector, void is added before the new range.

Existing ranges can be merged with the new data if they overlap.

template<typename T>

template<typename CONT >

const datarange_t& lar::sparse_vector< T >::add_range ( size_type  offset, const CONT &  new_data  )

inline

Copies the elements in container to a range with specified offset.

Template Parameters

CONT	type of container supporting the standard begin/end interface

Parameters

offset	where to add the elements
new_data	container holding the data to be copied

Returns

the range where the new data was added

If the offset is beyond the current end of the sparse vector, void is added before the new range.

Existing ranges can be merged with the new data if they overlap.

Definition at line 837 of file sparse_vector.h.

    { return add_range(offset, new_data.begin(), new_data.end()); }

template<typename T >

const lar::sparse_vector< T >::datarange_t & lar::sparse_vector< T >::add_range	(	size_type	offset,
		vector_t &&	new_data
	)

Adds a sequence of elements as a range with specified offset.

Parameters

offset	where to add the elements
new_data	container holding the data to be moved

Returns

the range where the new data was added

If the offset is beyond the current end of the sparse vector, void is added before the new range.

Existing ranges can be merged with the new data if they overlap. If no merging happens, new_data vector is directly used as the new range added; otherwise, it is just copied.

Definition at line 1967 of file sparse_vector.h.

{
  // insert the new range before the existing range which starts after offset
  return add_range_before(offset, std::move(new_data),
    std::upper_bound(
      ranges.begin(), ranges.end(), offset,
      typename datarange_t::less_int_range(datarange_t::less)
    )
    );

} // lar::sparse_vector<T>::add_range(vector)

template<typename T>

template<typename ITER >

const lar::sparse_vector<T>::datarange_t& lar::sparse_vector< T >::add_range	(	size_type	offset,
		ITER	first,
		ITER	last
	)

Definition at line 1946 of file sparse_vector.h.

{
  // insert the new range before the existing range which starts after offset
  range_iterator iInsert = find_next_range_iter(offset);

  // is there a range before this, which includes the offset?
  if ((iInsert != ranges.begin()) && std::prev(iInsert)->borders(offset)) {
    // then we should extend it
    (--iInsert)->extend(offset, first, last);
  }
  else {
    // no range before the insertion one includes the offset of the new range;
    // ... we need to add it as a new range
    iInsert = insert_range(iInsert, { offset, first, last });
  }
  return merge_ranges(iInsert);
} // lar::sparse_vector<T>::add_range<ITER>()

template<typename T >

const lar::sparse_vector< T >::datarange_t & lar::sparse_vector< T >::add_range_before ( size_type  offset, vector_t &&  new_data, range_iterator  nextRange  )

protected

Implementation detail of add_range(), with where to add the range.

Definition at line 2224 of file sparse_vector.h.

{
  // insert the new range before the existing range which starts after offset
  range_iterator iInsert = nextRange;

  // is there a range before this, which includes the offset?
  if ((iInsert != ranges.begin()) && (iInsert-1)->borders(offset)) {
    // then we should extend it
    (--iInsert)->extend(offset, new_data.begin(), new_data.end());
  }
  else {
    // no range before the insertion one includes the offset of the new range;
    // ... we need to add it as a new range;
    // it is not really clear to me [GP] why I need a std::move here, since
    // new_data is a rvalue already; in doubt, I have painted all this kind
    // of constructs with move()s, just in case
    iInsert = insert_range(iInsert, { offset, std::move(new_data) });
  }
  return merge_ranges(iInsert);
} // lar::sparse_vector<T>::add_range_before(vector, iterator)

template<typename T>

template<typename ITER >

const datarange_t& lar::sparse_vector< T >::append ( ITER  first, ITER  last  )

inline

Adds a sequence of elements as a range at the end of the vector.

Parameters

first	iterator to the first element to be added
last	iterator after the last element to be added

Returns

the range where the new data was added

The input range is copied at the end of the sparse vector. If the end of the sparse vector was the end of a range, that range is expanded, otherwise a new one is created.

Definition at line 927 of file sparse_vector.h.

    { return add_range(size(), first, last); }

template<typename T>

template<typename CONT >

const datarange_t& lar::sparse_vector< T >::append ( const CONT &  range_data )

inline

Adds a sequence of elements as a range at the end of the vector.

Parameters

range_data

contained holding the data to be copied or moved

Returns

the range where the new data was added

The input data is copied at the end of the sparse vector. If the end of the sparse vector was the end of a range, that range is expanded, otherwise a new one is created.

Definition at line 940 of file sparse_vector.h.

    { return add_range(size(), range_data); }

template<typename T>

const datarange_t& lar::sparse_vector< T >::append ( vector_t &&  range_data )

inline

Adds a sequence of elements as a range at the end of the vector.

Parameters

range_data

contained holding the data to be copied or moved

Returns

the range where the new data was added

If there is a range at the end of the sparse vector, it will be expanded with the new data. Otherwise, this method will use the data vector directly as a new range added at the end of the sparse vector.

Definition at line 953 of file sparse_vector.h.

    { return add_range(size(), std::move(range_data)); }

template<typename T>

template<typename ITER >

void lar::sparse_vector< T >::assign ( ITER  first, ITER  last  )

inline

Copies data from a sequence between two iterators.

Template Parameters

ITER	type of iterator

Parameters

first	iterator pointing to the first element to be copied
last	iterator pointing after the last element to be copied

The previous content of the sparse vector is lost.

Definition at line 669 of file sparse_vector.h.

{ clear(); append(first, last); }

template<typename T>

template<typename CONT >

void lar::sparse_vector< T >::assign ( const CONT &  new_data )

inline

Copies data from a container.

Template Parameters

CONT	type of container supporting the standard begin/end interface

Parameters

new_data

container with the data to be copied

The previous content of the sparse vector is lost.

Definition at line 679 of file sparse_vector.h.

{ clear(); append(new_data); }

template<typename T>

void lar::sparse_vector< T >::assign ( vector_t &&  new_data )

inline

Moves data from a vector.

Parameters

new_data

vector with the data to be moved

The previous content of the sparse vector is lost.

Definition at line 687 of file sparse_vector.h.

{ clear(); append(std::move(new_data)); }

template<typename T>

bool lar::sparse_vector< T >::back_is_void ( ) const

inline

Returns whether the sparse vector ends with void.

See Also

is_void()

Definition at line 612 of file sparse_vector.h.

    { return ranges.empty() || (ranges.back().end_index() < size()); }

template<typename T >

lar::sparse_vector< T >::iterator lar::sparse_vector< T >::begin ( )

inline

Standard iterators interface.

Definition at line 1751 of file sparse_vector.h.

  { return iterator(*this, typename iterator::special::begin()); }

template<typename T >

lar::sparse_vector< T >::const_iterator lar::sparse_vector< T >::begin ( ) const

inline

Definition at line 1760 of file sparse_vector.h.

  { return const_iterator(*this, typename const_iterator::special::begin()); }

template<typename T>

range_const_iterator lar::sparse_vector< T >::begin_range ( ) const

inline

Returns a constant iterator to the first data range.

Definition at line 757 of file sparse_vector.h.

{ return ranges.begin(); }

template<typename T>

size_type lar::sparse_vector< T >::capacity ( ) const

inline

Returns the capacity of the vector (compatibility only)

Definition at line 568 of file sparse_vector.h.

{ return nominal_size; }

template<typename T>

const_iterator lar::sparse_vector< T >::cbegin ( ) const

inline

Definition at line 583 of file sparse_vector.h.

{ return begin(); }

template<typename T>

const_iterator lar::sparse_vector< T >::cend ( ) const

inline

Definition at line 584 of file sparse_vector.h.

{ return end(); }

template<typename T>

void lar::sparse_vector< T >::clear ( )

inline

Removes all the data, making the vector empty.

Definition at line 558 of file sparse_vector.h.

{ ranges.clear(); nominal_size = 0; }

template<typename T>

template<typename ITER , typename OP >

const datarange_t& lar::sparse_vector< T >::combine_range	(	size_type	offset,
		ITER	first,
		ITER	last,
		OP &&	op,
		value_type	void_value = value_zero
	)

Combines a sequence of elements as a range with data at offset.

Template Parameters

ITER	type of iterator
OP	combination operation

Parameters

offset	where to add the elements
first	iterator to the first element to be added
last	iterator after the last element to be added
op	operation to be executed element by element
void_value	(default: value_zero) the value to use for void cells

Returns

the range where the new data landed

This is a more generic version of add_range(), where instead of replacing the target data with the data in [ first, last [, the existing data is combined with the one in that interval. The operation op is a binary operation with signature equivalent to Data_t op(Data_t, Data_t), and the operation is equivalent to v[i + offset] = op(v[i + offset], *(first + offset)): op is a binary operation whose first operand is the existing value and the second one is the one being provided. If the cell i + offset is currently void, it will be created and the value used in the combination will be void_value.

If the offset is beyond the current end of the sparse vector, void is added before the new range.

Existing ranges can be merged with the new data if they overlap.

template<typename T>

template<typename CONT , typename OP >

const datarange_t& lar::sparse_vector< T >::combine_range ( size_type  offset, const CONT &  other, OP &&  op, value_type  void_value = value_zero  )

inline

Combines the elements in container with the data at offset.

Template Parameters

CONT	type of container supporting the standard begin/end interface
OP	combination operation

Parameters

offset	where to add the elements
other	container holding the data to be combined
op	operation to be executed element by element
void_value	(default: value_zero) the value to use for void cells

Returns

the range where the new data was added

See Also

combine_range()

This is equivalent to combine_range(size_type, ITER, ITER, OP, Data_t) using as the new data range the full content of other container.

Definition at line 905 of file sparse_vector.h.

    {
      return combine_range(offset, other.begin(), other.end(),
        std::forward<OP>(op), void_value);
    }

template<typename T>

template<typename ITER , typename OP >

auto lar::sparse_vector< T >::combine_range	(	size_type	offset,
		ITER	first,
		ITER	last,
		OP &&	op,
		value_type	void_value
	)		-> const datarange_t&

Definition at line 1982 of file sparse_vector.h.

{
  /*
   * This is a complicate enough task, that we go brute force:
   * 1) combine all the input elements within the datarange where offset falls
   *    in
   * 2) create a new datarange combining void with the remaining input elements
   * 3) if the void area is over before the input elements are, repeat steps
   *    (1) and (2) with the updated offset
   * 4) at this point we'll have a train of contiguous ranges, result of
   *    combination of the input elements alternating with existing elements
   *    and with void cells: apply the regular merge algorithm
   *
   */

  auto src = first;
  auto const insertionPoint = offset; // saved for later
  auto destRange = find_range_iter_at_or_after(offset);
  while (src != last) {

    //
    // (1) combine all the input elements within the datarange including offset
    //     (NOT extending the range)
    //
    if ((destRange != end_range()) && destRange->includes(offset)) {
      // combine input data until this range is over (or input data is over)
      auto dest = destRange->get_iterator(offset);

      auto const end = destRange->end();
      while (src != last) {
        *dest = op(*dest, *src);
        ++src;
        ++offset;
        if (++dest == end) break;
      } // while
      if (src == last) break;
      offset = destRange->end_index();
      ++destRange;
    } // if

    //
    // (2) create a new datarange combining void with input elements
    //
    // at this point, offset is in the void, we do have more input data,
    // and `destRange` does _not_ contain the current insertion offset;
    // we fill as much void as we can with data, creating a new range.
    // When to stop? at the beginning of the next range, or when data is over
    //
    size_type const newRangeSize = (destRange == end_range())
      ? std::distance(src, last): (destRange->begin_index() - offset);

    // prepare the data (we'll plug it in directly)
    vector_t combinedData;
    combinedData.reserve(newRangeSize);
    size_type i = 0;
    while (i++ < newRangeSize) {
      combinedData.push_back(op(void_value, *src));
      if (++src == last) break; // no more data
    }
    // move the data as a new range inserted before the next range we just found
    // return value is the iterator to the inserted range
    destRange = insert_range(destRange, { offset, std::move(combinedData) });

    //
    // (3) if there is more input, repeat steps (1) and (2) with updated offset
    //
    offset = destRange->end_index();
    ++destRange;
  } // while

  //
  // (4) apply the regular merge algorithm;
  //     since we did not extend existing ranges, it may happen that we have
  //     created a new range at `insertionPoint` contiguous to the previous one;
  //     so we take care of checking that too
  //
  return merge_ranges
    (find_extending_range_iter(insertionPoint == 0? 0: insertionPoint - 1));

} // lar::sparse_vector<T>::combine_range<ITER>()

template<typename T >

lar::sparse_vector< T >::size_type lar::sparse_vector< T >::count ( ) const

inline

Returns the number of non-void cells.

Definition at line 1818 of file sparse_vector.h.

{
  return std::accumulate(begin_range(), end_range(), size_type(0),
    [](size_type s, const datarange_t& rng) { return s + rng.size(); }
    );
} // count()

template<typename T >

lar::sparse_vector< T >::range_iterator lar::sparse_vector< T >::eat_range_head ( range_iterator  iRange, size_t  index  )

protected

Voids the starting elements up to index (excluded) of a given range.

Definition at line 2268 of file sparse_vector.h.

{
  if (index <= iRange->begin_index()) return iRange;
  if (index >= iRange->end_index()) return ranges.erase(iRange);
  iRange->move_head(index);
  return iRange;
} // lar::sparse_vector<T>::eat_range_head()

template<typename T>

bool lar::sparse_vector< T >::empty ( ) const

inline

Returns whether the vector is empty.

Definition at line 565 of file sparse_vector.h.

{ return size() == 0; }

template<typename T >

lar::sparse_vector< T >::iterator lar::sparse_vector< T >::end ( )

inline

Definition at line 1755 of file sparse_vector.h.

  { return iterator(*this, typename iterator::special::end()); }

template<typename T >

lar::sparse_vector< T >::const_iterator lar::sparse_vector< T >::end ( ) const

inline

Definition at line 1765 of file sparse_vector.h.

  { return const_iterator(*this, typename const_iterator::special::end()); }

template<typename T>

range_const_iterator lar::sparse_vector< T >::end_range ( ) const

inline

Returns a constant iterator to after the last data range.

Definition at line 760 of file sparse_vector.h.

{ return ranges.end(); }

template<typename T >

size_t lar::sparse_vector< T >::expected_vector_size ( size_t  size )

inlinestatic

Returns the expected size taken by a vector of specified size.

Definition at line 2288 of file sparse_vector.h.

                                                                   {
  // apparently, a chunk of heap memory takes at least 32 bytes;
  // that means that a vector of 1 or 5 32-bit integers takes the same
  // space; the overhead appears to be 8 bytes, which can be allocated
  return sizeof(vector_t)
    + std::max(size_t(32), (alignof(datarange_t)*size + 8));
} // lar::sparse_vector<T>::expected_vector_size()

template<typename T>

range_iterator lar::sparse_vector< T >::find_extending_range_iter ( size_type  index )

inlineprotected

Returns an iterator to the range no earlier than index, or end() if none.

Parameters

index

the absolute index

Returns

iterator to the range including index, or the next range if none

The returned iterator points to a range that "borders" the specified index, meaning that the cell at index is either within the range, or it is the one immediately after that range. If index is in the middle of the void, though (i.e. if the previous cell is void), the next range is returned instead. Finally, if there is no next range, end_range() is returned.

The result may be also interpreted as follow: if the start of the returned range is lower than index, then the cell at index belongs to that range. Otherwise, it initiates its own range (but that range might end up being contiguous to the next(.

Definition at line 1111 of file sparse_vector.h.

    { return find_extending_range_iter(index, ranges.begin()); }

template<typename T>

range_const_iterator lar::sparse_vector< T >::find_extending_range_iter ( size_type  index ) const

inlineprotected

Definition at line 1113 of file sparse_vector.h.

    { return find_extending_range_iter(index, ranges.cbegin()); }

template<typename T >

lar::sparse_vector< T >::range_iterator lar::sparse_vector< T >::find_extending_range_iter ( size_type  index, range_iterator  rbegin  )

protected

Returns an iterator to the range that contains the first non-void element after index, or end() if none.

Parameters

index	the absolute index
rbegin	consider only from this range on

Returns

iterator to the next range not including index, or ranges.end() if none

Note that the returned range can contain index as well.

Definition at line 2199 of file sparse_vector.h.

{
  // this range has the offset (first index) above the index argument:
  auto it = find_next_range_iter(index, rbegin);
  // if index were not void, would it belong to the previous range?
  // if so, the previous range is the one we want
  return ((it != rbegin) && std::prev(it)->borders(index))? std::prev(it): it;
} // lar::sparse_vector<T>::find_extending_range_iter()

template<typename T >

lar::sparse_vector< T >::range_const_iterator lar::sparse_vector< T >::find_extending_range_iter ( size_type  index, range_const_iterator  rbegin  ) const

protected

Definition at line 2212 of file sparse_vector.h.

{
  // this range has the offset (first index) above the index argument:
  auto it = find_next_range_iter(index, rbegin);
  // if index were not void, would it belong to the previous range?
  // if so, the previus range is the one we want
  return ((it != rbegin) && std::prev(it)->borders(index))? std::prev(it): it;
} // lar::sparse_vector<T>::find_extending_range_iter() const

template<typename T>

range_iterator lar::sparse_vector< T >::find_next_range_iter ( size_type  index )

inlineprotected

Returns an iterator to the range after index.

Parameters

index

the absolute index

Returns

iterator to the next range not including index, or ranges.end() if none

Definition at line 1056 of file sparse_vector.h.

    { return find_next_range_iter(index, ranges.begin()); }

template<typename T>

range_const_iterator lar::sparse_vector< T >::find_next_range_iter ( size_type  index ) const

inlineprotected

Definition at line 1058 of file sparse_vector.h.

    { return find_next_range_iter(index, ranges.cbegin()); }

template<typename T >

lar::sparse_vector< T >::range_iterator lar::sparse_vector< T >::find_next_range_iter ( size_type  index, range_iterator  rbegin  )

protected

Returns an iterator to the range after index, or ranges.end() if none.

Parameters

index	the absolute index
rbegin	consider only from this range on

Returns

iterator to the next range not including index, or ranges.end() if none

Definition at line 2150 of file sparse_vector.h.

{
  // this range has the offset (first index) above the index argument:
  return std::upper_bound(
    rbegin, ranges.end(), index,
    typename datarange_t::less_int_range(datarange_t::less)
    );
} // lar::sparse_vector<T>::find_next_range_iter()

template<typename T >

lar::sparse_vector< T >::range_const_iterator lar::sparse_vector< T >::find_next_range_iter ( size_type  index, range_const_iterator  rbegin  ) const

protected

Definition at line 2162 of file sparse_vector.h.

{
  // this range has the offset (first index) above the index argument:
  return std::upper_bound(
    rbegin, ranges.end(), index,
    typename datarange_t::less_int_range(datarange_t::less)
    );
} // lar::sparse_vector<T>::find_next_range_iter() const

template<typename T >

const lar::sparse_vector< T >::datarange_t & lar::sparse_vector< T >::find_range

(

size_type

index

)

const

Returns the range containing the specified index.

Parameters

index

absolute index of the element to be sought

Returns

the containing range

Exceptions

std::out_of_range

if index is in no range (how appropriate!)

See Also

is_void()

Definition at line 1910 of file sparse_vector.h.

{
  if (ranges.empty()) throw std::out_of_range("empty sparse vector");
  // range on the index:
  range_const_iterator iNextRange = find_range_iterator(index);
  if (iNextRange == ranges.end())
    throw std::out_of_range("index in no range of the sparse vector");
  return *iNextRange;
} // lar::sparse_vector<T>::find_range() const

template<typename T >

lar::sparse_vector< T >::datarange_t & lar::sparse_vector< T >::find_range ( size_type  index )

inline

Definition at line 1922 of file sparse_vector.h.

{
  return const_cast<datarange_t&>
    (const_cast<const this_t*>(this)->find_range(index));
} // lar::sparse_vector<T>::find_range()

template<typename T >

lar::sparse_vector< T >::range_iterator lar::sparse_vector< T >::find_range_iter_at_or_after ( size_type  index )

protected

Returns an iterator to the range at or after index.

Parameters

index

the absolute index

Returns

iterator to the next range including index or after it, or ranges.end() if none

See Also

find_next_range_iter()

If index is in a range, an iterator to that range is returned. If index is in the void, an iterator to the next range after index is returned. If there is no such range after index, ranges.end() is returned.

Definition at line 2186 of file sparse_vector.h.

{
  // this range has the offset (first index) above the index argument:
  auto after = find_next_range_iter(index);
  // if the previous range exists and contains index, that's the one we want
  return ((after != ranges.begin()) && (index < std::prev(after)->end_index()))
    ? std::prev(after): after;
} // lar::sparse_vector<T>::find_range_iter_at_or_after()

template<typename T >

lar::sparse_vector< T >::range_const_iterator lar::sparse_vector< T >::find_range_iter_at_or_after ( size_type  index ) const

protected

Definition at line 2174 of file sparse_vector.h.

{
  // this range has the offset (first index) above the index argument:
  auto after = find_next_range_iter(index);
  // if the previous range exists and contains index, that's the one we want
  return ((after != ranges.begin()) && (index < std::prev(after)->end_index()))
    ? std::prev(after): after;
} // lar::sparse_vector<T>::find_range_iter_at_or_after() const

template<typename T >

lar::sparse_vector< T >::range_const_iterator lar::sparse_vector< T >::find_range_iterator

(

size_type

index

)

const

Returns an iterator to the range containing the specified index.

Parameters

index

absolute index of the element to be sought

Returns

iterator to containing range, or get_ranges().end() if in void

Exceptions

std::out_of_range

if index is not in the vector

See Also

is_void()

Definition at line 1897 of file sparse_vector.h.

{
  if (ranges.empty()) throw std::out_of_range("empty sparse vector");
  // range after the index:
  range_const_iterator iNextRange = find_next_range_iter(index);
  return ((iNextRange == ranges.begin())
    || (index >= (--iNextRange)->end_index()))?
    ranges.end(): iNextRange;
} // lar::sparse_vector<T>::find_range_iterator() const

template<typename T>

range_iterator lar::sparse_vector< T >::find_range_iterator ( size_type  index )

inline

Definition at line 772 of file sparse_vector.h.

    { return ranges.begin() + find_range_number(index); }

template<typename T>

std::size_t lar::sparse_vector< T >::find_range_number ( size_type  index ) const

inline

Returns the number (0-based) of range containing index.

Parameters

index

absolute index of the element to be sought

Returns

index of containing range, or n_ranges() if in void

Exceptions

std::out_of_range

if index is not in the vector

See Also

is_void()

Definition at line 783 of file sparse_vector.h.

    { return find_range_iterator(index) - begin_range(); }

template<typename T >

lar::sparse_vector< T >::size_type lar::sparse_vector< T >::fix_size ( )

protected

Extends the vector size according to the last range.

Definition at line 2278 of file sparse_vector.h.

                                                                    {
  if (!ranges.empty())
    nominal_size = std::max(nominal_size, ranges.back().end_index());
  return nominal_size;
} // lar::sparse_vector<T>::fix_size()

template<typename T>

const range_list_t& lar::sparse_vector< T >::get_ranges ( ) const

inline

Returns the internal list of non-void ranges.

Definition at line 717 of file sparse_vector.h.

{ return ranges; }

template<typename T>

range_iterator lar::sparse_vector< T >::insert_range ( range_iterator  iInsert, const datarange_t &  data  )

inlineprotected

Plug a new data range in the specified position; no check performed.

Definition at line 1140 of file sparse_vector.h.

    { return data.empty()? iInsert: ranges.insert(iInsert, data); }

template<typename T>

range_iterator lar::sparse_vector< T >::insert_range ( range_iterator  iInsert, datarange_t &&  data  )

inlineprotected

Definition at line 1142 of file sparse_vector.h.

    { return data.empty()? iInsert: ranges.insert(iInsert, std::move(data)); }

template<typename T>

static value_type lar::sparse_vector< T >::is_equal ( value_type  a, value_type  b  )

inlinestatic

Returns whether two values are the same.

Definition at line 1020 of file sparse_vector.h.

    { return is_zero(abs(a - b)); }

template<typename T>

static value_type lar::sparse_vector< T >::is_equal ( value_type  a, value_type  b, value_type  thr  )

inlinestatic

Returns whether two values are the same below a given threshold.

Definition at line 1024 of file sparse_vector.h.

    { return is_zero(abs(a - b), thr); }

template<typename T >

bool lar::sparse_vector< T >::is_valid

(

)

const

Returns if the vector is in a valid state.

The vector is in a valid state if:

• no ranges overlap or touch each other (a void gap must exist)
• no range is empty
• all ranges are sorted
• the size of the vector is not smaller than the sum of the size of the ranges plus the internal gaps An invalid state can be the result of “too smart” use of this class, or of a bug, which should be reported to the author.

Definition at line 2126 of file sparse_vector.h.

                                         {
  // a sparse vector with no non-null elements can't be detected invalid
  if (ranges.empty()) return true;

  range_const_iterator iNext = ranges.begin(), rend = ranges.end();
  while (iNext != rend) {
    range_const_iterator iRange = iNext++;
    if (iRange->empty()) return false;
    if (iNext != rend) {
      if (!(*iRange < *iNext)) return false;
      if (!iRange->separate(*iNext)) return false;
    }
  } // while
  if (nominal_size < ranges.back().end_index()) return false;
  return true;
} // lar::sparse_vector<T>::is_valid()

template<typename T >

bool lar::sparse_vector< T >::is_void

(

size_type

index

)

const

Returns whether the specified position is void.

Parameters

index

position of the cell to be tested

Exceptions

out_of_range

if index is not in the vector

See Also

is_back_void()

Definition at line 1807 of file sparse_vector.h.

                                                       {
  if (ranges.empty() || (index >= size()))
    throw std::out_of_range("empty sparse vector");
  // range after the index:
  range_const_iterator iNextRange = find_next_range_iter(index);
  return ((iNextRange == ranges.begin())
    || ((--iNextRange)->end_index() <= index));
} // lar::sparse_vector<T>::is_void()

template<typename T>

static value_type lar::sparse_vector< T >::is_zero ( value_type  v )

inlinestatic

Returns whether the value is exactly zero.

Definition at line 1013 of file sparse_vector.h.

{ return v == value_zero; }

template<typename T>

static value_type lar::sparse_vector< T >::is_zero ( value_type  v, value_type  thr  )

inlinestatic

Returns whether the value is zero below a given threshold.

Definition at line 1016 of file sparse_vector.h.

    { return abs(v - value_zero) <= thr; }

template<typename T>

auto lar::sparse_vector< T >::iterate_ranges

(

)

-> decltype(auto)

template<typename T >

void lar::sparse_vector< T >::make_void	(	iterator	first,
		iterator	last
	)

Makes all the elements from first and before last void.

Definition at line 2069 of file sparse_vector.h.

                                                                 {
  // iterators have in "currentRange" either the range they point into,
  // or the range next to the void they point to

  if ((first.cont != this) || (last.cont != this)) {
    throw std::runtime_error
      ("lar::sparse_vector::make_void(): iterators from alien container");
  }
  // if first is after next, no range is identified
  if (first >= last) return;

  range_iterator
    first_range
      = ranges.begin() + (first.get_current_range() - ranges.begin()),
    last_range = ranges.begin() + (last.get_current_range() - ranges.begin());

  //--- "first": void up to this iterator ---
  // if first in the last void region, there is nothing to erase
  if (first_range == ranges.end()) return;

  // if first is in the middle of a valid range instead, we have to resize it
  if (first.index > first_range->begin_index()) {
    if (first_range == last_range) {
      // we are going to erase a subset of a range;
      // this effectively creates two ranges;
      // first create the rightmost (last) range, and add it to the list
      last_range = ranges.emplace(++last_range, last.index,
        first_range->begin() + first_range->relative_index(last.index),
        first_range->end()
        );
      // then cut the existing one
      first_range->move_tail(first.index);
      return;
    }
    first_range->move_tail(first.index);
    ++first_range; // from next range on, start voiding
  }

  //--- "last"
  // if the index is inside a range, remove up to it
  if ((last_range != ranges.end()) && (last.index > last_range->begin_index()))
    eat_range_head(last_range, last.index);

  // finally, remove entirely the ranges in between
  ranges.erase(first_range, last_range);
} // lar::sparse_vector<T>::make_void()

template<typename T >

auto lar::sparse_vector< T >::make_void_around

(

size_type

index

)

Casts the whole range with the specified item into the void.

Parameters

index

absolute index of the element whose range is cast to void

Returns

the range just voided

Exceptions

std::out_of_range

if index is not in the vector

See Also

unset(), make_void()

Definition at line 1930 of file sparse_vector.h.

                                                                         {
  if (ranges.empty() || (index >= size()))
    throw std::out_of_range("empty sparse vector");
  // range after the index:
  range_iterator iNextRange = find_next_range_iter(index);
  if ((iNextRange == ranges.begin())
    || ((--iNextRange)->end_index() <= index))
  {
    return {};
  }
  return void_range(iNextRange);
} // lar::sparse_vector<T>::make_void_around()

template<typename T >

lar::sparse_vector< T >::datarange_t & lar::sparse_vector< T >::merge_ranges ( range_iterator  iRange )

protected

Merges all the following contiguous ranges.

Parameters

iRange

iterator to the range to merge the following ones into

Returns

iterator to the merged range

Starting from the range next to iRange, if that range is contiguous to iRange the two are merged. The merging continues while there are ranges contiguous to iRange. In the end, an iterator is returned pointing to a range that has the same starting point that iRange had, and that is not followed by a contiuguous range, since all contiguous ranges have been merged into it.

Definition at line 2248 of file sparse_vector.h.

{
  range_iterator iNext = iRange + 1;
  while (iNext != ranges.end()) {
    if (!iRange->borders(iNext->begin_index())) break;
    // iRange content dominates, but if iNext has data beyond it,
    // then we copy it
    if (iNext->end_index() > iRange->end_index()) {
      iRange->extend
        (iRange->end_index(), iNext->get_iterator(iRange->end_index()), iNext->end());
    }
    iNext = ranges.erase(iNext);
  } // while
  fix_size();
  return *iRange;
} // lar::sparse_vector<T>::merge_ranges()

template<typename T >

size_t lar::sparse_vector< T >::min_gap ( )

inlinestatic

Minimum optimal gap between ranges (a guess)

Definition at line 2298 of file sparse_vector.h.

                                           {
  // we assume here that there is no additional overhead by alignment;
  // the gap adds the space of another datarange_t, including the vector,
  // its data and overhead from heap (apparently, 8 bytes);
  //
  return (sizeof(datarange_t) + 8) / sizeof(value_type) + 1; // round up
} // lar::sparse_vector<T>::min_gap()

template<typename T>

size_type lar::sparse_vector< T >::minimum_size ( ) const

inlineprotected

Returns the size determined by the ranges already present.

Definition at line 1135 of file sparse_vector.h.

    { return ranges.empty()? 0: ranges.back().end_index(); }

template<typename T>

size_type lar::sparse_vector< T >::n_ranges ( ) const

inline

Returns the internal list of non-void ranges.

Definition at line 721 of file sparse_vector.h.

{ return ranges.size(); }

template<typename T>

sparse_vector& lar::sparse_vector< T >::operator= ( sparse_vector< T > const &  )

default

Copy assignment: default.

template<typename T>

sparse_vector& lar::sparse_vector< T >::operator= ( sparse_vector< T > &&  from )

inline

Move assignment.

Definition at line 534 of file sparse_vector.h.

    {
      ranges = std::move(from.ranges);
      nominal_size = from.nominal_size;
      from.nominal_size = 0;
      return *this;
    } // operator= (sparse_vector&&)

template<typename T >

lar::sparse_vector< T >::value_type lar::sparse_vector< T >::operator[]

(

size_type

index

)

const

Access to an element (read only)

Definition at line 1770 of file sparse_vector.h.

{
  // first range not including the index
  range_const_iterator iNextRange = find_next_range_iter(index);

  // if not even the first range includes the index, we are in the void
  // (or in some negative index space, if index signedness allowed);
  if (iNextRange == ranges.begin()) return value_zero;

  // otherwise, let's take the previous range;
  // if it includes the index, we return its value;
  // or it precedes it, and our index is in the void: return zero
  const datarange_t& range(*--iNextRange);
  return (index < range.end_index())? range[index]: value_zero;
} // lar::sparse_vector<T>::operator[]

template<typename T >

lar::sparse_vector< T >::reference lar::sparse_vector< T >::operator[]

(

size_type

index

)

Access to an element (read/write for non-void elements only!)

Definition at line 1789 of file sparse_vector.h.

{
  // first range not including the index
  range_iterator iNextRange = find_next_range_iter(index);

  // if not even the first range includes the index, we are in the void
  // (or in some negative index space, if index signedness allowed);
  if (iNextRange == ranges.begin()) return reference();

  // otherwise, let's take the previous range;
  // if it includes the index, we return its value;
  // or it precedes it, and our index is in the void: return zero
  datarange_t& range(*--iNextRange);
  return (index < range.end_index())? reference(range[index]): reference();
} // lar::sparse_vector<T>::operator[]

template<typename T>

bool lar::sparse_vector< T >::optimize ( )

inline

Performs internal optimization, returns whether the object was changed.

Definition at line 1000 of file sparse_vector.h.

{ return optimize(min_gap()); }

template<typename T>

bool lar::sparse_vector< T >::optimize ( size_t  )

inline

Definition at line 1001 of file sparse_vector.h.

{ return false; /* no optimization implemented yet */ }

template<typename T>

void lar::sparse_vector< T >::push_back ( value_type  value )

inline

Adds one element to the end of the vector (zero values too)

Parameters

value

value to be added

Definition at line 642 of file sparse_vector.h.

{ resize(size() + 1, value); }

template<typename T>

void lar::sparse_vector< T >::push_back ( value_type  value, value_type  thr  )

inline

Adds one element to the end of the vector (if zero, just adds void)

Parameters

value	value to be added
thr	threshold below which the value is considered zero

If the threshold is strictly negative, all values are pushed back

Definition at line 651 of file sparse_vector.h.

    {
      if (is_zero(value, thr)) resize(size() + 1);
      else                     push_back(value);
    } // push_back()

template<typename T>

const datarange_t& lar::sparse_vector< T >::range ( size_t  i ) const

inline

Returns the i-th non-void range (zero-based)

Definition at line 724 of file sparse_vector.h.

{ return ranges[i]; }

template<typename T >

auto lar::sparse_vector< T >::range_const_data

(

std::size_t

i

)

const

Like range_data() but with explicitly read-only access to data.

Definition at line 1891 of file sparse_vector.h.

  { auto& r = ranges[i]; return details::iteratorRange(r.cbegin(), r.cend()); }

template<typename T >

auto lar::sparse_vector< T >::range_data

(

std::size_t

i

)

Provides direct access to data of i-th non-void range (zero-based)

Parameters

i	index of the range

Returns

an object suitable for ranged-for iteration

No information about the positioning of the range itself is provided, which can be obtained with other means (e.g. range(i).begin_index()). The returned object can be used in a ranged-for loop:

for (std::size_t iRange = 0; iRange < sv.n_ranges(); ++iRange) {
  for (auto& value: sv.range_data(iRange)) {
    v *= 2.0;
  }
}

(with sv a lar::sparse_vector instance).

While this is a somehow clumsier interface than get_ranges(), it allows, using the non-const version, write access to the data elements. It intentionally provides no write access to the location of each range, though.

Definition at line 1887 of file sparse_vector.h.

  { auto& r = ranges[i]; return details::iteratorRange(r.begin(), r.end()); }

template<typename T>

auto lar::sparse_vector< T >::range_data ( std::size_t const  i ) const

inline

Definition at line 750 of file sparse_vector.h.

{ return range_const_data(i); }

template<typename T >

void lar::sparse_vector< T >::resize

(

size_type

new_size

)

Resizes the vector to the specified size, adding void.

Definition at line 1710 of file sparse_vector.h.

                                                   {
  if (new_size >= size()) {
    nominal_size = new_size;
    return;
  }

  // truncating...
  range_iterator iLastRange = find_next_range_iter(new_size);
  ranges.erase(iLastRange, ranges.end());
  if (!ranges.empty()) {
    range_iterator iLastRange = ranges.end() - 1;
    if (new_size == iLastRange->begin_index())
      ranges.erase(iLastRange);
    else if (new_size < iLastRange->end_index())
      iLastRange->resize(new_size - iLastRange->begin_index());
  } // if we have ranges

  // formally resize
  nominal_size = new_size;
} // lar::sparse_vector<T>::resize()

template<typename T >

void lar::sparse_vector< T >::resize	(	size_type	new_size,
		value_type	def_value
	)

Resizes the vector to the specified size, adding def_value.

Definition at line 1733 of file sparse_vector.h.

                                                                         {
  if (new_size == size()) return;
  if (new_size > size()) {

    if (back_is_void()) // add a new range
      append(vector_t(new_size - size(), def_value));
    else // extend the last range
      ranges.back().resize(new_size - ranges.back().begin_index(), def_value);

    nominal_size = new_size;
    return;
  }
  // truncating is the same whether there is a default value or not
  resize(new_size);
} // lar::sparse_vector<T>::resize()

template<typename T >

lar::sparse_vector< T >::value_type & lar::sparse_vector< T >::set_at	(	size_type	index,
		value_type	value
	)

Writes into an element (creating or expanding a range if needed)

Parameters

index	the index of the element to set
value	the value to be set

Returns

a reference to the changed value

See Also

unset_at()

Note that setting the value to zero will not cast the element into void. Use unset_at for that.

Definition at line 1829 of file sparse_vector.h.

{
  // first range not including the index
  range_iterator iNextRange = find_next_range_iter(index);

  // if not even the first range includes the index, we are in the void
  // (or in some negative index space, if index signedness allowed);
  if (iNextRange != ranges.begin()) {
    // otherwise, let's take the previous range;
    // if it includes the index, we set the existing value;
    // or it precedes it, and our index is in the void, add the value as a
    // range
    datarange_t& range(*std::prev(iNextRange));
    if (index < range.end_index()) return range[index] = value;
  }
  // so we are in the void; add the value as a new range
  return const_cast<datarange_t&>(add_range(index, { value }))[index];
} // lar::sparse_vector<T>::set_at()

template<typename T >

bool lar::sparse_vector< T >::should_merge ( const typename datarange_t::base_t &  a, const typename datarange_t::base_t &  b  )

inlinestatic

Returns if merging the two specified ranges would save memory.

Definition at line 2308 of file sparse_vector.h.

{
  size_type gap_size = (a < b)?
    b.begin_index() - a.begin_index() - a.size():
    a.begin_index() - b.begin_index() - b.size();
  return expected_vector_size(a.size() + b.size() + gap_size)
    <= expected_vector_size(a.size()) + expected_vector_size(b.size());
} // lar::sparse_vector<T>::should_merge()

template<typename T>

size_type lar::sparse_vector< T >::size ( ) const

inline

Returns the size of the vector.

Definition at line 562 of file sparse_vector.h.

{ return nominal_size; }

template<typename T >

void lar::sparse_vector< T >::unset_at

(

size_type

index

)

Casts the element with the specified index into the void.

Definition at line 1850 of file sparse_vector.h.

                                                  {
  // first range not including the index
  range_iterator iNextRange = find_next_range_iter(index);

  // if not even the first range includes the index, we are in the void
  // (or in some negative index space, if index signedness allowed);
  if (iNextRange == ranges.begin()) return;

  // otherwise, let's take the previous range;
  // or it precedes the index, and our index is in the void
  datarange_t& range(*--iNextRange);
  if (index >= range.end_index()) return; // void already

  // it includes the index:
  // - if it's a one-element range, remove the range
  if (range.size() == 1) ranges.erase(iNextRange);
  // - if it's on a border, resize the range
  else if (index == range.begin_index())
    range.move_head(index + 1);
  else if (index == range.end_index() - 1)
    range.move_tail(index);
  // - if it's inside, break the range in two
  else if (index < range.end_index()) {
    // we are going to put a hole in a range;
    // this effectively creates two ranges;
    // first create the rightmost range, and add it to the list
    ranges.emplace(++iNextRange, index + 1,
      range.begin() + range.relative_index(index + 1),
      range.end()
      );
    // then cut the existing one
    range.move_tail(index);
  }
} // lar::sparse_vector<T>::unset_at()

template<typename T >

auto lar::sparse_vector< T >::void_range

(

range_iterator const

iRange

)

Turns the specified range into void.

Parameters

iRange

iterator or index of range to be deleted

Returns

the range just voided

See Also

make_void(), unset_at()

The range is effectively removed from the sparse vector, rendering void the interval it previously covered. The range object itself is returned (no copy is performed).

The specified range must be valid. Trying to void an invalid range (including end_range()) yields undefined behavior.

Definition at line 2118 of file sparse_vector.h.

                                                                         {
  auto r { std::move(*iRange) }; // triggering move constructor
  ranges.erase(iRange);          // the emptied range is removed from vector
  return r;                      // returning it as a temporary avoids copies
} // lar::sparse_vector<T>::void_range()

template<typename T>

datarange_t lar::sparse_vector< T >::void_range ( std::size_t const  iRange )

inline

Definition at line 973 of file sparse_vector.h.

    { return void_range(ranges.begin() + iRange); }

Member Data Documentation

template<typename T>

size_type lar::sparse_vector< T >::nominal_size

protected

current size

Definition at line 1046 of file sparse_vector.h.

template<typename T>

range_list_t lar::sparse_vector< T >::ranges

protected

list of ranges

Definition at line 1047 of file sparse_vector.h.

template<typename T>

constexpr lar::sparse_vector< T >::value_type lar::sparse_vector< T >::value_zero {0}

static

a representation of 0

Definition at line 1007 of file sparse_vector.h.

---

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

• sparse_vector.h