DGtal  0.9.3beta
Public Member Functions | Data Fields
DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node Struct Reference

#include <DGtal/arithmetic/LighterSternBrocot.h>

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

Public Member Functions

 Node (Integer p1, Integer q1, Quotient u1, Quotient k1, Node *anOrigin)
 
Nodechild (Quotient v)
 
Nodeorigin () const
 
Nodeancestor () const
 
Nodefather () const
 
bool even () const
 
bool odd () const
 
bool isSameDepthLeft () const
 

Data Fields

Integer p
 
Integer q
 
Quotient u
 
Quotient k
 
NodemyOrigin
 
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 139 of file LighterSternBrocot.h.

Constructor & Destructor Documentation

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::Node ( Integer  p1,
Integer  q1,
Quotient  u1,
Quotient  k1,
Node anOrigin 
)

Constructor for node.

Parameters
p1the numerator.
q1the denominator.
u1the quotient (last coefficient of its continued fraction).
k1the depth (1+number of coefficients of its continued fraction).
anOriginA pointer to the origin node [u_0,...,u_{n-1},1].

Member Function Documentation

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Node* DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::ancestor ( ) const
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 ).
template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Node* DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::child ( Quotient  v)
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.
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 193 of file LighterSternBrocot.h.

References DGtal::NumberTraits< T >::even().

193  {
195  }
static bool even(ParamType aT)
Definition: NumberTraits.h:162
Quotient k
the depth (1+number of coefficients of its continued fraction).
template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Node* DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::father ( ) const
Returns
the father of this fraction in O(1), ie [u0,...,uk] => [u0,.. .,uk - 1]
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 201 of file LighterSternBrocot.h.

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

201  {
202  return odd();
203  }
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 197 of file LighterSternBrocot.h.

References DGtal::NumberTraits< T >::odd().

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

197  {
198  return NumberTraits<Quotient>::odd( k );
199  }
Quotient k
the depth (1+number of coefficients of its continued fraction).
static bool odd(ParamType aT)
Definition: NumberTraits.h:170
template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Node* DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::origin ( ) const
Returns
the origin of this node in O(1), ie [u0,...,uk] => [u0,...,u_{k-1},1], i.e. [u0,...,u_{k-1}+1].

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 183 of file LighterSternBrocot.h.

Referenced by 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 189 of file LighterSternBrocot.h.

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 185 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 177 of file LighterSternBrocot.h.

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

the denominator;

Definition at line 179 of file LighterSternBrocot.h.

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

the quotient (last coefficient of its continued fraction).

Definition at line 181 of file LighterSternBrocot.h.


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