MOOCHO (Single Doxygen Collection) Version of the Day
AbstractLinAlgPack_SpVecIndexLookupClassDef.hpp
Go to the documentation of this file.
00001 // @HEADER
00002 // ***********************************************************************
00003 // 
00004 // Moocho: Multi-functional Object-Oriented arCHitecture for Optimization
00005 //                  Copyright (2003) Sandia Corporation
00006 // 
00007 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00008 // license for use of this work by or on behalf of the U.S. Government.
00009 // 
00010 // Redistribution and use in source and binary forms, with or without
00011 // modification, are permitted provided that the following conditions are
00012 // met:
00013 //
00014 // 1. Redistributions of source code must retain the above copyright
00015 // notice, this list of conditions and the following disclaimer.
00016 //
00017 // 2. Redistributions in binary form must reproduce the above copyright
00018 // notice, this list of conditions and the following disclaimer in the
00019 // documentation and/or other materials provided with the distribution.
00020 //
00021 // 3. Neither the name of the Corporation nor the names of the
00022 // contributors may be used to endorse or promote products derived from
00023 // this software without specific prior written permission.
00024 //
00025 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00026 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00027 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00028 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00029 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00030 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00031 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00032 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00033 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00034 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00035 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00036 //
00037 // Questions? Contact Roscoe A. Bartlett (rabartl@sandia.gov) 
00038 // 
00039 // ***********************************************************************
00040 // @HEADER
00041 
00042 #ifndef SP_VEC_INDEX_LOOKUP_CLASS_DEF_H
00043 #define SP_VEC_INDEX_LOOKUP_CLASS_DEF_H
00044 
00045 #include "AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp"
00046 #include "AbstractLinAlgPack_compare_element_indexes.hpp"
00047 
00048 // /////////////////////////////////////////////////////////////////////////////////////
00049 // Definitions of members for SpVecIndexLookup<>
00050 
00051 template<class T_Element>
00052 typename AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::poss_type
00053 AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::find_poss(
00054   index_type index, UpperLower uplow) const
00055 {
00056   // First look at the cache.  If it matches then use that information, otherwise
00057   // perform a binary search to find the possition then cache it for latter.
00058 
00059   if(index_cached_) {
00060     if(index == index_cached_)  // Same as cache so use cache
00061       return poss_type(adjust_cached_poss(uplow),ele_rel_cached_);
00062     if(index == index_cached_ + 1 && ele_rel_cached_ == AFTER_ELE
00063       && uplow == LOWER_ELE)
00064     {
00065       // Since poss_cached_ = ( max p s.t. ele_[p].index() < index_cached_ )
00066       // there are three possibilities here:
00067       // Either:
00068 
00069       // a) poss_cashed_ == nz_ - 1
00070       if( poss_cached_ == nz_ - 1 )
00071         return poss_type( poss_cached_ , AFTER_ELE ); 
00072 
00073       // b) ele_[poss_cashed_+1].index() == index
00074       if( ele_[poss_cached_+1].index() == index )
00075         return poss_type( poss_cached_+1 , EQUAL_TO_ELE );
00076 
00077       // c) ele_[poss_cashed_+1].index() > index.
00078       if( ele_[poss_cached_+1].index() > index )
00079         return poss_type( poss_cached_+1 , BEFORE_ELE );
00080     }
00081     if(index == index_cached_ - 1 && ele_rel_cached_ == BEFORE_ELE
00082       && uplow == UPPER_ELE)
00083     {
00084       // Since poss_cached_ = ( max p s.t. ele_[p].index() < index_cached_ )
00085       // there are three possibilities here:
00086       // Either:
00087 
00088       // a) poss_cashed_ == 0
00089       if( poss_cached_ == 0 )
00090         return poss_type( poss_cached_ , BEFORE_ELE );  
00091       
00092       // b) ele_[poss_cashed_-1].index() == index
00093       if( ele_[poss_cached_+1].index() == index )
00094         return poss_type( poss_cached_-1 , EQUAL_TO_ELE );
00095 
00096       // c) ele_[poss_cashed_-1].index() < index.
00097       return poss_type( poss_cached_ - 1, AFTER_ELE); 
00098     }
00099   }
00100 
00101   // Perform binary search for the element
00102   poss_type poss = binary_ele_search(index,uplow);
00103 
00104   // Cache the result if needed.  Don't cache an endpoint
00105   if(poss.poss != 0 && poss.poss != nz() - 1) {
00106     index_cached_ = index;
00107     poss_cached_ = poss.poss;
00108     ele_rel_cached_ = poss.rel;
00109   }
00110 
00111   return poss;
00112 }
00113 
00114 template<class T_Element>
00115 AbstractLinAlgPack::size_type
00116 AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::find_element(
00117   index_type index, bool is_sorted ) const
00118 {
00119   typedef T_Element* itr_t;
00120   if(is_sorted) {
00121     const std::pair<itr_t,itr_t> p = std::equal_range( ele(), ele() + nz()
00122       , index - offset(), compare_element_indexes_less<element_type>() );
00123     // If p.second - p.first == 1 then the element exits
00124     if( p.second - p.first == 1 )
00125       return p.first - ele(); // zero based
00126     else
00127       return nz(); // zero based
00128   }
00129   else {
00130     const itr_t itr = std::find_if( ele(), ele() + nz()
00131       , compare_element_indexes_equal_to<element_type>(index - offset()) );
00132     return itr - ele(); // zero based
00133   }
00134 }
00135 
00136 template<class T_Element>
00137 void
00138 AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::validate_state() const
00139 {
00140   TEUCHOS_TEST_FOR_EXCEPTION( ele() && ele()->index() + offset() < 1, NoSpVecSetException,
00141     "SpVecIndexLookup<T_Element>::validate_state(): Error, ele()->index() + offset() < 1");
00142 }
00143 
00144 template<class T_Element>
00145 AbstractLinAlgPack::size_type
00146 AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::adjust_cached_poss(
00147   UpperLower uplow) const
00148 {
00149   if(ele_rel_cached_ == EQUAL_TO_ELE) return poss_cached_;  // nonzero element
00150   switch(uplow) {
00151     case LOWER_ELE: {
00152       switch(ele_rel_cached_) {
00153         case BEFORE_ELE:
00154           return poss_cached_;
00155         case AFTER_ELE:
00156           return poss_cached_ + 1;
00157       }
00158     }
00159     case UPPER_ELE: {
00160       switch(ele_rel_cached_) {
00161         case BEFORE_ELE:
00162           return poss_cached_ - 1;
00163         case AFTER_ELE:
00164           return poss_cached_;
00165       }
00166     }
00167   }
00168   return 0; // you will never get here but the compiler needs it.
00169 }
00170 
00171 template<class T_Element>
00172 typename AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::poss_type
00173 AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::binary_ele_search(
00174   index_type index, UpperLower uplow) const
00175 {
00176 
00177   poss_type poss_returned;
00178 
00179   size_type lower_poss = 0, upper_poss = nz_ - 1;
00180 
00181   // Look at the end points first then perform the binary search
00182   
00183   typename T_Element::index_type lower_index = ele()[lower_poss].index() + offset();
00184   if(index <= lower_index) {  // before or inc. first ele.
00185     if(index == lower_index)  poss_returned.rel = EQUAL_TO_ELE;
00186     else            poss_returned.rel = BEFORE_ELE;
00187     poss_returned.poss = lower_poss;
00188     return poss_returned;
00189   }
00190 
00191   typename T_Element::index_type upper_index = ele()[upper_poss].index() + offset();
00192   if(index >= upper_index) { // after or inc. last ele.
00193     if(index == upper_index)  poss_returned.rel = EQUAL_TO_ELE;
00194     else            poss_returned.rel = AFTER_ELE;
00195     poss_returned.poss = upper_poss;
00196     return poss_returned;
00197   }
00198 
00199   // Perform the binary search
00200   for(;;) {
00201 
00202     if(upper_poss == lower_poss + 1) {
00203       // This is a zero element that is between these two nonzero elements
00204       if(uplow == LOWER_ELE) {
00205         poss_returned.rel = BEFORE_ELE;
00206         poss_returned.poss = upper_poss;
00207         return poss_returned; 
00208       }
00209       else {
00210         poss_returned.rel = AFTER_ELE;
00211         poss_returned.poss = lower_poss;
00212         return poss_returned;
00213       }
00214     }
00215 
00216     // Bisect the region
00217     size_type mid_poss = (upper_poss - lower_poss) / 2 + lower_poss;
00218     typename T_Element::index_type mid_index = ele()[mid_poss].index() + offset();
00219 
00220     if(mid_index == index) {   // The nonzero element exists
00221       poss_returned.rel = EQUAL_TO_ELE;
00222       poss_returned.poss = mid_poss;
00223       return poss_returned;
00224     }
00225 
00226     // update binary search region
00227     if(index < mid_index) {
00228       upper_poss = mid_poss;
00229       upper_index = mid_index;
00230     }
00231     else {
00232       // mid_index < index
00233       lower_poss = mid_poss;
00234       lower_index = mid_index;
00235     }
00236   }
00237 }
00238 
00239 #endif // SP_VEC_INDEX_LOOKUP_CLASS_DEF_H
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines