CODEWITHSUNDEEP
c#
Digital_Utopia
Digital_Utopia

Reputation: 856

Looking for a faster way of searching for a property in a List of classes

Below is the class I'm using to represent a tree structure, for displaying files and folders of a game's archive format. 

public class DirNode : INotifyPropertyChanged
{
     public String Name { get; set; }
     public int Index { get; private set; }
     public int FileIndex { get; private set; }
     public int Type { get; private set; }
     public List<DirNode> Directories { get; set; }
     public List<FileNode> Files { get; set; }

     public DirNode(String n, int index, int type, int fi)
     {
           Name = n;
           Directories = new List<DirNode>();
           Files = new List<FileNode>();
           Index = index;
           Type = type;
           FileIndex = fi;
     }
}

Below is a method of the class that I'm currently using to parse path strings into the tree. It worked well enough when I was only loading one archive, but when trying to "mount" multiple archives, the inefficiency certainly shows

 public void AddPath(String[] path, int index, int fileIndex)
        {
            if (path.Length > 1) //It's a Folder;
            {
                bool found = false;
                int i = 0;
                while (i < this.Directories.Count && found == false)//search to see if this folder already exists
                {
                    if (this.Directories[i].Name == path[0])
                    {
                        found = true;
                        String[] newPath = new String[path.Length - 1];
                        Array.Copy(path, 1, newPath, 0, newPath.Length);
                        this.Directories[i].AddPath(newPath, index,fileIndex);
                        return;
                    }

                    i++;
                }
                if (found == false) //new item
                {
                    DirNode dn = new DirNode(path[0], -1, 0,fileIndex);
                    this.Directories.Add(dn);
                    String[] newPath = new String[path.Length - 1];
                    Array.Copy(path, 1, newPath, 0, newPath.Length);
                    this.Directories[this.Directories.Count - 1].AddPath(newPath, index,fileIndex);
                }
            }
            else if (path.Length == 1) //a file!
            {
                DirNode fn = new DirNode(path[0], index, 1,fileIndex);
                this.Directories.Add(fn);
                return;
            }
            else
            {
                //really no reason why we should be here. 
                return;
            }
        }

I know BinarySearch requires a pre-sorted list, which won't work, as the lists aren't sorted until after the tree is assembled. But it is, ultimately sorted, so a Hash won't work either. If anybody has any ideas, I'd love to hear them.

Of course, if anybody knows of a virtual implementation of the .NET DirectoryInfo class, that would likely even be better.

Upvotes: 1

Views: 40

Answers (1)

Lucero
Lucero

Reputation: 60190

Why don't you store the items in Directories and Files sorted at insertion time, so that you can actually perform a binary search on each directory level? The BinarySearch() on the List class will give you the index if found and the index complement (use the ~ operator) when not found, so that you know the index where the new item needs to be inserted right away.

Something like this (not tested in any way, just hacked down in the editor):

Class for comparing the name of two DirNodes:

internal class DirNodeNameComparer: IComparer<DirNode> {
    public static readonly DirNodeNameComparer Default = new DirNodeNameComparer();

    public int Compare(DirNode x, DirNode y) {
        return string.Compare(x.Name, y.Name);
    }
}

Your AddPath method updated to keep a sorted representation:

public void AddPath(String[] path, int index, int fileIndex)
{
    if (path.Length > 1) //It's a Folder;
    {
        DirNode dn = new DirNode(path[0], -1, 0, fileIndex);
        int i = this.Directories.BinarySearch(dn, DirNodeNameComparer.Default);
        if (i < 0) {
            i = ~i;
            this.Directories.Insert(i, dn);
        }
        String[] newPath = new String[path.Length - 1];
        Array.Copy(path, 1, newPath, 0, newPath.Length);
        this.Directories[i].AddPath(newPath, index,fileIndex);
        return;
    }
    else if (path.Length == 1) //a file!
    {
        DirNode fn = new DirNode(path[0], index, 1, fileIndex);
        int i = this.Directories.BinarySearch(fn, DirNodeNameComparer.Default);
        this.Directories.Insert(~i, fn); // really Directories?
        return;
    }
    else
    {
        //really no reason why we should be here. 
        return;
    }
}

Upvotes: 1

Related Questions