SternBrocot.h

 
#pragma once
 
#if defined(SternBrocot_RECURSES)
#error Recursive header files inclusion detected in SternBrocot.h
#else // defined(SternBrocot_RECURSES)
#define SternBrocot_RECURSES
 
#if !defined SternBrocot_h
#define SternBrocot_h
 
// Inclusions
#include <iostream>
#include <vector>
#include "DGtal/base/Common.h"
#include "DGtal/base/InputIteratorWithRankOnSequence.h"
#include "DGtal/kernel/CInteger.h"
#include "DGtal/kernel/NumberTraits.h"
 
namespace DGtal
{
 
  // template class SternBrocot
  template <typename TInteger, typename TQuotient = int32_t>
  class SternBrocot
  {
  public:
    typedef TInteger Integer;
    typedef TQuotient Quotient;
    typedef SternBrocot<Integer,Quotient> Self;
    
    BOOST_CONCEPT_ASSERT(( concepts::CInteger< Integer > ));
 
  public:
 
    struct Node {
 
      Node( Integer p1, Integer q1, Quotient u1, Quotient k1, 
            Node* ascendant_left1, Node* ascendant_right1, 
            Node* descendant_left1, Node* descendant_right1,
            Node* inverse1 );
 
      Integer p;
      Integer q;
      Quotient u;
      Quotient k;
      Node* ascendantLeft;
      Node* ascendantRight;
      Node* descendantLeft;
      Node* descendantRight;
      Node* inverse;
    };
 
    class Fraction {
    public:
      typedef TInteger Integer;
      typedef TQuotient Quotient;
      typedef SternBrocot<TInteger,TQuotient> SternBrocotTree;
      typedef typename SternBrocotTree::Fraction Self;
      typedef typename NumberTraits<Integer>::UnsignedVersion UnsignedInteger;
      typedef std::pair<Quotient, Quotient> Value;
      typedef std::vector<Quotient> CFracSequence;
      typedef InputIteratorWithRankOnSequence<CFracSequence,Quotient> ConstIterator;
 
      // --------------------- std types ------------------------------
      typedef Value value_type;
      typedef ConstIterator const_iterator;
      typedef const value_type & const_reference;
 
    private:
      Node* myNode; 
 
    public:
      Fraction( Integer aP, Integer aQ,
                Fraction ancestor = SternBrocotTree::zeroOverOne() );
 
      Fraction( Node* sb_node = 0 );
 
      Fraction( const Self & other );
 
      Self& operator=( const Self & other );
 
      bool null() const;
      Integer p() const;
      Integer q() const;
      Quotient u() const;
      Quotient k() const;
      Fraction left() const;
      Fraction right() const;
      bool even() const; 
      bool odd() const; 
      Fraction father() const;
      Fraction father( Quotient m ) const;
      Fraction previousPartial() const;
      Fraction inverse() const;
      Fraction partial( Quotient kp ) const;
      Fraction reduced( Quotient i ) const;
 
      void push_back( const std::pair<Quotient, Quotient> & quotient );
 
      void pushBack( const std::pair<Quotient, Quotient> & quotient );
 
      void getSplit( Fraction & f1, Fraction & f2 ) const; 
 
      void getSplitBerstel( Fraction & f1, Quotient & nb1, 
                            Fraction & f2, Quotient & nb2 ) const; 
 
      void getCFrac( std::vector<Quotient> & quotients ) const;
 
      bool equals( Integer p1, Integer q1 ) const;
 
      bool lessThan( Integer p1, Integer q1 ) const;
 
      bool moreThan( Integer p1, Integer q1 ) const;
 
      bool operator==( const Fraction & other ) const;
 
      bool operator!=( const Fraction & other ) const;
 
      bool operator<( const Fraction & other ) const;
 
      bool operator>( const Fraction & other ) const;
 
      void selfDisplay ( std::ostream & out ) const;
 
      ConstIterator begin() const;
 
      ConstIterator end() const;
      
      Fraction median(const Fraction & g) const;
      
 
      Fraction simplestFractionInBetween(const Fraction & other) const;
        
    };
 
  
 
    // ----------------------- Standard services ------------------------------
  public:
 
    ~SternBrocot();
 
    static SternBrocot & instance();
 
    static Fraction zeroOverOne();
 
    static Fraction oneOverZero();
 
    static Fraction fraction( Integer p, Integer q,
                              Fraction ancestor = zeroOverOne() );
 
    // ----------------------- Interface --------------------------------------
  public:
 
    static void display ( std::ostream & out, const Fraction & f );
 
    bool isValid() const;
 
    Quotient nbFractions;
 
    // ------------------------- Protected Datas ------------------------------
  private:
    // ------------------------- Private Datas --------------------------------
  private:
    static SternBrocot* singleton;
 
    Node* myZeroOverOne;
    Node* myOneOverZero;
    Node* myOneOverOne;
 
    // ------------------------- Hidden services ------------------------------
  private:
 
    SternBrocot();
 
    SternBrocot ( const SternBrocot & other );
 
    SternBrocot & operator= ( const SternBrocot & other );
 
    // ------------------------- Internals ------------------------------------
  private:
 
  }; // end of class SternBrocot
 
 
  // template <typename TInteger, typename TQuotient>
  // std::ostream&
  // operator<< ( std::ostream & out, 
  //              const typename SternBrocot<TInteger, TQuotient>::Fraction & object );
 
} // namespace DGtal
 
 
// Includes inline functions.
#include "DGtal/arithmetic/SternBrocot.ih"
 
//                                                                           //
 
#endif // !defined SternBrocot_h
 
#undef SternBrocot_RECURSES
#endif // else defined(SternBrocot_RECURSES)