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 >:

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
T	myX

T	myY

Integer	myP

Integer	myQ

Quotient	myU

bool	myBool

Quotient	myN1

Quotient	myN2

T	myF1

T	myF2

std::vector< Quotient >	myQuots

std::pair< Quotient, Quotient >	myValue

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	Return type	Precondition	Semantics	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

SternBrocot::Fraction, LighterSternBrocot::Fraction
also LightSternBrocot::Fraction (but do not use).

Notes

Template Parameters

T	the type that should be a model of CPositiveIrreducibleFraction.

Definition at line 162 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 173 of file CPositiveIrreducibleFraction.h.

◆ ConstIterator

template<typename T >

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

Definition at line 172 of file CPositiveIrreducibleFraction.h.

◆ Integer

template<typename T >

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

Definition at line 168 of file CPositiveIrreducibleFraction.h.

◆ Quotient

template<typename T >

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

Definition at line 169 of file CPositiveIrreducibleFraction.h.

◆ Value

template<typename T >

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

Definition at line 171 of file CPositiveIrreducibleFraction.h.

◆ value_type

template<typename T >

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

Definition at line 170 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()

template<typename T >

DGtal::concepts::CPositiveIrreducibleFraction< T >::BOOST_CONCEPT_USAGE ( CPositiveIrreducibleFraction< T > )

inline

Definition at line 180 of file CPositiveIrreducibleFraction.h.

  {
    concepts::ConceptUtils::sameType( myX, T( myP, myQ ) );
    myX.push_back( myValue );
    myX.pushBack( myValue );
    checkConstConstraints();
  }

References DGtal::concepts::CPositiveIrreducibleFraction< T >::checkConstConstraints(), DGtal::concepts::CPositiveIrreducibleFraction< T >::myP, DGtal::concepts::CPositiveIrreducibleFraction< T >::myQ, DGtal::concepts::CPositiveIrreducibleFraction< T >::myValue, DGtal::concepts::CPositiveIrreducibleFraction< T >::myX, and DGtal::concepts::ConceptUtils::sameType().

◆ 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 187 of file CPositiveIrreducibleFraction.h.

  {
    concepts::ConceptUtils::sameType( myP, myX.p() );
    concepts::ConceptUtils::sameType( myQ, myX.q() );
    concepts::ConceptUtils::sameType( myU, myX.u() );
    concepts::ConceptUtils::sameType( myU, myX.k() );
    concepts::ConceptUtils::sameType( myBool, myX.null() );
    concepts::ConceptUtils::sameType( myX, myX.left() );
    concepts::ConceptUtils::sameType( myX, myX.right() );
    concepts::ConceptUtils::sameType( myBool, myX.even() );
    concepts::ConceptUtils::sameType( myBool, myX.odd() );
    concepts::ConceptUtils::sameType( myX, myX.father() );
    concepts::ConceptUtils::sameType( myX, myX.father( myU ) );
    concepts::ConceptUtils::sameType( myX, myX.previousPartial() );
    concepts::ConceptUtils::sameType( myX, myX.inverse() );
    concepts::ConceptUtils::sameType( myX, myX.partial( myU ) );
    concepts::ConceptUtils::sameType( myX, myX.reduced( myU ) );
    myX.getSplit( myF1, myF2 );
    myX.getSplitBerstel( myF1, myN1, myF2, myN2 );
    myX.getCFrac( myQuots );
    concepts::ConceptUtils::sameType( myBool, myX.equals( myP, myQ ) );
    concepts::ConceptUtils::sameType( myBool, myX.lessThan( myP, myQ ) );
    concepts::ConceptUtils::sameType( myBool, myX.moreThan( myP, myQ ) );
    concepts::ConceptUtils::sameType( myBool, myX == myY );
    concepts::ConceptUtils::sameType( myBool, myX != myY );
    concepts::ConceptUtils::sameType( myBool, myX < myY );
    concepts::ConceptUtils::sameType( myBool, myX > myY );
    concepts::ConceptUtils::sameType( myIterator, myX.begin() );
    concepts::ConceptUtils::sameType( myIterator, myX.end() );
  }