5
\$\begingroup\$

Given two version numbers, version1 and version2, compare them.

Version numbers consist of one or more revisions joined by a dot '.'. Each revision consists of digits and may contain leading zeros. Every revision contains at least one character.

To compare version numbers, compare their revisions in left-to-right order. Revisions are compared using their integer values ignoring any leading zeros. This means that revisions 1 and 001 are considered equal. If a version number does not specify a revision at an index, then treat the revision as 0. For example, version 1.0 is less than version 1.1 because their revision 0s are the same, but their revision 1s are 0 and 1 respectively, and 0 < 1.



int compareVersion(const char * v1, const char * v2)
{
    while (*v1 || * v2) 
    {
        int a=0, b=0;
        
        while (*v1 && *v1 != '.')  a = 10*a + (*v1++ - '0');
        while (*v2 && *v2 != '.')  b = 10*b + (*v2++ - '0');
        if (*v1) v1++;
        if (*v2) v2++;
        if (a < b) return -1;
        if (a > b) return +1;
    }
    return 0;
}
\$\endgroup\$
1
  • \$\begingroup\$ How about data of unequal lenghts, say 2 vs. 2.0...? Is the no–number less than zero, or equal zero? \$\endgroup\$
    – CiaPan
    Commented Feb 25, 2022 at 8:41

3 Answers 3

5
\$\begingroup\$

This code is nicely presented and easy to follow. It's immediately clear how it works.

For code like this, I strongly recommend writing unit tests to verify the behaviour and exercise the border-line cases. A good test case is compareVersion("1", "1.0"). This function considers those to be equal - that may or may not be a reasonable interpretation of the requirements, but it's worth documenting, perhaps in a comment. If we want 1.0 to sort greater than 1, then only a simple change is needed:

while (*v1 && * v2) 
{
    ⋮
}

return !*v2 - !*v1;

That last line may be cryptic enough to be worth a comment - it's based on the standard comparison idiom (a > b) - (b > a).

Another set of inputs that we should test is of invalid inputs - at the moment we'll get fairly arbitrary results if we're called with non-numeric characters in the input. Though I'm not really sure what we should do with them - perhaps ignore non-digits. Remember to convert to unsigned char if using standard isdigit() function!

Since version number components can't be negative, it might be better to use unsigned types for a and b. We could use strtoul() or similar to convert the digits to numbers, but hold that though - at present, there's no check for overflow, but we could make an overflow-proof version quite easily by identifying the significant digits in each component (i.e. ignoring leading zeros). If one component has more significant digits than the other, it's greater, otherwise compare the significant digits as strings (strncmp()).

\$\endgroup\$
0
1
\$\begingroup\$

Your code is clear in my opinion, I will suggest some improvements that are not really necessary on this scale but will help when you will start dealing with more complex and longer code:

Commenting the why

What are these lines doing:

    if (*v1) v1++;
    if (*v2) v2++;

They are skipping the dot right? This explains why you are doing the comparison and incrementing the counter, so add a comment:

    // Skip the dots
    if (*v1) v1++;
    if (*v2) v2++;

Self descriptive names

a and b are very generic names that could represent anything, I renamed them v1_current and v2_current

Modularity

What is

    while (*v1 && *v1 != '.')  a = 10*a + (*v1++ - '0');

doing? It is updating the value of a adding the value found between two dots, this can be extracted into a function to be tested separately to increase the robustness and readability of the code:

void update_count(const char * version, int *current_count) {
    // Update the current count with the value between the dots.
    while (*version && *version != '.')  (*current_count) = 10*(*current_count) + (*version++ - '0');
}

Automatic testing

How can I be sure that I did not break anything while doing these changes? A very lightweight automated testing using assert can benefit even simple project to making it simpler to both optimize and refactor the code.

Final revision

Here I applied all the improvements, the code is longer, but much of the added length are tests that can double as documentation for a potential future user and the helper function, that is a good practice.

#include <stdio.h>
#include <assert.h>

void update_count(const char * version, int *current_count) {
    // Update the current count with the value between the dots.
    while (*version && *version != '.')  (*current_count) = 10*(*current_count) + (*version++ - '0');
}

