TreeEnumerators.cs

Go to the documentation of this file.

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

namespace Mercury.Nucleus.Trees
{
//=============================================================================
//  DFSTreeEnumerator
//=============================================================================

    public class DFSTreeEnumerator<T> : IEnumerator<T>, IEnumerator
    {
        //--[  Private fields  ]-----------------------------------------------

        private bool           end;   // past the end
        private Tree<T>        root;  // root node
        private Stack<Tree<T>> nodes; // stack of nodes

        //--[  Constructors  ]-------------------------------------------------

        public DFSTreeEnumerator(Tree<T> root)
        {
            this.end   = false;
            this.root  = root;
            this.nodes = new Stack<Tree<T>>();
        }

        //--[  Properties  ]---------------------------------------------------

        public T Current { get { return nodes.Peek().Value; } }

        object IEnumerator.Current { get { return nodes.Peek().Value; } }

        //--[  Interface implementation  ]-------------------------------------

        #region [  IEnumerator  ]

        public void Dispose()
        {
            nodes.Clear();
            return;
        }

        public bool MoveNext()
        {
            if (end) throw new InvalidOperationException();

            if (nodes.Count == 0)
            { nodes.Push(root); return true; }

            var tree = nodes.Pop();

            for (int ix = tree.Children.Count - 1; ix >= 0; --ix)
                nodes.Push(tree[ix]);

            return !(end = (nodes.Count == 0));
        }

        public void Reset()
        {
            nodes.Clear();
            end = false;
        }

        #endregion

    }

//=============================================================================
//  BFSTreeEnumerator
//=============================================================================

    public class BFSTreeEnumerator<T> : IEnumerator<T>, IEnumerator
    {
        //--[  Private fields  ]-----------------------------------------------

        private bool           end;   // past the end
        private Tree<T>        root;  // root node
        private Queue<Tree<T>> queue; // queue of nodes to explore

        //--[  Constructors  ]-------------------------------------------------

        public BFSTreeEnumerator(Tree<T> root)
        {
            this.end   = false;
            this.root  = root;
            this.queue = new Queue<Tree<T>>();
        }

        //--[  Properties  ]---------------------------------------------------

        public T Current { get { return queue.Peek().Value; } }

        object IEnumerator.Current { get { return queue.Peek().Value; } }

        //--[  Interface methods  ]--------------------------------------------

        #region [  IEnumerator  ]

        public void Dispose()
        {
            queue.Clear();
            return;
        }

        public bool MoveNext()
        {
            if (end) throw new InvalidOperationException();

            if (queue.Count == 0)
            { queue.Enqueue(root); return true; }

            Tree<T> tree = queue.Dequeue();
            for (int ix = 0; ix < tree.Children.Count; ++ix)
                queue.Enqueue(tree[ix]);

            return !(end = (queue.Count == 0));
        }

        public void Reset()
        {
            end = false;
            queue.Clear();
        }

        #endregion

    }
}