Joined Output and the Fencepost Problem

2006-10-30, , , Comments

If fenceposts are placed 10m apart then how long is a row of 10 fenceposts? Quickly now …

If you answered 100m you got it wrong. Since the gap between two posts is 10m and there are 9 gaps in a row of 10 posts, the correct answer is 90m.

This is an example of the fencepost problem. It comes up all the time in computing. In this post, I tackle the example of using C++ to output a range of items.

C++ Range Output

In Omit Needless Code, Kevlin Henney develops some concise and expressive code to output a collection of strings separated by newlines:

std::vector<std::string> items;
... // populate items
typedef std::ostream_iterator<std::string> out;
std::copy(items.begin(), items.end(), out(std::cout, "\n"));

It’s the "\n" which adds the newlines. We could have used any other string — a simple space " " or a comma followed by a space ", " might be more suitable in some cases.

Unfortunately, though, this code adds a newline after each item in the list, including the last item, which is rarely what we want — just like we didn’t want the gap after the terminal post in the fencepost problem. For whitespace, such as a newline, this may not be too upsetting; by happy coincidence, we may even want an extra newline. Usually, though, the extra gap is a nuisance, as the following example shows.

The Full Monty

#include <iostream>
#include <iterator>
#include <string>
#include <vector>

typedef std::vector<std::string> breakfast;

void
add_full_monty(breakfast & add_to)
{
    static char const * items[] =
    {
        "bacon",
        "eggs",
        "beans",
        "toast",
        "sausage",
        "tomatoes",
        "black-pudding",
    };
    static char const ** const last_item
        = items + sizeof items / sizeof items[0];
    add_to.insert(add_to.end(), items, last_item);
}

void
output_breakfast(breakfast const & items, std::ostream & to)
{
    typedef std::ostream_iterator<breakfast::value_type> out;
    std::copy(items.begin(), items.end(), out(to, " and "));
}

int
main(int argc, char * argv[])
{
    breakfast my_breakfast;
    add_full_monty(my_breakfast);
    std::cout << "For breakfast I had ";
    output_breakfast(my_breakfast, std::cout);
    std::cout << '.' << std::endl;
    return 0;
}

Running this program produces:

For breakfast I had bacon and eggs and beans and toast and sausage and tomatoes and black-pudding and .

which isn’t entirely satisfying. There’s one " and " too many. Before fixing the problem, did you notice the surplus comma after the "black-pudding" and just before the end of the static array initialiser?

    static char const * items[] = {
        ....
        "black-pudding",
    };

This looks rather like another fencepost problem; as if a careless cut-and-paste has resulted in one comma too many. In fact, although the comma doesn’t need to be there, it’s innocuous, since, in a rare moment of generosity, C++ (and C) specifically allow for it. Permitting this extra separator makes life much easier for code-generators which don’t have to worry about treating the final item in a collection differently.

Python Joined-Up Output

Here’s some Python code which does a similar job. Running:

def full_monty():
    return "spam", "spam", "eggs", "spam",

print "For breakfast I had %s." % " and ".join(full_monty())

produces:

For breakfast I had spam and spam and eggs and spam.

The string join method uses the string " and " to fill the gaps between tuple items, which is just what we wanted.

Note here the trailing comma after the final "spam" in the return from the full_monty function. Again, it’s not necessary in this case, but you would need it to return a tuple comprising a single item.

def healthy_breakfast():
    return "muesli",

For consistency, I prefer to include this comma even when it’s not required.

C++ Joined-Up Output

Here’s some C++ code which will do the job of outputting a range of items, separated by a join string, and which doesn’t suffer from the fencepost problem

joined_output.hpp
#if !defined JOINED_OUTPUT_HPP_INCLUDED
#define JOINED_OUTPUT_HPP_INCLUDED

#include <ostream>

template <class Iterator>
void
joined_output(std::ostream & put_to,
              Iterator first,
              Iterator last,
              char const * join_with)
{
    if (first != last)
    {
        Iterator curr = first++;
        while (first != last)
        {
            put_to << *curr << join_with;
            curr = first++;
        }
        put_to << *curr;
    }
}
#endif // defined JOINED_OUTPUT_HPP_INCLUDED

