Generic Methods

A Generic Implementation of Counting Sort

Posted on Updated on

What is “Counting Sort”?

Counting Sort is a super fast sort algorithm that only works for certain types of data.

  • It is only useful if you have a relatively small range of values to sort
  • Even if there you have a large number of items to sort

For example, if you have a large list of “Person” objects, and each Person has an age between 1 and 100, then counting sort would be useful. Because what you are sorting on, age, has a relatively small range. The ages are repeated a lot, i.e. you will probably have a lot of Persons with age=18, a lot with age=65, etc.

For a counter example, assume each Person has a social security number; this would not be good use for Counting Sort, because there shouldn’t be any repeated SSNs.

Algorithm Speed

  • Counting Sort runs in O(n) (refer to Big O Notation for an explanation)
  • Which is superior to most other sorts, which run in O(n ∙ ln(n)) time

Counting Sort is only necessary in a special situations where you have need  maximum efficiency, typically big data sets or other situations where you sort a lot.

Concepts Covered in this Post

  • Counting Sort
  • Generic Methods
  • Extension Methods
  • C# delegates using ‘Func’ declaration

CountingSortScreenShot

First, The Code, Then The Explanation

using System;
using System.Collections.Generic;

namespace CountingSortExample {
  public static class CountingSortExt {
    public static IList<T> CountingSort<T>(this IList<T> sortMe,
                                           Func<T, int> sortProp) {
      List<int> buckets = new List<int>();
      for (int i = 0; i < sortMe.Count; i++) {
        int theVal = sortProp(sortMe[i]);

        //Increase the bucket size, if necessary
        for (int j = buckets.Count; j <= theVal; j++)
          buckets.Add(0);

        buckets[theVal]++;
      }

      int[] startIndex = new int[buckets.Count];
      for (int j = 1; j < startIndex.Length; j++) {
        startIndex[j] = buckets[j-1] + startIndex[j-1];
      }

      T[] result = new T[sortMe.Count];
      for (int i = 0; i < sortMe.Count; i++) {
        int theVal = sortProp(sortMe[i]);
        int destIndex = startIndex[theVal]++;
        result[destIndex] = sortMe[i];
      }

      return result;
    }
  }
}

Usage

List<Person> _PersonList;      //List populated elsewhere
//Now do the work:
IList<Person> sorted = _PersonList.CountingSort(p => p.Age);

Notes on Generic Aspects of My Implementation

  • public static class CountingSortExt  – This is an extension method, so it must be a static class
    • Using an extension method allows the syntax immediately above, i.e. _Personlist.CountingSort…
  • public static IList<T> CountingSort – Static again because it is an extension method
    • T is a placeholder for the class type being sorted
  • Func<T, int> sortProp – an anonymous function that allows the caller to specify the field used to perform the sort with
    • When you invoke it, it will look like this: p => p.Age
    • Which means “Use the age field for sorting”

Brief Discussion of the Algorithm

Counting Sort Diagram

Counting sort works by:

  1. Counting how many there are of each age. There is one person with age 7, seven persons with age 18, two persons with age 21 and five persons with age 65.
  2. We can use the counts to compute the destination index to move each person to
  3. For example, since there is only one seven-year-old, we know to move the first eighteen-year-old into slot 2.

Another Example

Because I implemented my method as a generic method, you can sort anything that has an int property, such as sorting a list of strings by length. You simply need to pass a lambda expression indicating the field/property to sort on, such as a string length property, as shown in the sample below:

List<string> stringList = new List { 
	"adsf",
	"adsfl;jkadsf",
	"qwerp9oui",
	"a",
	";ljsdfqweroiusd",
	"zcxv,mnzxcvnm,k"
};
IList<string> sortedString = stringList.CountingSort(w => w.Length);
foreach(string s in sortedString)
	Console.WriteLine(s);

Potential Modification

Note that my code works well when the field/property being sorted is close to 0. If that is not the case for you, you could replace my list ‘Buckets’ with a dictionary, or other type of hash list. Otherwise, if you have high values for the sorting field/property, you will allocate a large amount of memory for Buckets.

Download the Code

You can download my code from my DropBox account; they will ask you to set-up a free account for the privilege of downloading it.

Defensive Coding with Linq and Generic Methods

Posted on Updated on

Suppose you work with some off-shore programmers. Also suppose that those off-shore programmers write your BLL (Business Logic Layer) Code. Further, suppose those programmer constantly change your results without telling you. Finally, suppose they give you results in DataTable format, which is completely flexible and not strongly typed, thus making it hard to detect unannounced changes.

