11
\$\begingroup\$

I needed a function that would take a list of folders and removed all sub folders, so that only the top level folders stayed in the list.

For example, given the list:

c:\stuf\morestuff
c:\stuf\morestuff\sub1
c:\otherstuf
c:\otherstuf\sub1
c:\otherstuf\sub2

I wanted the list to be reduced to:

c:\stuf\morestuff
c:\otherstuf

So I came up with this solution:

// remove empty strings and sub folders
private static void CleanUpFolders(List<string> uniqueFolders)
{
    uniqueFolders.RemoveAll(
        delegate(string curFolder)
        {
            // remove empty
            if (string.IsNullOrEmpty(curFolder))
                return true;

            // remove sub paths
            if (uniqueFolders.Exists(
                delegate(string s)
                {
                    if (!string.IsNullOrEmpty(s) &&
                        curFolder.StartsWith(s) &&
                        string.Compare(s, curFolder) != 0)
                        return true;
                    return false;
                } ))
                return true;

            return false;
        }               
    );
}

This seems to work (not very well tested though) but I was left wondering about some things:

  • is there an issue with using variables inside anonymous methods that were declared outside?
  • any potential issues with nested anonymous methods?
  • any other issues or best practices worth mentioning?
\$\endgroup\$
12
\$\begingroup\$

is there an issue with using variables inside anonymous methods that were declared outside?

No, this is what anonymous methods are designed for! It is a very useful trick to keep up your sleeve. Read up on Closures. There are all sorts of things you can do with them.

Obviously there are issues with doing anything when you don't understand it fully, but the way you are using them in your code is what these things are all about!

any potential issues with nested anonymous methods?

Same thing.

any other issues or best practices worth mentioning?

Unless you are still using c# 2, the syntax has been simplified to use what is known as a lambda. Instead of using

delegate(string curFolder) { ..code.. }

you can just go :

curFolder => ..code..

As RemoveAll takes a Predicate, you can also lose the return key word. As long as the statement evaluates to True or False, it will take that as the return.

You have some code that is basically going :

if x == true
    return true
return false

This can be simplified to :

return x

With those two things, your code could be simplified to :

 uniqueFolders.RemoveAll(
        curFolder => 

            string.IsNullOrEmpty(curFolder) ||
                   uniqueFolders.Exists( s=> 
                        !string.IsNullOrEmpty(s) &&
                        curFolder.StartsWith(s) &&
                        string.Compare(s, curFolder) != 0)

    );

Its a bit of a mouthfull. You may want to factor out a new method.

uniqueFolders.RemoveAll( curFolder => IsNotRootFolder(uniqueFolders, curFolder ) );

bool IsNotRootFolder ( uniqueFolders, curFolder )
{
   return string.IsNullOrEmpty(curFolder) ||
          uniqueFolders.Exists( s=> 
            !string.IsNullOrEmpty(s) &&
            curFolder.StartsWith(s) &&
            string.Compare(s, curFolder) != 0)
}
\$\endgroup\$
  • 2
    \$\begingroup\$ To be clear, there is a potential issue with using variable in anonymous methods which are declared outside the anonymous method; you don't have that issue here, but you should make sure you understand the concept of "Access to Modified Closure" - stackoverflow.com/questions/235455/access-to-modified-closure \$\endgroup\$ – E.Z. Hart Mar 10 '11 at 19:47
5
\$\begingroup\$

One consideration is performance. Your current code is scanning the list as part of RemoveAll (that's O(n)) and for each item it is calling Exists on the list (that's also O(n) because it has to loop the entire list). The Exists call has the potential to get cheaper as you get closer to done if items are removed but in the worst case it looks like an O(N^2) implementation. Instead, use a HashSet - this makes lookups O(1) and results in an O(n) implementation.

Also, use the framework Path class to get the parent folders instead of StartsWith - your current code treats c:\john as a parent of c:\johnny\appleseed and removes c:\johnny\appleseed from the list.

private static void CleanUpFolders(List<string> uniqueFolders)
{
    var folderLookup = new HashSet<string>(uniqueFolders);
    uniqueFolders.RemoveAll(x => String.IsNullOrEmpty(x) ||
                                 x.Generate(Path.GetDirectoryName)
                                     .Skip(1) // the original
                                     .TakeWhile(p => p != Path.GetPathRoot(p))
                                     .Any(folderLookup.Contains));
}

assuming generically reusable Generate extension method

public static class TExtensions
{
    public static IEnumerable<T> Generate<T>(this T initial, Func<T, T> next) 
    {
        var current = initial;
        while (true)
        {
            yield return current;
            current = next(current);
        }
    }
}

test:

