14
\$\begingroup\$

I have a list of strings where I want to find the index of a first- and second-choice video compressor.

Logic: If the first choice is available, return its index. If not, and the second choice is available, return its index. If not, return zero.

Here is what I have now:

List<string> availableVideoCompressors = GetAvailableVideoCompressors();
int compressorIndexToUse = 0;
if (availableVideoCompressors.Any(c => c.StartsWith("ffdshow", StringComparison.OrdinalIgnoreCase)))
    compressorIndexToUse = availableVideoCompressors.Select((c, i) => new { c, i }).First(c => c.c.Equals("ffdshow", StringComparison.OrdinalIgnoreCase)).i;
else if (availableVideoCompressors.Any(c => c.StartsWith("Microsoft Video 1", StringComparison.OrdinalIgnoreCase)))
    compressorIndexToUse = availableVideoCompressors.Select((c, i) => new {c, i}).First(c => c.c.StartsWith("Microsoft Video 1", StringComparison.OrdinalIgnoreCase)).i;
return compressorIndexToUse;

The problem is that I am iterating the list several times. Once to determine if the desired compressor is available, then again to obtain its index, for each candidate compressor.

I am not sure how to refactor to avoid this repetition. What can I do instead?

\$\endgroup\$
5
\$\begingroup\$

If you already have the list of compressors, I would do the following:

var index = availableVideoCompressors.FindIndex(c => c.StartsWith("ffdshow", StringComparison.OrdinalIgnoreCase));
if (index == -1)
    index = availableVideoCompressors.FindIndex(c => c.StartsWith("Microsoft Video 1", StringComparison.OrdinalIgnoreCase));
if (index == -1)
    return 0;
return index;
\$\endgroup\$
  • \$\begingroup\$ This is effectively what I went with because I feel it was the clearest to read, but also only iterated the list (at most) once for each choice. \$\endgroup\$ – JYelton Dec 12 '14 at 17:43
5
\$\begingroup\$

Let's start with a simpler problem where there's just one choice:

for (var i = 0; i < compressors.Count; i++)
{
    if (compressors[i].StartsWith(firstChoice, StringComparison.OrdinalIgnoreCase))
    {
        return i;
    }
}

return 0;

(I would much prefer returning -1 if no match is found, but requirements are requirements.)

Now we can build on top of this to deal with the second preference:

var secondChoiceIndex = -1;
for (var i = 0; i < compressors.Count; i++)
{
    if (compressors[i].StartsWith(firstChoice, StringComparison.OrdinalIgnoreCase))
    {
        return i;
    }

    if (secondChoiceIndex == -1 && compressors[i].StartsWith(secondChoice, StringComparison.OrdinalIgnoreCase))
    {
        secondChoiceIndex = i;
    }
}

return secondChoiceIndex == -1 ? 0 : secondChoiceIndex;
\$\endgroup\$
  • \$\begingroup\$ You could make secondChoice an int? loaded with null at start, and then at the end return secondChoice ?? 0. \$\endgroup\$ – ANeves Dec 12 '14 at 13:08
4
\$\begingroup\$

You could reduce it to only up to two iterations by changing .First() to .FirstOrDefault() and removing the ifs.

private static int GetDesiredIndex(List<string> availableVideoCompressors)
{
    var namesWithIndexes = availableVideoCompressors
        .Select((compressor, index) => new { Name = compressor, Index = index })
        .ToList();
    var ffdshow = namesWithIndexes
        .FirstOrDefault(c => c.Name.Equals("ffdshow", StringComparison.OrdinalIgnoreCase));
    if (ffdshow != null)
        return ffdshow.Index;
    var msVideo1 = namesWithIndexes
            .FirstOrDefault(c => c.Name.StartsWith("Microsoft Video 1", StringComparison.OrdinalIgnoreCase));
    if (msVideo1 != null)
    {
        return msVideo1.Index;
    }
    return 0;
}
\$\endgroup\$
3
\$\begingroup\$

Because your logic goes a little beyond a simple search you have to write your own method in order to avoid multiple enumerations. Unless your list is huge (10K+ elements), or you're regenerating your list every enumeration, it probably won't make much performance difference.

