using System;
using System.Collections.Generic;

namespace Chernobyl.Collections.Generic.Hierarchy
{
    /// <summary>
    /// An enumerator that enumerates through a tree in depth first order 
    /// (http://en.wikipedia.org/wiki/Depth-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 DepthFirstEnumerator<T> : TreeEnumerator<T>
    {
        /// <summary>
        /// Initializes a new instance of the
        /// <see cref="DepthFirstEnumerator{T}"/> 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 DepthFirstEnumerator(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.Last == null)
                    {
                        finished = true;
                        result = false;
                    }
                    else if (EnumeratorLevels.Last.Value.MoveNext() == true)
                    {
                        // drop down into the next 'level' of the tree by 
                        // appending the children enumerator
                        Current = EnumeratorLevels.Last.Value.Current;
                        EnumeratorLevels.AddLast(GetChildEnumerator(Current));
                        finished = true;
                    }
                    else // We are finished with the last enumerator we added
                        EnumeratorLevels.RemoveLast();
                }
            }

            return result;
        }
    }
}