Thursday, September 27, 2012

c++11 Variadic template

Another interesting feature of c++11 is the variadic templates. Basically these allow you to add infinite, heterogeneous parameters to your functions. However their syntax seems to force you to define them recursively. As a result they seem to be usable in 2 main ways.

  1. Map: Apply an repeated operation over the entire list of objects
  2. Reduce(or fold): Take in the list of objects and compound them into something
How very Hadoop. This apparent limited usability makes them a prime candidate for reduction in a forwarding function. Something that simply recurses the list of parameters and forwards them through a normaliser into a Lambda or directly into a templated function that can handle the specific Type. Here is the Normalize and Lambda approach.
#include <iostream>
#include <sstream>
#include <functional>

template <typename R, typename I>
R normalise(I i)
{
  try
    {
      R item;
      std::stringstream s;
      s << i;
      s >> item;
      return item;
    }
  catch(...)
    {}

  return R();
}

template <typename R, typename I>
R reduce(std::function<R (const R&, const R&)> action, I i)
{
  return normalise<R>(i);
}

template <typename R, typename I, typename... II>
R reduce(std::function<R (const R&, const R&)> action, I i, II... ii)
{
  return action(normalise<R>(i), reduce<R>(action, ii...));
}

template <typename R, typename I>
R map(std::function<void (const R&)> action, I i)
{
  action(normalise<R>(i));
}

template <typename R, typename I, typename... II>
void map(std::function<void (const R&)> action, I i, II... ii)
{
  action(normalise<R>(i));
  map<R>(action, ii...);
}

int main()
{ 
  std::function<int (const int&, const int&)> max
    = [](const int& a, const int& b)->int { return a>b ? a : b;  };  

  std::function<float (const float&, const float&)> min
    = [](const float& a, const float& b)->float { return a<b ? a : b;  };  

  std::function<float (const float&, const float&)> sum
    = [](const float& a, const float& b)->float { return a+b;  };  

  std::cout << "Max:" << reduce(max, "452", 3.422, 32, 0x000000ff, "543.485") << "\n";
  std::cout << "Min:" << reduce(min, "452", 3.422, 32, 0x000000ff, "543.485") << "\n";
  std::cout << "Sum:" << reduce(sum, "452", 3.422, 32, 0x000000ff, "543.485") << "\n";

  float res = 0;
  std::function<void (const float&)> accum
    = [&res](const float& a) { res += a;  };  

  map(accum, "452", 3.422, 32, 0x000000ff, "543.485");
  
  std::cout << "\n" << "Accum:" << res << "\n";

  std::stringstream ss;
  std::function<void (const float&)> stream = [&ss](const float& a) { ss << a << ",";  };

  map(stream, "452", 3.422, 32, 0x000000ff, "543.485");
  std::cout << ss.str() << "\n";
}

Tablified Traits

Here is simple c++ trait wrapper that goes around the old standard c++ array of structs lookup table. It handles the forward and reverse lookup of the trait entry via its main key and an attrib and then the access of the various attributes from the resulting row.

There are some caveats to it. The Enum id cant be sparse. and the UNKNOWN entry needs to be second last before the MAX entry marker.

#include <iostream>

template<int LAST, typename R, typename T>
R lookup(T* table, R T::*member, int key) 
{
  if (key < LAST) return table[key].*member;
  return table[LAST].*member;
}

template<int LAST, typename R, typename T>
int locate(T* table, R T::*member, R target) 
{
  int k = 0;
  while (k < LAST)
    {
      if (table[k].*member ==  target)
 return k;
      k++;
    }
  return LAST;
}

template<int LAST, typename T>
int locate(T* table, const char* T::*member, const char* target) 
{
  int k = 0;
  while (k < LAST)
    {
      if (std::string(table[k].*member) == std::string(target))
 return k;
      k++;
    }
  return LAST;
}

class TableTrait
{
public:
  enum Key
    {
      ITEM1,
      ITEM2,
      ITEM3,
      ITEM4,
      ITEM5,
      UNKNOWN, //Must be second last
      MAX      //Must be last
    };    

private:  
  struct TableEntry
  {
    Key         key;
    int         attribA;
    bool        attribB;
    const char* attribC;
  };

  static TableEntry lookup_table[MAX];

  int key_;
public:
  TableTrait(int key) :
    key_(lookup<UNKNOWN>(lookup_table, &TableEntry::key, key))
  {}

  TableTrait(const char* rev_key) :
    key_(locate<UNKNOWN>(lookup_table, &TableEntry::attribC, rev_key))
  {}

  bool        valid()   { return key_ != UNKNOWN; }
  Key         key()     { return static_cast<Key>(key_); }
  int         attribA() { return lookup<UNKNOWN>(lookup_table, &TableEntry::attribA, key_); }
  bool        attribB() { return lookup<UNKNOWN>(lookup_table, &TableEntry::attribB, key_); }
  const char* attribC() { return lookup<UNKNOWN>(lookup_table, &TableEntry::attribC, key_); }  
};

