none
Recursion in collections count? RRS feed

  • Question

  • I have a collection like so

     

    Parents.Child 

    ChildIsParent.FirstGrandChild

     

    and so on...

     

    my question is how would i return a count of total items i have in a recursive tree??? pass a method a collection it returns me and int of the total collection count.


    Give youself a round of applause!!
    Tuesday, May 3, 2011 8:29 PM

Answers

  • That is the most performance oriented way to do it.  However, if you need a method which does this without deriving a new collection:

    public int TotalNodeCount(NodeCollection collection)
    {
      int ret = collection.Count;
    
      foreach(Node node in collection)
      {
        ret += TotalNodeCount(node.Children);
      }
    
      return ret;
    
    }
    
    • Proposed as answer by Aspen VJ Wednesday, May 11, 2011 7:10 AM
    • Marked as answer by Aspen VJ Thursday, May 12, 2011 1:48 AM
    • Unmarked as answer by Aspen VJ Friday, May 13, 2011 4:49 AM
    • Marked as answer by Aspen VJ Tuesday, May 17, 2011 1:19 AM
    Wednesday, May 4, 2011 5:07 PM

All replies

  • If all of the elements in the tree are of the same type, e.g., Node, which has a collection called Children, then you can use this method:

     public static IEnumerable<T> Visit<T>(this T baseObject, Func<T, IEnumerable<T>> visitFunction, Func<T, bool> stopCondition = null)
        {
          if (baseObject == null)
          {
            throw new ArgumentNullException("baseObject");
          }
          if (visitFunction == null)
          {
            throw new ArgumentNullException("visitFunction");
          }
          if (stopCondition == null || !stopCondition(baseObject))
          {
            var children = visitFunction(baseObject);
            foreach (var child in children)
            {
              yield return child;
              var grandchildren = child.Visit(visitFunction, stopCondition);
              foreach (var grandchild in grandchildren)
              {
                yield return grandchild;
              }
            }
          }
        }

    The usage would be like this:

    class Node 
    {
      public IEnumerable<Node> Children { get; } 
    } 
    List<Node> nodes = new List<Node>(); 
    var allDescendents = from node in nodes select node.Visit(n=>n.Children).SelectMany(list=>list);
    var count = allDescendents.Count();
    HTH,

    Evan

     

     



    Tuesday, May 3, 2011 8:46 PM
  • Hi,

    It is interresting to implement it with Visitor pattern, But it is very simple with Aggregate method :

    using System.Collections.Generic;
    using System.Linq;
    
    namespace RecursiveCount
    {
      public class Asset
      {
        public int Id { get; set; }
        public List<Asset> Parents { get; set; }
        public List<Asset> Children { get; set; }
    
        public Asset(int id)
        {
          this.Id = id;
          this.Parents = new List<Asset>();
          this.Children = new List<Asset>();
        }
    
      }
    
      class Program
      {
        static void Main(string[] args)
        {
          Asset oAsset1 = new Asset(1);
          Asset oAsset2 = new Asset(2);
          Asset oAsset3 = new Asset(3);
          Asset oAsset4 = new Asset(4);
          Asset oAsset5 = new Asset(5);
    
          oAsset1.Children.Add(oAsset2);
          oAsset2.Parents.Add(oAsset1);
    
          oAsset1.Children.Add(oAsset3);
          oAsset3.Parents.Add(oAsset1);
    
          oAsset2.Children.Add(oAsset4);
          oAsset4.Parents.Add(oAsset2);
    
          oAsset3.Children.Add(oAsset4);
          oAsset4.Parents.Add(oAsset3);
    
          oAsset4.Children.Add(oAsset5);
          oAsset5.Parents.Add(oAsset4);
    
          // get all children count of oAsset1
          int count = RecursiveChildrenCount(oAsset1);
    
        }
    
        static int RecursiveChildrenCount(Asset oAsset)
        {
          if (oAsset.Children.Count == 0)
          {
            return 0;
          }
          else
          {
            return oAsset.Children.Count + oAsset.Children.Aggregate(0,
              (count, asset) => count += RecursiveChildrenCount(asset));
          }
    
        }
      }
    }
    
    
    Regards,


    aelassas.free.fr
    Tuesday, May 3, 2011 10:17 PM
  • Hello,

    Why do you need to iterate your tree to get that info ? this kind of data should be managed by you in each parent.

    The moment you add a new child to a parent, the add method should request the amount of items for this collection similarly the remove method should discount it.

    That way the total amount of items is always stored progressively.


    Eyal (http://shilony.net), Regards.

    Any fool can write code that a computer can understand. Good programmers write code that humans can understand. -- Martin Fowler.

    Tuesday, May 3, 2011 11:10 PM
    Moderator
  • Right Seems like I should be able to write a class that is derived from ArrayList oir List<MyObject> and it has a total property and evertime i call the add method I increment the count???? is that the correct thinking to have Eyal?
    Give youself a round of applause!!
    Wednesday, May 4, 2011 4:03 PM
  • That is the most performance oriented way to do it.  However, if you need a method which does this without deriving a new collection:

    public int TotalNodeCount(NodeCollection collection)
    {
      int ret = collection.Count;
    
      foreach(Node node in collection)
      {
        ret += TotalNodeCount(node.Children);
      }
    
      return ret;
    
    }
    
    • Proposed as answer by Aspen VJ Wednesday, May 11, 2011 7:10 AM
    • Marked as answer by Aspen VJ Thursday, May 12, 2011 1:48 AM
    • Unmarked as answer by Aspen VJ Friday, May 13, 2011 4:49 AM
    • Marked as answer by Aspen VJ Tuesday, May 17, 2011 1:19 AM
    Wednesday, May 4, 2011 5:07 PM
  • Right Seems like I should be able to write a class that is derived from ArrayList oir List<MyObject> and it has a total property and evertime i call the add method I increment the count???? is that the correct thinking to have Eyal?

    Sorry, but I can't figure whether you are sarcastic or really want an answer, I'll go and assume the latter.

    You can't just go and increment it, you need to check whether the child is already in the collection and whether it is changed.

    You need to notify the root of changes whenever the amount of elements for a certain child got changed, so certainly there should be some tracking mechanism.

    Regardless to my recommendation, recursions are the easiest to implement however they don't scale as good as you expect for complex trees, therefor I thought like giving you an alternative, that's all, take it or leave it.

    I think that these kind of things should be done moderately, I don't know whether it should scale or not, or how large it is, again I assume.


    Eyal (http://shilony.net), Regards.

    Any fool can write code that a computer can understand. Good programmers write code that humans can understand. -- Martin Fowler.



    Thursday, May 5, 2011 1:33 AM
    Moderator
  • I couldn't help my self leaving a comment on the three ways of doing recursive counting in nested collections presented in the posts. Especially when you read the second sentance of Eyal's signature - "Good programmers write code that humans can understand".

    Evan, very interesting method, but do you really think that someone who asks how to do recursive counting in the first place will know what's going on in this pattern, not to mention the use of 4.0 framework features in your sample. Besides, the amount of IL this produces isn't justified.

    My vote goes to CS001's solution. Simple, effective and human readable.

    /Calle

     


    - Still confused, but on a higher level -
    Thursday, May 5, 2011 8:29 AM
  • Hi,

    You do not need to create any class because It already exists :ObservableCollection<T> Class

    CollectionChanged gets fired when an item is added, removed, changed, moved, or the entire list is refreshed. You can subscribe to CollectionChanged to receive notifications.

    Kind regards,


    aelassas.free.fr
    Thursday, May 5, 2011 9:49 AM
  • Here is an example I made using recursions, once I'll have the time I'll implement the approach I've posted in my previous post.

    namespace Experimental.Console.Tree
    {
    	using System.Collections.Generic;
    
    	internal interface IRoot<T> : IEnumerable<T>
    	{
    		int Count { get; }
    
    		void Add(INode<T> node);
    
    		bool Remove(INode<T> node);
    
    		int GetTotalElements();
    	}
    }
    
    namespace Experimental.Console.Tree
    {
    	using System.Collections.Generic;
    
    	internal interface INode<T> : IEnumerable<T>
    	{
    		int Count { get; }
    
    		IList<IRoot<T>> Roots { get; }
    
    		bool HasChildren { get; }
    
    		void Add(T element);
    
    		bool Remove(T element);
    	}
    }
    
    namespace Experimental.Console.Tree
    {
    	using System;
    	using System.Collections;
    	using System.Collections.Generic;
    	using System.Linq;
    
    	internal class Root : IRoot<object>
    	{
    		private readonly IList<INode<object>> _nodes;
    
    		public Root()
    		{
    			_nodes = new List<INode<object>>();
    		}
    
    		#region Implementation of IRoot<object>
    
    		public int Count
    		{
    			get { return _nodes.Count; }
    		}
    
    		public void Add(INode<object> branch)
    		{
    			_nodes.Add(branch);
    		}
    
    		public bool Remove(INode<object> branch)
    		{
    			return _nodes.Remove(branch);
    		}
    
    		public int GetTotalElements()
    		{
    			int totalElements = 0;
    
    			foreach (var node in _nodes)
    			{
    				if (node.HasChildren)
    				{
    					//LINQ: totalElements += node.Roots.Sum(root => root.GetTotalElements());
    
    					foreach (var root in node.Roots)
    					{
    						totalElements += root.GetTotalElements();
    					}
    				}
    
    				totalElements += node.Count;
    			}
    
    			return totalElements;
    		}
    
    		#endregion
    
    		#region Implementation of IEnumerable
    
    		public IEnumerator<object> GetEnumerator()
    		{
    			return _nodes.GetEnumerator();
    		}
    
    		IEnumerator IEnumerable.GetEnumerator()
    		{
    			return GetEnumerator();
    		}
    
    		#endregion
    	}
    }
    
    namespace Experimental.Console.Tree
    {
    	using System;
    	using System.Collections;
    	using System.Collections.Generic;
    
    	internal class Node : INode<object>
    	{
    		private IList<IRoot<object>> _root;
    
    		private readonly IList<object> _items;
    
    		public Node()
    		{
    			_items = new List<object>();
    		}
    
    		#region Implementation of INode<object>
    
    		public int Count
    		{
    			get { return _items.Count; }
    		}
    
    		public IList<IRoot<object>> Roots
    		{
    			get 
    			{
    				return _root ?? (_root = new List<IRoot<object>>());
    			}
    		}
    
    		public bool HasChildren
    		{
    			get 
    			{
    				if (_root == null)
    				{
    					return false;
    				}
    				else
    				{
    					return _root.Count > 0;
    				}
    			}
    		}
    
    		public void Add(object element)
    		{
    			_items.Add(element);
    		}
    
    		public bool Remove(object element)
    		{
    			return _items.Remove(element);
    		}
    
    		#endregion
    
    		#region Implementation of IEnumerable
    
    		public IEnumerator<object> GetEnumerator()
    		{
    			return _items.GetEnumerator();
    		}
    
    		IEnumerator IEnumerable.GetEnumerator()
    		{
    			return GetEnumerator();
    		}
    
    		#endregion
    	}
    }
    
    namespace Experimental.Console.Tree
    {
    	using System;
    
    	internal static class Test
    	{
    		public static void Run(params string[] args)
    		{
    			// Root
    
    			Root root = new Root();
    
    			// Root\Node
    
    			Node node = new Node
    				{
    					new object(), 
    					new object()
    				}; // We could use the .Add method to add these items but the collection initializer is just more convenient (imo) and less imperative
    
    			root.Add(node);
    
    			// Root\Node\Root1
    
    			Root root1 = new Root();
    
    			node.Roots.Add(root1);
    
    			// Root\Node\Root1\Node11
    
    			Node node11 = new Node
    				{
    					new object(), 
    					new object(), 
    					new object()
    				};
    
    			root1.Add(node11);
    
    			// Root\Node\Root1\Node12
    
    			Node node12 = new Node
    				{
    					new object(), 
    					new object()
    				};
    
    			root1.Add(node12);
    
    			// Root\Node\Root1\Node12\Root121
    
    			Root root121 = new Root();
    
    			node12.Roots.Add(root121);
    
    			// Root\Node\Root1\Node12\Root121\Node1211
    
    			Node node1211 = new Node
    				{
    					new object()
    				};
    
    			root121.Add(node1211);
    
    			// Print the total amount of elements.
    
    			Console.WriteLine(root.GetTotalElements());
    
    			Console.ReadKey(true);
    		}
    	}
    }
    
    

    Eyal (http://shilony.net), Regards.

    Any fool can write code that a computer can understand. Good programmers write code that humans can understand. -- Martin Fowler.
    Thursday, May 5, 2011 4:51 PM
    Moderator
  • Your code would be much smaller if you use an ObservableCollection.
    aelassas.free.fr
    Thursday, May 5, 2011 5:10 PM
  • Your code would be much smaller if you use an ObservableCollection.

    Not required in this kind of scenario and I think that the amount of code is irrelevant.

    Bear in mind that this is an example, reducing the amount of code only makes it worst for new comers.

    However, I might use it to implement the approach I previously advised to the OP.


    Eyal (http://shilony.net), Regards.

    Any fool can write code that a computer can understand. Good programmers write code that humans can understand. -- Martin Fowler.
    Thursday, May 5, 2011 5:26 PM
    Moderator
  • To assume I am a new comer or a newbie or dont understand recursion  is strange just answer the questions and keep it moving please and thank you....just looking for the best way to do recursion in this sense...thanks for the help!!!! more and more opinions lead to better development and just learning more.  purpose of Forumn i thought was for collaborative thinking thats it right??? or am i wrong??
    Give youself a round of applause!!
    Thursday, May 12, 2011 5:30 PM
  • To assume I am a new comer or a newbie or dont understand recursion  is strange just answer the questions and keep it moving please and thank you....just looking for the best way to do recursion in this sense...thanks for the help!!!! more and more opinions lead to better development and just learning more.  purpose of Forumn i thought was for collaborative thinking thats it right??? or am i wrong??

    I wasn't assuming anything, I just stated that a full-blown example can/may help new comers, no one said anything about you.


    Eyal (http://shilony.net), Regards.

    Any fool can write code that a computer can understand. Good programmers write code that humans can understand. -- Martin Fowler.

    Friday, May 13, 2011 3:00 AM
    Moderator
  • best solution thank you so much 
    Monday, December 10, 2018 7:03 AM