TemplateTools.h

Go to the documentation of this file.

/* Copyright (C) 2002, 2003, 2004 Bernd Speiser */
/* This file is part of BSUtilities.

BSUtilities is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

BSUtilities is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
  
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.
*/

/*
These classes are derived based on ideas and code in the following
books and articles:

A. Alexandrescu, Modern C++ Design, Addison Wesley, Boston, 2001

K. Czarnecki and U.W. Eisenecker, Generative Programming, 
Addison Wesley, Boston, 2000

W.E. Brown, Proceedings of the Second Workshop on C++ Template 
Programming, Oct. 14, 2001, Tampa Bay, Fla., USA;
http://www.oonumerics.org/tmpw01/brown.pdf

J.M. Bucknall, http://www.boyet.com/Articles/GcdfractionClass.html 

B.K.P. Horn, Rational Arithmetic for Minicomputers, 
Software - Practice and Experience 8, 171 - 176 (1978) 
*/

#ifndef _TemplateTools_h
#define _TemplateTools_h

#include "NullType.h"
#include "TypeManip.h"
#include "Typelist.h"

#include <limits>
#include <utility>
#include <cstdlib>
#include <cmath>

namespace BSUtilities {

//
// compile time logical decisions
//


template<bool condition, class Then, class Else>
  struct IF
  {
    typedef Then RET;
  };

template<class Then, class Else>
  struct IF<false, Then, Else>
  {
    typedef Else RET;
  };


template<bool Arg1, bool Arg2> 
  struct OR
  {
    enum {RET = false};
  };


template<bool Arg2> 
  struct OR<true, Arg2>
  {
    enum {RET = true};
  };


template<bool Arg1> 
  struct OR<Arg1, true>
  {
    enum {RET = true};
  };


template<> 
  struct OR<true, true>
  {
    enum {RET = true};
  };

//
// equivalence of types and templates
//


template<class X> class EmptyTemplate_1 {};


template<class X, class Y> class EmptyTemplate_2 {};


template<class X, class Y>
  struct SameType 
  {
    enum {sameType = false};
  };

template<class X>
  struct SameType<X, X> 
  {
    enum {sameType = true};
  };


template<template<class> class X, template<class> class Y>
  struct SameTemplate_1 
  {
    enum {sameTemplate_1 = false};
  };


template<template<class> class X>
  struct SameTemplate_1<X, X> 
  {
    enum {sameTemplate_1 = true};
  };


template<template<class, class> class X, template<class, class> class Y>
  struct SameTemplate_2 
  {
    enum {sameTemplate_2 = false};
  };


template<template<class, class> class X>
  struct SameTemplate_2<X, X> 
  {
    enum {sameTemplate_2 = true};
  };

//
// Loki::TYPELIST helpers
//


template<class A, class B> struct Concatenate;

template<class Head1, class Head2, class Tail1, class Tail2>  
struct Concatenate<Loki::Typelist<Head1, Tail1>, 
                                          Loki::Typelist<Head2, Tail2> >
  {typedef Loki::Typelist<Head1, 
    typename Concatenate<Tail1, Loki::Typelist<Head2, Tail2> >
                                                    ::Result > Result;};

template<class A> struct Concatenate<A, Loki::NullType> 
                                                    {typedef A Result;};

template<class B> struct Concatenate<Loki::NullType, B> 
                                                    {typedef B Result;};

//
// compile time Rational number calculations
//

template<long N>
  struct Signum {static long const RET = (N < 0L) ? -1L : +1L;};

template<> struct Signum<0L> {static long const RET = 0L;};

template<long N>
  struct Abs {static long const RET = (N < 0L) ? -N : N;};

template<long M, long N>
  struct Gcd
  {
    private:
      static long const m = Abs<M>::RET;
      static long const n = Abs<N>::RET;

