c# recursive generics data structure searching

Question

Hi folks, been struggling with this for a couple of days now and still stumped. i have a data structure that starts with containers that can hold other containers, and eventually leaf nodes. i'm looking for a way of being to iterate thru elements of a type directly, without pulling them into another collection so i can operate on them in place and then save the resulting structure out.

The code below is a noddy version, and if you set a break point on each findElements function you'll see that it drops out without recursing. this is on mono and ms runtimes, so i'm sure it's me not getting something rather than a bug ;)

also, the function should ideally be

IEnumerable<object> findElements<T>();

but i can't get the cast to work on this line then :

if (this is T) yield return this;

should ideally be

if (this is T) yield return (T)this;

thanks for any suggestions / clarity / light

using System;
using System.Collections.Generic;
using System.Text;

namespace covariantTest {
class MainClass {
 public static void Main(string[] args) {
  Console.WriteLine("Starting");
  Document root = new Document("rooty");
  root.Children.Add(new File("file 1"));
  root.Children.Add(new File("file 2"));
  Document doc2 = new Document("doc2");
  File file3 = new File("file 3");
  file3.Lines.Add(new Line("line 1 file 3"));
  file3.Lines.Add(new Line("line 2 file 3"));
  doc2.Children.Add(file3);
  File file4 = new File("file 4");
  file4.Lines.Add(new Line("stuff about stuff"));
  file4.Lines.Add(new Line("Babylon n ting"));
  file4.Lines.Add(new Line("last line"));
  doc2.Children.Add(file4);
  root.Children.Add(doc2);

  // find the lines
  foreach (object obj in root.findElements<Line>()) {
   Line line = obj as Line;
   Console.WriteLine(line.Contents);
  }
  // done
  Console.WriteLine("Press enter to finish");
  Console.ReadLine();
 }
}// Main

#region classes
public class Line : ISearchable {
 private string _contents = string.Empty;

 public Line() {}
 public Line(string contents) {
  _contents = contents;
 }
 #region properties
 public string Contents {
  get { return _contents; }
  set { _contents = value; }
 }
 #endregion properties
 public IEnumerable<object> findElements<T>() {
  if (this is T) yield return this;
 }
}// Line

public class File : Container {
 private List<Line> _lines = new List<Line>();

 public File() : base() {}
 public File(string name) : base(name) {}

 #region properties
 public List<Line> Lines {
  get { return _lines; }
  set { _lines = value; }
 }
 #endregion properties
 public override IEnumerable<object> findElements<T>() {
  if (this is T) yield return this;
  else base.findElements<T>();
 }
}// File

public class Document : Container {

 public Document() : base() {}
 public Document(string name) : base(name) {}

 public override IEnumerable<object> findElements<T>() {
  if (this is T) yield return this;
  else base.findElements<T>();
 }

}// Document

public abstract class Container : ISearchable {
 private string _name = string.Empty;
 private List<Container> _children = new List<Container>();

 public Container() {}
 public Container(string name) {
  _name = name;
 }
 #region properties
 public string Name { 
  get { return _name; } 
  set { _name = value; }
 }
 public List<Container> Children { 
  get { return _children; } 
  set { _children = value; }
 }
 #endregion properties
 #region interfaces
 public virtual IEnumerable<object> findElements<T>() {
  if (this is T) yield return this;
  foreach (Container item in _children) {
   item.findElements<T>();
  }
 }
 #endregion interfaces
}// Container
#endregion classes

#region interfaces
public interface ISearchable {
 IEnumerable<object> findElements<T>();
}
#endregion interfaces
}// namespace

Answer 1

Hi there.
I think you code is a bit complex, but I may have bad understood you target.
Anyway, here is a sample to scan in a "flat-fashion" your tree. I also used a very small code just to show-how, but obviously you have to work on.

namespace ConsoleApplication3
{
    //this is a node of your tree, but you may add whatever you want inside
    class Item
    {
        public List<Item> Items { get; set; }
    }


    class Program
    {
        static void Main(string[] args)
        {
            //define the tree structure
            var tree = new Item();

            // (complete your tree-structrure)

            //define the action delegate
            Action<Item> action = (item) => Console.WriteLine(item);

            //scan the hierarchy
            Scan(
                tree,
                typeof(Item),
                action);
        }


        //here is the flat-scan function, the "typeToFind" here is just
        //for example and have very little sense to be in
        static void Scan(
            Item startItem,
            Type typeToFind,
            Action<Item> action)
        {
            var temp = new List<Item>();
            temp.Add(startItem);

            while (temp.Count > 0)
            {
                var item = temp[0];
                temp.RemoveAt(0);

                if (typeToFind.IsInstanceOfType(item))
                {
                    action(item);
                }

                temp.AddRange(item.Items);
            }
        }
    }
}

Hope this helps. Cheers.

Answer 2

How do you expect it to work? If I understand it correctly, then yield does not work when called from another function (so if you call base.findElements then you ain't gonna get any results from it). I suggest rewriting it without yield. To avoid creating many lists, I would pass list as a parameter, in such a way:

public interface ISearchable {
    void doFindElements<T>(List<T> putThemHere);
}

// this is extender for syntactical sugar
public static class SearchableExtender
{
    public static IEnumerable<T> findElements<T>(this ISearchable obj)
    {
        List<T> result = new List<T>();
        obj.doFindElements(result);
        return result;
    }
}

public abstract class Container : ISearchable {
...
    public virtual void doFindElements<T>(List<T> putThemHere)
    {
        if (this is T) putThemHere.Add(this);
        foreach (Container item in _children) { item.doFindElements(putThemHere); }
    }
...
}

By the way, you don't need to override doFindElements in Document, inherited version from Container will do OK, as "this" would mean a Document here. Implementation of File is completely wrong. Base Container class would not see Lines property and instead would use empty Children property. There are two ways to work around this:

1. You need to kill _lines and instead work with _children from the base class (for example, you can make Collection<Line> descendent that would be a wrapper around _children class by overriding InsertItem, SetItem, RemoveItem and ClearItems and calling appropriate methods of _children).

2. Remove _children from Container, instead make virtual abstract function IEnumerable GetChildElements() that each descendent would implement and return its own List<> of child elements. In doFindElements you would call that function instead of _children. You can even make second base class, like UntypedContainer: Container that would declare List<Container> _children, override GetChildElements() to return _children and inherit Document from it. File would still be inherited from simple Container, as it have its own children list.

The second way is simpler and better.