[fpc-pascal] Comparing version numbers

[Eduardo]

At 23:03 02/06/2006, you wrote:
>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 ?

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.