Tree.cs

Go to the documentation of this file.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
using System.Text;

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

    public class Tree<T> : IEquatable<Tree<T>>, IComparable<Tree<T>>,
                           IEnumerable<T>,      IEnumerable
    {
        //--[  Private fields  ]-----------------------------------------------

        private string strhash = null; // used for caching
        private int?   memhash = null; // memoized hash
        private string memstr  = null; // memoized ToString

        internal string CacheKey
        { get { return strhash ?? (strhash = memhash.ToString()); } }

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

        public Tree(T value)
            : this(value, new List<Tree<T>>())
        { }

        public Tree(Tree<T> other, IEnumerable<Tree<T>> children)
            : this(other.Value, other.Children.Concat(children))
        { }

        public Tree(T value, IEnumerable<Tree<T>> children)
        { 
            Value       = value; 
            Depth       = 0;
            LeavesCount = 0;
            NodesCount  = 1;

            List<Tree<T>> cld = new List<Tree<T>>();
            foreach (var tree in children)
            { 
                cld.Add(tree); 
                Depth = Math.Max(Depth, tree.Depth + 1); 
                LeavesCount += tree.IsLeaf ? 1 : tree.LeavesCount;
                NodesCount  += tree.NodesCount;
            }

            Children = cld;
        }

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

        public int Depth { get; private set; }

        public int LeavesCount { get; private set; }

        public int NodesCount { get; private set; }

        public T Value { get; private set; }

        public bool IsLeaf { get { return Children.Count == 0; } }

        public IReadOnlyList<Tree<T>> Children { get; private set; }

        public DFSTreeEnumerator<T> DepthFirstEnumerator
        { get { return new DFSTreeEnumerator<T>(this); } }

        public BFSTreeEnumerator<T> BreadthFirstEnumerator
        { get { return new BFSTreeEnumerator<T>(this); } }

        //--[  Indexer  ]------------------------------------------------------

        public Tree<T> this[int ix] { get { return Children[ix]; } }

        //--[  Overriden methods  ]--------------------------------------------

        #region [  Object       ]

        public override bool Equals(object obj)
        {
            Tree<T> tree = obj as Tree<T>;
            return tree == null ? false : Equals(tree);
        }

        public override int GetHashCode()
        {
            if (memhash.HasValue) return memhash.Value;

            int count = Children.Count;
            memhash = Value.GetHashCode() * (13 * count + 7);

            int px = 7;
            for (int ix = 0; ix < count; ++ix)
            {
                memhash += (px * (ix + 1)) * Children[ix].GetHashCode();
                px      *= 7;
            }

            return memhash.Value;
        }

        public string ToString(int maxdepth)
        {
            if ((maxdepth >= Depth) && (memstr != null)) return memstr;
            if (IsLeaf)        return Value.ToString();
            if (maxdepth == 0) return Value.ToString() + "{" + LeavesCount.ToString() + "}";

            StringBuilder sb = new StringBuilder();
            sb.Append('[').Append(Value.ToString());

            for (int ix = 0; ix < Children.Count; ++ix)
            {
                var c = (maxdepth < 0) || (maxdepth >= Children[ix].Depth);
                sb.Append(' ').Append(Children[ix].ToString(c ? -1 : maxdepth - 1));
            }

            sb.Append(']');

            if (maxdepth >= Depth) return (memstr = sb.ToString());
            return sb.ToString();
        }

        public override string ToString()
        { return memstr ?? (memstr = this.ToString(-1)); }

        #endregion

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

        #region [  IEquatable   ]

        public bool Equals(Tree<T> other)
        {
            if (other == null)                             return false;
            if (object.ReferenceEquals(this, other))       return true; // performance hack
            if (this.GetHashCode() != other.GetHashCode()) return false;

            bool temp =    Value.Equals(other.Value)
                        && Children.Count == other.Children.Count;

            for (int ix = 0; temp && (ix < Children.Count); ++ix)
                temp = Children[ix].Equals(other.Children[ix]);

            return temp;
        }

        #endregion

        #region [  IComparable  ]

        public int CompareTo(Tree<T> other)
        {
            int temp = Comparer<T>.Default.Compare(Value, other.Value);

            if (temp == 0) temp = Children.Count - other.Children.Count;

            for (int ix = 0; (temp == 0) && (ix < Children.Count); ++ix)
                temp = Children[ix].CompareTo(other.Children[ix]);

            return temp;
        }

        #endregion

        #region [  IEnumerable  ]

        public IEnumerator<T> GetEnumerator()   { return DepthFirstEnumerator; }

        IEnumerator IEnumerable.GetEnumerator() { return DepthFirstEnumerator; }

        #endregion

    }
}