linalg_vec.h

强大的矩阵模版类

//
// Copyright 1997, 1998, 1999 University of Notre Dame.
// Authors: Andrew Lumsdaine, Jeremy G. Siek, Lie-Quan Lee
//
// This file is part of the Matrix Template Library
//
// You should have received a copy of the License Agreement for the
// Matrix Template Library along with the software;  see the
// file LICENSE.  If not, contact Office of Research, University of Notre
// Dame, Notre Dame, IN  46556.
//
// Permission to modify the code and to distribute modified code is
// granted, provided the text of this NOTICE is retained, a notice that
// the code was modified is included with the above COPYRIGHT NOTICE and
// with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
// file is distributed with the modified code.
//
// LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
// By way of example, but not limitation, Licensor MAKES NO
// REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
// PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
// OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
// OR OTHER RIGHTS.
//
//===========================================================================

#ifndef MTL_LINALG_VECTOR_H
#define MTL_LINALG_VECTOR_H


#include <utility>
#include <vector>

#include "mtl/refcnt_ptr.h"
#include "mtl/dense_iterator.h"
#include "mtl/reverse_iter.h"
#include "mtl/light1D.h"
#include "mtl/mtl_config.h"
#include "mtl/matrix_traits.h"
#include "mtl/scaled1D.h"
#include "mtl/mtl_exception.h"
#include "mtl/external_vector.h"


namespace mtl {

  //: Linalg Vector Adaptor
  //!category: containers, adaptors
  //!component: type
  //
  // This captures the main functionality of a dense MTL vector.  The
  // dense1D and external1D derive from this class, and specialize
  // this class to use either internal or external storage.
  //
  //!definition: linalg_vector.h
  //!tparam: RepType - the underlying representation
  //!models: Linalg_Vector

template <class RepType, class RepPtr = RepType*, int NN = 0>
class linalg_vec {
public:
  typedef linalg_vec self;
  typedef RepType rep_type;
  typedef RepPtr rep_ptr;

  enum { N = NN };

  /**@name Type Definitions */

  /*  enum { dimension = 1 }; */
  typedef oned_tag dimension;

  //: The sparsity tag
  typedef dense_tag sparsity;

  //: The scaled type of this container
  //!wheredef: Scalable
  typedef scaled1D< self > scaled_type;

  //: The value type
  //!wheredef: Container
  typedef typename rep_type::value_type value_type;

  //: The reference type
  //!wheredef: Container
  typedef typename rep_type::reference reference;

  //: The const reference type
  //!wheredef: Container
  typedef typename rep_type::const_reference const_reference;

  //: The pointer (to the value_type) type
  //!wheredef: Container
  typedef typename rep_type::pointer pointer;

  //: The size type (non negative)
  //!wheredef: Container
  typedef typename rep_type::size_type size_type;

  //: The difference type (an integral type)
  //!wheredef: Container
  typedef typename rep_type::difference_type difference_type;

#if !defined( _MSVCPP_ )
  //: The iterator type
  //!wheredef: Container
  typedef dense_iterator<typename rep_type::iterator> iterator;

  //: The const iterator type
  //!wheredef: Container
  typedef dense_iterator<typename rep_type::const_iterator> const_iterator;
#else
  typedef dense_iterator<typename rep_type::value_type, 0, 0, size_type> iterator;
  typedef dense_iterator<typename rep_type::value_type, 1, 0, size_type> const_iterator;
#endif
  //: The reverse iterator type
  //!wheredef: Reversible Container
  typedef reverse_iter<iterator> reverse_iterator;

  //: The const reverse iterator type
  //!wheredef: Reversible Container
  typedef reverse_iter<const_iterator> const_reverse_iterator;

  /* skip over the zeros and report the indices
     this implements the nonzero structure array
     */
  typedef linalg_vec<RepType, RepPtr, NN> Vec;

  typedef size_type Vec_size_type;
  typedef difference_type Vec_difference_type;
  typedef iterator Vec_iterator;
  typedef const_iterator Vec_const_iterator;

  class IndexArray {
  public:

    typedef Vec_size_type size_type;
    typedef Vec_difference_type difference_type;
    typedef Vec_size_type value_type;

