Problem
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];
}
}
}
}
Solution
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.
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.
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();
}
}
}
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;
}