Just for fun, I decided to demonstrate to myself that C++ is really just as suited to this kind of thing.
Test-first, please
First, let me define the requirements a little more strictly: I assumed it needs to handle these cases:
int main()
{
const std::string in("This is some e-z test in 5-7 steps; this works: a-b-c. This works too: b-k-c-e. Likewise 8-4-6");
std::cout << "input : " << in << std::endl;
std::cout << "output: " << expand(in) << std::endl;
}
input : This is some e-z test in 5-7 steps; this works: a-b-c. This works too: b-k-c-e. Likewise 8-4-6
output: This is some efghijklmnopqrstuvwxyz test in 567 steps; this works: abc. This works too: bcdefghijk. Likewise 45678
C++0x Implementation
Here is an implementation (actually a few variants) in 14 lines (23 including whitespace, comments) of C++0x code1
static std::string expand(const std::string& in)
{
static const regex re(R"([a-z](?:-[a-z])+|[0-9](?:-[0-9])+)");
std::string out;
auto tail = in.begin();
for (auto match : make_iterator_range(sregex_iterator(in.begin(), in.end(), re), sregex_iterator()))
{
out.append(tail, match[0].first);
// char range bounds: the cost of accepting unordered ranges...
char a=127, b=0;
for (auto x=match[0].first; x<match[0].second; x+=2)
{ a = std::min(*x,a); b = std::max(*x,b); }
for (char c=a; c<=b; out.push_back(c++));
tail = match.suffix().first;
}
out.append(tail, in.end());
return out;
}
Of course I'm cheating a little because I'm using regex iterators from Boost. I will do some timings comparing to the C version for performance. I rather expect the C++ version to compete within a 50% margin. But, let's see what kind of surprises the GNU compiler ahs in store for us :)
Here is a complete program that demonstrates the sample input. _It also contains some benchmark timings and a few variations that trade-off
- functional flexibility
- legibility / performance
#include <set> // only needed for the 'slow variant'
#include <boost/regex.hpp>
#include <boost/range.hpp>
using namespace boost;
using namespace boost::range;
static std::string expand(const std::string& in)
{
// static const regex re(R"([a-z]-[a-z]|[0-9]-[0-9])"); // "a-c-d" --> "abc-d", "a-c-e-g" --> "abc-efg"
static const regex re(R"([a-z](?:-[a-z])+|[0-9](?:-[0-9])+)");
std::string out;
out.reserve(in.size() + 12); // heuristic
auto tail = in.begin();
for (auto match : make_iterator_range(sregex_iterator(in.begin(), in.end(), re), sregex_iterator()))
{
out.append(tail, match[0].first);
// char range bounds: the cost of accepting unordered ranges...
#if !SIMPLE_BUT_SLOWER
// debug 15.149s / release 8.258s (at 1024k iterations)
char a=127, b=0;
for (auto x=match[0].first; x<match[0].second; x+=2)
{ a = std::min(*x,a); b = std::max(*x,b); }
for (char c=a; c<=b; out.push_back(c++));
#else // simpler but slower
// debug 24.962s / release 10.270s (at 1024k iterations)
std::set<char> bounds(match[0].first, match[0].second);
bounds.erase('-');
for (char c=*bounds.begin(); c<=*bounds.rbegin(); out.push_back(c++));
#endif
tail = match.suffix().first;
}
out.append(tail, in.end());
return out;
}
int main()
{
const std::string in("This is some e-z test in 5-7 steps; this works: a-b-c. This works too: b-k-c-e. Likewise 8-4-6");
std::cout << "input : " << in << std::endl;
std::cout << "output: " << expand(in) << std::endl;
}
1 Compiled with g++-4.6 -std=c++0x
