1 // Copyright (c) 1999-2007
2 // Utrecht University (The Netherlands),
3 // ETH Zurich (Switzerland),
4 // INRIA Sophia-Antipolis (France),
5 // Max-Planck-Institute Saarbruecken (Germany),
6 // and Tel-Aviv University (Israel).  All rights reserved.
7 //
8 // This file is part of CGAL (www.cgal.org)
9 //
10 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Number_types/include/CGAL/Quotient.h $
11 // $Id: Quotient.h 14c3b7e 2020-05-27T16:33:33+02:00 Laurent Rineau
12 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
13 //
14 //
15 // Author(s)     : Stefan Schirra, Sylvain Pion, Michael Hemmer
16 
17 // The template class Quotient<NT> is based on the LEDA class
18 // leda_rational written by Stefan Naeher and Christian Uhrig.
19 // It is basically a templated version with restricted functionality
20 // of the version of rational in LEDA release 3.3.
21 // The modification was done by Stefan.Schirra@mpi-sb.mpg.de
22 
23 // The include is done before the protect macro on purpose, because
24 // of a cyclic dependency.
25 
26 #ifndef CGAL_QUOTIENT_H
27 #define CGAL_QUOTIENT_H
28 
29 #include <utility>
30 #include <istream>
31 
32 #include <CGAL/Interval_nt.h>
33 #include <CGAL/Kernel/mpl.h>
34 
35 #include <boost/operators.hpp>
36 
37 namespace CGAL {
38 
39 #define CGAL_int(T)    typename First_if_different<int,    T>::Type
40 #define CGAL_double(T) typename First_if_different<double, T>::Type
41 
42 // Simplify the quotient numerator/denominator.
43 // Currently the default template doesn't do anything.
44 // This function is not documented as a number type requirement for now.
45 template < typename NT >
46 inline void
simplify_quotient(NT &,NT &)47 simplify_quotient(NT &, NT &) {}
48 
49 // This one should be replaced by some functor or tag.
50 // Meanwhile, the class is specialized for Gmpz, mpz_class, leda_integer.
51 template < typename NT >
52 struct Split_double
53 {
operatorSplit_double54   void operator()(double d, NT &num, NT &den) const
55   {
56     num = NT(d);
57     den = 1;
58   }
59 };
60 
61 
62 template <class NT_>
63 class Quotient
64   : boost::ordered_field_operators1< Quotient<NT_>
65   , boost::ordered_field_operators2< Quotient<NT_>, NT_
66   , boost::ordered_field_operators2< Quotient<NT_>, CGAL_int(NT_)
67   , boost::ordered_field_operators2< Quotient<NT_>, CGAL_double(NT_)
68     > > > >
69 {
70  public:
71   typedef NT_        NT;
72 
Quotient()73   Quotient()
74     : num(0), den(1) {}
75 
Quotient(const NT & n)76   Quotient(const NT& n)
77     : num(n), den(1) {}
78 
Quotient(const CGAL_double (NT)& n)79   Quotient(const CGAL_double(NT) & n)
80   { Split_double<NT>()(n, num, den); }
81 
Quotient(const CGAL_int (NT)& n)82   Quotient(const CGAL_int(NT) & n)
83     : num(n), den(NT(1)) {}
84 
85   template <class T>
Quotient(const T & n)86   explicit Quotient(const T& n) : num(n), den(1) {}
87 
88   template <class T>
Quotient(const Quotient<T> & n)89   Quotient(const Quotient<T>& n) : num(n.numerator()), den(n.denominator()) {}
90 
91   Quotient& operator=(const NT & n)
92   {
93     num = n;
94     den = 1;
95     return *this;
96   }
97 
CGAL_double(NT)98   Quotient& operator=(const CGAL_double(NT) & n)
99   {
100     Split_double<NT>()(n, num, den);
101     return *this;
102   }
103 
CGAL_int(NT)104   Quotient& operator=(const CGAL_int(NT) & n)
105   {
106     num = n;
107     den = 1;
108     return *this;
109   }
110 
111   template <class T1, class T2>
Quotient(const T1 & n,const T2 & d)112   Quotient(const T1& n, const T2& d) : num(n), den(d)
113   { CGAL_precondition( d != 0 ); }
114 
115   Quotient<NT>& operator+= (const Quotient<NT>& r);
116   Quotient<NT>& operator-= (const Quotient<NT>& r);
117   Quotient<NT>& operator*= (const Quotient<NT>& r);
118   Quotient<NT>& operator/= (const Quotient<NT>& r);
119   Quotient<NT>& operator+= (const NT& r);
120   Quotient<NT>& operator-= (const NT& r);
121   Quotient<NT>& operator*= (const NT& r);
122   Quotient<NT>& operator/= (const NT& r);
123   Quotient<NT>& operator+= (const CGAL_int(NT)& r);
124   Quotient<NT>& operator-= (const CGAL_int(NT)& r);
125   Quotient<NT>& operator*= (const CGAL_int(NT)& r);
126   Quotient<NT>& operator/= (const CGAL_int(NT)& r);
127   Quotient<NT>& operator+= (const CGAL_double(NT)& r);
128   Quotient<NT>& operator-= (const CGAL_double(NT)& r);
129   Quotient<NT>& operator*= (const CGAL_double(NT)& r);
130   Quotient<NT>& operator/= (const CGAL_double(NT)& r);
131 
132   friend bool operator==(const Quotient& x, const Quotient& y)
133   { return x.num * y.den == x.den * y.num; }
134   friend bool operator==(const Quotient& x, const NT& y)
135   { return x.den * y == x.num; }
136   friend inline bool operator==(const Quotient& x, const CGAL_int(NT) & y)
137   { return x.den * y == x.num; }
138   friend inline bool operator==(const Quotient& x, const CGAL_double(NT) & y)
139   { return x.den * y == x.num; } // Uh?
140 
141   Quotient<NT>&    normalize();
142 
numerator()143   const NT&   numerator()   const { return num; }
denominator()144   const NT&   denominator() const { return den; }
145 
swap(Quotient & q)146   void swap(Quotient &q)
147   {
148     using std::swap;
149     swap(num, q.num);
150     swap(den, q.den);
151   }
152 
153 #ifdef CGAL_ROOT_OF_2_ENABLE_HISTOGRAM_OF_NUMBER_OF_DIGIT_ON_THE_COMPLEX_CONSTRUCTOR
tam()154   int tam() const { return (std::max)(num.tam(), den.tam()); }
155 #endif
156 
157  public:
158   NT   num;
159   NT   den;
160 };
161 
162 template <class NT>
163 inline
swap(Quotient<NT> & p,Quotient<NT> & q)164 void swap(Quotient<NT> &p, Quotient<NT> &q)
165 {
166   p.swap(q);
167 }
168 
169 template <class NT>
170 CGAL_MEDIUM_INLINE
171 Quotient<NT>&
normalize()172 Quotient<NT>::normalize()
173 {
174   if (num == den)
175   {
176       num = den = 1;
177       return *this;
178   }
179   if (-num == den)
180   {
181       num = -1;
182       den = 1;
183       return *this;
184   }
185   NT ggt = CGAL_NTS gcd(num, den);
186   if (ggt != 1 )
187   {
188       num = CGAL::integral_division(num, ggt);
189       den = CGAL::integral_division(den, ggt);
190   }
191   return *this;
192 }
193 
194 template <class NT>
195 CGAL_MEDIUM_INLINE
196 Quotient<NT>&
197 Quotient<NT>::operator+= (const Quotient<NT>& r)
198 {
199     num = num * r.den + r.num * den;
200     den *= r.den;
201     simplify_quotient(num, den);
202     return *this;
203 }
204 
205 template <class NT>
206 CGAL_MEDIUM_INLINE
207 Quotient<NT>&
208 Quotient<NT>::operator-= (const Quotient<NT>& r)
209 {
210     num = num * r.den - r.num * den;
211     den *= r.den;
212     simplify_quotient(num, den);
213     return *this;
214 }
215 
216 template <class NT>
217 CGAL_MEDIUM_INLINE
218 Quotient<NT>&
219 Quotient<NT>::operator*= (const Quotient<NT>& r)
220 {
221     num *= r.num;
222     den *= r.den;
223     simplify_quotient(num, den);
224     return *this;
225 }
226 
227 template <class NT>
228 CGAL_MEDIUM_INLINE
229 Quotient<NT>&
230 Quotient<NT>::operator/= (const Quotient<NT>& r)
231 {
232     CGAL_precondition( r.num != 0 );
233     num *= r.den;
234     den *= r.num;
235     simplify_quotient(num, den);
236     return *this;
237 }
238 
239 template <class NT>
240 CGAL_MEDIUM_INLINE
241 Quotient<NT>&
242 Quotient<NT>::operator+= (const NT& r)
243 {
244     num += r * den;
245     return *this;
246 }
247 
248 template <class NT>
249 CGAL_MEDIUM_INLINE
250 Quotient<NT>&
251 Quotient<NT>::operator-= (const NT& r)
252 {
253     num -= r * den;
254     return *this;
255 }
256 
257 template <class NT>
258 CGAL_MEDIUM_INLINE
259 Quotient<NT>&
260 Quotient<NT>::operator*= (const NT& r)
261 {
262     num *= r;
263     return *this;
264 }
265 
266 template <class NT>
267 CGAL_MEDIUM_INLINE
268 Quotient<NT>&
269 Quotient<NT>::operator/= (const NT& r)
270 {
271     CGAL_precondition( r != 0 );
272     den *= r;
273     return *this;
274 }
275 
276 template <class NT>
277 CGAL_MEDIUM_INLINE
278 Quotient<NT>&
279 Quotient<NT>::operator+= (const CGAL_int(NT)& r)
280 {
281     num += r * den;
282     return *this;
283 }
284 
285 template <class NT>
286 CGAL_MEDIUM_INLINE
287 Quotient<NT>&
288 Quotient<NT>::operator-= (const CGAL_int(NT)& r)
289 {
290     num -= r * den;
291     return *this;
292 }
293 
294 template <class NT>
295 CGAL_MEDIUM_INLINE
296 Quotient<NT>&
CGAL_int(NT)297 Quotient<NT>::operator*= (const CGAL_int(NT)& r)
298 {
299     num *= r;
300     return *this;
301 }
302 
303 template <class NT>
304 CGAL_MEDIUM_INLINE
305 Quotient<NT>&
306 Quotient<NT>::operator/= (const CGAL_int(NT)& r)
307 {
308     CGAL_precondition( r != 0 );
309     den *= r;
310     return *this;
311 }
312 
313 template <class NT>
314 CGAL_MEDIUM_INLINE
315 Quotient<NT>&
316 Quotient<NT>::operator+= (const CGAL_double(NT)& r)
317 {
318   //num += r * den;
319   NT r_num, r_den;
320   Split_double<NT>()(r,r_num,r_den);
321   num = num*r_den + r_num*den;
322   den *=r_den;
323   return *this;
324 }
325 
326 template <class NT>
327 CGAL_MEDIUM_INLINE
328 Quotient<NT>&
329 Quotient<NT>::operator-= (const CGAL_double(NT)& r)
330 {
331   //num -= r * den;
332   NT r_num, r_den;
333   Split_double<NT>()(r,r_num,r_den);
334   num =  num*r_den - r_num*den;
335   den *= r_den;
336   return *this;
337 }
338 
339 template <class NT>
340 CGAL_MEDIUM_INLINE
341 Quotient<NT>&
CGAL_double(NT)342 Quotient<NT>::operator*= (const CGAL_double(NT)& r)
343 {
344   // num *= r;
345 
346   NT r_num, r_den;
347   Split_double<NT>()(r,r_num,r_den);
348   num *= r_num;
349   den *= r_den;
350   return *this;
351 }
352 
353 template <class NT>
354 CGAL_MEDIUM_INLINE
355 Quotient<NT>&
356 Quotient<NT>::operator/= (const CGAL_double(NT)& r)
357 {
358   CGAL_precondition( r != 0 );
359   NT r_num, r_den;
360   Split_double<NT>()(r,r_num,r_den);
361   num *= r_den;
362   den *= r_num;
363   return *this;
364 }
365 
366 template <class NT>
367 CGAL_MEDIUM_INLINE
368 Comparison_result
quotient_cmp(const Quotient<NT> & x,const Quotient<NT> & y)369 quotient_cmp(const Quotient<NT>& x, const Quotient<NT>& y)
370 {
371     // No assumptions on the sign of  den  are made
372 
373     // code assumes that SMALLER == - 1;
374     CGAL_precondition( SMALLER == static_cast<Comparison_result>(-1) );
375 
376     int xsign = CGAL_NTS sign(x.num) * CGAL_NTS sign(x.den) ;
377     int ysign = CGAL_NTS sign(y.num) * CGAL_NTS sign(y.den) ;
378     if (xsign == 0) return static_cast<Comparison_result>(-ysign);
379     if (ysign == 0) return static_cast<Comparison_result>(xsign);
380     // now (x != 0) && (y != 0)
381     int diff = xsign - ysign;
382     if (diff == 0)
383     {
384         int msign = CGAL_NTS sign(x.den) * CGAL_NTS sign(y.den);
385         NT leftop  = NT(x.num * y.den * msign);
386         NT rightop = NT(y.num * x.den * msign);
387         return CGAL_NTS compare(leftop, rightop);
388     }
389     else
390     {
391         return (xsign < ysign) ? SMALLER : LARGER;
392     }
393 }
394 
395 
396 template <class NT>
397 std::ostream&
398 operator<<(std::ostream& s, const Quotient<NT>& r)
399 {
400    return s << r.numerator() << '/' << r.denominator();
401 }
402 
403 template <class NT>
404 std::istream&
405 operator>>(std::istream& in, Quotient<NT>& r)
406 {
407   /* format  num/den  or simply  num  */
408 
409   NT num,den=1;
410   in >> num;
411   if(!in) return in;
412   std::istream::sentry s(in); // skip whitespace
413   if(in.peek()!='/'){
414           if(!in.good()){
415                   in.clear(std::ios_base::eofbit);
416                   // unlikely to be some other reason?
417           }
418   } else {
419           char c;
420           in.get(c); // remove the '/'
421           in >> den;
422           if(!in) return in;
423   }
424   r=Quotient<NT>(num,den);
425   return in;
426 }
427 
428 template< class NT >
429 inline
430 Quotient<NT>
431 operator+( const Quotient<NT>& x ) {
432   return Quotient<NT>(x);
433 }
434 
435 template <class NT>
436 inline
437 Quotient<NT>
438 operator-(const Quotient<NT>& x)
439 { return Quotient<NT>(-x.num,x.den); }
440 
441 
442 template <class NT>
443 CGAL_MEDIUM_INLINE
444 NT
quotient_truncation(const Quotient<NT> & r)445 quotient_truncation(const Quotient<NT>& r)
446 { return (r.num / r.den); }
447 
448 
449 
450 
451 template <class NT>
452 CGAL_MEDIUM_INLINE
453 bool
454 operator<(const Quotient<NT>& x, const Quotient<NT>& y)
455 {
456   return quotient_cmp(x,y) == SMALLER;
457 }
458 
459 template <class NT>
460 CGAL_MEDIUM_INLINE
461 bool
462 operator<(const Quotient<NT>& x, const NT& y)
463 {
464   return quotient_cmp(x,Quotient<NT>(y)) == SMALLER;
465 }
466 
467 template <class NT>
468 CGAL_MEDIUM_INLINE
469 bool
470 operator<(const Quotient<NT>& x, const CGAL_int(NT)& y)
471 {
472   return quotient_cmp(x,Quotient<NT>(y)) == SMALLER;
473 }
474 
475 template <class NT>
476 CGAL_MEDIUM_INLINE
477 bool
478 operator<(const Quotient<NT>& x, const CGAL_double(NT)& y)
479 {
480   return quotient_cmp(x,Quotient<NT>(y)) == SMALLER;
481 }
482 
483 
484 template <class NT>
485 inline
486 bool
487 operator>(const Quotient<NT>& x, const NT& y)
488 { return quotient_cmp(x,Quotient<NT>(y)) == LARGER; }
489 
490 template <class NT>
491 inline
492 bool
493 operator>(const Quotient<NT>& x, const CGAL_int(NT)& y)
494 { return quotient_cmp(x, Quotient<NT>(y)) == LARGER; }
495 
496 template <class NT>
497 inline
498 bool
499 operator>(const Quotient<NT>& x, const CGAL_double(NT)& y)
500 { return quotient_cmp(x, Quotient<NT>(y)) == LARGER; }
501 
502 
503 template< class NT >
504 class Is_valid< Quotient<NT> >
505   : public CGAL::cpp98::unary_function< Quotient<NT>, bool > {
506   public :
operator()507     bool operator()( const Quotient<NT>& x ) const {
508       return is_valid(x.num) && is_valid(x.den);
509     }
510 };
511 
512 
513 template <class NT>
514 inline
515 const NT&
denominator(const Quotient<NT> & q)516 denominator(const Quotient<NT>& q)
517 { return q.den ; }
518 
519 template <class NT>
520 inline
521 const NT&
numerator(const Quotient<NT> & q)522 numerator(const Quotient<NT>& q)
523 { return q.num ; }
524 
525 // The min/max are functions are needed since LEDA defines template
526 // min/max functions which clash with std::min/max with ADL.
527 template <class NT>
528 inline
529 const Quotient<NT>&
530 min
BOOST_PREVENT_MACRO_SUBSTITUTION(const Quotient<NT> & p,const Quotient<NT> & q)531 BOOST_PREVENT_MACRO_SUBSTITUTION
532 (const Quotient<NT>& p, const Quotient<NT>& q)
533 {
534   return (std::min)(p, q);
535 }
536 template <class NT>
537 inline
538 const Quotient<NT>&
539 max
BOOST_PREVENT_MACRO_SUBSTITUTION(const Quotient<NT> & p,const Quotient<NT> & q)540 BOOST_PREVENT_MACRO_SUBSTITUTION
541 (const Quotient<NT>& p, const Quotient<NT>& q)
542 {
543   return (std::max)(p, q);
544 }
545 
546 /*
547 template <class NT>
548 NT
549 gcd(const NT&, const NT&)
550 { return NT(1); }
551 */
552 
553 #undef CGAL_double
554 #undef CGAL_int
555 
556 //
557 // Algebraic structure traits
558 //
559 namespace INTERN_QUOTIENT {
560   template< class NT, class Sqrt_functor >
561   class Sqrt_selector {
562     public:
563       class Sqrt
564         : public CGAL::cpp98::unary_function< NT, NT > {
565         public:
operator()566           NT operator()( const NT& x ) const {
567             CGAL_precondition(x > 0);
568             return NT(CGAL_NTS sqrt(x.numerator()*x.denominator()),
569                       x.denominator());
570           }
571       };
572   };
573 
574   template< class NT >
575   class Sqrt_selector< NT, Null_functor > {
576     public:
577       typedef Null_functor Sqrt;
578   };
579 
580 // TODO: Algebraic_category could be Field_with_sqrt_tag, if NT
581 //       is INEXACT (because Sqrt can be inexact) and has a Sqrt-functor.
582 template<class NT> class Algebraic_structure_traits_quotient_base;
583 
584 template< class NT > class Algebraic_structure_traits_quotient_base< Quotient<NT> >
585   : public Algebraic_structure_traits_base< Quotient<NT>, Field_tag >  {
586 
587 public:
588     typedef Quotient<NT> Type;
589 
590     typedef typename Algebraic_structure_traits<NT>::Is_exact        Is_exact;
591     typedef Tag_false Is_numerical_sensitive;
592 
593 
594 
595     class Is_square
596         : public CGAL::cpp98::binary_function< Quotient<NT>, Quotient<NT>&, bool > {
597     public:
operator()598         bool operator()( Quotient<NT> x, Quotient<NT>& y ) const {
599             NT x_num, x_den, y_num, y_den;
600             x.normalize();
601             x_num = x.numerator();
602             x_den = x.denominator();
603 
604             typename Algebraic_structure_traits<NT>::Is_square is_square;
605             bool num_is_square = is_square(x_num,y_num);
606             bool den_is_square = is_square(x_den,y_den);
607             y= Quotient<NT>(y_num,y_den);
608             return num_is_square && den_is_square;
609         }
operator()610         bool operator()(Quotient<NT> x) const {
611             x.normalize();
612             typename Algebraic_structure_traits<NT>::Is_square is_square;
613             return is_square(x.numerator())&&is_square(x.denominator());
614         }
615 
616     };
617 
618     typedef typename boost::mpl::if_c<
619         !boost::is_same< typename Algebraic_structure_traits<NT>::Sqrt,
620                          Null_functor >::value,
621          typename INTERN_QUOTIENT::Sqrt_selector< Type,
622                                                   Is_exact >::Sqrt,
623          Null_functor
624                             >::type Sqrt;
625 
626     class Simplify
627       : public CGAL::cpp98::unary_function< Type&, void > {
628       public:
operator()629         void operator()( Type& x) const {
630             x.normalize();
631         }
632     };
633 };
634 
635 
636 template<class NT> class Real_embeddable_traits_quotient_base;
637 // Real embeddable traits
638 template < class NT > class Real_embeddable_traits_quotient_base< Quotient<NT> >
639   : public INTERN_RET::Real_embeddable_traits_base< Quotient<NT>,
640                   typename Real_embeddable_traits< NT >::Is_real_embeddable > {
641   public:
642     typedef Quotient<NT> Type;
643 
644     class Compare
645       : public CGAL::cpp98::binary_function< Type, Type,
646                                 Comparison_result > {
647       public:
operator()648         Comparison_result operator()( const Type& x,
649                                             const Type& y ) const {
650           return quotient_cmp(x, y);
651         }
652     };
653 
654     class To_double
655       : public CGAL::cpp98::unary_function< Type, double > {
656       public:
operator()657         double operator()( const Type& x ) const {
658         // Original global function was marked with an TODO!!
659           if (x.num == 0 )
660             return 0;
661 
662           double nd = CGAL_NTS to_double( x.num );
663 
664           if (x.den == 1 )
665             return nd;
666 
667           double dd = CGAL_NTS to_double( x.den );
668 
669           if ( CGAL_NTS is_finite( x.den ) && CGAL_NTS is_finite( x.num ) )
670             return nd/dd;
671 
672           if ( CGAL_NTS abs(x.num) > CGAL_NTS abs(x.den) )
673           {
674               NT  nt_div = x.num / x.den;
675               double divd = CGAL_NTS to_double(nt_div);
676               if ( divd >= std::ldexp(1.0,53) )
677               { return divd; }
678           }
679           if ( CGAL_NTS abs(x.num) < CGAL_NTS abs(x.den) )
680           { return 1.0 / CGAL_NTS to_double( NT(1) / x ); }
681 
682           return nd/dd;
683         }
684     };
685 
686     class To_interval
687       : public CGAL::cpp98::unary_function< Type, std::pair< double, double > > {
688       public:
operator()689         std::pair<double, double> operator()( const Type& x ) const {
690           Interval_nt<> quot =
691                           Interval_nt<>(CGAL_NTS to_interval(x.numerator())) /
692                           Interval_nt<>(CGAL_NTS to_interval(x.denominator()));
693           return std::make_pair(quot.inf(), quot.sup());
694         }
695     };
696 
697     class Is_finite
698       : public CGAL::cpp98::unary_function< Type, bool > {
699       public:
operator()700         bool operator()( const Type& x ) const {
701           return CGAL_NTS is_finite(x.num) && CGAL_NTS is_finite(x.den);
702         }
703     };
704 };
705 } // namespace INTERN_QUOTIENT
706 
707 template< class NT > class Algebraic_structure_traits< Quotient<NT> >
708     : public INTERN_QUOTIENT::Algebraic_structure_traits_quotient_base<
709 Quotient<NT> >{};
710 
711 template< class NT > class Real_embeddable_traits< Quotient<NT> >
712     : public INTERN_QUOTIENT::Real_embeddable_traits_quotient_base<
713 Quotient<NT> >{};
714 
715 
716 // self coercion
717 CGAL_DEFINE_COERCION_TRAITS_FOR_SELF_TEM( Quotient<NT>, class NT)
718 
719 // from int to Quotient
720 template <class NT>
721 struct Coercion_traits<typename First_if_different<int, NT>::Type,Quotient<NT> >
722 {
723     typedef Tag_true  Are_explicit_interoperable;
724     typedef Tag_true  Are_implicit_interoperable;
725     typedef Quotient<NT> Type;
726     struct Cast{
727         typedef Type result_type;
728         Type operator()(const Quotient<NT>& x)   const { return x;}
729         Type operator()(
730                 const typename First_if_different<int, NT>::Type& x) const {
731             return Type(x);}
732     };
733 };
734 template <class NT>
735 struct Coercion_traits<Quotient<NT>,typename First_if_different<int, NT>::Type>
736     :public Coercion_traits<typename First_if_different<int, NT>::Type,
737 Quotient<NT> >{};
738 
739 // from double to Quotient
740 template <class NT>
741 struct Coercion_traits<typename First_if_different<double, NT>::Type,
742 Quotient<NT> >{
743     typedef Tag_true  Are_explicit_interoperable;
744     typedef Tag_true  Are_implicit_interoperable;
745     typedef Quotient<NT> Type;
746     struct Cast{
747         typedef Type result_type;
748         Type operator()(const Quotient<NT>& x)   const { return x;}
749         Type operator()(
750                 const typename First_if_different<double, NT>::Type& x) const {
751             return Type(x);}
752     };
753 };
754 template <class NT>
755 struct Coercion_traits<Quotient<NT>,
756 typename First_if_different<double, NT>::Type>
757     :public Coercion_traits<typename First_if_different<double, NT>::Type,
758 Quotient<NT> >
759 {};
760 
761 // from NT to Quotient
762 CGAL_DEFINE_COERCION_TRAITS_FROM_TO_TEM ( NT, Quotient<NT>, class NT)
763 
764 /*! \ingroup NiX_Fraction_traits_spec
765  *  \brief Specialization of Fraction_traits for Quotient<NT>
766  */
767 template <class NT>
768 class Fraction_traits< Quotient<NT> > {
769 public:
770     typedef Quotient<NT> Type;
771     typedef ::CGAL::Tag_true Is_fraction;
772     typedef NT Numerator_type;
773     typedef Numerator_type Denominator_type;
774 
775     //TODO: check whether Numerator_type has a GCD.
776     //will use Scalar_factor from Scalar_factor_traits (not implemented yet)
777     //for more details see EXACUS:NumeriX/include/NiX/Scalar_factor_traits.h
778     typedef typename Algebraic_structure_traits< Numerator_type >::Gcd Common_factor;
779 
780     class Decompose {
781     public:
782         typedef Type first_argument_type;
783         typedef Numerator_type& second_argument_type;
784         typedef Numerator_type& third_argument_type;
785         void operator () (
786                 const Type& rat,
787                 Numerator_type& num,
788                 Numerator_type& den) {
789             num = rat.numerator();
790             den = rat.denominator();
791         }
792     };
793 
794     class Compose {
795     public:
796         typedef Numerator_type first_argument_type;
797         typedef Numerator_type second_argument_type;
798         typedef Type result_type;
799         Type operator ()(
800                 const Numerator_type& num ,
801                 const Numerator_type& den ) {
802             Type result(num, den);
803             return result;
804         }
805     };
806 };
807 
808 } //namespace CGAL
809 
810 namespace Eigen {
811   template<class> struct NumTraits;
812   template<class NT> struct NumTraits<CGAL::Quotient<NT> >
813   {
814     typedef CGAL::Quotient<NT> Real;
815     typedef CGAL::Quotient<NT> NonInteger;
816     typedef CGAL::Quotient<NT> Nested;
817     typedef CGAL::Quotient<NT> Literal;
818 
819     static inline Real epsilon() { return NumTraits<NT>::epsilon(); }
820     static inline Real dummy_precision() { return NumTraits<NT>::dummy_precision(); }
821 
822     enum {
823       IsInteger = 0,
824       IsSigned = 1,
825       IsComplex = 0,
826       RequireInitialization = NumTraits<NT>::RequireInitialization,
827       ReadCost = 2*NumTraits<NT>::ReadCost,
828       AddCost = 150,
829       MulCost = 100
830     };
831   };
832 }
833 
834 #endif  // CGAL_QUOTIENT_H
835