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