Gunnar Peipman's ASP.NET blog

Testing sorting algorithms

Some time ago I had to deal with sorting algorithms. Besides my main task I found a good way how to test custom sorting algorithms. This blog entry is one of early birds, more about sorting algorihtms is coming soon. Hopefully some time after TechEd 2007 for Developers. The procedure I wrote to test sorting algorithms is simple and works. Of course, I am always opened for better ideas if somebody wants to suggest some. Here's the little overview about what I've done.

Is array sorted?

At first, let's look at method that checks if array is sorted or not. To make things simpler I expect that all members in array implement IComparable interface. This expectation has very strong point: it is easy to compare objects of classes that have comparison operators defined but it is impossible to compare objects of classes that doesn't have those operators defined. To make my method as universal as possible I move comparison logic out of it.

About implementation. Don't look for any highly respected architectural decisions from this example. This is example about testing, not about nice and respected architecture. But here is my IsSorted() method.

The other point I found mentally interesting is question about empty array - is it sorted or not? :)

Testing IsSorted() method

As a next step let's write test for IsSorted() method. In this example I'm using Int32 as a type of arrays to test. Of course you can use any other types you need. To make our tests better we test IsSorted() method with array that contains some elements with same values. Then we can be sure that we can find also CompareTo() methods that make comparisons incorrectly somewhy. And one note - I'm using NUnit for tests.

I wrote to tests - one test for sorted array and the other for unsorted array. In this case we see behavior of IsSorted() for both cases that may occure. The tests are as follows.

Now we can be sure that isSorted() method will be tsted against sorted and unsorted arrays. Before we can test sorting algorithms we need to write some tests more.

Testing comparisons

Specially in the case of custom objects with comparers we need to test if comparers are working well. If they don't we may get wrong results from other tests. So let's test them now.

Now we can make sure comparisons are tested and if something went wrong our tests will tell us so.

Sorting algorithm

Now let's write sorting algorithm we want to test. I have many algorithms and I selected SelectionSort() for this example. Here's the code.

I wrote all my sorting algorithms using generics so I can use the same algorithms with differents types of objects.

Testing Sorting Algorihtm

Now let's write test for SelectionSort() algorithm using integers.

Now we have test for SelectionSort() that uses array of integers. Same way we can test also other sorting algorithms we want because IsSorted() method is not dependent of sorting algorithm we are testing. Also it has no strong dependence of types of objects we are testing because we require that all objects used here implement IComparable interface.

How to create grayscale images on .NET

In this example we will use simple color recalculation method to grayscale images. For each pixel on image we will calculate "average color" that we write back on image. Average color is sum of current color's red, green and blue channels integer value divided by three. This value is assigned to all three channels for current pixel.

Colored picture of rabbit commiting
the crime.

Although grayscaled she is still on action.

The cool thing about this rabbit is her colors - black, white and gray. As you can see rabbit colors are almost the same on both pictures. Okay, let's see the code.

Some notes about this code. It is also possible to calculate grayscale colors for channels differently. Instead of average of channels colors we can also use:

• maximum of channel values,
• minimum of channel values,
• custom divider.

It depends purely on context what one may need. Channel values maximum is good for pictures that are little bit too dark. Minimum is good for pictures that are little bit too bright. Custom divider may find usage in applications where user may want to change brightness manually. Current example by itself is goof for original pictures that are okay enough to publish them.

I know there are faster methods available for grayscaling. These methods are usually based on unmanaged code. This example here is slower but it is managed code you can use safely in your applications.

SQL-DMO and searching from meta-data

Lately I faced the need to search for specified strings in all stored procedures in given database. I found SQL-DMO library very useful for it. So, ten minutes later I had a simple form that fits my needs perfectly. And some minutes later I had there some more cool features. As a result I had form that enables me to search for strings from stored procedures, user defined functions and views. Also I was able to search strings from mentioned objects names. I tested it on a little bit larger MS SQL Server database, iterating approximately through 500 database objects and searching for given string and I mentioned no performance problems. So, here's the example.

Getting Started 

SQLDMO is provided with MSDE and MS SQL Server. SQLDMO stands for SQL Data Management Objects. It is library that enables you to access MS SQL Server
and MSDE meta data easily and write tools to manage database.

Form 

At first let's create a simple form. I made my project (long ago) on Visual Studio.Net.

<%@Page language="c#" Codebehind="Default.aspx.cs"
      AutoEventWireup="false" Inherits="DbTools.Default" %>
<html>
<head>
    <title>Search for string in SP’s</title>
</head>

