9
\$\begingroup\$

I am building up a basic folder tree with a list of strings in the form /root/node/node/node. Here is the basic algorithm I am using currently to build this collection and fill in my TreeGridView:

// This method gets the list of folders and leaves, then trims out any folder paths
// that are already encompassed in a larger folder path, the idea is that it causes
// less work when adding the actual tree nodes (I may be wrong in this assumption)
List<string> BuildFinalList()
{
    // This list is a collection of root folder paths and leaf folder names
    // i.e. pair("/root/node/node", "node"), pair("/root/node", "node)
    List<KeyValuePair<string, string>> folders = GetListOfFolders();
    var paths = new List<string>();
    foreach(var folder in folders)
    {
        var leaf = folder.Value;
        var root = folder.Key;
        paths.Add(string.Concat(root, "/", leaf);
    }
    paths.Sort(_INVERSE_LENGTH_COMPARE); // this sorts the list longest to shortest

    // Iterate the computed paths from longest to shortest, if a path is not
    // encompassed by an existing path in the final list, add it to the
    // final list, otherwise just move to the next path
    var finalList = new List<string>();
    foreach(var path in paths)
    {
        bool found = false;
        foreach(var item in finalList)
        {
            if (item.StartsWith(path, StringComparison.Ordinal))
            {
                found = true;
                break;
            }
        }

        if (!found)
        {
            finalList.Add(path);
        }
    }
    return finalList;
 }

Once I have the final list built, I then add the nodes to the tree (for simplification, I have removed the calls to end update and begin update of the tree that contains the root node):

void FillTreeNodes(TreeNode root)
{
    var rootText = root.Text;
    var rootTextLength = rootText.Length;
    var nodeStrings = BuildFinalList();
    foreach(var nodeString in nodeStrings)
    {
        var roots = nodeString.Split(new char[] { '/' },
            StringSplitOptions.RemoveEmptyEntries);

        // The initial parent is the root node
        var parentNode = root;
        var sb = new StringBuilder(rootText, nodeString.Length + rootTextLength);
        for(int rootIndex = 0; rootIndex < roots.Length; rootIndex++)
        {
            // Build the node name
            var parentName = roots[rootIndex];
            sb.Append("/");
            sb.Append(parentName);
            var nodeName = sb.ToString();

            // Search for the node
            var index = parentNode.Nodes.IndexOfKey(nodeName);
            if (index == -1)
            {
                 // Node was not found, add it
                 var temp = new TreeNode(parentName, 1, 1);
                 temp.Name = nodeName;
                 parentNode.Nodes.Add(temp);
                 parentNode = temp;
            }
            else
            {
                 // Node was found, set that as parent and continue
                 parentNode = parentNode.Nodes[index];
            }
        }
    }
}
\$\endgroup\$
0

4 Answers 4

6
\$\begingroup\$

One improvement that comes to mind is:

bool found = false;
foreach(var item in finalList)
{
    if (item.StartsWith(path, StringComparison.Ordinal))
    {
        found = true;
        break;
    }
}

Finding out whether a condition is met for any item in a collection is a common enough problem that LINQ has a method for that: Enumerable.Any. Using that the above code can be written as just:

bool found = finalList.Any(item =>
    item.StartsWith(path,StringComparison.Ordinal);

Which is both shorter and simpler.

\$\endgroup\$
1
  • \$\begingroup\$ I have updated code based on the suggestion. \$\endgroup\$
    – pstrjds
    Feb 9, 2011 at 16:24
3
\$\begingroup\$

FillTreeNodes looks pretty much OK to me, I can't see any major ways to improve it. I would suggest, though, that the StringBuilder can be replaced with a simple "/" + parentName.

I'n not convinced preprocessing the list is going to give you much. That said, we can remove the need to sort the list by removing any leaves we come across when trying to add the path to the list.

Notice that by breaking the logic out into a separate function, we avoid the need for "found" flags.

List<string> BuildLeafList()
{
    var leafList = new List<string>();
    foreach (var folder in GetListOfFolders())
    {
        var root = folder.Key;
        var leaf = folder.Value;
        string path = string.Concat(root, "/", leaf);
        AddPathToLeafList(path, leafList);
    }

    return leafList;
}

private void AddPathToLeafList(string path, List<string> leafList)
{
    for (int i = 0; i < leafList.Count;)
    {
        string leaf = leafList[i];

        // If we have a leaf that already encompasses path, stop
        if (leaf.StartsWith(path, StringComparison.Ordinal))
        {
            return;
        }

        // If path encompasses leaf, remove leaf
        if (leaf.StartsWith(path, StringComparison.Ordinal))
        {
            leafList.RemoveAt(i);
        }
        else
        {
            i += 1;
        }
    }

    leafList.Add(path);
}

I'm not too happy about the way the loop works though. It seems a little awkward to sometimes increment i, and other times not.

\$\endgroup\$
5
  • \$\begingroup\$ I think you meant path.StartsWith(leaf... in the second if block. I initially had something like this, but in the long run, I believe the sorting is more performative. This implementation would possibly require iterating the entire list each time I add a leaf. Also, removing from a list is and O(N) operation. In the implementation I presented, sorting should be O(NLogN) and then I make one more pass through the list so at worst case N^2LogN (if I am reading my code right that is). \$\endgroup\$
    – pstrjds
    Mar 29, 2011 at 5:03
  • \$\begingroup\$ With regards to StringBuilder. The string is being appended to in each loop iteration. I know I am copying the string out, but it seemed like the preallocated StringBuilder set to the length that it will eventually end up should be more performative for the append. If I did something like nodeName += ("/" + parentName) then there would be at least 2 string allocations in each iteration of the loop. Using SB there should be only one, the sb.ToString() call. I can't say I looked at the IL though to verify that, my assumption is based on several articles regarding strings and StringBuilder. \$\endgroup\$
    – pstrjds
    Mar 29, 2011 at 5:08
  • \$\begingroup\$ In your implementation you are also potentially iterating through the entire list for each leaf, after the sort. I /think/ in the worst case, in terms of number of iterations over the list, both implementations similar enough. However, you have the overhead of the sort. I did, however, forget to factor in the cost of remove, which does make mine more expensive :) \$\endgroup\$
    – ICR
    Mar 29, 2011 at 18:48
  • \$\begingroup\$ As for the StringBuilder, I missed that the initialisation was outside of the loop. I am obviously not on my game :) \$\endgroup\$
    – ICR
    Mar 29, 2011 at 18:49
  • \$\begingroup\$ No problem - I was writing my comments late at night, so not sure if I was correct or not. I think both implementations end up close enough as far as performance. The remove from the list was the place that I thought it might end up less performative. I appreciate the feedback though. At this point, my code is already in the "wild" so it will stay as it is for now :) When I get back to working on the next version, I am going to be redoing some of this framework so I am probably going to implement the code more along these lines. So thanks :) \$\endgroup\$
    – pstrjds
    Mar 30, 2011 at 13:39