public void Should_only_keep_parent_directories()
{
    var directories = new List<string>
        {
            null,
            "",
            @"c:\bob",
            @"c:\john",
            @"c:\johnny\appleseed",
            @"c:\bob\mike\nick",
            @"C:\a\c",
            @"c:\stuf\morestuff",
            @"c:\stuf\morestuff\sub1",
            @"c:\otherstuf",
            @"c:\otherstuf\sub1",
            @"c:\otherstuf\sub1a",
            @"c:\otherstuf\sub2"
        };

    CleanUpFolders(directories);
    directories.Count.ShouldBeEqualTo(6);
    directories.ShouldContainAll(new[]
        {
            @"c:\bob",
            @"c:\stuf\morestuff",
            @"c:\otherstuf",
            @"C:\a\c",
            @"c:\john",
            @"c:\johnny\appleseed"
        });
}    
\$\endgroup\$
  • 1
    \$\begingroup\$ if you added c:\a\b to the directories list then c:\a would be added to parents and c:\a\b would be removed. but there is no c:\a in the list to cover it. \$\endgroup\$ – Brian Reichle Mar 11 '11 at 2:17
  • \$\begingroup\$ Good point @Brian. I revised the implementation to cover this case. \$\endgroup\$ – Handcraftsman Mar 11 '11 at 15:47
  • \$\begingroup\$ Now if you add c:\bob and c:\bob\mike\nick then the latter will not be removed because c:\bob\mike is not also in the list. \$\endgroup\$ – Brian Reichle Mar 11 '11 at 23:30
  • \$\begingroup\$ Yep, right again @Brian. Fixed. \$\endgroup\$ – Handcraftsman Mar 13 '11 at 18:13
3
\$\begingroup\$
is there an issue with using variables inside anonymous methods that were declared outside?

no, if an anonymous method accesses a local variable then C# will create a separate class to host the method and variable allowing it all to "just work". (*)

any potential issues with nested anonymous methods?

The only issue I see with the nested anonymous methods is that it makes the code ugly and hard to read, but then I find linq in general has this effect :).

any other issues or best practices worth mentioning?

Since your paths are windows paths, you may want to consider using case insensitive comparisons.

This is how I would have done it, it works off the basis that if you sort the list then all strings that start with the string at position X will be in a single block that appears immediately after it.

private static void CleanUpFolders(List<string> uniqueFolders)
{
    uniqueFolders.RemoveAll(string.IsNullOrEmpty);
    uniqueFolders.Sort(StringComparer.OrdinalIgnoreCase);

    int write = 0;
    string last = null;

    for (int read = 0; read < uniqueFolders.Count; read++)
    {
        string value = uniqueFolders[read];

        if (last = null || value.StartsWith(last, StringComparison.OrdinalIgnoreCase))
        {
            uniqueFolders[write] = value;
            last = value;
            write++;
        }
    }

    if (write < uniqueFolders.Count)
    {
        uniqueFolders.RemoveRange(write, uniqueFolders.Count - write);
    }
}

(*) if you change the referenced variable after creating the delegate, it will affect what the delegate sees which can be non-obvious, particularly if you create a delegate in a loop that accesses the index or current item.

At the end of the loop in this example, all delegates will return 10;

Func<int>[] bob = new Func<int>[10];

for(int i = 0; i < bob.Length; i++)
{
    bob[i] = () => i;
}

But at the end of this loop each will return it's own index.

for(int i = 0; i < bob.Length; i++)
{
    int j = i;
    bob[i] = () => j;
}
\$\endgroup\$
2
\$\begingroup\$

The other answers are already pretty much complete, but I'm wondering about the usage of your code.

Are these real folders, present on the system running the code? Do you have to receive the folders as a list of strings?

Brian Reichle already mentioned that string representation of folders are system dependant. Perhaps you are better of writing a solution based around the DirectoryInfo class.

This is a simple recursive solution using an extension method:

public static List<DirectoryInfo> GetTopFolders( this DirectoryInfo dir )
{
    List<DirectoryInfo> result = new List<DirectoryInfo>();

    DirectoryInfo[] subDirs = dir.GetDirectories();
    if ( subDirs.Length > 0 )
    {
        result.Add( dir );
        subDirs.ForEach( d => result.AddRange( GetTopFolders( d ) ) );
    }

    return result;
} 

It uses the following IEnumerable extension method:

public static void ForEach<T>( this IEnumerable<T> source, Action<T> action )
{
    foreach ( var item in source )
    {
        action( item );
    }
}

UPDATE:

Or even better using Linq and the EnumerateDirectories function. Note that the passed dir argument isn't included in this result.

public static IEnumerable<DirectoryInfo> GetTopFolders( this DirectoryInfo dir )
{
    return from d in dir.EnumerateDirectories("*", SearchOption.AllDirectories)
           where d.EnumerateDirectories().Any()
           select d;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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