I have tried about a dozen different algorithms now, and I admit to being stumped because everyone I've tried fails SOMEWHERE.

The task before me is to compare version numbers of software packages and determine which is higher.
First try was to simply do a string comparison.
This almost worked, except that
4.0.12
Is asciibeticallly smaller than
4.0.1

So much for that idea then.
So I figured, let's convert them to integers, we drop any non-numeric characters and with the rest we do just add them up, each time multyplying by 10 first.
So 4.0.12 becomes 4012 etc.
Almost worked and solved the above problem - but now: 4.0.12 -> 4012
4.1.0 -> 410
And 4.1.0 is of course supposed to be bigger.

So next plan, convert them to real's using a variation of the same theme. So that worked a bit better, now
4.10 > 4.012
Unfortunately this has it's own problem because
4.0.7 > 4.012
(But 4.0.12 is a higher version).

I am out of ideas.
Somehow I have to treat all the parts correctly, while being compatible with things that follow slightly different schemes (udev packages for example have no fullstops).
The one good piece of news is that I ONLY need to compare versions of the SAME package. So I don't have to worry about comparing 4.0.12 with udev's 070 for example.

So the question is:
1) does somebody HAVE an algorithm for this already ?
2) If not, can somebody give me a hint about what approach to take ?

A.J.

String based: rework till you have a fixed pattern like 0004.0000.0012 Problem: the first 5 digit version nr (e.g. perl minor) breaks. If you take 5 digits, the first 6 digit will fail etc.

number based: a version is a (small) array of integers. Better than string, but a string is variable length allowing in theory infinite subversions. So make it a dyn array to achieve the same.

A.J. Venter wrote

So the question is: 1) does somebody HAVE an algorithm for this already ? 2) If not, can somebody give me a hint about what approach to take ?

Split the version string in several numbers:
version := '4.0.12';
major := 4
minor := 0;
patch := 12;
versionnumber := major * 10000 + minor * 100 + patch

then you can numerically compare version numbers.

the 100 (a) and 10000 (b) can be adjusted for your needs.

a must be bigger than the max number of patches
b must be bigger that the max numer of patches times the max numer of minor versions.

So this algorithm can not 4.194.299

Vincent

Actually I found my answer just now after asking a friend who is a debian user.
Turns out debian documents the pseudocode for their method in the manpages.

So I am just busy translating the pseudo to pascal now.

1. take any initial string of non-digits from each, remove, and compare ASCIIbetically.
If there's a difference, terminate. If not:
2. Take any initial string of digits from each, remove, and compare numerically.
If there's a difference, terminate. If not, goto 1.

(Oh and I'm using while, not goto :p )

A.J.

Simple, just a variation of your first try. Use ASCII comparation, but all parts must have the same digits, in your case, you padd the 3rd part (or any part) with any letter down the ascii code of 0, for example ' ' (a space)
4.0.12 and 4.0.1 -----> 4.0.12 and 4.0.1[space] so the 4.0.1 are the equal, but when comparing 2 with [space] it does it corrctly. The padd can be done at comparation time, so you don't need to add any [space] when creating the version number.
4.0.7 and 4.0.12 -----> 4.0.7[space] and 4.0.12, same case as above, 2 > [space]
4.0.70 and 4.0.12 -----> no padding so 4.0.70>4.0.12

pseudocode :
// s,t string to compare, array based 1.
function bigger (s,t : string) : boolean;
i,j,k,l : array index;
out : partial result of function
begin
         out := FALSE
         // Padd with spaces
         i,j := 1;
         repeat
                  k := i; l := j
                // Count how many chars are in s until the next '.'
                  repeat
                           k:= k+1;
                  until s(k)='.' ;
                // Idem in t
                  repeat
                           l := l+1;
                  until t(l)='.';
                // If there are more chars in s, k will be greater than l
                // Also, as, we have inserted spaces, now both, k and
l, have the greater of k and l
                  if k>l then insertspaces( t , l, k-l+1) l :=
k;   // Insertspaces maps directly with a Pascal string manipulation function
                  if k<l then insertspaces( s, k, l-k+1) k :=l;
                // Update i and j values; k and l are equals, i and j too
                  i := i+k; j := j+l;
         until i > len(s) OR j > len(t);
         // Compare
         i,j := 1;
         repeat
                  out := s(i)>=t(j);
                  i := i+1; j := j+1;
         until (i > len(s) OR j > len(t)) AND out;
         bigger := out;
end;{End Function Bigger}
//Returns TRUE if s >= t, FALSE if s < t

Translation to Pascal and optimizations are leaved as exercise

HTH

------------------------------------------------------------------------------------------------------------------------------------------------------------------- Scientists have shown that the moon is moving away at a tiny yet measurable distance from the earth every year.
If you do the math, you can calculate that 85 million years ago the moon was orbiting the earth at a distance of
about 35 feet from the earth's surface. This would explain the death of the dinosaurs. The tallest ones, anyway.

Simple, just a variation of your first try. Use ASCII comparation, but all parts must have the same digits, in your case, you padd the 3rd part (or any part) with any letter down the ascii code of 0, for example ' ' (a space)

This was a brilliant idea as far as I can see. MUCH simpler than the debian way.
And my code for it is a LOT shorter than yours ;)

