using System;
using System.Collections.Generic;

namespace Chernobyl.Collections.Generic.Hierarchy
{
    /// <summary>
    /// An enumerator that enumerates through a tree in breadth first order 
    /// (http://en.wikipedia.org/wiki/Breadth_first_search). This enumerator 
    /// does not operate on a specific "tree type", instead, it operates on 
    /// types that are structured like tree nodes, i.e. the class holds instances 
    /// of it's own type; for example:
    /// <code>
    /// class Foobar
    /// {
    ///     public List{Foobar} Children { get; }
    /// }
    /// </code>
    /// </summary>
    /// <typeparam name="T">The type that contains a list of instances of it's 
    /// own type (a class that acts as a node in a tree).</typeparam>
    public class BreadthFirstEnumerator<T> : TreeEnumerator<T>
    {
        /// <summary>
        /// Initializes a new instance of the <see cref="BreadthFirstEnumerator&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="startingNode">The inclusive node to start from (it will 
        /// become the first value of <see cref="IEnumerator{T}.Current"/>. </param>
        /// <param name="getChildEnumerator">The method that retrieves the 
        /// <see cref="IEnumerator{T}"/> from an instance of type 
        /// <typeparamref name="T"/>. Typically, it will look something like 
        /// this (using a lambda expression):
        /// <code>
        /// foobar => foobar.Children.GetEnumerator();
        /// </code>
        /// </param>
        public BreadthFirstEnumerator(T startingNode, Func<T, IEnumerator<T>> getChildEnumerator) 
            : base(startingNode, getChildEnumerator)
        { }

        /// <summary>
        /// Advances the enumerator to the next element of the collection.
        /// </summary>
        /// <returns>
        /// true if the enumerator was successfully advanced to the next element; 
        /// false if the enumerator has passed the end of the collection.
        /// </returns>
        /// <exception cref="InvalidOperationException">The collection was 
        /// modified after the enumerator was created. </exception>
        public override bool MoveNext()
        {
            bool result = true;
            
            if (Started == false)
            {
                Started = true;
                Current = Start;
                EnumeratorLevels.AddLast(GetChildEnumerator(Current));
            }
            else
            {
                bool finished = false;
                while (finished == false)
                {
                    // have we gone through the entire tree?
                    if (EnumeratorLevels.Count == 0)
                    {
                        finished = true;
                        result = false;
                    }
                    else if (EnumeratorLevels.First.Value.MoveNext() == true)
                    {
                        // grab the new Current and add it's children to our queue
                        Current = EnumeratorLevels.First.Value.Current;
                        EnumeratorLevels.AddLast(GetChildEnumerator(Current));
                        finished = true;
                    }
                    else
                    {
                        // we are finished with this level, we can move to the next 
                        // enumerator over or we can continue to the next level down, 
                        // whichever is next
                        EnumeratorLevels.RemoveFirst();
                    }
                }
            }

            return result;
        }
    }
}