Kev's Big Log - Generic Search Predicates

Generic Search Predicates - Predicate<T> match

The MSDN docs don't really do Generic Search Predicate delegates justice and I think they're an often overlooked and underused tool in your utility belt. A typical example in MSDN shows something like -

   1: using System;

   2: using System.Collections.Generic;

   3: class Example

   4: {

   5:     static void Main()

   6:     {

   7:         List<string> dinosaurs = new List<string>();

   8:         dinosaurs.Add("Tyrannosaurus");

   9:         dinosaurs.Add("Amargasaurus");

  10:         dinosaurs.Add("Mamenchisaurus");

  11:         dinosaurs.Add("Deinonychus");

  12:         dinosaurs.Add("Compsognathus");

13:

  14:         // Find first dino ending with 'saurus'

  15:         Console.WriteLine("First dino ending with 'saurus': {0}", dinosaurs.Find(EndsWithSaurus));

16:

  17:         // Find last dino ending with 'saurus'

  18:         Console.WriteLine("Last dino ending with 'saurus': {0}", dinosaurs.FindLast(EndsWithSaurus));

19:

  20:         // Get list of dino's ending with 'saurus'

  21:         List<string> dinos = dinosaurs.FindAll(EndsWithSaurus);

  22:         Console.WriteLine("All dino's ending with 'saurus':");

  23:         foreach(string dino in dinos)

  24:         {

  25:             Console.WriteLine(dino);

  26:         }

  27:     }

28:

  29:     private static bool EndsWithSaurus(string dinosaur)

  30:     {

  31:         return dinosaur.EndsWith("saurus");

  32:     }

  33: }

Without re-hashing the docs, the generic collection classes typically implement the following methods (and others):

<T> Find( Predicate<T> match )
List<T> FindAll( Predicate<T> match )
int FindIndex( Predicate<T> match )

...and so on. When these methods are executed, behind the scenes the generic collection is iterated over and for each element the EndsWithSaurus method is called whilst passing the the current element. If you disassemble each of the above methods in List<T> in mscorlib.dll this is what we see:

   1: public T Find(Predicate<T> match)

   2: {

   3:     if (match == null)

   4:     {

   5:         ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);

   6:     }

   7:     for (int i = 0; i < this._size; i++)

   8:     {

   9:         if (match(this._items[i]))

  10:         {

  11:             return this._items[i];

  12:         }

  13:     }

  14:     return default(T);

  15: }

   1: public List<T> FindAll(Predicate<T> match)

   2: {

   3:     if (match == null)

   4:     {

   5:         ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);

   6:     }

   7:     List<T> list = new List<T>();

   8:     for (int i = 0; i < this._size; i++)

   9:     {

  10:         if (match(this._items[i]))

  11:         {

  12:             list.Add(this._items[i]);

  13:         }

  14:     }

  15:     return list;

  16: }

   1: public int FindIndex(Predicate<T> match)

   2: {

   3:     return this.FindIndex(0, this._size, match);

   4: }

   5: public int FindIndex(int startIndex, int count, Predicate<T> match)

   6: {

   7:     if (startIndex > this._size)

   8:     {

   9:         ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);

  10:     }

  11:     if ((count < 0) || (startIndex > (this._size - count)))

  12:     {

  13:         ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);

  14:     }

  15:     if (match == null)

  16:     {

  17:         ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);

  18:     }

  19:     int num = startIndex + count;

  20:     for (int i = startIndex; i < num; i++)

  21:     {

  22:         if (match(this._items[i]))

  23:         {

  24:             return i;

  25:         }

  26:     }

  27:     return -1;

  28: }

Predicate<T> match is a delegate that you the developer write to define the elements you wish to match. In the code example above, the line:

  21:         List<string> dinos = dinosaurs.FindAll(EndsWithSaurus);

is simply syntactic sugar. We could actually rewrite this as -

   1: List<String> dinos = dinosaurs.FindAll( delegate(string dinosaur) { return EndsWithSaurus(dinosaur); } );

2:

   3: Console.WriteLine("All dino's ending with 'saurus':");

   4: foreach (string dino in dinos)

   5: {

   6:     Console.WriteLine(dino);

   7: }

The C# compiler takes care of creating the predicate delegate for us. Now that we understand the mechanics, here's an example of using Predicate<T> delegates to parse some command line arguments. We have a simple console application that accepts one mandatory switch and some optional switches:

userinfo -user:<username> [[-setpassword:<password>] [-showinfo ] | -deleteuser]

The -user:<username> switch is mandatory. -setpassword and -showinfo can be used together but not if -deleteuser is present. The switches can be supplied in any order. Here's the sample, it's incomplete but you should get the idea:

   1: using System;

   2: using System.Collections.Generic;

