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.

First off, I will try to explain the problem and then I will show you the code I have come up with so far.

I've got a list of properties. Each property has a tag of type int and a value of one of the following types: (bool, string, int, long). some sample properties:

tag: 1, value: "some string"
tag: 14, value: true
tag: 20, value: 123

There is also a list of rules. Each rule is like a property, plus one of the following operators: (<, >, <=, >=, ==, !=, startsWith). The startsWith operator is used to check whether one string starts with another one.

Some sample rules:

tag: 1, value: "hello", operator: ==
tag: 14, value: true, operator: ==

Each list of rules is called a Criteria and is used to validate a list of properties. A criteria validates a list of properties if only all the rules of the criteria are met. For example, the two rules above make up a criteria. This criteria does not validate the aforementioned list of properties because the 1st rule forces the value of tag (1) to be equal (==) to "hello" which is not.

The following criteria:

tag: 1, value: "some string", operator: ==
tag: 20, value: 100, operator: >
tag: 20, value: 120, operator: <

does not validate the above properties too, because although the first two rules are met, the last rule, which forces the value of tag (20) to be less than 120 is not true. Therefore the whole criteria does not validate the properties.
And here is a criteria that validates to true:

tag: 1, value: "some", operator: startsWith
tag: 14, value: false, operator: !=
tag: 20, value: 123, operator: >=
tag: 20, value: 100, operator: >

So the final code will look like something like this:

Param* properties = new Param[MAX_PARAMS];

properties[1] = Param("something");     // tag 1 => value: "something"
properties[2] = Param(12);              // tag 2 => value: 12
properties[3] = Param(20);              // tag 3 => value: 20
properties[4] = Param(string("bye"));   // tag 4 => value: "bye"

multimap<int, Rule> rules;

rules.insert(RulePair(1, Rule("some", SW)));    // the value of tag 1 should start with "some"
rules.insert(RulePair(3, Rule(20, LTE)));       // the value of tag 3 should be <= 20
rules.insert(RulePair(3, Rule(10, SW)));        // the value of tag 3 should be start with 10 (which is a meaningless rule)
rules.insert(RulePair(2, Rule(10, GT)));        // the value of tag 2 should be > 10
rules.insert(RulePair(4, Rule("bye1", EQ)));    // the value of tag 4 should be equal to "bye1"

if(CheckRules(rules, properties))
{
    cout << "everything is fine!" << endl;
}

And this is the whole code that I have come up with. I have used boost::variant to be able to store and compare different types in a single map. In the following code I have supposed I only need properties of type either string or int, but new types can be easily added. Any advice on improving the readability, performance or efficiency of this code is appreciated!

#include <map>
#include "boost/variant/variant.hpp"
#include "boost/variant/apply_visitor.hpp"

#define MAX_PARAMS 1000

using namespace std;
using namespace boost;

typedef variant<string, int> MyVariant;

struct IsEqual
{
    MyVariant mValue;
    bool operator()( MyVariant &other ) const
    {
        return mValue == other;
    }
    IsEqual( MyVariant const& value ):mValue(value) {}
};

struct IsLessThan
{
    MyVariant mValue;
    bool operator()( MyVariant &other ) const
    {
        return other < mValue;
    }
    IsLessThan( MyVariant const& value ):mValue(value) {}
};

struct IsLessThanEqual
{
    MyVariant mValue;
    bool operator()( MyVariant &other ) const
    {
        return other < mValue || other == mValue;
    }
    IsLessThanEqual( MyVariant const& value ):mValue(value) {}
};

struct IsGreaterThan
{
    MyVariant mValue;
    bool operator()( MyVariant &other ) const
    {
        return !(other < mValue) && !(other == mValue);
    }
    IsGreaterThan( MyVariant const& value ):mValue(value) {}
};

struct IsGreaterThanEqual
{
    MyVariant mValue;
    bool operator()( MyVariant &other ) const
    {
        return !(other < mValue);
    }
    IsGreaterThanEqual( MyVariant const& value ):mValue(value) {}
};

class StartsWith
    : public boost::static_visitor<bool>
{
public:
    string mPrefix;
    bool operator()(string &other) const
    {
        return other.compare(0, mPrefix.length(), mPrefix) == 0;
    }
    template<typename U>
    bool operator()(U &other)const
    {
        return false;
    }
    StartsWith(string const& prefix):mPrefix(prefix){}
};

enum Operator
{
    EQ,     // ==
    NEQ,    // !=
    GT,     // >
    GTE,    // >=
    LT,     // <
    LTE,    // <=
    SW,     // Starts With
};

string GetOperatorString(Operator op)
{
    switch (op)
    {
        case EQ:
            return "=";
        case NEQ:
            return "!=";
        case GT:
            return ">";
        case GTE:
            return ">=";
        case LT:
            return "<";
        case LTE:
            return "<=";
        case SW:
            return "should start with";
    }
    return "";
}

class Rule : public boost::static_visitor<bool>
{
public:
    MyVariant v;
    string mPrefix;
    Operator mOperator;