<body>
    <form id="Form1" method="post" runat="server">
        <h3>Search for string in all stored procedures</h3>
        <p>
            Text to search: <asp:TextBox id="txtSTR" runat="server" />
            <asp:Button id="btnGO" runat="server" Text="Search" />
        </p>
        <p>
            <asp:Label id="lblResults" runat="server"
            Font-Bold="True" >Results<asp:Label>
        </p>
        <p>
            <asp :Label id="lblNoResults" runat="server"/>
            <asp :DataGrid id="dbgSPS" runat="server" />
        </p>
    </form>
</body>
</html>

Code is simple and needs no additional comments here. Make sure you make reference to SQL-DMO library. Also don't forget to import SQ-LDMO in code-behind file. You will find all necessary comments in code below. Just add this code to code-behind file of the page you previously created.

private void Page_Load(object sender, System.EventArgs e)
{
    // Let's initialize controls
    this.lblNoResults.Visible = false;   
    this.lblResults.Visible = false;
    this.dbgSPS.Visible = false;

    // If not postback clear search box
    if(!this.IsPostBack)   
    {
        this.txtSTR.Text = "";
        return;
    }
}
private void btnGO_Click(object sender, System.EventArgs e)
{
    // No search string was given
    if(this.txtSTR.Text.Trim()=="")
    {
        this.lblNoResults.Visible = true;
        this.lblResults.Visible = true;
        this.lblNoResults.Text = "Sisesta otsitav täheühend!";
        return;
    }

    DataTable dt;
    DataRow dr;
    SQLServer2Class srv;
    _Database2 db;
    StoredProcedures sps;   
    UserDefinedFunctions fns;
    Views vws;


    // Initialize table for results
    dt = new DataTable();
    dt.Columns.Add(new DataColumn("Type"));
    dt.Columns.Add(new DataColumn("Name"));

    // Create connection and ask list of stored procedures
    srv = new SQLServer2Class();
    srv.Connect("(local)","myUserName","myPassword");
    db = (_Database2)srv.Databases.Item("myDatabase",null);
    sps = db.StoredProcedures;

    // Check the body of procedures and add procedures with match
    // to results table.
    foreach(StoredProcedure sp in sps)
        if(sp.Text.ToLower().IndexOf(this.txtSTR.Text.ToLower())>-1 ||
                sp.Name.ToLower().IndexOf(this.txtSTR.Text.ToLower())>-1)       
        {
            dr = dt.NewRow();
            dr["Type"] = "Stored procedure";
            dr["Name"] = sp.Name;
            dt.Rows.Add(dr);
        }

    // Check the body of functions and add functions with match
    // to results table
    fns = db.UserDefinedFunctions;
    foreach(UserDefinedFunction fn in fns)
        if(fn.Text.ToLower().IndexOf(this.txtSTR.Text.ToLower())>-1 ||
            fn.Name.ToLower().IndexOf(this.txtSTR.Text.ToLower())>-1)
        {
            dr = dt.NewRow();
            dr["Type"] = "Function";
            dr["Name"] = fn.Name;
            dt.Rows.Add(dr);
        }
    fns = null;

    // Check the body of views and add views with match
    // to results table
    vws = db.Views;
    foreach(View vw in vws)
        if(vw.Text.ToLower().IndexOf(this.txtSTR.Text.ToLOwer())>-1 ||
            vw.Name.ToLower().IndexOf(this.txtSTR.Text.ToLower())>-1)
        {
            dr = dt.NewRow();
            dr["Type"] = "View";
            dr["Name"] = vw.Name;
            dt.Rows.Add(dr);
        }
    vws = null;

    // Kill objects
    sps = null;
    db = null;
    srv.DisConnect();
    srv = null;
    this.lblResults.Visible = true;

    // No results
    if(dt.Rows.Count==0)   
    {
        this.lblNoResults.Text = "No results";
        this.lblNoResults.Visible = true;
        return;
    }

    // Show results
    this.lblNoResults.Text = "Results";
    dt.DefaultView.Sort = "Name";
    this.dbgSPS.DataSource = dt;
    this.dbgSPS.DataBind();
    this.dbgSPS.Visible = true;
    dt.Dispose();
}

Although solution isn't maybe so well as you expected but it works fine. I have mentioned no performance issues this far using this code. But if you know better solution to this problem, please drop me a note here.

MoreDefensiveDatasource

At the end of the previous month I wrote a posting on DefensiveDatasource class that can be used to associate ASP.NET's GridView with collections containing objects of different types and based on one and the same base class. Dividing data into pages in GridView does, however, not succeed. An error message "The data source does not support server-side data paging" is displayed.

