AbstractLinAlgPack: C++ Interfaces For Vectors, Matrices And Related Linear Algebra Objects Version of the Day
AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp
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 SPVEC_INDEX_LOOKUP_CLASS_DECL_H
00043 #define SPVEC_INDEX_LOOKUP_CLASS_DECL_H
00044 
00045 #include <stdexcept>
00046 
00047 #include "AbstractLinAlgPack_Types.hpp"
00048 
00049 namespace AbstractLinAlgPack {
00050 
00051 namespace SparseVectorUtilityPack {
00052 
00053 // ///////////////////////////////////////////////////////////////////////
00063 template <class T_Element>
00064 class SpVecIndexLookup {
00065 public:
00066 
00069 
00071   typedef T_Element             element_type;
00073   typedef typename element_type::index_type index_type;
00075   typedef ptrdiff_t             difference_type;
00077   class NoSpVecSetException : public std::logic_error
00078   {public: explicit NoSpVecSetException(const std::string& what_arg) : std::logic_error(what_arg) {}};
00080   class InvalidInternalStateException : public std::logic_error
00081   {public: explicit InvalidInternalStateException(const std::string& what_arg) : std::logic_error(what_arg) {}};
00083   enum UpperLower { UPPER_ELE, LOWER_ELE };
00085   enum ElementRelation { BEFORE_ELE, AFTER_ELE, EQUAL_TO_ELE };
00087   struct poss_type {
00088     poss_type() : poss(0), rel(EQUAL_TO_ELE) {} 
00089     poss_type(size_type _poss, ElementRelation _rel) : poss(_poss), rel(_rel) {} 
00090     size_type     poss;
00091     ElementRelation   rel;
00092   };
00093 
00095 
00098 
00100   SpVecIndexLookup()
00101     : ele_(0), nz_(0), offset_(0), index_cached_(0)
00102   {}
00103 
00105   SpVecIndexLookup(element_type* ele, size_type nz, difference_type offset)
00106     : ele_(ele), nz_(nz), offset_(offset), index_cached_(0)
00107   {}
00108 
00110 
00113 
00118   void set_sp_vec(element_type* ele, size_type nz, difference_type offset) {
00119     ele_ = ele;   nz_ = nz;   offset_ = offset;
00120     sp_vec_was_modified();
00121   }
00122 
00124   void incr_nz() {
00125     nz_++;
00126   }
00127 
00129 
00132 
00134   element_type*   ele() const {
00135     return ele_;
00136   }
00138   size_type     nz() const {
00139     return nz_;
00140   }
00142   difference_type   offset() const {
00143     return offset_;
00144   }
00145 
00147 
00150 
00179   poss_type find_poss(index_type index, UpperLower uplow) const;
00180 
00198   size_type find_element( index_type index, bool is_sorted ) const;
00199   
00201 
00204 
00208   void sp_vec_was_modified() {
00209     index_cached_ = 0;
00210   }
00211 
00222   void validate_state() const;
00223 
00225 
00226 private:
00227   // ///////////////////////////////////////////////////////////////////////////////
00228   // Private types
00229 
00230   // //////////////////////////////////////////////////////////////////////////////
00231   // Private data members
00232 
00233   element_type*   ele_;   // pointer to array of elements
00234   size_type     nz_;    // number of nonzero elements in ele_
00235   difference_type   offset_;  // offset for each element in ele_.  The actuall index for
00236                   // each element i is ele_[i].index() + offset().
00237   mutable index_type    index_cached_;  // index of last binary search
00238   mutable size_type   poss_cached_; // possition last looked up
00239   mutable ElementRelation ele_rel_cached_;// Specifies where the element looked up is in relation
00240                       // to the element at poss_cached:
00241                       //    before_ele: zero element before poss_cached_
00242                       //    after_ele:  zero element after poss_cached_
00243                       //    equal_to_ele: nonzero element at poss_cached_
00244 
00245   // ////////////////////////
00246   // Private member functions
00247 
00249   void assert_sp_vec_setup() const {
00250     if(!ele_)
00251       throw NoSpVecSetException("The sparse vector (ele, nz, offset) has not been set yet");
00252   }
00253 
00255   size_type adjust_cached_poss(UpperLower uplow) const;
00256 
00274   poss_type binary_ele_search(index_type index, UpperLower uplow) const;
00275 
00276 
00277 };  // end class SpVecIndexLookup
00278 
00279 } // namespace SparseVectorUtilityPack
00280 
00281 } // end namespace AbstractLinAlgPack
00282 
00283 #endif // SPVEC_INDEX_LOOKUP_CLASS_DECL_H
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends