#include <LighterSternBrocot.h>

Collaboration diagram for DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node:

Public Member Functions
	Node (Integer p1, Integer q1, Quotient u1, Quotient k1, Node *_origin)
Node *	child (Quotient v)
Node *	origin () const
Node *	ancestor () const
Node *	father () const
bool	even () const
bool	odd () const
bool	isSameDepthLeft () const

Data Fields
Integer	p
Integer	q
Quotient	u
Quotient	k
Node *	myOrigin
MapQuotientToNode	myChildren

Detailed Description

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
struct DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node

Represents a node in the Stern-Brocot. The node stores information on the irreducible fraction itself (p/q, the partial quotient u, the depth k), but also pointers to ascendant and descendants in the Stern-Brocot tree. Nodes are constructed on demand, when the user ask for a descendant or for a specific fraction.

The LighterSternBrocot instances only fractions greater than or equal to 1/1. The node 0/1 does not exist. It is the inverse of 1/0. Given a fraction [u_0,...,u_n], for u_n >= 2, its origin is [u_0,...,u_{n-1},1]. The k-th son, k >= 2, of [u_0,...,u_n] is the fraction [u_0,...,u_n - 1, k].

See also:: LighterSternBrocot::fraction

Definition at line 140 of file LighterSternBrocot.h.

Constructor & Destructor Documentation

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::Node	(	Integer	p1,
		Integer	q1,
		Quotient	u1,
		Quotient	k1,
		Node *	_origin
	)

inline

Constructor for node.

Parameters:

p1	the numerator.
q1	the denominator.
u1	the quotient (last coefficient of its continued fraction).
k1	the depth (1+number of coefficients of its continued fraction).
<em>origin	A pointer to the origin node [u_0,...,u{n-1},1].

Definition at line 50 of file LighterSternBrocot.ih.

  : p( p1 ), q( q1 ), u( u1 ), k( k1 ), 
    myOrigin( _origin )
{
  ASSERT( p >= NumberTraits<Integer>::ONE );
  //  if ( k == 0 )
  // std::cerr << "(" << p1 << "/" << q1 << "," << u1 << "," << k1 << ")";
}

Member Function Documentation

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node * DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::ancestor ( ) const

inline

Returns:: the ancestor of this fraction in O(1), ie [u0,...,u_{k-1},uk] => [u0,...,u_{k-1}] if u_{k-1} > 1, => [u0,...,u_{k-2}] otherwise. Equivalent to reduced( 1 ).

Definition at line 119 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::child(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::instance(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::myOneOverZero, DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::origin(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::u.

{
  ASSERT( origin() != 0 );
  Node* prevNode = origin();
  Quotient _u = prevNode->u;
  prevNode = prevNode->origin();
  if ( prevNode == 0 ) return instance().myOneOverZero;
  return prevNode->child( _u - NumberTraits<Quotient>::ONE );
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node * DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::child ( Quotient v )

inline

Returns:: the node [u_0, ..., u_n - 1, v] if [u_0, ..., u_n] is the current node. Construct it if it does not exist yet.

Definition at line 64 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::instance(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::myOneOverOne, DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::myOneOverZero, and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::nbFractions.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::ancestor(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::father(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::Fraction(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::left(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::next(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::reduced(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::right().

{
  typedef typename MapQuotientToNode::iterator Iterator;
  ASSERT( v != NumberTraits<Quotient>::ZERO );
  if ( v == NumberTraits<Quotient>::ONE ) 
    return ( this == instance().myOneOverZero )
      ? instance().myOneOverOne
      : this;
  Iterator itkey = myChildren.find( v );
  if ( itkey != myChildren.end() ) 
    return itkey->second;
  if ( this == instance().myOneOverZero )
    {
      Node* newNode = 
        new Node( (int) NumberTraits<Quotient>::castToInt64_t( v ),  // p' = v
                  NumberTraits<Integer>::ONE,              // q' = 1
                  v,                                       // u' = v
                  NumberTraits<Quotient>::ZERO,                // k' = 0
                  this );
      myChildren[ v ] = newNode;
      ++( instance().nbFractions );
      return newNode;
    }
  long int _v = NumberTraits<Quotient>::castToInt64_t( v );
  long int _u = NumberTraits<Quotient>::castToInt64_t( this->u );
  Integer _pp = origin() == instance().myOneOverZero 
    ? NumberTraits<Integer>::ONE
    : origin()->p;
  Integer _qq = origin() == instance().myOneOverZero
    ? NumberTraits<Integer>::ONE
    : origin()->q;
  Node* newNode = // p' = v*p - (v-1)*(p-p2)/(u-1)
    new Node( p * _v - ( _v - 1 ) * ( p - _pp ) / (_u - 1), 
              q * _v - ( _v - 1 ) * ( q - _qq ) / (_u - 1), 
              v,                           // u' = v
              k + NumberTraits<Quotient>::ONE, // k' = k+1
              this );
  myChildren[ v ] = newNode;
  ++( instance().nbFractions );
  return newNode;
}

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

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::even ( ) const

inline

Returns:: 'true' iff this node has an even depth.

Definition at line 194 of file LighterSternBrocot.h.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::k.

                               {
        return NumberTraits<Quotient>::even( k );
      }

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node * DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::father ( ) const

inline

Returns:: the father of this fraction in O(1), ie [u0,...,uk] => [u0,.. .,uk - 1]

Definition at line 133 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::child(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::instance(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::myOneOverZero.

{
  ASSERT( origin() != 0 );
  Node* prevNode = origin();
  if ( this->u == NumberTraits<Quotient>::ONE ) // 1/1
    return instance().myOneOverZero;
  return prevNode->child( this->u - NumberTraits<Quotient>::ONE );
}

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

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::isSameDepthLeft ( ) const

inline

Returns:: 'true' iff the descendant with the same depth is to the left.

Definition at line 202 of file LighterSternBrocot.h.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::odd().

                                          {
        return odd();
      }

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

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::odd ( ) const

inline

Returns:: 'true' iff this node has an odd depth.

Definition at line 198 of file LighterSternBrocot.h.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::k.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::isSameDepthLeft().

                              {
        return NumberTraits<Quotient>::odd( k );
      }

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node * DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::origin ( ) const

inline

Returns:: the origin of this node in O(1), ie [u0,...,uk] => [u0,...,u_{k-1},1], i.e. [u0,...,u_{k-1}+1].

Definition at line 110 of file LighterSternBrocot.ih.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::ancestor(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::left(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::next(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::reduced(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::right().

{
  return myOrigin;
}

Field Documentation

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

Quotient DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::k

the depth (1+number of coefficients of its continued fraction).

Definition at line 184 of file LighterSternBrocot.h.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::even(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::odd(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::trueK().

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

MapQuotientToNode DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::myChildren

a map which gives the descendant [u_0,...,u_n - 1, k] if k is the key. Note that they are left or right descendant according to the parity of the depth. (odd=left, even=right).

Definition at line 190 of file LighterSternBrocot.h.

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

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

Node* DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::myOrigin

A pointer to the origin node [u_0,...,u_{n-1},1].

Definition at line 186 of file LighterSternBrocot.h.

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

Integer DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::p

the numerator;

Definition at line 178 of file LighterSternBrocot.h.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator==().

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