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.
// 
// This library is free software; you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation; either version 2.1 of the
// License, or (at your option) any later version.
//  
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//  
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
// USA
// 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