lar::sparse_vector< T > Class Template Reference

A sparse vector. More...

#include "sparse_vector.h"

Classes
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...
void	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 ()
	Standard iterators interface. More...
const_iterator	begin () const
	Standard iterators interface. More...
const_iterator	end () const
	Standard iterators interface. More...
const_iterator	cbegin () const
	Standard iterators interface. More...
const_iterator	cend () const
	Standard iterators interface. More...
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 region of the sparse vector which contains all non-void values.
const range_list_t &	get_ranges () const
	Returns the internal list of non-void ranges. More...
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...
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...
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)
	Returns the internal list of non-void ranges. More...
const datarange_t &	find_range (size_type index) const
	Returns the range containing the specified index. More...
datarange_t &	find_range (size_type index)
	Returns the range containing the specified index. More...
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...
void	void_range (range_iterator iRange)
	Turns the specified range into void. More...
void	void_range (size_t iRange)
	Turns the specified range into void. More...
bool	optimize ()
	Performs internal optimization, returns whether the object was changed. More...
bool	optimize (size_t)
	Performs internal optimization, returns whether the object was changed. More...

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...
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 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, or end() if none. More...
range_const_iterator	find_next_range_iter (size_type index) const
	Returns an iterator to the range after index, or end() if none. More...
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
	Returns an iterator to the range after index, or ranges.end() if none. More...
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
	Returns an iterator to the range no earlier than index, or end() if none. More...
range_iterator	find_extending_range_iter (size_type index, range_iterator rbegin)
	Returns an iterator to the range after index, or end() if none. More...
range_const_iterator	find_extending_range_iter (size_type index, range_const_iterator rbegin) const
	Returns an iterator to the range after index, or end() if none. More...
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)
	Plug a new data range in the specified position; no check performed. More...

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 457 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 470 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 467 of file sparse_vector.h.

template<typename T>

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

Definition at line 469 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 487 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 485 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 480 of file sparse_vector.h.

template<typename T>

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

size type

Definition at line 466 of file sparse_vector.h.

template<typename T>

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

private

Definition at line 458 of file sparse_vector.h.

template<typename T>

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

type of the stored values

Definition at line 463 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 464 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 494 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 498 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 506 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 514 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 536 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 931 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.

Referenced by lar::sparse_vector< T >::add_range(), lar::sparse_vector< T >::make_void_around(), and butcher::EventButcher::produce().

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 767 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 1746 of file sparse_vector.h.

