DGtal  1.5.beta
DGtal::concepts::CPositiveIrreducibleFraction< T > Struct Template Reference

Aim: Defines positive irreducible fractions, i.e. fraction p/q, p and q non-negative integers, with gcd(p,q)=1. More...

#include <DGtal/arithmetic/CPositiveIrreducibleFraction.h>

Inheritance diagram for DGtal::concepts::CPositiveIrreducibleFraction< T >:
[legend]

Public Types

typedef T::Integer Integer
 
typedef T::Quotient Quotient
 
typedef T::value_type value_type
 
typedef T::Value Value
 
typedef T::ConstIterator ConstIterator
 
typedef T::const_iterator const_iterator
 
- Public Types inherited from DGtal::concepts::CBackInsertable< T >
typedef T::value_type value_type
 
- Public Types inherited from DGtal::concepts::CConstSinglePassRange< T >
typedef T::ConstIterator ConstIterator
 

Public Member Functions

 BOOST_CONCEPT_ASSERT ((concepts::CInteger< Integer >))
 
 BOOST_CONCEPT_ASSERT ((concepts::CInteger< Quotient >))
 
 BOOST_STATIC_ASSERT ((concepts::ConceptUtils::SameType< value_type, std::pair< Quotient, Quotient > >::value))
 
 BOOST_STATIC_ASSERT ((concepts::ConceptUtils::SameType< value_type, Value >::value))
 
 BOOST_CONCEPT_USAGE (CPositiveIrreducibleFraction)
 
void checkConstConstraints () const
 
- Public Member Functions inherited from DGtal::concepts::CBackInsertable< T >
 BOOST_CONCEPT_USAGE (CBackInsertable)
 
void checkConstConstraints () const
 
- Public Member Functions inherited from DGtal::concepts::CConstSinglePassRange< T >
 BOOST_CONCEPT_ASSERT ((boost_concepts::SinglePassIteratorConcept< ConstIterator >))
 
 BOOST_CONCEPT_USAGE (CConstSinglePassRange)
 
void checkConstConstraints () const
 

Private Attributes

myX
 
myY
 
Integer myP
 
Integer myQ
 
Quotient myU
 
bool myBool
 
Quotient myN1
 
Quotient myN2
 
myF1
 
myF2
 
std::vector< QuotientmyQuots
 
std::pair< Quotient, QuotientmyValue
 
ConstIterator myIterator
 

Detailed Description

template<typename T>
struct DGtal::concepts::CPositiveIrreducibleFraction< T >

Aim: Defines positive irreducible fractions, i.e. fraction p/q, p and q non-negative integers, with gcd(p,q)=1.

Description of concept 'CPositiveIrreducibleFraction'

Irreducible fractions are nicely represented with the Stern-Brocot tree. Furthermore, the development of a fraction p/q into its simple continued fraction with quotients \([u_0, \ldots, u_k]\) has one-to-one correspondence with the position of the fraction in the Stern-Brocot tree.

One can "visit" irreducible fractions by enumerating the sequence of its partial quotients. Furthermore, one can push a new quotient at the end of this fraction to get a new fraction which shares all quotients except the last one. In this sense, a fraction is a sequence (container) that can only grow.

Refinement of

Associated types

  • Integer: the type for representing a numerator or a denominator. Must be a model of CInteger.
  • Quotient: the type for representing partial quotients, i.e. the integers that appear in the continued fractions of p/q, and for representing the depth of the fraction. Might be the same as Integer but may be also smaller, since quotients are generally much smaller than the convergent numerators and denominators. Must be a model of CInteger since depths may be negative (1/0 is -1).
  • Value and value_type: the type std::pair<Quotient,Quotient>, useful to create back insertion sequence.
  • ConstIterator and const_iterator: the type for visiting the quotients of the fraction in sequence. The value of the iterator has type Value.

Notation

  • X : A type that is a model of CPositiveIrreducibleFraction
  • x : object of type X, which is below some fraction written \([u_0, \ldots, u_k]\) as a continued fraction
  • x1, x2, y : other objects of type X
  • p, q : object of type Integer
  • m, n1, n2 : objects of type Quotient
  • quots : an object of type std::vector<Quotient>
  • pair : a object of std::pair<Quotient,Quotient>, here (m,k+1)

