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 // This library is free software; you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as
00012 // published by the Free Software Foundation; either version 2.1 of the
00013 // License, or (at your option) any later version.
00014 //  
00015 // This library is distributed in the hope that it will be useful, but
00016 // WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018 // Lesser General Public License for more details.
00019 //  
00020 // You should have received a copy of the GNU Lesser General Public
00021 // License along with this library; if not, write to the Free Software
00022 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
00023 // USA
00024 // Questions? Contact Roscoe A. Bartlett (rabartl@sandia.gov) 
00025 // 
00026 // ***********************************************************************
00027 // @HEADER
00028 
00029 #ifndef SP_VEC_INDEX_LOOKUP_CLASS_DEF_H
00030 #define SP_VEC_INDEX_LOOKUP_CLASS_DEF_H
00031 
00032 #include "AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp"
00033 #include "AbstractLinAlgPack_compare_element_indexes.hpp"
00034 
00035 // /////////////////////////////////////////////////////////////////////////////////////
00036 // Definitions of members for SpVecIndexLookup<>
00037 
00038 template<class T_Element>
00039 typename AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::poss_type
00040 AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::find_poss(
00041   index_type index, UpperLower uplow) const
00042 {
00043   // First look at the cache.  If it matches then use that information, otherwise
00044   // perform a binary search to find the possition then cache it for latter.
00045 
00046   if(index_cached_) {
00047     if(index == index_cached_)  // Same as cache so use cache
00048       return poss_type(adjust_cached_poss(uplow),ele_rel_cached_);
00049     if(index == index_cached_ + 1 && ele_rel_cached_ == AFTER_ELE
00050       && uplow == LOWER_ELE)
00051     {
00052       // Since poss_cached_ = ( max p s.t. ele_[p].index() < index_cached_ )
00053       // there are three possibilities here:
00054       // Either:
00055 
00056       // a) poss_cashed_ == nz_ - 1
00057       if( poss_cached_ == nz_ - 1 )
00058         return poss_type( poss_cached_ , AFTER_ELE ); 
00059 
00060       // b) ele_[poss_cashed_+1].index() == index
00061       if( ele_[poss_cached_+1].index() == index )
00062         return poss_type( poss_cached_+1 , EQUAL_TO_ELE );
00063 
00064       // c) ele_[poss_cashed_+1].index() > index.
00065       if( ele_[poss_cached_+1].index() > index )
00066         return poss_type( poss_cached_+1 , BEFORE_ELE );
00067     }
00068     if(index == index_cached_ - 1 && ele_rel_cached_ == BEFORE_ELE
00069       && uplow == UPPER_ELE)
00070     {
00071       // Since poss_cached_ = ( max p s.t. ele_[p].index() < index_cached_ )
00072       // there are three possibilities here:
00073       // Either:
00074 
00075       // a) poss_cashed_ == 0
00076       if( poss_cached_ == 0 )
00077         return poss_type( poss_cached_ , BEFORE_ELE );  
00078       
00079       // b) ele_[poss_cashed_-1].index() == index
00080       if( ele_[poss_cached_+1].index() == index )
00081         return poss_type( poss_cached_-1 , EQUAL_TO_ELE );
00082 
00083       // c) ele_[poss_cashed_-1].index() < index.
00084       return poss_type( poss_cached_ - 1, AFTER_ELE); 
00085     }
00086   }
00087 
00088   // Perform binary search for the element
00089   poss_type poss = binary_ele_search(index,uplow);
00090 
00091   // Cache the result if needed.  Don't cache an endpoint
00092   if(poss.poss != 0 && poss.poss != nz() - 1) {
00093     index_cached_ = index;
00094     poss_cached_ = poss.poss;
00095     ele_rel_cached_ = poss.rel;
00096   }
00097 
00098   return poss;
00099 }
00100 
00101 template<class T_Element>
00102 AbstractLinAlgPack::size_type
00103 AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::find_element(
00104   index_type index, bool is_sorted ) const
00105 {
00106   typedef T_Element* itr_t;
00107   if(is_sorted) {
00108     const std::pair<itr_t,itr_t> p = std::equal_range( ele(), ele() + nz()
00109       , index - offset(), compare_element_indexes_less<element_type>() );
00110     // If p.second - p.first == 1 then the element exits
00111     if( p.second - p.first == 1 )
00112       return p.first - ele(); // zero based
00113     else
00114       return nz(); // zero based
00115   }
00116   else {
00117     const itr_t itr = std::find_if( ele(), ele() + nz()
00118       , compare_element_indexes_equal_to<element_type>(index - offset()) );
00119     return itr - ele(); // zero based
00120   }
00121 }
00122 
00123 template<class T_Element>
00124 void
00125 AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::validate_state() const
00126 {
00127   TEST_FOR_EXCEPTION( ele() && ele()->index() + offset() < 1, NoSpVecSetException,
00128     "SpVecIndexLookup<T_Element>::validate_state(): Error, ele()->index() + offset() < 1");
00129 }
00130 
00131 template<class T_Element>
00132 AbstractLinAlgPack::size_type
00133 AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::adjust_cached_poss(
00134   UpperLower uplow) const
00135 {
00136   if(ele_rel_cached_ == EQUAL_TO_ELE) return poss_cached_;  // nonzero element
00137   switch(uplow) {
00138     case LOWER_ELE:
00139       switch(ele_rel_cached_) {
00140         case BEFORE_ELE:
00141           return poss_cached_;
00142         case AFTER_ELE:
00143           return poss_cached_ + 1;
00144       }
00145     case UPPER_ELE:
00146       switch(ele_rel_cached_) {
00147         case BEFORE_ELE:
00148           return poss_cached_ - 1;
00149         case AFTER_ELE:
00150           return poss_cached_;
00151       }
00152   }
00153   return 0; // you will never get here but the compiler needs it.
00154 }
00155 
00156 template<class T_Element>
00157 typename AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::poss_type
00158 AbstractLinAlgPack::SparseVectorUtilityPack::SpVecIndexLookup<T_Element>::binary_ele_search(
00159   index_type index, UpperLower uplow) const
00160 {
00161 
00162   poss_type poss_returned;
00163 
00164   size_type lower_poss = 0, upper_poss = nz_ - 1;
00165 
00166   // Look at the end points first then perform the binary search
00167   
00168   typename T_Element::index_type lower_index = ele()[lower_poss].index() + offset();
00169   if(index <= lower_index) {  // before or inc. first ele.
00170     if(index == lower_index)  poss_returned.rel = EQUAL_TO_ELE;
00171     else            poss_returned.rel = BEFORE_ELE;
00172     poss_returned.poss = lower_poss;
00173     return poss_returned;
00174   }
00175 
00176   typename T_Element::index_type upper_index = ele()[upper_poss].index() + offset();
00177   if(index >= upper_index) { // after or inc. last ele.
00178     if(index == upper_index)  poss_returned.rel = EQUAL_TO_ELE;
00179     else            poss_returned.rel = AFTER_ELE;
00180     poss_returned.poss = upper_poss;
00181     return poss_returned;
00182   }
00183 
00184   // Perform the binary search
00185   for(;;) {
00186 
00187     if(upper_poss == lower_poss + 1) {
00188       // This is a zero element that is between these two nonzero elements
00189       if(uplow == LOWER_ELE) {
00190         poss_returned.rel = BEFORE_ELE;
00191         poss_returned.poss = upper_poss;
00192         return poss_returned; 
00193       }
00194       else {
00195         poss_returned.rel = AFTER_ELE;
00196         poss_returned.poss = lower_poss;
00197         return poss_returned;
00198       }
00199     }
00200 
00201     // Bisect the region
00202     size_type mid_poss = (upper_poss - lower_poss) / 2 + lower_poss;
00203     typename T_Element::index_type mid_index = ele()[mid_poss].index() + offset();
00204 
00205     if(mid_index == index) {   // The nonzero element exists
00206       poss_returned.rel = EQUAL_TO_ELE;
00207       poss_returned.poss = mid_poss;
00208       return poss_returned;
00209     }
00210 
00211     // update binary search region
00212     if(index < mid_index) {
00213       upper_poss = mid_poss;
00214       upper_index = mid_index;
00215     }
00216     else {
00217       // mid_index < index
00218       lower_poss = mid_poss;
00219       lower_index = mid_index;
00220     }
00221   }
00222 }
00223 
00224 #endif // SP_VEC_INDEX_LOOKUP_CLASS_DEF_H

Generated on Tue Oct 20 12:51:44 2009 for MOOCHO (Single Doxygen Collection) by doxygen 1.4.7