DGtal  0.9.4beta
Public Types | Public Member Functions | Private Attributes
DGtal::concepts::CPositiveIrreducibleFraction< T > Struct Template Reference

#include <DGtal/arithmetic/CPositiveIrreducibleFraction.h>

Inheritance diagram for DGtal::concepts::CPositiveIrreducibleFraction< T >:
[legend]
Collaboration 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 :

Notation

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 numeratorO(1)
denominator x.q() Integer ! x.null() returns the denominatorO(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 descendantx.left() X ! x.null() returns the left descendant of p/q in the Stern-Brocot tree O(1)
right descendantx.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)
previousPartialx.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 162 of file CPositiveIrreducibleFraction.h.

Member Typedef Documentation

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

Definition at line 173 of file CPositiveIrreducibleFraction.h.

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

Definition at line 172 of file CPositiveIrreducibleFraction.h.

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

Definition at line 168 of file CPositiveIrreducibleFraction.h.

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

Definition at line 169 of file CPositiveIrreducibleFraction.h.

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

Definition at line 171 of file CPositiveIrreducibleFraction.h.

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

Definition at line 170 of file CPositiveIrreducibleFraction.h.

Member Function Documentation

template<typename T >
DGtal::concepts::CPositiveIrreducibleFraction< T >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< Integer >)  )
template<typename T >
DGtal::concepts::CPositiveIrreducibleFraction< T >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< Quotient >)  )
template<typename T >
DGtal::concepts::CPositiveIrreducibleFraction< T >::BOOST_CONCEPT_USAGE ( CPositiveIrreducibleFraction< T >  )
inline
template<typename T >
DGtal::concepts::CPositiveIrreducibleFraction< T >::BOOST_STATIC_ASSERT ( (concepts::ConceptUtils::SameType< value_type, std::pair< Quotient, Quotient > >::value)  )
template<typename T >
DGtal::concepts::CPositiveIrreducibleFraction< T >::BOOST_STATIC_ASSERT ( (concepts::ConceptUtils::SameType< value_type, Value >::value)  )
template<typename T >
void DGtal::concepts::CPositiveIrreducibleFraction< T >::checkConstConstraints ( ) const
inline

Definition at line 187 of file CPositiveIrreducibleFraction.h.

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().

188  {
200  concepts::ConceptUtils::sameType( myX, myX.previousPartial() );
204  myX.getSplit( myF1, myF2 );
205  myX.getSplitBerstel( myF1, myN1, myF2, myN2 );
206  myX.getCFrac( myQuots );
216  }
void sameType(const T &t1, const T &t2)

Field Documentation

template<typename T >
bool DGtal::concepts::CPositiveIrreducibleFraction< T >::myBool
private
template<typename T >
T DGtal::concepts::CPositiveIrreducibleFraction< T >::myF1
mutableprivate
template<typename T >
T DGtal::concepts::CPositiveIrreducibleFraction< T >::myF2
mutableprivate
template<typename T >
ConstIterator DGtal::concepts::CPositiveIrreducibleFraction< T >::myIterator
private
template<typename T >
Quotient DGtal::concepts::CPositiveIrreducibleFraction< T >::myN1
mutableprivate
template<typename T >
Quotient DGtal::concepts::CPositiveIrreducibleFraction< T >::myN2
mutableprivate
template<typename T >
Integer DGtal::concepts::CPositiveIrreducibleFraction< T >::myP
private
template<typename T >
Integer DGtal::concepts::CPositiveIrreducibleFraction< T >::myQ
private
template<typename T >
std::vector<Quotient> DGtal::concepts::CPositiveIrreducibleFraction< T >::myQuots
mutableprivate
template<typename T >
Quotient DGtal::concepts::CPositiveIrreducibleFraction< T >::myU
private
template<typename T >
std::pair<Quotient,Quotient> DGtal::concepts::CPositiveIrreducibleFraction< T >::myValue
private
template<typename T >
T DGtal::concepts::CPositiveIrreducibleFraction< T >::myX
private
template<typename T >
T DGtal::concepts::CPositiveIrreducibleFraction< T >::myY
private

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