#include <LightSternBrocot.h>

Collaboration diagram for DGtal::LightSternBrocot< TInteger, TQuotient, TMap >:

Data Structures
class	Fraction
	This fraction is a model of CPositiveIrreducibleFraction. More...
struct	Node

Public Types
typedef TInteger	Integer
typedef TQuotient	Quotient
typedef TMap	Map
typedef LightSternBrocot < TInteger, TQuotient, TMap >	Self
typedef TMap::template Rebinder< Quotient, Node * > ::Type	MapQuotientToNode

Public Member Functions
	BOOST_CONCEPT_ASSERT ((CInteger< Integer >))
	BOOST_CONCEPT_ASSERT ((CSignedInteger< Quotient >))
	~LightSternBrocot ()
bool	isValid () const

Static Public Member Functions
static LightSternBrocot &	instance ()
static Fraction	zeroOverOne ()
static Fraction	oneOverZero ()
static Fraction	fraction (Integer p, Integer q, Fraction ancestor=zeroOverOne())
static void	display (std::ostream &out, const Fraction &f)

Data Fields
Quotient	nbFractions

Private Member Functions
	LightSternBrocot ()
	LightSternBrocot (const LightSternBrocot &other)
LightSternBrocot &	operator= (const LightSternBrocot &other)
template<>
LightSternBrocot < DGtal::int32_t, DGtal::int32_t > *	singleton
template<>
LightSternBrocot < DGtal::int64_t, DGtal::int32_t > *	singleton
template<>
LightSternBrocot < DGtal::int64_t, DGtal::int64_t > *	singleton

Private Attributes
Node *	myZeroOverOne
Node *	myOneOverZero
Node *	myOneOverOne

Static Private Attributes
static LightSternBrocot *	singleton = 0

Detailed Description

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
class DGtal::LightSternBrocot< TInteger, TQuotient, TMap >

Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it progressively and to navigate within fractions in O(1) time for most operations. It is well known that the structure of this tree is a coding of the continued fraction representation of fractions.

Description of template class 'LightSternBrocot'

There are two main differences with the class SternBrocot. The first one is that inverses are not stored. With this optimization, there are twice less nodes and each node is lighter. The second one lies in the access to the children of a node. Here, a map type M is provided so that a node [u_0; u_1, ..., u_n] can access its child node [u_0; u_1, ..., u_n, k] in the time of the operation M::operator[].

In this representation, the fraction 1/1 has depth 1, like 1/2, 1/3, etc. Furthermore, each fraction has an ancestor, which is the reduced partial of order 1 of the fraction. Be careful the ancestor of an ancestor is not the reduced of order 2. Each node [u_0; u_1, ..., u_n] has two sets of children: the nodes [u_0; u_1, ..., u_n, k], for k >= 2, and the nodes [u_0; u_1, ..., u_n - 1, 1, k], for k >= 2. A disadvantage of this representation is that to obtain the father of something like [...,u_k, 1, ..., 1, u_n ], one has to go up the tree till u_k, to go back down on the other side.

In practice, although this class has supposedly a better complexity than SternBrocot, it is 1% slower for integers smaller than 10^9 and 5% slower for integers smaller than 10^4. Note however that it takes like 6 times less memory (and asymptotically less when the number of computations tends toward infinity).

This class is not to be instantiated, since it is useless to duplicate it. Use static method LightSternBrocot::fraction to obtain your fractions.

Parameters:

TInteger	the integral type chosen for the fractions.
TQuotient	the integral type chosen for the quotients/coefficients or depth (may be "smaller" than TInteger, since they are generally much smaller than the fraction itself).
TMap	the rebinder type for defining an association TQuotient -> LighterSternBrocot::Node*. For instance, StdMapRebinder is fine.

Definition at line 108 of file LightSternBrocot.h.

Member Typedef Documentation

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef TInteger DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Integer

Definition at line 111 of file LightSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef TMap DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Map

Definition at line 113 of file LightSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef TMap:: template Rebinder<Quotient, Node*>::Type DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::MapQuotientToNode

Definition at line 119 of file LightSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef TQuotient DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Quotient

Definition at line 112 of file LightSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef LightSternBrocot<TInteger,TQuotient,TMap> DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Self

Definition at line 114 of file LightSternBrocot.h.

Constructor & Destructor Documentation

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::~LightSternBrocot ( )

inline

Destructor.

Definition at line 631 of file LightSternBrocot.ih.

References DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::myOneOverOne, DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::myOneOverZero, and DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::myZeroOverOne.