int FindWithFallback(IEnumerable<string> enumerable, string primary, string secondary)
{
    bool foundPrimary = false;
    bool foundSecondary = false;
    int primaryIndex = -1;
    int secondaryIndex = 0;
    foreach(var c in enumerable) 
    {
        ++primaryIndex;
        if (c.StartsWith(primary, StringComparison.OrdinalIgnoreCase)) 
        {
            foundPrimary = true;
            break;
        }
        else if (!foundSecondary && c.StartsWith(secondary, StringComparison.OrdinalIgnoreCase)) 
        {
            foundSecondary = true;
            secondaryIndex = primaryIndex;
        }
    }

    if (foundPrimary) 
    {
        return primaryIndex;
    }
    else if (foundSecondary) 
    {
        return secondaryIndex;
    }
    else
    {
        return 0;
    }
}
\$\endgroup\$
3
\$\begingroup\$

Now I'm getting ridiculous, but since this was tagged Linq:

private int choiceVideoCompressor(List<string> l)
{
    return l.IndexOf(
           l.Where(c => c.StartsWith("ffdshow", StringComparison.OrdinalIgnoreCase))
           .Concat(l.Where(c => c.StartsWith("Microsoft Video 1", StringComparison.OrdinalIgnoreCase)))
           .Concat(l).First());
}

This only iterate over the list until one element is found. Thus if the list contains "ffdshow", it will only loops once!

That is some nice lazy evaluation :)

I did have to cheat and get the index of the element with IndexOf(), meaning the list is iterated one time extra up until the element is found again.

You can get around that with this trick:

private int choiceVideoCompressor2(List<string> l)
{
   var l1 = l.Select((element, index) => new { e = element, i = index });
   return l1.Where(c => c.e.StartsWith("ffdshow", StringComparison.OrdinalIgnoreCase))
            .Concat(l1.Where(c =>c.e.StartsWith("Microsoft Video 1", StringComparison.OrdinalIgnoreCase)))
            .Concat(l1)
            .First().i;
}

This also does not actually loops over the code more than needed. Even l1 is only evaluated up to the first element if the list start with "ffdshow".

Edit: Improved version based on comments:

    private int choiceVideoCompressor(IEnumerable<string> l, IEnumerable<string> fallbacks)
    {
        var l1 = l.Select((element, index) =>  new { e = element, i = index });
        var l2 = l1.Take(0);
        foreach (string s in fallbacks)) {
            l2 = l2.Concat(l1.Where(c => c.e.StartsWith(s, StringComparison.OrdinalIgnoreCase)));
        }
        return l2.Concat( new[] {new { e = "", i = 0 }}).First().i;
    }

This handels N fallbacks and wont throw a InvalidOperationException when the list is empty.

\$\endgroup\$
  • \$\begingroup\$ This is very clever. I like how you get around the ordering issue by using consecutive concats. The only problem with your solution is that it fails on an empty source, but that's pretty easy to fix. Also, your method could take an IEnumerable instead of List. Thumbs Up for a really good idea. Do you think it could be possible to extend this to n fallback values instead of keeping it to 2? \$\endgroup\$ – Etienne Maheu Dec 16 '14 at 14:15
  • 1
    \$\begingroup\$ A empty list completely slipped my mind. I'm not even sure how to handle that: You could return 0 here but down the road somewhere you will need to select a decoder before you can display a video. Then again, a InvalidOperationException is probably not expected here no. As for n fall-backs: I'll edit you a nice one. \$\endgroup\$ – Dorus Dec 16 '14 at 14:56
2
\$\begingroup\$

Basically, what you are trying to accomplish can easily be done through the use of the Aggregate method but I would stay away from it for performance reasons. You cannot early return from an Aggregate process so you would have to continue looping for all items in the list even though you found a valid result.

I would instead use a variant of the TakeWhile method to scan through the list until the interesting element is found. The issue with TakeWhile is that it tests for the predicate before returning the value. This causes the returned index to always be one iteration off. This is where the TakeUntil method comes into play. Basically, where TakeWhile acts like a while loop, TakeUntil acts like a do while loop.

This method tracks two values, the final index to return and a score of the best value found so far.

public static IEnumerable<T> TakeUntil<T>(this IEnumerable<T> source, Func<T, bool> predicate)
{
    foreach (var item in source)
    {
        yield return item;
        if (predicate(item))
        {
            yield break;
        }
    }
}

public static int FindIndex<T>(this IEnumerable<T> source, params T[] firstOf) {
    var bestScore = Int32.MaxValue;
    var foundIndex = 0;

    return source.Select((v, i) =>
    {
        var currentScore = Array.IndexOf(firstOf, v);

        // Found a match so update the score and save the current index;
        if (currentScore != -1 && currentScore < bestScore)
        {
            bestScore = currentScore;
            foundIndex = i;
        }

        return foundIndex;
    })
    // Found the best possible match so return early.
    .TakeUntil(_ => bestScore == 0)
    .Last();
}
\$\endgroup\$
  • \$\begingroup\$ Also, as a bonus, my solution supports an unlimited amount of fallbacks. The closer to the beginning of the list, the better they are. It could be multi threaded easily through the use of concurrent bags. If you need to customize how elements are compared, you can implement IEquatable on T. And it comes as a handy extension method. \$\endgroup\$ – Etienne Maheu Dec 12 '14 at 4:33
  • \$\begingroup\$ Extreme overkill. But interesting to read, regardless. \$\endgroup\$ – ANeves Dec 12 '14 at 13:10
  • \$\begingroup\$ I fail to see how it is overkill. It is, with your solution, the only solutions that uses linq in their answer which I considered a requirement according to question's tags. It is also the only solution that does it in a single pass which was, in a way, a requirement too. \$\endgroup\$ – Etienne Maheu Dec 12 '14 at 13:23
  • 1
    \$\begingroup\$ I find it overkill because it seems more complex and convoluted than it needs to be. For example, I am not sure whether it will select (1,2,3) or (3,3,3), and I am not sure that it works without running it. The solution being so much more complicated than the requirement indicates, to me, that it can be improved. It's just an opinion. \$\endgroup\$ – ANeves Dec 12 '14 at 13:34
  • \$\begingroup\$ After a little bit of testing, I updated the whole thing. Unfortunately, it requires a custom extension method to work, which is sad, but it is at least reusuable. It also feels a lot less convulated now. As for what it select, it is actually neither. It always select the best possible match so far, so it would be (0, 0, 2, 2, 4, 5) with values of (5, 4, 2). \$\endgroup\$ – Etienne Maheu Dec 12 '14 at 14:30
2
\$\begingroup\$

Well, just store the found index in a variabel. FindIndex is your friend here, but it returns -1 when no match is found. This is preferred normally so you can see the difference between a match on the first element and no match.

    private int choiceVideoCompressor(List<string> l)
    {
        int index = l.FindIndex(c => c.StartsWith("ffdshow", StringComparison.OrdinalIgnoreCase));
        return index != -1 ? index :l.FindIndex(c => c.StartsWith("Microsoft Video 1", StringComparison.OrdinalIgnoreCase));
   }

And, when you want to return 0 instead of -1 when no default is found:

    private int choiceVideoCompressor(List<string> l)
    {
        int index = l.FindIndex(c => c.StartsWith("ffdshow", StringComparison.OrdinalIgnoreCase));
        index = index != -1 ? index : l.FindIndex(c => c.StartsWith("Microsoft Video 1", StringComparison.OrdinalIgnoreCase));
        return index != -1 ? index : 0;
    }

You can call this function with

    choiceVideoCompressor(GetAvailableVideoCompressors());
\$\endgroup\$
  • \$\begingroup\$ I would prefer to remove the ternary and use if(index >= 0) { return index; } return list.FindIndex(...);. IMO simpler is better. \$\endgroup\$ – ANeves Dec 12 '14 at 16:48
  • \$\begingroup\$ Yeah you can always replace the ternary if you absolutely want to avoid it. You can also use return Math.max(index, 0) on the last line if you think that's more clear. Still, i deemed this case simple enough to allow a ternary over adding 4 lines for a if statement and multiple exit points. \$\endgroup\$ – Dorus Dec 12 '14 at 17:56