    class iterator {
    public:
      typedef size_type value_type;
      typedef size_type reference;
      typedef size_type* pointer;
      typedef Vec_difference_type difference_type;
      typedef typename std::iterator_traits<Vec_iterator>::iterator_category iterator_category;
      iterator(Vec_iterator iter, Vec_iterator e) : i(iter), end(e) {
	while (*i == Vec_value_type(0)) ++i;
      }
      reference operator*() const { return i.index(); }
      iterator& operator++() { 
	++i; while (*i == Vec_value_type(0) && i != end) ++i;
	return *this; }
      iterator operator++(int) { iterator t = *this; ++(*this); return t; }
      iterator& operator--() { 
	--i; while (*i == Vec_value_type(0) && i != end) --i;
	return *this; }
      iterator operator--(int) { iterator t = *this; --(*this); return t; }
      difference_type operator-(const iterator& x) const { return i - x.i; }
      bool operator==(const iterator& x) const { return i == x.i; }
      bool operator!=(const iterator& x) const { return i != x.i; }
      bool operator<(const iterator& x) const { return i < x.i; }
      Vec_iterator i;
      Vec_iterator end;
    };
    class const_iterator {
    public:
      typedef size_type value_type;
      typedef size_type reference;
      typedef size_type* pointer;
      typedef Vec_difference_type difference_type;
      typedef typename std::iterator_traits<Vec_iterator>::iterator_category iterator_category;
      const_iterator(Vec_const_iterator iter, Vec_const_iterator e)
	: i(iter), end(e) { 
	while (*i == Vec_value_type(0) && i != end) ++i;
      }
      reference operator*() const { return i.index(); }
      const_iterator& operator++() { 
	++i; while (*i == Vec_value_type(0) && i != end) ++i;
	return *this; }
      const_iterator operator++(int) { 
	const_iterator t = *this; ++(*this); return t; }
      const_iterator& operator--() { 
	--i; while (*i == Vec_value_type(0)) --i;
	return *this; }
      const_iterator operator--(int) { 
	const_iterator t = *this; --(*this); return t; }
      difference_type operator-(const const_iterator& x) const { 
	return i - x.i; }
      bool operator==(const const_iterator& x) const { return i == x.i; }
      bool operator!=(const const_iterator& x) const { return i != x.i; }
      bool operator<(const const_iterator& x) const { return i < x.i; }
      Vec_const_iterator i;
      Vec_const_iterator end;
    };

    inline IndexArray(const Vec& v) : vec((Vec*)&v) { }
    inline iterator begin() { return iterator(vec->begin(), vec->end()); }
    inline iterator end() { return iterator(vec->end(), vec->end()); }
    inline const_iterator begin() const{ 
      return const_iterator(((const Vec*)vec)->begin(), 
			    ((const Vec*)vec)->end()); 
    }
    inline const_iterator end() const { 
      return const_iterator(((const Vec*)vec)->end(), 
			    ((const Vec*)vec)->end()); }

    size_type size() const {
      size_type s = 0;
      Vec_const_iterator i;
      for (i = ((const Vec*)vec)->begin(); i != ((const Vec*)vec)->end(); ++i)
	if (*i != Vec_value_type(0)) ++s;
      return s;
    }

    Vec* vec;
  };

  //: The type for an array of the indices of the element in the vector
  //!wheredef: Vector
  typedef IndexArray IndexArrayRef;

  //: The type for a subrange vector-view of the original vector  
  //!wheredef: Vector
  typedef light1D<value_type> subrange_type;

  typedef std::pair<size_type, size_type> range;

  /**@name Constructors */
  
  //: Default Constructor (allocates the container)
  //!wheredef: Container
  inline linalg_vec() : rep(0) { }

  //: Normal Constructor
  inline linalg_vec(rep_ptr x, size_type start_index)
    : rep(x), first(start_index) { }

  //: Copy Constructor  (shallow copy)
  //!wheredef: ContainerRef
  inline linalg_vec(const self& x) : rep(x.rep), first(x.first) { }

  //: The destructor.
  //!wheredef: Container
  inline ~linalg_vec() { }  

  //: Assignment Operator (shallow copy)
  //!wheredef: AssignableRef
  inline self& operator=(const self& x) { 
    rep = x.rep;
    first = x.first;
    return *this; 
  }

  /**@name Access Methods */
  
  /**@name Iterator Access Methods */
  
  //: Return an iterator pointing to the beginning of the vector
  //!wheredef: Container
  inline iterator begin() { return iterator(rep->begin(), 0, first); }
  //: Return an iterator pointing past the end of the vector
  //!wheredef: Container
  inline iterator end() { return iterator(rep->begin(), rep->size(), first); }
  //: Return a const iterator pointing to the begining of the vector
  //!wheredef: Container
  inline const_iterator begin() const { return const_iterator(rep->begin(), 
							      0, first); }
  //: Return a const iterator pointing past the end of the vector
  //!wheredef: Container
  inline const_iterator end() const{ return const_iterator(rep->begin(),
						       rep->size(), first); }
  //: Return a reverse iterator pointing to the last element of the vector
  //!wheredef: Reversible Container
  inline reverse_iterator rbegin() { return reverse_iterator(end()); }
  //: Return a reverse iterator pointing past the end of the vector
  //!wheredef: Reversible Container
  inline reverse_iterator rend() { return reverse_iterator(begin()); }
  //: Return a const reverse iterator pointing to the last element of the vector
  //!wheredef: Reversible Container
  inline const_reverse_iterator rbegin() const { 
    return reverse_iterator(end()); }
  //: Return a const reverse iterator pointing past the end of the vector
  //!wheredef: Reversible Container
  inline const_reverse_iterator rend() const{ 
    return reverse_iterator(begin()); }
  
  /**@name Element Access Methods */
  

  //: Return a reference to the element with the ith index
  //!wheredef: Vector
  inline reference operator[](size_type i) MTL_THROW_ASSERTION {
    MTL_ASSERT(i < size(), "linalg_vec::operator[]");
    return (*rep)[i - first];
  }

  inline subrange_type operator()(range r) MTL_THROW_ASSERTION {
    return subrange_type(data() + r.first, r.second - r.first);