Hierarchical Ordering – Dependency Walker

Recently I ran into some challenging moments trying to reorder some classes which had an hierarchical order. Implementing the IComparable<T> interface and calling the Sort method on the List<T> just wasn’t enough. This was caused by the fact that the CompareTo method doesn’t know anything about the nested hierarchy.

The problem described above emerged when I was working with OpenLayers. We have made a lot of changes to OpenLayers and therefore I do not use the merged OpenLayers file but the separate source files. OpenLayers comes with a Python build script which orders the sourcefiles (based on it’s hierarchy) and compresses it to one file. Due to some circumstances the standard OpenLayers build script had to be changed significantly. The changes where bigger than my knowledge of Python and therefore I decided to make a .NET builder which will do the same thing as the Python script but with my changes in it.  And then I ran into the problem with the correct order of files.

OpenLayers files has a ‘@ reguires’ commentline in it’s files which determines the dependency between the files. I started to create a class which represents the OpenLayers file:

internal class OpenLayersFile: IComparable<OpenLayersFile>
{
    public OpenLayersFile(string filename)
    { ... }

    public string Name { get; set; }
    public List<string> DependsOn { get; set; }
    public int CompareTo(OpenLayersFile otherFile)
    { ... }
}

The class was simple. It has a Name – property which is the concatenated name of the file (e.g. OpenLayers/Layer/WMS.js). and a DependsOn – property which is a list of “Names” of the files it depends on. The CompareTo method just does a check if DependsOn contains the Name of the file it’s compared to. The logic is omitted because it will clutter up the code snippet and doesn’t add value to this post.

Because List<T>.Sort() didn’t work as described expected as described above I created my own Dependency Walker which runs down all the files and orders them correctly. This dependency walker also keeps in mind to order correct when we have a baseclass with a baseclass which has a baseclass (and so on). Here is the code:

private static class DependencyWalker
{
     public static void Walk(List<OpenLayersFile> files)
     {
          for (int index = 0; index < files.Count; index++)
          {
              OpenLayersFile fileToCompare = files[index];
              for (int i = 0; i < index; i++)
              {
                  OpenLayersFile otherFile = files[i];
                  if (fileToCompare.CompareTo(otherFile) == -1)
                  {
                      files.Remove(fileToCompare);
                      files.Insert(i, fileToCompare);
                      index = 0;
                      break;
                   }
                }
           }
      }
}

This worked perfectly for me and I hope that it will help you too. I am also interested if you have a different solution to the problem. If so, please contact me.

Happy coding!

  1. No comments yet.

  1. No trackbacks yet.