Tell me more ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.

For example, there is an array a of size 10 contain data as follow:

0.0
0.01
0.02
0.03
5.04
6.05
7.06
13.07
20.08
22.09

If the step fixed is 5, expected data range are:

start   end
0.0     0.03
5.04    7.06
13.07   13.07
20.08   22.09

Any suggestions to implement it like this in C/C++ ? How to program?

share|improve this question
A suggestion: with a single loop. – Inspired 12 hours ago
So, you are saying "start a new row if the difference between the current value and the next value is greater than 5?" – Mats Petersson 12 hours ago
Yes, it is. My English is not good. – Dong 12 hours ago
I want to get the start value and the end value. – Dong 12 hours ago

4 Answers

up vote 1 down vote accepted

You can do it in a simple loop:

#include <stdio.h>

int main(void)
{
    float f, a[] = {0.0, 0.01, 0.02, 0.03, 5.04, 6.05, 7.06, 13.07, 20.08, 22.09};
    size_t i;

    #define N (sizeof a / sizeof a[0])

    for (f = a[0], i = 0; i <= N; i++) {
        if (i == N || a[i] > f + 5.0) {
            printf("%f %f\n", f, a[i - 1]);
            if (i != N) f = a[i];
        }
    }
    return 0;
}
share|improve this answer
It looks like simple but it works well. Thank you! – Dong 11 hours ago
Hey Dong, see edit please, you need to check if (i != N) – David RF 11 hours ago
Hi David, you are great! why can't I find this cool method. – Dong 11 hours ago
Thanks Dong!! ;) – David RF 10 hours ago

You can use a simple loop, saving the last start range. A straightforward implementation in C++:

#include <utility>
#include <vector>

vector<pair<size_t, size_t> > getRanges (vector<double> array)
{
    vector<pair<size_t, size_t> > result;
    size_t indexLastStart = 0;
    double valueLastStart = array[0];

    for (size_t i = 1; i < array.size(); i++)
    {
        if (array[i] - valueLastStart > 5.0)
        {
            result.push_back(make_pair(indexLastStart, i - 1));
            indexLastStart = i;
            valueLastStart = array[i];
        }
    }

    result.push_back(make_pair(indexLastStart, array.size() - 1));
    return result;
}

You can use this function as follow:

int main()
{
    double t[] = { 
        0.0,
        0.01,
        0.02,
        0.03,
        5.04,
        6.05,
        7.06,
        13.07,
        20.08,
        22.09
    };
    vector<double> a(t, t + sizeof t / sizeof *t);
    vector<pair<size_t, size_t> > r = getRanges(a);

    for (size_t i = 0; i < r.size(); i++)
        cout << a[r[i].first] << "\t" << a[r[i].second] << endl;

    return 0;
}

In C, it might look something like:

#include <stdio.h>

struct range
{
    int start;
    int end;
};

size_t getRanges(struct range *result, double *array, size_t inputSize)
{
    size_t outputSize = 0;
    size_t indexLastStart = 0;
    double valueLastStart = array[0];
    struct range added;
    size_t i;

    for (i = 1; i < inputSize; i++)
    {
        if (array[i] - valueLastStart > 5.0)
        {
            added.start = indexLastStart;
            added.end = i - 1;

            result[outputSize++] = added;
            indexLastStart = i;
            valueLastStart = array[i];
        }
    }

    added.start = indexLastStart;
    added.end = inputSize - 1;
    result[outputSize++] = added;
    return outputSize;
}

int main()
{
    double t[10] =
    { 
        0.0,
        0.01,
        0.02,
        0.03,
        5.04,
        6.05,
        7.06,
        13.07,
        20.08,
        22.09
    };
    struct range result[10];
    size_t i;
    size_t size = getRanges(result, t, sizeof t / sizeof *t);

    for (i = 0; i < size; i++)
    {
        printf("%.2f\t%.2f\n", t[result[i].start], t[result[i].end]);
    }

    return 0;
}

This algorithm runs in linear time O(n).

share|improve this answer
Thank you for your code. But, it seems like not easy for me to understand your script. I haven't use "vector" ever. Could you please rewrite it in other way ? In fact, the array size is unknown, data read from a file in row. I want to keep the start value and the end value. – Dong 12 hours ago
@Dong: See my edit for C version. Although you read your data from a file, you can store them in an array (t here), and calculate their size. If you want to generate results on the fly, you should just replace result[outputSize++] assignments by printf calls. – Kirilenko 12 hours ago
Thanks for your kind help! It runs well. – Dong 11 hours ago
#include <iostream>
using namespace std;

int fun(double* arr, int n, double* res)
{
    int start = 0;
    int end   = 0;
    int len   = 0;
    for(int i = start; i < n; ++i)
    {
        if(arr[i]- arr[end] < 5)
        {
            end = i;
        }
        else
        {
            res[len++] = arr[start];
            res[len++] = arr[end];
            start = end = i;
        }
    }
    res[len++] = arr[start];
    res[len++] = arr[end];
    return len;
}

int main()
{
    double t[] = { 
        0.0,
        0.01,
        0.02,
        0.03,
        5.04,
        6.05,
        7.06,
        13.07,
        20.08,
        22.09
    };

    int n = sizeof(t) / sizeof(*t);
    double *res = new double[n];
    int k = fun(t, n, res);
    for(int j = 0; j < k; j += 2)
        cout<<res[j]<<"  "<<res[j+1]<<endl;
 }
share|improve this answer
Thanks. It also works well. But I can choose only one answer. – Dong 11 hours ago

Little late, but anyways here is my quite compact implementation for C++.

template <typename T>
std::vector<std::pair<T, T>> generate_pairs(T *first, T *last)
{
    std::vector<std::pair<T, T>> result(std::distance(first, last) / 2);
    std::generate(std::begin(result), std::end(result), [&first] { return std::make_pair(*first++, *first++); });
    return result;
}

int main(int argc, char *argv[])
{
    double arr[] = { 0.0, 0.01, 0.02, 0.03, 5.04, 6.05, 7.06, 13.07, 20.08, 22.09 };

    auto v = generate_pairs(std::begin(arr), std::end(arr));
    for (const auto &p : v)
        cout << "(" << p.first << ", " << p.second << ")" << endl;

    return 0;
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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