SeqAn-1.1/seqan/basic/basic_metaprogramming.h

   1  /*==========================================================================
   2                 SeqAn - The Library for Sequence Analysis
   3                           http://www.seqan.de
   4  ============================================================================
   5   Copyright (C) 2007
   6
   7   This library is free software; you can redistribute it and/or
   8   modify it under the terms of the GNU Lesser General Public
   9   License as published by the Free Software Foundation; either
  10   version 3 of the License, or (at your option) any later version.
  11
  12   This library is distributed in the hope that it will be useful,
  13   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15   Lesser General Public License for more details.
  16
  17  ============================================================================
  18   $Id: basic_metaprogramming.h,v 1.2 2009/02/19 01:51:23 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_BASIC_METAPROGRAMMING_H
  22 #define SEQAN_BASIC_METAPROGRAMMING_H
  23
  24 namespace SEQAN_NAMESPACE_MAIN
  25 {
  26
  27         //////////////////////////////////////////////////////////////////////////////
  28         // generic "if" (using meta-programming)
  29         // if Flag is true,  the resulting type is Type1
  30         // if Flag is false, the resulting type is Type2
  31         //////////////////////////////////////////////////////////////////////////////
  32
  33         template <bool Flag,class Type1, class Type2>
  34         struct IF
  35         {
  36                 typedef Type1 Type;
  37         };
  38
  39         template <class Type1, class Type2>
  40         struct IF<false,Type1,Type2>
  41         {
  42                 typedef Type2 Type;
  43         };
  44
  45
  46         //////////////////////////////////////////////////////////////////////////////
  47         // generic type comparison (using meta-programming)
  48         // if Type1 equals Type2,               VALUE is true
  49         // if Type1 differs from Type2, VALUE is false
  50         //////////////////////////////////////////////////////////////////////////////
  51
  52         template <class Type1, class Type2>
  53         struct TYPECMP
  54         {
  55                 typedef False Type;
  56                 enum { VALUE = false };
  57         };
  58
  59         template <class Type1>
  60         struct TYPECMP<Type1, Type1>
  61         {
  62                 typedef True Type;
  63                 enum { VALUE = true };
  64         };
  65
  66         //////////////////////////////////////////////////////////////////////////////
  67         // generic "switch" (using meta-programming)
  68         //////////////////////////////////////////////////////////////////////////////
  69
  70         const int DEFAULT = ~(~0u >> 1); // initialize with the smallest int
  71
  72         struct NilCase {};
  73
  74         template <int tag_,class Type_,class Next_ = NilCase>
  75         struct CASE
  76         {
  77                 enum { tag = tag_ };
  78                 typedef Type_ Type;
  79                 typedef Next_ Next;
  80         };
  81
  82         template <int tag,class Case>
  83         class SWITCH
  84         {
  85                 typedef typename Case::Next NextCase;
  86                 enum
  87                 {
  88                         caseTag = Case::tag,
  89                         found   = (caseTag == tag || caseTag == DEFAULT)
  90                 };
  91         public:
  92                 typedef typename
  93                         IF<
  94                                 found,
  95                                 typename Case::Type,
  96                                 typename SWITCH<tag,NextCase>::Type
  97                         >::Type Type;
  98         };
  99
 100         template <int tag>
 101         class SWITCH<tag,NilCase>
 102         {
 103         public:
 104                 typedef NilCase Type;
 105         };
 106
 107
 108         //////////////////////////////////////////////////////////////////////////////
 109         // generic loops (using meta-programming)
 110         // corresponds to for(i=1; i<=I; ++i) ...
 111         //////////////////////////////////////////////////////////////////////////////
 112
 113         // example of a loop Worker class
 114         struct WorkerNothing
 115         {
 116                 template <typename Arg>
 117                 static inline void body(Arg &arg, int I) {}
 118         };
 119
 120         template <typename Worker, int I>
 121         class LOOP {
 122         public:
 123                 template <typename Arg>
 124                 static inline void run(Arg &arg) {
 125                         LOOP<Worker, I - 1>::run(arg);
 126                         Worker::body(arg, I);
 127                 }
 128         };
 129
 130         template <typename Worker>
 131         class LOOP<Worker, 0> {
 132         public:
 133                 // end of loop
 134                 template <typename Arg>
 135                 static inline void run(Arg &) {}
 136         };
 137
 138         //////////////////////////////////////////////////////////////////////////////
 139         // generic reverse loops (using meta-programming)
 140         // corresponds to for(i=I; i>0; --i) ...
 141         //////////////////////////////////////////////////////////////////////////////
 142
 143         template <typename Worker, int I>
 144         class LOOP_REVERSE {
 145         public:
 146                 template <typename Arg>
 147                 static inline void run(Arg &arg) {
 148                         Worker::body(arg, I);
 149                         LOOP_REVERSE<Worker, I - 1>::run(arg);
 150                 }
 151         };
 152
 153         template <typename Worker>
 154         class LOOP_REVERSE<Worker, 0> {
 155         public:
 156                 // end of loop
 157                 template <typename Arg>
 158                 static inline void run(Arg &) {}
 159         };
 160
 161         //////////////////////////////////////////////////////////////////////////////
 162         // logarithmus dualis (using meta-programming)
 163         //////////////////////////////////////////////////////////////////////////////
 164
 165         template < __int64 numerus >
 166         struct Log2 {
 167                 enum { VALUE = Log2<(numerus + 1) / 2>::VALUE + 1 };            // ceil(log_2(n))
 168         };
 169
 170         template < __int64 numerus >
 171         struct Log2Floor {
 172                 enum { VALUE = Log2Floor<numerus / 2>::VALUE + 1 };             // floor(log_2(n))
 173         };
 174
 175         template <> struct Log2<1> { enum { VALUE = 0 }; };
 176         template <> struct Log2<0> { enum { VALUE = 0 }; };
 177         template <> struct Log2Floor<1> { enum { VALUE = 0 }; };
 178         template <> struct Log2Floor<0> { enum { VALUE = 0 }; };
 179
 180
 181         //////////////////////////////////////////////////////////////////////////////
 182         // exponentiation (using meta-programming)
 183         //////////////////////////////////////////////////////////////////////////////
 184
 185         template < __int64 base, __int64 exponent >
 186         struct Power {
 187                 enum {
 188                         VALUE =
 189                                 Power<base, exponent / 2>::VALUE *
 190                                 Power<base, exponent - (exponent / 2)>::VALUE
 191                 };
 192         };
 193
 194         template < __int64 base > struct Power<base, 1> { enum { VALUE = base }; };
 195         template < __int64 base > struct Power<base, 0> { enum { VALUE = 1 }; };
 196
 197
 198         //////////////////////////////////////////////////////////////////////////////
 199         // memset with fill size (using meta-programming)
 200         //////////////////////////////////////////////////////////////////////////////
 201
 202         using ::memset;
 203
 204         template <unsigned SIZE, bool direct>
 205         struct MemsetWorker {
 206                 finline static void run(unsigned char* ptr, unsigned char c) { memset(ptr, c, SIZE); }
 207         };
 208
 209         template <unsigned  SIZE>
 210         struct MemsetWorker<SIZE, true> {
 211                 finline static void run(unsigned char* ptr, unsigned char c) {
 212                         *((unsigned*)ptr) = ((unsigned)c << 24) + ((unsigned)c << 16) + ((unsigned)c << 8) + (unsigned)c;
 213                         MemsetWorker<SIZE - 4, true>::run(ptr + 4, c);
 214                 }
 215         };
 216
 217         template <>
 218         struct MemsetWorker<0, true> {
 219                 finline static void run(unsigned char*, unsigned char) {}
 220         };
 221
 222         template <>
 223         struct MemsetWorker<1, true> {
 224                 finline static void run(unsigned char* ptr, unsigned char c) { *ptr = c; }
 225         };
 226
 227         template <>
 228         struct MemsetWorker<2, true> {
 229                 finline static void run(unsigned char* ptr, unsigned char c) { *(unsigned short *)ptr = ((unsigned short)c << 8) + (unsigned short)c; }
 230         };
 231
 232         template <>
 233         struct MemsetWorker<3, true> {
 234                 finline static void run(unsigned char* ptr, unsigned char c) {
 235                         MemsetWorker<2, true>::run(ptr, c);
 236                         MemsetWorker<1, true>::run(ptr + 2, c);
 237                 }
 238         };
 239
 240         template <unsigned SIZE>
 241         finline void memset(void* ptr, unsigned char c) {
 242                 MemsetWorker<SIZE, SIZE <= 32>::run((unsigned char*)ptr, c);
 243         }
 244
 245
 246         //////////////////////////////////////////////////////////////////////////////
 247         // memset with fill value (using meta-programming)
 248         //////////////////////////////////////////////////////////////////////////////
 249
 250         template <unsigned SIZE, bool direct, unsigned char c>
 251         struct MemsetConstValueWorker {
 252                 finline static void run(unsigned char* ptr) { memset(ptr, c, SIZE); }
 253         };
 254
 255         template <unsigned  SIZE, unsigned char c>
 256         struct MemsetConstValueWorker<SIZE, true, c> {
 257                 finline static void run(unsigned char* ptr) {
 258                         *((unsigned*)ptr) = ((unsigned)c << 24) + ((unsigned)c << 16) + ((unsigned)c << 8) + (unsigned)c;
 259                         MemsetConstValueWorker<SIZE - 4, true, c>::run(ptr + 4);
 260                 }
 261         };
 262
 263         template <unsigned char c>
 264         struct MemsetConstValueWorker<0, true, c> {
 265                 finline static void run(unsigned char* ptr) {}
 266         };
 267
 268         template <unsigned char c>
 269         struct MemsetConstValueWorker<1, true, c> {
 270                 finline static void run(unsigned char* ptr) { *ptr = c; }
 271         };
 272
 273         template <unsigned char c>
 274         struct MemsetConstValueWorker<2, true, c> {
 275                 finline static void run(unsigned char* ptr) { *(unsigned short *)ptr = ((unsigned short)c << 8) + (unsigned short)c; }
 276         };
 277
 278         template <unsigned char c>
 279         struct MemsetConstValueWorker<3, true, c> {
 280                 finline static void run(unsigned char* ptr) {
 281                         MemsetConstValueWorker<2, true, c>::run(ptr);
 282                         MemsetConstValueWorker<1, true, c>::run(ptr + 2);
 283                 }
 284         };
 285
 286         template <unsigned SIZE, unsigned char c>
 287         finline void memset(void* ptr) {
 288                 MemsetConstValueWorker<SIZE, SIZE <= 32, c>::run((unsigned char*)ptr);
 289         }
 290
 291 }
 292
 293 #endif