Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I want to make a C++ object hierarchy of "classifiers", which can be composed together via logical operators into a single classifier that implements the whole logical combination.

This is actually for a particle physics analysis library, but I'll present a much simpler example which just classifies integers. The motivation is that a candidate physics object to be classified might have lots of floating point properties on which basis it could be kept or discarded: e.g. mass, energy, angles, etc. -- I can't possibly create all the possible combinations of function signatures to handle this, and even if I could, there's no way for the compiler to determine e.g. "does the 3rd double mean mass or angle?" So the intention is to make the users' code clearer and less ambiguous, while reducing the number of function signatures in my API and increasing flexibility.

Here's an example of what I would like the resulting usage to look like, for the integer classifier example:

Classifier c = IsOdd() || (IsEven() && LessThan(6));
for (int i = 0; i < 10; ++i) {
    if (c.classify(i)) cout << i << " ";
}
// prints 0 1 2 3 4 5 7 9

This demonstrates several requirements:

  • I want to be able to do more than one logical combination in a single expression
  • The objects are all stack-allocated -- no news are involved to mess up the syntax. new IsOdd() || (new IsEven() ... ) would both be distracting and would introduce problems of memory management for the user.
  • The logical operators should have their usual meanings, precedences, and lazy evaluation behaviour: calling classify on a composite classifier should call the same function on each of the chain of logical combinations, stopping as soon as possible.
  • The concrete classifiers (IsOdd, LessThan, etc.) should be objects with state, e.g. the constructor argument passed to LessThan rather than having to have a different LessThanX class for every integer!
  • The base class should ideally be able to be instantiated rather than have to be handled through (const) references.

I've made several attempts to implement this, but keep hitting problems. Typically these have been polymorphism-related: if each Classifier is to contain other classifier(s), then they need to be held as pointers (references can't be stored) and we're back to memory management issues. I found a way around this using the dynamic_any extension to boost's any:

Infrastructure:

#include <boost/any.hpp>
#include <dynamic_any.hpp>
using boost::any_cast;
using boost::dynamic_any_cast;

#include <string>
#include <vector>
#include <iostream>
#include <cassert>
#include <utility>
using namespace std; // for clarity only, won't go in any public header!


/// Main types

class Classifier {
public:
  virtual bool classify(int a) const = 0;
};


class ClassifierAND : public Classifier {
public:
  bool classify(int a) const {
    return dynamic_any_cast<const Classifier&>(classifiers.first).classify(a)
      && dynamic_any_cast<const Classifier&>(classifiers.second).classify(a);
  }
  pair<boost::dynamic_any, boost::dynamic_any> classifiers;
};

class ClassifierOR : public Classifier {
public:
  bool classify(int a) const {
    return dynamic_any_cast<const Classifier&>(classifiers.first).classify(a)
      || dynamic_any_cast<const Classifier&>(classifiers.second).classify(a);
  }
  pair<boost::dynamic_any, boost::dynamic_any> classifiers;
};


/// Operator overloads

template <typename Classifier1, typename Classifier2>
inline ClassifierAND operator && (const Classifier1& c1, const Classifier2& c2) {
  ClassifierAND rtn;
  rtn.classifiers.first = c1;
  rtn.classifiers.second = c2;
  return rtn;
}

template <typename Classifier1, typename Classifier2>
inline ClassifierOR operator || (const Classifier1& c1, const Classifier2& c2) {
  ClassifierOR rtn;
  rtn.classifiers.first = c1;
  rtn.classifiers.second = c2;
  return rtn;
}

Concrete classifiers:

struct IsEven : public Classifier {
  bool classify(int a) const { return a % 2 == 0; }
};

struct LessThan : public Classifier {
  LessThan(int val) { cutval = val; }
  bool classify(int a) const { return a < this->cutval; }
  int cutval;
};

struct GtrThan : public Classifier {
  GtrThan(int val) { cutval = val; }
  bool classify(int a) const { return a > this->cutval; }
  int cutval;
};

Test program:

void test(const Classifier& c) {
  for (int i = -3; i < 10; ++i) {
    if (c.classify(i)) cout << i << " ";
  }
  cout << "\n";
}


int main() {

  IsEven e;
  GtrThan g4(4);
  GtrThan g2(2);
  LessThan l(-1);

  const Classifier& c1 = e || GtrThan(4);
  test(c1);
  // -2 0 2 4 5 6 7 8 9

  ClassifierAND c2 = e && g2 && g4;
  test(c2);
  test(e && g2 && g4);
  // 6 8 (twice)

  test(e && l);
  // -2

  const Classifier& c4 = IsEven() || LessThan(3);
  test(c4);
  test(IsEven() || LessThan(3));
  // -3 -2 -1 0 1 2 4 6 8 (twice)

}

As seen from the output, this does work... but I think/hope it can still be improved. In particular, the Classifier base class is virtual, which forces me to use const references: fine as an argument signature (cf. test) but a bit confusing for an explicit variable as in the last test and risks "object slicing" errors if used without care.

