Leniel Macaferi's blog

Creating Excel spreadsheets .XLS and .XLSX in C#

2009-07-02T19:51:00.001-03:00

Recently I had to implement some code to create an Excel spreadsheet/report using C#.

The task was: given an Excel spreadsheet template - a .XLS file (with formulas, pivot tables, macros, etc) I had to fill some data in one of the sheets of the spreadsheet and send this modified spreadsheet back to the user requesting such an operation (Excel report).

The following attests the need for Excel nowadays:

Excel has long been recognized as the de facto standard when it comes to presenting management reports. The unique combination of great calculation engine, excellent charting facilities, pivot tables and the possibility to perform “what if” analysis, make it the “must have” business intelligence tool.
by John Tunnicliffe

I had a great time while studying the possible ways of doing what the task asks for.

It appears to be a simple task at first but as the time passes by you get to know that this is not the case, well, till the moment this blog post was written at least, I think. :-)

Firstly I tried automating Excel through COM automation, but as the application was meant to be used in a web context it is not recommended to use automation. Why? Because COM automation for Excel is not thread safe, that is, EXCEL.EXE was not constructed to be used by concurrent users accessing the same process, in this case EXCEL.EXE; besides, Microsoft Excel must be installed on the server what is not always possible.

For more details on why you shouldn’t use Excel on the server, read this article on Microsoft Help and Support site: Considerations for server-side Automation of Office. The key part is this:

Microsoft does not currently recommend, and does not support, Automation of Microsoft Office applications from any unattended, non-interactive client application or component (including ASP, ASP.NET, DCOM, and NT Services), because Office may exhibit unstable behavior and/or deadlock when Office is run in this environment.

I’ve just experienced the above. EXCEL.EXE insisted in being alive in task manager even after processing the data and being closed in code. Each call to process a spreadsheet opens an EXCEL.EXE process on the server. With such EXCEL.EXE processes don’t being closed as they should you get lots of those processes on memory which could overload the server.

Don not use COM automation if you’re developing server-side code.

After struggling with COM automation I finally got to know ExcelPackage which works with Office Open Document Format (OOXML). It can read an .XLSX (Microsoft Excel 2007) template and create another .XLSX file based on such template, giving you lots of possibilities to work with the template copy.

I’ve gotten really happy because I had found a way of doing what the task was asking for but with a minor detail: ExcelPackage works only with .XLSX file format letting the .XLS (Microsoft Excel 2003) format out of the game. Well it turned out to be a big impediment because the client (software buyer) wouldn’t allow us to install the famous Microsoft Office Compatibility Pack for Word, Excel, and PowerPoint 2007 File Formats on user machines so that users could open and save OOXML file formats even using Microsoft Office 2003 suite.

Discovering ExcelPackage was good but it didn’t do the trick that implies the use of an .XLS template.

I got back Googling again and strived to find an open source library that would allow me to do what I wanted. After some time I finally discovered NPOI. Wow, it could read the .XLS template and generate the end result I wanted. Great. I downloaded the binaries immediately and started playing with it to see what it could really do.

OK, after this short story, I’ll show you how to use both open source projects (ExcelPackage and NPOI).

I’ve created a new ASP.NET MVC project as can be seen in this picture:

In the Content folder I’ve placed the template spreadsheets.
In the Libs folder I’ve placed the DLLs necessary to use both ExcelPackage and NPOI open source projects.

The controller that interests us is the one called ExcelWriterController:

The methods that handle the creation of the spreadsheet are: ExcelPackageCreate and NPOICreate.

For each controller action (method) there’s a corresponding view that renders the UI to the user. Those views are the ones shown inside the ExcelWriter folder: ExcelPackage.aspx and NPOI.aspx.

This is the Home Page of the Excel Writer MVC Application - take a look at the tabs (ExcelPackage and NPOI) that lead you to the View pages:

Each view has a button which when clicked calls the corresponding action method on the ExcelWriterController.

This is the NPOI view page:

I’ll play with a simple spreadsheet I filled with the data I got from Excel’s blog post titled Formula to Access a List of Values Interspersed with Zeros or Blanks.

Let’s see the code that goes into the ExcelPackageCreate method:

/// <summary>
/// Creates a new Excel spreadsheet based on a template using the ExcelPackage library.
/// A new file is created on the server based on a template.
/// </summary>
/// <returns>Excel report</returns>
[AcceptVerbs(HttpVerbs.Post)]
public ActionResult ExcelPackageCreate()
{
    try
    {
        FileInfo template = new FileInfo(Server.MapPath(@"\Content\ExcelPackageTemplate.xlsx"));

        FileInfo newFile = new FileInfo(Server.MapPath(@"\Content\ExcelPackageNewFile.xlsx"));

        // Using the template to create the newFile...
        using(ExcelPackage excelPackage = new ExcelPackage(newFile, template))
        {
            // Getting the complete workbook...
            ExcelWorkbook myWorkbook = excelPackage.Workbook;

            // Getting the worksheet by its name...
            ExcelWorksheet myWorksheet = myWorkbook.Worksheets["Sheet1"];

            // Setting the value 77 at row 5 column 1...
            myWorksheet.Cell(5, 1).Value = 77.ToString();

            // Saving the change...
            excelPackage.Save();
        }

        TempData["Message"] = "Excel report created successfully!";

        return RedirectToAction("ExcelPackage");
    }
    catch(Exception ex)
    {
        TempData["Message"] = "Oops! Something went wrong.";

        return RedirectToAction("ExcelPackage");
    }
}

Let’s see the code that goes into the NPOICreate method:

/// <summary>
/// Creates a new Excel spreadsheet based on a template using the NPOI library.
/// The template is changed in memory and a copy of it is sent to
/// the user computer through a file stream.
/// </summary>
/// <returns>Excel report</returns>
[AcceptVerbs(HttpVerbs.Post)]
public ActionResult NPOICreate()
{
    try
    {
        // Opening the Excel template...
        FileStream fs =
            new FileStream(Server.MapPath(@"\Content\NPOITemplate.xls"), FileMode.Open, FileAccess.Read);

        // Getting the complete workbook...
        HSSFWorkbook templateWorkbook = new HSSFWorkbook(fs, true);

        // Getting the worksheet by its name...
        HSSFSheet sheet = templateWorkbook.GetSheet("Sheet1");

        // Getting the row... 0 is the first row.
        HSSFRow dataRow = sheet.GetRow(4);

        // Setting the value 77 at row 5 column 1
        dataRow.GetCell(0).SetCellValue(77);

        // Forcing formula recalculation...
        sheet.ForceFormulaRecalculation = true;

        MemoryStream ms = new MemoryStream();

        // Writing the workbook content to the FileStream...
        templateWorkbook.Write(ms);

        TempData["Message"] = "Excel report created successfully!";

        // Sending the server processed data back to the user computer...
        return File(ms.ToArray(), "application/vnd.ms-excel", "NPOINewFile.xls");
    }
    catch(Exception ex)
    {
        TempData["Message"] = "Oops! Something went wrong.";

        return RedirectToAction("NPOI");
    }
}

One drawback of the ExcelPackage library is that it must create a file on the server. There are some modifications to the library that enables you to create the template copy on memory and send it to the user as the NPOI library does. Take a look at the ExcelPackage’s discussion page at CodePlex and specifically this thread: Why create Excel spreadsheets on the server?

The great thing about NPOI of course is that it enables you to work with the template in code and the send a copy of the spreadsheet directly to the user. The template remains intact and the user receives a modified copy of the template which contains the data processed by the application.

With NPOI when you click on the Create Excel report button you get the download dialog window:

With ExcelPackage you’d have to get the path of the file created on the server, in this case \Content\ExcelPackageNewFile.xlsx and then send that file to the user. This is an extra step and adds an additional burden to the server. I didn’t implement it and so I let this as an exercise to you.

Well, the spreadsheet included in this simple project has only formulas but you can for sure have an Excel template with lots of formulas, pivot tables, macros, etc. This gives you the power of Excel in code in a clean fashion.

Hope this helps shed some light on this topic!

Note
Using the open source libraries presented in this post you won’t need Microsoft Excel installed on the server.

Visual Studio 2008 C# ASP.NET MVC Web Application
You can get the Microsoft Visual Studio Project at:

http://leniel.googlepages.com/ExcelWriterMvcProject.zip

To try out the code you can use the free Microsoft Visual Web Developer 2008 Express Edition that you can get at: http://www.microsoft.com/express/vwd/Default.aspx

References
ExcelPackage: Office Open XML Format file creation
http://excelpackage.codeplex.com/

ExcelPackage binaries download
http://excelpackage.codeplex.com/Release/ProjectReleases.aspx

NPOI
http://npoi.codeplex.com/

NPOI binaries download
http://npoi.codeplex.com/Release/ProjectReleases.aspx

Interesting discussion on stackoverflow
Create Excel (.XLS and .XLSX) file from C#

A* pathfinding search in C# - Part 2

2009-06-20T19:07:00.000-03:00

To illustrate the path finding problem and how it can be solved using A* I decided to use the Romania map (with the same Cities I used in Breadth and depth first search series of posts). Now I modified it adding more connections between the cities so that we have more fun while debugging the code.

This time I decided to get the real values of latitude and longitude for the cities shown in the Romania map. To accomplish this I used this Google Spreadsheet that is a geocoder. It uses Google Maps to get geolocalization data to the address we pass to an URL. For example, to get geodata for Bucharest we’d do the following:

http://maps.google.com/maps/geo?output=csv&q=Bucharest, Romania.

The output is:

200,4,44.4479237,26.0978790

The last two values are the latitude and longitude respectively.

This is the Map created using the data stored in the spreadsheet with the help of the Map gadget from Google Docs:

You can pass your mouse over each pin to see the name of the city it represents in the map.

The following picture shows the fictitious connections (paths) between the cities and the cost to move from city to city.

