Data structure for mapping URLs or local paths

I've been trying to workout a good way of doing this fast but I'm not sure what will be the most optimal, I'm hoping some of you more experienced developers can assist via your Data Structures knowledge :-)

Essentially I have a list of paths (Eg. C:\inetpub\wwwroot\, C:\www\websites\vhosts\somesite.com\, D:\www-mirror\websites\vhosts\somesite.co.uk), I have to check that the current file I'm working on (say C:\inetpub\wwwroot\styles\style.css) exists in the preconfigured list of paths.

So what I initially thought was to interate my list of items and do a CurrentFilename.StartsWith(PreconfigureListOfPathsPathName). But I'm iterating through the list quite regularly and it slows down as the list can contain sometimes 10, othertimes 1000 (clients on a server) paths.

What would you suggest as a fast solution for this problem? I'm writing in C# 3.5, this is only a small (but a critical) section of the project.

I thought about binary search trees, breaking down the paths and then doing a treemap and iterating through each path. But I'm not sure if its correct as we could have lots of nodes.

D:\www-mirror\websites\vhosts\somesite.co.uk\
D:\www-mirror\websites\vhosts\somesite.com\
D:\www-mirror\websites\vhosts\somesite.org\
D:\www-mirror\websites\vhosts\somesite.pl\

Tree map:

www-mirror->websites->vhosts->somesite* (has 4 nodes)
www-mirror->blah->woah->okay

But it looks a bit wonky.

Answers


Initialize a HashSet with the preconfigured paths. Then for each file to test, cut down the path from the end and probe the HashSet at each iteration:

class PreconfiguredPaths {
  private readonly HashSet<string> known = new HashSet<string>();

  public PreconfiguredPaths(params string[] paths) {
    foreach (var p in paths)
      known.Add(Normalize(p));
  }

  public string Parent(string path) {
    path = Normalize(path);

    while (path.Length > 0) {
      if (known.Contains(path))
        return path;
      else if (!path.Contains("\\"))
        break;

      path = Regex.Replace(path, @"\\[^\\]+$", "");
    }

    return null;
  }

  private string Normalize(string path) {
    return Regex.Replace(path, "\\\\+", "\\").TrimEnd('\\').ToLower();
  }
}

For example:

var paths = new PreconfiguredPaths(
  @"C:\inetpub\wwwroot\",
  @"C:\www\websites\vhosts\somesite.com\",
  @"D:\www-mirror\websites\vhosts\somesite.co.uk"
);

string[] files = {
  @"C:\inetpub\wwwroot\styles\style.css",
  @"F:\foo\bar\baz",
  @"D:\",
};

foreach (var f in files)
  Console.WriteLine("{0} => {1}", f, paths.Parent(f));

Output:

C:\inetpub\wwwroot\styles\style.css => c:\inetpub\wwwroot
F:\foo\bar\baz =>
D:\ =>

Need Your Help

Windows Phone 8 Webbrowser (zoom)

c# windows-phone-8 windows-phone

I'm creating a Windows Phone 8 app, but I'm stuck at the last part...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.