function CompareVersion(Version1,Version2:String):Boolean;
Var
   L1,L2,I : Integer;
   V1,V2 : String;
Begin
 V1 := Version1;
 V2 := Version2;
 L1 := Length(V1);
 L2 := Length(V1);
 If L1 > L2 then
      For I := L2 to L1 do
       V2 := V2 + ' ';
 If L2 > L1 then
      For I := L1 to L2 do
       V1 := V1 + ' ';
 CompareVersion := V1 > V2;
end;

The debian version on the other hand is well over 200 lines of code by itself, and I am not entirely sure my version is going to be stable on all testdata yet.

With the testdata I have right now, which is a very good representation of INTENDED usage (and we all know how rarely that is only usage) both now seem to give the exact same results.
So - I am leaving the debian version in the code, but commented out, and going with Eduardo's unless I find a VERY good reason to go with the other later - because THIS one is guaranteed WAY easier to maintain, much less likely to puke on bad data and I cannot see a difference in results.

Thanks a great deal.
A.J.

That's the c way of do the things. I have seen deterministic code in c that works very well, but if you compile the code with 2 different compilers you get different output from same input. (Determinist algorithms always out the same output from the same input, by definition).

Your code can't work with these ones, 4.1.15 and 4.12.1 because you only pad the 3rd (15 and 1), you need to pad each part of the version, my pseudocode out 4.1[space].15 and 4.12.1[space]. You can call your function with the 4,4; again with 12,1 utnil you get a result.... but you need a ternary boolean, as 4,4 generates an invalid result state.

Mmm, good point, I didn't think of that, but it's fairly easy to expand now (I am much better at reading real code than pseudocode)

A.J.

I think this is the winner solution.

But you don´t have to do this:

versionnumber := major * 10000 + minor * 100 + patch

It´s better to just do many ifs, something like this:

type
  TVersao = packed record
    TamanhoDaEstrutura: Cardinal;
    VersaoMaior: Integer;
    VersaoMenor: Integer;
    Distribuicao: Integer;
    Construcao: Integer;
    Patch: Integer;
  end;
function IsVersionBigger(Esperada, Ver: TVersion): Boolean;
begin
  Result := False;
  if Esperada.VersaoMaior < Ver.VersaoMaior then
   Result := True
  else if Esperada.VersaoMenor < Ver.VersaoMenor then
   Result := True
  else if Esperada.Distribuicao < Ver.Distribuicao then
   Result := True
  else if Esperada.Construcao < Ver.Construcao then
   Result := True
  else if Esperada.Patch <= Ver.Patch then
   Result := True;
end;

