LighterSternBrocot.h

#pragma once

#if defined(LighterSternBrocot_RECURSES)
#error Recursive header files inclusion detected in LighterSternBrocot.h
#else // defined(LighterSternBrocot_RECURSES)

#define LighterSternBrocot_RECURSES

#if !defined LighterSternBrocot_h

#define LighterSternBrocot_h

// Inclusions
#include <iostream>
#include <vector>
#include "DGtal/base/Common.h"
#include "DGtal/base/StdRebinders.h"
#include "DGtal/base/InputIteratorWithRankOnSequence.h"
#include "DGtal/kernel/CInteger.h"
#include "DGtal/kernel/CSignedInteger.h"
#include "DGtal/kernel/NumberTraits.h"

namespace DGtal
{

  // template class LighterSternBrocot
  template <typename TInteger, typename TQuotient, 
            typename TMap = StdMapRebinder >
  class LighterSternBrocot
  {
  public:
    typedef TInteger Integer;
    typedef TQuotient Quotient;
    typedef TMap Map;
    typedef LighterSternBrocot<TInteger,TQuotient,TMap> Self;
    
    BOOST_CONCEPT_ASSERT(( CInteger< Integer > ));
    BOOST_CONCEPT_ASSERT(( CSignedInteger< Quotient > ));

    struct Node;
    typedef typename TMap:: template Rebinder<Quotient, Node*>::Type MapQuotientToNode;

  public:

    struct Node {

      Node( Integer p1, Integer q1, Quotient u1, Quotient k1, 
            Node* _origin );

      Node* child( Quotient v );

      Node* origin() const;

      Node* ancestor() const;
      Node* father() const;

      Integer p;
      Integer q;
      Quotient u;
      Quotient k;
      Node* myOrigin;
      MapQuotientToNode myChildren;


      inline bool even() const {
        return NumberTraits<Quotient>::even( k );
      }
      inline bool odd() const {
        return NumberTraits<Quotient>::odd( k );
      }
      inline bool isSameDepthLeft() const {
        return odd();
      }
      
    };

    class Fraction {
    public:
      typedef TInteger Integer;
      typedef TQuotient Quotient;
      typedef LighterSternBrocot<TInteger, TQuotient, TMap> 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; 
      bool mySup1;

    public:      
      Fraction( Integer aP, Integer aQ,
                Fraction start = SternBrocotTree::zeroOverOne() );

      Fraction( Node* sb_node = 0, bool sup1 = false );

      Fraction( const Self & other );

      Self& operator=( const Self & other );

      bool null() const;
      Integer p() const;
      Integer q() const;
      Quotient u() const;
      Quotient k() const;

      bool isSup1() const { return mySup1; }
      Quotient trueK() const { return myNode->k; }

    protected:
      Fraction child( Quotient v ) const;
      Fraction origin() const;
      Fraction next( Quotient v ) const;

    public:

      Fraction left() const;
      Fraction right() const;
      bool even() const; 
      bool odd() const; 

      Fraction ancestor() const;
      bool isAncestorDirect() 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;

    };



    // ----------------------- Standard services ------------------------------
  public:
    ~LighterSternBrocot();

    static LighterSternBrocot & instance();

    static Fraction zeroOverOne();

    static Fraction oneOverZero();

    static Fraction oneOverOne();

    static Fraction fraction( Integer p, Integer q, 
                              Fraction ancestor = oneOverZero()  );

    // ----------------------- Interface --------------------------------------
  public:

    static void display ( std::ostream & out, const Fraction & f );

    bool isValid() const;

    Quotient nbFractions;

    // ------------------------- Protected Datas ------------------------------
  protected:
    // ------------------------- Private Datas --------------------------------
  private:

    static LighterSternBrocot* singleton;

    Node* myOneOverZero;
    Node* myOneOverOne;

    // ------------------------- Hidden services ------------------------------
  protected:

  private:

    LighterSternBrocot();

    LighterSternBrocot ( const LighterSternBrocot & other );

    LighterSternBrocot & operator= ( const LighterSternBrocot & other );

    // ------------------------- Internals ------------------------------------
  private:

  }; // end of class LighterSternBrocot


  // template <typename TInteger, typename TQuotient, typename TMap>
  // std::ostream&
  // operator<< ( std::ostream & out, 
  //              const typename LighterSternBrocot<TInteger, TQuotient, TMap>::Fraction & object );

} // namespace DGtal


// Includes inline functions.
#include "DGtal/arithmetic/LighterSternBrocot.ih"

//                                                                           //

#endif // !defined LighterSternBrocot_h

#undef LighterSternBrocot_RECURSES
#endif // else defined(LighterSternBrocot_RECURSES)