Take a desired string, iterate through objects to see if it exists in a given field and append a number until a unique string is found

Question

I wanted to in the most generic way possible write a method in C# to achieve the following.

• Take in a string, a set of objects, and a function to access the field of a given object
• Look at all of the strings from the fields of these objects to match against provided string
• If provided string is not unique in a case insensitive manner, append _x to the end, where x is an incrementing integer until a unique string is found

With that in mind, I created this.

private string GetUniqueStringForModel<T>(string originalString, IEnumerable<T> enumerableObjects, Func<T, string> stringFieldFunction) where T : class
{
    var uniqueString = originalString;
    var duplicateCount = 1;

    while (enumerableObjects.Select(stringFieldFunction).ToList().Any(currentString => string.Equals(currentString, uniqueString, StringComparison.InvariantCultureIgnoreCase)))
    {
        uniqueString = originalString + "_" + duplicateCount++;
    }

    return uniqueString;
}

I would rather have not put the ToList() in but when working with Entity Framework it was complaining about doing the string comparison in LINQ (presumably because it couldn't compile it SQL).

Any thoughts or ideas for improvement?

Answer 1

There's certainly room for improvement.

1. Move that that Select(stringFieldFunction).ToList() out of the while loop. Iterating an IEnumerable might be quite expensive, and there's no need to repeat that work when you find a duplicate.
2. Select only those strings that have originalString as a prefix. That will reduce the amount of items you need to check against when adjusting the suffix.
3. Instead of making a list, turn those results into a (hash)set, for faster lookup.

Regarding EF complaining: apparently it doesn't support those StringComparsion overloads, so it'll have to fetch all rows from the database and run your Any predicate in memory, which may be slower as expected. Maybe an alternative approach like using ToUpperInvariant can be translated to SQL?

---

Applying the above changes will give you the following:

private string GetUniqueValue<T>(string value, IEnumerable<T> items, Func<T, string> getValue)
{
    var possibleDuplicates = items
        .Select(getValue)
        .Where(val => val.StartsWith(value, StringComparison.InvariantCultureIgnoreCase))
        .ToHashSet();

    var result = value;
    var suffix = 1;
    while (possibleDuplicates.Contains(result))
    {
        result = value + "_" + suffix;
        suffix += 1;
    }
    return result;
}

---

Addendum

As t3chb0t and ErikE already pointed out, if you want the benefits of Linq-to-SQL, then you need to use IQueryable<T>. Not only that, you also need to make sure that you're using the Queryable Linq extension methods, not the Enumerable variants.

The difference is that Enumerable methods have Func<> parameters, while the Queryable variants have Expression<Func<>> parameters. An Expression is a data structure that represents a piece of code, which makes translation to SQL possible. Because stringFieldFunction is a Func, not an Expression<Func>, the Enumerable.Select variant is used. That cannot be translated to SQL, so all data has to be loaded from the database before the Select (and any subsequent operation) can be performed on it.

To recap: use IQuerable<T>, make sure you're using Queryable Linq methods, and only use supported methods within your expressions.

Answer 2

It will be more efficient to call .ToList() just once:

// ...
var list = enumerableObjects.Select(stringFieldFunction).ToList();
while (list.Any(currentString => string.Equals(currentString, uniqueString, StringComparison.InvariantCultureIgnoreCase)))
{
    uniqueString = originalString + "_" + duplicateCount++;
}

Answer 3

private string GetUniqueStringForModel<T>(
    string originalString,
    IQueryable<T> databaseQueryable,
    Expression<Func<T, string>> stringFieldFunction
) where T : class {
    var lowerBound = originalString.ToLowerInvariant();
    var upperBound = originalString.ToUpperInvariant() + "z";
    var candidates = new HashSet<string>(
       databaseQueryable
          .Select(stringFieldFunction)
          .Where(field => field >= lowerBound && field < upperBound)
          .ToSet()
    );

    return Enumerable
       .Range(0, int.MaxValue)
       .Select(i => originalString + (i == 0 ? "" : $"_{i}"))
       .First(candidate => !candidates.Contains(candidate));
}

There are a few things going on here.

First, since you are using Entity Framework and received the error you did, I believe that your IEnumerable is actually an IQueryable. If you want to add predicates to the query that are performed on the database server, you need to maintain the IQueryable as that data type and not prematurely force it to become an IEnumerable. This is of crucial importance to understand and I encourage you to go study the difference between these and what effects it has. The exact same code is compiled completely differently when cast to an IQueryable instead of an IEnumerable—differently in a way necessary for being able to project your C# code to SQL for doing the majority of the work in the database.

Second, your Func can work, but it must contain only methods and operators that work with Entity Framework and must be an Expression<Func<>>. If you want to use a method that is not supported, that can only be done by, after whatever IQueryables have filtered it so far, materializing the result set in memory using .ToList() and then iterate over it locally (using a regular Func).

My goal in the above code was to fetch the set of values that could possibly match the originalString. Notice that by assigning the values to variables, this leaves the queryable's Where clause susceptible to being read by EF, because it will be compiled as an Expression instead of to byte code. (That is why you need IQueryable instead of IEnumerable). The trick I used to select the appropriate range may not be a good one (I haven’t touched C# for 16 months). Study the operators and your data and pick a better one. Find the greatest value that can be added (not "z") and add that.

Third, the very limited set of results is being converted to a Set so that we can get O(1) lookup time. I promise you that performing a ToList() on an IQueryable (masked as an IEnumerable) on each new number suffix attempt is a superbly wonderful way to destroy performance. Please don't do that. Your code as written will read every single row from the underlying IQueryable on every iteration of the while loop—hopefully there are some conditions on it and this isn’t the entire table!

Fourth, you have to pay attention to the string comparison in the database and for the HashSet. Do you want case sensitivity or case insensitivity? Is there another kind of collation that might be needed to perform foreign language support? You need to provide the HashSet a StringComparer that will perform properly.

Fifth, why even provide a stringFieldFunction when the caller can just do .Select(stringFieldFunction) itself? This doesn't seem useful to me. Don't add unnecessary parameters. Doing it in the caller will avoid having to muck about with Func vs. Expression<Func>.

Answer 4

ToUpper translates into SQL allowing you to avoid the StringComparison.InvariantCultureIgnoreCase.

In addition the IsNumeric function allows you to guard so that you can use parse the string to get the counter directly (In LinqtoEntities with a MSSQL backend .Cast() performs this function).

Finally when operating with queryables you need to use an Expression rather than a Func

This allows the following;

private string GetUniqueStringForModel<T>(
  string originalString, 
  IQueryable<T> enumerableObjects, 
  Expression<Func<T, string>> stringFieldFunction
) where T : class
{
IQueryable<String> enumerableStrings=Queryable.Select<T,string> 
(enumerableObjects,stringFieldFunction);

if(!enumerableObjects.Select(stringFieldFunction).Any(
x=>x.ToUpper()==originalString.ToUpper()))
return originalString;

originalString=originalString+"_";
var length=originalString.Length;

if(!enumerableStrings.Any(
x=>x.ToUpper().StartsWith(originalString.ToUpper())&&
System.Data.Objects.SqlClient.SqlFunctions.IsNumeric(
x.Substring(length)) == 1))
return originalString+"1";

var highest=
  enumerableStrings
  .Where(x=>(x.ToUpper().StartsWith(originalString.ToUpper())) &&
    System.Data.Objects.SqlClient.SqlFunctions.IsNumeric(
    x.Substring(length)) == 1)
  .Select(x=>x.Substring(length))
  .Cast<int>()
  .Max()+1;
return originalString+highest;
}

Not quite the same as your code, if you have "Foo", "Foo_1" and "Foo_5" your code will return "Foo_2" while the above should return "Foo_6", but it's only 3 db calls, and each only return a single row.