Additionally the ClassifierAND/OR types are really clunky -- I'd originally tried to put a "next" Classifier member and a logical operation enum in the base class to avoid these pairs, but couldn't make it work nicely. It would be nice to hide these or avoid them entirely so that the compiler doesn't emit warnings about a chain of logically combined classifiers being of a type that the user isn't exposed to.

I'm also not sure if the efficiency can be improved: due to the AND/OR pairs, there could in general be quite a lot of pair nesting.

Any feedback and suggestions for improvements would be very welcome!

share|improve this question
2  
I think you will have better success using templates and duck typeing rather than a polymorphic interface. The C++ standard library uses duck typing to achieve the same affect you are trying to achieve here. –  Loki Astari Oct 24 '12 at 20:57
add comment

1 Answer

I think you will have better success using templates and duck typeing rather than a polymorphic interface. The C++ standard library uses duck typing to achieve the same affect you are trying to achieve here.

This is what I would do:

// A couple of these are already in the standard library have a look.
struct IsEven
{
  bool operator()(int a) const { return a % 2 == 0; }
};

struct LessThan
{
  LessThan(int val): cutval(val)  {}
  bool operator()(int a) const { return a < cutval; }
  int cutval;
};

struct GtrThan
{
  GtrThan(int val): cutval(val) {}
  bool operator()(int a) const { return a > this->cutval; }
  int cutval;
};

template<typename T1, typename T2>
struct AndOp
{
    AndOp(T1 const& t1, T2 const& t2) : t1(t1), t2(t2) {}
    T1 const    t1;
    T2 const    t2;
    bool operator()(int a) const { return t1(a) && t2(a);}
};

template<typename T1, typename T2>
struct OrOp
{
    OrOp(T1 const& t1, T2 const& t2) : t1(t1), t2(t2) {}
    T1 const    t1;
    T2 const    t2;
    bool operator()(int a) const { return t1(a) || t2(a);}
};

template<typename T1, typename T2>
AndOp<T1, T2> make_and_op(T1 const& t1, T2 const& t2)
{
    return AndOp<T1, T2>(t1, t2);
}
template<typename T1, typename T2, typename T3>
AndOp<AndOp<T1, T2>, T3> make_and_op(T1 const& t1, T2 const& t2, T3 const& t3)
{
    return AndOp<AndOp<T1, T2>, T3>(make_and_op(t1, t2), t3));
}

template<typename T1, typename T2>
OrOp<T1, T2> make_or_op(T1 const& t1, T2 const& t2)
{
    return OrOp<T1, T2>(t1, t2);
}

Now we can test with:

template<typename T>
void test(const T& c) {
  for (int i = -3; i < 10; ++i) {
    if (c(i)) cout << i << " ";
  }
  cout << "\n";
}

int main()
{

  test(make_or_op(IsEven(), GtrThan(4)));
  // -2 0 2 4 5 6 7 8 9

  test(make_and_op(IsEven(), GtrThan(2), GtrThan(4)));
  // 6 8

  test(make_and_op(IsEven(), LessThan(-1)));
  // -2

  test(make_or_op(IsEven(), LessThan(3))); 
  // -3 -2 -1 0 1 2 4 6 8
}
share|improve this answer
    
Thanks Loki. Without polymorphism this could get cumbersome, though: you've explicitly made a 3-arg make_and_op to avoid nested calls to the 2-arg version. I really wanted to overload the boolean operators to make this feel natural to the user, not have surprises ("no 3-arg OR?" ;-) "If the AND worked for 2 and 3 args, it must work for 4...", etc.) and not have boilerplate taking up a lot of space. Probably we can combine the two approaches by also inheriting from a base class and defining boolean ops on that... or not? –  andybuckley Oct 26 '12 at 7:54
    
Sorry don't like you overload of the || (and &&) operators. Its the classic lets abuse the operators syndrome to do a clever trick. It works for you because you wrote it. But nobody else will find it intuitive. –  Loki Astari Oct 26 '12 at 8:14
    
I'm confused: the use of those operators is for logical combination of the classifiers according to exactly the normal meanings of those operators... or at least, that's the the intention. How is it unintuitive? IMHO, having to use named functions to express boolean combinations is much more confusing... –  andybuckley Oct 26 '12 at 9:00
    
@andybuckley: Because they are not performing the operation you expect. I expect || (and &&) to return a boolean value using short cut semantics. So in this situation where they do neither of the above; then have to dig into the code to find out exactly what is happening before you can use them. Check out any forum (or google) about "C++ overloading operator abuse". This falls squarely in this category. Its intuitive to you because you wrote it. To everybody else they will need to dig out the source to work out what is happening before they can use it. –  Loki Astari Oct 26 '12 at 14:13
    
@andybuckley: Best practive (and maintainable code) would dictate the use of a named function that describes what is happening. (Yours is a nice trick that everybody learning C++ tries. But ultimately leads to maintenance problems). –  Loki Astari Oct 26 '12 at 14:14
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.