    public:
      static long const RET = Gcd<n, m%n>::RET;
  };

template<long M> struct Gcd<M, 0L> 
                                {static long const RET = Abs<M>::RET;};

template<> struct Gcd<0L, 0L> {static long const RET = 1L;};


inline long gcd (const long &i1, const long &i2)
  {
    if (i2 == 0L && i1 == 0L)
      return 1L;
    else if (i2 == 0L)
      return std::abs(i1);
    else
      return gcd (std::abs(i2), std::abs (i1%i2));
  }


template<class T>
  std::pair<long, long> contFrac (const T &value)
    {
      bool isNegative = (value < T(0.0));

      long p1 = 0;
      long p2 = 1;
      long q1 = 1;
      long q2 = 0;

      long p0;
      long q0;

      long i = 0;
      T s = std::abs(value);

      long limit = std::numeric_limits<long>::max ();

      while (p2 < limit && q2 < limit)
      {
        p0 = p1;
        q0 = q1;
        p1 = p2;
        q1 = q2;

        i = long (floor (s));

        p2 = p0 + i * p1;
        q2 = q0 + i * q1;


        if (std::abs(std::abs(value) - T(p2)/T(q2)) 
                                   > std::numeric_limits<T>::epsilon ())
          s = 1/(s - floor(s));

        else
        {
          p1 = p2;
          q1 = q2;
          break;
        }
      } 

      if (isNegative)
        p1 = -p1;

      return std::make_pair (p1, q1);
    }

template<long N, long D=1L>
  struct Rational
  {
    private:
      static long const gcd = Signum<D>::RET * Gcd<N,D>::RET;

    public:
      static long const numerator = N;
      static long const denominator = D;

      typedef Rational<N/gcd, D/gcd> Canonical;

      template<class To>
        static To convert() 
                         {return static_cast<To>(N)/static_cast<To>(D);}

  };

template<long D>
  struct Rational<0L, D>
  {
    public:
      static long const numerator = 0L;
      static long const denominator = 1L;

      typedef Rational<0L, 1L> Canonical;

      template<class To>
                       static To convert() {return static_cast<To>(0);}
  };


template<class R1, class R2> class RationalEquality;
template<long N1, long D1, long N2, long D2> 
  class RationalEquality<Rational<N1, D1>, Rational<N2, D2> >
  {
    private:
      typedef Rational<N1, D1> R1;
      typedef Rational<N2, D2> R2;

    public:
      enum {RET = ((R1::Canonical::numerator 
                                         == R2::Canonical::numerator) 
          && (R1::Canonical::denominator == R2::Canonical::denominator))
                                                              ? 1 : 0 };
  };

template<class R1, class R2> class RationalAdd;

template<long N1, long D1, long N2, long D2>
  class RationalAdd<Rational<N1, D1>, Rational<N2, D2> >
  {
    private:
      typedef Rational<N1, D1> R1;
      typedef Rational<N2, D2> R2;

    public:
      typedef typename 
        Rational<R1::Canonical::numerator * R2::Canonical::denominator 
          + R2::Canonical::numerator * R1::Canonical::denominator, 
            R1::Canonical::denominator * R2::Canonical::denominator>
                                                        ::Canonical RET;
  };

template<class R1, class R2> class RationalSub;

template<long N1, long D1, long N2, long D2>
  class RationalSub<Rational<N1, D1>, Rational<N2, D2> >
  {
    private:
      typedef Rational<N1, D1> R1;
      typedef Rational<N2, D2> R2;

    public:
      typedef typename 
        Rational<R1::Canonical::numerator * R2::Canonical::denominator 
          - R2::Canonical::numerator * R1::Canonical::denominator, 
            R1::Canonical::denominator * R2::Canonical::denominator>
                                                        ::Canonical RET;
  };

template<class R1, class R2> class RationalMult;

template<long N1, long D1, long N2, long D2>
  class RationalMult<Rational<N1, D1>, Rational<N2, D2> >
  {
    private:
      typedef Rational<N1, D1> R1;
      typedef Rational<N2, D2> R2;

    public:
      typedef typename Rational<R1::Canonical::numerator 
        * R2::Canonical::numerator, R1::Canonical::denominator 
                           * R2::Canonical::denominator>::Canonical RET;
  };

template<class R1, class R2> class RationalDiv;

template<long N1, long D1, long N2, long D2>
  class RationalDiv<Rational<N1, D1>, Rational<N2, D2> >
  {
    private:
      typedef Rational<N1, D1> R1;
      typedef Rational<N2, D2> R2;

    public:
      typedef typename Rational<R1::Canonical::numerator 
        * R2::Canonical::denominator, R1::Canonical::denominator 
                           * R2::Canonical::numerator>::Canonical RET;
  };

template<class R1> class RationalNeg;

template<long N1, long D1>
  class RationalNeg<Rational<N1, D1> >
  {
    private:
      typedef Rational<N1, D1> R1;

    public:
      typedef typename Rational<-R1::Canonical::numerator, 
                             R1::Canonical::denominator>::Canonical RET;
  };

}

#endif /* _TemplateTools_h */

---