AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element > Class Template Reference

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

#include <AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp>

List of all members.

Public types

typedef T_Element element_type
 
typedef element_type::index_type index_type
 
typedef ptrdiff_t difference_type
 
enum  UpperLower { UPPER_ELE, LOWER_ELE }
  More...
enum  ElementRelation { BEFORE_ELE, AFTER_ELE, EQUAL_TO_ELE }
  More...

Constructors

 SpVecIndexLookup ()
 Construct uninitialized with not sparse vector set (ele() == 0#).
 SpVecIndexLookup (element_type *ele, size_type nz, difference_type offset)
 Construct initialize with a sparse vector.

Sparse vector representation setup

void set_sp_vec (element_type *ele, size_type nz, difference_type offset)
 Set a new sparse vector.
void incr_nz ()
 Increment nz only.

Sparse vector representation access

element_typeele () 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.
size_type find_element (index_type index, bool is_sorted) const
 Lookup an element.

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.
void validate_state () const
 Called by client to ensure that the internal state is valid.

Private Member Functions

void assert_sp_vec_setup () const
 Assert that a sparse vector has been set up.
size_type adjust_cached_poss (UpperLower uplow) const
 Adjust the cached possition.
poss_type binary_ele_search (index_type index, UpperLower uplow) const
 Perform a binary search for an element in the sparse vector.

Private Attributes

element_typeele_
size_type nz_
difference_type offset_
index_type index_cached_
size_type poss_cached_
ElementRelation ele_rel_cached_

Classes

class  InvalidInternalStateException
  More...
class  NoSpVecSetException
  More...
struct  poss_type
 Struct with members: size_type poss; ElementRelation rel;. 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 51 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 58 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

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

Definition at line 60 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

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

Definition at line 62 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 70 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 72 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 87 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 92 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 105 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>
void AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::incr_nz (  )  [inline]

Increment nz only.

Definition at line 111 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>
element_type* AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::ele (  )  const [inline]

Definition at line 121 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>
size_type AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::nz (  )  const [inline]

Definition at line 125 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>
difference_type AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::offset (  )  const [inline]

Definition at line 129 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:

Postconditions:

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 40 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:

Postconditions:

Definition at line 103 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 195 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 125 of file AbstractLinAlgPack_SpVecIndexLookupClassDef.hpp.

template<class T_Element>
void AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::assert_sp_vec_setup (  )  const [inline, private]

Assert that a sparse vector has been set up.

Definition at line 236 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 133 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#

Definition at line 158 of file AbstractLinAlgPack_SpVecIndexLookupClassDef.hpp.


Member Data Documentation

template<class T_Element>
element_type* AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::ele_ [private]

Definition at line 220 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>
size_type AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::nz_ [private]

Definition at line 221 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>
difference_type AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::offset_ [private]

Definition at line 222 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>
index_type AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::index_cached_ [mutable, private]

Definition at line 224 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>
size_type AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::poss_cached_ [mutable, private]

Definition at line 225 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.

template<class T_Element>
ElementRelation AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup< T_Element >::ele_rel_cached_ [mutable, private]

Definition at line 226 of file AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp.


The documentation for this class was generated from the following files:
Generated on Tue Oct 20 12:54:09 2009 for MOOCHO (Single Doxygen Collection) by doxygen 1.4.7