TableTrait::TableEntry TableTrait::lookup_table[TableTrait::MAX] =
{
  { ITEM1,   3, false, "ITEM1"   },
  { ITEM2,   2, true,  "ITEM2"   },
  { ITEM3,   6, false, "ITEM3"   },
  { ITEM4,   5, true,  "ITEM4"   },
  { ITEM5,   8, false, "ITEM5"   },
  { UNKNOWN, 0, false, "UNKNOWN" }
};

int main()
{
  std::cout << "lookup: " << TableTrait(TableTrait::ITEM1).attribC() << "\n";
  std::cout << "lookup: " << TableTrait(TableTrait::ITEM2).attribB() << "\n";
  std::cout << "locate: " << TableTrait("ITEM3"          ).attribA() << "\n";
  std::cout << "locate: " << TableTrait("ITEM2"          ).key()     << "\n";
  std::cout << "locate: " << TableTrait("Blah"           ).attribC() << "\n";
}

Friday, September 21, 2012

C++ Mixins and Curiously Recurring Templates

C++ Curiously Recurring and Mixin's

In large systems it is often desirable to have a policy or rule classes that handle a group of settings for particular instance of a data object. Generally the most common settings are chosen for the base class so that it becomes the "Default" policy. Other Policy's are added by over loading the various part of the Rules class to make new policies such as "DefaultWithA" and "DefaultWithB". But then someone will note the need for a "DefaultWithAandB"

At this point coders either cut and paste. Or try to break the Main rule object into sub-grouping objects "PolicyGroupA" and "PolicyGroupB" and convert the the main Rule into an interface that just aggreatates the tree of sub rules objects. This slowly crags up the rule checking with a series wrapper function calls just to get to the final cluster of rules. Furthermore its often rather difficult to divide these objects in a sane way because they have some form of relationship that caused them to be grouped at the start anyway.

Ruby provides an interesting addition to its language to handle common functionally and code grouping called a mixin. Rubys mixin is just another inheritance trick and once you realize what it is its easy to repeat it in C++. Simply put works out as a near brother of the curiously reoccurring templates. here is how it works;

#include <iostream>

class Default
{
public:
  virtual void ruleA() { std::cout << "default::ruleA\n"; }
  virtual void ruleB() { std::cout << "default::ruleB\n"; }
  virtual void ruleC() { std::cout << "default::ruleC\n"; }
};

class Impl1 : public Default
{
public:
  virtual void ruleC() { std::cout << "Impl1::ruleC\n"; }
};

template <typename T>
class MixinA : public T
{
public:
  virtual void ruleA() { std::cout << "mixin::ruleA\n"; }
};

template <typename T>
class MixinB : public T
{
public:
  virtual void ruleB() { std::cout << "mixin::ruleB\n"; }
};

class Unrelated
{
};

class DefaultWithMixinA : public MixinA<Default >
{
};


class DefaultWithMixinAandB : public MixinB< MixinA< Default > >
{
};

class Impl1WithMixinA : public MixinA<Impl1>
{
};

class UnrelatedWithMixinA : public MixinA<Unrelated>
{
};

int main()
{
  std::cout << "DefaultWithMixinA\n";
  DefaultWithMixinA d;
  d.ruleA();
  d.ruleB();
  d.ruleC();
  
  std::cout << "DefaultWithMixinAandB\n";
  DefaultWithMixinAandB ab;
  ab.ruleA();
  ab.ruleB();
  ab.ruleC();
  
  std::cout << "Impl1WithMixinA\n";
  Impl1WithMixinA i;
  i.ruleA();
  i.ruleB();
  i.ruleC();
  
  std::cout << "UnrelatedWithMixinA\n";
  UnrelatedWithMixinA u;
  u.ruleA();
}

Here is some code so that you can see the difference between this and a real curiously reoccurring template. Pay close attention to how it inherits

#include <iostream>

template <typename T>
struct CuriouslyRecurring
{
public:
  virtual void ruleA()  { std::cout << "CRP::ruleA\n"; }
};

template <typename T>
struct Mixin : public T
{
public:
  virtual void ruleA() { std::cout << "mixin::ruleA\n"; }
};

struct Default
{
public:
  virtual void ruleA() { std::cout << "default::ruleA\n"; }
};

struct DefaultWithMixin : public Mixin< Default >
{

};

struct SelfWithCRT : CuriouslyRecurring< SelfWithCRT >
{
};

// Impossible complier cant tell which ruleA to use when you call it
//struct DefaultWithCRT : public CuriouslyRecurring< DefaultWithCRT >, Default
//{
//};

// Impossible this is a MIXIN cant overload an incomplete class
//struct SelfMixin : public Mixin< SelfMixin >
//{
//};

int main()
{
  SelfWithCRT crt;  
  crt.ruleA();

  DefaultWithMixin mix;  
  mix.ruleA();

  //DefaultWithCRT dcrt;  
  //dcrt.ruleA();
}