There is a simple solution to this problem. We have to create a new class conforming to the ICollection interface based on DefensiveDatasource. As we need to deal with DefensiveDatasource only in case of collections of the IList type, I restricted the collection selection of the new class so that only IList based collections can be submitted to the class as initial collections.

For more extensive collection support I recommend using the ICollection interface as a restriction.

Creating simple tasks calendar for SharePoint sidebar

I needed view of SharePoint calendar where I can see not accomplished activities from beginning of calendar until tomorrow. If you ask me why I needed something like this, there is a simple answer: this calendar contains almost everything that is going on (mainly different milestones and deadlines). As it is common calendar and everybody wants to see everything then there is no need for personalized filter. And there was one more requirement - there must be support for states of tasks describing if event is planned, done or canceled, so we can show in sidebar calendar only the planned tasks or events.

Here is my solution to this problem.

1. Create new calendar if you don't have one.
2. Add new column called Begin Date.
3. Follow the instructions given in my previous post Filtering SharePoint calendar by Start Time.
4. Add new column called Status.
5. Status must be required field and let's say it may have values Planned, Done and Canceled. Planned is default value.

Now the calendar list is okay and we can go further and create a web part that is showing tasks the way we want.

1. Go to page you want to put your tasks calendar and open it in edit mode.
2. Add your calendar to right side of page and open it in modifying mode.
3. Go to views list and click on Edit the current view.
4. Web part view is opened and now you can customize the view.

All we need to do is to add some filter conditions and - of course - sort order of the list. Let's start with sort order. To see problematic tasks (the tasks from previous days) on top of list and newer ones after these, we have to sort the list by Begin Date to ascending order. As our list may be pretty long we want to show there only tasks that are started in the past or that take place today or tomorrow, we need one filter based on Begin Date. To make sure we have only planned tasks visible in our list, we need one filter more - for Status.

1. Sort your list by Begin Date to ascending order.
2. Add filter condition where Status is equal to Planned.
3. Add filter condition where Begin Date is less that [Today]+2.

Save the list, web part and page and go to the page where your web part is. Now it should show only planned tasks for past, today and  tomorrow.

Filtering SharePoint calendar by Start Time

I had a problem when trying to filter WSS 3.0 calendar list by Start Time column. This column doesn't appear in filtered columns list somewhy. I found solution that smells like dirty hack to me, but at least it solved my problem. Oooh, this SharePoint is sometimes so kinky.... I'm almost sur ethere is better way to do that but if you are in hurry and need a working hack then here we go!

So, let's go step by step:

• Open Calendar list settings.
• Add new column called (by example) Begin.
• Choose "Calculated" as a type of new column.
• In the Formula field insert the following formula:
  =[Start Time]
• Select Date and Time as data type of new column.
• Clear check from "Add to default view" checkbox.
• Save the new column.

Now you should be able to use the column called Begin instead of Start Date when you need to filter calendar list.

DefensiveDatasource

We recently implemented some changes in the software development methodology used at Developers Team and quite by chance encountered an interesting .Net 2.0 problem. Namely, when an object array inherited from the same base class is cast on a base class and submitted to the data binder, the latter gets confused. The array contained objects from different classes but all these classes had one and the same base class.

After some investigation into the problem we realised the following sad fact. When data are bound to GridView, for example, then it is assumed that all objects have been created based on one and the same class. It means that in case of an array from an abstract class Animal, containing objects from classes Cat and Dog, we'll get an error. GridView takes the first object from the array, studies it and assumes all other objects in the array to be of the same type.

From the viewpoint of the object-oriented world this means we are in quite a mess. Until we are dealing with ADO.NET data objects, everything is fine. DataTable and DataView contain DataRow and DataRowView collections, respectively, and this means GridView always gets objects of the same type. When moving on to specific objects, however, GridView and also other controllers associated with data can no longer manage.

Still, we found a temporary solution to this problem. Namely Sean M. Foy has written a class named DefensiveDatasource that helps GridView and others with the same trouble to understand the aforementioned arrays and collections. Using DefensiveDatasource in code is not complicated.

I found also the following materials concerning the deeper nature and possible solutions of the problem:

• Really complex databinding: ITypedList with weakly typed collections (Frans Bouma)
• Polymorphic Databinding Solutions (Ayende Rahien)

.Net and Deep Copy