3:

   4: class Program

   5: {

   6:     static int Main(string[] args)

   7:     {

   8:         if (args.Length == 0) return Usage(ErrorLevel.NoArgs);

9:

  10:         // Load args array into a generic list of strings

  11:         List<string> switches = new List<string>(args);

12:

  13:         // Asking for help?

  14:         if (switches.FindIndex(FindHelp) > 0) return Usage(ErrorLevel.DetailedHelp);

15:

  16:         string username;

  17:         ErrorLevel errorLevel;

  18:         if (!TryParseUsername(switches, out username, out errorLevel)) return Usage(errorLevel);

19:

20:

  21:         // Check that -deleteuser is not present with -setpassword and -showinfo

  22:         if (switches.Exists(FindDeleteSwitch) && (switches.Exists(FindSetPasswordSwitch) || switches.Exists(FindShowInfoSwitch)))

  23:         {

  24:             return Usage(ErrorLevel.DeleteSwitchIsExclusive);

  25:         }

26:

  27:         if(switches.Exists(FindDeleteSwitch))

  28:         {

  29:             // Delete user

  30:         }

  31:         else

  32:         {

  33:             if(switches.Exists(FindSetPasswordSwitch))

  34:             {

  35:                 // Set password

  36:             }

37:

  38:             if(switches.Exists(FindShowInfoSwitch))

  39:             {

  40:                 // Show info about user

  41:             }

  42:         }

43:

  44:         return (int)ErrorLevel.NoErrors;

  45:     }

46:

47:

  48:     private static bool FindHelp(string s)

  49:     {

  50:         s = s.Replace("/", "-");

  51:         return s.Equals("-help", StringComparison.InvariantCultureIgnoreCase) ||

  52:                 s.Equals("-?", StringComparison.InvariantCultureIgnoreCase);

  53:     }

54:

  55:     private static bool FindUserSwitch(string s)

  56:     {

  57:         s = s.Replace("/", "-");

  58:         return s.StartsWith("-user:", StringComparison.InvariantCultureIgnoreCase);

  59:     }

60:

  61:     private static bool FindDeleteSwitch(string s)

  62:     {

  63:         s = s.Replace("/", "-");

  64:         return s.Equals("-deleteuser", StringComparison.InvariantCultureIgnoreCase);

  65:     }

66:

  67:     private static bool FindSetPasswordSwitch(string s)

  68:     {

  69:         s = s.Replace("/", "-");

  70:         return s.StartsWith("-setpassword:", StringComparison.InvariantCultureIgnoreCase);

  71:     }

72:

  73:     private static bool FindShowInfoSwitch(string s)

  74:     {

  75:         s = s.Replace("/", "-");

  76:         return s.Equals("-showinfo", StringComparison.InvariantCultureIgnoreCase);

  77:     }

78:

  79:     private static bool TryParseUsername(List<string> switches, out string username, out ErrorLevel errorLevel)

  80:     {

  81:         // Simple example, we just want to find the -user switch

  82:         username = switches.Find(FindUserSwitch);

83:

  84:         // Returns null if no match

  85:         if (username == null)

  86:         {

  87:             errorLevel = ErrorLevel.UserSwitchMissing;

  88:             return false;

  89:         }

90:

  91:         // Check that we have a valid <username> part of -user:<username> switch

  92:         string[] temp = username.Split(':');

  93:         if (temp.Length != 2 || temp[1].Length == 0)

  94:         {

  95:             errorLevel = ErrorLevel.UsernameMissing;

  96:             return false;

  97:         }

98:

  99:         username = temp[1];

 100:         errorLevel = ErrorLevel.NoErrors;

 101:         return true;

 102:     }

 103:

 104:     private static int Usage(ErrorLevel errorLevel)

 105:     {

 106:         Console.WriteLine("Usage: useradmin -user:username [ [-setpassword:password] [-showinfo] | -deleteuser ]");

 107:

 108:         switch(errorLevel)

 109:         {

 110:             case ErrorLevel.UserSwitchMissing:

 111:                 Console.WriteLine("-user:<username> is mandatory.");

 112:                 break;

 113:

 114:             case ErrorLevel.UsernameMissing:

 115:                 Console.WriteLine("-user:<username>, <username> is missing.");

 116:                 break;

 117:

 118:             // Other error level messages

 119:             // ...

 120:

 121:             case ErrorLevel.DeleteSwitchIsExclusive:

 122:                 Console.WriteLine("-deleteuser is exclusive of -showinfo and -setpassword");

 123:                 break;

 124:

 125:             default:

 126:                 break;

 127:         }

 128:

 129:

 130:

 131:         if(errorLevel == ErrorLevel.DetailedHelp)

 132:         {

 133:             Console.WriteLine("Detailed help:...");

 134:         }

 135:         return (int)errorLevel;

 136:     }

 137:

 138:     public enum ErrorLevel

 139:     {

 140:         NoErrors,

 141:         NoArgs,

 142:         DetailedHelp,

 143:         UserSwitchMissing,

 144:         UsernameMissing,

 145:         DeleteSwitchIsExclusive

 146:         // Other error level values as necessary

 147:     }

 148: }

Tuesday, November 13, 2007 3:32:55 AM UTC