This supports up to 4 dots separating 5 version parts. Of course, you can build a dynamic structure to hold any number of version parts and then do a while to hold the any number of ifs.

Turns out there is a deeper flaw anyway :s
Neither version works with for example this one:
2.8.7 - 2.8.13
Even if you pad 2.8.7 you still end up with a failure. The only way to prevent said failure is to pad it at the beginning: 2.8. 7 < 2.8.13
But THAT way around breaks a whole bunch of others for example in my case there is an older package versioned 070utopia which needs to be seen as older than 071 (without the sub specifier) - THAT one only works if you pad at the end.
So there is no way to predict which side you need to pad for the right result.

Considering that, I went back to the debian algorithm. True it's a very c-like approach to things, but it does seem to work and I guess if it works for debian that's a fairly major vote of confidence.

Here is my code (note that FirstNonDigit and FirstDigit are functions I wrote, which return the pos of the first digit/nondigit in the string - either returns -1 in case of no match).

Begin
Done := False;
Res := False;
repeat
If (FirstNonDigit(V1) = -1) and
   (FirstDigit(V1) = -1) then
    Done := True;
IF FirstNonDigit(V1) < FirstDigit(V1) then
begin
 S1 := Copy(V1,1,FirstDigit(V1) -1);
 Delete(V1,1,firstDigit(v1) -1);
 S2 := Copy(V2,1,FirstDigit(V2) -1);
 Delete(V2,1,FirstDigit(v2) -1);
 If S1  S2 then
 begin
    Done := True;
    If S1 > S2 then
     Res := True;
  end;
end;
IF (FirstNonDigit(V1) > FirstDigit(V1)) and (Not Done) then
begin
 S1 := Copy(V1,1,FirstNonDigit(V1) -1);
 Delete(V1,1,firstNonDigit(v1) -1);
 S2 := Copy(V2,1,FirstNonDigit(V2) -1);
 Delete(V2,1,FirstNonDigit(v2) -1);
 If StrToInt(S1)  StrToInt(S2) then
    Done := True;
 If StrToInt(S1) > StrToInt(S2) then
        Res := True;
end;
until done;
CompareVersion := Res;
end;

A.J. Venter wrote

The debian version on the other hand is well over 200 lines of code by itself, and I am not entirely sure my version is going to be stable on all testdata yet.

Learn to code with UnitTests (process is called Test Driven Development). I have to admin, it takes a while to get use to it, but you have a major confidence boost after writing some code, and having tests to prove that it works.

This version number process is a perfect candidate to start with.

Regards,
Graeme.

Learn to code with UnitTests (process is called Test Driven Development).

Never used. How does this work? I found only a unit called "UnitTests.pp" and nothing else.
Thank you.

jk

The first article that started the practice, written by Kent Beck and Erich Gamma:
http://junit.sourceforge.net/doc/testinfected/testing.htm

See also the JUnit website
http://www.junit.org/index.htm
for more articles on the subject.

To get you started with unit testing with FPC:
http://www.freepascal.org/docs-html/fpcunit.pdf

Regards,
Dean

Use an xUnit testing framework while coding. Free Pascal comes with fpcUnit. Under Delphi people normally use DUnit. Under Java they use JUnit, etc...

Regarding TDD (Test Driven Development) look at the following websites: In short - You write a test, Write the code, Run the tests, Refactor. Then repeat the whole process... The first 3 steps should be completed in under a minute. As I said, it is very different to traditional programming style, but once mastered, you can't think of programming any other way.

http://en.wikipedia.org/wiki/Test_driven_development http://www.testdriven.com
http://www.agiledata.org/essays/tdd.html

Regards,
- Graeme -

Well my only real worry was whether I needed to do exception catching on the strToInt calls, but I cannot imagine a dataset where my other functions wouldn't ensure I have valid inputs for those.

I'm checking your links though - it may well be worth running through it.

I should just mention this function is actually part of a lazarus project, but since it's not visual in any way and doesn't use the LCL at all, I reckoned fpc-pascal would be a more appropriate place to ask questions.

