1 // -*- C++ -*-
2 //==============================================================================================
3 //
4 // This file is part of LiDIA --- a library for computational number theory
5 //
6 // Copyright (c) 1994--2001 the LiDIA Group. All rights reserved.
7 //
8 // See http://www.informatik.tu-darmstadt.de/TI/LiDIA/
9 //
10 //----------------------------------------------------------------------------------------------
11 //
12 // $Id$
13 //
14 // Author :
15 // Changes : See CVS log
16 //
17 //==============================================================================================
18
19
20 #ifndef LIDIA_FACTORIZATION_H_GUARD_
21 #define LIDIA_FACTORIZATION_H_GUARD_
22
23
24
25 #ifndef LIDIA_UDIGIT_H_GUARD_
26 # include "LiDIA/udigit.h"
27 #endif
28 #ifndef LIDIA_SORT_VECTOR_H_GUARD_
29 # include "LiDIA/sort_vector.h"
30 #endif
31 #ifndef LIDIA_PPAIR_H_GUARD_
32 # include "LiDIA/base/ppair.h"
33 #endif
34 #ifndef LIDIA_SINGLE_FACTOR_H_GUARD_
35 # include "LiDIA/single_factor.h"
36 #endif
37
38
39
40 #ifdef LIDIA_NAMESPACE
41 namespace LiDIA {
42 # define IN_NAMESPACE_LIDIA
43 #endif
44
45
46
47 //template < class T > class single_factor;
48 //class decomposable_object;
49
50 class factorization_flags
51 {
52 protected:
53 enum factorization_state {
54 sorted = 1,
55 normalized = 2,
56 refined = 4
57 };
58 };
59
60
61
62 template< class T >
63 class factorization: public factorization_flags, private decomposable_object
64 {
65
66 private:
67
68 // data elements
69
70 single_factor< T > *epsilon; // unit
71 sort_vector< ppair< single_factor < T >, lidia_size_t > >
72 prime_component, composite_component;
73
74
75 udigit attributes; // information not concerning primality
76
77
78 // access functions for 'attributes'
clear_attributes()79 void clear_attributes()
80 {
81 attributes &= ~ (sorted | normalized | refined);
82 }
83
84 void check_for_trivial_case();
85 // sets information for simple factorizations
86
87
88 static void
89 refine2(sort_vector< ppair< single_factor< T >, lidia_size_t > > & v,
90 ppair< single_factor< T >, lidia_size_t > & SF,
91 const ppair< single_factor< T >, lidia_size_t > & a,
92 const ppair< single_factor< T >, lidia_size_t > & b);
93
94 static void
95 normalize(sort_vector< ppair< single_factor< T >, lidia_size_t > > &v);
96
97 public:
98 //
99 // constructors, destructor
100 //
101
102 factorization();
103 factorization(const factorization< T > & F);
104 factorization(const single_factor< T > & f);
105 ~factorization();
106
107 void reset(); // reset the factorization to one.
108 void kill(); // reset the factorization and deallocate memory.
109
110 //
111 // assignment
112 //
113
114 factorization< T > & operator = (const factorization< T > & x);
115 factorization< T > & operator = (const single_factor< T > & x);
116
117 #ifndef HEADBANGER
118 void assign (const factorization< T > & F);
119 void assign (const single_factor< T > & f);
120 #endif //HEADBANGER
121
122 //
123 // comparisons
124 //
125
126 bool operator == (const factorization< T > & b) const;
127 bool operator != (const factorization< T > & b)
128 {
129 return !(*this == b);
130 }
131
132
133 //
134 // access functions
135 //
136
137 const single_factor< T > & prime_base(lidia_size_t) const;
138 lidia_size_t prime_exponent(lidia_size_t) const;
139 const single_factor< T > & composite_base(lidia_size_t) const;
140 lidia_size_t composite_exponent(lidia_size_t) const;
141
142 const T & unit() const;
143
144 T value() const;
145
no_of_prime_components()146 lidia_size_t no_of_prime_components() const
147 {
148 return prime_component.size();
149 }
150
no_of_composite_components()151 lidia_size_t no_of_composite_components() const
152 {
153 return composite_component.size();
154 }
155
no_of_components()156 lidia_size_t no_of_components() const
157 {
158 return prime_component.size() + composite_component.size();
159 }
160
161
162 //
163 // predicates
164 //
165
166 bool is_prime_factorization();
167
168 bool is_prime_factorization(int test);
169 // test == 0 ->no explicit primality test (only flags are checked)
170 // returns true iff (*this) is known to be a prime factorization
171 // test != 0 ->explicit primality test for unknown elements
172 // returns false iff (*this) has an element which is not_prime
173 // (see manual)
174
175 bool is_sorted() const; // 'sorted' means: both lists are sorted
176
177 bool is_normalized() const;
178
179 bool is_refined() const;
180
181 //
182 // input / output
183 //
184
185 //
186 // I/O - format :
187 // [ [unit] ]
188 // or
189 // [ [unit], [base_1, exp_1], [base_2, exp_2], ..., [base_i, exp_i] ]
190 // or
191 // [ [base_1, exp_1], [base_2, exp_2], ..., [base_i, exp_i] ]
192 //
193
194 void read(std::istream &is);
195 void write(std::ostream &os) const;
196
197
198 //#####
199 // NUR ZU TESTZWECKEN !!!
200 void output() const;
201 // **********************
202
203
204 //
205 // functions for computing with factorizations
206 //
207
208 #ifndef HEADBANGER
209 void concat(const factorization< T > &a, const factorization< T > &b);
210 // *this = a concat b
211 #endif //HEADBANGER
212
213 void invert(); //== power(-1)
214
215 void square(); //== power(2)
216
217 void power(lidia_size_t p);
218
219
220
221 //
222 // high-level functions
223 //
224
225 void sort();
226
227 void normalize(); //was: compose();
228
229 void refine(); //factor refinement algorithm
230 bool refine(const single_factor< T > & x);
231 //returns true iff *this can be refined by computing gcd's
232 //of all (composite) elements with 'x'
233
234 void replace(lidia_size_t ix, const factorization< T > & F);
235 // deletes composite_component[i] and appends the components of F
236
append(const single_factor<T> & a)237 void append(const single_factor< T > & a)
238 {
239 append(a, 1);
240 }
241 void append(const single_factor< T > & a, lidia_size_t exp);
242 // appends 'a^exp' to the factorization
243
swapping_append(single_factor<T> & a)244 void swapping_append(single_factor< T > & a)
245 {
246 swapping_append(a, 1);
247 }
248 void swapping_append(single_factor< T > & a, lidia_size_t exp);
249
250
251 void append(const T& a, lidia_size_t exp);
252
253 //
254 // factoring
255 //
256
257 void factor_all_components();
258 // calls 'single_factor < T >::factor()' for all composite components
259 // and replaces the components by the resulting factorizations
260 };
261
262
263
264 template< class T >
265 inline
~factorization()266 factorization< T >::~factorization ()
267 {
268 delete epsilon;
269 }
270
271
272
273 //
274 // assigners
275 //
276
277 template< class T >
278 inline factorization< T > &
279 factorization< T >::operator = (const factorization< T > & f)
280 {
281 assign(f);
282 return *this;
283 }
284
285
286
287 template< class T >
288 inline factorization< T > &
289 factorization< T >::operator = (const single_factor< T > & f)
290 {
291 assign(f);
292 return *this;
293 }
294
295
296
297 //
298 // accessors
299 //
300
301 template< class T >
302 inline const single_factor< T > &
prime_base(lidia_size_t index)303 factorization< T >::prime_base (lidia_size_t index) const
304 {
305 if ((index< 0) || (index >= no_of_prime_components()))
306 lidia_error_handler("factorization< T >",
307 "prime_base::index out of range");
308
309 return prime_component[index].left();
310 }
311
312
313
314 template< class T >
315 inline lidia_size_t
prime_exponent(lidia_size_t index)316 factorization< T >::prime_exponent (lidia_size_t index) const
317 {
318 if ((index< 0) || (index >= no_of_prime_components()))
319 lidia_error_handler("factorization< T >",
320 "prime_exponent::index out of range");
321
322 return prime_component[index].right();
323 }
324
325
326
327 template< class T >
328 inline const single_factor< T > &
composite_base(lidia_size_t index)329 factorization< T >::composite_base (lidia_size_t index) const
330 {
331 if ((index< 0) || (index >= no_of_composite_components()))
332 lidia_error_handler("factorization< T >",
333 "composite_base::index out of range");
334
335 return composite_component[index].left();
336 }
337
338
339
340 template< class T >
341 inline lidia_size_t
composite_exponent(lidia_size_t index)342 factorization< T >::composite_exponent (lidia_size_t index) const
343 {
344 if ((index< 0) || (index >= no_of_composite_components()))
345 lidia_error_handler("factorization< T >",
346 "composite_exponent::index out of range");
347
348 return composite_component[index].right();
349 }
350
351
352
353 template< class T >
354 inline const T &
unit()355 factorization< T >::unit () const
356 {
357 return epsilon->base();
358 }
359
360
361
362 //
363 // predicates
364 //
365
366 template< class T >
367 inline bool
is_prime_factorization()368 factorization< T >::is_prime_factorization ()
369 {
370 return this->is_prime_factorization(0);
371 }
372
373
374
375 template< class T >
376 inline bool
is_sorted()377 factorization< T >::is_sorted () const
378 {
379 return static_cast<bool>(attributes & sorted);
380 }
381
382
383
384 template< class T >
385 inline bool
is_normalized()386 factorization< T >::is_normalized () const
387 {
388 return static_cast<bool>(attributes & normalized);
389 }
390
391
392
393 template< class T >
394 inline bool
is_refined()395 factorization< T >::is_refined () const
396 {
397 return static_cast<bool>(attributes & refined);
398 }
399
400
401
402 //
403 //
404 //
405
406 template< class T >
407 inline std::istream &
408 operator >> (std::istream &is, factorization< T > &F)
409 {
410 F.read(is);
411 return is;
412 }
413
414
415
416 template< class T >
417 inline std::ostream &
418 operator << (std::ostream &os, const factorization< T > & F)
419 {
420 F.write(os);
421 return os;
422 }
423
424
425
426 template< class T >
427 inline void
invert(factorization<T> & f,const factorization<T> & a)428 invert (factorization< T > & f,
429 const factorization< T > & a)
430 {
431 f.assign(a);
432 f.invert();
433 }
434
435
436
437 template< class T >
438 inline factorization< T >
inverse(const factorization<T> & f)439 inverse (const factorization< T > &f)
440 {
441 factorization< T > tmp(f);
442
443 tmp.invert();
444 return tmp;
445 }
446
447
448
449 template< class T >
450 inline void
square(factorization<T> & f,const factorization<T> & a)451 square (factorization< T > & f,
452 const factorization< T > & a)
453 {
454 f.assign(a);
455 f.square();
456 }
457
458
459
460 template< class T >
461 inline void
power(factorization<T> & f,const factorization<T> & a,lidia_size_t p)462 power (factorization< T > & f,
463 const factorization< T > & a,
464 lidia_size_t p)
465 {
466 f.assign(a);
467 f.power(p);
468 }
469
470
471
472 #ifndef HEADBANGER
473 template< class T >
474 inline void
multiply(factorization<T> & c,const factorization<T> & a,const factorization<T> & b)475 multiply (factorization< T > &c,
476 const factorization< T > &a,
477 const factorization< T > &b)
478 {
479 c.concat(a, b);
480 }
481
482
483
484 template< class T >
485 inline void
divide(factorization<T> & c,const factorization<T> & a,const factorization<T> & b)486 divide (factorization< T > &c,
487 const factorization< T > &a,
488 const factorization< T > &b)
489 {
490 factorization< T > tmp(b);
491
492 tmp.invert();
493 multiply(c, a, tmp);
494 }
495 #endif // HEADBANGER
496
497
498
499 template< class T >
500 inline factorization< T >
501 operator * (const factorization< T > & a,
502 const factorization< T > & b)
503 {
504 factorization< T > c;
505
506 multiply(c, a, b);
507 return c;
508 }
509
510
511
512 template< class T >
513 inline factorization< T >
514 operator / (const factorization< T > & a,
515 const factorization< T > & b)
516 {
517 factorization< T > c;
518
519 divide(c, a, b);
520 return c;
521 }
522
523
524
525 template< class T >
526 inline factorization< T >
factor_all_components(const factorization<T> & F)527 factor_all_components (const factorization< T > &F)
528 {
529 factorization< T > FF(F);
530
531 FF.factor_all_components();
532 return FF;
533 }
534
535
536
537 #ifdef LIDIA_NAMESPACE
538 } // end of namespace LiDIA
539 # undef IN_NAMESPACE_LIDIA
540 #endif
541
542
543
544 #ifdef LIDIA_INCLUDE_CC
545 # include "LiDIA/factorization.cc"
546 #endif
547
548
549
550 #endif
551