    bool operator()(MyVariant &other) const
    {
        if (mOperator == EQ)
        {
            return IsEqual(v)(other);
        }
        else if (mOperator == NEQ)
        {
            return !IsEqual(v)(other);
        }
        else if (mOperator == LT)
        {
            return IsLessThan(v)(other);
        }
        else if (mOperator == LTE)
        {
            return IsLessThanEqual(v)(other);
        }
        else if (mOperator == GT)
        {
            return IsGreaterThan(v)(other);
        }
        else if (mOperator == GTE)
        {
            return IsGreaterThanEqual(v)(other);
        }
        else if (mOperator == SW)
        {
            return apply_visitor(StartsWith(mPrefix), other);
        }
    }
    Rule(MyVariant &v_, Operator op):v(v_),mOperator(op){}
    Rule(string &prefix, Operator op):v(prefix), mPrefix(prefix),mOperator(op){}
    Rule(const char* prefix, Operator op):v(prefix), mPrefix(prefix),mOperator(op){}
    Rule(int _v, Operator op):v(_v), mOperator(op){}
    Rule(){}
};

typedef multimap<int, Rule>::iterator RulesItr;

class Param
{
public:
    Param():mAvailable(false){}
    Param(MyVariant v):mAvailable(true), mValue(v){}
    bool IsAvailable(){return mAvailable;}
    MyVariant GetValue(){return mValue;}
private:
    bool mAvailable;
    MyVariant mValue;
};

bool CheckRules(multimap<int, Rule> rules, Param* properties)
{
    if (rules.empty()) return true;

    RulesItr nextRule = rules.begin();
    int nextPropTag = 0;
    Param* property;
    while (nextRule != rules.end())
    {
        nextPropTag = nextRule->first;
        if (nextPropTag >= MAX_PARAMS) return false;
        property = &properties[nextPropTag];
        if (!property->IsAvailable()) return false;
        MyVariant propertyValue = property->GetValue();
        while (nextRule != rules.end() && nextRule->first == nextPropTag)
        {
            Rule &tester = nextRule++->second; // read and go forward
            cout << "rule: " << propertyValue << " " << GetOperatorString(tester.mOperator) << " " << tester.v;
            if (!tester(propertyValue))
            {
                cout << ": Failed!" << endl;
                return false;
            }
            cout << ": OK!" << endl;
        }
    } // while
    return true;
}


typedef pair<int, Rule> RulePair;

int main(int argc, char **argv) 
{
    Param* properties = new Param[MAX_PARAMS];

    properties[1] = Param("something"); // tag 1 => value: "something"
    properties[2] = Param(12); // tag 2 => value: 12
    properties[3] = Param(20); // tag 3 => value: 20
    properties[4] = Param(string("bye")); // tag 4 => value: "bye"

    multimap<int, Rule> rules;

    rules.insert(RulePair(1, Rule("some", SW))); // the value of tag 1 should start with "some"
    rules.insert(RulePair(3, Rule(20, LTE))); // the value of tag 3 should be <= 20
    rules.insert(RulePair(3, Rule(10, SW))); // the value of tag 3 should be start with 10 (which is a meaningless rule)
    rules.insert(RulePair(2, Rule(10, GT))); // the value of tag 2 should be > 10
    rules.insert(RulePair(4, Rule("bye1", EQ))); // the value of tag 4 should be equal to "bye1"

    if (CheckRules(rules, properties))
    {
        cout << "everything is fine!" << endl;
    }
    else
    {
        cout << "rule mismatch!" << endl;
    }

    return 0;
}
share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

I would get rid of the if-else statement in operator() of Rule, and replace it with a stored apply_visitor functor, or move the apply_vistor from operator() of Rule into StartsWith and make all of your checkers have the same signature.

Suppose we go with moving apply_visitor into StartsWith.

Then Rule stores a std::function< bool( MyVariant const& other ) > check;, which you produce once at Rule construction (possibly through a big if-else block, but you only run that block once). Then operator() on Rule just calls that check on the input parameter.

If I was to go further, I'd work on rule-factories. A rule-factory is a function that takes a MyVariant and produces a std::function< bool( MyVariant const& other ) >. Then register a rule factory for each enum entry. And now your Rule class itself goes away -- a Rule is just any std::function that takes a MyVariant and returns true or false.

The end syntax looks like:

typedef std::function< bool(MyVariant const&) > Rule;
typedef std::function< Rule(MyVariant) > RuleFactory;