Given those assumptions, you’ve got a situation where they break your code all the time and  leave you to clean-up the mess. And that is the situation I will address in this post.

Not to slam off-shore programmers per se, but perhaps something about working in a different time zone, in a different culture, makes it more likely they will not understand your needs, even if those needs seem blindingly obvious to you! So, my attitude is, just do the best you can under the circumstances and hope the blame falls on the right shoulders. Defensive coding will help. Even if your teammates work in the cube next to you, that type of coding can help.

What You Will Learn

  1. How to use Linq (actually Lambda expressions) on DataTables to check for missing columns
  2. How to use Generic Methods to simplify your logic for extracting data out of a DataTable while checking for misnamed columns

Step One: Check if the Table Returned by the BLL Team has the Columns You Need

If the result set lacks columns we need, we need to log that problem. Also, we should try to work with the data we get and avoid completely crashing. Here is my short-and-sweet method to log missing columns and check how many desired data columns are present in the data we get from the BLL. Basically, I use the ‘Except’ method to compare one list (the expected columns list) against another list (the actual column list in the data table):

public int ColumnMatchCount(DataTable dtReturnTable,
                            List<string> expectedColumnNames,
                            string callingMethod)
{
    //Use the lambda expression 'Except' to determine which columns
    //are not present in the data table provided by BLL
    var unmatched = expectedColumnNames
        .Except(dtReturnTable.Columns.Cast<DataColumn>()
        .Select(c => c.ColumnName));
    foreach (string missingCol in unmatched) {
        //Log the problem column
        _Logger.Log(LogLevel.Error, callingMethod +
                    " - expected BLL to provide column '"
                    + missingCol
                    + "' in the ReturnTable, but it was not present.");
    }
    //Tell the caller how many columns match
    return expectedColumnNames.Count - unmatched.Count();
}

Key point: The data table has a columns collection we can compare using the Except method. Since DataTables are not quite the type of data that works with Linq, we use ‘Cast<DataColumn>() to make ti work. Because DataTables existed before Linq.

In my case, I will give my clients data if at all possible, i.e. if the BLL crew has given me at least one column that matches what they told me they would provide. I’ll provide some sample code shortly, but first, let’s look at my method to get the data out of the data table when the column I expect might not be there.

Step Two: Get Data from the DataTable  When a Column is Missing

If the BLL gave me the column I expected, no big deal (of course, I also want to handle possible null values). But, if the column I want is not even present, a default value should be used instead. The method below does that, and it works for any data type, whether string, int, DateTime, etc. Because it is written as a Generic Method, it can handle any data type you provide.

public T CopyValueFromTable<T>(DataRow dr, string columnName)
{
    T result = default(T);
    if (dr.Table.Columns.Contains(columnName) && ! dr.IsNull(columnName))
        result = (T)dr[columnName];
    return result;
}

The method takes a data row as input and examines that DataRow’s parent table.

    dr.Table

