00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef DJC_COROPA_LIBALGEBRA_SPARSEVECTORH_SEEN
00019 #define DJC_COROPA_LIBALGEBRA_SPARSEVECTORH_SEEN
00020
00022
00041 template<class BASIS, class MAP>
00042 class sparse_vector :
00043 MAP
00044 {
00045 public:
00047 using MAP::begin;
00049 using MAP::end;
00051 using MAP::find;
00053 using MAP::erase;
00055 using MAP::operator [];
00057 using MAP::clear;
00058
00060 void swap (typename sparse_vector & rhs) {
00061 MAP::swap(rhs);
00062 }
00064 typedef typename BASIS::RATIONAL RATIONAL;
00066 typedef typename MAP::key_type KEY;
00068 typedef typename MAP::mapped_type SCALAR;
00070 typedef typename MAP::iterator iterator;
00072 typedef typename MAP::const_iterator const_iterator;
00073 public:
00075 const static SCALAR zero;
00077 const static SCALAR one;
00079 const static SCALAR mone;
00080
00083 static BASIS basis;
00084
00085 public:
00087
00091 sparse_vector(void) {}
00093 sparse_vector(const sparse_vector& v) : MAP(v) {}
00095
00099 explicit sparse_vector(const KEY& k, const SCALAR& s = one)
00100 {
00101 if (s != zero)
00102 (*this)[k] = s;
00103 }
00104 public:
00106 inline sparse_vector operator-(void) const
00107 {
00108 if (empty())
00109 return *this;
00110 const_iterator in;
00111 sparse_vector result;
00112 for (in = begin(); in != end(); ++in)
00113 result[in->first] = -(in->second);
00114 return result;
00115 }
00117 inline sparse_vector& operator*=(const SCALAR& s)
00118 {
00119 if (s != zero)
00120 {
00121 iterator it;
00122 if (!empty())
00123 for (it = begin(); it != end(); ++it)
00124 it->second *= s;
00125 }
00126 else
00127 clear();
00128 return *this;
00129 }
00131 inline __DECLARE_BINARY_OPERATOR(sparse_vector,*,*=,SCALAR)
00133 inline sparse_vector& operator/=(const RATIONAL& s)
00134 {
00135 iterator it;
00136 if (!empty())
00137 for (it = begin(); it != end(); ++it)
00138 {
00139 RATIONAL temp(1);
00140 it->second *= (temp / s);
00141 }
00142 return *this;
00143 }
00145 inline __DECLARE_BINARY_OPERATOR(sparse_vector,/,/=,RATIONAL)
00147 inline sparse_vector& operator+=(const sparse_vector& rhs)
00148 {
00149 iterator it;
00150 const_iterator cit;
00151 if (rhs.empty())
00152 return *this;
00153 if (empty())
00154 return *this = rhs;
00155 for (cit = rhs.begin(); cit != rhs.end(); ++cit)
00156 {
00157 it = find(cit->first);
00158 if (it == end())
00159 (*this)[cit->first] = cit->second;
00160 else if ((it->second += cit->second) == zero)
00161 erase(it->first);
00162 }
00163 return *this;
00164 }
00166 inline __DECLARE_BINARY_OPERATOR(sparse_vector,+,+=,sparse_vector)
00168 inline sparse_vector& operator-=(const sparse_vector& rhs)
00169 {
00170 iterator it;
00171 const_iterator cit;
00172 if (rhs.empty())
00173 return *this;
00174 if (empty())
00175 return *this = -rhs;
00176 for (cit = rhs.begin(); cit != rhs.end(); ++cit)
00177 {
00178 it = find(cit->first);
00179 if (it == end())
00180 (*this)[cit->first] = -(cit->second);
00181 else if ((it->second -= cit->second) == zero)
00182 erase(it->first);
00183 }
00184 return *this;
00185 }
00187 inline __DECLARE_BINARY_OPERATOR(sparse_vector,-,-=,sparse_vector)
00188
00189
00190 inline sparse_vector& add_scal_prod(const sparse_vector& rhs,
00191 const SCALAR& s)
00192 {
00193 iterator it;
00194 const_iterator cit;
00195 if ((s == zero) || rhs.empty())
00196 return *this;
00197 if (empty())
00198 {
00199 *this = rhs;
00200 return operator *= (s);
00201 }
00202 for (cit = rhs.begin(); cit != rhs.end(); ++cit)
00203 {
00204 it = find(cit->first);
00205 if (it == end())
00206 (*this)[cit->first] = cit->second * s;
00207 else if ((it->second += cit->second * s) == zero)
00208 erase(it->first);
00209 }
00210 return *this;
00211 }
00213 inline sparse_vector& sub_scal_prod(const sparse_vector& rhs,
00214 const SCALAR& s)
00215 {
00216 iterator it;
00217 const_iterator cit;
00218 if ((s == zero) || rhs.empty())
00219 return *this;
00220 if (empty())
00221 {
00222 *this = rhs;
00223 return operator *= (-s);
00224 }
00225 for (cit = rhs.begin(); cit != rhs.end(); ++cit)
00226 {
00227 it = find(cit->first);
00228 if (it == end())
00229 (*this)[cit->first] = cit->second * -s;
00230 else if ((it->second -= cit->second * s) == zero)
00231 erase(it->first);
00232 }
00233 return *this;
00234 }
00236 inline sparse_vector& add_scal_div(const sparse_vector& rhs,
00237 const RATIONAL& s)
00238 {
00239 iterator it;
00240 const_iterator cit;
00241 if (rhs.empty())
00242 return *this;
00243 if (empty())
00244 {
00245 *this = rhs;
00246 return operator /= (s);
00247 }
00248 for (cit = rhs.begin(); cit != rhs.end(); ++cit)
00249 {
00250 it = find(cit->first);
00251 if (it == end())
00252 (*this)[cit->first] = cit->second / s;
00253 else if ((it->second += (cit->second / s)) == zero)
00254 erase(it->first);
00255 }
00256 return *this;
00257 }
00259 inline sparse_vector& sub_scal_div(const sparse_vector& rhs,
00260 const RATIONAL& s)
00261 {
00262 iterator it;
00263 const_iterator cit;
00264 if (rhs.empty())
00265 return *this;
00266 if (empty())
00267 {
00268 *this = rhs;
00269 return operator /= (-s);
00270 }
00271 for (cit = rhs.begin(); cit != rhs.end(); ++cit)
00272 {
00273 it = find(cit->first);
00274 if (it == end())
00275 (*this)[cit->first] = - cit->second / s;
00276 else if ((it->second -= (cit->second / s)) == zero)
00277 erase(it->first);
00278 }
00279 return *this;
00280 }
00282 bool operator==(const sparse_vector& rhs) const
00283 {
00284 if (size() != rhs.size())
00285 return false;
00286 const_iterator i, j;
00287 for (i = begin(); i != end(); ++i)
00288 {
00289 j = rhs.find(i->first);
00290 if ((j == rhs.end()) || (j->second != i->second))
00291 return false;
00292 }
00293 return true;
00294 }
00296 bool operator < (const sparse_vector& rhs) const
00297 {
00298 return std::lexicographical_compare(begin(), end(), rhs.begin(), rhs.end());
00299 }
00301 bool operator!=(const sparse_vector& rhs) const
00302 {
00303 return !operator == (rhs);
00304 }
00306 inline SCALAR NormL1() const
00307 {
00308 const_iterator i;
00309 SCALAR ans(zero);
00310 for (i = begin(); i != end(); ++i)
00311 {
00312 ans += abs(i->second);
00313 }
00314 return ans;
00315 }
00317 inline SCALAR NormL1(const DEG & d) const
00318 {
00319 const_iterator i;
00320 SCALAR ans(zero);
00321 for (i = begin(); i != end(); ++i)
00322 {
00323 if (d == basis.degree(i->first))
00324 ans += abs(i->second);
00325 }
00326 return ans;
00327 }
00329
00333 inline friend std::ostream& operator<<(std::ostream& os,
00334 const sparse_vector& rhs)
00335 {
00336 const_iterator cit;
00337 std::pair<BASIS*, KEY> token;
00338 token.first = &sparse_vector::basis;
00339 os << '{';
00340 for (cit = rhs.begin(); cit != rhs.end(); ++cit)
00341 {
00342 token.second = cit->first;
00343 os << ' ' << cit->second << '(' << token << ')';
00344 }
00345 os << " }";
00346 return os;
00347 }
00348 };
00349
00350
00351
00353 template<class BASIS, class MAP>
00354 BASIS sparse_vector<BASIS, MAP>::basis;
00355
00357 template<class BASIS, class MAP>
00358 typename
00359 const MAP::mapped_type sparse_vector<BASIS, MAP>::one(+1);
00360
00362 template<class BASIS, class MAP>
00363 typename
00364 const MAP::mapped_type sparse_vector<BASIS, MAP>::zero(0);
00365
00367 template<class BASIS, class MAP>
00368 typename
00369 const MAP::mapped_type sparse_vector<BASIS, MAP>::mone(-1);
00370
00371
00372
00373 #endif
00374
00375
00376