int compareVersion(const char * v1, const char * v2)
{
    // Compare two version numbers of the form
    // dd.d.dd where d is a digit (ex: 2.1.3 is bigger than 1.2.1)
    // Returns:
    //  +1 if the first version number is bigger than the second one
    //  -1 if the second one is bigger
    //   0 if they are equal

    while (*v1 || * v2) 
    {
        int v1_current=0, v2_current=0;
        
        // Read the number between two dots (or the first or last one)
        update_count(v1, &v1_current);
        update_count(v2, &v2_current);

        // Skip the dots
        if (*v1) v1++;
        if (*v2) v2++;

        // +1 if the first version number is bigger than the second one
        if (v1_current < v2_current) return -1;
        if (v1_current > v2_current) return +1;
    }
    return 0;
}

int main() {

    int a = 0;
    update_count("1.0.32", &a);
    assert(a == 1);

    int b = 0;
    update_count("23.4.1", &b);
    assert(b == 23);

    assert(compareVersion("1.0.32", "1.0.32") == 0);
    assert(compareVersion("1.0.32", "1.0.33") == -1);
    assert(compareVersion("1.0.36", "1.0.34") == 1);
    assert(compareVersion("2.0.32", "1.0.32") == 1);

}
\$\endgroup\$
5
  • \$\begingroup\$ update_count(v1, &v1_current); .... if (*v1) v1++; looks wrong as pointer v1 is not changed due to update_count(). This also implies test cases are not robust. \$\endgroup\$ Commented Mar 3, 2022 at 3:48
  • \$\begingroup\$ Try assert(compareVersion("2.10.32", "2.010.32") == 0); \$\endgroup\$ Commented Mar 3, 2022 at 3:57
  • \$\begingroup\$ assert() is not useful for testing when not compiling in DEBUG mode. Was that your intent? \$\endgroup\$ Commented Mar 3, 2022 at 4:22
  • \$\begingroup\$ @chux-ReinstateMonica after you are sure that your code is correct you can compile with optimizations to remove the assert statements \$\endgroup\$
    – Caridorc
    Commented Mar 3, 2022 at 10:42
  • \$\begingroup\$ @chux-ReinstateMonica thanks for the bug hunting, sadly I am in exam session so I cannot fix them now, feel free to fix them yourself either by editing my answer or by making a new answer. \$\endgroup\$
    – Caridorc
    Commented Mar 3, 2022 at 10:45
1
\$\begingroup\$

Overflow

Using int can have trouble with integers as small as 32K. Consider a version using a time stamp of 14 digits as one of the fields 20220302101901. Use some unsigned type, perhaps uintmax_t. Even then I would consider detecting overflow - or see below.

What if non-digit or non-dot?

Since separators like ,, and letters are treated pathologically like digits, how about giving those meaning as separators and not using them to compute the version value?

// while (*v1 && *v1 != '.')  a = 10*a + (*v1++ - '0');
while (isdigit(*v1))  a = 10*a + (*v1++ - '0');

Pedantically, should use unsigned char values with is...()

while (isdigit(*(const unsigned char*)v1))  a = 10*a + (*v1++ - '0');

... or use (*v1 >= '0' && *v1 <= '9') if avoiding libraries.

NULL?

Since version compare is often done near the beginning of code and the result is very important, I'd like the comparison to tolerate more of the usual mistakes like NULL or effect some error message.

int compareVersion(const char * v1, const char * v2) {
  if (v1 == NULL) v1 = "";
  if (v2 == NULL) v2 = "";
  ...

Unlimited integer precision

No multiplication, no precision limit.

// Used unsigned access.  Avoid UB with `isdigit()` and correct for non-2's complement.
const unsigned char *u1 = v1;
const unsigned char *u2 = v2;

while (*u1 || *u2) {
  // Consume leading uninformative zero digits.
  while (*u1 == '0') u1++; 
  while (*u2 == '0') u2++; 

  int compare = 0;
  while (isdigit(*u1) && isdigit(*u2)) {
    if (*u1 != *u2 && compare == 0) { 
      compare = *u1 > *u2 ? 1 : -1;
    }
    u1++;
    u2++;
  }
  // Compare meaningful here only if same number of digits in u1, u2.

  // If one string has more significant digits, it is larger
  if (isdigit(*u1)) {
    return 1;
  }
  if (isdigit(*u2)) {
    return -1;
  }

  if (compare) {
    return compare;
  }
  if (*u1) u1++;
  if (*u2) u2++;
}
return 0;

  
  
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I'd picked up on the unlimited-precision compare, but assumed we had to count the digits before comparing them, rather than just discarding the comparison when one input turns out to be shorter. Thank you for showing us that! \$\endgroup\$ Commented Mar 3, 2022 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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