That table has a Columns collection, and we can check it to see if the column exists or not.

    if (dr.Table.Columns.Contains(columnName)

If the BLL crew remembered to give us the column we need, and it it is actually present and not null, then extract it.

dr[columnName]

If you understand Generic Methods, you will recognize that ‘T’ is the data type our caller wants us to use, so we convert the data column to type ‘T’. We cast it to type T using the parenthesis notation; remember that
‘T’ is a placeholder for any type, such as int, string, DateTime, etc.

    result = (T)dr[columnName];

The first line in my method ensures that an appropriate default value will be returned if no other choice is available, the ‘default’ method will give us an empty string, a zero, etc., depending on what type is represented by ‘T’:

    T result = default(T);

Putting it All Together

Screen shot shows my code handling unexpected missing column 'ServiceCenterID' and using a default value instead. The discrepancy was logged.
Screen shot shows my code handling unexpected missing column ‘ServiceCenterID’ and using a default value instead. The discrepancy was logged.
private void btnSimulateUnplanedChange_Click(object sender, RoutedEventArgs e) {
    BLL dataFetcher = new BLL();
    //Ask our simulated BLL to get some data, which will lack the column 'ServiceCenterID'
    DataTable ReturnTable = dataFetcher.UnannouncedChange_GetServiceCenters();
    List<string> expectedColumns = new List<string> { "Location", 
                                "LocationDescription", "ServiceCenter", "SCDescription" };
    List<InventoryResponse> response = new List<InventoryResponse>();


    //If at least one column name matckes, 
    if (ColumnMatchCount(ReturnTable, expectedColumns, "GetResults") > 1) {
        foreach (DataRow dr in ReturnTable.Rows) {
            InventoryResponse invResp = new InventoryResponse();
            invResp.ServiceCenterID = CopyValueFromTable<int>(dr, "ServiceCenterID");
            invResp.Location = CopyValueFromTable<string>(dr, "Location");
            invResp.SCDescription = CopyValueFromTable<string>(dr, "SCDescription");
            response.Add(invResp);
        }
        txtResults.Text = RjbUtilities.DebuggerUtil.ComplexObjectToString(response);
    } else {
        _Logger.Log(LogLevel.Error, "No column names match the expected values");
    }
}

Summary

Sometimes you can’t work with top-quality programmers and possibly they don’t understand the concept of their teammates depending on their code. If you can’t force them to grow-up and communicate, at least you can make sure your code logs the problem and does the best it can with what they give you.

I showed you one method ‘ColumnMatchCount’ that checks how many expected columns are present the results the BLL crew gives you. I showed you another method ‘CopyValueFromTable’ that will provide default values and avoid crashing if the BLL crew renamed a column without telling you.

If you write similar defensive code, you might be lucky and your managers will blame the appropriate people!

Download my sample code here.

Simplify Repeated Code with Delegates and Generic Methods

Posted on Updated on

Scenario: Repeated Code in All my Web Methods

  • I’m writing a bunch of WCF web methods
  • They all have chunks of nearly identical code
    • (For example: code for logging, authentication, validation, error handling, etc.)
  • But each method has a certain number of lines of code that are unique
  • The upshot is that every time I add a new web method, I add a huge amount of code that is the same as before
  • And every time we change our general procedure (i.e different logging, different validation, etc.), I need to modify that repeated code, a task that is error prone and boring

What You will Learn

If you read this post, you will see a practical sample of how to:

  • Use delegates to execute code that is unique for each of your individual web service methods
  • Use a generic method to handle process all your web methods, using any request or response data types
  • Use interfaces to add power to you generic methods!

See below for a simplified description of these powerful techniques. The code sample download link is at the end.

Important Principal: Do Not Repeat Yourself!

I have a deadline, and I would like to meet it by avoiding repeated code. I’ll bet you also have a deadline, and maybe you would like to keep your job by meeting that deadline!

Also, my client deserves easy-to-maintain code, so I will write my code to give them the power to easily make changes in one place and have it affect all my web methods. Testing is also easier when you avoid repeating yourself, because you have fewer lines to test.

What I’m talking about is the “best practice” called “DRY”, or Do not Repeat Yourself. In my experience, sophisticated/productive programmers all use DRY, whereas most corporate drones have no frigging clue. Which is why most of their code sucks, IMHO!

The “UniversalMessageProcessor” I describe in this post will show you how to avoid repeating yourself by using delegates, generic methods, and a few other things, thus helping you meet your deadline and give your clients the easy-to-maintain code they deserve.

Sample Code – Shows the Essence of my Repeated Code

Read my simplified sample immediately below to get an idea of the repeated code that I wish to improve a la DRY:

public ResponseType1 GetData1(RequestType1 request){
	try {
		//Simplified representation of the repeated authentication code
		//(Use your imagination to envision longer code)
		CheckAuthentication(request.Credentials);
                //Also repeated in every web method, yada yada yada
		ValidateRequest(request);
                //Another chunk of repeated code that is actually more like 15 lines:
		LogRequest(request);
		//Simplified representation of the lengthy code to copy the result from BLL into 
		//the response we send to service partner, again, imagine 30 lines instead of 2)
                bllResult = Bll.GetReponseType1(request);
		ReponseType1 myResponse = CopyBllResultToResponse(bllResult);
		LogResponse(myResponse);
		return myResponse
	} catch (Exception ex) {
		LogError(ex, request);
	}
}

In other words, I have a bunch of web methods that follow the simplified pattern above, except they use ‘ResponseType2’, ‘ResponseType3’, etc. Only the portion in yellow is unique to each web method; otherwise they are (mostly) similar. I would like to avoid all this repeated code! But first, let’s make sure we understand a couple of techniques I will use, delegates and generic methods:

Nutshell Definitions for ‘Delegate’ and ‘Generic Method’

Delegates: a Variable to Hold Your Code

In a nutshell, a delegate (sometimes called a function pointer) is how you represent your code as a variable (i.e. as a First Class Object) which you can pass to other methods. Like this (over simplified) sample:

Func<int, string> GetSign = (i) => {
	if (i < 0)
		return "-";
	else if (i > 0)
		return ("+");
	else
		return "";
};

//Usage:
string s1 = GetSign(5);
Console.WriteLine(s1);
//Output will be "+"

GetSign‘ is a delegate, and I can pass it to another method, because it is a variable. You may also see folks declare delegates using the ‘Action‘ keyword, instead of the ‘Func‘ keyword I used above.

For another example of passing delegates as parameters, take a look at how I used them to solve a puzzle: https://actualrandy.wordpress.com/2014/09/18/calculator-letters-puzzle-solved/

Generic Methods – Work on Any Data Type!

In another nutshell, a generic method is a method which does the same work regardless of parameter type. Here’s a quick sample from the MSDN site:

static void Swap<T>(ref T lhs, ref T rhs)
{
    T temp;
    temp = lhs;
    lhs = rhs;
    rhs = temp;
}
//Usage:
string s1 = "A", s2 = "B";
Swap<string>(s1, s2);
int i1 = 1, i2 = 2;
Swap<int>(i1, i2);

In this sample, ‘T‘ could be int, string, DateTime, or any other data type you need!

Enough Background, Here’s the Code!

The code for this post is available for download at the bottom of the article. I will discuss the important portions here. The download code has two web methods (but my production code has a lot more, I simplified my sample for your sake). Let’s look at my first web method, which returns a list of locations associated with the caller’s service center:

public GetLocationServiceCenterResponse GetLocationByServiceCenter(GetLocationServiceCenterRequest request) {
    //The delegate performs the work which only applies to this 
    //web method; the common work is performed by ProcessMessage
    Func<IRequestWithCredential, IReturnMessageResponse, BllResult> getBllResult = (req, response) => {
        //cast to the type we need:
        GetLocationServiceCenterRequest getLocRequest = (GetLocationServiceCenterRequest)req;

        //Invoke the Business-Logic-Layer method that does the database work:
        BllResult theBllResult = BllMain.GetLocationServiceCenter(getLocRequest);

        //Here we will copy the result from the ReturnTable into the response
        //Note that the ReturnTable is a weakly-typed DataTable that varies according to the method
        GetLocationServiceCenterResponse getLocResponse = (GetLocationServiceCenterResponse)response;
        getLocResponse.Locations = new List<LocationInfo>();
        if (theBllResult.ReturnCode == BllConstants.SUCCESS) {
            //Copy the weakly-typed data from the BllResult into our response:
            foreach (DataRow dr in theBllResult.ReturnTable.Rows) {
                LocationInfo curLoc = new LocationInfo();
                curLoc.Location = (string)dr["LocationID"];
                curLoc.Description = (string)dr["Description"];
                curLoc.LocationType = (string)dr["LocationType"];
                getLocResponse.Locations.Add(curLoc);
            }
        }

        return theBllResult;
    };
    //End of delegate body

    //Now, do all the work, using the delegate we built above:
    GetLocationServiceCenterResponse result = ProcessMessage<GetLocationServiceCenterRequest, GetLocationServiceCenterResponse>
                        (request, "getLocationServiceCenter", getBllResult);
    return result;
}

As you can see above, the main thing I do is declare my delegate, ‘getBllResult’, and then pass it to a medhod called ‘ProcessMessage’. The delegate begins in the highlighted code. Just to refresh your memory, this delegate handles the work that is unique to finding locations by service center.

Also, take a look at how I invoke ‘ProcessMessage’ – I tell it the input and output types (GetLocationServiceCenterRequest, GetLocationServiceCenterResponse) in between the angle brackets:

result = ProcessMessage<GetLocationServiceCenterRequest, GetLocationServiceCenterResponse> ...

If you download my code, you will see that I do almost the exact same thing with my second web method. The only difference is that my second method declares the delegate to handle different types of data. This means that all the web methods are greatly shortened, because all they do is define a delegate and call ProcessMessage!

Now Look at My ‘Universal’ ProcessMessage Method

The following is a simplified sample – I cut-out approximately 50 lines of logging/authentication, etc., just so you can read it easier!

public TResult ProcessMessage<TRequest, TResult>
1		(TRequest request, 
2		 string methodName, 
3		 Func<IRequestWithCredential, IReturnMessageResponse, BllResult> getBllResult
		)
4	where TResult : IReturnMessageResponse, new()
5	where TRequest : IRequestWithCredential 
{
6   TResult result = new TResult();
    _Logger.Log(LogLevel.Info, methodName + " started...");
    result.ReturnMessage.ReturnMessageDetails = new List<ReturnMessageDetail>();
    try {
        if (AuthenticateApp(request.credential)) {
            _Logger.Log(LogLevel.Info, methodName + " validating request");
            List<ValidationResult> lstValidationResults = new List<ValidationResult>();
            //The GeneralValidator uses reflection to validate any class and its child members
7           if (_Validator.ValidateComplexObject<TRequest>(request, lstValidationResults)) {
                //Execute the function passed to us
8               BllResult bllResult = getBllResult(request, result);

                if (bllResult != null && bllResult.ReturnCode == BllConstants.FAIL) {
                    result.ReturnMessage.ReturnCode = BllConstants.FAIL;
                    result.ReturnMessage.ReturnText = ERR_MESSAGE;
                } else if (bllResult != null) {
                    //We got the result we wanted, set the appropriate values in our result
                    result.ReturnMessage.ReturnCode = bllResult.ReturnCode;
                    result.ReturnMessage.ReturnText = bllResult.ErrorMessage;
                }
            } else {
                //Validation failed
                CopyValidationResultsToResponse(result, lstValidationResults);
                }
            }
        } else {
            //Invalid authentication
            result.ReturnMessage = new ReturnMessage{ ReturnCode = BllConstants.FAIL, 
                  ReturnText = "Your credentials suck --> no data for you, ya filthy hacker!"};
        }
    } catch (Exception ex) {
        while (ex != null) {
            result.ReturnMessage = new ReturnMessage{ ReturnText =  ex.Message };
            _Logger.Log(LogLevel.Error, ex.Message);
            ex = ex.InnerException;
        }
    }
9    return result;
}

 Explanation!