Some time ago I had to clone objects and .Net's shallow copy proved to be insufficient – it was necessary to use deep copy. No good tools are provided by .Net itself. If required, the object to be cloned must conform to the ICloneable interface and the Clone() method can be defined for the object. As the classes were not very numerous, but relatively bulky and complicated, there was no point in writing a Clone() method for all of them. I needed something else.

With the help of Google I found a very smart method for performing deep copy. Its performance may not be exceptional but it does its work nicely. The idea of the method is simple – first the object has to be serialised and then deserialised. Serialisation loses the relation between the specific instance of the object and the object data left to us. On deserialisation a new object identical to the old one is created based on these data, but now we are dealing with a different instance.

NB! This method can be used to deep copy only classes marked as serialisable. If there are problems with the events of the objects to be deserialised, you can find a solution from Rockford Lhotka's blog posting .NET 2.0 solution to serialization of objects that raise events. If the security level of the appropriate IIS application is not set to Full (internal), this method can generate errors in Windows Vista. If someone knows a solution to this problem, please don’t hesitate to inform me.

NB! PLEASE READ GREG'S COMMENT ABOUT THIS SOLUTION!!!

ASP.NET and Hierarchical Data

In addition to other new and interesting things ASP.NET also brought along controllers supporting representation of hierarchical data. This posting introduces IHierarchyData and IHierarchyEnumerable interfaces we can use to create wrappers for classes representing hierarchical data of the business logic layer.

Classes and interfaces supporting hierarchical data are located in the System.Web.UI namespace. There is nothing strange about this choice as these are tools directed to controls supporting hierarchical data. In principle they would not be right for the business logic layer as they are wrappers by their structure, not classes that should be extended by the classes of the business logic layer.

In some ways it is even good as one can hide pretty different hierarchy management mechanisms behind the wrappers. At that the controls supporting hierarchical data always retain the same interface they can use for binding data to them.

Getting Started

Let's use the IHierarchyData and IHierarchyEnumerable interfaces as an example. Let there be a class named Section in the business logic layer, representing for example the sections’ arrangement of a content management system. The sections can contain subsections and thus every section also has a parent section located one step higher from it. This does not apply to the first level sections as for them the parent section is zero. 

There is no point in documenting the class here separately as the inline documentation should be quite sufficient. As concerns the business logic layer, I'll leave the solution open because otherwise we would wander very far from the original subject.

IHierarchyData

Let's see the IHierarchyData interface first. It is a wrapper for hierachical data objects. This interface defines the following properties and methods.

• GetChildren() - returns a list of child objects of the current data object.
• GetParent() - returns the parent object of the current object.
• HasChildren - returns true if the current data object has child data objects.
• Item - returns the data object associated with the current object.
• Path - return the location path of the data object in the hierarchy.
• Type - the name of the object's type.

To make, for example, a TreeView control to understand the sections class as a hierarchical class, we have to create a class that conforms to the IHierarchyData interface. Let's name this class SectionData.

Let's provide the created SectionData object with a Section object the SectionData object uses to respond to the controller using it.

IHierchicalEnumerable

Data sources are collections of data objects. Therefore we also need one interface for hierarchical collections. For this the System.Web.UI namesapce offers the IHierarchicalEnumerable interface. This adds two methods to the collection.

• GetHierarchyData() - returns the wrapper matching the current data object, conforming to the IHierarchyData interface.
• GetEnumerator() - returns the enumerator to be used for cycling the elements of the collection.

Thus, now we have to create a collection conforming to the IHierarchicalEnumerable interface for our sections. To avoid copying the initial collection we should create a wrapper and provide the initial collection to it as an argument.

Now we have everything needed to bind the sections to some hierarchical control automatically. This example deals with the TreeView control.

Binding Data to TreeView

Let's try to bind the data to the TreeView control. For this we need one web form. The TreeView has to be dragged to this form. Let's add the following block to the control's definition.

    <DataBindings>
    <asp:TreeNodeBinding TextField="Title" ValueField="Id" />
    </DataBindings>

In case of the GET call the data are bound to the control on loading the control and in case of the POST call when it is requested by the control that caused the posting.

In this code SectionManager is the management class of the sections and the ListFirstLevel() returns a list of all the first level sections. When associated with data, the TreeView control named trvSections located on the form nicely displays the section hierarcy.

To comment this, I would like to add that we do not deal with creating the Section class and assigning values to its attributes here, as a whole separate article could be written on this subject.

Summary

To sum it up we can say it is not hard to build hierarchical data support for ASP.NET 2.0 controls. It is possible to create wrapper classes with the help of interfaces provided by the System.Web.UI namespace, that can be used for building a varied hierarchy support.