2
\$\begingroup\$

You can use Find method with custom search delegate inside:

string compressor = availableVideoCompressors.Find(delegate(string rec){ 
    return (rec.StartsWith("ffdshow") || rec.StartsWith("Microsoft Video 1"));
});

return compressor;

http://msdn.microsoft.com/en-us/library/x0b5b5bc(v=vs.110).aspx

UPDATE: I missed a requirement that first choice match should have priority over the other. It has been answered in other answers already, but for the sake of correctness of the code, here is the updated version:

int index = availableVideoCompressors.FindIndex(delegate(string rec){ 
    return (rec.StartsWith("ffdshow"));
});

if (index < 0) {
    index = availableVideoCompressors.FindIndex(delegate(string rec){ 
        return rec.StartsWith("Microsoft Video 1");
});

return index;
\$\endgroup\$
  • \$\begingroup\$ This returns a string when I actually need the index, but I think this may be the right direction. \$\endgroup\$ – JYelton Dec 11 '14 at 21:52
  • \$\begingroup\$ There is similar FindIndex method if you do need an index. I thought you only need an index to get an actual string. \$\endgroup\$ – sha Dec 11 '14 at 21:54
  • 2
    \$\begingroup\$ If the second preference appears before the first in availableVideoCompressors, this code will return the second preference. \$\endgroup\$ – mjolka Dec 11 '14 at 22:31
  • \$\begingroup\$ @mjolka: Good catch! Thank you. I didn't realize this requirement. \$\endgroup\$ – sha Dec 11 '14 at 22:37
  • \$\begingroup\$ Isn't this a more elaborate way of writing return availableVideoCompressors.Find(x => x.StartsWith("ffdshow") || x.StartsWith("Microsoft Video 1"));? \$\endgroup\$ – Jeroen Vannevel Dec 12 '14 at 0:18
0
\$\begingroup\$

I have two ideas. The first assumes you have no control over the order of availableVideoCompressors and the second assumes you do.

You could store the video compressors you want in the order you want them in a separate List. Adding one to the list is a simple matter of adding one to the prefs variable.

List<string> availableVideoCompressors = new List<string>() { "a", "b" };
List<string> prefs = new List<string>() { "b", "a" };
int index = -1;

foreach (string x in prefs)
{
    index = availableVideoCompressors.FindIndex(x);

    if (index > -1)
        return index;
}

return 0;

If you have control over the creation of the availableVideoCompressors then you could add items to the list in the order you would want them, and then the code below would follow the original spec:

var index = availableVideoCompressors
    .FindIndex(c => c.StartsWith("ffdshow", StringComparison.OrdinalIgnoreCase)
                 || c.StartsWith("Microsoft Video 1", StringComparison.OrdinalIgnoreCase));

return index == -1
    ? 0
    : index;
\$\endgroup\$
  • 2
    \$\begingroup\$ This might return "Microsoft Video 1" index while "ffdshow" is listed lower, but it should only give the the second option if the first one is unavailable as per spec. \$\endgroup\$ – Dorus Dec 12 '14 at 21:57
  • \$\begingroup\$ @Dorus: That's exactly how this will work, hence the || operator. \$\endgroup\$ – Greg Burghardt Dec 12 '14 at 22:03
  • 1
    \$\begingroup\$ Logic: If the first choice is available, return its index. If not, and the second choice is available, return its index. If not, return zero. \$\endgroup\$ – Dorus Dec 12 '14 at 22:07
  • 1
    \$\begingroup\$ If the list contains { "Microsoft Video 1", "ffdshow" }, it will return "Microsoft Video 1", but it should be returning "ffdshow". \$\endgroup\$ – Dorus Dec 14 '14 at 12:01
  • 2
    \$\begingroup\$ I changed my answer so it implements the OP's original spec. Sorry for the confusion. \$\endgroup\$ – Greg Burghardt Dec 15 '14 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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