{
        // insert the new range before the existing range which starts after offset
        range_iterator iInsert = std::upper_bound(
                ranges.begin(), ranges.end(), offset,
                typename datarange_t::less_int_range(datarange_t::less)
                );
        
        // 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(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 1725 of file sparse_vector.h.

References lar::sparse_vector< T >::add_range().

{
        // 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()) && (iInsert-1)->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>

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 857 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 870 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 883 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 658 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 668 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 676 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 601 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 1529 of file sparse_vector.h.

References evd::details::begin().

Referenced by operator<<(), and recob::Wire::Signal().

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

template<typename T >

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

inline

Standard iterators interface.

Definition at line 1538 of file sparse_vector.h.

References evd::details::begin().

        { 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 699 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 557 of file sparse_vector.h.

{ return nominal_size; }

template<typename T>

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

inline

Standard iterators interface.

Definition at line 572 of file sparse_vector.h.

{ return begin(); }

template<typename T>

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

inline

Standard iterators interface.

Definition at line 573 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 547 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 835 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 1773 of file sparse_vector.h.

References evd::details::end(), and lar::sparse_vector< T >::datarange_t::get_iterator().

{
        /*
         * 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_extending_range_iter(offset, ranges.begin());
        while (src != last) {
                
                //
                // (1) combine all the input elements within the datarange including offset
                // 
                if ((destRange != end_range()) && (offset < destRange->end_index())) {
                        // this means `destRange` contains 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();
                } // if
                
                //
                // (2) create a new datarange combining void with input elements
                //
                // at this point, offset is in the void, and we do have more input data;
                // 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
                ++destRange;
                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
        //
        return merge_ranges(find_extending_range_iter(insertionPoint));
        
} // 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 1596 of file sparse_vector.h.

References s, lar::sparse_vector< T >::set_at(), and lar::range_t< SIZE >::size().

{
        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 1997 of file sparse_vector.h.

Referenced by lar::sparse_vector< T >::merge_ranges().

{
        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 554 of file sparse_vector.h.

{ return size() == 0; }

template<typename T >

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

inline

Standard iterators interface.

Definition at line 1533 of file sparse_vector.h.

References evd::details::end().

Referenced by operator<<(), and recob::Wire::Signal().

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

template<typename T >

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

inline

Standard iterators interface.

Definition at line 1543 of file sparse_vector.h.

References evd::details::end().

        { 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 702 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 2017 of file sparse_vector.h.

References max.

                                                                   {
        // 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 teh 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 1015 of file sparse_vector.h.

Referenced by lar::sparse_vector< T >::find_extending_range_iter(), and lar::sparse_vector< T >::find_next_range_iter().

                { 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

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 teh 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 1017 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 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

Definition at line 1952 of file sparse_vector.h.

References lar::sparse_vector< T >::find_extending_range_iter().

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

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

Returns an iterator to the range 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

Definition at line 1965 of file sparse_vector.h.

References lar::sparse_vector< T >::merge_ranges().

{
        // 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, or end() if none.

Parameters

index

the absolute index

Returns

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

Definition at line 977 of file sparse_vector.h.

Referenced by lar::sparse_vector< T >::find_next_range_iter(), and lar::sparse_vector< T >::is_valid().

                { 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

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

Parameters

index

the absolute index

Returns

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

Definition at line 979 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 1927 of file sparse_vector.h.

References lar::sparse_vector< T >::find_next_range_iter().

{
        // 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

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 1939 of file sparse_vector.h.

References lar::sparse_vector< T >::find_extending_range_iter().

{
        // 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 seeked

Returns

the containing range

Exceptions

std::out_of_range

if index is in no range (how appropriate!)

See also

is_void()

Definition at line 1689 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

Returns the range containing the specified index.

Parameters

index

absolute index of the element to be seeked

Returns

the containing range

Exceptions

std::out_of_range

if index is in no range (how appropriate!)

See also

is_void()

Definition at line 1701 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_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 seeked

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

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

inline

Returns the internal list of non-void ranges.

Definition at line 1679 of file sparse_vector.h.

{
        return ranges.begin() + (
                (const_cast<const this_t*>(this)->find_range_iterator(index))
                - ranges.begin());
} // lar::sparse_vector<T>::find_range_iterator()

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 2007 of file sparse_vector.h.

References max.

                                                                    {
        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 690 of file sparse_vector.h.

Referenced by hit::HitAnaAlg::FillWireInfo(), hit::GausHitFinder::produce(), and hit::DPRawHitFinder::produce().

{ 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 1041 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

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

Definition at line 1043 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 941 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 945 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 1903 of file sparse_vector.h.

References lar::sparse_vector< T >::find_next_range_iter().

                                         {
        // 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 1585 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 934 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 937 of file sparse_vector.h.

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

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 1854 of file sparse_vector.h.

References lar::sparse_vector< T >::const_iterator::cont, lar::sparse_vector< T >::const_iterator::get_current_range(), and lar::sparse_vector< T >::const_iterator::index.

                                                                 {
        // 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 >

void 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

Exceptions

std::out_of_range

if index is not in the vector

See also

unset(), make_void()

Definition at line 1709 of file sparse_vector.h.

References lar::sparse_vector< T >::add_range().

                                                          {
        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;
        }
        ranges.erase(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 ranges.

Definition at line 1977 of file sparse_vector.h.

References lar::sparse_vector< T >::eat_range_head(), and lar::sparse_vector< T >::datarange_t::extend().

Referenced by lar::sparse_vector< T >::find_extending_range_iter().

{
        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 2027 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 1036 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 693 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 523 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 1548 of file sparse_vector.h.

References lar::range_t< SIZE >::end_index().

{
        // 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 1567 of file sparse_vector.h.

References lar::range_t< SIZE >::end_index().

{
        // 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 921 of file sparse_vector.h.

{ return optimize(min_gap()); }

template<typename T>

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

inline

Performs internal optimization, returns whether the object was changed.

Definition at line 922 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 631 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 640 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 696 of file sparse_vector.h.

{ return ranges[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 1488 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 1511 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 1607 of file sparse_vector.h.

References lar::range_t< SIZE >::end_index().

Referenced by lar::sparse_vector< T >::count().

{
        // 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(*--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 2037 of file sparse_vector.h.

References lar::range_t< SIZE >::begin_index(), and lar::range_t< SIZE >::size().

{
        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 551 of file sparse_vector.h.

Referenced by operator<<().

{ 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 1628 of file sparse_vector.h.

References lar::sparse_vector< T >::datarange_t::begin(), lar::range_t< SIZE >::begin_index(), lar::sparse_vector< T >::datarange_t::end(), lar::range_t< SIZE >::end_index(), lar::sparse_vector< T >::datarange_t::move_head(), lar::sparse_vector< T >::datarange_t::move_tail(), lar::range_t< SIZE >::relative_index(), and lar::range_t< SIZE >::size().

                                                  {
        // 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>

void lar::sparse_vector< T >::void_range ( range_iterator  iRange )

inline

Turns the specified range into void.

Parameters

iRange

iterator or index of range to be deleted

See also

make_void(), unset_at()

Definition at line 894 of file sparse_vector.h.

{ ranges.erase(iRange); }

template<typename T>

void lar::sparse_vector< T >::void_range ( size_t  iRange )

inline

Turns the specified range into void.

Parameters

iRange

iterator or index of range to be deleted

See also

make_void(), unset_at()

Definition at line 895 of file sparse_vector.h.

{ ranges.erase(ranges.begin() + iRange); }

Member Data Documentation

template<typename T>

size_type lar::sparse_vector< T >::nominal_size

protected

current size

Definition at line 967 of file sparse_vector.h.

template<typename T>

range_list_t lar::sparse_vector< T >::ranges

protected

list of ranges

Definition at line 968 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 928 of file sparse_vector.h.

---

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

• /cvmfs/larsoft.opensciencegrid.org/products/lardataobj/v07_06_00/source/lardataobj/Utilities/sparse_vector.h