Sparse Vector Index Lookup and Caching class. More...

#include <AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp>

Inheritance diagram for AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >:

Classes
class	InvalidInternalStateException

class	NoSpVecSetException

struct	poss_type
	Struct with members: size_type poss; ElementRelation rel;. More...

Private Member Functions
void	assert_sp_vec_setup () const
	Assert that a sparse vector has been set up. More...

size_type	adjust_cached_poss (UpperLower uplow) const
	Adjust the cached possition. More...

poss_type	binary_ele_search (index_type index, UpperLower uplow) const
	Perform a binary search for an element in the sparse vector. More...

Private Attributes
element_type *	ele_

size_type	nz_

difference_type	offset_

index_type	index_cached_

size_type	poss_cached_

ElementRelation	ele_rel_cached_

Public types
enum	UpperLower { UPPER_ELE, LOWER_ELE }

enum	ElementRelation { BEFORE_ELE, AFTER_ELE, EQUAL_TO_ELE }

typedef T_Element	element_type

typedef element_type::index_type	index_type

typedef ptrdiff_t	difference_type

Constructors
	SpVecIndexLookup ()
	Construct uninitialized with not sparse vector set (ele() == 0#) More...

	SpVecIndexLookup (element_type *ele, size_type nz, difference_type offset)
	Construct initialize with a sparse vector. More...

Sparse vector representation setup
void	set_sp_vec (element_type *ele, size_type nz, difference_type offset)
	Set a new sparse vector. More...

void	incr_nz ()
	Increment nz only. More...

Sparse vector representation access
element_type *	ele () const

size_type	nz () const

difference_type	offset () const

Element lookup and caching
poss_type	find_poss (index_type index, UpperLower uplow) const
	Lookup an element and cache the result if a binary search was performed. More...

size_type	find_element (index_type index, bool is_sorted) const
	Lookup an element. More...

State management
void	sp_vec_was_modified ()
	Called by client to inform the object that the sparse vector was modified so that the cache may be invalidated. More...

void	validate_state () const
	Called by client to ensure that the internal state is valid. More...

Detailed Description

template<class T_Element>
class AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >

Sparse Vector Index Lookup and Caching class.

This class is used to perform a lookup for elements in a sparse vector stored as an array of nonzero elements of a templated type T_Element. The type T_Element must conform to the SparseElementTemplateInterface specification. These elements must be sorted in accending order.

The default C++ assignment operator and copy constructor are allowed.

Definition at line 64 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

Member Typedef Documentation

template<class T_Element>

typedef T_Element AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::element_type

Definition at line 71 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>

typedef element_type::index_type AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::index_type

Definition at line 73 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>

typedef ptrdiff_t AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::difference_type

Definition at line 75 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

Member Enumeration Documentation

template<class T_Element>

enum AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup::UpperLower

Enumerator
UPPER_ELE
LOWER_ELE

Definition at line 83 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>

enum AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup::ElementRelation

Enumerator
BEFORE_ELE
AFTER_ELE
EQUAL_TO_ELE

Definition at line 85 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

Constructor & Destructor Documentation

template<class T_Element>

AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::SpVecIndexLookup ( )

inline

Construct uninitialized with not sparse vector set (ele() == 0#)

Definition at line 100 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>

AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::SpVecIndexLookup	(	element_type *	ele,
		size_type	nz,
		difference_type	offset
	)

inline

Construct initialize with a sparse vector.

Definition at line 105 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

Member Function Documentation

template<class T_Element>

void AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::set_sp_vec	(	element_type *	ele,
		size_type	nz,
		difference_type	offset
	)

inline

Set a new sparse vector.

This will wipe out any cache that may be stored.

Definition at line 118 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>

void AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::incr_nz ( )

inline

Increment nz only.

Definition at line 124 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>

element_type* AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::ele ( ) const

inline

Definition at line 134 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>

size_type AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::nz ( ) const

inline

Definition at line 138 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>

difference_type AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::offset ( ) const

inline

Definition at line 142 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element >

AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::poss_type AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::find_poss	(	index_type	index,
		UpperLower	uplow
	)		const

Lookup an element and cache the result if a binary search was performed.

This function should only be used if it can be assumed that the elements are sorted in assending order.

If #index# is the same as the previously cached lookup then this function will execute in O(1) time, otherwise a O(log(nz)) binary search will be performed to find the element and the result of the lookup will be cached.

To be able to utilize a previously cached search this function must know if an upper element or lower element is to be found.\

Preconditions:

ele() > 0# (throw #NoSpVecSetException#)

Postconditions:

[uplow == lower_ele] #index <= ele()[return.poss].index() + offset()#
[uplow == upper_ele] ele()[return.poss].index() + offset() <= index#

Returns: #poss_type# object where #return.poss# gives a position in tye underlying array and #return.rel# gives where the element with #index# is in relation to this possition. [ BEFORE_ELE# if ele()[return.poss].index() + offset() < index# ] #return.rel# = [ EQUAL_TO_ELE# if ele()[return.poss].index() + offset() == index# ] [ AFTER_ELE# if ele()[return.poss].index() + offset() > index# ]

Definition at line 53 of file AbstractLinAlgPack_SpVecIndexLookupClassDef.hpp.

template<class T_Element >

AbstractLinAlgPack::size_type AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::find_element	(	index_type	index,
		bool	is_sorted
	)		const

Lookup an element.

Lookup an exact match for an element. If the element is not found, the end of the sequence will be returned.

If is_sorted == true then a binary search will be used (O(log(nz)). If is_sorted==false a sequential search will be used (O(nz)). No result is cached here.

Preconditions:

ele() > 0# (throw #NoSpVecSetException#)

Postconditions:

[return == nz()] No element exits with this index
[return < nz()] #index == ele()[return].index() + offset()#

Definition at line 116 of file AbstractLinAlgPack_SpVecIndexLookupClassDef.hpp.

template<class T_Element>

void AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::sp_vec_was_modified ( )

inline

Called by client to inform the object that the sparse vector was modified so that the cache may be invalidated.

Definition at line 208 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element >

void AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::validate_state ( ) const

Called by client to ensure that the internal state is valid.

If ele() != 0# but nz == 0# or ele()[0].index() + offset() < 1# then this is an invalid sparse vector and the function will throw a #NoSpVecSetException# exception. It is up to the client to ensure that a valid sparse vector is set.

If there in some other problem with internal state then an exception #InvalidInternalStateException# will be thrown. The error message will be meant for a developer to inspect.

Definition at line 138 of file AbstractLinAlgPack_SpVecIndexLookupClassDef.hpp.

template<class T_Element>

void AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::assert_sp_vec_setup ( ) const

inlineprivate

Assert that a sparse vector has been set up.

Definition at line 249 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element >

AbstractLinAlgPack::size_type AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::adjust_cached_poss ( UpperLower uplow ) const

private

Adjust the cached possition.

Definition at line 146 of file AbstractLinAlgPack_SpVecIndexLookupClassDef.hpp.

template<class T_Element >

AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::poss_type AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::binary_ele_search	(	index_type	index,
		UpperLower	uplow
	)		const

private

Perform a binary search for an element in the sparse vector.

Parameters

index	[I] index begin looked for
uplow	[I] whether it is an upper (UPPER_ELE#) or lower (LOWER_ELE#) element needed
poss	[O] possition where the element was found. If #uplow == LOWER_ELE# then #poss# will be the largest possible integer that satisfies: #index <= ele_[poss].index()#. If #uplow == UPPER_ELE# then #poss# will be the smallest possible integer that satisfies: ele_[poss].index() <= index#
ele_rel	[O] Where the element with #index# is in relation to the element at #poss# returned. There are three possible values. BEFORE_ELE# : The element saught is a zero element that is before the element at #poss# AFTER_ELE# : The element saught is a zero element that is after the element at #poss# #EQUAL_TO_POSS#: This is a nonzero elment that exists at possition #poss#