To fill the Graph that represents the Romania map above I created a static private method called FillGraphWithEarthMap inside the AStar class that does the job of creating the Nodes and adding them to the graph (bellow I show a shortened version of such a method because it is a really big method given the fact that we have 20 cities and 41 connections (paths) between them:

/// <summary>
/// Fills a Graph with Romania map information.
/// The Graph contains Nodes that represents Cities of Romania.
/// Each Node has as its key the City name and its Latitude and Longitude associated information.
/// Nodes are vertexes in the Graph. Connections between Nodes are edges.
/// </summary>
/// <param name="graph">The Graph to be filled</param>
/// <param name="distanceType">The DistanceType (KM or Miles) between neighbor cities</param>
private static void FillGraphWithEarthMap(Graph graph, DistanceType distanceType)
{
    // 20 Vertexes in total
    Node arad = new Node("Arad", null, 46.1792414, 21.3150154); // Creating a Node...
    graph.AddNode(arad); // Adding the Node to the Graph...

    Node bucharest = new Node("Bucharest", null, 44.4479237, 26.097879);
    graph.AddNode(bucharest);

    Node craiova = new Node("Craiova", null, 44.3182085, 23.8016427);
    graph.AddNode(craiova);

    .
    .
    .

    // 41 Edges in total
    // Arad <-> Sibiu
    graph.AddUndirectedEdge(arad, sibiu, Haversine.Distance(arad, sibiu, distanceType));
    // Arad <-> Timisoara
    graph.AddUndirectedEdge(arad, timisoara, Haversine.Distance(arad, timisoara, distanceType));
    // Arad <-> Zerind
    graph.AddUndirectedEdge(arad, zerind, Haversine.Distance(arad, zerind, distanceType));

    .
    .
    .
}

The Vertexes
You must create a vertex/Node for each City of the map, passing to the Node’s class constructor the name of the City and its Latitude and Longitude coordinates. Add each Node to the Graph passed as a parameter to the method.

The Edges
You must create an undirected edge/path for each connection between two cities, passing to the constructor the first city, the second city and the cost to go from one city to the other. In this case the cost is calculated through the Haversine class discussed in A* pathfinding search in C# - Part 1.

To help debug the code I created two methods: DistanceBetweenNodes and ViewOtherPaths. Both methods are kept in the AStar class.

This is the DistanceBetweenNodes method:

/// <summary>
/// Prints on screen the distance from a city to its neighbors.
/// </summary>
/// <param name="graph">The Graph</param>
/// <param name="distanceType">The distance type: KM or Miles</param>
private static void DistanceBetweenNodes(Graph graph, DistanceType distanceType)
{
    // First we cast the Graph.Nodes which is a NodeList to type Node and then we order the list of Nodes by the Node Key
    // so that we get the list of cities in ascending order.
    foreach(Node n in graph.Nodes.Cast<Node>().OrderBy(n => n.Key))
    {
        // For each city neighbor we gets its information and print it on screen.
        foreach(EdgeToNeighbor etn in n.Neighbors)
        {
            Console.WriteLine("Distance from {0} to {1} is -> {2:#.##} {3}", n.Key, etn.Neighbor.Key, etn.Cost, distanceType);
        }
    }
}

Inside the FindPath method presented on A* pathfinding search in C# - Part 1, I call the ViewOtherPaths method (it’s commented out):

/// <summary>
/// This is the method responsible for finding the shortest path between a Start and Destination cities using the A*
/// search algorithm.
/// </summary>
/// <typeparam name="TNode">The Node type</typeparam>
/// <param name="start">Start city</param>
/// <param name="destination">Destination city</param>
/// <param name="distance">Function which tells us the exact distance between two neighbours.</param>
/// <param name="estimate">Function which tells us the estimated distance between the last node on a proposed path and the
/// destination node.</param>
/// <returns></returns>
static public Path<TNode> FindPath<TNode>(
    TNode start,
    TNode destination,
    Func<TNode, TNode, double> distance,
    Func<TNode, double> estimate) where TNode : IHasNeighbours<TNode>
{
    var closed = new HashSet<TNode>();

    var queue = new PriorityQueue<double, Path<TNode>>();

    queue.Enqueue(0, new Path<TNode>(start));

    while(!queue.IsEmpty)
    {
        var path = queue.Dequeue();

        if(closed.Contains(path.LastStep))
            continue;

        if(path.LastStep.Equals(destination))
            return path;

        closed.Add(path.LastStep);

        foreach(TNode n in path.LastStep.Neighbours)
        {
            double d = distance(path.LastStep, n);

            var newPath = path.AddStep(n, d);

            queue.Enqueue(newPath.TotalCost + estimate(n), newPath);
        }

        //ViewOtherPaths(queue, estimate);
    }

    return null;
}

This is the ViewOtherPaths method:

/// <summary>
/// This method can be used to view the other paths inside the PriorityQueue.
/// </summary>
/// <typeparam name="TNode">The Node type</typeparam>
/// <param name="queue">The priority queue</param>
/// <param name="estimate">Function which tells us the estimated distance between the last node on a proposed path and the
/// destination node.</param>
private static void ViewOtherPaths<TNode>(PriorityQueue<double, Path<TNode>> queue, Func<TNode, double> estimate)
{
    // The priority queue is composed of KeyValuePairs which has as key a double value (the TotalCost) and
    // has as Value a Queue which contains Paths.
    foreach(KeyValuePair<double, Queue<Path<TNode>>> kvp in queue)
    {
        // For each path in the Queue...
        foreach(Path<TNode> otherPath in kvp.Value)
        {
            // Reverse the Path so that we get the order of the cities in a more meaningful way...
            var otherPathReversed = otherPath.Cast<Node>().Reverse();

            // Prints on screen the Cities that are part of this path.
            foreach(Node n in otherPathReversed)
            {
                Console.WriteLine(n.Key);
            }

            // Get the total cost of the other path.
            double otherPathTotalCost = otherPath.TotalCost;
            // Get the estimation cost of the other path.
            double otherPathEstimation = estimate(otherPath.LastStep);

            // Prints on the screen the relevant information so that it gets easier to debug the code and see how
            // the A* search algorithm really does the job...
            Console.WriteLine("Total Cost other path = {0}", otherPathTotalCost);
            Console.WriteLine("Estimation other path = {0}", otherPathEstimation);
            Console.WriteLine(@"Priority Queue Cost other path = {0} =
                            Total Cost other path + Estimation other path =
                            {1}", kvp.Key, otherPathTotalCost + otherPathEstimation);
        }

        Console.WriteLine();
    }

    Console.WriteLine();
}

I also use two additional methods to get the Start and Destination cities entered by the user when s/he runs the code. Both methods keep a loop until the user enters the name of a city that is indeed part of the Graph we’ve just created:

/// <summary>
/// Gets the Destination city.
/// </summary>
/// <param name="graph">The Graph</param>
/// <returns>Name of Destination city</returns>
private static string GetDestinationCity(Graph graph)
{
    string destinationCity;

    do
    {
        Console.Write("\nEnter a Destination city: ");

        destinationCity = Console.ReadLine();
    }
    while(!graph.Nodes.ContainsKey(destinationCity));

    return destinationCity;
}

/// <summary>
/// Gets the Destination city.
/// </summary>
/// <param name="graph">The Graph</param>
/// <returns>Name of Destination city</returns>
private static string GetDestinationCity(Graph graph)
{
    string destinationCity;

    do
    {
        Console.Write("\nEnter a Destination city: ");

        destinationCity = Console.ReadLine();
    }
    while(!graph.Nodes.ContainsKey(destinationCity));

    return destinationCity;
}

This is the main entry point of the Console Application I created:

static void Main(string[] args)
{
    do
    {
        // Creating the Graph...
        Graph graph = new Graph();

        //FillGraphWithGridMap(graph);

        FillGraphWithEarthMap(graph, DistanceType.Kilometers);

        // Prints on the screen the distance from a city to its neighbors.
        // Used mainly for debug information.
        // DistanceBetweenNodes(graph, DistanceType.Kilometers);

        Console.WriteLine("A* Search - Sample implementation by Leniel Macaferi, June 7-20, 2009\n");
        Console.WriteLine("These are the Cities you can choose as Start and Destination in Romania: \n");

        // Prints on screen the cities that you can choose as Start and Destination.
        foreach(Node n in graph.Nodes.Cast<Node>().OrderBy(n => n.Key))
        {
            Console.WriteLine(n.Key);
        }

        string startCity = GetStartCity(graph);

        string destinationCity = GetDestinationCity(graph);

        Node start = graph.Nodes[startCity];

        Node destination = graph.Nodes[destinationCity];

        // Function which tells us the exact distance between two neighbours.
        Func<Node, Node, double> distance = (node1, node2) => node1.Neighbors.Cast<EdgeToNeighbor>().Single(etn => etn.Neighbor.Key == node2.Key).Cost;

        // Estimation/Heuristic function (Manhattan distance)
        // It tells us the estimated distance between the last node on a proposed path and the destination node.
        //Func<Node, double> manhattanEstimation = n => Math.Abs(n.X - destination.X) + Math.Abs(n.Y - destination.Y);

        // Estimation/Heuristic function (Haversine distance)
        // It tells us the estimated distance between the last node on a proposed path and the destination node.
        Func<Node, double> haversineEstimation = n => Haversine.Distance(n, destination, DistanceType.Kilometers);

        //Path<Node> shortestPath = FindPath(start, destination, distance, manhattanEstimation);
        Path<Node> shortestPath = FindPath(start, destination, distance, haversineEstimation);

        // Prints the shortest path.
        foreach(Node n in shortestPath.Reverse())
        {
            Console.WriteLine(n.Key);
        }

        Console.Write("\nDo you wanna try A* Search again? Yes or No? ");
    }
    while(Console.ReadLine().ToLower() == "yes");
}

The main entry point above calls all the other methods I showed in this post.

This is all you need to run the A* pathfinding search algorithm! :-)

I think the code is well documented through comments.

I wish this helps you understand how to put together the working pieces necessary to run a test case.

Next time: I’ll run a test case using the Graph we have assembled in this post.

A* pathfinding search in C# - Part 1

2009-06-13T22:33:00.005-03:00

Last Sunday after I got back from church I read Kirill Osenkov’s post Algorithms in C#: shortest path around a polygon (polyline routing). Kirill mentions Eric Lippert’s excellent series of posts titled Path Finding Using A* in C# 3.0. I’ve read that series of posts a long time ago (2007 - I was on the last year of the computer engineering course).

See you how life is interesting: in 2007 after reading Lippert’s posts I wanted to see a running sample of the code but didn’t try to implement that until the time I read Osenkov’s post. Why did it took so long? I don’t know how to answer this.

I studied A* in the 9th term of the computer engineering course (Feb-Jun, 2007). The discipline was Artificial Intelligence. At that time I didn’t implement any code for this specific algorithm (I think this is due the so famous excuse during the classes - we just don’t have enough time to do that. We have lots of topics to see yet.) . Therefore, we’ve just run test cases on sheets of paper. Not so good but a start.

Well, Eric wrote the base structure of the A* pathfinding algorithm but didn’t provide a complete running sample. He wrote the following:

I have a nice example of using A* to find the shortest path around a lake (but not the longest shortest path!) but I'm not going to post it here until Orcas ships. I'll just put up the whole project file at that time and you can check it out all at once.

Still on Sunday night I took the time to write some code that put up a running A* search.

I basically merged some code I had already posted on the series of posts titled Breadth and depth first search and created some properties here and there to get the whole thing running. It’s nothing more than code reuse.

The following is the basic project’s structure I created:

In Path Finding Using A* in C# 3.0, Part One the A* algorithm is described.

In Path Finding Using A* in C# 3.0, Part Two the data structures necessary to implement the A* algorithm are defined.

In this part Eric writes:

Let’s make an immutable stack of nodes which tracks the total cost of the whole path. Later on, we’ll see that we need to enumerate the nodes of this thing, so we’ll do a trivial implementation of IEnumerable while we’re at it. And since we don’t know exactly what a node will look like, let’s make the thing generic.

In part two we are presented to an immutable stack that I’ve put inside the Path class.

In Path Finding Using A* in C# 3.0, Part Three we are presented to a priority queue. This structure is responsible for putting the best paths so far in priority order, that is, the path with a lesser cost has a major priority.

In this part Eric writes:

In order to make the A* algorithm work we need to get the lowest-estimated-cost-path-discovered-so-far out of the list of paths under consideration. The standard data structure for doing so is called a “priority queue”. Priority queues are so-called because they are typically used to store a list of jobs where each job has an associated priority.

The PriorityQueue lies within its namesake class.

In Path Finding Using A* in C# 3.0, Part Four we get the FindPath method that is the one responsible for finding the shortest path possible. This method uses all of the remaining classes shown on the project structure above.

I put the FindPath method inside the AStar class.

In this part Eric writes:

What do we need to make the algorithm run? We need a start node, a destination node, a function which tells us the exact distance between two neighbours, and a function which tells us the estimated distance between the last node on a proposed path and the destination node.

This is the beautiful PathFind method:

static public Path<TNode> FindPath<TNode>(
    TNode start,
    TNode destination,
    Func<TNode, TNode, double> distance,
    Func<TNode, double> estimate) where TNode : IHasNeighbours<TNode>
{
    var closed = new HashSet<TNode>();

    var queue = new PriorityQueue<double, Path<TNode>>();

    queue.Enqueue(0, new Path<TNode>(start));

    while(!queue.IsEmpty)
    {
        var path = queue.Dequeue();

        if(closed.Contains(path.LastStep))
            continue;

        if(path.LastStep.Equals(destination))
            return path;

        closed.Add(path.LastStep);

        foreach(TNode n in path.LastStep.Neighbours)
        {
            double d = distance(path.LastStep, n);

            var newPath = path.AddStep(n, d);

            queue.Enqueue(newPath.TotalCost + estimate(n), newPath);
        }
    }

    return null;
}

When you get at the fourth part of Eric’s posts you may get thinking: How can I run this thing? That’s what I try to explain in this post.

The immutable stack implemented in part two of Eric’s posts is a generic one, that is, it accepts an object custom made to represent a Node in the path.

I already had a class Node that I used sometime ago while studying Artificial Intelligence. Take a look at Breadth and depth first search series of posts.

I also needed a Graph that represents the map formed with the connections between the nodes.

The Graph has a NodeList that stores all the nodes currently in the graph.

A node can have neighbors, that is, other nodes connected to it and such connections are represented in the code through the class AdjacencyList. Each node has an AdjacencyList that stores its neighbors.

A connection (edge) between two nodes (vertexes) is represented by the EdgeToNeighbor class that stores the neighbor of a node and the cost to get to that neighbor.

The AdjacencyList, EdgeToNeighbor, Graph, Node and NodeList classes are the outcome of an excellent series of articles by Scott Mitchell titled An Introduction to Data Structures. I got those classes and added them to the project.

This way I had all set to pass in the first two parameters of the PathFind method.

Now I needed to figure out how to create the distance and estimate functions to pass as the third and fourth parameters.

For the distance function I did this:

// Function which tells us the exact distance between two neighbours.
Func<Node, Node, double> distance = (node1, node2) => node1.Neighbors.Cast<EdgeToNeighbor>().Single(etn => etn.Neighbor.Key == node2.Key).Cost;

The distance function receives two nodes as parameters as can be seen in the PathFind method and returns a double value. I then use a lambda expression to find the Cost, (distance) in this case, between the two nodes. I get the neighbors of node1 and cast those to EdgeToNeighbor and execute a query using a lambda expression again to return the Cost only if the key of one of the neighbors of node1 is equal to the key of node2.

For the estimation function I did this:

// Estimation/Heuristic function (Haversine distance)
// It tells us the estimated distance between the last node on a proposed path and the destination node.
Func<Node, double> haversineEstimation = n => Haversine.Distance(n, destination, DistanceType.Kilometers);

Now I’m using as the estimation the Haversine formula. This formula gives the great-circle distances between two points on a sphere (Earth) from their longitudes and latitudes.

I got the Haversine formula code from the post Haversine Formula in C# and in SQL by Seth Long. I just adapted it a little bit so that I could use it with the Node data structure.

The haversine generic delegate receives as input a Node and return a double. Using a lambda expression I get the Haversine distance from node n to the destination node and I set that I want the distance in Kilometers.

With the distance and estimate functions on hand we’re OK to call the PathFind method.
Wait! Don’t we need something before that? Of course we need. We need to populate the graph with nodes. After all we’re after the shortest path between two nodes and we need some nodes to test the A* star pathfinding search. :-)

Next time: I’ll show you how to create a complete scenario using the same Romania map I used in the Breadth and depth first search series of posts.

References
[1] Lippert, Eric. Path Finding Using A* in C# 3.0, Part One. 2007. Available at <http://blogs.msdn.com/ericlippert/archive/2007/10/02/path-finding-using-a-in-c-3-0.aspx>. Accessed on June 13, 2009.

[2] Lippert, Eric. Path Finding Using A* in C# 3.0, Part Two. 2007. Available at <http://blogs.msdn.com/ericlippert/archive/2007/10/04/path-finding-using-a-in-c-3-0-part-two.aspx>. Accessed on June 13, 2009.

[3] Lippert, Eric. Path Finding Using A* in C# 3.0, Part Three. 2007. Available at <http://blogs.msdn.com/ericlippert/archive/2007/10/08/path-finding-using-a-in-c-3-0-part-three.aspx>. Accessed on June 13, 2009.

[4] Lippert, Eric. Path Finding Using A* in C# 3.0, Part Four. 2007. Available at <http://blogs.msdn.com/ericlippert/archive/2007/10/10/path-finding-using-a-in-c-3-0-part-four.aspx>. Accessed on June 13, 2009.

[5] Mitchell, Scott. An Extensive Examination of Data Structures. 2005. Available at <http://msdn.microsoft.com/en-us/library/ms379570(VS.80).aspx>. Accessed on June 13, 2009.

[6] Long, Seth. Haversine Formula in C# and in SQL. 2008. Available at <http://megocode3.wordpress.com/2008/02/05/haversine-formula-in-c>. Accessed on June 13, 2009.

Calculating prime numbers with LINQ in C#

2009-05-31T03:33:00.000-03:00

To serve as a processing test in a follow up post I’m posting how to calculate prime numbers using a LINQ query expression.

In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. The first twenty-five prime numbers are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

The following code^[1] shows how to calculate the prime numbers that are less equal ( <= ) a given number “max”:

Func<int, IEnumerable<int>> primeNumbers = max =>
     from i in Enumerable.Range(2, max - 1)
     where Enumerable.Range(2, i - 2).All(j => i % j != 0)
     select i;

IEnumerable<int> result = primeNumbers(10);

foreach(int i in result)
{
  Console.WriteLine(i);
}

In my final computer engineering assignment I presented LINQ - Language Integrated Query and its constructs. With such constructs it’s possible to achieve a high degree of method chaining.

LINQ is declarative, not imperative. It allows us to simply state what we want to do without worrying about how it is done.

In the code above we declare a Func<(Of <(T, TResult>)>) generic delegate which has an int as input parameter and an IEnumerable<int> as the result.
Func delegates are very useful for encapsulating user-defined expressions that are applied to each element in a set of source data.

Using a lambda expression ( => ) we assign a query expression to the delegate.
A lambda expression is an anonymous function that can contain expressions and statements, and can be used to create delegates or expression tree types.

The query expression states that from each value i in the Enumerable.Range(2, max - 1) where all elements of the range Enumerable.Range(2, i – 2) satisfy the condition All(j => i % j != 0), we select i.

max is the delegate input parameter.

The % symbol is the modulus operator in C#. It computes the remainder after dividing its first operand by its second.

For example: considering max = 10 we’d have the following…

The range in the from clause is: { 2, 3, 4, 5, 6, 7, 8, 9, 10 }

Taking the 1st value out of the from range, we have i = 2.

The range in the where clause is Range (2, 2 - 2) = Range (2 , 0) = { }.

Since i = 2 is by default included in the result, what must be evaluated lies where the variable max is used. So, taking the 2nd value and assigning it to i we have i = 3.

The range in the where clause is Range (2, 3 - 2) = Range (2 , 1) = { 2 }.

Evaluating j => i % j we have 3 % 2 = 1, and so, 3 is a prime number.

Taking the 3rd value and assigning it to i we have i = 4.

The range in the where clause is Range (2, 4 - 2) = Range (2, 2) = { 2, 3 }.

Evaluating j => i % j we have 4 % 2 = 0 and 4 % 3 = 1, and so 4 is not a prime number because all elements of the where range must yield a result != 0 for the expression i % j != 0.

Now we have i = 5.

The range in the where clause is Range (2, 5 - 2) = Range (2 , 3) = { 2, 3, 4 }.

Evaluating j => i % j we have 5 % 2 = 1, 5 % 3 = 2 and 5 % 4 = 1. From this we have that 5 is a prime number.

Now we have i = 6.

The range in the where clause is Range (2, 6 - 2) = Range (2 , 4) = { 2, 3, 4, 5 }.

Evaluating j => i % j we have 6 % 2 = 0, 6 % 3 = 0, 6 % 4 = 2 and 6 % 5 = 1. From this we have that 6 is not prime number.

Now we have i = 7.

The range in the where clause is Range (2, 7 - 2) = Range (2 , 5) = { 2, 3, 4, 5, 6 }.

Evaluating j => i % j we have 7 % 2 = 1, 7 % 3 = 1, 7 % 4 = 3, 7 % 5 = 2 and 7 % 6 = 1. From this we have that 7 is prime number.

Now we have i = 8.

The range in the where clause is Range (2, 8 - 2) = Range (2 , 6) = { 2, 3, 4, 5, 6, 7 }.

Evaluating j => i % j we have 8 % 2 = 0, 8 % 3 = 2, 8 % 4 = 0, 8 % 5 = 3, 8 % 6 = 2 and 8 % 7 = 1. 8 isn’t a prime number.

Now we have i = 9.

The range in the where clause is Range (2, 9 - 2) = Range (2 , 7) = { 2, 3, 4, 5, 6, 7, 8 }.

Evaluating j => i % j we have 9 % 2 = 1, 9 % 3 = 0, 9 % 4 = 1, 9 % 5 = 4, 9 % 6 = 3, 9 % 7 = 2 and 9 % 8 = 1. 9 isn’t a prime number.

Now we have i = 10.

The range in the where clause is Range (2, 10 - 2) = Range (2 , 8) = { 2, 3, 4, 5, 6, 7, 8, 9 }.

Evaluating j => i % j we have 10 % 2 = 0, 10 % 3 = 1, 10 % 4 = 2, 10 % 5 = 0, 10 % 6 = 4, 10 % 7 = 3, 10 % 8 = 2 and 10 % 9 = 1. 10 isn’t a prime number.

Finally we have 4 prime numbers <= 10; they are: { 2, 3, 5, 7 }.

The following table illustrates the result:

i	where Range(2, i - 2)	All(j => i % j != 0)
2	{ }
3	{ 2 }	3 % 2 = 1
4	{ 2, 3 }	4 % 2 = 0 4 % 3 = 1
5	{ 2, 3, 4 }	5 % 2 = 1 5 % 3 = 2 5 % 4 = 1
6	{ 2, 3, 4, 5 }	6 % 2 = 0 6 % 3 = 0 6 % 4 = 2 6 % 5 = 1
7	{ 2, 3, 4, 5, 6 }	7 % 2 = 1 7 % 3 = 1 7 % 4 = 3 7 % 5 = 2 7 % 6 = 1
8	{ 2, 3, 4, 5, 6, 7 }	8 % 2 = 0 8 % 3 = 2 8 % 4 = 0 8 % 5 = 3 8 % 6 = 2 8 % 7 = 1
9	{ 2, 3, 4, 5, 6, 7, 8 }	9 % 2 = 1 9 % 3 = 0 9 % 4 = 1 9 % 5 = 4 9 % 6 = 3 9 % 7 = 2 9 % 8 = 1
10	{ 2, 3, 4, 5, 6, 7, 8, 9 }	10 % 2 = 0 10 % 3 = 1 10 % 4 = 2 10 % 5 = 0 10 % 6 = 4 10 % 7 = 3 10 % 8 = 2 10 % 9 = 1

I’ll use the primeNumbers delegate in the next post to evaluate PLINQ (Parallel LINQ) and measure the performance gains when the same calculation is done in parallel instead of in sequence.

References
[1] Perfetti, Michel. LINQ Quiz: The list of prime numbers in 3 clauses? 2007. Available at <http://blogs.developpeur.org/raptorxp/archive/2007/11/26/quizz-linq-la-liste-des-nombres-premiers-en-3-clauses.aspx>. Accessed on May 31, 2009.

Logging NHibernate SQL with log4net in ASP.NET

2009-05-23T15:59:00.001-03:00

Have you ever wondered how to log the SQL generated by NHibernate?

This post tries to exemplify just that.

NHibernate uses HQL to leverage its expressiveness to the developer, but behind the scenes there is an engine that transforms the HQL into pure SQL that is executed against the database. This SQL can be logged so that you can see its structure and get a snapshot of what the database engine receives.

log4net is a logging tool that helps the developer see what SQL NHibernate is generating under the covers.

This is a brief description of log4net taken from its homepage:

log4net is a tool to help the programmer output log statements to a variety of output targets.

First and foremost you need to enable NHibernate logging in its configuration file. The property that sets this is hibernate.show_sql.

<add key="hibernate.show_sql" value="true" />

The following piece of code shows how to configure an appender and a logger that makes use of the appender. This code is kept inside the Web.config file in the log4net configuration section:

<appender name="NHibernateRollingFileAppender" type="log4net.Appender.RollingFileAppender">
    <file value="LogNHibernate.txt"/>
    <appendToFile value="true"/>
    <rollingStyle value="Size"/>
    <datePattern value="yyyyMMdd"/>
    <maxSizeRollBackups value="10"/>
    <maximumFileSize value="10MB"/>
    <layout type="log4net.Layout.PatternLayout">
        <conversionPattern value="%date - %message%newline"/>
    </layout>
</appender>

