Recursive Enumerator

using System;
using System.Collections.Generic;

namespace SecretNest.RecursiveEnumerator
{
    /// <summary>
    /// Get the enumerator for querying the parents of specified item.
    /// </summary>
    /// <typeparam name="T">Item type</typeparam>
    /// <param name="current">Item for querying parents</param>
    /// <returns>Enumerator of parents querying</returns>
    public delegate IEnumerator<T> GetParentsEnumerator<T>(T current);

    /// <summary>
    /// Enumerator for querying parents
    /// </summary>
    /// <typeparam name="T">Item type</typeparam>
    public class Enumerator<T> : IEnumerator<T>
    {
        T current, initial;

        Queue<T> notQueried = new Queue<T>();

        HashSet<T> queried = new HashSet<T>(); //for avoiding duplicated query
        Queue<T> rollbackHistory = new Queue<T>(); //for soft reset
        Queue<T> history = new Queue<T>(); //for soft reset
        IEnumerator<T> activeQuery;

        /// <summary>
        /// Callback for getting the enumerator, which is used for querying the parents of specified item.
        /// </summary>
        public GetParentsEnumerator<T> GetParentsEnumeratorCallback { get; set; }

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="initial">Initial item</param>
        public Enumerator(T initial)
        {
            notQueried.Enqueue(initial);
            this.initial = initial;
        }

        /// <summary>
        /// Constructor
        /// </summary>
        /// <param name="initial">Initial item</param>
        /// <param name="callback">Callback for getting the enumerator, which is used for querying the parents of specified item.</param>
        public Enumerator(T initial, GetParentsEnumerator<T> callback)
        {
            notQueried.Enqueue(initial);
            this.initial = initial;
            GetParentsEnumeratorCallback = callback;
        }

        /// <summary>
        /// Gets the current element in the collection.
        /// </summary>
        public T Current
        {
            get { return current; }
        }

        bool disposed;
        /// <summary>
        /// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources.
        /// </summary>
        public void Dispose()
        {
            Dispose(true);
            GC.SuppressFinalize(this);
        }

        private void Dispose(bool disposing)
        {
            if (!disposed)
            {
                if (disposing)
                {
                    current = default(T);
                    notQueried = null;
                    queried = null;
                    history = null;
                }
                disposed = true;
            }
        }

        /// <summary>
        /// Gets the current element in the collection.
        /// </summary>
        object System.Collections.IEnumerator.Current
        {
            get { return current; }
        }

        /// <summary>
        /// Skip same items
        /// </summary>
        public bool SkipSameItems { get; set; }

        /// <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>
        public bool MoveNext()
        {
            if (disposed) throw new ObjectDisposedException(null);
            if (rollbackHistory.Count > 0)
            {
                current = rollbackHistory.Dequeue();
                history.Enqueue(current);
                return true;
            }
            if (activeQuery != null)
            {
            here:
                if (activeQuery.MoveNext())
                {
                    if (SkipSameItems && history.Contains(activeQuery.Current)) { goto here; }
                    current = activeQuery.Current;
                    history.Enqueue(current);
                    notQueried.Enqueue(current);
                    return true;
                }
                else
                {
                    activeQuery = null;
                }
            }
            if (GetParentsEnumeratorCallback != null)
            {
                while (notQueried.Count != 0)
                {
                    T item = notQueried.Dequeue();
                    if (!queried.Contains(item))
                    {
                        IEnumerator<T> enumerator = GetParentsEnumeratorCallback(item);
                        queried.Add(item);
                        here:
                        if (enumerator != null)
                        {
                            if (enumerator.MoveNext())
                            {
                                activeQuery = enumerator;
                                if (SkipSameItems && history.Contains(enumerator.Current)) { goto here; }
                                current = enumerator.Current;
                                history.Enqueue(current);
                                notQueried.Enqueue(current);
                                return true;
                            }
                            else
                            {
                                enumerator = null;
                            }
                        }
                    }
                }
            }
            return false;
        }

        /// <summary>
        /// Sets the enumerator to its initial position, which is before the first element in the collection. Keep all histories for caching.
        /// </summary>
        public void Reset()
        {
            if (disposed) throw new ObjectDisposedException(null);
            while (history.Count > 0)
            {
                rollbackHistory.Enqueue(history.Dequeue());
            }
            current = default(T);
        }

        /// <summary>
        /// Sets the enumerator to its initial position, which is before the first element in the collection. Reset all data, and close active sub-query.
        /// </summary>
        public void HardReset()
        {
            if (disposed) throw new ObjectDisposedException(null);
            queried.Clear();
            notQueried.Clear();
            notQueried.Enqueue(initial);
            history.Clear();
            activeQuery = null;
            current = default(T);
        }
    }
}

 

Download code and demo projects

Leave a Reply

Your email address will not be published. Required fields are marked *