Search through HierarchicalData with recursion

Question

I am building a treeview with a list of ScanItem. The class of ScanItem is actually:

public class ScanItem
    {
        public string FullPath { get; set; }
        public string Name
        {
            get
            {
                return Path.GetFileName(FullPath);
            }

        }
        public DateTime ModifiedDate { get; set; }
        public DateTime CreatedDate { get; set; }
        public FileAttributes Attributes { get; set; }
        public bool IsDirectory { get; set; }


        public string Extension
        {
            get
            {
                if (IsDirectory)
                    return "Folder";
                else
                    return Path.GetExtension(Name);
            }
        }

        public UInt64 Size { get; set; }            
    }

In order for me to create a treeview I needed to create two other classes in order to distinguish the folders and files in my treeview:

    public class ScanFile : ScanItem
    {

    }
    public class ScanDir : ScanItem 
    {
        public List<ScanItem> Items { get; set; }
        public ScanDir()
        {
            Items = new List<ScanItem>();
        }                
    }

Note that the class ScanFile is just like the ScanItem and the ScanDir class has an extra property called Items and will contain a list of items of itself.

So if I where to iterate through this direcotory (C:\Temp):

my List will actually contain:

note that if I expand one ScanDir object I will get another List:

in order to populate the following treeview:

So I was able to populate this list using recursion by searching for files and directories in a specific path.

I just wanted to explain my situation because there are several places in the internet that enable you to filter a treeview and that is what I actually want to do. But it will be nice if I can iterate through each item in List and then remove it if some criteria is not met:

I have actually tried using the following recursive method to filter my results.

public List<ScanItem> search(List<ScanItem> items)
    {
        var filter = new List<ScanItem>();

        foreach (var item in items)
        {
            if (!item.FullPath.Contains("stringIwantToLookFor")) continue;
            filter.Add(item);
            if (item.IsDirectory)
            {
                search(((ScanDir)item).Items);                    
            }                
        }

        return filter;
    }

I think that if an item is found I need to add all the parent root directories and that's why it does not work. The reason why I want to build my own recursion method is because I want to be able to filter the treeview based on spesific criteria.

EDIT:

In other words if I want to have all the items that contain "X.txt" in my listview I want to just see:

Answer 1

so If I am looking for the files that contain foo this method will populate the files that contain foo in the list 'newList' . I would have to set that list equal to a new list before calling that method. I am obviously missing basic implementation such as changing foo for a parameter etc. I am also missing to remove the empty directories I am working on that.

    private List<ScanDir> history = new List<ScanDir>();
    private ScanDir LastDir;
    private List<ScanItem> newList = new List<ScanItem>();
    public void Search(List<ScanItem> allItems) //adds files that contain foo
    {
        bool updateLastDir = false;

        foreach(ScanItem s in allItems)
        {
            if (updateLastDir)
            {
                history = (from a in history
                           select a).Distinct().ToList();

                LastDir = null;
                for (int i = history.Count - 1; i >= 0; i--)
                {
                    if (history[i].FullPath == Directory.GetParent(s.FullPath).ToString())
                    {
                        LastDir = history[i];
                        break;
                    }                        
                }

                updateLastDir = false;                                        
            }
            if (s.IsDirectory)
            {
                var temp = new ScanDir { FullPath = s.FullPath, IsDirectory = true, comparePath = s.comparePath, Attributes = s.Attributes };

                if (LastDir == null)
                {
                    newList.Add(temp);                        
                }
                else
                {
                    LastDir.Items.Add(temp);

                }

                LastDir = temp;
                history.Add(LastDir);

                Search(((ScanDir)s).Items);

                history.RemoveAt(history.Count - 1);

                updateLastDir = true;


            }
            else
            {
                if (s.Name.Contains("Foo")) // then add it
                {
                    if (LastDir == null)                        
                        newList.Add(s);                        
                    else                        
                        LastDir.Items.Add(s);                       
                }
            }
        }

    }

Answer 2

I would do it like this: create public abstract ScanItem Seach(string s) on your ScanItem. You can then call it with the string you want to search for.

The actual implementation would look like this:

ScanFile:

public override ScanItem Seach(string s)
{
    if (Name.Contains(s))
        return this;

    return null;
}

ScanDir:

public override ScanItem Seach(string s)
{
    var results = Items.Select(i => i.Seach(s)).Where(i => i != null).ToList();
    if (results.Any())
    {
        var result = (ScanDir)MemberwiseClone();
        result.Items = results;
        return result;
    }

    return null;
}

The implementation in ScanFile is easy: if the file matches, return it, else return null. In ScanDir, call Search on all child items recursively. If any of them returned non-null, create a copy of the current object and set the Items of the copy only to those that matched. If none matched, return null.

Note that this will search only through the names of files, not directories. But if you want to do that, such modification is going to be straight-forward.

Answer 3

I realized my comment to your post might not have been descriptive enough, so I've written some C#-ish pseudocode to demonstrate what I was getting at.

Here's an example of using the Visitor pattern to implement search in a polymorphic, loosely-coupled way:

interface FilesystemVistor
{
  void Visit (FilesystemItem item);
}
interface FilesystemItem
{
  void Accept(FilesystemVistor visitor);
  string Name;
}

class Directory : FilesystemItem
{
  private FilesystemItem[] _children;
  public void Accept(FilesystemVistor visitor) {
    visitor.Visit(this);
    foreach(FilesystemItem item in _children)
    {
      visitor.Visit(item);
    }
  }
}
class File : FilesystemItem
{
  public void Accept(FilesystemVistor visitor) {
    visitor.Visit(this);
  }
}

class FilesystemSearcher : FilesystemVistor
{
  private List<string> _results;
  public void Visit(FilesystemItem item) {
    if (item.Name == "Foo") { _results.Add(item.Name); }
  }
}

This "visitor pattern"-based design will allow you to implement any kind of search without having the search algorithm having to "know" anything about the structure of the file system and the file system doesn't need an extra property like "IsDirectory" to expose its implementation details.

Answer 4

You should treat the directories a little different because now, if the root directory does not meet the criteria the routine will exit immediately.

Try this: change your ScanItem a little:

public class ScanItem {
  ...
  public virtual bool IsDirectory { get; }
  ...
}

add this to your scanFile:

public class ScanFile : ScanItem {
  public override bool IsDirectory {
    get { return false; }
  }
}

and this to your scanDir:

public class ScanDir : ScanItem {
  public List<ScanItem> Items { get; set; }
  public ScanDir() {
    Items = new List<ScanItem>();
  }

  public ScanDir CopyWithoutChildren() {
    return new ScanDir() {
      FullPath = this.FullPath,
      ModifiedDate = this.ModifiedDate,
      CreatedDate = this.CreatedDate,
      Attributes = this.Attributes,
      Size = this.Size
    };
  }

  public override bool IsDirectory {
    get { return true; }
  }
}

Now do the filtering on the files, omitting empty directories:

public List<ScanItem> search(List<ScanItem> items) {
  var filter = new List<ScanItem>();

  foreach(var item in items) {
    if(item.IsDirectory) {
      List<ScanItem> potential = search(((ScanDir)item).Items);
      if(potential.Count > 0) {
        ScanDir dir = ((ScanDir)item).CopyWithoutChildren();
        dir.Items.AddRange(potential);
        filter.Add(dir);
      }
    } else {
      if(!item.FullPath.Contains("stringIwantToLookFor")) continue;
      filter.Add(item);
    }
  }

  return filter;
}

I didn't test it, but I guess that should do what you want.