It’s not especially pretty but at least this library code can be tucked away somewhere and used as required rather than replicated everywhere joined-up output is needed. Its use is straightforward, as the following test code demonstrates:

test_joined_output.cpp
#include "joined_output.hpp"
#include <cassert>
#include <list>
#include <sstream>
#include <vector>
#include <iostream>
#include <iterator>

void
test_bidirectional_joined_output()
{
    int const ii[] = { 0, 1, 2, 3, 4, 5 };
    int const * const end_ii = ii + sizeof ii / sizeof *ii;
    std::list<int> const ll(ii, end_ii);
    
    std::stringstream put_to;
    joined_output(put_to, ii, end_ii, " ");
    joined_output(put_to, ll.begin(), ll.end(), " ");
    assert(put_to.str() == "0 1 2 3 4 5" "0 1 2 3 4 5");
    
    put_to.str(std::string());
    joined_output(put_to, ii, end_ii, "");
    joined_output(put_to, ll.begin(), ll.end(), "");
    assert(put_to.str() == "012345" "012345");
    
    put_to.str(std::string());
    joined_output(put_to, ii, ii, " ");
    joined_output(put_to, ll.begin(), ll.begin(), " ");
    joined_output(put_to, ll.end(), ll.end(), " ");
    assert(put_to.str().empty());
    
    put_to.str(std::string());
    joined_output(put_to, ii + 1, ii + 2, " ");
    assert(put_to.str() == "1");
}

void
test_input_joined_output()
{
    std::istringstream input("0 1 2 3 4 5");
    std::ostringstream output;
    joined_output(output,
                  std::istream_iterator<int>(input),
                  std::istream_iterator<int>(),
                  " + ");
    assert(output.str() == "0 + 1 + 2 + 3 + 4 + 5");
}

int
main(int argc, char * argv[])
{
    test_bidirectional_joined_output();
    test_input_joined_output();
    return 0;
}

Specialised C++ Joined-Up Output

If we were dealing with a bi-directional or random access iterator then our implementation of joined_output() could get away without using any local variables:

#include <algorithm>
#include <iterator>
#include <ostream>

template <class BidirectionalIterator>
void
joined_output(std::ostream & put_to,
              BidirectionalIterator first,
              BidirectionalIterator last,
              std::string const & join_with)
{
    if (first != last)
    {
        typedef typename
            std::iterator_traits<BidirectionalIterator>::value_type V;
        std::copy(first, --last,
            std::ostream_iterator<V>(put_to, join_with));
        put_to << *last;
    }
}

This being C++, we probably do fret about such micro-optimisations in library code. So, for completeness, here’s the file joined_output.hpp reworked to show how joined_output() can be specialised according to iterator type. I prefer the earlier and simpler version but I’m posting this version in case I ever need to remember how to do this sort of thing again.

joined_output.hpp
#if !defined JOINED_OUTPUT_HPP_INCLUDED
#define JOINED_OUTPUT_HPP_INCLUDED

#include <algorithm>
#include <cassert>
#include <iterator>
#include <ostream>

template <class Iterator>
void
joined_output(std::ostream & put_to,
              Iterator first,
              Iterator last,
              char const * join_with)
{
    if (first != last)
    {
        joined_output(typename std::iterator_traits<Iterator>::iterator_category(),
                      put_to, first, last, join_with);
    }
}

template <class BidirectionalIterator>
void
joined_output(std::bidirectional_iterator_tag,
              std::ostream & put_to,
              BidirectionalIterator first,
              BidirectionalIterator last,
              char const * join_with)
{
    assert(first != last);
    typedef typename
        std::iterator_traits<BidirectionalIterator>::value_type V;
    std::copy(first, --last,
        std::ostream_iterator<V>(put_to, join_with));
    put_to << *last;
}

template <class InputIterator>
void
joined_output(std::input_iterator_tag,
              std::ostream & put_to,
              InputIterator first,
              InputIterator last,
              char const * join_with)
{
    assert(first != last);
    InputIterator curr = first++;
    while (first != last)
    {
        put_to << *curr << join_with;
        curr = first++;
    }
    put_to << *curr;
}

#endif // defined JOINED_OUTPUT_HPP_INCLUDED