1/* Copyright (C) LinBox 2 * 3 * 4 * 5 * ========LICENCE======== 6 * This file is part of the library LinBox. 7 * 8 * LinBox is free software: you can redistribute it and/or modify 9 * it under the terms of the GNU Lesser General Public 10 * License as published by the Free Software Foundation; either 11 * version 2.1 of the License, or (at your option) any later version. 12 * 13 * This library is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * Lesser General Public License for more details. 17 * 18 * You should have received a copy of the GNU Lesser General Public 19 * License along with this library; if not, write to the Free Software 20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 21 * ========LICENCE======== 22 */ 23 24/*! @file blackbox/zo-gf2.inl 25 * @ingroup blackbox 26 * @brief NO DOC 27 */ 28 29#ifndef __LINBOX_zo_gf2_INL 30#define __LINBOX_zo_gf2_INL 31 32#include <givaro/givintfactor.h> 33 34namespace LinBox 35{ 36 // Dot product structure enabling std::transform call 37 template<class Blackbox, class InVector> 38 struct dotp { 39 const typename Blackbox::Field& _field; 40 const InVector& _x; 41 dotp(const typename Blackbox::Field& F, const InVector& x) : 42 _field(F), _x(x) 43 {} 44 45 46 bool operator()(const typename Blackbox::Row_t& row) const 47 { 48 bool tmp(false); 49 for(typename Blackbox::Row_t::const_iterator loc = row.begin(); loc != row.end(); ++loc) { 50 _field.addin(tmp,_x.at(*loc)); 51 } 52 return tmp; 53 } 54 }; 55 56#include <algorithm> 57 template<class OutVector, class InVector> 58 inline OutVector & ZeroOne<GF2>::apply(OutVector & y, const InVector & x) const 59 { 60 dotp<Self_t,InVector> mydp(this->field(), x); 61 std::transform(this->begin(), this->end(), y.begin(), mydp ); 62 return y; 63 } 64 65#if 0 66 template<class OutVector, class InVector> 67 inline OutVector & ZeroOne<GF2>::apply(OutVector & y, const InVector & x) const 68 { 69 typename OutVector::iterator yit = y.begin(); 70 Self_t::const_iterator row = this->begin(); 71 for( ; row != this->end(); ++yit, ++row) { 72 bool tmp(false); 73 for(Row_t::const_iterator loc = row->begin();loc != row->end(); ++loc) 74 field().addin(tmp,x[*loc]); 75 *yit = tmp; 76 } 77 return y; 78 } 79#endif 80 81 template<class OutVector, class InVector> 82 inline OutVector & ZeroOne<GF2>::applyTranspose(OutVector & y, const InVector & x) const 83 { 84 std::fill(y.begin(),y.end(),false); 85 typename InVector::const_iterator xit = x.begin(); 86 Self_t::const_iterator row = this->begin(); 87 for( ; row != this->end(); ++row, ++xit) { 88 for(typename Self_t::Row_t::const_iterator loc = row->begin(); loc != row->end(); ++loc) { 89 field().addin(y[*loc],*xit); 90 } 91 } 92 return y; 93 } 94 95 96 inline const ZeroOne<GF2>::Element& ZeroOne<GF2>::setEntry(size_t i, size_t j, const Element& v) { 97 Row_t& rowi = this->operator[](i); 98 Row_t::iterator there = std::lower_bound(rowi.begin(), rowi.end(), j); 99 if (! field().isZero(v) ) { 100 if ( (there == rowi.end() ) || (*there != j) ) { 101 rowi.insert(there, j); 102 ++_nnz; 103 } 104 } 105 else { 106 if ( (there != rowi.end() ) && (*there == j) ) { 107 rowi.erase(there); 108 --_nnz; 109 } 110 } 111 return v; 112 } 113 114 inline ZeroOne<GF2>::Element& ZeroOne<GF2>::getEntry(Element& r, size_t i, size_t j) const 115 { 116 const Row_t& rowi = this->operator[](i); 117 Row_t::const_iterator there = std::lower_bound(rowi.begin(), rowi.end(), j); 118 if (there != rowi.end() ) 119 return r=*there; 120 else 121 return r=field().zero; 122 } 123 124 inline const ZeroOne<GF2>::Element& ZeroOne<GF2>::getEntry(size_t i, size_t j) const 125 { 126 const Row_t& rowi = this->operator[](i); 127 Row_t::const_iterator there = std::lower_bound(rowi.begin(), rowi.end(), j); 128 if (there != rowi.end() ) 129 return reinterpret_cast<const ZeroOne<GF2>::Element&>(*there); 130 else 131 return field().zero; 132 } 133 134 inline std::istream &ZeroOne<GF2>::read (std::istream &is) { 135 // Reads a long int and take it mod 2 afterwards (v&1) 136 Givaro::ZRing<int64_t> Ints; 137 MatrixStream<Givaro::ZRing<int64_t> > S(Ints, is); 138 S.getDimensions( _rowdim, _coldim ); 139 this->resize(_rowdim); 140 Index r, c; 141 int64_t v; 142 _nnz = 0; 143 while( S.nextTriple(r, c, v) ) { 144 if (v&1) { 145 this->operator[](r).push_back(c); 146 ++_nnz; 147 } 148 } 149 for(Father_t::iterator i=this->begin(); i!=this->end(); ++i) 150 std::sort(i->begin(),i->end()); 151 return is; 152 } 153 154 inline std::ostream& ZeroOne<GF2>::write (std::ostream& out, Tag::FileFormat format) const 155 { 156 if (format == Tag::FileFormat::Guillaume) { 157 out << _rowdim << ' ' << _coldim << " M\n"; 158 for(size_t i=0; i<_rowdim; ++i) { 159 const Row_t& rowi = this->operator[](i); 160 for(Row_t::const_iterator it=rowi.begin(); it != rowi.end(); ++it) 161 out << (i+1) << ' ' << (*it+1) << " 1\n"; 162 } 163 return out << "0 0 0" << std::endl; 164 } 165 else if (format == Tag::FileFormat::Maple) { 166 out << '['; 167 bool firstrow=true; 168 for (const_iterator i = begin (); i != end (); ++i) { 169 if (firstrow) { 170 out << '['; 171 firstrow =false; 172 } 173 else 174 out << ", ["; 175 176 Row_t::const_iterator j = i->begin (); 177 for (int64_t j_idx = 0; j_idx < static_cast<int64_t>(_coldim); j_idx++) { 178 if (j == i->end () || j_idx != static_cast<int64_t>(*j) ) 179 out << '0'; 180 else { 181 out << '1'; 182 ++j; 183 } 184 if (j_idx < (static_cast<int64_t>(_coldim)-1) ) 185 out << ','; 186 } 187 188 out << ']'; 189 } 190 return out << ']'; 191 } 192 else 193 return out << "ZeroOne over GF(2), format other than SMS or Maple not implemented" << std::endl; 194 } 195 196 /*! Raw iterator. 197 * @ingroup iterators 198 */ 199 class ZeroOne<GF2>::Iterator { 200 public: 201 typedef Element value_type; 202 203 Iterator(size_t pos, Element elem) : 204 _elem(elem),_pos(pos) 205 {} 206 207 Iterator(const Iterator &In) : 208 _elem(In._elem),_pos(In._pos) 209 {} 210 211 const Iterator& operator=(const Iterator& rhs) 212 { 213 _pos = rhs._pos; 214 _elem = rhs._elem; 215 return *this; 216 } 217 218 219 bool operator==(const Iterator &rhs) 220 { 221 return ( _pos == rhs._pos && _elem == rhs._elem); 222 } 223 224 bool operator!=(const Iterator &rhs) 225 { 226 return ( _pos != rhs._pos || _elem != rhs._elem ); 227 } 228 229 Iterator & operator++() 230 { 231 ++_pos; 232 return *this; 233 } 234 235 Iterator operator++(int) 236 { 237 Iterator tmp = *this; 238 _pos++; 239 return tmp; 240 } 241 242 value_type operator*() { return _elem; } 243 244 value_type operator*() const 245 { 246 return _elem; 247 } 248 249 private: 250 value_type _elem; 251 size_t _pos; 252 }; 253 254 /* STL standard Begin and End functions. Used to get 255 * the beginning and end of the data. So that Iterator 256 * can be used in algorithms like a normal STL iterator. 257 */ 258 inline ZeroOne<GF2>::Iterator ZeroOne<GF2>::Begin() 259 { 260 return Iterator( 0, field().one ); 261 } 262 263 inline ZeroOne<GF2>::Iterator ZeroOne<GF2>::End() 264 { 265 return Iterator( _nnz, field().one ); 266 } 267 268 inline const ZeroOne<GF2>::Iterator ZeroOne<GF2>::Begin() const 269 { 270 return Iterator(0, field().one ); 271 } 272 273 inline const ZeroOne<GF2>::Iterator ZeroOne<GF2>::End() const 274 { 275 return Iterator(_nnz, field().one ); 276 } 277 278 /*! IndexedIterator. 279 * @ingroup iterators 280 * Iterates through the i and j of the current element 281 * and when accessed returns an STL pair containing the coordinates 282 */ 283 class ZeroOne<GF2>::IndexedIterator { 284 using Self_t=ZeroOne<GF2>::IndexedIterator; 285 public: 286 typedef std::pair<size_t, size_t> value_type; 287 288 IndexedIterator() {} 289 290 IndexedIterator(size_t rowidx, 291 LightContainer<LightContainer<size_t> >::const_iterator rowbeg, 292 LightContainer<LightContainer<size_t> >::const_iterator rowend, 293 size_t colidx, 294 LightContainer<size_t>::const_iterator colbeg) : 295 _rowbeg( LightContainer<LightContainer<size_t> >::const_iterator(rowbeg) ), 296 _rowend( LightContainer<LightContainer<size_t> >::const_iterator(rowend) ), 297 _colbeg( LightContainer<size_t>::const_iterator(colbeg) ), 298 _row(rowidx), 299 _col(colidx) 300 { 301 302 if( _rowbeg == _rowend ) return; 303 304 while ( _colbeg == _rowbeg->end() ) { 305 306 if (++_rowbeg == _rowend) return; 307 308 _colbeg = _rowbeg->begin(); 309 310 } 311 312 } 313 314 IndexedIterator(const Self_t &In) : 315 _rowbeg(In._rowbeg), _rowend(In._rowend), _colbeg(In._colbeg), _row(In._row), _col(In._col) 316 {} 317 318 const Self_t &operator=(const Self_t &rhs) 319 { 320 _rowbeg = rhs._rowbeg; 321 _rowend = rhs._rowend; 322 _colbeg = rhs._colbeg; 323 _row = rhs._row; 324 _col = rhs._col; 325 return *this; 326 } 327 328 bool operator==(const Self_t &rhs) const 329 { 330 return _rowbeg == rhs._rowbeg && _colbeg == rhs._colbeg; 331 } 332 333 bool operator!=(const Self_t &rhs) const 334 { 335 return _rowbeg != rhs._rowbeg || _colbeg != rhs._colbeg; 336 } 337 338 const Self_t& operator++() { 339 340 341 342 ++_colbeg; 343 while(_colbeg == _rowbeg->end()) { 344 if (++_rowbeg == _rowend) return *this; 345 ++_row; 346 _colbeg = _rowbeg->begin(); 347 } 348 _col = *_colbeg; 349 350 351 return *this; 352 } 353 354 const Self_t operator++(int) 355 { 356 Self_t tmp = *this; 357 this->operator++(); 358 return tmp; 359 } 360 361 value_type operator*() 362 { 363 return std::pair<size_t,size_t>(_row, _col); 364 } 365 366 const value_type operator*() const 367 { 368 return std::pair<size_t,size_t>(_row, _col); 369 } 370 private: 371 LightContainer<LightContainer<size_t> >::const_iterator _rowbeg, _rowend; 372 LightContainer<size_t>::const_iterator _colbeg; 373 size_t _row, _col; 374 }; 375 376 inline ZeroOne<GF2>::IndexedIterator ZeroOne<GF2>::indexBegin() 377 { 378 return ZeroOne<GF2>::IndexedIterator(0, this->begin(), this->end(), this->front().front(), this->front().begin() ); 379 } 380 381 inline const ZeroOne<GF2>::IndexedIterator ZeroOne<GF2>::indexBegin() const 382 { 383 return ZeroOne<GF2>::IndexedIterator(0, this->begin(), this->end(), this->front().front(), this->front().begin() ); 384 } 385 386 inline ZeroOne<GF2>::IndexedIterator ZeroOne<GF2>::indexEnd() 387 { 388 return ZeroOne<GF2>::IndexedIterator(_rowdim, this->end(), this->end(), this->back().size(),this->back().end() ); 389 } 390 391 inline const ZeroOne<GF2>::IndexedIterator ZeroOne<GF2>::indexEnd() const 392 { 393 return ZeroOne<GF2>::IndexedIterator(_rowdim, this->end(), this->end(), this->back().size(),this->back().end() ); 394 } 395 396 397 // Merge A with self 398 // Warning: respective supports must be disjoint 399 template<typename _Tp1> 400 void ZeroOne<GF2>::augment(const ZeroOne<_Tp1>& A) { 401 for(auto it = A.indexBegin(); 402 it != A.indexEnd(); ++it,++_nnz) { 403 this->operator[]( (*it).first ).push_back( (*it).second ); 404 } 405 } 406 407 template<typename _Tp1> 408 ZeroOne<GF2>::ZeroOne(const ZeroOne<_Tp1>& A, const GF2 F2) : 409 Father_t(A.rowdim()), _rowdim(A.rowdim()), _coldim(A.coldim()), _nnz(0) 410 { 411 this->augment(A); 412 } 413 414 template<> 415 struct ZeroOne<GF2>::rebind<GF2> { 416 typedef ZeroOne<GF2> other; 417 inline void operator() (other & Ap, 418 const Self_t& A, 419 const GF2& F) { 420 // Merge A with Ap 421 Ap.augment(A); 422 } 423 inline void operator() (other & Ap, const Self_t& A) { 424 this->operator()(Ap,A,Ap.field()); 425 } 426 }; 427 428 429} // end of namespace LinBox 430 431 432// Specialization of getentry 433#include "linbox/solutions/solution-tags.h" 434namespace LinBox 435{ 436 template<> struct GetEntryCategory<ZeroOne<GF2> > { typedef SolutionTags::Local Tag; }; 437 } // end of namespace LinBox 438 439#endif //__LINBOX_zo_gf2_INL 440 441// Local Variables: 442// mode: C++ 443// tab-width: 4 444// indent-tabs-mode: nil 445// c-basic-offset: 4 446// End: 447// vim:sts=4:sw=4:ts=4:et:sr:cino=>s,f0,{0,g0,(0,\:0,t0,+0,=s 448