Definitions

Valid expressions and semantics

Name Expression Type requirements Return type Precondition Semantics Post condition Complexity
Constructor Fraction( p, q ) X creates the fraction p'/q', where p'=p/g, q'=q/g, g=gcd(p,q) o(p+q)
numerator x.p() Integer ! x.null() returns the numerator O(1)
denominator x.q() Integer ! x.null() returns the denominator O(1)
quotient x.u() Quotient ! x.null() returns the quotient \(u_k\) O(1)
depth x.k() Quotient ! x.null() returns the depth k O(1)
null test x.null() bool returns 'true' if the fraction is null 0/0 (default fraction) O(1)
even parity x.even() bool ! x.null() returns 'true' iff the fraction is even, i.e. k is even O(1)
odd parity x.odd() bool ! x.null() returns 'true' iff the fraction is odd, i.e. k is odd O(1)
left descendant x.left() X ! x.null() returns the left descendant of p/q in the Stern-Brocot tree O(1)
right descendant x.right() X ! x.null() returns the right descendant of p/q in the Stern-Brocot tree O(1)
father x.father() X ! x.null() returns the father of this fraction, ie \([u_0,...,u_k - 1]\) O(1)
m-father x.father(m) X ! x.null(), m>=0 returns the m-father of this fraction, ie \([u_0,...,u_{k-1}, m]\) O( m)
previousPartial x.previousPartial() X ! x.null() returns the previous partial of this fraction, ie \([u_0,...,u_{k-1}]\) O(1)
inverse x.inverse() X ! x.null() returns the inverse of this fraction, ie \([0,u_0,...,u_k]\) if \(u_0 \neq 0 \) or \([u_1,...,u_k]\) otherwise O(1)
m-th partial x.partial(m) X ! x.null() returns the m-th partial of this fraction, ie \([u_0,...,u_m]\) O(1)
m-th reduced x.reduced(m) X ! x.null() returns the m-th reduced of this fraction, equivalently the \(k-m\) partial, ie \([u_0,...,u_{k-m}]\) O(1)
splitting formula x.getSplit(x1, x2) void ! x.null() modifies fractions x1 and x2 such that \( x1 \oplus x2 = x \) O(1)
Berstel splitting formula x.getSplitBerstel(x1, n1, x2, n2) void ! x.null() modifies fractions x1 and x2 and integers n1 and n2 such that \( (x1)^{n1} \oplus (x2)^{n2} = x \) O(1)
Continued fraction coefficients x.getCFrac(quots) void modifies the vector quots such that it contains the quotients \(u_0,u_1,...,u_k \) O(k)
equality x.equals(p, q) bool returns 'true' iff the fraction is equal to \( p / q \). O(1)
less than x.lessThan(p, q) bool returns 'true' iff the fraction is inferior to \( p / q \). O(1)
more than x.moreThan(p, q) bool returns 'true' iff the fraction is superior to \( p / q \). O(1)
equality == x == y bool returns 'true' iff the fraction is equal to y. O(1)
inequality != x != y bool returns 'true' iff the fraction is different from y. O(1)
less than < x < y bool returns 'true' iff the fraction is inferior to y. O(1)
more than > x > y bool returns 'true' iff the fraction is superior to y. O(1)
Next continued fraction x.pushBack( pair ) transforms this fraction \([0,u_0,...,u_k]\) into \([0,u_0,...,u_k,m]\), where pair is \((m,k+1)\) O(m)
Next continued fraction x.push_back( pair ) transforms this fraction \([0,u_0,...,u_k]\) into \([0,u_0,...,u_k,m]\), where pair is \((m,k+1)\) O(m)
Begin visiting quotients x.begin() ConstIterator returns a forward iterator on the beginning of the sequence of quotients \([u_0,...,u_k]\)
End visiting quotients x.end() ConstIterator returns a forward iterator after the end of the sequence of quotients \([u_0,...,u_k]\)

Invariants

Models

Notes

Template Parameters
Tthe type that should be a model of CPositiveIrreducibleFraction.

Definition at line 161 of file CPositiveIrreducibleFraction.h.

Member Typedef Documentation

◆ const_iterator

