So there is no way I can override a value in IPersistentCache? e.g. I can't do:

cache.Set("a", "test");

cache.Set("a", "nother test");

Without this limitation it should be easier. I use the path to the directory or file to be cached as a key in IPersistentCache and put the path + version to the file as a single item in its value arrays (with some separator like ":"). Then I add the item to the parent directory's item array (again path + version).

Of course adding this item means getting the complete array, building another array and setting this as the new value, which is far from ideal, but you could propably make this more performant by growing the array in larger sizes and setting items in the returned instance directly (if Get doesn't return a clone, but the actual instance of the array).

Another issue with this solution is that you have to enumerate through all versions of files in a directory even if you don't need them.

Other than that the lookup is simply done by getting the values for the path specified in ListFilesAndFolders enumerating them and depending on the recursion mode make further lookups for subdirectories.

Without the possibility to override a value in the cache, you could still simulate something like this with some sort of convention. For example, the first 2 entries are stored in key "PATHNAME", the next 4 are stored in "PATHNAME:2", the next 8 in "PATHNAME:3" ...

But Of course this requires further lookups and is ugly as hell...

Interesting challenge however, I'm excited to see your solution.

Thomas,

Each key have a single unique value.

You can do:

cache.Set("a", "test");

cache.Set("a", "nother test");

and then cache.Get("a") would return "another test".

You are in the right path.

what's your target perf for Add / List? O(?)

O(1), I init the list with the 101 capacity, so it should do no memory alloc

I know this does not meet all of your requirements, but to help ease my easily-confused brain, here is a rough draft, unit tested based upon your usage data. Note that when you say "no external dependencies" I assume that means no list processing, and my array experience is weak at best.

public class FileSystemCache : IFileSystemCache

{

    IPersistentCache cache;


    public FileSystemCache(IPersistentCache cache)

    {

        this.cache = cache;

    }


    public void Add(VersionedFile[] files)

    {

        foreach (VersionedFile root in files)

        {

            string[] paths = new string[files.Length];

            int files_processed = 0;


            foreach (VersionedFile child in files)

            {

                if (path_is_root(root, child))

                {

                    paths[files_processed] = child.Name;

                    files_processed++;

                }

            }


            this.cache.Set(get_key(root.Name,root.Version), paths);

        }

    }


    private static bool path_is_root(VersionedFile root, VersionedFile      child)

    {

        return root.Version == child.Version &&    child.Name.Contains(root.Name);

    }


    public string[] ListFilesAndFolders(string root, int version, Recursion recursion)

    {

        string[] files = this.cache.Get( get_key(root, version));

        int max_depth = get_max_depth(files.Length, recursion);

        string[] files_to_return = new string[files.Length];

        int files_processed = 0;


        foreach (string file_path in files)

        {

            if (get_depth(root, file_path) <= max_depth)

            {

                files_to_return[files_processed] = file_path;

                files_processed++;

            }

        }


        return files_to_return;

    }


    private static string get_key(string root, int version)

    {

        return root + ":" + version;

    }


    public int get_depth(string root, string child)

    {

        char[] delimiter = new char[] { '/' };

        return (child.Split(delimiter, StringSplitOptions.RemoveEmptyEntries).Length - root.Split(delimiter, StringSplitOptions.RemoveEmptyEntries).Length);

    }


    private int get_max_depth(int number_of_files, Recursion recursion)

    {

        switch (recursion)

        {

            case Recursion.None:

                return 0;

            case Recursion.OneLevel:

                return 1;

            default:

                return number_of_files;

        }

    }


}

I have posted a solution at my website, <a href="http://sharpbites.blogspot.com/2008/04/ayendes-challenge-2-directory-tree.html>here . :)