<logger name="NHibernateLogger" additivity="false">
    <level value="DEBUG"/> <!-- ALL, DEBUG, INFO, WARN, ERROR, FATAL or OFF –>
    <appender-ref ref="NHibernateRollingFileAppender"/>
</logger>

I’ll describe each part of the above code.

Appender is an output destination. In this case its a RollingFileAppender. It writes logging events to a file in the file system.

The file property specifies the name of the file that’ll store the logs.

The appendToFile property is set to true so that the appender will overwrite existing files.

The rollingStyle property set how to roll log files. In this case the appender will roll log files based on the file size.

To change the rolling period we need to set the datePattern property. It would be used if we adopted a rollingStyle based on Date instead of Size.

Up to 10 old files of 10MB each will be kept. These rolled files will be named: LogNHibernate.txt.1, LogNHibernate.txt.2, LogNHibernate.txt.3, etc...

A layout enables us to customize the output format. This is accomplished by associating a layout with an appender.

The PatternLayout, lets the user specify the output format according to conversion patterns similar to the C language printf function.

This is the logger and its additivity property controls appender accumulation, that is, how the logs are printed in the hierarchy of loggers.

For example, the output of a log statement of logger NHibernateLogger will go to all the appenders in NHibernateLogger and its ancestors. This is the meaning of the term "appender additivity".

The level property controls the amount of information you want to be written to the log.

<appender-ref ref="NHibernateRollingFileAppender"/>

The property appender-ref specifies what appenders this logger uses.

That’s it! :-)

With this basic configuration you can start you search for points where NHibernate is generating to much queries where it shouldn’t.

I’m currently working on a performance branch where I’m learning how to deal with NHibernate lazy configuration.

This process of logging the SQL generated by NHibernate plays a great role when one is solving the bottlenecks involved in performance implications.

Just one note: keep in mind that the process of logging is by itself an onerous one. The amount of data that gets written by NHibernate is expressive and depending on the level of information you set inside the logger, the file size will grow very fast.

Hope this helps the fellow developers.

References

log4net homepage
http://logging.apache.org/log4net

log4net introduction
http://logging.apache.org/log4net/release/manual/introduction.html

log4net configuration examples
http://logging.apache.org/log4net/release/config-examples.html

Regex engine in C# - matching strings

2009-05-11T02:55:00.001-03:00

To close this series of posts, today I’m going to match some input strings using the regex (l|e)*n?(i|e)el* that we’ve been using since the beginning.

To match the strings I’ll make use of the DFA we constructed in the last post titled Regex engine in C# - the DFA.

These are the 20 strings I’ll be matching:

eee, eeeil, eel, ennil, ie, leie, lele, leleel, lelel, lelenil, leliel, leniel, llnel, ln, lnel, lniel, nelll, niel, nil and nll.

In the DFA class we have a method called Simulate which I show bellow:

public string Simulate(string @in)
{
  state currentState = start;

  CharEnumerator i = @in.GetEnumerator();

  while(i.MoveNext())
  {
    KeyValuePair<state, input> transition = new KeyValuePair<state, input>(currentState, i.Current);

    if(!transTable.ContainsKey(transition))
      return "Rejected";

    currentState = transTable[transition];
  }

  if(final.Contains(currentState))
    return "Accepted";
  else
    return "Rejected";
}

The Simulate method takes as input a string to be matched and returns a string that signalizes success or failing when matching such a string.

To test it I’ll match the string “leniel” which by the way is my own name. :-)

So, what the Simulate method do?

It starts by assigning the start state 0 to the variable currentState.

Next we get a charEnumerator that is used in the while block to move letter by letter (input symbol by input symbol) till we get to the end of the string.

We declare a KeyValuePair<state, input> designated transition that has as the key the currentState and as the value the current input symbol we’re simulating.

We check to see if the DFA’s transition table contains such a transition, that is, if there’s a valid path from that state with that input symbol to another state. If it doesn’t, we reject the string we’re matching, otherwise we make the currentState variable receive the next state, that is, the state appointed by the transition we’ve just checked.

The process inside the while block goes on until we reach the last input symbol taken from the string we’re matching, in this case, the last “l” letter.

After getting out of the while block we make a final check to see if the state we achieved is part of the DFA’s set of final states. If it is, we accept the string, otherwise, we reject it.

This is an x-ray from the variables’ value when in the first iteration of the while block:

As you can see in the transition table, from start state (currentState) “0” with the fist input symbol “l” we can go to state “3”.

The following table shows the result obtained while testing the strings mentioned above:

Accepted	Rejected
eee	eeeil
eel	ennil
ie	lele
leie	lelel
leleel	lelenil
leliel	llnel
leniel	ln
lniel	lnel
niel	nelll
	nil
	nll

To make sure it’s correct, debug each one of these strings visually looking at the DFA’s graph representation shown below. Starting at state 0 we must end in one of the final states {7, 8, 9, 10}.

The Regex Engine executable
The Regex Engine presented in this series of posts is a C# Console Application. As such it was written in a way that its command line arguments must be entered in the following form:

RegularExpressionEngine "(l|e)*n?(i|e)el*" leniel

Where:

RegularExpressionEngine -> the name of the executable .exe file (the program itself)

"(l|e)*n?(i|e)el*" –> between the double quotes we pass the regex

leniel –> the string we want to match in the regex

Using Microsoft Visual Studio C# 2008 we can set the command line arguments using the Debug properties page of the project like the following picture:

To get to the Debug page, right click in the solution inside Solution Explorer as shown in the following picture:

After setting the command line arguments, hit F5 and you’re ready to go.

The Regex Engine source code
You can get the complete code (Microsoft Visual C# 2008 Console application) and executable at:

http://leniel.googlepages.com/RegularExpressionEngine.rar

To try out the code you can use the free Microsoft Visual C# 2008 Express Edition that you can get at: http://www.microsoft.com/express/vcsharp

Updated on 5/12/2009 10:06:00 PM

As I finished writing the posts, here goes the list that points to them:

Regular Expression Engine in C# (the Story)
Regex engine in C# - the Regex Parser
Regex engine in C# - the NFA
Regex engine in C# - the DFA

References
The following links can help you when dealing with regexes:

Regular-Expressions.info - Regex Tutorial, Examples and Reference - Regex Patterns
http://www.regular-expressions.info

Regular Expression Library (great site with lots of regexes and an excellent regex tester)
http://regexlib.com/Default.aspx
http://regexlib.com/RETester.aspx

Testing Windows 7 beta and RC versions

2009-05-09T18:14:00.001-03:00

Windows is the piece of software that underlies everything on my computer so that I thought it would be a great opportunity to write about it since we’re on the verge of its new version, namely, Windows 7.

I’ve been testing Windows 7 for the last two months. It’s been my operating system since then.

Firstly I got the 32-bit Beta release on March, 15th and today I’m downloading the 64-bit RC (release candidate) version. I plan to install it this weekend and as soon as I have it installed and configured I’ll update this post.

What I have to write about this operating system? Numbered from 1 to 7 in an unordered relevance fashion…

1 - It is fast.
2 - I risk to say it is faster than Windows XP.
3 - It is beautiful! Take a look at the new taskbar.
4 - It simplifies a lot of tasks.
5 - It has more native programs.
6 - Previous Windows’s native programs got a refresh and were optimized.
7 - It adds more security points to your day to day tasks.

My Windows 7 Beta taskbar:

I moved directly from Windows XP to Windows 7. I didn’t use Windows Vista because it was too bloated for my computer in the beginning of 2006 when I also tested it in the beta period. At that time I had an AMD Athlon XP 2400+ with 512 MB RAM memory and an onboard video card which didn’t allow me to get the so famous Aero interface. I didn’t have a plan to upgrade my hardware. That was the big impediment. I think that Windows Vista arrived in a time in which the majority of computers didn’t have a proper hardware configuration yet.

Now the landscape is different. Windows 7 appears in a time that it’s much cheaper to buy a 2-core computer with GBs of RAM memory; Computer prices went down during the past years even here in Brazil where hardware prices double if compared with US $. Today $ 1 = R$ 2.07. This price is still attractive. Believe it or not! :)

The following picture shows my current computer configuration:

This is the Windows Experience Index score I got - a low score given the fact that I still use an onboard video card and that the score is determined by the lowest subscore:

Even with a 3.2 score I have the windows Aero enabled. Take a look at the Windows Experience Index: An In-Depth Look post that describes the score levels and what system’s features are enabled or disabled based on them.

From the Engineering the Windows 7 “Windows Experience Index” post we have the following:

The Vista-era general guidelines for systems in the 1.0, 2.0, 3.0, 4.0 and 5.0 ranges still apply to Windows 7. But, Windows 7 has added levels 6.0 and 7.0; meaning 7.9 is the maximum score possible.

While using Windows 7 beta I installed all the software I work with as the Microsoft Visual Studio 2008 Professional, Oracle Database, PL/SQL Developer, TortoiseSVN, etc - a typical developer box.

Windows 7 didn’t crash and was a well behaved operating system during this beta period in which I did everything I used to do in Windows XP.

The only hardware problem I had was with a Creative Audigy sound card (model number SB0090). There was no driver available for Windows 7. So I had to install a driver that wasn’t full compatible. The sound didn’t sound as good as it should be. I experienced a lot of noise.
Creative Labs has a Windows 7 - Driver Availability Chart in case you’re interested.

All in all you’ll get a great experience with such a robust operating system. After all Windows is ubiquitous and the more you can do with it the better you get at work.

Updated on 6/6/2009 05:48:00 PM

I’ve installed Windows 7 64-bit version but I didn’t use it because for the sake of my work I thought Win 7 wouldn’t play as expected.

Firstly we should consider that Windows 7 64-bit has a default Program Files (x86) folder where it puts all applications that are made to run on a 32-bit operating system. This particularly broke my way because the software that I develop rely on an Oracle database connection. There is a known bug with Oracle that prevents an application hosted in a folder that has parenthesis in its name to access an Oracle database.

I didn’t notice any performance gains while running the 64-bit OS.

Today I finally installed the Windows 7 RC 32-bit. I upgraded from the 32-bit Beta version to the RC version. The upgrade is only possible from 32-bit to 32-bit versions and not from a 64-bit Beta to 32-bit RC and vice versa.

The upgrade took 1 hour and 40 minutes to complete and ran flawlessly. You may ask why this took so long? This is because in a upgrade it is necessary to copy a lot of files from the old OS to the new one.

I downloaded the ISO file and extracted its content to a temp folder. I changed the file cversion.ini as described in the post Delivering a quality upgrade experience from the Engineering Windows 7 blog so that I could go through the upgrade. I then clicked setup.exe while running the Windows 7 beta version and the installation started.

I got the following report:

Upgrading Windows will affect the following devices and/or programs:

These programs might not work properly after the upgrade. We recommend uninstalling these programs before upgrading. Cancel the upgrade, open Control Panel, and search for "uninstall a program". (Note: Programs marked as * can be safely reinstalled after the upgrade.)

Microsoft SQL Server 2008
Microsoft SQL Server 2005

I then decided to ignore the report and proceeded with the installation.

The above image shows the early stages of the upgrade. In fact there were more than 400000 files to be gathered. I already had an extensive list of apps installed on the beta OS as for example Microsoft Office 2007 that in itself is a big suite of apps.

Windows 7 then restarted sometimes and installed the new OS bits that were refined from Beta to RC. The last step was to transfer files, settings and programs to the new OS. It transferred a total of 524490 files.

My Windows 7 RC taskbar:

From this what I have to say now that I’m using the RC to write this blog post using Windows Live Writer is that the upgrade was successful. I didn’t need to reinstall anything (including Windows Live Writer). Everything is the way they were before installing the RC version.

I had a pleasant experience while upgrading from Beta to RC.

Congratulations to the Microsoft Windows 7 Team for providing this must have feature, that is, making upgrades possible! :-)

A last note: I described above the problem I had while configuring my Creative Audigy sound card in Windows 7 Beta. With the RC version the Creative Audigy soundcard is functioning as expected. One of the first things Windows 7 did was to install the sound card driver!

References
Engineering Windows 7 blog
http://blogs.msdn.com/e7

Windows 7 Team blog
http://windowsteamblog.com/blogs/windows7

Microsoft official Windows 7 site
http://www.microsoft.com/windows/windows-7/default.aspx

Windows 7 @ Paul Thurrott's SuperSite for Windows
http://www.winsupersite.com/win7

Windows 7 article at Wikipedia
http://en.wikipedia.org/wiki/Windows_7

List of features new to Windows 7
http://en.wikipedia.org/wiki/Features_new_to_Windows_7

Regex engine in C# - the DFA

2009-05-03T03:21:00.001-03:00

This time, we’ll take a look at the DFA’s class and its helper class called SubsetMachine.

To understand what’s a DFA, refer to the first post in this series called Regex engine in C# - the Regex Parser.

In the Regex engine in C# - the NFA post we ended with an NFA.

Now we’re going to build a DFA based on such NFA.

Remember that the main difference between a DFA and an NFA is that a DFA doesn’t have epsilon (ε) transitions that represent "nothing" or "no input" between states.

As described in the section DFA versus NFA in the introduction of this series of posts, it may be shown that a DFA is equivalent to an NFA, in that, for any given NFA, one may construct an equivalent DFA, and vice-versa: this is the powerset construction or subset construction.

So, let’s get our hands dirty with some code.

Below I present the DFA class:

//
//  Regular Expression Engine C# Sample Application
//  2006, by Leniel Braz de Oliveira Macaferi & Wellington Magalhães Leite.
//
//  UBM's Computer Engineering - 7th term [http://www.ubm.br/]
//  
//  This program sample was developed and turned in as a term paper for Lab. of
//  Compilers Construction. It was based on the source code provided by Eli Bendersky
//  [http://eli.thegreenplace.net/] and is provided "as is" without warranty.
//

using System;
using SCG = System.Collections.Generic;
using C5;

using state = System.Int32;
using input = System.Char;

namespace RegularExpressionEngine
{
  /// <summary>
  /// Implements a deterministic finite automata (DFA)
  /// </summary>
  class DFA
  {
    // Start state
    public state start;
    // Set of final states
    public Set<state> final;
    // Transition table
    public SCG.SortedList<KeyValuePair<state, input>, state> transTable;

    public DFA()
    {
      final = new Set<state>();

      transTable = new SCG.SortedList<KeyValuePair<state, input>, state>(new Comparer());
    }

    public string Simulate(string @in)
    {
      state curState = start;

      CharEnumerator i = @in.GetEnumerator();

      while(i.MoveNext())
      {
        KeyValuePair<state, input> transition = new KeyValuePair<state, input>(curState, i.Current);

        if(!transTable.ContainsKey(transition))
          return "Rejected";

        curState = transTable[transition];
      }

      if(final.Contains(curState))
        return "Accepted";
      else
        return "Rejected";
    }

    public void Show()
    {
      Console.Write("DFA start state: {0}\n", start);
      Console.Write("DFA final state(s): ");

      SCG.IEnumerator<state> iE = final.GetEnumerator();

      while(iE.MoveNext())
        Console.Write(iE.Current + " ");

      Console.Write("\n\n");

      foreach(SCG.KeyValuePair<KeyValuePair<state, input>, state> kvp in transTable)
        Console.Write("Trans[{0}, {1}] = {2}\n", kvp.Key.Key, kvp.Key.Value, kvp.Value);
    }
  }

  /// <summary>
  /// Implements a comparer that suits the transTable SordedList
  /// </summary>
  public class Comparer : SCG.IComparer<KeyValuePair<state, input>>
  {
    public int Compare(KeyValuePair<state, input> transition1, KeyValuePair<state, input> transition2)
    {
      if(transition1.Key == transition2.Key)
        return transition1.Value.CompareTo(transition2.Value);
      else
        return transition1.Key.CompareTo(transition2.Key);
    }
  }

}

As you see, a DFA has 3 variables: a start state, a set of final states and a transition table that maps transitions between states.

Below I present the SubsetMachine class that is responsible for the hard work of extracting an equivalent DFA from a given NFA:

//
//  Regular Expression Engine C# Sample Application
//  2006, by Leniel Braz de Oliveira Macaferi & Wellington Magalhães Leite.
//
//  UBM's Computer Engineering - 7th term [http://www.ubm.br/]
//  
//  This program sample was developed and turned in as a term paper for Lab. of
//  Compilers Construction. It was based on the source code provided by Eli Bendersky
//  [http://eli.thegreenplace.net/] and is provided "as is" without warranty.
//

using System;
using SCG = System.Collections.Generic;
using C5;

using state = System.Int32;
using input = System.Char;

namespace RegularExpressionEngine
{
  class SubsetMachine
  {
    private static int num = 0;

    /// <summary>
    /// Subset machine that employs the powerset construction or subset construction algorithm.
    /// It creates a DFA that recognizes the same language as the given NFA.
    /// </summary>
    public static DFA SubsetConstruct(NFA nfa)
    {
      DFA dfa = new DFA();

      // Sets of NFA states which is represented by some DFA state
      Set<Set<state>> markedStates = new Set<Set<state>>();
      Set<Set<state>> unmarkedStates = new Set<Set<state>>();

      // Gives a number to each state in the DFA
      HashDictionary<Set<state>, state> dfaStateNum = new HashDictionary<Set<state>, state>();

      Set<state> nfaInitial = new Set<state>();
      nfaInitial.Add(nfa.initial);

      // Initially, EpsilonClosure(nfa.initial) is the only state in the DFAs states and it's unmarked.
      Set<state> first = EpsilonClosure(nfa, nfaInitial);
      unmarkedStates.Add(first);

      // The initial dfa state
      state dfaInitial = GenNewState();
      dfaStateNum[first] = dfaInitial;
      dfa.start = dfaInitial;

      while(unmarkedStates.Count != 0)
      {
        // Takes out one unmarked state and posteriorly mark it.
        Set<state> aState = unmarkedStates.Choose();

        // Removes from the unmarked set.
        unmarkedStates.Remove(aState);

        // Inserts into the marked set.
        markedStates.Add(aState);

        // If this state contains the NFA's final state, add it to the DFA's set of
        // final states.
        if(aState.Contains(nfa.final))
          dfa.final.Add(dfaStateNum[aState]);

        SCG.IEnumerator<input> iE = nfa.inputs.GetEnumerator();

        // For each input symbol the nfa knows...
        while(iE.MoveNext())
        {
          // Next state
          Set<state> next = EpsilonClosure(nfa, nfa.Move(aState, iE.Current));

          // If we haven't examined this state before, add it to the unmarkedStates and make up a new number for it.
          if(!unmarkedStates.Contains(next) && !markedStates.Contains(next))
          {
            unmarkedStates.Add(next);
            dfaStateNum.Add(next, GenNewState());
          }

          KeyValuePair<state, input> transition = new KeyValuePair<state, input>();
          transition.Key = dfaStateNum[aState];
          transition.Value = iE.Current;

          dfa.transTable[transition] = dfaStateNum[next];
        }
      }

      return dfa;
    }

