AbstractLinAlgPack_SpVecIndexLookupClassDecl.hpp

// @HEADER
// ***********************************************************************
// 
// Moocho: Multi-functional Object-Oriented arCHitecture for Optimization
//                  Copyright (2003) Sandia Corporation
// 
// Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
// license for use of this work by or on behalf of the U.S. Government.
// 
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the Corporation nor the names of the
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Questions? Contact Roscoe A. Bartlett (rabartl@sandia.gov) 
// 
// ***********************************************************************
// @HEADER

#ifndef SPVEC_INDEX_LOOKUP_CLASS_DECL_H
#define SPVEC_INDEX_LOOKUP_CLASS_DECL_H

#include <stdexcept>

#include "AbstractLinAlgPack_Types.hpp"

namespace AbstractLinAlgPack {

namespace SparseVectorUtilityPack {

// ///////////////////////////////////////////////////////////////////////
template <class T_Element>
class SpVecIndexLookup {
public:


  typedef T_Element             element_type;
  typedef typename element_type::index_type index_type;
  typedef ptrdiff_t             difference_type;
  class NoSpVecSetException : public std::logic_error
  {public: explicit NoSpVecSetException(const std::string& what_arg) : std::logic_error(what_arg) {}};
  class InvalidInternalStateException : public std::logic_error
  {public: explicit InvalidInternalStateException(const std::string& what_arg) : std::logic_error(what_arg) {}};
  enum UpperLower { UPPER_ELE, LOWER_ELE };
  enum ElementRelation { BEFORE_ELE, AFTER_ELE, EQUAL_TO_ELE };
  struct poss_type {
    poss_type() : poss(0), rel(EQUAL_TO_ELE) {} 
    poss_type(size_type _poss, ElementRelation _rel) : poss(_poss), rel(_rel) {} 
    size_type     poss;
    ElementRelation   rel;
  };



  SpVecIndexLookup()
    : ele_(0), nz_(0), offset_(0), index_cached_(0)
  {}

  SpVecIndexLookup(element_type* ele, size_type nz, difference_type offset)
    : ele_(ele), nz_(nz), offset_(offset), index_cached_(0)
  {}



  void set_sp_vec(element_type* ele, size_type nz, difference_type offset) {
    ele_ = ele;   nz_ = nz;   offset_ = offset;
    sp_vec_was_modified();
  }

  void incr_nz() {
    nz_++;
  }



  element_type*   ele() const {
    return ele_;
  }
  size_type     nz() const {
    return nz_;
  }
  difference_type   offset() const {
    return offset_;
  }



  poss_type find_poss(index_type index, UpperLower uplow) const;

  size_type find_element( index_type index, bool is_sorted ) const;
  


  void sp_vec_was_modified() {
    index_cached_ = 0;
  }

  void validate_state() const;


private:
  // ///////////////////////////////////////////////////////////////////////////////
  // Private types

  // //////////////////////////////////////////////////////////////////////////////
  // Private data members

  element_type*   ele_;   // pointer to array of elements
  size_type     nz_;    // number of nonzero elements in ele_
  difference_type   offset_;  // offset for each element in ele_.  The actuall index for
                  // each element i is ele_[i].index() + offset().
  mutable index_type    index_cached_;  // index of last binary search
  mutable size_type   poss_cached_; // possition last looked up
  mutable ElementRelation ele_rel_cached_;// Specifies where the element looked up is in relation
                      // to the element at poss_cached:
                      //    before_ele: zero element before poss_cached_
                      //    after_ele:  zero element after poss_cached_
                      //    equal_to_ele: nonzero element at poss_cached_

  // ////////////////////////
  // Private member functions

  void assert_sp_vec_setup() const {
    if(!ele_)
      throw NoSpVecSetException("The sparse vector (ele, nz, offset) has not been set yet");
  }

  size_type adjust_cached_poss(UpperLower uplow) const;

  poss_type binary_ele_search(index_type index, UpperLower uplow) const;


};  // end class SpVecIndexLookup

} // namespace SparseVectorUtilityPack

} // end namespace AbstractLinAlgPack

#endif // SPVEC_INDEX_LOOKUP_CLASS_DECL_H