A.J.

I've said this before but most of the test-driven development stuff is kind of quack. That a program needs to be tested, is common sense. The programs which need to be tested more, are programs that are going to be used frequently. Write programs that test your library or program, but don't buy books or read web pages about that quack called test-driven development - because it's just books about common sense - flawed common sense, actually.

You simply can't always write tests *before* you develop your program because this is too much design up front. If you know all the tests you should write before you even *have your program coded*, then you are designing too much up front, and knowing too much up front - this is not the way case in programming - the program changes as you start developing it. So you can't test for everything before you write any code.

Sometimes you need a quick program that will only be used a few times in the entire year, and writing tests would be a waste of time.

And as for the testing suite that FPC uses - this is not even "test driven development", according to the true definition of test driven development. The test suite that fpc has are composed of a bunch of tests written by users and developers who found bugs after the code for FPC was already written. In other words, most of us realistically write code before writing tests - and the most effecient way to write tests is have your users write the tests, if you can. A bug reporting system is a testing system. But since bugs come after code has written, this must be against the test driven development model. I bet the test driven development model requires that you write all your bugs before any code is written - so that you don't need a bug reporting system. Hogwash.

Use common sense - test the hell out of your programs if they are going to be used 100 times per day, if you are having lots of problems with that program. If you aren't having any problems with that program - and it's doing its job - testing the program would be like beating a dead horse. All programs have bugs - but if the bugs affect no one, then there is no point in fixing those bugs. FPC for example has about a million undiscovered bugs - and no one in their right mind could know those bugs ahead of time by writing tests ahead of time - it's not humanly possible. Realistically, and reasonably (which test-driven development is not) most of the bugs are going to be tested for after some code is written for the job first. If you write tests first, you might be writing stupid tests that you already know work - because what you know works, is the tests you will write for! What you don't know works, isn't written yet - so you can't test it yet. Those are the tests that you need to spend time on - the stuff you don't know - not the stuff you know. Until you write complicated code that's broken, you can't write a good test. But this isn't what TDD pages or books seem to claim.

Write your own tests by hand - don't use any "testing framework". It's simply easier to write mini programs that test your code, than it is to use some testing framework. Each program and each library you write will need to be tested uniquely - a framework is impossible since there is no "framework" around testing. Testing is unique - anything so unique as testing cannot possibly have a framework. A web program will need completely different tests, and completely different prioritization of what to test than a search utility program or a file back up program, or a you-name-it program.

What people do need to learn about tests - is that they need to save their tests. Save them for later. This doesn't mean you need a testing framework. It simply means you need to dedicate a /tests/ folder in your project directory and save some tests there. But imagine you spend several days writing tests for a large project ahead of time - before writing actual code for the project - then you finally get around to writing the project and you find out that the project is a no-go. People don't want the project. Your software idea was good for a few folks - but the product isn't needed on the market - there was only 1-5 people who needed it per city. So you wasted all that time writing tests when you could have wrote a quick demo program and see if people needed summary, "test-driven development" is not going to magically solve any problems like they say it will in the books and on those web pages. Writing tests using common sense will help you - but reading into the magical test-driven quack out there will just slow you down. Learning that you must SAVE and write your tests down is smart - but following word for word some quackery like TDD is going to make things worse for you.

Just my opinion. Beware of the TDD consultants.

L505 wrote

You simply can't always write tests *before* you develop your program because this is too much design up front. If you know all the tests you should write before you even *have

