00001 #ifndef TNT_SPARSE_VECTOR_H
00002 #define TNT_SPARSE_VECTOR_H
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #include <vector>
00026 #include "tnt_vector.h"
00027
00028 namespace TNT
00029 {
00030
00031
00032
00033
00034
00035 template <class T, class Integer>
00036 class Sparse_Vector_Element
00037 {
00038 private:
00039
00040 T val_;
00041 Integer index_;
00042
00043 public:
00044
00045 Sparse_Vector_Element(const T& a, const Integer &i) :
00046 val_(a), index_(i) {}
00047
00048
00049 const T& value() const { return val_; }
00050 Integer index() const { return index_; }
00051
00052 T& value() { return val_; }
00053 Integer& index() { return index_; }
00054
00055
00056
00057 };
00058
00059
00075 template <class T>
00076 class Sparse_Vector
00077 {
00078
00079
00080 private:
00081
00082
00083
00084 std::vector< Sparse_Vector_Element<T, Subscript> > s_;
00085
00086 int dim_;
00087 int num_nonzeros_;
00088
00089
00090
00091
00092 public:
00093 typedef typename
00094 std::vector< Sparse_Vector_Element<T, Subscript> >::const_iterator
00095 const_iterator;
00096
00097
00098 const_iterator begin() const { return s_.begin(); }
00099 const_iterator end() const { return s_.end(); }
00100
00101 inline const T& value(Subscript i) const { return s_[i].value(); }
00102 inline Subscript index(Subscript i) const {return s_[i].index(); }
00103
00104 inline T dot_product(const Vector<T>& x) const
00105 {
00106 T sum(0);
00107
00108 for ( const_iterator p = begin(); p < end(); p++)
00109 {
00110 sum += p->value() * x[p->index()];
00111 }
00112 return sum;
00113 }
00114
00115 Sparse_Vector() : s_(), dim_(0), num_nonzeros_(0) {}
00116 Sparse_Vector(Subscript N): dim_(N), num_nonzeros_(0) {}
00117
00118
00119
00120 Sparse_Vector(Subscript N, Subscript nz, const T* Val, const Subscript *I):
00121 dim_(N),
00122 num_nonzeros_(0)
00123 {
00124 insert(nz, Val, I);
00125 }
00126
00127
00128
00129 void insert(const T& val, Subscript i)
00130 {
00131
00132 s_.push_back( Sparse_Vector_Element<T, Subscript>(val,i) );
00133 num_nonzeros_++;
00134 }
00135
00136 void insert(Subscript nz, const T* Val, const Subscript *I)
00137 {
00138
00139 for (int count=0; count<nz; count++)
00140 {
00141 insert(Val[count], I[count]);
00142 }
00143 }
00144
00145
00146 void insert_base_one(const T& val, Subscript i)
00147 {
00148 insert(val, i-1);
00149 }
00150
00151 void insert_base_one(Subscript nz, const T* Val, const Subscript *I)
00152 {
00153 for (int count=0; count<nz; count++)
00154 {
00155 insert(Val[count], I[count]-1);
00156 }
00157 }
00158
00159
00160
00161 inline int dim() const {return dim_;}
00162 int num_nonzeros() const {return num_nonzeros_;}
00163
00164
00165
00166
00167 inline double norm() const
00168 {
00169 T sum(0.0);
00170
00171 for (const_iterator p = begin(); p < end(); p++)
00172 {
00173 sum += p->value() * p->value();
00174 }
00175
00176 return sqrt(sum);
00177 }
00178
00179 std::ostream & print(std::ostream &s) const
00180 {
00181 for (typename Sparse_Vector<T>::const_iterator p = begin();
00182 p < end(); p++)
00183 {
00184 s << "( " << p->value() << ", " << p->index() << " ) \n";
00185 }
00186 return s;
00187 }
00188
00189 std::ostream & print_base_one(std::ostream &s) const
00190 {
00191 for (typename Sparse_Vector<T>::const_iterator p = begin();
00192 p < end(); p++)
00193 {
00194 s << "( " << p->value() << ", " << p->index()+1 << " ) \n";
00195 }
00196 return s;
00197 }
00198
00199
00200 };
00201
00202
00203
00204 template <class T>
00205 inline T dot_product(const Sparse_Vector<T> &s, const Vector<T> &x)
00206 {
00207 return s.dot_product(x);
00208 }
00209
00210 template <class T>
00211 inline T dot_product(const Vector<T> &x, const Sparse_Vector<T> &s)
00212 {
00213 return s.dot_product(x);
00214 }
00215
00216 template <class T>
00217 inline T operator*(const Vector<T> &x, const Sparse_Vector<T> &s)
00218 {
00219 return dot_product(x,s);
00220 }
00221
00222 template <class T>
00223 inline T operator*(const Sparse_Vector<T> &s, const Vector<T> &x)
00224 {
00225 return dot_product(x,s);
00226 }
00227
00228
00229 template <class T>
00230 inline double norm( const Sparse_Vector<T> & s)
00231 {
00232 return s.norm();
00233 }
00234
00235
00236 template <class T>
00237 std::ostream& operator<<(std::ostream &s, const Sparse_Vector<T> &A)
00238 {
00239
00240 return A.print(s);
00241 }
00242
00243
00244
00245 }
00246
00247 #endif
00248