Find the missing one!

[Techno]

So, lets say in our DB we are reading a column.
The column is a string (varchar). Example of values:

0.0.0.100-0
0.0.0.100-1
0.0.0.100-2
0.0.0.100-3
0.0.0.101-0
0.0.0.102-1
0.0.0.103-0


its like a "version" thing.

So, I need to know which one would be missing from the list. What I mean is:

0.0.0.100-0
0.0.0.100-1
0.0.0.100-3
0.0.0.100-4

in here, we know 0.0.0.100-2 so i need to "flag" this.

however, if all was fine, then it should also be able to handle this:

..
0.0.0.100-2
0.0.0.100-3
0.0.0.101-1
0.0.0.101-2

we know here that 0.0.0.101-0 is missing - it needs to flag this scenario too.

any ideas what the best way is?

[techgnome]

this might be how I'd do it...
(assuming SQL Server)
Create a table var, with fields that represent each part of the numbering...
5 fields... at least... amybe 6
Then I'd loop through each entry in the source table, breaking the pieces up (essentially splitting on the . and the - ) and putting each element into the corresponding fields in the table variable.

THEN... using ROW_NUMBER() function, partition by the 4th element, and order by the 4th & 5th element... what you should get then is a result that looks like this: (you may have to -1 the ROW_NUMBER to start with a 0)

0 100 0
1 100 1
2 100 3
3 100 4

you can dump those results into a temp table as well, or use it as an inner select...


Blah! never mind... I just realized that's not going to work either... I was thinking that you could then filter out where the ROW_NUMBER field doesn't match the 5th element... but then realized as I was looking at it, it's going to start returning rows as soon as there's a mis-match...

The only other thing I can think of is to create a table of sequential numbers... join to it, or may have to apply a full outer join to it... and then report back the holes...

-tg

[Techno]

Sure, but dont want to use SQL here. (long story - not my request).

we only have 1 table with 2 fields. one holds the full version, the other field is createdAt.

so I pull all the records here and then I need to do the logic/checking against the list<string>

[techgnome]

oh... a non-sql solution? pffft! easy....
let me see if I can whip up some code for you....

-tg

[Techno]

lol. thanks. i know it may look simple but it probably isnt

but then I am always made to feel stupid where I am at.... *sigh*.

should be something like, does a split string on the hyphen (-)
and check to see if the previous version + 1 is the current version but before the next version... or something like that

[techgnome]

See if this works for you... I added a button and a listbox to a form...

        private void button1_Click(object sender, EventArgs e)
        {
            List<string> myList = new List<string>();
            myList.Add("0.0.0.100-0");
            myList.Add("0.0.0.100-1");
            //myList.Add("0.0.0.100-2");
            myList.Add("0.0.0.100-3");
            myList.Add("0.0.0.101-0");
            myList.Add("0.0.0.102-1");
            myList.Add("0.0.0.103-0");

            string myPrefix = "";
            int counter = 0;
            foreach(string lstItem in myList) {
                if(lstItem.Split('-')[0] != myPrefix ) {
                    counter = 0; // reset the counter
                    myPrefix = lstItem.Split('-')[0];
                }
                if( Convert.ToInt32 ( lstItem.Split('-')[1] ) != counter) {
                    listBox1.Items.Add (string.Format("Missing: {0}-{1}", myPrefix,counter));
                }
                counter++;

            }
            
        }

In short it splits on the - and keeps track of when the left side changes... and resets a counter ... if the right side then doesn't match the counter, it's noted as missing... the code as is should return 2...
100-2 and 102-0

-tg

[Techno]

thanks! almost there but not quite

it does find the missing number but than when it finds the next correct seq, it still says that its missing. i.e:

versions.Add("0.0.0.101-0");
versions.Add("0.0.0.101-1");
versions.Add("0.0.0.101-3");
versions.Add("0.0.0.101-4");
versions.Add("0.0.0.101-5");
versions.Add("0.0.0.101-6");


it does say that -2 is missing, but then also goes on to say 4/5/6 is also missing

[techgnome]

well crumbs... I see why... but I'm not sure just how to fix it... hmmm... I'll have to spin this off into it's own thread and work on it in the back of my head...

-tg

[Techno]

thats cool. I found another way though. not that its any better or "that" different.

I know its probably a bit of an overkill but made a class which parses the string - I guess just for easier diagram/layout for them.

