7
\$\begingroup\$

My requirement is to convert a sequence of numbers into a display string as below.

Example

Input

1,2,3,4,5,7,7,8,8,8,10,15,10,11,12,88,87,86

Output

1-5,7-8,10-12,15,86-88


void makeDisplayString(std::vector<int>& vector, std::wstring& string)
{
    if(vector.empty()) return; // If empty do nothing

    std::sort(vector.begin(),vector.end()); // Sort vector first

    int& preValue =vector.at(0);
    string.append(std::to_wstring(preValue));

    bool continueFlag = false; // Flag to check if continuation of value

    for(auto const & num : vector)
    {
        if(preValue ==num)  continue; // if same number as previous , Skip it

        if(preValue+1 == num) // If number is one more than privious value
        {
            preValue = num;
            continueFlag=true; // set continuation flag and continue rest part
            continue;
        }

        if(continueFlag) 
        {
            // We reach here only if neither number is save as previous nor it is continous of numbering
            // But befor this number there was a continous numbering
            string.push_back(L'-');
            string.append(std::to_wstring(preValue));
            string.push_back(L',');
            preValue=num;

            string.append(std::to_wstring(num));
            continueFlag = false;
            continue;
        }
        // We reach here only if neither number is save as previous nor it is continous of numbering
        // Also befor this number there was no continous numbering
        preValue = num; 
        string.push_back(L',');
        string.append(std::to_wstring(num));
    }
    // This is to handle a sequence ending with continous number
    if(continueFlag) 
    {
        string.push_back(L'-');
        string.append(std::to_wstring(*vector.rbegin()));
    }
}
\$\endgroup\$
8
\$\begingroup\$

1. Separate data representation from actual output, using standard algorithms where possible.

make_ranges below takes input sequence array and returns limits of all ranges found, in two different sequences from, to:

template<typename F, typename T, typename A>
void make_ranges(F& from, T& to, A array)
{
    auto diff = array;
    std::sort(array.begin(), array.end());
    std::adjacent_difference(array.begin(), array.end(), diff.begin());

    std::vector<size_t> idx(array.size());
    std::iota(idx.begin(), idx.end(), 0);
    auto sep = [&diff] (size_t i) { return diff[i] > 1; };
    for(auto p = idx.begin(); p != idx.end();)
    {
        from.push_back(array[*p]);
        p = std::find_if(++p, idx.end(), sep);
        to.push_back(array[*(p - 1)]);
    }
}

2. For most generic use, use a stream for output:

template<typename S, typename I, typename J>
void print_range(S& stream, I i, J j)
{
    stream << *i;
    if (*j != *i)
        stream << "-" << *j;
}

template<typename S, typename F, typename T>
void print_ranges(S& stream, const F& from, const T& to)
{
    auto i = from.begin();
    auto j = to.begin();
    if (i != from.end())
        print_range(stream, i++, j++);
    while (i != from.end())
    {
        stream << ",";
        print_range(stream, i++, j++);
    }
}

3. For convenient use, provide a streaming operator interface:

template<typename S, typename A>
S& operator<<(S& stream, const array_ranges<A>& ranges)
{
    typename std::decay<A>::type from, to;
    make_ranges(from, to, std::get<0>(ranges));
    print_ranges(stream, from, to);
    return stream;
}

where array_ranges is a helper struct holding a sequence and indicating that its ranges should be streamed out instead of the sequence itself. Given a sequence, an array_ranges instance is made easily via helper function ranges:

template<typename A>
struct array_ranges : std::tuple<A> { using std::tuple<A>::tuple; };

template<typename A>
array_ranges<A> ranges(A&& a) { return array_ranges<A>{std::forward<A>(a)}; }

Example

Now the above can be used as

std::vector<int> arr{1,2,3,4,5,7,7,8,8,8,10,15,10,11,12,88,87,86};
std::cout << arr << std::endl;
std::cout << ranges(arr) << std::endl;

See live example.

If you want to print the ranges into a string, just use an std::ostringstream.

Discussion

With the above separation, you can do more advanced tasks like extracting ranges from arbitrary sequences, processing them (e.g. filtering or merging two sets of ranges), and finally printing them.

If you don't need any extra processing, this separation is more costly than direct printing since it stores intermediate results in arrays from, to. Using std::adjacent_difference introduces another intermediate result.

It is possible to save the extra cost of "intermediate results" while keeping the same design by more advanced techniques like expression templates, but this goes way beyond this simple task.

