The first program is kwic which generates the rotated lines.

Let’s get straight into it …​

kwic is straightforward enough - read a line, create all the rotations, write those back out.

There’s very little to surprise here, I think.

This was a fun little program, made all the easier by std::rotate sitting there in the standard library.

unrotate feels like it should be a doddle, but Kernighan and Plauger’s long-line wrapping requirement sent me off into a couple of mazey passages. Initially, I misunderstood the requirement to only wrap one way - that is if the text in the first half of the output is too long it should wrap around onto the end of the output. I then wrote some rather overwrought code to do that before realising that my code, while correct for what it did, was just doing the wrong thing. The output can wrap both ways - if the second half is too long, it wraps around to start of the output as well. As clearly shown in the little man page for the program.

I tried further tricky schemes, involving all kinds of clever string slicing, offset calculations and so on, wondering how to resolve the problem of text wrapping both ways, when I had my second realisation. Kernighan and Plauger model strings as fixed length buffers. They’re never going to have a string longer than their usual 80 characters, consequently their unfolded lines can only ever wrap at one end. It can’t be both.

My solution to overlength lines was to trim any excess from one or both ends, before unfolding. With that in place, everything else fell out nicely.

The portion of the input string after the fold marker actually appears on the left-hand side of the output, while the portion of the input string before the marker appears on the right-hand side of the output. So, having created a buffer of the appropriate size, we divide the input into those two pieces and copy them into place.

We handle the left hand side of the output first. We actually start at the end of the after fold text (a position known in C++ circles at rbegin()), which we copy into the right-most position in the first half of the output. We then work left, back towards the beginning of the after fold text. If we hit the start of the output buffer as we go, we wrap around to the far end. This, simply and safely, wraps lengthy text without having to do tricky string slicing, or working out leading or trailing padding.

We handle the before fold text in similar fashion, except this time we start at the beginning of that text, placing it at the leftmost position in the second half of the output and working to the right. If we hit the end of the buffer, we just wrap around to the beginning.

That only leaves the vexed question of long lines.

Let’s say we have a folded line that looks like this

and we want to unfold it into a output line only 20 characters long. The output should look like

By chopping out the excess characters from the middle of the input, the copy and wrap processes we’ve just looked at will be fine.

Keep the underlined parts, drop the middle to give

The abrupt cut-off at the end of This falls where the text wraps. This chopping out works when the fold marker is within half the output width of either end. When the fold marker falls somewhere in the middle, we have to be a bit cleverer.

should give an output of

We still want either end of the input, but we will need to insert a new fold marker to ensure the output unfolds properly.

The function trim_and_unrotate handles the long line case, applying the appropriate trimming, then calling back into unrotate_line.

I feel like I’ve ended up with quite an elegant solution. The functions are short and straightforward, and their conditionals are contained. It did take a little while to get there, especially after my initial incorrect solution, but sometimes that’s the nature of the beast. It’s hard to tell, but I’d guess I’ve spent about 5 hours in total, mainly on the output formatting. Still comfortably within Parnas' week or two. Oh, yea. I still got it.

If you feel so motivated, the git history will give some indication of how I thrashed about on this with partial and incorrect solutions before I finally caught on.

We’re back in familiar filtering ground here. We’re reading a sequence of lines of text, doing some processing on each line, and then spitting the result back out. The processing here is removing duplicates, and that’s straightforward:

We do have small bootstrapping problem though - what do we do for the very first line? What do we compare the first line we read with? In a language like, say, Java we can lean on null and do something like this

In Java, we’re never going to read a null string from the input, so we can safely use that as our initial value. For the first line we read currentLine.equals(previousLine) will never be true, so it gets printed out and the program proceeds properly.

In C++ strings are values rather than references. If I declare a string

then str has a value. The value happens to be the empty string, but it’s still a value. What’s more, it’s perfectly possible that we might read empty strings from our input.

So what to do? Do we need to apply some special processing to the very first line, perhaps using a flag to indicate this is first time through?

This works as we want, but that first_line flag really grates on me. It’s a wart.

When we write something like

we’re reaching back into C++'s deep past. C has no real string type, instead kind of bodging through with arrays of characters. A sequence of characters in double quotes, like "I am a string", is stored by C as an array of characters containing the characters of the string and, crucially, terminated with an extra '\0' character as an end of string marker. This behaviour is baked into the C language and library.

C++ preserves this behaviour and these functions - we couldn’t have C interop without that - and a C++ std::string can happily be initialised with a C style character array. However, a std::string isn’t just a simple wrapper around char*, it’s a little more sophisticated than that. Significantly, once it’s initialised and knows its own length, it does not rely on the '\0' character as a terminator. Even more than that, std::string is happy to contain multiple '\0' within its value.

Generally, when we create a std::string we’re initialising from a char*, copying another std::string, or just bringing up a default empty string. But std::string has a several other constructors, including

This constructs a string containing count copies of the character ch. std::string(5, 'a') would be, therefore, "aaaaa". Excitingly std::string(1, '\0') constructs a string containing a single '\0' character. This is something you wouldn’t ever ordinarily encounter, especially when, for example, reading text from an istream.

That’s a rather round-the-houses way of saying we can eliminate the first_line flag using our weird string of '\0'.

I can’t quite decide if this is a neat use of an intended feature, or a crime against code. Possibly both. It’s definitely well-formed C++, but it does feel kind of funky. If it moves you, in a pleasant or uncomfortable direction, I’d be delighted to hear from you.

The full source code, with tests and what-not, for unique, and indeed the whole project, is available in the stiX GitHub repository.

This whole endeavour relies on Software Tools in Pascal and Software Tools, both by Brian W Kernighan and PJ Plauger. I love these books and commend them to you. They are both still in print, but new copies are, frankly, ridiculously expensive. Happily, there are plenty of second-hand copies around, or you can borrow them from The Internet Archive using the links above.

For this project I’ve been using JetBrain’s CLion, which I liked enough to buy a license for. I use it all the time now.

The test harness I’m using is Catch. I’ve been aware of Catch pretty much since it was first released, but this project is the first time really getting in and using it. I like it, and it is my first choice for future work.