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_SpVecIndexLookupClassDef.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 SP_VEC_INDEX_LOOKUP_CLASS_DEF_H
43 #define SP_VEC_INDEX_LOOKUP_CLASS_DEF_H
44 
45 #include "AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp"
46 #include "AbstractLinAlgPack_compare_element_indexes.hpp"
47 
48 // /////////////////////////////////////////////////////////////////////////////////////
49 // Definitions of members for SpVecIndexLookup<>
50 
51 template<class T_Element>
54  index_type index, UpperLower uplow) const
55 {
56  // First look at the cache. If it matches then use that information, otherwise
57  // perform a binary search to find the possition then cache it for latter.
58 
59  if(index_cached_) {
60  if(index == index_cached_) // Same as cache so use cache
61  return poss_type(adjust_cached_poss(uplow),ele_rel_cached_);
62  if(index == index_cached_ + 1 && ele_rel_cached_ == AFTER_ELE
63  && uplow == LOWER_ELE)
64  {
65  // Since poss_cached_ = ( max p s.t. ele_[p].index() < index_cached_ )
66  // there are three possibilities here:
67  // Either:
68 
69  // a) poss_cashed_ == nz_ - 1
70  if( poss_cached_ == nz_ - 1 )
71  return poss_type( poss_cached_ , AFTER_ELE );
72 
73  // b) ele_[poss_cashed_+1].index() == index
74  if( ele_[poss_cached_+1].index() == index )
75  return poss_type( poss_cached_+1 , EQUAL_TO_ELE );
76 
77  // c) ele_[poss_cashed_+1].index() > index.
78  if( ele_[poss_cached_+1].index() > index )
79  return poss_type( poss_cached_+1 , BEFORE_ELE );
80  }
81  if(index == index_cached_ - 1 && ele_rel_cached_ == BEFORE_ELE
82  && uplow == UPPER_ELE)
83  {
84  // Since poss_cached_ = ( max p s.t. ele_[p].index() < index_cached_ )
85  // there are three possibilities here:
86  // Either:
87 
88  // a) poss_cashed_ == 0
89  if( poss_cached_ == 0 )
90  return poss_type( poss_cached_ , BEFORE_ELE );
91 
92  // b) ele_[poss_cashed_-1].index() == index
93  if( ele_[poss_cached_+1].index() == index )
94  return poss_type( poss_cached_-1 , EQUAL_TO_ELE );
95 
96  // c) ele_[poss_cashed_-1].index() < index.
97  return poss_type( poss_cached_ - 1, AFTER_ELE);
98  }
99  }
100 
101  // Perform binary search for the element
102  poss_type poss = binary_ele_search(index,uplow);
103 
104  // Cache the result if needed. Don't cache an endpoint
105  if(poss.poss != 0 && poss.poss != nz() - 1) {
106  index_cached_ = index;
107  poss_cached_ = poss.poss;
108  ele_rel_cached_ = poss.rel;
109  }
110 
111  return poss;
112 }
113 
114 template<class T_Element>
115 AbstractLinAlgPack::size_type
117  index_type index, bool is_sorted ) const
118 {
119  typedef T_Element* itr_t;
120  if(is_sorted) {
121  const std::pair<itr_t,itr_t> p = std::equal_range( ele(), ele() + nz()
122  , index - offset(), compare_element_indexes_less<element_type>() );
123  // If p.second - p.first == 1 then the element exits
124  if( p.second - p.first == 1 )
125  return p.first - ele(); // zero based
126  else
127  return nz(); // zero based
128  }
129  else {
130  const itr_t itr = std::find_if( ele(), ele() + nz()
132  return itr - ele(); // zero based
133  }
134 }
135 
136 template<class T_Element>
137 void
139 {
140  TEUCHOS_TEST_FOR_EXCEPTION( ele() && ele()->index() + offset() < 1, NoSpVecSetException,
141  "SpVecIndexLookup<T_Element>::validate_state(): Error, ele()->index() + offset() < 1");
142 }
143 
144 template<class T_Element>
145 AbstractLinAlgPack::size_type
147  UpperLower uplow) const
148 {
149  if(ele_rel_cached_ == EQUAL_TO_ELE) return poss_cached_; // nonzero element
150  switch(uplow) {
151  case LOWER_ELE: {
152  switch(ele_rel_cached_) {
153  case BEFORE_ELE:
154  return poss_cached_;
155  case AFTER_ELE:
156  return poss_cached_ + 1;
157  }
158  }
159  case UPPER_ELE: {
160  switch(ele_rel_cached_) {
161  case BEFORE_ELE:
162  return poss_cached_ - 1;
163  case AFTER_ELE:
164  return poss_cached_;
165  }
166  }
167  }
168  return 0; // you will never get here but the compiler needs it.
169 }
170 
171 template<class T_Element>
174  index_type index, UpperLower uplow) const
175 {
176 
177  poss_type poss_returned;
178 
179  size_type lower_poss = 0, upper_poss = nz_ - 1;
180 
181  // Look at the end points first then perform the binary search
182 
183  typename T_Element::index_type lower_index = ele()[lower_poss].index() + offset();
184  if(index <= lower_index) { // before or inc. first ele.
185  if(index == lower_index) poss_returned.rel = EQUAL_TO_ELE;
186  else poss_returned.rel = BEFORE_ELE;
187  poss_returned.poss = lower_poss;
188  return poss_returned;
189  }
190 
191  typename T_Element::index_type upper_index = ele()[upper_poss].index() + offset();
192  if(index >= upper_index) { // after or inc. last ele.
193  if(index == upper_index) poss_returned.rel = EQUAL_TO_ELE;
194  else poss_returned.rel = AFTER_ELE;
195  poss_returned.poss = upper_poss;
196  return poss_returned;
197  }
198 
199  // Perform the binary search
200  for(;;) {
201 
202  if(upper_poss == lower_poss + 1) {
203  // This is a zero element that is between these two nonzero elements
204  if(uplow == LOWER_ELE) {
205  poss_returned.rel = BEFORE_ELE;
206  poss_returned.poss = upper_poss;
207  return poss_returned;
208  }
209  else {
210  poss_returned.rel = AFTER_ELE;
211  poss_returned.poss = lower_poss;
212  return poss_returned;
213  }
214  }
215 
216  // Bisect the region
217  size_type mid_poss = (upper_poss - lower_poss) / 2 + lower_poss;
218  typename T_Element::index_type mid_index = ele()[mid_poss].index() + offset();
219 
220  if(mid_index == index) { // The nonzero element exists
221  poss_returned.rel = EQUAL_TO_ELE;
222  poss_returned.poss = mid_poss;
223  return poss_returned;
224  }
225 
226  // update binary search region
227  if(index < mid_index) {
228  upper_poss = mid_poss;
229  upper_index = mid_index;
230  }
231  else {
232  // mid_index < index
233  lower_poss = mid_poss;
234  lower_index = mid_index;
235  }
236  }
237 }
238 
239 #endif // SP_VEC_INDEX_LOOKUP_CLASS_DEF_H
poss_type find_poss(index_type index, UpperLower uplow) const
Lookup an element and cache the result if a binary search was performed.
#define TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test, Exception, msg)
size_t size_type
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.