A am afraid you are very misguided about what Test Driven Development actually is!!! Do yourself (and everybody on this list) a favour and by the book mentioned below (it's cheap, only $30) and try the examples. This way you will actually know what TDD is.

Test Driven Development: By Example (written by Kent Beck) http://tinyurl.com/kjl8a

A few points to correct some of you statements.

* TDD is a different way of thinking compared to traditional programming. It takes some getting used to, but once you grasp the concept it is brilliant.
* You do *not* write *all* tests before you start coding! You write a single test, testing a small part of your problem representing a small step of progress. This test should represent how you would like to use your code (the ideal interface, though it might change later) That test should fail because it hasn't been implemented yet. You then do a minor change (should take under a few seconds) in code (sometimes even hard code the result) to get the test to pass. You then refactor your code to get rid or all duplication (could be code duplication or data duplication). Your test should still pass. Now you move on to the next small test and repeat the whole cycle.
* Saying only frequently used applications should be test is ludicrous! So running a mission critical app once at the end of the year processing all data from the whole year shouldn't be tested? All code that has no obvious solution should be tested! It's like building a car and saying Nah, we don't need to test the airbags because they wouldn't be used in your everyday commute!!
* TDD doesn't actually slow down you first three
steps should all happen under a minute. That's writing the test and making the test pass in the quickest possible way. Refactoring the code to remove duplication takes longer. Once completed, you know know that part of code works and has a test to prove it. You can now base other code on that with the confidence knowing it works.

your program coded*, then you are designing too much up front, and knowing too much

Exactly the opposite. No design is done up front (the major difference to traditional programming). You are only testing a tiny part of a problem that represents progress, not the complete solution. You use the ideal interface that you would like to use in the end on you library or whatever (though it might change because nobody can foresee a perfect solution upfront).

And as for the testing suite that FPC uses - this is not even "test driven development", according to the true definition of test driven development. The test suite that fpc has are composed of a bunch of tests written by users and developers who found bugs after the

This is why I know you are confused between using a xUnit Testing Framework and TDD. FPC doesn't use fpcUnit, they use their own home grown solution. They have tests to confirm things they have fixed. So now they can continue implementing new things, and if anything new breaks old code, their tests will notify them of that! The same bug cannot be reintroduced again, ever!

code for FPC was already written. In other words, most of us realistically write code before writing tests -

I did say TDD is different to the normal way of coding.

the tests, if you can. A bug reporting system is a testing system. But since bugs come after code has written, this must be against the test driven development model.

Oh, so you would rather release you buggy product to the world and let them find problems you didn't think of. Boy, will you look like a real good developer when those bug reports start streaming in. Not to mention, how many sales you will loose after potential clients hear about you buggy software, and that they need to waste their time, telling you about things you should have done right the first time. I would rather release code, I know that works, and have the confidence in my product because I know my unit tests pass. Yes there might still be some test I didn't think of, but at least I should have a much more reliable product than yours.
The process of handling those minor bug reports are explained next.

I bet the

test driven development model requires that you write all your bugs before any code is written - so that you don't need a bug reporting system. Hogwash.

If a bug gets reported, I would add to my test suite a new test that exposes that bug (the test will fail), then fix the bug and the test should pass. Now that bug cannot be reintroduced without me knowing about it (this is kinda what the FPC Team is doing as far as I can see).

like beating a dead horse. All programs have bugs - but if the bugs affect no one, then there is no point in fixing those bugs.

Now I have heard it all!!! If you know about a bug, it should be fixed.

code is written for the job first. If you write tests first, you might be writing stupid tests that you already know work - because what you know works, is the tests

Wrong again. You write a test to represent a small step of progress towards the ultimate solution. That test should fail, until you have implemented it and refactored to get rid of duplication. You should really read that book written by Kent Beck, you have no clue what TDD actually is!

Write your own tests by hand - don't use any "testing framework". It's simply easier to write mini programs that test your code, than it is to use some testing framework. Each

Now you are proving that you don't know what a Testing Framework is. A testing framework gives you the tools to write test really fast and in a uniform manner. It also guarantees that results for those test will be presented after the test run has completed. All tests will be in a uniform style and shows you how you are supposed to use a function or library, etc.. (almost like a programmers manual if you like).

All I can say, is that you are completely misguided in what you think Test Driven Development is, or even a xUnit Testing Framework for that matter. Spend the $30 wisely and buy the book mentioned (no I don't get any commision on sales. Kent Beck doesn't even know I exist).

Regards,
Graeme.