template<typename T >
typedef T::const_iterator DGtal::concepts::CPositiveIrreducibleFraction< T >::const_iterator

Definition at line 172 of file CPositiveIrreducibleFraction.h.

◆ ConstIterator

template<typename T >
typedef T::ConstIterator DGtal::concepts::CPositiveIrreducibleFraction< T >::ConstIterator

Definition at line 171 of file CPositiveIrreducibleFraction.h.

◆ Integer

template<typename T >
typedef T::Integer DGtal::concepts::CPositiveIrreducibleFraction< T >::Integer

Definition at line 167 of file CPositiveIrreducibleFraction.h.

◆ Quotient

template<typename T >
typedef T::Quotient DGtal::concepts::CPositiveIrreducibleFraction< T >::Quotient

Definition at line 168 of file CPositiveIrreducibleFraction.h.

◆ Value

template<typename T >
typedef T::Value DGtal::concepts::CPositiveIrreducibleFraction< T >::Value

Definition at line 170 of file CPositiveIrreducibleFraction.h.

◆ value_type

template<typename T >
typedef T::value_type DGtal::concepts::CPositiveIrreducibleFraction< T >::value_type

Definition at line 169 of file CPositiveIrreducibleFraction.h.

Member Function Documentation

◆ BOOST_CONCEPT_ASSERT() [1/2]

template<typename T >
DGtal::concepts::CPositiveIrreducibleFraction< T >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< Integer >)  )

◆ BOOST_CONCEPT_ASSERT() [2/2]

template<typename T >
DGtal::concepts::CPositiveIrreducibleFraction< T >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< Quotient >)  )

◆ BOOST_CONCEPT_USAGE()

◆ BOOST_STATIC_ASSERT() [1/2]

template<typename T >
DGtal::concepts::CPositiveIrreducibleFraction< T >::BOOST_STATIC_ASSERT ( (concepts::ConceptUtils::SameType< value_type, std::pair< Quotient, Quotient > >::value)  )

◆ BOOST_STATIC_ASSERT() [2/2]

template<typename T >
DGtal::concepts::CPositiveIrreducibleFraction< T >::BOOST_STATIC_ASSERT ( (concepts::ConceptUtils::SameType< value_type, Value >::value)  )

◆ checkConstConstraints()

template<typename T >
void DGtal::concepts::CPositiveIrreducibleFraction< T >::checkConstConstraints ( ) const
inline

Definition at line 186 of file CPositiveIrreducibleFraction.h.

187  {
199  concepts::ConceptUtils::sameType( myX, myX.previousPartial() );
203  myX.getSplit( myF1, myF2 );
204  myX.getSplitBerstel( myF1, myN1, myF2, myN2 );
205  myX.getCFrac( myQuots );
215  }

References DGtal::concepts::CPositiveIrreducibleFraction< T >::myBool, DGtal::concepts::CPositiveIrreducibleFraction< T >::myF1, DGtal::concepts::CPositiveIrreducibleFraction< T >::myF2, DGtal::concepts::CPositiveIrreducibleFraction< T >::myIterator, DGtal::concepts::CPositiveIrreducibleFraction< T >::myN1, DGtal::concepts::CPositiveIrreducibleFraction< T >::myN2, DGtal::concepts::CPositiveIrreducibleFraction< T >::myP, DGtal::concepts::CPositiveIrreducibleFraction< T >::myQ, DGtal::concepts::CPositiveIrreducibleFraction< T >::myQuots, DGtal::concepts::CPositiveIrreducibleFraction< T >::myU, DGtal::concepts::CPositiveIrreducibleFraction< T >::myX, DGtal::concepts::CPositiveIrreducibleFraction< T >::myY, and DGtal::concepts::ConceptUtils::sameType().

Referenced by DGtal::concepts::CPositiveIrreducibleFraction< T >::BOOST_CONCEPT_USAGE().

Field Documentation

◆ myBool

◆ myF1

◆ myF2

◆ myIterator

◆ myN1

◆ myN2

◆ myP

◆ myQ

◆ myQuots

template<typename T >
std::vector<Quotient> DGtal::concepts::CPositiveIrreducibleFraction< T >::myQuots
mutableprivate

◆ myU

◆ myValue

◆ myX

◆ myY


The documentation for this struct was generated from the following file: