AbstractLinAlgPack: C++ Interfaces For Vectors, Matrices And Related Linear Algebra Objects  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp
1 // @HEADER
2 // ***********************************************************************
3 //
4 // Moocho: Multi-functional Object-Oriented arCHitecture for Optimization
5 // Copyright (2003) Sandia Corporation
6 //
7 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8 // license for use of this work by or on behalf of the U.S. Government.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are
12 // met:
13 //
14 // 1. Redistributions of source code must retain the above copyright
15 // notice, this list of conditions and the following disclaimer.
16 //
17 // 2. Redistributions in binary form must reproduce the above copyright
18 // notice, this list of conditions and the following disclaimer in the
19 // documentation and/or other materials provided with the distribution.
20 //
21 // 3. Neither the name of the Corporation nor the names of the
22 // contributors may be used to endorse or promote products derived from
23 // this software without specific prior written permission.
24 //
25 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 //
37 // Questions? Contact Roscoe A. Bartlett (rabartl@sandia.gov)
38 //
39 // ***********************************************************************
40 // @HEADER
41 
42 #ifndef SPVEC_INDEX_LOOKUP_CLASS_DECL_H
43 #define SPVEC_INDEX_LOOKUP_CLASS_DECL_H
44 
45 #include <stdexcept>
46 
47 #include "AbstractLinAlgPack_Types.hpp"
48 
49 namespace AbstractLinAlgPack {
50 
51 namespace SparseVectorUtilityPack {
52 
53 // ///////////////////////////////////////////////////////////////////////
63 template <class T_Element>
65 public:
66 
69 
71  typedef T_Element element_type;
73  typedef typename element_type::index_type index_type;
75  typedef ptrdiff_t difference_type;
77  class NoSpVecSetException : public std::logic_error
78  {public: explicit NoSpVecSetException(const std::string& what_arg) : std::logic_error(what_arg) {}};
80  class InvalidInternalStateException : public std::logic_error
81  {public: explicit InvalidInternalStateException(const std::string& what_arg) : std::logic_error(what_arg) {}};
83  enum UpperLower { UPPER_ELE, LOWER_ELE };
85  enum ElementRelation { BEFORE_ELE, AFTER_ELE, EQUAL_TO_ELE };
87  struct poss_type {
88  poss_type() : poss(0), rel(EQUAL_TO_ELE) {}
89  poss_type(size_type _poss, ElementRelation _rel) : poss(_poss), rel(_rel) {}
90  size_type poss;
91  ElementRelation rel;
92  };
93 
95 
98 
101  : ele_(0), nz_(0), offset_(0), index_cached_(0)
102  {}
103 
106  : ele_(ele), nz_(nz), offset_(offset), index_cached_(0)
107  {}
108 
110 
113 
119  ele_ = ele; nz_ = nz; offset_ = offset;
121  }
122 
124  void incr_nz() {
125  nz_++;
126  }
127 
129 
132 
134  element_type* ele() const {
135  return ele_;
136  }
138  size_type nz() const {
139  return nz_;
140  }
143  return offset_;
144  }
145 
147 
150 
179  poss_type find_poss(index_type index, UpperLower uplow) const;
180 
198  size_type find_element( index_type index, bool is_sorted ) const;
199 
201 
204 
209  index_cached_ = 0;
210  }
211 
222  void validate_state() const;
223 
225 
226 private:
227  // ///////////////////////////////////////////////////////////////////////////////
228  // Private types
229 
230  // //////////////////////////////////////////////////////////////////////////////
231  // Private data members
232 
233  element_type* ele_; // pointer to array of elements
234  size_type nz_; // number of nonzero elements in ele_
235  difference_type offset_; // offset for each element in ele_. The actuall index for
236  // each element i is ele_[i].index() + offset().
237  mutable index_type index_cached_; // index of last binary search
238  mutable size_type poss_cached_; // possition last looked up
239  mutable ElementRelation ele_rel_cached_;// Specifies where the element looked up is in relation
240  // to the element at poss_cached:
241  // before_ele: zero element before poss_cached_
242  // after_ele: zero element after poss_cached_
243  // equal_to_ele: nonzero element at poss_cached_
244 
245  // ////////////////////////
246  // Private member functions
247 
249  void assert_sp_vec_setup() const {
250  if(!ele_)
251  throw NoSpVecSetException("The sparse vector (ele, nz, offset) has not been set yet");
252  }
253 
255  size_type adjust_cached_poss(UpperLower uplow) const;
256 
274  poss_type binary_ele_search(index_type index, UpperLower uplow) const;
275 
276 
277 }; // end class SpVecIndexLookup
278 
279 } // namespace SparseVectorUtilityPack
280 
281 } // end namespace AbstractLinAlgPack
282 
283 #endif // SPVEC_INDEX_LOOKUP_CLASS_DECL_H
poss_type find_poss(index_type index, UpperLower uplow) const
Lookup an element and cache the result if a binary search was performed.
void set_sp_vec(element_type *ele, size_type nz, difference_type offset)
Set a new sparse vector.
void sp_vec_was_modified()
Called by client to inform the object that the sparse vector was modified so that the cache may be in...
SpVecIndexLookup(element_type *ele, size_type nz, difference_type offset)
Construct initialize with a sparse vector.
SpVecIndexLookup()
Construct uninitialized with not sparse vector set (ele() == 0#)
size_type find_element(index_type index, bool is_sorted) const
Lookup an element.
void validate_state() const
Called by client to ensure that the internal state is valid.