Pages

Test hello rapidxml

This include-only C++ library is a bit outdated, still it is commonly used when the job be done fast and requirements are not too sophisticated. You can get the source code from sourceforge were you could find also a slim technical manual.

There are at least a couple of rapidxml characteristics you should be aware before start working with it.

Rapidxml parsing is destructive. The xml_document::parse() method gets in input a non-constant C-string of characters, that it uses as an its own internal buffer. If you want to keep your XML as it is, you'd better pass in a copy of it.

Preconditions are usually checked with assertions. Exceptions are thrown from the xml_document::parse() method only. Be careful in testing what you are passing to an asserting function (for instance, xml_node::last_node() requires the node to have at least a child (it asserts its first_node is not NULL), and try/catching the parse call.

I have written a test case (using the Google Test framework) that shows how to parse a simple XML and to read the information in it. Notice that I just read a document, without performing any editing on it, this keeps the example simple enough.
#include "rapidxml/rapidxml.hpp"
#include <gtest/gtest.h>

TEST(RapidXml, simple)
{
  char buffer[] = "<root><first>one</first><second>two</second><third>whatever</third></root>"; // 1

  rapidxml::xml_document<char> doc; // 2
  ASSERT_NO_THROW(doc.parse<0>(buffer)); // 3

  rapidxml::xml_node<char>* root = doc.first_node(); // 4
  ASSERT_TRUE(root);
  ASSERT_STREQ("root", root->name()); // 5

  bool fields[4] {}; // 6
  for(rapidxml::xml_node<char>* node = root->first_node(); node != NULL; node = node->next_sibling()) // 7
  {
    if(strcmp(node->name(), "first") == 0) // 8
    {
      ASSERT_STREQ("one", node->value());
      fields[0] = true;
    }
    else if(strcmp(node->name(), "second") == 0)
    {
      ASSERT_STREQ("two", node->value());
      fields[1] = true;
    }
    else if(strcmp(node->name(), "third") == 0) // 9
    {
      fields[2] = true;
    }
    else // 10
    {
      fields[3] = true; // unexpected!
      std::cout << "Unexpected node: " << node->name() << std::endl;
    }
  }

  EXPECT_TRUE(fields[0]); // 11
  EXPECT_TRUE(fields[1]);
  EXPECT_TRUE(fields[2]);
  EXPECT_FALSE(fields[3]);
}
1. Remember that rapidxml is going to change this C-string (NULL-terminated array of characters) for its own purposes.
2. The xml_document template class has a template parameter that defaults to char. If you want to save some typing you can rewrite this line without specifying the parameter, and using the char default:
rapidxml::xml_document<> doc
3. xml_document::parse() expects an int as template parameter, pass zero to get the default behavior. In your code you should try/catch this call for rapidxml::parse_error exception (it extends the std::exception). Here I assert that it should not throw.
4. xml_document IS-A xml_node, so I call on doc the xml_node::first_node() method to get the first document child. If doc has no child, first_node() returns a NULL pointer, otherwise we have a pointer to that node.
5. I expect the root to be there, so I assert that it is not zero (AKA false), then I get its name and I assert it is as expected. xml_node IS-A xml_base, where we can see that the name() method never returns NULL, if the node has no name, an empty C-string is returned instead.
6. Root has three children. I want to ensure I see all of them and nothing more. This bunch of booleans keeps track of them. They are all initialized to false (through the handy C++ empty list initializer) and then, in the following loop, when I see one of them I set the relative flag to true. There are four booleans, and not three, because I want to flag also the case of an unexpected child.
7. The for-loop is initialized getting the first root child, then we get the next sibling, until we reach the end of the family (a NULL is returned). We should pay attention using xml_node::next_sibling(), since it asserts when the current node has no parent. But here we call next_sibling() on a node that is surely a children of another node.
8. For first and second node, we want to ensure it has a specific value, hence the assertion.
9. The third node could have any value, I just set the flag when I see it.
10. In case an unexpected node is detected, I keep track of this anomaly setting the relative flag.
11. Check if the expectations are confirmed.

Go to the full post

Commuting Engineer CodeEval problem

We have the coordinates of a bunch of places that we want to visit. Being nerds, we are not happy if we don't generate an algorithm to determine our path. But, the nature of the problem is such that we are ready to deal with a loose approximation to a good solution. Frankly speaking, we are aiming to get what could look, at least at first sight, as a not-so-bad solution.

You can get a more detailed description of the problem on the CodeEval blog. There you can even enter your solution that would be used (at least at the time when I am writing this post) as a first screening for some job interview.

You can't use the solution I am proposing here for a few good reason. Firstly, it is not a good idea to use a piece of code written by someone else to represent you. Secondly, I have written and tested my code for C++11 on GCC 4.8, that is a bit too modern stuff for the current CodeEval requirements. And thirdly, come on, you don't want to give away a good chance of having some fun writing your own solution.

As I said, I am not aiming to the best possible solution, and this is not caused by sloppiness, there are good reasons for that. Let's see a couple of them.

NP-hard

If you have some knowledge of theory of computation, you should have recognized the problem as an instance of the well known Traveling Salesman Problem, commonly called just TSP. It is an interesting problem because it can be stated in a few words, it looks very easy indeed, but it comes out to be an NP-hard (Non-deterministic Polynomial-time hard) one. That means, forget about to come out with an elegant solution.

In the real life, what I would do if I had to solve a problem like that, is checking for a library provinding some adequate algorithm. For instance, you could have a look to BGL, the Boost Graph Library.

But here we can't use external libraries, we have to rely just on the standard ones. So, what I'll do, is implementing a greedy algorithm, choosing any time the local best solution. It is easy to show as such a strategy is heavily flawed, but at least it assure us we get a solution that is not the worst one, and it does it in a reasonable time.

Geography

As you should know, Earth is not flat. We usually think to it like a sort of sphere, but also this one is nothing more than a weak approximation. This implies that we shouldn't consider the coordinates of a place as they were on a two-dimensional surface.

Besides, we are going to check the distance as if we could go in a straight line from one point to the other, and this is usually not the case.

Splitting the problem

I have reduced the original problem to something that I can actually solve with a relatively simple piece of code. Now I split it in a few simpler problems, for each of them I could write a function that solve it.

Parsing the input

Our input is a number of strings, each of them like this one:
1 | CodeEval 1355 Market St, SF (37.7768016, -122.4169151)
We are interested in its ordinal number, and in the place longitude and latitude.

I decided to organize my data using STL pair's and a vector, and I gave them names that hopefully help to understand better what going on in the code:
using Position = std::pair<double, double>;
using Location = std::pair<int, Position>;
using Locations = std::vector<Location>;
Given that, what I want is to extract a Location from each input string, that is going to be pushed in a Locations container. This is the declaration of the function I am thinking of:
Location parse(const std::string& input);
This test case (written for Google Test) shows how I expect it to behave:
TEST(CommEng, Parse1)
{
    std::string input("1 | CodeEval 1355 Market St, SF (37.7768016, -122.4169151)");
    Location loc = parse(input);

    EXPECT_EQ(1, loc.first);
    EXPECT_DOUBLE_EQ(37.7768016, loc.second.first);
    EXPECT_DOUBLE_EQ(-122.4169151, loc.second.second);
}
Notice I use the EXPECT_DOUBLE_EQ() gtest macro to check the actual value extracted from the input string. This is to avoid, or at least reducing, rounding problems. What I basically do using this macro is delegating to GoogleTest the job of choosing an appropriate epsilon that determines when the two compared values are considered about equal.

Here is my function implementation:
Location parse(const std::string& input)
{
    int nr = std::stoi(input); // 1

    std::string::size_type bracket = input.find('('); // 2
    if(bracket == std::string::npos)
        return {}; // 3

    std::string::size_type comma = input.find(',', bracket);
    if(comma == std::string::npos)
        return {};

    double lon = std::stod(input.substr(bracket + 1)); // 4
    double lat = std::stod(input.substr(comma + 1));
    return { nr, {lon, lat}}; // 5
}
1. stoi() is the standard C++11 function similar to old atoi() but having as input parameter an STL-string and not a C-string. Here I am extracting the place ordinal number, that is expected to be right at the beginning of the string. Real code should be more robust, and be ready to (probably) throw an exception.
2. Just a minimal error checking, if no open bracket and following comma is found, an empty Location is returned.
3. Maybe is worthy to remember that this C++11 notation means "call the default ctor for the expected object". So, what I am doing here is building an "empty" Location.
4. Extract the input substring from the expected position (again, more error handling required in production code), than convert it to double using the C++11 stod() function.
5. Construct a Location object and return it to the caller.

Approximated distance

Just apply the pythagorean theorem to calculate the distance between to positions. For what I have said above, the result should be considered just an approximation:
double distance(const Position& beg, const Position& end)
{
    return std::sqrt(std::pow(beg.first - end.first, 2) + pow(beg.second - end.second, 2));
}
The closest point

My greedy algorithm needs to identify the closest Location to a specific Position:
Locations::iterator findClosest(Position& beg, Locations& others)
{
    double closest = std::numeric_limits<double>::max(); // 1
    Locations::iterator pos = others.end();
    for(Locations::iterator it = others.begin(); it != others.end(); ++it) // 2
    {
        double current = distance(beg, it->second); // 3
        if(current < closest)
        {
            closest = current;
            pos = it;
        }
    }

    return pos; // 4
}
1. Initially I set as a solution as "nothing sensible", so the closest distance found is set the the biggest double number available, and the found position to invalid - the end() iterator.
2. Loop on all the available other points.
3. Calculate the current distance, if I found a good candidate, mark it as such, and check if there is anything better.
4. Return the iterator to the best solution I found.

Generating a path

The core of my algorithm is a function that gets in input a container of Locations and gives back a vector containing the path, where each step is identified by the Location descriptor.
std::vector<int> getPath(const Locations& input)
{
    if(input.empty()) // 1
        return {};

    Locations locations(input); // 2
    std::vector<int> results;
    Locations::iterator current = locations.begin(); // 3
    do { // 4
        Position curPos = current->second; // 5
        results.push_back(current->first);
        locations.erase(current);

        current = findClosest(curPos, locations); // 6

    } while(!locations.empty());

    return results;
}
1. Trivial case, nothing in input, nothing in output.
2. Create an input local copy, since I am about to modify it.
3. As for requirements, the path should start from the first element in the provided list.
4. Loop until all the input is consumed.
5. Erase the current position from the list of Locations that I haven't visited yet, but before that, push its descriptor in the output vector.
6. Find the next "current" element.

Full C++11 source code, and some more test cases, on github.

Go to the full post

CURLOPT_WRITEFUNCTION and C++

Even though I am developing for C++, I don't use the curlpp wrapper to libcurl, the well known file transfer library, preferring to access its bare C interface. I feel more comfortable in this way, still there are a few low level details that require to be explicitly considered. For instance, the CURLOPT_WRITEFUNCTION option accepts as parameter only addresses to free functions (or static member functions). When we want to use a (non static) member function, we have to be prepared to deal with a certain amount of ugliness.

I'd like Curl to put the data it fetches (for more details, please have a look to the previous post where I talked about the plain Curl setup) in a (non static) member variable of the same class from which curl_easy_perform() is called. Something like that:
class CurledClass
{
  // ...

private:
  std::string data_; // 1

  CURLcode curling(/* ... */)
  {
    CURL* curl = curl_easy_init();

    // ...

    CURLcode code = curl_easy_perform(curl); // 2
    curl_easy_cleanup(curl);

    return code;
  }
};
1. I want to store the answer I get from Curl in this data member.
2. Calling Curl to perform the job.

As I said before, we can't pass a pointer to a non-static member function to CURLOPT_WRITEFUNCTION, but we pass a pointer to a static function, but we can ask Curl to pass an extra parameter to that function. We can let that parameter, CURLOPT_WRITEDATA, to be the pointer to this object, so that our static function could actually call a non-static member function:
CURL* curl = curl_easy_init();

// ...
curl_easy_setopt(curl, CURLOPT_WRITEFUNCTION, &CurledClass::write); // 1
curl_easy_setopt(curl, CURLOPT_WRITEDATA, this); // 2
// ...

data_.clear(); // 3
// ...
curl_easy_perform(curl);
1. I specify the static member function I want to be called.
2. I put in the CURLOPT_WRITEDATA option the pointer to the current CurledClass object
3. It is usually a good idea to cleanup the buffer before using it.

The static function specified as CURLOPT_WRITEFUNCTION now just acts like an adapter to the member function I want to use instead:
class CurledClass
{
  // ...
  static size_t write(void* buf, size_t size, size_t nr, void* self) // 1
  {
    return static_cast<LbsTest*>(self)->mWrite(static_cast<char*>(buf), size, nr); // 2
  }

  size_t mWrite(char* buf, size_t size, size_t nr) // 3
  {
    data_.append(buf, size * nr); // 4
    return size * nr;
  }
};
1. Notice the last parameter, that I called "self". It stores the value we have put to CURLOPT_WRITEDATA.
2. The static function write() simply calls the member function mWrite(). To do that it (unsafely) casts the self parameter to this, and the first parameter to a pointer to char..
3. Here is the member function that does the job of copying the data from the Curl buffer to the local one.
4. Remember that Curl could call many times the CURLOPT_WRITEFUNCTION, and we are expected to splice the passed data to build the actual result. I am using a standard STL string as buffer, so I just append the new data as I get it.

Go to the full post

Assert death and deduction on Osmos

The Code Jam Round 1B 2013 Problem A is nicknamed Osmos. Writing googletest test cases for it, I found a way to call once the ASSERT_DEATH macro. Implementing the function, I have also used the template argument deduction. Hence the fancy name for this post.

We have in input an integer representing the weight of our mote (think of a mote like a greedy little sort-of-living organism), and a bunch of integers representing all the other motes in the neighborhood. We want our mote to survive. To do that, it has to absorb all the smaller motes (growing its weight in the process). We could help it in two ways, adding motes that it could swallow to increase its size, and removing motes that are too big for it. Besides, we are lazy. We want to minimize the number of our adding/removing actions.

Test cases would help to clarify the matter. I am using C++11 by GCC 4.8 on a Linux machine. Test cases are written in the xUnit way, using the gtest framework.
unsigned osmos(unsigned myMote, std::vector<unsigned>& motes); // 1

TEST(TestOsmos, CaseSample1) // 2
{
  const unsigned myMote = 2;
  std::vector<unsigned> motes { 2, 1 };

  ASSERT_EQ(0, osmos(myMote, motes));
}

TEST(TestOsmos, CaseSample2) // 3
{
  const unsigned myMote = 2;
  std::vector<unsigned> motes { 2, 1, 1, 6 };

  ASSERT_EQ(1, osmos(myMote, motes));
}

TEST(TestOsmos, CaseSample3) // 4
{
  const unsigned myMote = 10;
  std::vector<unsigned> motes { 25, 20, 9, 100 };

  ASSERT_EQ(2, osmos(myMote, motes));
}

TEST(TestOsmos, CaseSample4) // 5
{
  const unsigned myMote = 1;
  std::vector<unsigned> motes { 1, 1, 1, 1 };

  ASSERT_EQ(4, osmos(myMote, motes));
}

TEST(TestOsmos, CaseBigger) // 6
{
  const unsigned myMote = 42;
  std::vector<unsigned> motes { 1, 40, 12, 7 };

  ASSERT_EQ(0, osmos(myMote, motes));
}

TEST(TestOsmos, CaseMixed) // 7
{
  const unsigned myMote = 2;
  std::vector<unsigned> motes { 8, 15, 30, 40, 60 };

  ASSERT_EQ(3, osmos(myMote, motes));
}

TEST(TestOsmos, CaseBadMote) // 8
{
  const unsigned myMote = 0;
  std::vector<unsigned> motes { 8, 15, 30, 40, 60 };

  ASSERT_DEATH(osmos(myMote, motes),"Assertion .* failed.");
}
1. My osmos function gets in input my mote weight, and all the other motes ones. It gives back the number of adjustments I had to perform to the environment to help my mote. It is not clearly stated in the problem, but any mote weight shouldn't be less than one, and we can assume it would fit in an int.
2. There are four examples provided with the original problem, I have converted them in test cases. In the first one we expect our mote (sized two) to happily eat its smaller brother (one) so to get bigger enough (three) to eat the other one (sized two). No help is required from us, so the function should return zero.
3. My mote has no problem (even no ethical ones) to eat the tiny twins weighting one each, getting in this way big enough to eat the mote two, but it can't eat its brother six. We need to interfere once, either to remove six from the list, or to add a smaller mote so that our mote could absorb it, growing big enough to complete its job.
4. Eat nine, become nineteen. It is not enough to eat twenty, so I provide a eighteen mote, that would immediately be eaten by my mote that grows to a spectacular thirty seven. Eat twenty, twenty five, becomes eighty three. Again not enough to assimilate one hundred, so I need to help a second time, removing the big fish or adding another small mote to the list.
5. My mote is so small that it can't eat any other mote. I can only remove all the competitors.
6. I added a few more test for cases that jumped to my mind, here is the first one. If my mote is the biggest mote in town, there is no game for the other ones.
7. Similar to CaseSample3.
8. What if the user insert a ethereal mote with no weight? That should never occur, so I think it is right to assert on the mote value. That means that I am so unhappy of such an input that I terminate the program as soon as I spot it. You know as an assertion works, if it fails it terminates the execution outputting a string. The ASSERT_DEATH ensures termination and tests the returned string against the passed regular expression. Here I'm saying that I expect "Assertion (whatever) failed.", with anything instead of "(whatever)", accordingly to the compiler you are using you could get a different result.

There is a tiny nuisance here. On many platform googletest (at least up to version 1.6) issues a warning when calling ASSERT_DEATH, saying that it can't detect the current number of threads. You can easily get rid of this message, at least if you are working on Linux, following a suggestion you can find on stackoverflow.

And here is how I have implemented the function:
unsigned osmos(unsigned myMote, std::vector<unsigned>& motes)
{
  assert(myMote); // 1

  if(myMote == 1) // 2
    return motes.size();

  std::sort(motes.begin(), motes.end()); // 3

  if(myMote > motes.back()) // 4
    return 0;

  unsigned removing = motes.size(); // 5
  unsigned adding = 0; // 6
  for(unsigned i = 0; i < motes.size(); ++i) // 7
  {
    if(myMote <= motes[i]) // 8
    {
      removing = std::min<unsigned>(removing, adding + motes.size() - i); // 9
      while(myMote <= motes[i]) // 10
      {
        myMote += myMote - 1;
        ++adding;
      }
    }
    myMote += motes[i]; // 11
  }

  return std::min(removing, adding); // 12
}
1. It just can't happen that my mote is zero. If I detect it, something completely crazy is happening here, I don't know what to do anymore, and I do not expect the caller, its caller, any grand-caller knowing what to do. I do not have any alternative to terminate here the program execution. If you see it as a bit of an overstating, you would probably throw an exception instead.
2. My mote is so small, it can't ever eat anything. I have only one way of completing the job, removing all the motes from the passed collection. So I return the collection size.
3. Having the motes ordered by size, I could more efficiently determine which one my mote can eat. It costs a O(N log N) time complexity, but it is worthy.
4. Check the right-side mote in the collection (after sorting, the biggest one) against my mote. If my mote is bigger, it would surely eat all of them in a whiff, with no need of any help from my side.
5. Worst case scenario, I would need to remove all the motes to let my mote to win.
6. Best case scenario, I don't have to add anything.
7. Let's loop on all the motes.
8. My mote is not big enough to eat the current guy. We need to check if it is cheaper to add smaller motes or remove it.
9. The motes that I still have to process are the size of the collection minus the current position. In the worst case I should assume I have to remove all of them. Besides, I should remember that I could have already added a few motes to arrive in this position. I am interested in the less expensive solution, so I compare the previous worst case with the current one, and I choose the smallest one.
To make my choice, I use the STL min() template function. Usually I don't need to specify the parameter type, because the compiler is smart enough to deduct it automatically. But this is not the case, so I need to explicitly pass it the type I want to use.
10. Calculate how many motes I have to feed to my mote to make it big enough.
11. In any case my mote eats the current mote, growing up.
12. Let's compare if it is cheaper to remove or add motes, and return it. In this case the call to min() doesn't need any hint to understand that I want to use the unsigned int version.

Full C++ source code on github.

Go to the full post

Skipping missing element with RapidJson

In a previous post we have seen how by default RapidJson checks data coherence with C-style assertion, and how we can change this behavior to let it throw an exception instead.

Sometime throwing an exception is an overkill, and asserting should just be avoided. Let think about the case of accessing an element on the JSON document that is not mandatory. If it is there, fine, we can use it, otherwise we should simply skip it. Nothing exceptional or catastrophic is implied by not being it there.

The official RapidJson User Guide, shows as how to use the FindMember() method to get an element or a nullptr in case it is missing. But this is a way you can go through in RapidJson 0.2, that is not currently available to download. If you are using RapidJson 0.1x, you should think to something different.

In my JSON there is an array element named ds, that could contain a few elements. One of them is named "a", and should be a string.

Here is my assertion/exception-free code for this case:
const rapidjson::Value& ds; // 1

// ...

for(rapidjson::SizeType i = 0; i < ds.Size(); ++i) // 2
{
  if(ds[i]["a"].IsNull() || !ds[i]["a"].IsString()) // 3
  {
    // 4
  }
  else
  {
    std::string a(ds[i]["a"].GetString()); // 5
    // ...
  }
}
1. I'll fetch in the variable ds the content of the JSON "ds" element, ensuring it is an array.
2. Loop on all the ds elements.
3. In RapidJson 0.1x, trying to access a non-existing element we get a reference to a null-value singleton. If this is the case, the IsNull() method returns true. Since I expect my "a" element to be a string, I also call IsString() to ensure that.
4. If the "a" element is not there, or if it is not a string, I could take some alternative action, maybe logging some message, if I think the user should be aware of that.
5. Otherwise it is safe to access the "a" element, get its value as a C-string, and use it.

Go to the full post

Bidimensional array annihilator

We have in input a bidimensional array of integers. We should modify it so that any row and column that has originally at least a single element set to zero would have all of them set to zero.

Conceptually it is an easy problem, its main issue is a technical one, since that working with multidimensional arrays in C/C++ has never been exactly a piece of cake.

The idea is to store in two boolean vectors the status of each row and column, setting to true anyone that needs a reset.

Then using that flags to set to zero the elements that need it.

Firstly, let's see how to implement a solution that won't use any STL container.

The C harder way

All is done through C-arrays and raw pointers.

Here is the prototype of the function I want to define:
void cAnnihilator(int* data, const unsigned nRows, const unsigned nCols);
The problem does not specify the array size, so we need to keep it open in our call. For this reason I am forced to pass to the function just the pointer to the first element.

A couple of test case:
TEST(cAnnihilator, CaseSimple) // 1
{
  const int nRows = 5;
  const int nCols = 3;
  int data[nRows][nCols] = {
    { 1, 2, 3 },
    { 4, 5, 6 },
    { 7, 8, 9 },
    { 10, 11, 0 },
    { 13, 14, 15 }
  };

  cAnnihilator(&data[0][0], nRows, nCols); // 2

  for(int i = 0; i < nRows; ++i)
    ASSERT_EQ(data[i][2], 0);
  for(int i = 0; i < nCols; ++i)
    ASSERT_EQ(data[3][i], 0);
}

TEST(cAnnihilator, CaseNothing) // 3
{
  const int nRows = 2;
  const int nCols = 3;
  int data[2][3] = {
    { 1, 2, 3 },
    { 4, 5, 6 }
  };

  cAnnihilator(&data[0][0], nRows, nCols);

  for(int i = 0; i < nRows; ++i)
    for(int j = 0; j < nCols; ++j)
    ASSERT_NE(data[i][j], 0);
}
1. The simple case creates a 5x3 array with only a zero element, after the call to the annihilator, all the elements in column 2 and row 3 are expected to be set to zero.
2. I pass to the annihilator the pointer to the first element in the array and its dimensions.
3. This "nothing" test case gives in input a 3x2 array with no zero element. No change is expected in output.

Here is how I implemented the function:
void cAnnihilator(int* data, const unsigned nRows, const unsigned nCols)
{
  bool rows[nRows]; // 1
  for(unsigned i = 0; i < nRows; ++i)
    rows[i] = false;
  bool cols[nCols];
  for(unsigned i = 0; i < nCols; ++i)
    cols[i] = false;

  for(unsigned i = 0; i < nRows; ++i)
    for(unsigned j = 0; j < nCols; ++j)
      if(*(data + (i * nCols) + j) == 0) // 2
        rows[i] = cols[j] = true;

  for(unsigned i = 0; i < nRows; ++i)
    for(unsigned j = 0; j < nCols; ++j)
      if(rows[i] || cols[j])
        *(data + (i * nCols) + j) = 0; // 3
}
1. The rows and cols boolean array are initialized to "all false". When I'll find a zero element I'll set the relative row and column flag to true.
2. Convert the current element position in bidimensional array notation to its plain distance from the first array element.
3. Set to zero all the elements in rows and columns that require it.

The C++ way

There are a couple of improvement I'd like to to on the function parameter. Firstly, I'd like to give more work to the compiler, let it the burden of deducing the array's size, instead of requiring the client to pass the number of rows and columns. And secondly, I'd prefer to use a STL container instead the raw C-array.

As a result of these consideration, I wrote this function declaration:
template<size_t N, size_t M>
void annihilator(std::array<std::array<int, N>, M>& data);
Now I am passing to the annihilator a reference to an STL array of arrays. A M-sized array of N N-sized int arrays. N and M are template parameters that are deduced from the passed bidimensional array, so that the user doesn't have to specify them in the call.

The test cases for this version of my function look like this:
TEST(Annihilator, CaseSimple)
{
  std::array<std::array<int, 3>, 5> data {{ // 1
    {{ 1, 2, 3 }},
    {{ 4, 5, 6 }},
    {{ 7, 8, 9 }},
    {{ 10, 11, 12 }},
    {{ 13, 14, 15 }}
  }};

  unsigned row = 3; // 2
  unsigned col = 2;
  data[row][col] = 0;

  annihilator(data); // 3

  for(unsigned i = 0; i < data.size(); ++i) // 4
    ASSERT_EQ(data[i][col], 0);
  for(unsigned i = 0; i < data[3].size(); ++i)
    ASSERT_EQ(data[row][i], 0);
}

TEST(Annihilator, CaseNothing)
{
  std::array<std::array<int, 3>, 2> data {{
    {{ 1, 2, 3 }},
    {{ 4, 5, 6 }}
  }};

  annihilator(data);

  for(unsigned i = 0; i < data.size(); ++i)
    for(unsigned j = 0; j < data[i].size(); ++j)
      ASSERT_NE(data[i][j], 0);
}
1. This bracket surplus is a bit annoying. It is not required by the C++11 standard but the current GCC implementation. Your compiler could understand a single bracket.
2. Set a value to zero.
3. The annihilator call is so much cleaner.
4. Ensure the annihilator works as expected.

And finally, here is my C++11 annihilator implementation:
template<size_t N, size_t M>
void annihilator(std::array<std::array<int, N>, M>& data)
{
  std::array<bool, N> cols {}; // 1
  std::array<bool, M> rows {};

  for(unsigned i = 0; i < M; ++i)
    for(unsigned j = 0; j < N; ++j)
      if(data[i][j] == 0) // 2
        rows[i] = cols[j] = true;

  for(unsigned i = 0; i < M; ++i)
    for(unsigned j = 0; j < N; ++j)
      if(rows[i] || cols[j])
        data[i][j] = 0;
}
1. The initializer list is much more expressive than a for-loop. All the elements in cols and rows are initialized to false.
2. Accessing STL-array elements as if they were C-array one (and they actually are, after all).

The source code is on github.

Go to the full post

Hello libcurl world

Reading a resource on the Internet through http via libcurl is very easy. Here I get the google news feed and I output it to the standard console.

Getting curl

There a number of ways to get the libcurl on your machine, accordingly to your development platform. You would probably want to check the official documentation on curl.haxx.se to get the right solution for you.

In my case, developing on a Ubuntu box for GCC C++, I could rely on the Debian repository to install the curl 4 development package for GnuTLS, simplifying a bit this step:
sudo apt-get install libcurl4-gnutls-dev
After that, I can see a new usr/include/curl directory containing all the .h files I need. There is also a libcurl.so, that I need to link to my C++ project. In my case, I find it in the /usr/lib/x86_64-linux-gnu directory (I have a 64 bit distribution).

Libcurl is written in C-language, and exposes an API in C. There is C++ wrapper, curlpp, that aims to provide a simpler access to them. I am not especially fond of it, what I usually do instead is creating my own thin C++ layer around the C-API. In any case, here I show the bare C access to the library.

Initialization

Before using the curl functionality in the code, we have to initialize the library. And, symmetrically, we should also cleanup when we are done. So, typically, we'll have something like:
#include <curl/curl.h>
#include <iostream>

// ...

CURLcode result = curl_global_init(CURL_GLOBAL_NOTHING); // 1
if(result != CURLE_OK) // 2
{
  std::cout << "Curl initialization failure" << result << std::endl;
  return result;
}

// ...

curl_global_cleanup(); // 3
1. There are a few option we could pass to the curl global initialization routine. Here I am happy with the plain vanilla setup, so I pass a nothing (more than the usual stuff) flag.
2. In case of error, we can't use curl.
3. We are done with curl.

CURL object

Once we have the curl library correctly initialized, we ask to it a CURL handler on which we will perform our request. Again, when we are done with it, we should cleanup.

The usual way to perform a call with curl would follow this pattern:
CURL* curl = curl_easy_init(); // 1
if(!curl)
  return CURLE_FAILED_INIT; // 2

// ...

CURLcode code = curl_easy_perform(curl); // 3
curl_easy_cleanup(curl); // 4

return code; // 5
1. The curl library exposes two interfaces. The classic one, and the easy one. Let's keep it simple.
2. If curl-easy can't provide us a CURL handler, we can't do anything more than returning an error code.
3. After setting up our request, we ask curl-easy to perform it. We get back a status code.
4. We are done with the session, clean it up.
5. The user could be interested in knowing what happened to his job. For instance, if the resource can't be fetched because a timeout occurred, a 28, defined as CURLE_OPERATION_TIMEDOUT in curl.h, is returned.

Setting options on CURL

We tell to libcurl what we want to do setting options on the CURL object we get back from the easy_init function. An example clarifies the matter:
curl_easy_setopt(curl, CURLOPT_URL, url.c_str()); // 1
curl_easy_setopt(curl, CURLOPT_WRITEFUNCTION, &curlWriter); // 2
curl_easy_setopt(curl, CURLOPT_TIMEOUT, timeout); // 3
if(follow)
  curl_easy_setopt(curl, CURLOPT_FOLLOWLOCATION, 1L); // 4
1. The URL I want it to access. I had stored it in a STL string, so I have to extract a C-string from it.
2. The address of a function that it has to use to give my back what it gets calling that URL. Be patient, this callback function is showed below.
3. I am very impatient. I want the call to fail if libcurl is not able to get result in a specific time. Be aware that the timeout is specified in seconds.
4. If the resource I request has changed is URL, libcurl could find just a redirect instruction there. Do we want to follow it or not? Setting this option to one (as long) means that, yes, we want to follow it.

Write function

As promised, here is the callback function I passed to libcurl to let it give me back what it got:
size_t curlWriter(void* buf, size_t size, size_t nmemb) // 1
{
  if(std::cout.write(static_cast<char*>(buf), size * nmemb)) // 2
    return size * nmemb; // 3
  return 0;
}
1. The minimal interface for the callback function used by libcurl expects three parameters, buf is the pointer to the block of memory where it put a chunk of the answer, size is the block size in which that chunk is organized, and nmemb is the number of members we have there.
2. I just get that block of memory, and send it to the standard output console, assuming it is text resource.
3. Here I am saying to libcurl that I have correctly managed all the stuff it passed me, please send me some more - if you have it.

Full source code on github.

Go to the full post

Connect 4 rotate

The Code Jam Round 1A 2010 Problem A named Rotate is humorously based on the Connect 4 board game. We are in the middle of a game, and we could cheat rotating the table (only once and only clockwise). Is that worthy?

Or to better put the question, who is the winner after the rotation?

To make things a bit more interesting, both the board size and the winning sequence length are variable. They should be somewhere in the [3..50] range.

We'll have as input the board size, the winning length, and the current game configuration. And we have to give as output the name of the winner (Blue or Red) or, in case of a tie, tell if this happens because both are winner (Both) or no one (Neither).

The resulting code is not excessively complicated, but it is longish and require some carefulness. Here I present my C++11 solution, with a few of the test cases that helped me driving the development. I put the full source code on github.

Trying to keep my code understandable, I have organized it in a class. Its public interface is quite innocent. Just a constructor and a method that gives the winner name(s):
class Rotator
{
private:
    // ...

public:
    Rotator(unsigned size, unsigned len, const Input& input);
    std::string winner();
};
The first two constructor parameters shouldn't require any explanation, the third one is the representation of the board, before our cheating attempt. "Input" is an alias for the STL string vector.

Given this interface, I can start writing a few test cases.
TEST(Rotate, TestBad)
{
    const unsigned size = 7;
    const unsigned len = 3;
    Input input {
        ".......",
        ".......",
        ".......",
        "...R...",
        "...BB..",
        "..BRB..",
        ".RRBR." // too short!
    };

    ASSERT_THROW(Rotator r(size, len, input), std::logic_error);
}
TestBad was not required by the problem. But what if the input is corrupted? I couldn't feel right if I didn't add I bit of robustness to my solution. I want the Rotator constructor to throw a logic_error standard exception when something goes wrong.
TEST(Rotate, Test1)
{
    const unsigned size = 7;
    const unsigned len = 3;
    Input input {
        ".......",
        ".......",
        ".......",
        "...R...",
        "...BB..",
        "..BRB..",
        ".RRBR.."
    };

    Rotator r(size, len, input);
    ASSERT_EQ(results[Neither], r.winner());
}
After rotation, there are not enough aligned R or B. We are in a no-winner case.

In the second test case both players win:
TEST(Rotate, Test2)
{
    const unsigned size = 6;
    const unsigned len = 4;
    Input input {
        "......",
        "......",
        ".R...R",
        ".R..BB",
        ".R.RBR",
        "RB.BBB"
    };

    Rotator r(size, len, input);
    ASSERT_EQ(results[Both], r.winner());
}
After rotation we'll have 4 blues in the first column (now they are on the last row, and there is a dot splitting the sequence), and also 4 reds, in a diagonal line from the first column down to the fourth one.

Third test case, the red player wins:
TEST(Rotate, Test3)
{
    const unsigned size = 4;
    const unsigned len = 4;
    Input input {
        "R...",
        "BR..",
        "BR..",
        "BR.."
    };

    Rotator r(size, len, input);
    ASSERT_EQ(results[Red], r.winner());
}
After rotating, the gravity will put 4 red checkers in the bottom row.

Here is the constructor:
Rotator::Rotator(unsigned size, unsigned len, const Input& input) : size_(size), len_(len)
{
    if(!consistency(input)) // 1
        throw std::logic_error("Bad input");

    for(unsigned y = 0; y < size_; ++y) // 2
    {
        unsigned iBoard = size_ - 1; // 3
        for(unsigned x = 0; x < size_; ++x) // 4
        {
            unsigned iInput = size_ - 1 - x;
            if(input[y][iInput] != '.') // 5
                board_[y][iBoard--] = input[y][iInput]; // 6
        }
    }
}
1. This private method does some minimal check on the user input. If it fails, an exception is thrown.
2. The input is used to set the internal board. Actually, I do not perform the rotation. There is no added value in doing it, it is enough to simulate a gravity effect that push all the checkers to the right. It is much more simple, and there is no side effect on the solution.
3. "iBoard" is the current "x" position were I should put the checker. Initially is the rightmost one.
4. Notice the double for-loop. I scan the complete board looking for checkers. In case of a huge board with a very sparse distribution, this is not an optimal strategy. But remember that we have just 50 as max size.
5. Dot means no checker, we can happily ignore it.
6. We have a checker, we copy it from the input board to the internal one. After that, I decrease the internal index, so that it is ready for the next checker.

Something is missing in the code we have just seen. What the heck is "board_"? It is the private data member representing the board, a 50x50 bidimensional array that I declared in this way:
namespace
{
const char* results[] { "Neither", "Red", "Blue", "Both" };
enum Results { Neither, Red, Blue, Both };
const unsigned minSize = 3;
const unsigned maxSize = 50;
}

using Board = std::array<std::array<char, maxSize>, maxSize>;
using Input = std::vector<std::string>;

class Rotator
{
private:
    Board board_ {};
    // ...
Instead of using a raw C-array, I preferred the C++11 STL-array, much more friendly. So friendly that I can initialize it to have all '\0' values by the C++11 initializer list notation, as you can see I have done on board_ declaration.

Once the board is set, I simply have to check who is the winner:
std::string Rotator::winner()
{
    for(unsigned row = 0; row < size_ && (!blue_ || !red_); ++row) // 1
    {
        for(unsigned col = 0; col < size_ && (!blue_ || !red_); ++col) // 2
        {
            if((board_[row][col] == 'R' && !red_) || (board_[row][col] == 'B' && !blue_)) // 3
            {
                if(checkRight(row, col)) // 4
                    continue;
                if(checkDown(row, col))
                    continue;
                if(checkRightUp(row, col))
                    continue;
                checkRightDown(row, col);
            }
        }
    }

    return results[blue_*2 + red_]; // 5
}
1. Same remark as for the ctor. A double for-loop is not smart at all, and here it is even worse. The structure of the problem makes all the checkers to group in the lower left corner of the board, it would be easy to start checking from that corner and stop looking when we find an empty space. Still, I've already spent an awful lot of time on this problem, maybe I'll post a code refactor in the near future to show a better solution.
2. Notice that I have already used a tiny improvement. When I find that both players have won (both blue_ and red_ are true) I stop looping.
3. I check if the current position is a winning one only if there is a checker in this position, and if we don't already know that that color is a winner.
4. I check for a winning sequence straight on the right and down, and on the diagonal up and down. As soon I find a winning, I stop looking.
5. Sorry for this very C-like code, but I couldn't help to write it. I'm implicitly converting the booleans blue_ and red_ to integers, 0 is for false, 1 is for true. I weight blue_ with a 2 so that summing their values I get the index of the appropriate C-string to return the caller.

The differences among the four checkXxx() are minimal, I'll show here just one of them. See on github for the other ones.
bool Rotator::checkRight(unsigned row, unsigned col)
{
    if(col + len_ > size_) // 1
        return false;

    for(unsigned k = 1; k < len_; ++k)
        if(board_[row][col] != board_[row][col + k]) // 2
            return false;

    if(board_[row][col] == 'R') // 3
        red_ = true;
    else
        blue_ = true;

    return true;
}
1. I'm checking if the current position is the start of a winning sequence straight to the right. If there is not enough room, there is no need to check anything.
2. As soon as I see a checker of a different color on the right of the first one, I can stop the loop.
3. A winner has been found.

Go to the full post

Parsing files with RapidJson

If you need to parse a JSON stored in a file from a C++ application, you could use the RapidJson header-only library.

In a file, named minimal.json, I have a JSON like this:
{
  "res":"OK",
  "tot":419,
  "nr":20,
  "ds":
  [
    {"a": "one/a","b": "one/b"},
    {"a": "two/a","b": "two/b"}
  ]
}
I want to do a few things this JSON, checking its status (stored in "res", getting the "nr" and "tot" integer fields, and the "ds" array.

As an helper, I have created this class:
#include <rapidjson/document.h>

class RJDoc
{
private:
  rapidjson::Document doc_;

public:
  RJDoc(const std::string& json);

  bool checkStatus();
  int getTotal();
  int getNumber();
  const rapidjson::Value& getDs();
};
As usual, I wrote a number of test cases to drive the code development. Here is one of them:
TEST(TestRJDoc, CaseMinimal)
{
  RJDoc reader("minimal.json"); // 1
  ASSERT_TRUE(reader.checkStatus()); // 2
  ASSERT_EQ(419, reader.getTotal()); // 3
  ASSERT_EQ(20, reader.getNumber());

  const rapidjson::Value& ds = reader.getDs(); // 4
  ASSERT_EQ(2, ds.Size()); // 5

  ASSERT_STREQ("one/a", ds[0U]["a"].GetString()); // 6
  ASSERT_STREQ("two/b", ds[1U]["b"].GetString());
  ASSERT_THROW(ds[3U]["a"].GetString(), std::logic_error); // 7
}
1. I want to be able to instantiate a reader passing the name of the associated file.
2. The status check should pass if the "res" field exists and it is set to "OK".
3. A couple of utility methods to get "tot" and "nr".
4. The access to the "ds" array should be granted by a function that returns it as a RapidJson Value object (a sort of variant).
5. Ensure that the array size is as expected.
6. An element of an object in a JSON array is retrieved using this syntax. Notice that we have to explicitly tell to the compiler that the index is an unsigned value. And remember that the RapidJson Strings are actually plain raw C-strings.
7. I need to manage the case of missing field. For instance here I am trying to access a field of a non-existing element in the array. The default RapidJson behavior is letting an assertion fail. I want instead a standard exception to be thrown, so that I can catch it and perform some sort of fall back operation.

For point (7), we can see in rapidjson.h this piece of code:
///////////////////////////////////////////////////////////////////////////////
// RAPIDJSON_ASSERT

//! Assertion.
/*! By default, rapidjson uses C assert() for assertion.
 User can override it by defining RAPIDJSON_ASSERT(x) macro.
*/
#ifndef RAPIDJSON_ASSERT
#include <cassert>
#define RAPIDJSON_ASSERT(x) assert(x)
#endif // RAPIDJSON_ASSERT
So what I have done is defining the symbol RAPIDJSON_ASSERT before any RapidJson include in my code:
#include <stdexcept>
#define RAPIDJSON_ASSERT(x) if(!(x)) throw std::logic_error("rapidjson exception");
I have defined my class constructor in this way:
RJDoc(const std::string& filename)
{
  std::stringstream ss;
  std::ifstream ifs;
  ifs.open(filename.c_str(), std::ios::binary);
  ss << ifs.rdbuf(); // 1
  ifs.close();

  if(doc_.Parse<0>(ss.str().c_str()).HasParseError()) // 2
    throw std::invalid_argument("json parse error"); // 3
}
1. I read the file stream in a string stream.
2. Then I try to parse the string associated to the stream through the rapidjson::Document defined as private data member.
3. What if the file is missing, the data format is wrong or corrupted? I decided to throw a standard invalid_argument exception (and I wrote a few test cases to document this behavior).

The other methods are even simpler then the constructor:
bool RJDoc::checkStatus()
{
  rapidjson::Value& status = doc["res"];
  if(!status.IsString())
    return false;

  return std::strcmp(doc["res"].GetString(), "OK") == 0; // 1
}

int RJDoc::getTotal()
{
  return doc["tot"].GetInt(); // 2
}

int RJDoc::getNumber()
{
  return doc["nr"].GetInt();
}

const rapidjson::Value& RJDoc::getDs()
{
  rapidjson::Value& value = doc["ds"];
  if(!value.IsArray())
    throw std::logic_error("bad ds"); // 3

  return value;
}
1. When calling a RapidJson GetXXX() method on an element that is not present in the current document, as for my definition of RAPIDJSON_ASSERT, I'd get a std::logic_error exception. In this case I don't want that. This is the reason for carefully checking that "res" is a(n existing) string element before getting its value and comparing it against "OK".
2. No special check for "tot" or "nr", just throw a std::logic_error exception if they are missing.
3. I really want "ds" to be an array, otherwise there is no use in returning its unexpected value. So I'll throw just like no "ds" was available at all.

Go to the full post

Most/least common letters

This is a simple interview question that is often used to break the ice. We have a string, find the most used letters in it. As a variation, we could be interested in which letters appears only once in it. It is not difficult to work on the most general case, but to keep it simple we can assume only lowercase letters are used and that the input string is not an extremely long one.

Here is a linear C++11 solution for both questions. The idea is keeping track of the letters' frequency in an array where each element represents a letter and then scanning it to get the required information. Firstly, I defined a class interface:
class Tracker
{
private:
  std::array<int, 26> frequency_ {};  // 1
public:
  Tracker(const std::string& input, int watermark = std::numeric_limits<int>::max()); // 2

  std::string mostUsed(); // 3
  std::string uniques();
};
1. Element zero keeps track of a's, one of b's up to the twenty-five for 'z's. Notice the default C++11 in-class member initializer, an elegant way to set to zero all the array elements at object constructing time.
2. The constructor expects in input the string we want to analyze, and an optional int that defines when we have to stop counting. By default it is set to the maximum int value, just to avoid an overflow. In this way we could pass in input even huge strings, if we are ready to accept a possible imprecise answer.
3. For getting the most used letters in the input string.
4. Gives all the letters used only once.

A few test cases (written for Google Test, it should be easy to port them to any xUnit framework) that should clarify how the code should behave:
TEST(TestTracker, CaseEmpty) // 1
{
  Tracker tracker("");
  EXPECT_TRUE(tracker.uniques().empty());
  EXPECT_TRUE(tracker.mostUsed().empty());
}

TEST(TestTracker, CaseNormal) // 2
{
  Tracker tracker("something may be in here");
  EXPECT_EQ("abgorsty", tracker.uniques());
  EXPECT_EQ("e", tracker.mostUsed());
}

TEST(TestTracker, CaseWobly4) // 3
{
  Tracker tracker("woblywoblywoblywobly");
  EXPECT_TRUE(tracker.uniques().empty());
  EXPECT_EQ("blowy", tracker.mostUsed());
}

TEST(TestTracker, CaseWatermark2) // 4
{
  Tracker tracker("and something else may be here", 2);
  EXPECT_EQ("bdgilorty", tracker.uniques());
  EXPECT_EQ("aehmns", tracker.mostUsed());
}
1. Empty string in input, neither unique nor most used letters are expected.
2. A random string (but only with lowercase letters, and remember that any other characters - like blanks - are discarded) with a few unique letters and 'e' as the most used one. Notice that the Tracker methods return the requested letters in alphabetical order.
3. A word compose by unique letters repeated four times. No unique letter, all the letter in input are in the most used output.
4. Setting a watermark sort of truncate the check on the most used letters. All the ones having a frequency equal or greater than the watermark are returned.

Here is how I have defined the class methods:
Tracker::Tracker(const std::string& input, int watermark)
{
  for(unsigned i = 0; i < input.size(); ++i)
  {
    char c = input[i];
    if(std::islower(c) && frequency_[c - 'a'] < watermark) // 1
      ++frequency_[c - 'a'];
  }
}

std::string Tracker::uniques() // 2
{
  std::string result;

  for(unsigned i = 0; i < frequency_.size(); ++i)
  {
    if(frequency_[i] == 1)
      result += 'a' + i;
  }

  return result;
}

std::string Tracker::mostUsed() // 3
{
  std::string result;

  int top = 0;

  for(unsigned i = 0; i < frequency_.size(); ++i)
  {
    if(frequency_[i] == 0 || frequency_[i] < top) // 4
      continue;

    if(frequency_[i] > top) // 5
    {
      top = frequency_[i];
      result.clear();
    }

    result += 'a' + i; // 6
  }

  return result;
}
1. The constructor loops on all the characters in the input string. If the current one is a lowercase letter, and if the watermark has not been reached yet, its counting is increased. As said above, the 'a' frequency is stored in the first element of the array, etc.
2. Getting the unique letters is quite simple. It is just a matter of looping on the frequency array, when a 1 is found, we add the associated letter to the list (actually, a string) of the accepted cases. If no unique letter is found, an empty string is returned.
3. A bit more complicated the algorithm for the most used ones. A simpler approach would be performing two for loops. First one to identify the top frequency, second one to push all the letter with such a value back to the result string. Here I have decided to use a more involute algorithm just to have some fun. I do not expect any substantial difference in performance or complexity.
4. If the current letter was not in the string (its frequency is zero) or it is less popular than an already checked one, drop it, and pass to consider the next one.
5. If the current letter has an higher frequency than the previous ones, I keep track of its frequency (in top) and I reset the list of most common letters (the string result).
6. Push the current letter back to the result, to keep the alphabetic order. Notice that this instruction is executed both when we have a new top frequency (in this case the current letter would be the first listed one) and when the frequency is high as previously checked top letter (and in this case it would be the current last one).

Go to the full post

Simple ASIO TCP client/server example

A server sits on a specified port, and when a client connects, it sends a message and terminates. A client connects to the server, reads from the socket the message, and terminates. Nothing fancy, but it could be a good introduction on how to use ASIO synchronously to create TCP/IP connections.

After five years, the code is getting obsolete. I have reviewed it moving to the (currently - March 2018) latest version of ASIO, please follow the link to the new post. Sorry for the trouble.


You could get the full C++ code for this example on Github. If you run the executable with no parameter, you start the server, otherwise the client.

Server

In this trivial implementation, my server accepts just one connection before terminating, but it is pretty easy to make it run forever. It is just a matter of running this block in an indefinite loop, and not just once as I do here:
{
  boost::asio::ip::tcp::socket socket(aios); // 1
  std::cout << "Server ready" << std::endl;
  acceptor.accept(socket); // 2

  std::string message("Hello from ASIO");
  boost::asio::write(socket, boost::asio::buffer(message)); // 3
}
1. Create a new TCP/IP socket on an already existing ASIO I/O service.
2. Wait for a client connection.
3. Write a message on the socket to the client.

At the end of the block the socket is automatically closed by its dtor.

Before that, I have done some preparatory stuff:
boost::asio::io_service aios; // 1
boost::asio::ip::tcp::acceptor acceptor(aios, // 2
  boost::asio::ip::tcp::endpoint(boost::asio::ip::tcp::v4(), HELLO_PORT)); // 3
1. The I/O service is the first thing required.
2. The acceptor is used to accept calls from the clients.
3. We need to pass to the acceptor the endpoint, that specifies the protocol used (here is TCP/IP version 4), and the port used (here defined in a constant that I set to 50013).

Client

The client code is symmetrical. First step is about preparing the job:
boost::asio::io_service aios;

boost::asio::ip::tcp::resolver resolver(aios); // 1
boost::asio::ip::tcp::resolver::iterator endpoint = resolver.resolve(
  boost::asio::ip::tcp::resolver::query(host, HELLO_PORT_STR)); // 2
1. Resolver is the counterpart for acceptor. Calling resolve() on it, we get an iterator pointing to the first endpoint associated to a specific address. We can use that iterator to open a connection through the server on a socket, as we'll see below.
2. Query for a specific host and port (here I specified localhost and 50013, notice that both are c-strings).

Now I am ready to open the connection on a socket. If you are using a recent version of Boost Asio (I am working with 1.54), this is done in a one-liner:
boost::asio::connect(socket, endpoint);
If no connection could be opened on any endpoint, a boost system system_error is thrown.

On older asio versions, there was not such a connect() overload, and you have to implement its behavior by hand, in a piece of code like this:
boost::system::error_code error = boost::asio::error::host_not_found;
boost::asio::ip::tcp::resolver::iterator end; // 1
while(error && endpoint != end)
{
  socket.close();
  socket.connect(*endpoint++, error); // 2
}
if(error)
  throw boost::system::system_error(error); // 3
1. The default ctor for a resolver iterator returns its "end" on, we use it to loop on all the endpoints returned by resolver::resolve().
2. Try to connect to the current endpoint, in case of failure loop until we have another endpoint to check.
3. Can't find any endpoint, throw an exception.

Once we have a socket connected to the server, it's just a matter of getting the message it sends to us:
for(;;)
{
  std::array<char, 4> buf; // 1
  boost::system::error_code error;
  size_t len = socket.read_some(boost::asio::buffer(buf), error); // 2

  if(error == boost::asio::error::eof)
    break; // 3
  else if(error)
    throw boost::system::system_error(error); // 4

  std::cout.write(buf.data(), len);
  std::cout << '|'; // 5
}
std::cout << std::endl;
1. Usually I would use a much bigger buffer.
2. Partial read of the message, limited by the buffer dimension.
3. Detected end of file, stop looping.
4. In case of error throws an exception.
5. I show the junctions in the message due to the local buffer, usually it is rebuilt seamlessly.

I written this post as a review of a piece of code I conceived at beginning 2011, that is still documented in a couple of posts, one dedicated to the server part, the other to the client part. You may want to have a look a it.

The original source is the Boost Asio tutorial. Here is the slightly different version of their client and of the their server.

Go to the full post

Another asynchronous wait on a steady timer

This is a new version of an oldish Boost ASIO example of mine about asynchronously waiting on a timer, keeping advantage of C++11 features. If you are looking for something simpler, there's another post on the same matter but more focused on the bare ASIO functionality. Or you could go straight to the original source, the official tutorial on Boost.

Five years later, I found out that this post requires some adjustments. You could follow the link to its March 2018 version.

The main function of this example is spawning a new thread, that runs a function that does something indefinitely. But before creating the new thread, it would set an asynchronous timer, calling a function on its expiration that would cause the runner to terminate.

It makes sense to encapsulate both function in a single class, like this:
class MyJob
{
private:
    MyJob(const MyJob&) = delete; // 1
    const MyJob& operator=(const MyJob& ) = delete;

    std::mutex mx_; // 2
    bool expired_;
public:
    MyJob() : expired_(false) {}

    void log(const char* message) // 3
    {
        std::unique_lock<std::mutex> lock(mx_);
        std::cout << message << std::endl;
    }

    void timeout() // 4
    {
        expired_ = true;
        log("Timeout!");
    }

    void operator()() // 5
    {
        for(int i = 0; !expired_; ++i)
        {
            std::ostringstream os;
            os << '[' << i << ']';

            log(os.str().c_str());
            std::this_thread::sleep_for(std::chrono::seconds(1));
        }
    }
};
1. I don't want an object of this class to be copyable, we'll see later why. So I remove from this class interface copy constructor and assignment operator, using the C++11 equals-delete marker.
2. There are two threads insisting on a shared resource (the standard output console), a mutex is needed to rule its access.
3. The shared resource is used in this function only. A lock on the member mutex takes care of protecting it.
4. When the timer expires, it is going to call this method.
5. This function contains the job that is going to run in another thread. Nothing fancy, actually. Just a forever loop with some logging and sleeping. The timeout is going to change the loop control variable, so that we can have a way out.

This is the user code for the class described above:
boost::asio::io_service io; // 1
boost::asio::steady_timer timer(io, std::chrono::seconds(3)); // 2

MyJob job; // 3
timer.async_wait([&job](const boost::system::error_code&) {
  job.timeout();
}); // 4

std::thread thread(std::ref(job)); // 5
io.run();
thread.join();
1. An ASIO I/O service is created.
2. I create a steady timer (that is just like an old deadline timer, but uses the C++11 chrono functionality) on the I/O service object.
3. An object that describes the job I want to run in another thread is instantiated.
4. When the timer expires, the passed lambda function is executed. It is an asynchronous call, so it returns immediately the control, that passed to the next instruction (5). The lambda would call the timeout() method on the job object, that has been captured by reference. Having defined the MyJob class as non-copyable, forgetting the ampersand, passing the job by value, results in a compiler error. Here I don't care about the error code parameter, that is set by ASIO to say if the timer has expired correctly or with an error. I just stop the job running. In a real-life usage a check would be expected.
5. Before running the I/O service, I create a thread on our job - again passed by reference, as the std::ref() shows. Again, trying to pass it by value would result in compiler errors.

Full C++ code for this example is on Github.

Go to the full post