    /// <summary>
    /// Builds the Epsilon closure of states for the given NFA 
    /// </summary>
    /// <param name="nfa"></param>
    /// <param name="states"></param>
    /// <returns></returns>
    static Set<state> EpsilonClosure(NFA nfa, Set<state> states)
    {
      // Push all states onto a stack
      SCG.Stack<state> uncheckedStack = new SCG.Stack<state>(states);

      // Initialize EpsilonClosure(states) to states
      Set<state> epsilonClosure = states;

      while(uncheckedStack.Count != 0)
      {
        // Pop state t, the top element, off the stack
        state t = uncheckedStack.Pop();

        int i = 0;

        // For each state u with an edge from t to u labeled Epsilon
        foreach(input input in nfa.transTable[t])
        {
          if(input == (char)NFA.Constants.Epsilon)
          {
            state u = Array.IndexOf(nfa.transTable[t], input, i);

            // If u is not already in epsilonClosure, add it and push it onto stack
            if(!epsilonClosure.Contains(u))
            {
              epsilonClosure.Add(u);
              uncheckedStack.Push(u);
            }
          }

          i = i + 1;
        }
      }

      return epsilonClosure;
    }

    /// <summary>
    /// Creates unique state numbers for DFA states
    /// </summary>
    /// <returns></returns>
    private static state GenNewState()
    {
      return num++;
    }

  }
}

In the first post of this series we see the following line of code:

DFA dfa = SubsetMachine.SubsetConstruct(nfa);

The SubsetConstruct method from the SubsetMachine class receives as input an NFA and returns a DFA.

Inside the SubsetConstruct method we firstly instantiate a new DFA object and then we create two variables markedStates and unmarkedStates that are sets of NFA states which represent a DFA state.

// Sets of NFA states which is represented by some DFA state
Set<Set<state>> markedStates = new Set<Set<state>>();
Set<Set<state>> unmarkedStates = new Set<Set<state>>();

From this we see that a DFA state can represent a set of NFA states. Take a look at the introductory post and see Figure 2. It shows two DFA states that represent sets of NFA states, in this particular case the DFA final states represent the NFA states {s2, s3} and {s5, s6}.

The HashDictionary helps us to give a name (to number) each DFA state.

// Gives a number to each state in the DFA
HashDictionary<Set<state>, state> dfaStateNum = new HashDictionary<Set<state>, state>();

We declare a variable called nfaInitial that is a set of states. It receives the initial NFA state:

Set<state> nfaInitial = new Set<state>();
nfaInitial.Add(nfa.initial);

We’ll start using the EpsilonClosure function.

// Initially, EpsilonClosure(nfa.initial) is the only state in the DFAs states and it's unmarked.
Set<state> first = EpsilonClosure(nfa, nfaInitial);

The EpsilonClosure function receives as parameters the NFA and its initial state and returns a set of states. Take a look at the method signature:

static Set<state> EpsilonClosure(NFA nfa, Set<state> states)

So, what does it do? You may ask. To answer this question let’s debug this first method call:

From the NFA transition table presented in Figure 2 and from the transition graph presented in Figure 3 in the second post of this series we can see how many transitions are represented by eps transitions.

The first time we enter into this function we’ll get as a return value a set of states that contains all the states that are reachable with an eps transition from the start state 0.

Figure 1 - States reachable by an eps transition from start state 0.

For the sake of comparison I’ll show the NFA’s graph representation for the regex (l|e)*n?(i|e)el* that we’re studying since the beginning of this series.

Figure 2 - NFA’s graph representation for the regex (l|e)*n?(i|e)el*

If you pay close attention you’ll see that the order the regex parser found the states is the order we visually debug the code looking at the graph above.

With such states found we move next adding this DFA state into the variable unmarkedStates.

We then use a function called GetNewState that is responsible for generating a number that uniquely identifies each state of the DFA:

// The initial dfa state
state dfaInitial = GenNewState();

When we pass to the next line of code we add to the dfaStateNum dictionary a key that is the set of states returned by the EpsilonClosure function and a value that is the name of the initial state of the DFA.

dfaStateNum[first] = dfaInitial;

We make the initial state of the DFA be the dfaInitial value we just got.

dfa.start = dfaInitial;

Next we enter in the first while keyword. In this while we basically extract one of the unmarkedStates and add the same to the markedStates set. This has the meaning of telling that we already checked such state.

// Takes out one unmarked state and posteriorly mark it.
Set<state> aState = unmarkedStates.Choose();

// Removes from the unmarked set.
unmarkedStates.Remove(aState);

// Inserts into the marked set.
markedStates.Add(aState);

In the next line of code (one of the most interesting parts of the whole code) we check to see if this current DFA state (remember that it is a set of states) we’re on contains the NFA final state, if it holds true, we add it to the DFA’s set of final states:

// If this state contains the NFA's final state, add it to the DFA's set of final states.
if(aState.Contains(nfa.final))
  dfa.final.Add(dfaStateNum[aState]);

Now it’s time to check against the NFA’s input symbols. To accomplish this we declare an enumerator of type state that does the job of moving through each of the input symbols in the next while code block:

SCG.IEnumerator<input> iE = nfa.inputs.GetEnumerator();

// For each input symbol the nfa knows...
while(iE.MoveNext())
{ . . .

Now it’s time to create the next DFA state. We do this by declaring a new set of states and we call the EpsilonClosure function again to fill this state, but this time we pass the EpsilonClosure function a different second parameter.

// Next state
Set<state> next = EpsilonClosure(nfa, nfa.Move(aState, iE.Current));

Let’s go deeper to take a look at this second parameter.

As you see we call the function Move that is part of the NFA class. This function receives as parameters a set of states and an input symbol to be checked against. It returns a set of states.

What the move function does is: foreach state in the set of states passed as the first parameter we check each transition present in the NFA’s transition table from this state to another state with the input symbol passed as the second parameter.

So, the first time we pass we get the following output from the Move function:

Figure 3 - Result from the NFA’s Move function the 1st time it’s called

If we look at Figure 2 we can assert that from the states present in the first state of the DFA (see Figure 1) we can move to states {5, 16} with the first NFA input that is equal to ‘e’.

With the above result taken from the Move function we’re ready to go the EpsilonClosure function for the second time to create the 2nd DFA state in the SubsetMachine class. This second time we get the following result from EpsilonClosure function:

Figure 4 - Result from the EpsilonClosure function the 2nd time it’s called

Now, if you pay close attention, we can assert that starting at the states {5, 16} we can move with an eps-transition to the states shown above. Remember that the states we pass to the EpsilonClosure function are themselves included in the result returned by the function.

Now that we have created the 2nd DFA state we check to see if it wasn’t examined yet and if it holds true we add it to the unmarkedStates variable and give a new name to this state numbering it with the GenNewState function.

// If we haven't examined this state before, add it to the unmarkedStates and make up a new number for it.
if(!unmarkedStates.Contains(next) && !markedStates.Contains(next))
{
  unmarkedStates.Add(next);
  dfaStateNum.Add(next, GenNewState());
}

Now the best part of it. :)

We create a new transition that has as key the number of the DFA state we’re checking and as the value the current input symbol we’re after.

KeyValuePair<state, input> transition = new KeyValuePair<state, input>();
transition.Key = dfaStateNum[aState];
transition.Value = iE.Current;

We then add this transition to the DFA’s transition table:

Figure 5 - DFA’s transition table

This has the following meaning: from state 0 with input ‘e’ go to state 1!

These are the subsequent values we get for the first unmarkedState we’re checking:

With input ‘i’ we can go to state { 14 } from which with an eps transition we can go to state { 17 }.

With input ‘l’ we can go to state { 3 } from which with an eps transition we can go to states { 4, 13, 8, 3, 12, 7, 2, 11, 6, 1, 15, 10 }.

With input ‘n’ we can go to state { 9 } from which with an eps transition we can go to states { 12, 9, 13, 15 }.

A point that deserves consideration is that each time you run the regex parser it’s not guaranteed that the numbers that identify the DFA states will remain the same.

I won’t continue debugging because it would consume a lot of space in this blog post.

I think that with the above explanation it’s easy to get the point.

In short we’ll repeat the above steps for each unmarked state that hasn’t been checked yet working with it against each input symbol.

For the regex (l|e)*n?(i|e)el* in one of the times I ran the code, I got the following DFA’s transition table:

DFA start state: 0
DFA final state(s): 7 8 9 10

Trans[0, e] = 1

Trans[0, i] = 2

Trans[0, l] = 3

Trans[0, n] = 4

Trans[1, e] = 7

Trans[1, i] = 2

Trans[1, l] = 3

Trans[1, n] = 4

Trans[2, e] = 8

Trans[2, i] = 6

Trans[2, l] = 6

Trans[2, n] = 6

Trans[3, e] = 1

Trans[3, i] = 2

Trans[3, l] = 3

Trans[3, n] = 4

Trans[4, e] = 5

Trans[4, i] = 2

Trans[4, l] = 6

Trans[4, n] = 6

Trans[5, e] = 8

Trans[5, i] = 6

Trans[5, l] = 6

Trans[5, n] = 6

Trans[6, e] = 6

Trans[6, i] = 6

Trans[6, l] = 6

Trans[6, n] = 6

Trans[7, e] = 7

Trans[7, i] = 2

Trans[7, l] = 10

Trans[7, n] = 4

Trans[8, e] = 6

Trans[8, i] = 6

Trans[8, l] = 9

Trans[8, n] = 6

Trans[9, e] = 6

Trans[9, i] = 6

Trans[9, l] = 9

Trans[9, n] = 6

Trans[10, e] = 1

Trans[10, i] = 2

Trans[10, l] = 10

Trans[10, n] = 4

Figure 6 - DFA’s transition table for the regex (l|e)*n?(i|e)el*

Below is the DFA’s graph representation:

Figure 7 - DFA’s graph representation for the regex (l|e)*n?(i|e)el*

In the next post I’ll simulate some input strings against this DFA to assert its validity.

See you there!

Updated on 5/12/2009 09:57:00 PM

As I finished writing the posts, here goes the list that points to them:

Regular Expression Engine in C# (the Story)
Regex engine in C# - the Regex Parser
Regex engine in C# - the NFA
Regex engine in C# - matching strings

Regex engine in C# - the NFA

2009-04-13T01:04:00.002-03:00

As promised, let’s dive into the NFA’s class. To understand what’s an NFA, refer to the first post in this series called Regex engine in C# - the Regex Parser.

Last time we ended with the main Regex Engine class (RegexParser) which delegates to the NFA class the logic for constructing the NFA based on the parse tree we got on the last post.

The following is the NFA class:

//
//  Regular Expression Engine C# Sample Application
//  2006, by Leniel Braz de Oliveira Macaferi & Wellington Magalhães Leite.
//
//  UBM's Computer Engineering - 7th term [http://www.ubm.br/]
//  
//  This program sample was developed and turned in as a term paper for Lab. of
//  Compilers Construction. It was based on the source code provided by Eli Bendersky
//  [http://eli.thegreenplace.net/] and is provided "as is" without warranty.
//
//  It makes use of C5 collections library (see reference at the end of this post.)
//

using System;
using SCG = System.Collections.Generic;
using C5;

using state = System.Int32;
using input = System.Char;

namespace RegularExpressionEngine
{

  /// <summary>
  /// Implements a non-deterministic finite automata
  /// </summary>
  class NFA
  {
    public state initial;
    public state final;
    private int size;
    // Inputs this NFA responds to
    public SortedArray<input> inputs;
    public input[][] transTable;

    /// <summary>
    /// Provides default values for epsilon and none
    /// </summary>
    public enum Constants
    {
      Epsilon = 'ε',
      None = '\0'
    }

    public NFA(NFA nfa)
    {
      initial = nfa.initial;
      final = nfa.final;
      size = nfa.size;
      inputs = nfa.inputs;
      transTable = nfa.transTable;
    }

    /// <summary>
    /// Constructed with the NFA size (amount of states), the initial state and the
    /// final state
    /// </summary>
    /// <param name="size_">Amount of states.</param>
    /// <param name="initial_">Initial state.</param>
    /// <param name="final_">Final state.</param>
    public NFA(int size_, state initial_, state final_)
    {
      initial = initial_;
      final = final_;
      size = size_;

      IsLegalState(initial);
      IsLegalState(final);

      inputs = new SortedArray<input>();

      // Initializes transTable with an "empty graph", no transitions between its
      // states
      transTable = new input[size][];

      for(int i = 0; i < size; ++i)
        transTable[i] = new input[size];
    }

    public bool IsLegalState(state s)
    {
      // We have 'size' states, numbered 0 to size-1
      if(s < 0 || s >= size)
        return false;

      return true;
    }

    /// <summary>
    /// Adds a transition between two states.
    /// </summary>
    /// <param name="from"></param>
    /// <param name="to"></param>
    /// <param name="in"></param>
    public void AddTrans(state from, state to, input @in)
    {
      IsLegalState(from);
      IsLegalState(to);

      transTable[from][to] = @in;

      if(@in != (char)Constants.Epsilon)
        inputs.Add(@in);
    }

    /// <summary>
    /// Fills states 0 up to other.size with other's states.
    /// </summary>
    /// <param name="other"></param>
    public void FillStates(NFA other)
    {
      for(state i = 0; i < other.size; ++i)
        for(state j = 0; j < other.size; ++j)
          transTable[i][j] = other.transTable[i][j];

      SCG.IEnumerator<input> cE = other.inputs.GetEnumerator();

      while(cE.MoveNext())
        inputs.Add(cE.Current);
    }

    /// <summary>
    /// Renames all the NFA's states. For each nfa state: number += shift.
    /// Functionally, this doesn't affect the NFA, it only makes it larger and renames
    /// its states.
    /// </summary>
    /// <param name="shift"></param>
    public void ShiftStates(int shift)
    {
      int newSize = size + shift;

      if(shift < 1)
        return;

      // Creates a new, empty transition table (of the new size).
      input[][] newTransTable = new input[newSize][];

      for(int i = 0; i < newSize; ++i)
        newTransTable[i] = new input[newSize];

      // Copies all the transitions to the new table, at their new locations.
      for(state i = 0; i < size; ++i)
        for(state j = 0; j < size; ++j)
          newTransTable[i + shift][j + shift] = transTable[i][j];

      // Updates the NFA members.
      size = newSize;
      initial += shift;
      final += shift;
      transTable = newTransTable;
    }

    /// <summary>
    /// Appends a new, empty state to the NFA.
    /// </summary>
    public void AppendEmptyState()
    {
      transTable = Resize(transTable, size + 1);

      size += 1;
    }

    private static input[][] Resize(input[][] transTable, int newSize)
    {
      input[][] newTransTable = new input[newSize][];

      for(int i = 0; i < newSize; ++i)
        newTransTable[i] = new input[newSize];

      for(int i = 0; i <= transTable.Length - 1; i++)
        for(int j = 0; j <= transTable[i].Length - 1; j++)
        {
          if(transTable[i][j] != '\0')
            newTransTable[i][j] = transTable[i][j];
        }

      return newTransTable;
    }

    /// <summary>
    /// Returns a set of NFA states from which there is a transition on input symbol
    /// inp from some state s in states.
    /// </summary>
    /// <param name="states"></param>
    /// <param name="inp"></param>
    /// <returns></returns>
    public Set<state> Move(Set<state> states, input inp)
    {
      Set<state> result = new Set<state>();

      // For each state in the set of states
      foreach(state state in states)
      {
        int i = 0;

        // For each transition from this state
        foreach(input input in transTable[state])
        {
          // If the transition is on input inp, add it to the resulting set
          if(input == inp)
          {
            state u = Array.IndexOf(transTable[state], input, i);
            result.Add(u);
          }

          i = i + 1;
        }
      }

      return result;
    }