class MetaFactory
{
public:
  std::map<Operator, RuleFactory> m_factories;
  MetaFactory()
  {
    m_factories[EQ]  = [](MyVariant left){return [left](MyVariant right){return left == right;};};
    m_factories[NEQ] = [](MyVariant left){return [left](MyVariant right){return left != right;};};
    m_factories[GT]  = [](MyVariant left){return [left](MyVariant right){return left>right;};};
    m_factories[GTE] = [](MyVariant left){return [left](MyVariant right){return left>=right;};};
    m_factories[LT]  = [](MyVariant left){return [left](MyVariant right){return left<right;};};
    m_factories[LTE] = [](MyVariant left){return [left](MyVariant right){return left<=right;};};
    m_factories[LTE] = [](MyVariant left){return [left](MyVariant right){return apply_visitor(StartsWith(left), right);};};
  }
  static std::function<bool(MyVariant const&)> AlwaysFalseFactory(MyVariant var)
  {
    return [](MyVariant const&){return false;};
  }
  RuleFactory GetFactory( Operator op )
  {
    auto it = m_factories.find(op);
    Assert(it != m_factories.end());
    if (it == m_factories.end())
      return RuleFactory::AlwaysFalseFactory;
    return *it;
  }
};

typedef std::vector<std::pair<int,MyVariant>> Params;

bool CheckRules(std::multimap<int,Rule> const& rules, Params const& params)
{
  for (auto it = params.begin(); it != params.end(); ++it)
  {
    auto rules = rules.equal_range( it->first );
    for (auto rule = rules.first; rule != rules.second; ++rule)
    {
      if(!(*rule)(it->second))
        return false;
    }
  }
  return true;
}

int main()
{
  Params params;
  params.push_back( std::make_pair(1, "something") );
  params.push_back( std::make_pair(2, 12 ) );
  params.push_back( std::make_pair(3, 20 ) );
  params.push_back( std::make_pair(4, "bye" ) );

  MetaFactory meta;
  std::multimap<int, Rule> rules;
  rules.insert( std::make_pair( 1, meta.GetFactory(SW)("some") ) );
  rules.insert( std::make_pair( 3, meta.GetFactory(LTE)(20) ) );
  rules.insert( std::make_pair( 3, meta.GetFactory(SW)(10) ) );
  rules.insert( std::make_pair( 2, meta.GetFactory(GT)(10) ) );
  rules.insert( std::make_pair( 4, meta.GetFactory(EQ)("bye1") ) );

  if (CheckRules( rules, params ) )
  {
    cout << "everything is fine!\n";
  }
  else
  {
    cout << "rule failed!\n";
  }
}

now, the above doesn't have diagnostics in it. But I hope you get the idea -- don't use a class when a function will do.

I might make a Rule a pair of tests and error message std::function<std::string(MyVariant const&)s even, with the error message optional. This would give you diagnostics as well. Or the return value could be a pair of bool,std::string, where a true bool means "passed with a possible warning", and false means "failed with a descriptive error".

But you might not want to go this far. :)

...

If you lack C++11, this is a patch on the above:

template<typename Test>
struct RuleInstance
{
    Test test;
    MyVariant left;
    RuleInstance( MyVariant v, Test t ):test(t),left(v) {}
    bool operator()(MyVariant const& right) const
    {
        return test(left, right);
    }
};

template<typename Test>
struct FactoryInstance
{
    Test test;
    FactoryInstance(Test t):test(t) {}
    Rule operator()(MyVariant var) const
    {
        return RuleInstance<Test>(var, test);
    };
};

template<typename Test>
FactoryInstance<Test> make_factory( Test t ) { return t; };

// replace m_factories[EQ]  = [](MyVariant left){return [left](MyVariant right){return left == right;};}; with:
    // make this somewhere (a binary test function):
    bool LessMyVariant( MyVariant const& left, MyVariant const& right ) { return left < right; }

    // create the factory of rules like this:
    m_factories[EQ] = make_factory( LessMyVariant );

but the as you can see, this gets rid of lots of brevity.

On the other hand, this continues to be data-driven: having uniform code behavior, controlled by data, is often a boon to debugging. You can validate data easier than you can validate code!

Less effort was put into optimizing the C++03 version than the C++11 version, but the hit may be minimal.

share|improve this answer
    
Thank you! I will give your solution a try. The only point that you probably missed is that boost::variant only supports the == and < operators. –  Meysam Nov 19 '12 at 6:31
    
I think you have used lambda expressions in MetaFactory. Could you replace them with something else since I am afraid I may not be able to use C++0x features. (maybe if you could replace them with the equivalent boost syntax) –  Meysam Nov 19 '12 at 6:37
    
I am trying to get the C++11 version compiled. Here are some points: StartsWith's constructor accepts a string as its argument, not a variant. Another point is that I want to store all parameters in a map, since comparing two sorted lists is faster, but you have used vector for storing params which makes the CheckRules less efficient. I upvoted your answer for many great hints it bears, but I am a little reluctant to accept your answer because your code cannot be compiled. I will accept it as soon as I can take some time to fix and compile it or as soon as you fix it yourself. –  Meysam Nov 19 '12 at 7:37
    
About storing the params, I have used an array, which is still sorted like a map, given that the key to access each param is its index. –  Meysam Nov 19 '12 at 7:45
    
Please correct the return value of make_factory. –  Meysam Dec 19 '12 at 12:49
add comment

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.