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