    /// <summary>
    /// Prints out the NFA.
    /// </summary>
    public void Show()
    {
      Console.WriteLine("This NFA has {0} states: 0 - {1}", size, size - 1);
      Console.WriteLine("The initial state is {0}", initial);
      Console.WriteLine("The final state is {0}\n", final);

      for(state from = 0; from < size; ++from)
      {
        for(state to = 0; to < size; ++to)
        {
          input @in = transTable[from][to];

          if(@in != (char)Constants.None)
          {
            Console.Write("Transition from {0} to {1} on input ", from, to);

            if(@in == (char)Constants.Epsilon)
              Console.Write("Epsilon\n");
            else
              Console.Write("{0}\n", @in);
          }
        }
      }
      Console.Write("\n\n");
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="tree"></param>
    /// <returns></returns>
    public static NFA TreeToNFA(ParseTree tree)
    {
        switch (tree.type)
        {
            case ParseTree.NodeType.Chr:
                return BuildNFABasic(tree.data.Value);
            case ParseTree.NodeType.Alter:
                return BuildNFAAlter(TreeToNFA(tree.left), TreeToNFA(tree.right));
            case ParseTree.NodeType.Concat:
                return BuildNFAConcat(TreeToNFA(tree.left), TreeToNFA(tree.right));
            case ParseTree.NodeType.Star:
                return BuildNFAStar(TreeToNFA(tree.left));
            case ParseTree.NodeType.Question:
                return BuildNFAAlter(TreeToNFA(tree.left), BuildNFABasic((char)Constants.Epsilon));
            default:
                return null;
        }
    }

    /////////////////////////////////////////////////////////////////
    //
    // NFA building functions
    //
    // Using Thompson Construction, build NFAs from basic inputs or 
    // compositions of other NFAs.
    //

    /// <summary>
    /// Builds a basic, single input NFA
    /// </summary>
    /// <param name="in"></param>
    /// <returns></returns>
    public static NFA BuildNFABasic(input @in)
    {
      NFA basic = new NFA(2, 0, 1);

      basic.AddTrans(0, 1, @in);

      return basic;
    }

    /// <summary>
    /// Builds an alternation of nfa1 and nfa2 (nfa1|nfa2)
    /// </summary>
    /// <param name="nfa1"></param>
    /// <param name="nfa2"></param>
    /// <returns></returns>
    public static NFA BuildNFAAlter(NFA nfa1, NFA nfa2)
    {
      // How this is done: the new nfa must contain all the states in
      // nfa1 and nfa2, plus a new initial and final states. 
      // First will come the new initial state, then nfa1's states, then
      // nfa2's states, then the new final state

      // make room for the new initial state
      nfa1.ShiftStates(1);

      // make room for nfa1
      nfa2.ShiftStates(nfa1.size);

      // create a new nfa and initialize it with (the shifted) nfa2
      NFA newNFA = new NFA(nfa2);

      // nfa1's states take their places in new_nfa
      newNFA.FillStates(nfa1);

      // Set new initial state and the transitions from it
      newNFA.AddTrans(0, nfa1.initial, (char)Constants.Epsilon);
      newNFA.AddTrans(0, nfa2.initial, (char)Constants.Epsilon);

      newNFA.initial = 0;

      // Make up space for the new final state
      newNFA.AppendEmptyState();

      // Set new final state
      newNFA.final = newNFA.size - 1;

      newNFA.AddTrans(nfa1.final, newNFA.final, (char)Constants.Epsilon);
      newNFA.AddTrans(nfa2.final, newNFA.final, (char)Constants.Epsilon);

      return newNFA;
    }

    /// <summary>
    /// Builds an alternation of nfa1 and nfa2 (nfa1|nfa2)
    /// </summary>
    /// <param name="nfa1"></param>
    /// <param name="nfa2"></param>
    /// <returns></returns>
    public static NFA BuildNFAConcat(NFA nfa1, NFA nfa2)
    {
      // How this is done: First will come nfa1, then nfa2 (its initial state replaced
      // with nfa1's final state)
      nfa2.ShiftStates(nfa1.size - 1);

      // Creates a new NFA and initialize it with (the shifted) nfa2
      NFA newNFA = new NFA(nfa2);

      // nfa1's states take their places in newNFA
      // note: nfa1's final state overwrites nfa2's initial state,
      // thus we get the desired merge automatically (the transition
      // from nfa2's initial state now transits from nfa1's final state)
      newNFA.FillStates(nfa1);

      // Sets the new initial state (the final state stays nfa2's final state,
      // and was already copied)
      newNFA.initial = nfa1.initial;

      return newNFA;
    }

    /// <summary>
    /// Builds a star (kleene closure) of nfa (nfa*)
    /// How this is done: First will come the new initial state, then NFA, then the new final state
    /// </summary>
    /// <param name="nfa"></param>
    /// <returns></returns>
    public static NFA BuildNFAStar(NFA nfa)
    {
      // Makes room for the new initial state
      nfa.ShiftStates(1);

      // Makes room for the new final state
      nfa.AppendEmptyState();

      // Adds new transitions
      nfa.AddTrans(nfa.final, nfa.initial, (char)Constants.Epsilon);
      nfa.AddTrans(0, nfa.initial, (char)Constants.Epsilon);
      nfa.AddTrans(nfa.final, nfa.size - 1, (char)Constants.Epsilon);
      nfa.AddTrans(0, nfa.size - 1, (char)Constants.Epsilon);

      nfa.initial = 0;
      nfa.final = nfa.size - 1;

      return nfa;
    }
  }

}

We pass the parse tree (see last post) to a function responsible for converting the parse tree to an NFA.

private NFA TreeToNFA(ParseTree tree)
{
  switch(tree.type)
  {
    case ParseTree.NodeType.Chr:
      return BuildNFABasic(tree.data.Value);
    case ParseTree.NodeType.Alter:
      return BuildNFAAlter(TreeToNFA(tree.left), TreeToNFA(tree.right));
    case ParseTree.NodeType.Concat:
      return BuildNFAConcat(TreeToNFA(tree.left), TreeToNFA(tree.right));
    case ParseTree.NodeType.Star:
      return BuildNFAStar(TreeToNFA(tree.left));
    case ParseTree.NodeType.Question:
      return BuildNFAAlter(TreeToNFA(tree.left), BuildNFABasic((char)Constants.Epsilon));
    default:
      return null;
  }
}

The TreeToNFA function delegates to the building functions that employ Thompson Construction to build the NFA from basic inputs or compositions of other NFAs.

TreeToNFA is recursive! It calls itself, that is, the calls are put into the stack. Debug the code to see how it works.

The building functions are well documented. Take a look at the comments in the code above.

While debugging the code we get the following variables’ structure:

Figure 1 - Variables' structure while in debugging mode

From the above picture we see that there’s a transition from state 8 to state 9 with the input symbol ‘n’.

The NFA’s Show function will only output something if the transition’s value present in the transTable variable is different from 0 ‘\0’, that is, if there’s indeed a transition from one state to another.

So, for the regex (l|e)*n?(i|e)el* we get the following transition table:

This NFA has 22 states: 0 - 21
The initial state is 0
The final state is 21

Transition from 0 to 1 on input Epsilon

Transition from 0 to 7 on input Epsilon

Transition from 1 to 2 on input Epsilon

Transition from 1 to 4 on input Epsilon

Transition from 2 to 3 on input l

Transition from 3 to 6 on input Epsilon

Transition from 4 to 5 on input e

Transition from 5 to 6 on input Epsilon

Transition from 6 to 1 on input Epsilon

Transition from 6 to 7 on input Epsilon

Transition from 7 to 8 on input Epsilon

Transition from 7 to 10 on input Epsilon

Transition from 8 to 9 on input n

Transition from 9 to 12 on input Epsilon

Transition from 10 to 11 on input Epsilon

Transition from 11 to 12 on input Epsilon

Transition from 12 to 13 on input Epsilon

Transition from 12 to 15 on input Epsilon

Transition from 13 to 14 on input i

Transition from 14 to 17 on input Epsilon

Transition from 15 to 16 on input e

Transition from 16 to 17 on input Epsilon

Transition from 17 to 18 on input e

Transition from 18 to 19 on input Epsilon

Transition from 18 to 21 on input Epsilon

Transition from 19 to 20 on input l

Transition from 20 to 19 on input Epsilon

Transition from 20 to 21 on input Epsilon

Figure 2 - NFA’s transition table for the regex (l|e)*n?(i|e)el*

This is the NFA’s graph representation:

Figure 3 - NFA’s graph representation for the regex (l|e)*n?(i|e)el*

As you see, some states have an eps-transition – eps or epsilon (ε) that represents "nothing" or "no input". This is absolutely valid in an NFA.

Next time we’ll dive into the DFA class that uses a subset machine to construct a DFA based on an NFA.

See you there!

Updated on 5/12/2009 09:54:00 PM

As I finished writing the posts, here goes the list that points to them:

Regular Expression Engine in C# (the Story)
Regex engine in C# - the Regex Parser
Regex engine in C# - the DFA
Regex engine in C# - matching strings

References
[1] Kokholm, Niels; Sestoft, Peter. The C5 Generic Collection Library for C# and CLI. Available at <http://www.itu.dk/research/c5/>. Accessed on May 2, 2008.

Regex engine in C# - the Regex Parser

2009-02-24T21:25:00.001-03:00

I really like to study theory of computation. This series of posts show how much I like it! :)

Following the open post titled Regular Expression Engine in C# (the Story), let’s begin this endeavor with the definition of the words most used from now on:

State
A state is a unique configuration of information in a program or machine.

Finite State Machine (FSM)
A finite state machine is a model of behavior composed of a finite number of states, transitions between those states, and actions. It’s an abstract model of a machine with a primitive internal memory.

Nondeterministic Finite Automaton (NFA)
A nondeterministic finite automaton is a finite state machine where for each pair of state and input symbol there may be several possible next states.

Its mathematical model is as follow:
1. A set of states (S)
2. A set of input symbols - the input symbol alphabet (Σ)
3. A transition function that maps state-symbol pairs to a given state T : S × Σ → P(S)
4. A state s0 that is the start state s₀ ∈ S
5. A set of states that are the final states F ⊆ S

The following example explains a NFA M, with a 2 letters alphabet.

Let M = (Q, Σ, T, s₀, F) where:

Σ = { a, b }
Q = { s₀, s₁, s₂, s₃, s₄, s₅, s₆, s₇}
E({ s₀}) = { s₀, s₁, s₄ }
F = { s₇}
The transition function T can be defined by this state transition table:

State	a	b	ε
s0	{}	{}	{s1, s4}
s1	{s2}	{}	{}
s2	{s2, s3}	{s2}	{}
s3	{}	{}	{s7}
s4	{}	{s5}	{}
s5	{s5}	{s5, s6}	{}
s6	{}	{}	{s7}
s7	{}	{}	{}

Figure 1 - NFA example with 8 states

Deterministic Finite Automaton (DFA)
A deterministic finite automaton is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state.

Its mathematical model is as follow:
1. A finite set of states (S)
2. A finite set called the alphabet (Σ)
3. A transition function (δ : S × Σ → S)
4. A start state (s0 ∈ S)
5. A set of accept final states (F ⊆ S)
6. No state has an eps-transition – eps or epsilon (ε) represents "nothing" or "no input".
7. For each state S and input x, there is at most one edge labeled x leaving S.

Figure 2 - DFA equivalent to the NFA shown in Figure 1

DFA versus NFA
Despite the fact that the DFA and NFA have distinct definitions, it may be shown in the formal theory that they are equivalent, in that, for any given NFA, one may construct an equivalent DFA, and vice-versa: this is the powerset construction.

Both types of automata recognize only regular languages.

DFA + NFA = FSM

Regular Expression (regex)
A regular expression provide a concise and flexible means for identifying strings of text of interest, such as particular characters, words, or patterns of characters. Regular expressions are written in a formal language that can be interpreted by a regular expression processor (engine), a program that either serves as a parser generator or examines text and identifies parts that match the provided pattern (regex).

A regex (any regex!) can be represented as a FSM.

Some symbols you’ll encounter in regexes and their meanings:

Alternation: A vertical bar separates alternatives. For example, gray|grey can match "gray" or "grey".
Grouping: Parentheses are used to define the scope and precedence of the operators (among other uses). For example, gray|grey and gr(a|e)y are equivalent patterns which both describe the set of "gray" and "grey".
Quantification: A quantifier after a token (such as a character) or group specifies how often that preceding element is allowed to occur. The most common quantifiers are the question mark ?, the asterisk * and the plus sign +.

? = zero or one of the preceding element.
Example: colou?r matches both "color" and "colour".

* = zero or more of the preceding element.
Example: ab*c matches "ac", "abc", "abbc", "abbbc", and so on.

+ = one or more of the preceding element.
Example: ab+c matches "abc", "abbc", "abbbc", and so on, but not "ac".

After reading this we should be able to answer the following question:

What is the regular expression that describes the machine M shown in Figure 1 above?

The language of M can be described by the regular language given by this regular expression: (a|b)(a|b)*(a|b)

The Regex Parser
Let me show you some code.

As I’ve written in Regular Expression Engine in C# (the Story), I’ll present the code in a top-down approach, that is, from the higher level class to its dependencies.

The RegexParser class:

//
//    Regular Expression Engine C# Sample Application
//    2006, by Leniel Braz de Oliveira Macaferi & Wellington Magalhães Leite.
//
//  UBM's Computer Engineering - 7th term [http://www.ubm.br/]
//  
//  This program sample was developed and turned in as a term paper for Lab. of
//  Compilers Construction. It was based on the source code provided by Eli Bendersky
//  [http://eli.thegreenplace.net/] and is provided "as is" without warranty.
//

using System;
using System.Text;

namespace RegularExpressionEngine
{
  /// <summary>
  /// Implements a parser for a given regular expression.
  /// </summary>
  class RegexParser
  {
    private string data;
    private int next;

    /// <summary>
    /// 
    /// </summary>
    /// <param name="data"></param>
    private void Init(string data)
    {
      this.data = Preprocess(data);
      next = 0;
    }

    /// <summary>
    /// 
    /// </summary>
    /// <returns></returns>
    private char Peek()
    {
      return (next < data.Length) ? data[next] : '\0';
    }

    /// <summary>
    /// 
    /// </summary>
    /// <returns></returns>
    private char Pop()
    {
      char cur = Peek();

      if(next < data.Length)
        ++next;

      return cur;
    }

    /// <summary>
    /// 
    /// </summary>
    /// <returns></returns>
    private int GetPos()
    {
      return next;
    }

    /// <summary>
    /// Generates concatenation chars ('.') where appropriate.
    /// </summary>
    /// <param name="in"></param>
    /// <returns></returns>
    private string Preprocess(string @in)
    {
      StringBuilder @out = new StringBuilder();

      CharEnumerator c, up;
      c = @in.GetEnumerator();
      up = @in.GetEnumerator();

      up.MoveNext();

      // In this loop c is the current char of in, up is the next one.
      while(up.MoveNext())
      {
        c.MoveNext();

        @out.Append(c.Current);

        if((char.IsLetterOrDigit(c.Current) || c.Current == ')' || c.Current == '*' ||
          c.Current == '?') && (up.Current != ')' && up.Current != '|' &&
          up.Current != '*' && up.Current != '?'))
          @out.Append('.');
      }

      // Don't forget the last char...
      if(c.MoveNext())
        @out.Append(c.Current);

      return @out.ToString();
    }

    /// <summary>
    /// 
    /// </summary>
    /// <param name="node"></param>
    /// <param name="offset"></param>
    private static void PrintTree(ParseTree node, int offset)
    {
      if(node == null)
        return;

      for(int i = 0; i < offset; ++i)
        Console.Write(" ");

      switch(node.type)
      {
        case ParseTree.NodeType.Chr:
          Console.WriteLine(node.data);
          break;
        case ParseTree.NodeType.Alter:
          Console.WriteLine("|");
          break;
        case ParseTree.NodeType.Concat:
          Console.WriteLine(".");
          break;
        case ParseTree.NodeType.Question:
          Console.WriteLine("?");
          break;
        case ParseTree.NodeType.Star:
          Console.WriteLine("*");
          break;
      }

      Console.Write("");

      PrintTree(node.left, offset + 8);
      PrintTree(node.right, offset + 8);
    }

    /// <summary>
    /// RD parser
    /// char ::= alphanumeric character (letter or digit)
    /// </summary>
    /// <returns></returns>
    private ParseTree Chr()
    {
      char data = Peek();

      if(char.IsLetterOrDigit(data) || data == '\0')
      {
        return new ParseTree(ParseTree.NodeType.Chr, this.Pop(), null, null);
      }
      else
      {
        Console.WriteLine("Parse error: expected alphanumeric, got {0} at #{1}",
        Peek(), GetPos());

        Console.ReadKey();

        Environment.Exit(1);

        return null;
      }
    }

    /// <summary>
    /// atom ::= char | '(' expr ')'
    /// </summary>
    /// <returns></returns>
    private ParseTree Atom()
    {
      ParseTree atomNode;

      if(Peek() == '(')
      {
        Pop();

        atomNode = Expr();

        if(Pop() != ')')
        {
          Console.WriteLine("Parse error: expected ')'");

          Environment.Exit(1);
        }
      }
      else
        atomNode = Chr();

      return atomNode;
    }

    /// <summary>
    /// rep ::= atom '*' | atom '?' | atom
    /// </summary>
    /// <returns></returns>
    private ParseTree Rep()
    {
      ParseTree atomNode = Atom();

      if(Peek() == '*')
      {
        Pop();

        ParseTree repNode = new ParseTree(ParseTree.NodeType.Star, null, atomNode, null);

        return repNode;
      }
      else if(Peek() == '?')
      {
        Pop();

        ParseTree repNode = new ParseTree(ParseTree.NodeType.Question, ' ', atomNode, null);

        return repNode;
      }
      else
        return atomNode;
    }

    /// <summary>
    /// concat ::= rep . concat | rep
    /// </summary>
    /// <returns></returns>
    private ParseTree Concat()
    {
      ParseTree left = Rep();

      if(Peek() == '.')
      {
        Pop();

        ParseTree right = Concat();

        ParseTree concatNode = new ParseTree(ParseTree.NodeType.Concat, null, left, right);

        return concatNode;
      }
      else
        return left;
    }

    /// <summary>
    /// expr   ::= concat '|' expr | concat
    /// </summary>
    /// <returns></returns>
    private ParseTree Expr()
    {
      ParseTree left = Concat();

      if(Peek() == '|')
      {
        Pop();

        ParseTree right = Expr();

        ParseTree exprNode = new ParseTree(ParseTree.NodeType.Alter, null, left, right);

        return exprNode;
      }
      else
        return left;
    }