1
\$\begingroup\$

Not sure whether this is better for your application or not, but it is different. This is a pattern I used briefly a while back. It's works OK for sequentially dumping ordered hierarchies where each node's level is known. For typical or more complex recursive relationships I believe this to be a bad choice for maintainability and quality reasons.

using System;
using System.Collections.Generic;
using System.IO;
using System.Windows.Forms;

namespace WindowsFormsApplication1
{
    public partial class Form1 : Form
    {
        private void BuildFolderList(List<KeyValuePair<int, string>> folderInfoList, string entryPoint, int level)
        {
            try
            {
                foreach (string directory in Directory.GetDirectories(entryPoint))
                {
                    folderInfoList.Add(new KeyValuePair<int, string>(level, Path.GetFileName(directory)));
                    BuildFolderList(folderInfoList, directory, level + 1);
                }
            }
            catch (UnauthorizedAccessException ex)
            {
                // access to the folder was denied
            }
        }

        private void BuildFolderTree(object sender, EventArgs e)
        {
            List<KeyValuePair<int, string>> folderInfoList = new List<KeyValuePair<int, string>>();

            string rootLevelPath;

            // you can add multiple root-level paths whose subfolders can optionally be added recursively.

            rootLevelPath = @"C:\Projects";
            folderInfoList.Add(new KeyValuePair<int, string>(0, Path.GetFileName(rootLevelPath)));
            BuildFolderList(folderInfoList, rootLevelPath, 1);

            rootLevelPath = @"C:\Temp";
            folderInfoList.Add(new KeyValuePair<int, string>(0, Path.GetFileName(rootLevelPath)));
            // note: omitting subfolders for this item

            rootLevelPath = @"C:\Program Files";
            folderInfoList.Add(new KeyValuePair<int, string>(0, Path.GetFileName(rootLevelPath)));
            BuildFolderList(folderInfoList, rootLevelPath, 1);

            tv.BeginUpdate();
            try
            {
                tv.Nodes.Clear();

                TreeNode tn = null;
                int cur_lvl = -1, new_lvl;
                string nodeText;

                for (int i = 0; i < folderInfoList.Count; i++)
                {
                    new_lvl = folderInfoList[i].Key;
                    nodeText = folderInfoList[i].Value;

                    if (new_lvl == 0)
                    {
                        tn = tv.Nodes.Add(nodeText);
                    }
                    else
                    {
                        if (new_lvl == cur_lvl)
                        {
                            tn = tn.Parent.Nodes.Add(nodeText);
                        }
                        else if (new_lvl > cur_lvl)
                        {
                            tn = tn.Nodes.Add(nodeText);
                        }
                        else
                        {
                            while (tn.Level >= new_lvl)
                            {
                                tn = tn.Parent;
                            }

                            tn = tn.Nodes.Add(nodeText);
                        }
                    }
                    cur_lvl = new_lvl;
                }
            }
            finally
            {
                tv.EndUpdate();
            }
        }

        public Form1()
        {
            InitializeComponent();
        }
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ I think this pattern would work if I was building a list of folders from a recursive directory search. In my case I am not doing that. The code in GetListOfFolders() is pulling together lists of folder/leaf nodes from multiple SharePoint sites. \$\endgroup\$
    – pstrjds
    Mar 29, 2011 at 18:14
0
\$\begingroup\$

I updated the code based on the LINQ answer that was provided and this is what ended up as my final production code. I felt it was a little cleaner and easier to read than the code that was posted originally.

List<string> BuildFinalList()
{
    // This list is a collection of root folder paths and leaf folder names
    // i.e. pair("/root/node/node", "node"), pair("/root/node", "node)
    List<KeyValuePair<string, string>> folders = GetListOfFolders();
    var paths = new List<string>();
    foreach(var folder in folders)
    {
        var leaf = folder.Value;
        var root = folder.Key;
        paths.Add(string.Concat(root, "/", leaf);
    }
    paths.Sort(_INVERSE_LENGTH_COMPARE); // this sorts the list longest to shortest

    // Iterate the computed paths from longest to shortest, if a path is not
    // encompassed by an existing path in the final list, add it to the
    // final list, otherwise just move to the next path
    var finalList = new List<string>();
    foreach(var path in paths)
    {
        if (!finalList.Any(item => item.StartsWith(path, StringComparison.Ordinal)))
        {
            finalList.Add(path);
        }
    }
    return finalList;
 }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.