I injected some line numbers into my sample above, and they are linked to the numbered bullet points below:

  1. TRequest request – My method takes a generic input type ‘TRequest’, which could be, for example, ‘GetServiceCenterRequest’
  2. string methodName – The method uses your method name for logging
  3. Func<…, …, …> getBllResult – Third parameter is my delegate, which I will execute on line 8 (highlighted). Remember, the delegate is the code which is unique to each web method. Also remember, the point of using a delegate is that I can pass delegates like parameters!
  4. where TResult : IReturnMessageResponse, new() Generic methods allow you to use the ‘Where’ clause to restrict what types of data they will process. In this case, I require that the result/ouput type (‘TResult’) implement a simple interface called ‘IReturnMessageResponse’. That allows me to write code like this: ‘result.ReturnMessage = new ReturnMessage’, because the interface declares that every implementor has such an object. (Sample code below.)
    • new()” here, my ‘where-clause’ also requires that TRequest expose a constructor, which allows me to write the code on line 6
  5. where TRequest : IRequestWithCredential – Here, I require that the input paramter (‘TRequest’) implement a different interface, ‘IRequestWithCredential’. In a nutshell, every class that implements this interface has a Credential object.
  6. TResult result = new TResult() – because of my where-clause on line 4, the compiler knows my input parameter has a constructor it can call! Also, the class of my result is TResult, which can be any class, (subject to my where clause)
  7. ValidateComplexObject – Refer to my previous post on writing a universal validator using DataAnnotations and Reflection.
  8. BllResult bllResult = getBllResult(request, result) – here is where I invoke the delegate!. This is the whole point of my post, i.e. use the delegate inside a generic method to perform work that is unique to each web method. Note that my teammates wrote the BLL (Business Logic Layer) to always return a class called bllResult, each result has a table with different data).
  9. return result; – Since I declared this method to return TResult, my generic method will return whatever class type you need, such as a response object for GetLocationsByServiceCenter.

