Generic Tree Control

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.Linq;
using System.Linq.Expressions;
using System.Runtime.Serialization;


namespace Precio.Collections
{
    /// <summary>
    /// 
    /// </summary>
    /// <typeparam name="TNodeValue"></typeparam>
    /// <author>Martin Dahlstedt 2006 (m_dahlstedt@hotmail.com)</author>
    [Serializable()]
    public class Tree<TNodeValue> : IEnumerable<TreeNode<TNodeValue>>, ICollection<TreeNode<TNodeValue>>, IList<TreeNode<TNodeValue>>, IEnumerable, ICollection, IList, ISerializable
        where TNodeValue : TreeNodeValue
    {
        private TreeNode<TNodeValue> _rootNode = new TreeNode<TNodeValue>();

        protected Boolean _treeIndexed = false;

        private Int32 _indexes = 0;

        private Int32 _levels = 0;

        public event EventHandler<NodeIndexedEventArgs<TNodeValue>> NodeIndexedEvent;

        public event EventHandler<IndexCalculationFinishedEventArgs<TNodeValue>> IndexCalculationFinishedEvent;


        /// <summary>
        /// Gets the root node.
        /// </summary>
        public TreeNode<TNodeValue> RootNode
        {
            get
            {
                return _rootNode;
            }
        }


        /// <summary>
        /// Gets the count of nodes in the tree collection.
        /// </summary>
        public Int32 Count
        {
            get
            {
                return _indexes;
            }
        }


        public Int32 Levels
        {
            get
            {
                return _levels;
            }
        }


        /// <summary>
        /// Constructor for Tree.
        /// </summary>
        /// <param name="root"></param>
        public Tree(TNodeValue root)
        {
            _rootNode.NodeValue = root;
        }


        /// <summary>
        /// 
        /// </summary>
        public void BuildIndex()
        {
            BuildIndexInternal();

            _treeIndexed = true;

            IndexCalculationFinishedEventArgs<TNodeValue> args = new IndexCalculationFinishedEventArgs<TNodeValue>(_indexes);

            FireIndexCalculationFinishedEvent(args);
        }


        protected virtual void BuildIndexInternal()
        {

        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="predicate"></param>
        /// <returns></returns>
        public Boolean TrueForAll(Predicate<TNodeValue> predicate)
        {
            foreach (Pair<Int32, TNodeValue> nodePair in this)
            {
                if (!predicate(nodePair.Second))
                {
                    return false;
                }
            }

            return true;
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="predicate"></param>
        public void Filter(Predicate<TNodeValue> predicate)
        {
            MakeFilterIndex(predicate);
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="predicate"></param>
        /// <returns></returns>
        private Int32[] MakeFilterIndex(Predicate<TNodeValue> predicate)
        {
            List<Int32> ret = new List<Int32>();
            Int32 i = 0;

            foreach (Pair<Int32, TNodeValue> nodePair in this)
            {
                if (predicate(nodePair.Second))
                {
                    ret.Add(i);
                }

                i++;
            }


            return ret.ToArray();
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="action"></param>
        /// <param name="ignoreRoot"></param>
        public void ActionAll(Action<TNodeValue> action, Boolean ignoreRoot)
        {
            foreach (TreeNode<TNodeValue> nodePair in this)
            {
                if (ignoreRoot & nodePair.Level < 1)
                    continue;

                action(nodePair.NodeValue);
            }
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="predicate"></param>
        /// <param name="action"></param>
        /// <param name="ignoreRoot"></param>
        public void ActionIf(Predicate<TNodeValue> predicate, Action<TNodeValue> action, Boolean ignoreRoot)
        {
            foreach (TreeNode<TNodeValue> nodePair in this)
            {
                if (ignoreRoot & nodePair.Level < 1)
                    continue;

                if (predicate(nodePair.NodeValue))
                {
                    action(nodePair.NodeValue);
                }
            }
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="predicate"></param>
        /// <param name="action"></param>
        /// <param name="ignoreRoot"></param>
        public void ActionIfNot(Predicate<TNodeValue> predicate, Action<TNodeValue> action, Boolean ignoreRoot)
        {
            foreach (TreeNode<TNodeValue> nodePair in this)
            {
                if (ignoreRoot & nodePair.Level < 1)
                    continue;

                if (!predicate(nodePair.NodeValue))
                {
                    action(nodePair.NodeValue);
                }
            }
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="tree"></param>
        /// <returns></returns>
        public Tree<TNodeValue> Merge(Tree<TNodeValue> tree)
        {
            Tree<TNodeValue> mergedTree = new Tree<TNodeValue>(this.RootNode.NodeValue);

            foreach (TreeNode<TNodeValue> nodeInformation in this)
            {
                // skip the most top node
                if (nodeInformation.Level < 1)
                    continue;

                mergedTree.AddLast(nodeInformation.Parent.RelativePath, nodeInformation.NodeValue);
            }

            foreach (TreeNode<TNodeValue> nodePair in tree)
            {
                // skip the most top node
                if (nodePair.Level < 1)
                    continue;

                mergedTree.AddLast(nodePair.Parent.RelativePath, nodePair.NodeValue);
            }

            return mergedTree;
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="tree"></param>
        /// <param name="Equals"></param>
        /// <returns></returns>
        public CompareTree<TNodeValue> CompareTo(Tree<TNodeValue> tree, Predicate<CompareTreeArgs<TNodeValue>> comparePredicate)
        {
            CompareTree<TNodeValue> compareTree = new CompareTree<TNodeValue>(this.RootNode.NodeValue);

            InternalCompareTo(this, tree, ref compareTree, comparePredicate, true);

            InternalCompareTo(tree, this, ref compareTree, comparePredicate, false);

            return compareTree;
        }


        public TreeNode<TNodeValue> this[String relativePath]
        {
            get
            {
                foreach (TreeNode<TNodeValue> nodePair in this)
                {
                    if (String.Compare(nodePair.RelativePath, relativePath, StringComparison.OrdinalIgnoreCase) == 0)
                        return nodePair;
                }

                throw new NullReferenceException(String.Format(@"Could not find the node information on the relative path '{0}'.", relativePath));
            }
        }


        private void InternalCompareTo(Tree<TNodeValue> tree1, Tree<TNodeValue> tree2, ref CompareTree<TNodeValue> compareTree, Predicate<CompareTreeArgs<TNodeValue>> comparePredicate, Boolean isSource)
        {
            foreach (TreeNode<TNodeValue> nodePair1 in tree1)
            {
                // skip the most top node
                if (nodePair1.Level < 1)
                    continue;


                CompareNodeValue<TNodeValue> compareNode = null;

                foreach (TreeNode<TNodeValue> nodePair2 in tree2)
                {
                    // skip the most top node
                    if (nodePair2.Level < 1)
                        continue;


                    if (!nodePair1.RelativePath.Equals(nodePair2.RelativePath, StringComparison.OrdinalIgnoreCase))
                        continue;


                    if (!nodePair1.Name.Equals(nodePair2.Name, StringComparison.OrdinalIgnoreCase))
                        continue;

                    CompareTreeArgs<TNodeValue> args = new CompareTreeArgs<TNodeValue>(nodePair1.NodeValue, nodePair2.NodeValue);

                    CompareNodeValue<TNodeValue>.CompareStatus compareStatus = comparePredicate(args) ? CompareNodeValue<TNodeValue>.CompareStatus.Equal : CompareNodeValue<TNodeValue>.CompareStatus.Different;

                    compareNode = new CompareNodeValue<TNodeValue>(nodePair1.NodeValue, nodePair1.NodeValue.Path, compareStatus);

                    break;
                }

                //Check if we need to add the node since it was missing in the second folder.
                if (compareNode == null)
                {
                    CompareNodeValue<TNodeValue>.CompareStatus compareStatus = isSource ? CompareNodeValue<TNodeValue>.CompareStatus.MissingInDestination : CompareNodeValue<TNodeValue>.CompareStatus.MissingInSource;

                    compareNode = new CompareNodeValue<TNodeValue>(nodePair1.NodeValue, nodePair1.NodeValue.Path, compareStatus);
                }

                compareTree.AddLast(nodePair1.Parent.RelativePath, compareNode);
            }
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="parentRelativePath"></param>
        /// <param name="nodeValue"></param>
        public TreeNode<TNodeValue> AddLast(String parentRelativePath, TNodeValue nodeValue)
        {
            TreeNode<TNodeValue> parentNode = GetTreeNodeByRelativePath(_rootNode, parentRelativePath);

            if (parentNode == null)
                throw new NullReferenceException(String.Format(@"Could not find the parent root by the relative path {0}.", parentRelativePath));

            return this.AddLast(parentNode, nodeValue);
        }


        private TreeNode<TNodeValue> GetTreeNodeByRelativePath(TreeNode<TNodeValue> parentNode, String relativePath)
        {
            if (parentNode.RelativePath == relativePath)
                return parentNode;


            TreeNode<TNodeValue> foundTreeNode = null;

            foreach (TreeNode<TNodeValue> childNode in parentNode.ChildNodes)
            {
                foundTreeNode = GetTreeNodeByRelativePath(childNode, relativePath);

                if (foundTreeNode != null)
                    break;
            }

            return foundTreeNode;
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="parentNode">Parent node in which the new node is to be created on.</param>
        /// <param name="nodeValue">The value of the new node.</param>
        public TreeNode<TNodeValue> AddLast(TreeNode<TNodeValue> parentNode, TNodeValue nodeValue)
        {
            String relativePath = String.Format(@"{0}\{1}", parentNode.RelativePath, nodeValue.Name);

            relativePath = relativePath.TrimStart('\\');

            TreeNode<TNodeValue> newNode = new TreeNode<TNodeValue>(nodeValue, parentNode, nodeValue.Name, relativePath);


            //Check to see there is already a space on that relative path.
            foreach (TreeNode<TNodeValue> childNode in parentNode.ChildNodes)
            {
                if (childNode.RelativePath == relativePath)
                    return null;
            }

            parentNode.ChildNodes.AddLast(newNode);

            _indexes++;


            Int32 levels = String.IsNullOrEmpty(newNode.RelativePath) ? 0 : newNode.RelativePath.Split('\\').Length;

            _levels = levels > _levels ? levels : _levels;

            NodeIndexedEventArgs<TNodeValue> args = new NodeIndexedEventArgs<TNodeValue>(newNode);

            FireNewNodeAddedEvent(args);

            return newNode;
        }


        public Boolean Remove(TreeNode<TNodeValue> treeNode)
        {
            TreeNode<TNodeValue> nodeToRemove = GetTreeNodeByRelativePath(_rootNode, treeNode.RelativePath);

            Boolean result = nodeToRemove.Parent.ChildNodes.Remove(nodeToRemove);

            if (result)
            {
                _indexes--;
            }

            return result;
        }


        private IEnumerator<TreeNode<TNodeValue>> GetEnumerator(TreeNode<TNodeValue> treeNode)
        {
            //Return the first (root) node first.
            yield return treeNode;

            LinkedListNode<TreeNode<TNodeValue>> linkedList = treeNode.ChildNodes.First;

            while (linkedList != null)
            {
                IEnumerator<TreeNode<TNodeValue>> enumerator = GetEnumerator(linkedList.Value);

                while (enumerator.MoveNext())
                {
                    yield return enumerator.Current;
                }

                linkedList = linkedList.Next;
            }
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="e"></param>
        private void FireNewNodeAddedEvent(NodeIndexedEventArgs<TNodeValue> e)
        {
            if (this.NodeIndexedEvent != null)
            {
                this.NodeIndexedEvent(this, e);
            }
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="e"></param>
        private void FireIndexCalculationFinishedEvent(IndexCalculationFinishedEventArgs<TNodeValue> e)
        {
            if (this.IndexCalculationFinishedEvent != null)
            {
                this.IndexCalculationFinishedEvent(this, e);
            }
        }

        #region IList<Pair<TreeNodePathInfo,T>> Members

        public int IndexOf(TreeNode<TNodeValue> treeNode)
        {
            Int32 currentIndex = 0;

            foreach (TreeNode<TNodeValue> temp in this)
            {
                if (temp.NodeValue == treeNode.NodeValue)
                    return currentIndex;

                currentIndex++;
            }

            return -1;
        }


        public void Insert(int index, TreeNode<TNodeValue> treeNode)
        {
            throw new NotImplementedException();
        }


        public void RemoveAt(int index)
        {
            TreeNode<TNodeValue> treeNode = this[index];

            this.Remove(treeNode);
        }


        public TreeNode<TNodeValue> this[int index]
        {
            get
            {
                Int32 currentIndex = 0;

                foreach (TreeNode<TNodeValue> treeNode in this)
                {
                    if (currentIndex == index)
                        return treeNode;

                    currentIndex++;
                }

                throw new NullReferenceException(String.Format(@"Could not find the node information on index {0}.", index));
            }

            set
            {
                TreeNode<TNodeValue> nodePair = this[index];

                nodePair = value;
            }
        }

        #endregion

        #region IList Members

        public int Add(object value)
        {
            this.Add((TreeNode<TNodeValue>)value);

            return 1;
        }

        public Boolean Contains(object value)
        {
            return this.Contains(value as TreeNode<TNodeValue>);
        }

        public Int32 IndexOf(object value)
        {
            throw new NotImplementedException();
        }

        public void Insert(int index, object value)
        {
            throw new NotImplementedException();
        }

        public Boolean IsFixedSize
        {
            get { throw new NotImplementedException(); }
        }

        public void Remove(object value)
        {
            throw new NotImplementedException();
        }

        object IList.this[int index]
        {
            get
            {
                throw new NotImplementedException();
            }

            set
            {
                throw new NotImplementedException();
            }
        }

        #endregion

        #region IEnumerable<TreeNode<TNodeValue>> Members

        IEnumerator<TreeNode<TNodeValue>> IEnumerable<TreeNode<TNodeValue>>.GetEnumerator()
        {
            return GetEnumerator(_rootNode);
        }

        #endregion

        #region IEnumerable Members

        public IEnumerator GetEnumerator()
        {
            return GetEnumerator(_rootNode);
        }

        #endregion

        #region ICollection<Pair<TreeNodePathInfo,T>> Members

        public void Add(TreeNode<TNodeValue> treeNode)
        {
            TreeNode<TNodeValue> parentTreeNode = GetTreeNodeByRelativePath(_rootNode, treeNode.Parent.RelativePath);

            if (parentTreeNode == null)
                throw new NullReferenceException(String.Format(@"Could not find the parent root by the relative path {0}.", treeNode.RelativePath));

            this.AddLast(parentTreeNode, treeNode.NodeValue);
        }


        public void Clear()
        {
            _rootNode = new TreeNode<TNodeValue>();
        }


        public Boolean Contains(TreeNode<TNodeValue> treeNode)
        {
            foreach (TreeNode<TNodeValue> temp in this)
            {
                if (temp.NodeValue == treeNode.NodeValue)
                    return true;
            }

            return false;
        }


        public void CopyTo(TreeNode<TNodeValue>[] array, int arrayIndex)
        {
            throw new NotImplementedException();
        }


        public Boolean IsReadOnly
        {
            get
            {
                return false;
            }
        }

        #endregion

        #region ICollection Members

        public void CopyTo(Array array, int index)
        {
            throw new NotImplementedException();
        }

        public bool IsSynchronized
        {
            get
            {
                return false;
            }
        }

        public object SyncRoot
        {
            get { throw new NotImplementedException(); }
        }

        #endregion

        #region ISerializable Members

        public void GetObjectData(SerializationInfo info, StreamingContext context)
        {
            throw new NotImplementedException();
        }

        #endregion
    }
}