How to get the next prefix in C++?

Question

Given a sequence (for example a string "Xa"), I want to get the next prefix in order lexicographic (i.e "Xb"). The next of "aZ" should be "b"

A motivating use case where this function is useful is described here.

As I don't want to reinvent the wheel, I'm wondering if there is any function in C++ STL or boost that can help to define this generic function easily? If not, do you think that this function can be useful?

Notes

• Even if the examples are strings, the function should work for any Sequence.
• The lexicographic order should be a template parameter of the function.

From the answers I conclude that there is nothing on C++/Boost that can help to define this generic function easily and also that this function is too specific to be proposed for free. I will implement a generic next_prefix and after that I will request if you find it useful.

I have accepted the single answer that gives some hints on how to do that even if the proposed implementation is not generic.

Answer 1

That seem so specific that I can't see how it would get in STL or boost.

Answer 2

When you say the order is a template parameter, what are you envisaging will be passed? A comparator that takes two characters and returns bool?

If so, then that's a bit of a nightmare, because the only way to find "the least char greater than my current char" is to sort all the chars, find your current char in the result, and step forward one (or actually, if some chars might compare equal, use upper_bound with your current char to find the first greater char).

In practice, for any sane string collation you can define a "get the next char, or warn me if I gave you the last char" function more efficiently, and build your "get the next prefix" function on top of that. Hopefully, permitting an arbitrary order is more flexibility than you need.

Answer 3

Orderings are typically specified as a comparator, not as a sequence generator.

Lexicographical orderings in particular tend be only partial, for example, in case or diacritic insensitivity. Therefore your final product will be nondeterministic, or at best arbitrary. ("Always choose lowest numerical encoding"?)

In any case, if you accept a comparator as input, the only way to translate that to an increment operation would be to compare the current value against every other in the character space. Which could work, 127 values being so few (a comparator-sorted table would make short work of the problem), or could be impossibly slow, if you use any other kind of character.

Answer 4

The best way is likely to define the character ordering somehow, then define the rules from going from one character to two characters to three characters.

Use whatever sort function you wish to use over the complete list of characters that you want to include, then just use that as the ordering. Find the index of the current character, and you can easily find the previous and next characters. Only advance the right-most character, unless it's going to roll over, then advance the next character to the left.

In other words, reinventing the wheel is like 10 lines of Python. Probably less than 500 lines of C++. :)

Answer 5

I'm not sure I understand the semantics by which you wish the string to transform, but maybe something like the following can be a starting point for you. The code will increment the sequence, as if it was a sequence of digits representing a number.

template<typename Bi, typename I>
bool increment(Bi first, Bi last, I minval, I maxval)
{
    if( last == first ) return false;
    while( --last != first && *last == maxval ) *last = minval;
    if( last == first && *last == maxval ) {
        *last = minval;
        return false;
    }
    ++*last;
    return true;
}

Maybe you wish to add an overload with a function object, or an overload or specialization for primitives. A couple of examples:

string s1("aaz");
increment(s1.begin(), s1.end(), 'a', 'z');
cout << s1 << endl;     // aba

string s2("95");
do {
    cout << s2 << ' ';  // 95 96 97 98 99
} while( increment(s2.begin(), s2.end(), '0', '9') );
cout << endl;