My Two Interfaces

OK, I promised above that I would list my interfaces, as you can see, they are really simple. Just to refresh your memory,

  • All my request classes implement IRequestWithCredential
  • And all my response classes implement IReturnMessageResponse
  • By doing so, the compiler is not confused when I execute code like ‘request.Credential = null’, or similar actions
  • I.e., any time I refer to something defined the the interface, the compiler is happy!
//First interface:
public interface IReturnMessageResponse
{
    ReturnMessage ReturnMessage { get; set; }
}

//Second interface
public interface IRequestWithCredential
{
    Credential credential { get; set; }
}

 Summary

  1. When you write your code, you should avoid repeating yourself, because it will help you meet your deadline and shrink your code.
  2. If you are writing a web interface, you can find lots of repeated code to optimize, depending on how much logging, authentication, validation, etc. you are required to do. (But the same principle applies to other code!)
  3. You can create a generic method that will work for any of your response classes and request classes, that is step one to saving a ton of code!
  4. Your generic method can accept a delegate input parameter; you method will execute that method to handle code that is unique to each web method.
  5. You can constrain your generic method using the ‘where-clause’; one use is that it tells the compiler that your types implement an interface

By applying these techniques, you should be able to reduce your web method code by 20%-50%, depending on how much repeated code you have. That’s a big savings, and should really speed things up.

Link download to the Code