    /// <summary>
    /// The main entry point of the Console Application
    /// </summary>
    /// <param name="args"></param>
    static void Main(string[] args)
    {
      if(args.Length != 3)
      {
        Console.WriteLine("Call with the regex as an argument.");

        Environment.Exit(1);
      }

      RegexParser myRegexParser = new RegexParser();

      // Passing the regex to be preprocessed.
      myRegexParser.Init(args[1]);

      // Creating a parse tree with the preprocessed regex
      ParseTree parseTree = myRegexParser.Expr();

      // Checking for a string termination character after
      // parsing the regex
      if(myRegexParser.Peek() != '\0')
      {
        Console.WriteLine("Parse error: unexpected char, got {0} at #{1}",

        myRegexParser.Peek(), myRegexParser.GetPos());

        Environment.Exit(1);
      }

      PrintTree(parseTree, 1);

      NFA nfa = NFA.TreeToNFA(parseTree);

      nfa.Show();

      DFA dfa = SubsetMachine.SubsetConstruct(nfa);

      dfa.Show();

      Console.Write("\n\n");

      Console.Write("Result: {0}", dfa.Simulate(args[2]));

      Console.ReadKey();
    }

  }
}

From the Main entry point above in the code you can see that it’s a console application that starts with 3 arguments (parameters). For example, the parameters could be:

RegularExpressionEngine "(l|e)*n?(i|e)el*" leniel

Where:

1st param = RegularExpressionEngine = name of the program (executable)

2nd param = (l|e)*n?(i|e)el* = the pattern (regex) to match (to check against)

3rd param = leniel = the input that will be tested against the regex

Next we instantiate a new RegexParser and call its Init method passing to it the second parameter - (l|e)*n?(i|e)el* - that is located at the index 1 position within the string[] args array.

At the Init method we set the variable data with the resulting string of the Preprocess() method, which as the name suggests preprocesses the regex so that we can translate it to an appropriate format to create a parse tree.

This is the preprocessed data we get for the regex: (l|e)*.n?.(i|e).e.l*

Note that it adds dots (.) where appropriate.

The regex engine presented here uses . for concatenation, | for alternation, and * for star. So, the regex (l|e)*n?(i|e)el* can be represented in a tree form, just like an arithmetic expression.

We then create a ParseTree that is nothing more than a data structure.

The ParseTree class:

using System;
using System.Text;

using input = System.Char;

namespace RegularExpressionEngine
{
  /// <summary>
  /// Parse tree
  /// </summary>
  class ParseTree
  {
    public enum NodeType
    {
      Chr,
      Star,
      Question,
      Alter,
      Concat
    }
    
    public NodeType type;
    public input? data;
    public ParseTree left;
    public ParseTree right;

    public ParseTree(NodeType type_, input? data_, ParseTree left_, ParseTree right_)
    {
      type = type_;
      data = data_;
      left = left_;
      right = right_;
    }
  }
}

The local variable parseTree is generated through the result we get from the Expr() method. This method reads the preprocessed regex to create a parse tree that will be used further to create an NFA.

If you look at the ParseTree class you’ll se that it has four properties: a nodeType, the input symbol (a character) and a left and right ParseTree. It’s a parse tree made of parse trees if you get the point.

The property nodeType stores the type of the node that can be one of four types represented by the enum NodeType.

The parse tree is created in four methods that also return a ParseTree. These methods are: Atom(), Chr(), Concat(), and Rep().

The order in which the afore mentioned methods are called is the following:

Expr() calls Concat() that calls Rep() that calls Atom(). Note that Atom() can call Expr() again in case the first character of the regex be a grouping symbol “(“.

These are the rules we must abide to create our parse tree:

/// <summary>
/// expr   ::= concat '|' expr | concat
/// </summary>
/// <returns></returns>
private ParseTree Expr()
{
  ParseTree left = Concat();

  if(Peek() == '|')
  {
    Pop();

    ParseTree right = Expr();

    ParseTree exprNode = new ParseTree(ParseTree.NodeType.Alter, null, left, right);

    return exprNode;
  }
  else
    return left;
}

We call the method Concat() within Expr():

/// <summary>
/// concat ::= rep . concat | rep
/// </summary>
/// <returns></returns>
private ParseTree Concat()
{
  ParseTree left = Rep();

  if(Peek() == '.')
  {
    Pop();

    ParseTree right = Concat();

    ParseTree concatNode = new ParseTree(ParseTree.NodeType.Concat, null, left, right);
    
    return concatNode;
  }
  else
    return left;
}

Then we call Rep() within Concat():

/// <summary>
/// rep ::= atom '*' | atom '?' | atom
/// </summary>
/// <returns></returns>
private ParseTree Rep()
{
  ParseTree atomNode = Atom();

  if(Peek() == '*')
  {
    Pop();

    ParseTree repNode = new ParseTree(ParseTree.NodeType.Star, null, atomNode, null);

    return repNode;
  }
  else if(Peek() == '?')
  {
    Pop();

    ParseTree repNode = new ParseTree(ParseTree.NodeType.Question, ' ', atomNode, null);

    return repNode;
  }
  else
    return atomNode;
}

The Atom() method is called within Rep():

/// <summary>
/// atom ::= chr | '(' expr ')'
/// </summary>
/// <returns></returns>
private ParseTree Atom()
{
  ParseTree atomNode;

  if(Peek() == '(')
  {
    Pop();

    atomNode = Expr();

    if(Pop() != ')')
    {
      Console.WriteLine("Parse error: expected ')'");

      Environment.Exit(1);
    }
  }
  else
    atomNode = Chr();

  return atomNode;
}

An interesting thing to note is that we’re using recursive calls in two methods: Expr() and Concat(). A method is recursive if it calls itself.

In Concat() we use the Peek() method to verify if the first character of the regex is an open round bracket ‘(‘. Peek() doesn’t increment the counter variable next used to access a symbol located at the index appointed by next within the data variable (the preprocessed regex). It only returns the symbol (a char).

If the first character is an ‘(‘, then we use the Pop() method to get the next character to be checked and increment the counter variable next.

As you can see in the Atom() method, we call the Expr() method again, which will then iterate all over, that is, build the tree downward.

In case the parser doesn’t find a group character ‘(‘ we fall within the else statement and then the atomNode which is itself a parse tree will receive a ParseTree object that contains a symbol.

/// <summary>
/// RD parser
/// char ::= alphanumeric character
/// </summary>
/// <returns></returns>
private ParseTree Chr()
{
  char data = Peek();

  if(char.IsLetterOrDigit(data) || data == '\0')
  {
    return new ParseTree(ParseTree.NodeType.Chr, this.Pop(), null, null);
  }
  else
  {
    Console.WriteLine("Parse error: expected alphanumeric, got {0} at #{1}",
    Peek(), GetPos());

    Environment.Exit(1);

    return null;
  }
}

We check to see if the character peeked is a letter or digit or a character that signalizes the end of a string ‘\0’. In case it is we return a new object of type ParseTree, passing to its constructor the type of the node and the symbol it’ll store. We pass null to the last two parameters because in the case of an alphanumeric (letter or digit) the node created will be a leaf node. For more on this, read the article about parse trees.

This is the parse tree we get if we execute the program with the regex
(l|e)*n?(i|e)el*:

.
        *
                |
                        l
                        e
        .
                ?
                        n
                .
                        |
                                i
                                e
                        .
                                e
                                *
                                        l

In the next post we’ll generate a NFA with this tree. I’ll then present the NFA class.

Updated on 5/12/2009 09:50:00 PM

As I finished writing the series of posts, here goes the list that points to them:

Regular Expression Engine in C# (the Story)
Regex engine in C# - the NFA
Regex engine in C# - the DFA
Regex engine in C# - matching strings

References
[1] Bendersky, Eli. Algorithmic Forays - Part 1. March 7, 2004. Available at <http://www.gamedev.net/reference/programming/features/af1>. Accessed on February 24, 2008.

[2] Bendersky, Eli. Algorithmic Forays - Part 2. March 29, 2004. Available at <http://www.gamedev.net/reference/programming/features/af2>. Accessed on February 24, 2008.

[3] Bendersky, Eli. Algorithmic Forays - Part 3. April 28, 2004. Available at <http://www.gamedev.net/reference/programming/features/af3>. Accessed on February 24, 2008.

[4] Bendersky, Eli. Algorithmic Forays - Part 4. June 7, 2004. Available at <http://www.gamedev.net/reference/programming/features/af4>. Accessed on February 24, 2008.

[5] Bendersky, Eli. Algorithmic Forays - Part 5. August 17, 2004. Available at <http://www.gamedev.net/reference/programming/features/af5>. Accessed on February 24, 2008.

[6] Bendersky, Eli. Algorithmic Forays - Part 6. November 4, 2004. Available at <http://www.gamedev.net/reference/programming/features/af6>. Accessed on February 24, 2008.

Regular Expression Engine in C# (the Story)

2009-02-23T03:36:00.001-03:00

A “long time ago”, more precisely 3 years ago, I was studying Automata and Formal Languages which was a Computer Engineering discipline in the 6th semester out of 10 at UBM.

At that time I was amazed by the new things I was learning such as NFA - Nondetermistic Finite Automaton, DFA - Deterministic Finite Automaton, Finite State Machine and Regular Expressions. For more on this, read my last post: Fortran Numerical Constants Recognizer.

For the sake of my development I started searching for programming related material that could put me informed about such amazing computer science constructs.

I then came across a series of articles at GameDev.net called Algorithmic Forays. It’s been written by Eli Bendersky. This guy did a great job putting together the base for a Regular Expression Engine that exercise the concepts of NFA and DFA. His code was presented in C++ and I took the time to learn a bit more about this powerful language too.

After reading Algorithmic Forays from part 1 through part 6 I started thinking about translating the code from C++ to C#. That’d be a great opportunity to grasp new C# constructs and at the same time get in touch with material related to the discipline afore mentioned.

Setting that in my mind I put my hands at work and after struggling here and there I got the code translated. I also thought about writing a Portuguese version of the article to be publicized at my university’s scientific magazine. The idea was to write an adapted version of the article presenting both code (C++ and C#) showing how to achieve the same results using different programming languages data structures.

I’ve sent a message to Eli asking him permission to write a Portuguese version of the article. You can read the e-mail I’ve sent Eli and his reply below:

Leniel Macaferi <le@…>

Algorithmic Forays for a Regex Parser

le@... <le@...> Wed, Jan 3, 2007 at 5:43 AM

To: eli…@…

Cc: Wellington Magalhães Leite <wml@…>

Dear Eli,

My name is Leniel and I'm a student of Computer Engineering here in
Brazil. I'm currently in the 9th term out of 10.
You can see my basic profile at
http://www.codeproject.com/script/profile/whos_who.asp?id=1224713

Today I'm on my vacation and I'm going to come back studying on February.

I'm passionate for anything related to technology and specially
programming which is my hobby just like yours.

Firstly I'd like to congratulate you by your advanced knowledge of
such great topics about Computer Science and Computer Engineering like
the one you discussed in the article Algorithmic Forays - Part 1 to 6.

Well, I've read your biography at http://eli.thegreenplace.net/about/
and I'm currently seeing your photo album. You're a great example for
us to follow due your characteristics as liking to study and liking to
travel the whole world. It's just what I want to do too as a
professional and as a traveler! You really do very well on this.

Your site is all of good! Think about the entire internet filled with
sites just like yours. With a complete bunch of interesting
information! My God it's a dream.

Coming to the real reason I'm writing to you - it's about a project
that has been proposed to me and a friend of mine called Wellington.
When we were in the 7th term at the university during our class of
Laboratory of Compiler Construction studying Lex and Yacc, our teacher
asked us to prepare an article about the process of creation of an
engine to parse Regular Expressions. Since that moment we started
searching the Internet for something that we could use as a base for
our article. For our lucky, we found your article Algorithmic Forays
at www.gamedev.net that is amazing for everyone to understand. It's
simple and direct with implementation examples.
During the 6th term at the university we had a discipline called
Automatons and Formal Languages. Was at this period that we learned
topics regarding Finite State Machines (FSM), Deterministic Finite
Automatons (DFA), Nondeterministic Finite Automatons (NFA) and Regular
Expressions. So, from there we know that a DFA + NFA = FSM! We've also
implemented some code for covering and getting a better understanding
of how such topics work in reality.

In true, we started our project preparing an article on April, May of
2006, when I particularly started converting all your Algorithmic
Foray's C++ code to the C# language that is the one I most like to use
for writing any kind of code. But due our other tasks, in other words,
other disciplines, we stopped working on this project. It's important
to mention that I could finalize translating your C++ code to C# on
the middle of May 2006.

I've learned such great things working with the code as mastering my
knowledge with the Generics in C#. I even got one third party DLL
called C5.dll from http://www.itu.dk/research/c5/ which includes lots
of new classes to work with sets of data as is necessary when dealing
with regular expressions.

Yesterday, 1/2, when I woke up I just thought why not to continue
working on that project about a regex parser. So, I started again with
new motivations.

I started translating your whole article from English to Portuguese
and I'd like to ask you if we could use some text and diagrams of your
article as the base of our article and we would present it with both
versions of code, C++ and C#.

Our aim is to forward it to be issued in our university's scientific
magazine and propagate to the ones interested – see
http://www.ubm.br/ubm/paginas/copep/inicial.php?pagina=apresentacao.php
(it's in Portuguese - you're learning Spanish and it's a little bit
alike. I've already publicized one article in this magazine with the
title: Development and Numeric Simulation of Algorithms for
Computational Resolution of Ordinary Differential Equations. It was a
project I developed while I was in the 4th term. The code was
developed using C++. Further, this article will be available in the
Internet through an indexing project that's been prepared by a
university here in Brazil.

We'll certainly cite the article's fonts as you can see in the
preliminary code I'm going to send you in this e-mail. Your great
initiative of publicizing the article must be preserved by any mean.
Haven't you used any other bibliography? Was it developed by just your
thoughts?

Remember that this code I'm sending you needs a review because I have
to pass through it to get it all in mind again and see if everything
is Ok. To run the code you just need to recompile it using a C#
compiler. I use the Microsoft Visual Studio 2005 Express Edition as
you mentioned in your home page here
http://eli.thegreenplace.net/2006/12/03/a-complete-c-development-environment-from-microsoft-free/
The initial parameter I'm using is set in the command line argument
inside the project's properties in Debug and is as follow:
RegularExpressionEngine "(a|b)*abb" aaababb
It's seems to be working Ok.
Try it for yourself!

From now on we're just waiting for your reply.

By the way, if you and your wife want to come to visit Brazil you can
certainly come to my house. I'd like to have you as my guests. Who
knows, one day I can go to Israel and meet you personally. That would
be great too. Israel is the apple of God's eye!

I simply think we have the same liking!

It was a pleasure to write to you.

My best regards,
Leniel Braz de Oliveira Macaferi
Volta Redonda, Rio de Janeiro, Brazil

Leniel Macaferi <le@…>

Algorithmic Forays for a Regex Parser

Eli Bendersky <eli@…> Sun, Jan 21, 2007 at 2:03 AM

To: "le@…" <le@…>

Hello Leniel,

First of all, thanks for all the compliments - I'm flattered.
You can certainly use any part of the articles and the diagrams for your translation. As for my sources, I certainly didn't invent anything - I took all the material from the "Dragon Book" ("Compilers" by Aho, Sethi and Ullman), perhaps with the help of some googling, but as far as I remember, the book was the main source.

Keep being enthusiastic about your studies. That's a good thing :-)

Regards,

Eli

As you can see from the above e-mail, Eli agreed and so it was OK to write a Portuguese version of his articles.

As the semesters passed and new commitments queued I stopped translating the articles and I have just decided this past week that now it’s a good time to come back to it and finish the planned objective of 2 years ago.

While I write the next blog posts I’ll translate the remaining articles to Portuguese. I expect to publish it online here on this blog so that it can help people out there to learn this fascinating subject of Computation Theory.

I’ll follow a different path to explain how the regular expression engine work, that is, from part 1 to part 6 I’ll be showing each division of the engine by means of its representing class in code. I’ll do so, so that I can present each part of the translated code (C++ to C#) in such a way that it gets easier to understand. I’ll use a top down approach, that is, I’ll begin showing the higher level class and then I’ll go deep to its dependencies.

This is the story behind the Regular Expression Engine in C# I’ll be presenting in the next posts, starting with this one.

Hope that you like it as much as I do. This was for sure one of or even the best discipline I’ve had in the Computer Engineering course and one of the more exciting things to write about.

Updated on 5/12/2009 09:41:00 PM

As I finished writing the series of posts, here goes the list that points to them:

Regex engine in C# - the Regex Parser
Regex engine in C# - the NFA
Regex engine in C# - the DFA
Regex engine in C# - matching strings

Fortran Numerical Constants Recognizer

2009-02-09T01:19:00.001-02:00

Compilers construction paper
I and a dear brother in faith of mine called Wellington Magalhães Leite wrote a paper titled: Fortran Numerical Constants Recognizer

It exercises concepts related to state transition diagram, finite state machine and automata theory.

Needless to say, compilers construction was one of the best disciplines or even the best discipline I had in the computer engineering course. I really like this kind of stuff. State machines and automata theory really rocks! Automata theory is other discipline I had that really got my attention.

State Transition Diagram
This is the lexical state transition diagram in which our work is based:

Alphabet = {d, +, - , . , E} (d is any digit)

The arches of any vertex to an Error vertex aren’t showed but they exist.

Expressions like the following are recognized: 13, +13, -13, 13., 1.25, .25, -.25, -32.43, 13E-15, 13.E-15, -13.25E+72, .75E5, etc.

Expressions like the following aren’t recognized: ++13, .E13, etc.

The vertex with a 0 (zero) value is the initial state.

The vertexes with bold circles are the final states.

Note: It’s important to note that lexical state transition diagrams are finite automatons.

Abstract
A didactic method for the construction of a compiler front-end is the one substantiated in transition diagrams. So, its construction helps with the familiarization regarding the tasks of a compiler project.

This paper presents a Fortran numerical constants recognizer. It is developed based on a state transition diagram and its implementation follows the standards of the C# programming language.

Keywords: fortran, compiler construction, state transition diagram, C# programming language

CONTENTS
1 INTRODUCTION 6
  1.1 Objective	6
  1.2 Definition 6
2 DEVELOPMENT 7
  2.1 Mapping the constants 7
  2.2 Mapping the functions 7
  2.3 Application main entry point 10
3 APPLICATION 12
  3.1 Validating expressions 12
      3.1.1 Single expression 12
      3.1.2 Set of expressions 13
4 CONCLUSION 14
5 REFERENCES 15
6 ADDENDUM 16

Resumo
Um método muito didático para a construção do front-end de um compilador é aquele fundamentado em diagramas de transição. Logo, seu estudo ajuda na familiarização com as atividades envolvidas no projeto de um compilador.

Esse trabalho apresenta um sistema reconhecedor de constantes numéricas em Fortran. O mesmo é desenvolvido a partir de um diagrama de transição de estados e sua codificação segue os padrões e moldes da linguagem de programação C#.

Palavras-chave: fortran, construção de compiladores, diagrama de transição de estados, linguagem de programação C#

SUMÁRIO
1 Introdução 5
   1.1 Objetivo	5
   1.2 Definição 5
2 Desenvolvimento 6
   2.1 Mapeamento das constantes 6
   2.2 Mapeamento das funções 6
   2.3 Mapeamento da chamada principal 10
3 Aplicação 12
   3.1 Validação de expressões 12
       3.1.1 Uma única expressão 13
       3.1.2 Uma lista de expressões 14
4 Conclusão 15
5 Bibliografia	16
6 Anexo 17

Source code

class StateTransitionSystem
{
  public static void Main(string[] args)
  {
    Console.Title = "State Transition System for recognizing numeric constants in FORTRAN";

    Console.BackgroundColor = ConsoleColor.White;
    Console.ForegroundColor = ConsoleColor.Black;

    char ch;

    do
    {
      Console.Clear();

      // Print startup banner
      Console.Write("\nState Transition System C# Sample Application\n");
      Console.Write("Copyright ©2006 Leniel Braz de Oliveira Macaferi & Wellington Magalhães Leite.\n\n");
      Console.Write("UBM COMPUTER ENGINEERING - 7TH SEMESTER [http://www.ubm.br/]\n\n");

      // Describes program function
      Console.Write("This program example demonstrates the State Transition Diagram's algorithm for\n");
      Console.Write("numeric constants validation in FORTRAN.\n\n");

      // Describes program's options     
      Console.Write("You can validate expressions by two different ways as follow:\n\n");
      Console.Write("1 - A single expression by providing an entry.\n\n");
      Console.Write("2 - A set of expressions by providing an input file.\n");
      Console.Write("  * Notice: the expressions must be separeted in-lines.\n");

      Console.Write("\n\nEnter your choice: ");

      ch = Console.ReadKey().KeyChar;

      switch(ch)
      {
        case '1':
          {
            SingleExpression();
            break;
          }
        case '2':
          {
            SetOfExpressions();
            break;
          }
      }
    }
    while(ch == '1' || ch == '2');
  }

  /// <summary>
  /// Enumeration where each item corresponds to one state in the State Transition Diagram.
  /// </summary>
  public enum PossibleStates
  {
    s0 = 0,
    s1,
    s2,
    s3,
    s4,
    s5,
    s6,
    s7,
    error
  }

  /// <summary>
  /// Array of type PossibleStates, which contains the finalStates acceptable by the
  /// State Transition Diagram.
  /// </summary>
  public static PossibleStates[] finalStates = { PossibleStates.s2, PossibleStates.s3, PossibleStates.s6 };

  /// <summary>
  /// Verifies if the last state achieved by the machine belongs to the finalStates
  /// array.
  /// </summary>
  public static bool IsFinalState(PossibleStates currentState)
  {
    for(int i = 0; i < finalStates.Length; i++)
      if(currentState == finalStates[i])
        return true;

    return false;
  }

  /// <summary>
  /// Recognizes the current state and the character “label” being analysed, values
  /// passed as parameters. After, the function does the transition of state case some
  /// condition is satisfied, otherwise, the function will return an error flag.
  /// </summary>
  public static PossibleStates Recognizer(PossibleStates currentState, char c)
  {
    switch(currentState)
    {
      case PossibleStates.s0:
        {
          if(c == '+' || c == '-')
            return PossibleStates.s1;

          if(char.IsDigit(c))
            return PossibleStates.s2;

          if(c == '.')
            return PossibleStates.s4;

          break;
        }

      case PossibleStates.s1:
        {
          if(char.IsDigit(c))
            return PossibleStates.s2;

          if(c == '.')
            return PossibleStates.s4;

          break;
        }

      case PossibleStates.s2:
        {
          if(char.IsDigit(c))
            return PossibleStates.s2;

          if(c == '.')
            return PossibleStates.s3;

          if(c == 'E')
            return PossibleStates.s5;

          break;
        }

      case PossibleStates.s3:
        {
          if(char.IsDigit(c))
            return PossibleStates.s3;

          if(c == 'E')
            return PossibleStates.s5;

          break;
        }

      case PossibleStates.s4:
        {
          if(char.IsDigit(c))
            return PossibleStates.s3;

          break;
        }

      case PossibleStates.s5:
        {
          if(char.IsDigit(c))
            return PossibleStates.s6;

          if(c == '+' || c == '-')
            return PossibleStates.s7;

          break;
        }

      case PossibleStates.s6:
        {
          if(char.IsDigit(c))
            return PossibleStates.s6;

          break;
        }

      case PossibleStates.s7:
        {
          if(char.IsDigit(c))
            return PossibleStates.s6;

          break;
        }
    }
    return PossibleStates.error;
  }

  /// <summary>
  /// Reads an input expression, recognizes its characters, changes the states
  /// accordingly to those characters and hence validates the entry.
  /// </summary>
  public static void SingleExpression()
  {
    do
    {
      // The machine points to the initial state of the State Transition Diagram.
      PossibleStates currentState = PossibleStates.s0;

      Console.Write("\n\nEnter the expression to be evaluated: ");

      // strExpression receives the entry typed by the user.
      string strExpression = Console.ReadLine();

      /* For each string's character (label), calls the function Recognizer that
      on the other hand changes the machine state accordingly. */
      for(int i = 0; strExpression.Length > i; ++i)
        if(currentState != PossibleStates.error)
          currentState = Recognizer(currentState, strExpression[i]);
        else
          break;

      /* Calls the function IsFinalState to verify if the state where the machine
       stopped is a final state or not. */
      if(IsFinalState(currentState))
        Console.WriteLine("\n Valid expression.\n");
      else
        Console.WriteLine("\n Invalid expression!\n");

      Console.Write("Do you wanna try again? (y\\n) ");
    }
    while(Console.ReadKey().KeyChar == 'y');
  }

  /// <summary>
  /// Reads an input file, recognizes its lines, expression by expression and changes
  /// the states accordingly to each expression. In other words, validates the entire
  /// list.
  /// </summary>
  public static void SetOfExpressions()
  {
    do
    {
      Console.Write("\n\nEnter the file path: ");

      // Obtains the file name.
      string fileName = Console.ReadLine();

      // Verifies if the file exists.
      if(!File.Exists(fileName))
        Console.Write("\n File not found!\n\n");
      else
      {
        // Reads all the file's lines and stores them.
        StreamReader sReader = new StreamReader(fileName);

        string expression;

        // Evaluates each line until achieve the EOF (end of file).
        while((expression = sReader.ReadLine()) != null)
        {
          // The machine points to the initial state of the State Transition Diagram.
          PossibleStates currentState = PossibleStates.s0;

          /* For each expression's character (label), calls the function Recognizer that
          on the other hand changes the machine state accordingly. */
          for(int i = 0; expression.Length > i; ++i)
            if(currentState != PossibleStates.error)
              currentState = Recognizer(currentState, expression[i]);
            else
              break;

          /* Calls the function IsFinalState to verify if the state where the machine
           stopped for the expression is a final state or not. */
          if(IsFinalState(currentState))
            Console.WriteLine("\n{0} is a valid expression.", expression);
          else
            Console.WriteLine("\n{0} is an invalid expression!", expression);
        }
        sReader.Close();
      }
      Console.Write("\nDo you wanna try again? (y\\n) ");
    }
    while(Console.ReadKey().KeyChar == 'y');
  }
}

Screenshots
See screenshots of Fortran numerical constants recognizer in action:

You can get a PDF copy of the paper and the accompanying Fortran Numerical Constants Recognizer files in a ZIP file at:

English version
http://leniel.googlepages.com/FortranNumericalConstantsRecognizer.pdf

Portuguese version
http://leniel.googlepages.com/SisReconhecedorConstNumericasFortran.pdf

Microsoft Visual Studio C# 2008 Console Application project
http://leniel.googlepages.com/FortranNumericalConstantsRecognizer.zip

Note: The program’s source code is in a Microsoft Visual Studio C# 2008 Console Application project. If you don’t have Visual Studio, you can get a free copy of its express edition at http://www.microsoft.com/express/download.

ASP.NET Chart with MVC and Google Spreadsheet API

2009-02-02T00:59:00.008-02:00

BarcodeLib.com provides the leading barcode components for Java and ASP .NET developers.
For Java developers, you can use their Java barcode library, a high quality Java barcode generator generates high quality barcode images in Java applications.
For ASP.NET, C#, VB.NET developers, ASP.NET barcode or C# barcode will help developers generate barcode images in C#, VB.NET websites.
.NET barcode library will also help developers generate barcode images in .NET WinForms application, SQL Server reporting service, and Crystal Reports for .NET.
Barcode Fonts also allows to display barcode (Code 39, Code 129, UPC) in
office documents (Microsoft Word, Microsoft Excel) and reports (Crystal reports) easily. C# Barcode Reader, a barcode image recognition SDK for C#, VB.NET developers.

Scott Guthrie recently posted about the New ASP.NET Charting Control: <asp:chart runat="server"/>.

This weekend I decided to give it a try and as always I had to go through the samples to learn how to assemble a chart.

To learn about the new charting controls I got the Microsoft Chart Controls Samples project and played with the contents of the Getting Started section.

At the same time I was translating to Portuguese ScottGu’s blog post about the ASP.NET MVC 1.0 Release Candidate. I was also updating a Google spreadsheet that I use to keep track of worked hours at Chemtech.

To learn how to integrate ASP.NET charting controls with ASP.NET MVC and Google Spreadsheet Data API I created a new ASP.NET MVC project and started coding a sample application.

The following is how I got it all together:

using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Web.Mvc;
using System.Web.UI.DataVisualization.Charting;
using Google.GData.Client;
using Google.GData.Extensions;
using Google.GData.Spreadsheets;
namespace MvcChartGoogleSpreadsheet.Views.Home
{
    /// <summary>
    /// ASP.NET MVC application + ASP.NET charting controls + Google Spreadsheet Data API web-based application
    /// It demonstrates the operations supported by each of these technologies.
    /// It requires authentication in the form of your Google Docs & Spreadsheets username
    /// and password, and retrieves data from a worksheet of your choice.
    /// A chart is created with the data acquired through a CellFeed query.
    /// </summary>
    public partial class Index : ViewPage
    {
        private List<WorksheetEntry> allWorksheets = new List<WorksheetEntry>();

        protected void Page_Load(object sender, System.EventArgs e)
        {
            // Calling the method that configures the chart.
            ConfigureChart();

            // Creating a Google SpreadsheetService object passing to it the name of the application.
            SpreadsheetsService service = new SpreadsheetsService("MvcChartGoogleSpreadsheet");

            // Google account information (login and password)
            service.setUserCredentials("username@gmail.com", "password");

            GetAllSpreadsheetsAndWorksheets(service);

            // Using LINQ query expression to get a specific worksheet.
            var entry = from wse in allWorksheets
                        where
                            wse.Title.Text == "2008 leniel.net" // This is the name of the worksheet.
                        select wse;

            // Demonstrate a CellFeed query.
            CellFeed cellFeed = GetWorksheetCellFeed(service, entry.First());

            // Each entry represents a cell within the worksheet.
            foreach(CellEntry cellEntry in cellFeed.Entries)
            {
                // I just want to get the contents of column 2 of the worksheet.
                // The value of the cell present in column 2 will be used in the X axis.
                if(cellEntry.Cell.Column == 2)
                {
                    // I get the value of column 7 (cellEntry.Cell.Column + 5) of the same row. This value will be used in the Y axis.
                    // I replace the colon present in the value with a dot. I do so to make the data valid for calculating values.
                    string yValue = ((CellEntry)cellFeed.Entries.SingleOrDefault(es => ((CellEntry)es).Cell.Row == cellEntry.Cell.Row && ((CellEntry)es).Cell.Column == cellEntry.Cell.Column + 5)).Cell.Value.Replace(":", ".");

                    // I then remove the extra data that isn't necessary at all in my case.
                    yValue = yValue.Remove(yValue.Length - 3, 3);

                    // I pass the X and Y values to create a Point used in the series of the chart.
                    chart1.Series["Hours of work"].Points.AddXY(cellEntry.Cell.Value, yValue);
                }
            }
        }

        private void ConfigureChart()
        {
            chart1.Series.Add("Hours of work");

            chart1.Titles.Add("My chart title");

            // Add header separator of type line      
            chart1.Legends["Default"].HeaderSeparator = LegendSeparatorStyle.Line;
            chart1.Legends["Default"].HeaderSeparatorColor = Color.Gray;

            // Add Color column      
            LegendCellColumn firstColumn = new LegendCellColumn();
            firstColumn.ColumnType = LegendCellColumnType.SeriesSymbol;
            firstColumn.HeaderText = "Color";
            firstColumn.HeaderBackColor = Color.WhiteSmoke;
            chart1.Legends["Default"].CellColumns.Add(firstColumn);

            // Add Legend Text column      
            LegendCellColumn secondColumn = new LegendCellColumn();
            secondColumn.ColumnType = LegendCellColumnType.Text;
            secondColumn.HeaderText = "Name";
            secondColumn.Text = "#LEGENDTEXT";
            secondColumn.HeaderBackColor = Color.WhiteSmoke;
            chart1.Legends["Default"].CellColumns.Add(secondColumn);

            // Add AVG cell column      
            LegendCellColumn avgColumn = new LegendCellColumn();
            avgColumn.Text = "#AVG{N2}";
            avgColumn.HeaderText = "Avg";
            avgColumn.Name = "AvgColumn";
            avgColumn.HeaderBackColor = Color.WhiteSmoke;
            chart1.Legends["Default"].CellColumns.Add(avgColumn);

            // Add Total cell column      
            LegendCellColumn totalColumn = new LegendCellColumn();
            totalColumn.Text = "#TOTAL{N1}";
            totalColumn.HeaderText = "Total";
            totalColumn.Name = "TotalColumn";
            totalColumn.HeaderBackColor = Color.WhiteSmoke;
            chart1.Legends["Default"].CellColumns.Add(totalColumn);

            // Set Min cell column attributes      
            LegendCellColumn minColumn = new LegendCellColumn();
            minColumn.Text = "#MIN{N1}";
            minColumn.HeaderText = "Min";
            minColumn.Name = "MinColumn";
            minColumn.HeaderBackColor = Color.WhiteSmoke;
            chart1.Legends["Default"].CellColumns.Add(minColumn);

            // Show labels at every 2 days
            chart1.ChartAreas["ChartArea1"].AxisX.LabelStyle.Interval = 2;
            chart1.ChartAreas["ChartArea1"].AxisX.MajorGrid.Interval = 2;
            chart1.ChartAreas["ChartArea1"].AxisX.MajorTickMark.Interval = 2;

            // Set series tooltips
            chart1.Series["Hours of work"].ToolTip = "#VALX";

// Set the width of the chart
           chart1.Width = 510;

           // Set legend docking
           chart1.Legends["Default"].Docking = Docking.Bottom;

           // Set legend alignment
           chart1.Legends["Default"].Alignment = StringAlignment.Center;

        }

        /// <summary>
        /// Gets a list of all the user's spreadsheets, and the
        /// list of worksheets that each spreadsheet contains.
        /// </summary>
        /// <param name="service">An authenticated SpreadsheetsService object</param>
        private void GetAllSpreadsheetsAndWorksheets(SpreadsheetsService service)
        {
            SpreadsheetQuery query = new SpreadsheetQuery();

            SpreadsheetFeed feed = service.Query(query);

            foreach(SpreadsheetEntry entry in feed.Entries)
            {
                GetAllWorksheets(service, entry);
            }
        }

        /// <summary>
        /// Gets a list of all worksheets in the specified spreadsheet.
        /// </summary>
        /// <param name="service">An authenticated SpreadsheetsService object</param>
        /// <param name="entry">The spreadsheet whose worksheets are to be retrieved</param>
        private void GetAllWorksheets(SpreadsheetsService service, SpreadsheetEntry entry)
        {
            AtomLink link = entry.Links.FindService(GDataSpreadsheetsNameTable.WorksheetRel, null);

            WorksheetQuery query = new WorksheetQuery(link.HRef.ToString());

            WorksheetFeed feed = service.Query(query);

            foreach(WorksheetEntry worksheet in feed.Entries)
            {
                allWorksheets.Add(worksheet);
            }
        }

        /// <summary>
        /// Performs a cell range query on the specified worksheet to
        /// retrieve only the cells contained within the specified range.
        /// </summary>
        /// <param name="service">An authenticated SpreadsheetsService object</param>
        /// <param name="entry">The worksheet to retrieve</param>
        private static CellFeed GetWorksheetCellFeed(SpreadsheetsService service, WorksheetEntry entry)
        {
            AtomLink listFeedLink = entry.Links.FindService(GDataSpreadsheetsNameTable.CellRel, null);

            CellQuery query = new CellQuery(listFeedLink.HRef.ToString());

            // Defining the range of cells that I want to be retrieved.
            query.Range = "B5:G29";

            CellFeed feed = service.Query(query);

            return feed;
        }
    }
}

The above code is commented so I don’t think it needs more words.

ASP.NET MVC
I’ve already written about ASP.NET MVC in a post titled Hello World Web Site with ASP.NET MVC. If you don’t know what MVC means, don’t panic! It’s just an architectural and design pattern that advocates a clean separation of concerns in software engineering.

To get the ASP.NET MVC I’d recommend the Web Platform Installer that Microsoft released not so long ago.

Just download and install the Web Platform Installer and select what web development tools you want to be installed on your machine.

As you can see above I already have the ASP.NET MVC Release Candidate 1 installed on my machine. In case you don’t have it yet, select the checkbox and click the Install button. The Web Platform Installer will do the rest of the job, that is, it’ll download the packages and install it conveniently for you.

An interesting thing about the Web Platform Installer is that it’ll always have the most updated bits to be installed.

After installing the ASP.NET MVC you’re ready to create an ASP.NET MVC Web Application in Visual Studio 2008:

Google Spreadsheet API
To accomplish the goal of this post I needed more documentation and so I went to Google Spreadsheets APIs and Tools page. From there I went to read the Google Spreadsheets Data API Developer's Guide. Specifically the Developer's Guide for .NET since I’m playing with Microsoft development platform.

After reading some bits here and some bits there I went directly to the Libraries and Code page and went to the download page of google-gdata – the .NET library for the Google Data API.

I downloaded the file Google Data API Setup(1.3.1.0).msi and installed it. It has sample projects for all Google Data APIs. I was interested in the Spreadsheet API and so I got the specific code and dropped it on the ASP.NET MVC project.

As you can see in the above code the using statements include 3 references to Google Data API DLLs:

using Google.GData.Client;
using Google.GData.Extensions;
using Google.GData.Spreadsheets;

These DLLs are part of Google Data API Setup(1.3.1.0).msi installation file and are located at C:\Program files\Google\Google Data API SDK\Redist in my machine. You’ll need to add these DLLs to the References folder of the ASP.NET MVC project.

ASP.NET Charting Controls

There are charts of all types:

- Bar and Column Charts
- Line Charts
- Area Charts
- Pie and Doughnut Charts
- Point Charts
- Range Charts
- Circular Charts
- Accumulation Charts
- Data Distribution Charts
- Price Change Financial Charts
- Advanced Financial Charts
- Combinational Charts

To get the charting controls in Visual Studio 2008 I downloaded 2 files:

- Microsoft Chart Controls for Microsoft .NET Framework 3.5
- Microsoft Chart Controls Add-on for Microsoft Visual Studio 2008

After installing both files, open Visual Studio 2008 and go to a webform/viewpage .ASPX page. Now in the Toolbox you’ll find the new Chart control.

Drag and drop the chart onto the page and you’re ready to go.

Look to the using statement present in the code behind page:

using System.Web.UI.DataVisualization.Charting;

This is the column chart I got when I ran the application:

LINQ
I used some constructs of LINQ in the above sample application. If you need further details about this fantastic technology: read my post LINQ - Language Integrated Query.

Note:
To work with Dates in a chart I had to go through the Microsoft Chart Controls Samples project and look at Working with Chart Data – Working with Dates – Setting Time Scale.

Summary
As you could see the ASP.NET charting control is feature rich and you can use it to show data from all sorts of sources as for example a Google spreadsheet. I just showed here the simplest of the charts.

Using the charting controls in an ASP.NET MVC application is a really straightforward task. Of course, you’d have action methods that’d generate the chart for you based on some logic you implement in such methods. The sample given here was just to exercise the integration of technologies available nowadays to build richer internet applications.

References
ASP.NET MVC
Hello World Web Site with ASP.NET MVC
ASP.NET MVC : The Official Microsoft ASP.NET Site
ScottGu's Blog
Model View Controller (MVC) at Wikipedia

Google Spreadsheet API
Google Spreadsheets APIs and Tools page
Google Spreadsheets Data API Developer's Guide
Google Spreadsheets Developer's Guide for .NET
Google Spreadsheets Libraries and Code page
google-gdata – the .NET library for the Google Data API

ASP.NET Charting controls
Download the Microsoft Chart Controls Documentation
Microsoft Chart Control Forum
Alex Gorev's Weblog - Data Visualization
Charting With ASP.NET And LINQ

Downloads
ASP.NET MVC
Web Platform Installer

Google Spreadsheet API
Google Data API Setup(1.3.1.0).msi

ASP.NET Charting controls
Microsoft Chart Controls for Microsoft .NET Framework 3.5
Microsoft Chart Controls Add-on for Microsoft Visual Studio 2008
Microsoft Chart Controls Samples project

Visual Studio 2008 C# ASP.NET MVC Web Application
You can get the Microsoft Visual Studio Project at:

http://leniel.googlepages.com/MvcChartGoogleSpreadsheet.zip

Note: Remember to change/substitute the username and password present in the file C:\MvcChartGoogleSpreadsheet\Views\Home\Index.aspx.cs so that the application can log you on to Google Spreadsheet service and get your data (spreadsheet along with the worksheets).

Line prefixer suffixer in C#

2009-01-20T01:52:00.001-02:00

I extracted a lot of Ids from a database table and needed to pass such Ids as a parameter to a webservice method. The webservice method was expecting a parameter of type List<long>. I didn’t find a way of passing such a list to the webservice using the built in webservice form constructed by Visual Studio. The cause is that a List<long> isn’t a primitive type.

Talking with my peers I learned of a tool called soapUI. It’s a tool used to test webservices. Using it I could pass the list of Ids.

I created a new project in soapUI passing to it the webservice WSDL URL and I was ready to go.

This is the value I’ve put in Initial WSDL/WADL:

http://localhost:7777/WebServices/MyWebserviceName.asmx?WSDL

After clicking OK, soapUI will then load the webservice definition.

Clicking in Request 1 as shown in the following picture, the XML of a SOAP envelope appears so that we can test the webservice method.

The problem now was that I had a file called “input.txt” with only the Ids – each one in its proper line. The XML of the SOAP envelope expect that each id be passed in the format:

<ns:long>?</ns:long>

For example,

<ns:long>7</ns:long>

As we can observe, my input data don’t fit the pattern required by the XML.

To put my data in conformity with the XML I created a small but useful application called LinePrefixerSuffixer that receives the name of an input file containing the the initial data, the text to be “prefixed” in the start of each line, the text to be “suffixed” in the end of each line of the file and the name of the output file.

So for example, to comply with the above pattern, I’d call the console application with:

LinePrefixerSuffixer input.txt “<ns:long>” “</ns:long>” output.txt

Let’s say I have a file called input.txt with 1000 numbers in the same directory of the LinePrefixerSuffixer.exe executable.

Each line of the input.txt file has a number as:

1
2
3
4
5
6
7
.
.
.

Running the above command line in the command prompt I’d get a file called output.txt with each line now in the format I want, that is:

<ns:long>1</ns:long>
<ns:long>2</ns:long>
<ns:long>3</ns:long>
<ns:long>4</ns:long>
<ns:long>5</ns:long>
<ns:long>6</ns:long>
<ns:long>7</ns:long>
. 
. 
.

The C# code of the app is as follow:

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace LinePrefixerSuffixer
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                // Read in all lines of the file using query expression (LINQ).
                // I "prefix" the start of each line with the content of args[1] and
                // "suffix" the end of each line with the content of args[2].
                IEnumerable<string> fileLines = from line in File.ReadAllLines(args[0])
                                                select args[1] + line + args[2];

                // Writing the prefixed and suffixed file lines to a file named with the content of args[3].
                File.WriteAllLines(args[3], fileLines.ToArray());

                Console.WriteLine("Operation done.");
            }
            catch(Exception e)
            {
                Console.WriteLine("Use: LinePrefixerSuffixer <input.txt> prefix suffix <output.txt>");
            }
        }
    }
}

Now I can pass the content of the output.txt file to soapUI without worrying about having to manually prefix/suffix each line of my input.txt file:

Summary
In this post we saw how to build a simple but powerful application that prefixes and suffixes each line of a file.

We’ve used concepts related to file handling and LINQ and with only 4 lines of code we could manage to accomplish the task.

I think this shows how powerful modern programming languages as C# enables a clean and beautiful coding experience.

Hope this helps.

Visual Studio C# Console Application
You can get the Microsoft Visual Studio Project and the app executable at:

http://leniel.googlepages.com/LinePrefixerSuffixer.zip

Note: As this program uses LINQ, you must have Microsoft .NET Framework 3.5 runtime libraries installed on you computer. You can get it at:

http://www.microsoft.com/downloads/details.aspx?FamilyID=333325fd-ae52-4e35-b531-508d977d32a6&DisplayLang=en

References
[1] soapUI - the Web Services Testing tool. Available at <http://www.soapui.org>. Accessed on January 20, 2009.

[2] Sam Allen. File Handling - C#. Available at <http://dotnetperls.com/Content/File-Handling.aspx>. Accessed on January 20, 2009.

[3] LINQ. The LINQ Project. Available at <http://msdn.microsoft.com/en-us/netframework/aa904594.aspx>. Accessed on January 20, 2008.

[4] LINQ. Language Integrated Query. Available at <http://www.leniel.net/2008/01/linq-language-integrated-query.html>. Accessed on January 20, 2008.

Chemtech compliments newly graduated engineers

2009-01-18T02:53:00.002-02:00

Last Friday, January 16th, I was complimented by Chemtech. The company gave compliments to all employees that finished their college course in 2007/2008.

The computer engineers including me beside Rubião from right to left.

We got together at the 23rd floor of Rio de Janeiro’s office where Luiz Eduardo Ganem Rubião (CEO and founder of Chemtech) talked a little bit about the company’s perspectives giving us some insight related to life, economy, the job market and ongoing and future projects.

The way Rubião thinks about life subjects, mainly being an optimist is how I face the day to day. There’s no time to be wasted with illusions and we should always think positive. Doing so we’ll for sure harvest good fruits.

The following is the transcription of the letter I received with a present (a book of my area of specialization - computer engineering) …

Rio de Janeiro, January 16th, 2009

Dear Leniel Braz de Oliveira Macaferi,

Young people like you represent the future of technology. With your know how you can contribute to Brazil’s development so that it stands out in the worldwide technology. It is in the knowledge, in technology that a differential arises.

Chemtech is proud to have been with you in your first steps to engineering and for us still being together. It’s with satisfaction that today we call you an engineer! A Chemtecheano engineer, a Brazilian engineer.

We’re together in this journey that starts with your graduation. Success!

A strong hug from the Chemtech family.

NHibernate Query Analyzer + ActiveRecord

2008-11-30T00:16:00.001-02:00

It's been a long time since I last posted something.

My work at Chemtech is really motivating and is keeping me busy. Well, I think this is good because I really like to work and while I help my team building new projects, we as a group contribute in some way to the world.

Each day I learn new things and the tip I want to pass ahead is related to a new tool I knew a few days ago. It's called NHibernate Query Analyzer. NHQA helps a lot while working in a project with a relational database that makes use of NHibernate as the persistence manager.

I was having a problem getting NHQA to work with a business data layer constructed with the help of ActiveRecord - I searched the Internet for a path that would led me in the right direction and after solving small errors I got NHQA working with a proper configuration file. Below I post the content of the file so that you can get a sense of what must be done with the initial configuration of NHQA:

<?xml version="1.0" encoding="utf-8" ?>
<configuration>

  <configSections>
    <section name="activerecord" type="Castle.ActiveRecord.Framework.Config.ActiveRecordSectionHandler, Castle.ActiveRecord" ></section>
  </configSections>

  <activerecord>
    <config>
      <add key="hibernate.show_sql" value="true" />

      <add key="hibernate.connection.driver_class" value="NHibernate.Driver.OracleClientDriver" />

      <add key="hibernate.connection.provider" value="NHibernate.Connection.DriverConnectionProvider" />

      <add key="hibernate.dialect" value="NHibernate.Dialect.OracleDialect" />

      <add key="hibernate.connection.connection_string" value="Data Source=YOUR DATA SOURCE;User ID=YOUR USER ID;Password=YOUR PASSWORD;" />
    </config>
  </activerecord>

</configuration>

See a screenshot of NHQA with a business data layer DLL plus the app.config file:

To get it going, just hit the Build Project button and once it’s built, just open a new Query (ctrl + Q) and start visualizing the SQL generated from the Hibernate Query Language (HQL) you type. Besides this great feature you can also view the results from an HQL query in both tabular and object graph formats.

Get a copy of the app.config file here.

Hope this helps.

Arriving at Chemtech

2008-08-31T03:06:00.001-03:00

It's with great pleasure that I'm writing this post. I finally got a job after 5 months of eager expectation. I'm going to work at Chemtech.

I've been sending lots of resumes to almost all IT related companies from Brazil and to some international companies since I got out of ITA-Petrobras.

Fortunately, on July 10 I received an e-mail from Chemtech asking for my grade transcripts related to the computer engineering course. I then sent the transcripts to them on July 30. On August 28 I was invited to participate in a in house interview that would take place the next day. On August 29 I went to Rio de Janeiro. During the interview conducted by two managers and one software developer, a job proposal for a Junior Analyst position was made and I accepted. The area of specialty is computer engineering.

I dreamed about getting a job in a top technology company. From the moment I began the Computer Engineering course in 2003 my constant thought has been to get a position in a company that is attractive.

Today what was a dream is now pure reality.

I'm extremely motivated to be a part of the Chemtech team!

I thank Jesus Christ for helping me to achieve this goal. After all, it's for Him that I live! :)

Systems Analyst job interview at Oi

2008-07-10T12:58:00.001-03:00

On Tuesday, July 8, I went to Praia de Botafogo in Rio de Janeiro to take part in a job interview scheduled for 2:00 P.M. I arrived there 1:45 P.M. During the trip (2 hours) the bus got backed up because there were some construction being carried out at Via Dutra highway. I thought I wouldn't get there on time, but fortunately everything went OK.

As I mentioned in the post Network Analyst job interview at Oi, I participated in the first interview for a Network Analyst position.

On Monday, June 30, I got a phone call from Oi's HR department offering me an interview for a Systems Analyst position. I told the girl called Sofia that I had already participated in an interview there and that I'd like to know the feedback first so that I could decide if I wanted to go for a second interview this time regarding a different position. She then told me that the systems analyst position would better fit my skills and that I would work directly in the IT department. The department is responsible for the development and improvement of the tools. She asked me a few questions (technical skills) and said I wouldn't need to go for the first interview again with the HR department. The most intriguing question she asked was: How much do you wanna earn? I answered that this question is a filter and that if I said a high value they wouldn't let me go ahead in the recruiting process. She then took the time to say to me how much Oi could pay me (she said she was opening an exception for telling me the value they could pay). I then agreed with the value since the wage plus the benefits would sum a great amount for someone who is just beginning his professional life. Sofia said that she would forward my name for the second round of interviews (the whole process is comprised of 3 interviews). This second interview is the one that would assess my technical skills. I asked when would this interview take place. She answered that there was no scheduled time.

On Monday, July 7, I got a phone call from the manager of the area I would work for. He is called Juscelino. I was being called for an interview on the next day.

I was interviewed by three guys. The other two are professionals already working on the IT department. Juscelino conducted the interview. I was asked about how I started my career in the IT area. I told the complete story starting in August 1997 when I first got a computer then passing to the computer technician course from 1999 to 2002 and then the computer engineering course from 2003 to 2007. He asked some questions about my experience on the previous jobs I had and other questions related to technical skills such as object oriented programming, databases, UML, etc. The focus on this job will be PHP + MySQL. One thing that I emphasized is that if you know well one programming language and a database technology it gets easy to learn a new one, that is, you already know the basic concepts and that the rest of the work is to manage to learn the intrinsic syntax of the different programming language or database technology. At the end Juscelino asked me if I had any doubts regarding the technical details of the job. I said no. Then they asked me non technical questions as: What's your hobby?, Where do you see yourself in the future? Things like that. Juscelino ended the interview and said or no (I don't remember exactly) that I would be contacted for the last interview. While I was heading to the exit door he said: we'll talk more latter. I think this is a good signal. The interview lasted only 15-20 minutes.

Let's see what happens next. If it happens I'll post here some notes about the third part of the interview process.

Nanotechnology and the future of technology

2008-07-04T15:56:00.003-03:00

Nanotechnology refers to a field of applied science and technology whose theme is the control of matter on the atomic and molecular scale, generally 100 nanometers (billionths of meters) or smaller, and the fabrication of devices or materials that lie within that size range. Is any technology that is based on the placement or manipulation of single atoms.

Many innovations will come to light, which will make extensive use of nanotechnology. We know little about the natural phenomena that are surrounding us. In truth everything is already made and is near us, but we just can’t see because we need in the course of time develop our science and create new tools that will make us capable of discovering new chemical elements.

There is a famous maxim from French chemist Lavoisier that is:

In nature nothing is lost, nothing is created, everything is transformed.

We are in a constant process of evolution and development.

With the discovering of new chemical elements and inherent natural phenomena, we’ll be capable of creating new types of materials what on the other hand will bring over more and more discoveries. Discoveries lead to innovations.

If we think that we are working with minuscule particles and that the smaller particle hasn’t been discovered yet, we can assert that we have a lot to learn. In truth it wasn’t long since that the first chemical elements were discovered.

Now it’s interesting to catch sight of how many nice opportunities there are to use nanotechnology. As an example: the manufacturing process of computer processors. I just can’t wait to have a super fast computer. To that end it’s necessary that nanotechnology evolves. For a faster processor it is necessary that billions of small electrical components called transistors be placed in a microchip. The smaller the transistors the greater amount of them can be put in a single chip. There’s a law specific to this subject called Moore's law.

New techniques can also be applied in the medicine field with the development of robots invisible to the human eyes that can flow within the human body fighting against all sorts of diseases.

At last, nanotechnology is a really important and promising technology and I expect that it evolves rapidly for the sake of men’s well being of course because other forms of use also exists. I won’t comment about them here. I think that the reader caught what I want to express with this. If not, try to remember about war technologies.

I can foresee that in a time period of 40 years (approximately 2050) we’ll be in a new baseline and nanotechnology will be a completely forgotten technology. As a matter of fact, it always happens with technologies.

As of the date of this post we already have 11 nanometers technology. For comparison, the processor Intel Core Duo that is the one I use today is manufactured with a 65 nanometers technology.