{
  if ( myZeroOverOne != 0 ) delete myZeroOverOne;
  if ( myOneOverZero != 0 ) delete myOneOverZero;
  if ( myOneOverOne != 0 ) delete myOneOverOne;
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::LightSternBrocot ( )

inlineprivate

Constructor. Hidden since singleton class.

Definition at line 640 of file LightSternBrocot.ih.

References DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Node::ascendant, DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Node::descendant, DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Node::descendant2, DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::myOneOverOne, DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::myOneOverZero, DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::myZeroOverOne, and DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::nbFractions.

Referenced by DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::instance().

{
  // // Version 1/1 has depth 0.
  // myOneOverZero = new Node( NumberTraits<Integer>::ONE,
  //                           NumberTraits<Integer>::ZERO,
  //                           NumberTraits<Quotient>::ZERO,
  //                           -NumberTraits<Quotient>::ONE,
  //                           0 );
  // myZeroOverOne = new Node( NumberTraits<Integer>::ZERO,
  //                           NumberTraits<Integer>::ONE,
  //                           NumberTraits<Quotient>::ZERO,
  //                           NumberTraits<Quotient>::ZERO,
  //                           myOneOverZero );
  // myOneOverZero->ascendant = 0; //myZeroOverOne;
  // myOneOverOne = new Node( NumberTraits<Integer>::ONE,
  //                          NumberTraits<Integer>::ONE,
  //                          NumberTraits<Quotient>::ONE,
  //                          NumberTraits<Quotient>::ZERO,
  //                          myOneOverZero );
  // myOneOverZero->descendant[ NumberTraits<Quotient>::ZERO ] = myZeroOverOne;
  // myOneOverZero->descendant[ NumberTraits<Quotient>::ONE ] = myOneOverOne;
  // nbFractions = 3;
  // Version 1/1 has depth 1.
  myOneOverZero = new Node( NumberTraits<Integer>::ONE,
                            NumberTraits<Integer>::ZERO,
                            NumberTraits<Quotient>::ZERO,
                            -NumberTraits<Quotient>::ONE,
                            0 );
  myZeroOverOne = new Node( NumberTraits<Integer>::ZERO,
                            NumberTraits<Integer>::ONE,
                            NumberTraits<Quotient>::ZERO,
                            NumberTraits<Quotient>::ZERO,
                            myOneOverZero );
  myOneOverZero->ascendant = 0;
  myOneOverOne = new Node( NumberTraits<Integer>::ONE,
                           NumberTraits<Integer>::ONE,
                           NumberTraits<Quotient>::ONE,
                           NumberTraits<Quotient>::ONE,
                           myZeroOverOne );
  myZeroOverOne->descendant[ NumberTraits<Quotient>::ONE ] = myOneOverOne;
  myOneOverZero->descendant[ NumberTraits<Quotient>::ZERO ] = myZeroOverOne;
  myOneOverZero->descendant[ NumberTraits<Quotient>::ONE ] = myZeroOverOne;
  myOneOverZero->descendant2[ NumberTraits<Quotient>::ONE ] = myOneOverOne;
  nbFractions = 3;
}

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::LightSternBrocot ( const LightSternBrocot< TInteger, TQuotient, TMap > & other )

private

Copy constructor.

Parameters:

other the object to clone. Forbidden by default.

Member Function Documentation

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::BOOST_CONCEPT_ASSERT ( (CInteger< Integer >) )

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::BOOST_CONCEPT_ASSERT ( (CSignedInteger< Quotient >) )

template<typename TInteger , typename TQuotient , typename TMap >

void DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::display	(	std::ostream &	out,
		const Fraction &	f
	)

inlinestatic

Writes/Displays the fraction on an output stream.

Parameters:

out	the output stream where the object is written.
f	the fraction to display.

Writes/Displays the object on an output stream.

Parameters:

out	the output stream where the object is written.

Definition at line 724 of file LightSternBrocot.ih.

References DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::getCFrac(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::k(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::null(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::p(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::q(), and DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::u().

{
  if ( f.null() ) out << "[Fraction null]";
  else
    {
      out << "[Fraction f=" << f.p() 
          << "/" << f.q()
          << " u=" << f.u()
          << " k=" << f.k()
        // << " s1=" << f.isSup1() 
          << std::flush;
      std::vector<Quotient> quotients;
      if ( f.k() >= 0 )
        {
          f.getCFrac( quotients );
          out << " [" << quotients[ 0 ];
          for ( unsigned int i = 1; i < quotients.size(); ++i )
            out << "," << quotients[ i ];
          out << "]";
        }
      out << " ]";
    }
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::fraction	(	Integer	p,
		Integer	q,
		Fraction	ancestor = `zeroOverOne()`
	)

inlinestatic

Creates the fraction p/q.

Parameters:

p	the numerator (>=0)
q	the denominator (>=0)
ancestor	(optional) unused in this representation.

Returns:: the corresponding fraction in the Stern-Brocot tree.

NB: Complexity is bounded by n where n is the depth of the continued fraction of p/q.

Definition at line 768 of file LightSternBrocot.ih.

{
  return Fraction( p, q );
  // // special case 1/0
  // if ( ( p == NumberTraits<Integer>::ONE ) 
  //      && ( q == NumberTraits<Integer>::ZERO ) ) 
  //   return oneOverZero();
  // Fraction f = zeroOverOne();
  // bool sup1 = p > q;
  // if ( sup1 ) std::swap( p, q );
  // Integer _quot, _rem;
  // IntegerComputer<Integer> ic;
  // Quotient v;
  // bool prec_was_one = false;
  // Quotient j = NumberTraits<Quotient>::ZERO;
  // while ( q != NumberTraits<Integer>::ZERO )
  //   {
  //     ic.getEuclideanDiv( _quot, _rem, p, q );
  //     v = NumberTraits<Integer>::castToInt64_t( _quot );
  //     if ( f.k() == j ) 
  //       f = f.next( v );
  //     else 
  //       f = f.next1( v );
  //     if ( v != 0 ) ++j;
  //     p = q;
  //     q = _rem;
  //   }
  // if ( prec_was_one ) f = f.next( NumberTraits<Quotient>::ONE );
  // return sup1 ? f.inverse() : f;
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LightSternBrocot< TInteger, TQuotient, TMap > & DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::instance ( )

inlinestatic

Returns:: the (only) instance of LightSternBrocot.

Definition at line 690 of file LightSternBrocot.ih.

References DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::LightSternBrocot(), and DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::singleton().

Referenced by DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::k(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::next(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::next1(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::oneOverZero(), and DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::zeroOverOne().

{
  if ( singleton == 0 )
    singleton = new LightSternBrocot;
  return *singleton;
}

template<typename TInteger , typename TQuotient , typename TMap >

bool DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::isValid ( ) const

inline

Checks the validity/consistency of the object.

Returns:: 'true' if the object is valid, 'false' otherwise.

Definition at line 756 of file LightSternBrocot.ih.

{
    return true;
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::oneOverZero ( )

inlinestatic

The fraction 1/0

Definition at line 709 of file LightSternBrocot.ih.

References DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::instance(), and DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::myZeroOverOne.

Referenced by DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::Fraction().

{
  return Fraction( instance().myZeroOverOne, true );
}

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

LightSternBrocot& DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::operator= ( const LightSternBrocot< TInteger, TQuotient, TMap > & other )

private

Assignment.

Parameters:

other the object to copy.

Returns:: a reference on 'this'. Forbidden by default.

Referenced by DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::Fraction().

template<>

LightSternBrocot< DGtal::int32_t, DGtal::int32_t > * DGtal::LightSternBrocot< DGtal::int32_t, DGtal::int32_t >::singleton ( )

private

Definition at line 57 of file LightSternBrocot.cpp.

Referenced by DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::instance().

template<>

LightSternBrocot< DGtal::int64_t, DGtal::int32_t > * DGtal::LightSternBrocot< DGtal::int64_t, DGtal::int32_t >::singleton ( )

private

Definition at line 61 of file LightSternBrocot.cpp.

template<>

LightSternBrocot< DGtal::int64_t, DGtal::int64_t > * DGtal::LightSternBrocot< DGtal::int64_t, DGtal::int64_t >::singleton ( )

private

Definition at line 65 of file LightSternBrocot.cpp.

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::zeroOverOne ( )

inlinestatic

The fraction 0/1

Definition at line 701 of file LightSternBrocot.ih.

References DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::instance(), and DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::myZeroOverOne.

Referenced by DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::Fraction().

{
  return Fraction( instance().myZeroOverOne, false );
}

Field Documentation

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

Node* DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::myOneOverOne

private

Definition at line 532 of file LightSternBrocot.h.

Referenced by DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::k(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::LightSternBrocot(), and DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::~LightSternBrocot().

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

Node* DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::myOneOverZero

private

Definition at line 531 of file LightSternBrocot.h.

Referenced by DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::k(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::LightSternBrocot(), and DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::~LightSternBrocot().

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

Node* DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::myZeroOverOne

private

Definition at line 530 of file LightSternBrocot.h.

Referenced by DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::k(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::LightSternBrocot(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::next(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::oneOverZero(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::zeroOverOne(), and DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::~LightSternBrocot().

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

Quotient DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::nbFractions

The total number of fractions in the current tree.

Definition at line 516 of file LightSternBrocot.h.

Referenced by DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::LightSternBrocot(), DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::next(), and DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::next1().

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

DGtal::LightSternBrocot< TInteger, TQuotient, TMap > * DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::singleton = 0

staticprivate

Singleton class.

Definition at line 524 of file LightSternBrocot.h.

The documentation for this class was generated from the following files:

Data Structures

Public Types

Public Member Functions

Static Public Member Functions

Data Fields

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder> class DGtal::LightSternBrocot< TInteger, TQuotient, TMap >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
class DGtal::LightSternBrocot< TInteger, TQuotient, TMap >