I would personally prefer a clean design to optimal performance for this task. This makes code more readable and maintainable. Also, with a bit more abstraction, you may find that parts of the code above can be reused elsewhere (especially print_ranges, but I don't want to go too far).

Another choice you could follow is to have an std::pair or (better) a dedicated data structure representing one range. A single sequence would then be enough instead of two sequences from, to, but processing such a sequence would be a bit more involved.

Of course, you are free to flat everything into a single call without intermediates if you prefer.

\$\endgroup\$
4
\$\begingroup\$

State flags usually indicate a design problem.

How about this instead (after vector is sorted) :

template <typename I>
I get_sequential_range(I first, I last)
{
    I end_range = ++first;
    while ((end_range != last) &&(*end_range <= *first + 1)) {
        ++first;
        ++end_range;
    }
    return end_range;
}

template <typename I>
std::stringstream make_display_string(I first, I last)
{
    std::stringstream out;
    I end_range;
    while(first != last) {
        end_range = find_sequential_range(first, last);
        out << *first << '-' << *(end_range - 1) << ',';
        first = end_range;
    }
    return out;
}

Disclaimer: untested. Consider it a pseudocode. And sorry if I misunderstood your task.

\$\endgroup\$
  • \$\begingroup\$ @dvp Good point. \$\endgroup\$ – vnp Apr 23 '14 at 18:07
  • \$\begingroup\$ Oops, no, sorry. That algorithm does something completely unrelated D: \$\endgroup\$ – dyp Apr 23 '14 at 18:16
  • \$\begingroup\$ (It's some kind of negation of adjacent_find; you could use a negated predicate but then the corner-cases get ugly. Redefining some find_not_adjacent seems to be cleaner.) \$\endgroup\$ – dyp Apr 23 '14 at 18:30
3
\$\begingroup\$

I'm late to the party, but here is a nice clean C++11 answer which works with any container supporting begin() and end() iterators (and therefore range-based for) and any contained object meaningfully supporting operator=, operator!=, a stream inserter and operator+. That includes all integer types and character types, of course. Also note that I decided to omit sorting from the algorithm itself, preferring instead to leave that to an external std::sort in the example code.

#include <string>
#include <sstream>
#include <iostream>
#include <vector>
#include <valarray>
#include <algorithm>

template <typename C>
std::string rangeprint(const C &r)
{
    auto first = r[0];
    auto last = r[0];
    std::stringstream result;
    result << first;
    for (const auto &n : r) {
        if (n != last+1 && n != last) {
            if (last != first)
                result << '-' << last;
            result << ',' << n;
            first = n;
        }
        last = n;
    }
    if (last != first) 
        result << '-' << last;
    return result.str();
}

int main()
{
    std::vector<int> r{1,2,3,4,5,7,7,8,8,8,10,15,10,11,12,88,87,86};
    std::sort(r.begin(), r.end());
    std::cout << rangeprint(r) << '\n';

    const std::valarray<char> b{'A','B','C','D','F','G','M','X','Z'};
    std::cout << rangeprint(b) << '\n';
}

Update:

Just for fun, I created a new class to show how this might be used with user-created classes. Here's the class:

class GreekAlphabet {
private:
    const static std::vector<std::string> letterName;
    std::size_t index;
public:
    GreekAlphabet(const GreekAlphabet &g) : index(g.index) {}
    GreekAlphabet(const char *s) {
        for (index = 0; index < letterName.size(); ++index)
            if (s == letterName[index])
                break;
        if (index == letterName.size()) {
            throw std::range_error("invalid Greek letter");
        }
    }
    bool operator!=(const GreekAlphabet &b) const { 
        return index != b.index; 
    }
    GreekAlphabet operator+(int b) const { 
        GreekAlphabet c(*this); 
        c.index = (c.index+b)%letterName.size(); 
        return c; 
    }
    friend std::ostream& operator<<(std::ostream& out, 
              const GreekAlphabet &a) 
    {
        return out << GreekAlphabet::letterName[a.index];
    }
};

const std::vector<std::string> GreekAlphabet::letterName{
        "alpha", "beta", "gamma", "delta", "epsilon", "zeta", 
        "eta", "theta", "iota", "kappa", "lambda", "mu", "nu", "xi",
        "omicron", "pi", "rho", "sigma", "tau", "upsilon", "phi", 
        "chi", "psi", "omega"};

And here's an example of its use with rangeprint():

int main()
{
    const std::vector<GreekAlphabet> ga{"alpha", "beta", "gamma",
        "delta","mu", "nu", "xi", "pi", "rho", "omega"};
    std::cout << rangeprint(ga) << '\n';
}

This prints:

alpha-delta,mu-xi,pi-rho,omega
\$\endgroup\$
2
\$\begingroup\$

I'll start by reviewing the code as it stands, then add some commentary about how I think I'd do this job instead.

I'd say your code is quite readable--while I personally prefer snake_case variable names over the camelCase you've used, it's at least a decent convention and you've followed it fairly consistently.

The names themselves aren't quite as meaningful as I'd prefer though. The prime example would be using vector as the name of the variable holding the input. I see two problems here. First, you've re-used a name from the standard library for an entirely different purpose (a variable instead of a template). While I'm somewhat more tolerant of re-using names for different purposes than many, it seems ill-advised in this case. Second, and more importantly, vector only tells us about an incidental detail of how the input data happens to be stored. It would be much more useful to give it a name that reflects its purpose and use instead--input for one possible example.

That brings us to another point: I think your code specifies types to an unnecessary degree--to the point that its flexibility is substantially reduced. In some cases you can justify reduced flexibility when the greater specialization makes the code much easier to read and/or use--but at least in this case, we don't seem to be gaining a lot.

Finally, I think the code combines two rather separate tasks:

  1. Breaking a collection of inputs into contiguous ranges, and
  2. Converting contiguous ranges to readable strings.

It seems to me that the code would benefit from keeping these two operations separate.

For the first of these, I think @iavr had (at least roughly) the right idea: it should be implemented as a generic algorithm that takes input as a pair of iterators. Unlike his solution, I'd also write the output via an iterator rather than directly to a stream (-like object) using an insertion operator.

This makes it trivial to write the output to a string (via a stringstream), or directly to any other sort of stream, or to a collection (e.g., vector or deque) of the right type.

To do this, I'd start by defining a type to hold a range, and handle insertion of that type into a stream:

template <class T>
class range_t { 
    T begin, end;
public:
    range_t(T begin, T end) : begin(begin), end(end) {}

    friend std::ostream &operator<<(std::ostream &os, range_t const &r) {
        os << r.begin;
        if (r.end != r.begin)
            os << "-" << r.end;
        return os;
    }
};

The stream insertion operator also handles conversion of that object to a string (the second task noted above) by writing to a stringstream. Depending on the situation, it can be beneficial to add a to_string function to carry out that conversion directly. This is largely an optimization though, adding more code to avoid the overhead of a stringstream. I'll leave it out for now, but note that it's generally fairly trivial to add as long as T is a type that itself has a to_string (which it does for the normal integer types in C++11).

Then for the sake of convenience, I'd define a function template to create an object of that type (this allows the type parameter to be deduced from the passed type rather than having to be specified explicitly):

template <class T>
range_t<T> range(T begin, T end) { return range_t<T>(begin, end); }

With those in place we can get to the real code to create a series of ranges from some input data:

template <typename RIt, typename OutIt>
void contiguous_ranges(RIt begin, RIt end, OutIt result) {
    std::sort(begin, end);

    auto pos = begin;
    for (++pos ; pos != end; ++pos) {
        if (*pos > *(pos - 1) + 1) {
            *result++ = range(*begin, *(pos - 1));
            begin = pos;
        }
    }
    *result++ = range(*begin, *(end-1));
}

One minor note: although this uses random-access iterators for the input (thus "RIt" for the type name), the random access is needed only for the std::sort. The rest of the algorithm only requires input iterators (and it's fairly easy to use a different sorting algorithm that doesn't require random access iterators, though typically with some loss of efficiency).

You'd put these together something like this:

std::vector<int> input {1,2,3,4,5,7,7,8,8,8,10,15,10,11,12,88,87,86};

contiguous_ranges(input.begin(), input.end(), 
    infix_ostream_iterator<range_t<int> >(std::cout, ", "));

[To avoid an extra comma at the end of the output, I've used the infix_ostream_iterator from a previous question though you could substitute a normal std::ostream_iterator if you didn't mind an extra comma after the end of the output.]

At least to me, this seems to combine simplicity in use, readability (especially to anybody already accustomed to standard algorithms) and flexibility--it's able to produce output to a string, a stream, or essentially any collection that's accessible via an output iterator.

\$\endgroup\$
  • \$\begingroup\$ The behavior of a C++ program is undefined if it adds declarations or definitions to namespace std. See What can and can't I specialize in the std namespace?. \$\endgroup\$ – iavr Apr 23 '14 at 10:04
  • \$\begingroup\$ @iavr: Good point--one of those things I'm prone to doing when it's late and I'm tired (but fix in the morning). \$\endgroup\$ – Jerry Coffin Apr 23 '14 at 15:10
0
\$\begingroup\$

I'm wondering if you might be over thinking it a bit. By keeping track of start value and end value you test the next number against the end value if it's less than 2 it's the new end value otherwise add this range to your string and start a new range:

std::wstring makeDisplayString(std::vector<int>& invect)
{
    std::wstringstream ss(L"");
    if(!invect.empty()) // If empty do nothing
    {
        std::sort(invect.begin(),invect.end()); // Sort vector first
        //start a new range
        int startValue =invect[0];
        int endValue;
        for(auto const & num : invect)
        {
            if((num - endValue) < 2)
            {
                endValue = num;
            }
            else
            {
                if(startValue == endValue)
                    ss << startValue << ",";
                else
                    ss << startValue << "-" << endValue << ",";
                startValue = num;
                endValue = num;
            }
        }
        ss << startValue << "-" << endValue;
    }
    return ss.str();
}

Rather than trying to change an existing string this returns the string.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.