public sealed class DbVersioner
        {
            public string Version {get; private set;}
            public int CurrentSubVersion {get;private set;}
            public string FullVersion { get { return this.Version + "-" + CurrentSubVersion; } }
            public string Original { get; private set; }

            public DbVersioner(string ver)
            {
                if (String.IsNullOrEmpty(ver))
                {
                    throw new ArgumentNullException();
                }
                this.Original = ver;

                string[] split = ver.Split(new char[] { '-' }, StringSplitOptions.RemoveEmptyEntries);
                this.Version = split[0];

                if (split.Length == 2)
                {
                    int tmpSubVer = 0;
                    Int32.TryParse(split[1], out tmpSubVer);
                    this.CurrentSubVersion = tmpSubVer;
                }
            }
        }

// main

int nextVer = 0;
            int tmpSubVer;
            DbVersioner tmpDbCurrentVersion;
            DbVersioner tmpDbNextVersion;

            for (int counter = 0; counter < dbScriptVersions.Count; counter++)
            {
                tmpDbCurrentVersion = dbScriptVersions[counter];
                tmpSubVer = tmpDbCurrentVersion.CurrentSubVersion;

                if (tmpSubVer != nextVer) 
                {
                    throw new NotSupportedException();
                }

                if (counter < dbScriptVersions.Count - 1)
                {
                    tmpDbNextVersion = dbScriptVersions[counter + 1];
                }
                else
                {
                    tmpDbNextVersion = tmpDbCurrentVersion;
                }

                if (String.Equals(tmpDbCurrentVersion.Version, tmpDbNextVersion.Version, StringComparison.InvariantCultureIgnoreCase))
                {
                    nextVer++;
                }
                else
                {
                    nextVer = 0; 
                }
            }

[Techno]

ok so im almost done but running into a problem.

after doing a sort based on the Revision (yes, there has been further progress on this. Revision is just the: 0.0.0.xxx - the xxx), i am running into a problem on obtaining the very last/most recent item example:

0.0.0.200-0
0.0.0.200-1


I do the sort and FirstOrDefault() - it gives me 200-0, but I need 200-1.

any ideas how to get the last, correct one?

[techgnome]

try FindLast ... or FindLastIndex...

-tg

[Techno]

hmm still not sure it would work though.
ill try

[Milk]

Had to have a play, not sure if I understand the versioning properly

static void Test()
{
    var versionList = new List<string>(){ 
        "0.0.0.100-0",
        "0.0.0.102-1",
        "0.0.0.103-0",
        "0.0.0.103-0",//Dup
        "0.0.100.100-2",
        "0.0.0.103-2",
        "0.0.0.100-3",
        "0.0.0.101-0",
        "0.0.0.100-1",
        "100.100.100.100.7",
        "0.0.0.102-3",
        "0.0.100.100-3",
        "0.0.0.103-5",
        "0.0.0.103-6",
        "0.0.100.100-0",
        "0.0.100.101-1",
        "0.0.100.101-2",
    };
    List<string> missingVersions = GetMissingVersions(versionList);
 
    foreach (var v in missingVersions)
    {
        Console.WriteLine(v);
    }
    Console.ReadKey();
}
 
static List<string> GetMissingVersions(List<string> versionList)
{
    var missingList = new List<string>();
    var numbers = versionList
         .Select(n => GetVersionNumber(n))
         .OrderBy(n => n);
 
    long lastnum = 0; 
    foreach (var num in numbers)
    {
        if (num / 10 != lastnum / 10)//Different major, add any missing minors
        {
            for (long n = num - (num % 10); n < num; n++)
                missingList.Add(GetVersionText(n));
        }
        else if (num - lastnum != 1)//Missing or duplicate minor (duplicates ignored)
        {
            for (long n = lastnum + 1; n < num; n++)
                missingList.Add(GetVersionText(n));
        }
        lastnum = num;
    }
    return missingList;
}
 
static long GetVersionNumber(string versionText)
{
    //expects well formed version text ###.###.###.###-#
    var nums = versionText.Split('.', '-').Select(n => Int64.Parse(n)).ToArray();
    //Pottential index out of range! Pottential format exception!
    return 
        nums[0] * 10000000000 +
        nums[1] * 10000000 +
        nums[2] * 10000 +
        nums[3] * 10 +
        nums[4];
}
 
static string GetVersionText(long versionNumber)
{
    long n0 = (versionNumber / 10000000000);
    long n1 = (versionNumber / 10000000) % 1000;
    long n2 = (versionNumber / 10000) % 1000;
    long n3 = (versionNumber / 10) % 1000;
    long n4 = versionNumber % 10;
    return string.Format("{0}.{1}.{2}.{3}-{4}", n0, n1, n2, n3, n4);
}

edit line 43 should read: for (long n = num - (num % 10); n < num; n++)