using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Reflection;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.IO;
using System.Runtime.Serialization;
using System.Xml.Serialization;
using System.Security.Permissions;

[assembly: SuppressMessage("Microsoft.Performance", "CA1804:RemoveUnusedLocals", Scope = "member", Target = "Common.NodeTree`1+EnumeratorBase`1.Count", MessageId = "o")]
[assembly: SuppressMessage("Microsoft.Performance", "CA1804:RemoveUnusedLocals", Scope = "member", Target = "Common.NodeTree`1+BaseEnumerableCollectionPair+BaseNodesEnumerableCollection.Count", MessageId = "o")]
[assembly: SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes", Scope = "member", Target = "Common.NodeTree`1.GetNodeTree(Common.INode`1<T>):Common.NodeTree`1<T>")]
[assembly: SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes", Scope = "member", Target = "Common.NodeTree`1.GetNodeTree(Common.ITree`1<T>):Common.NodeTree`1<T>")]
[assembly: SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes", Scope = "member", Target = "Common.NodeTree`1.NewTree():Common.ITree`1<T>")]
[assembly: SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes", Scope = "member", Target = "Common.NodeTree`1.NewNode():Common.INode`1<T>")]
[assembly: SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes", Scope = "member", Target = "Common.NodeTree`1.XmlAdapterTag")]
[assembly: SuppressMessage("Microsoft.Design", "CA1000:DoNotDeclareStaticMembersOnGenericTypes", Scope = "member", Target = "Common.NodeTree`1.XmlDeserialize(System.IO.Stream):Common.ITree`1<T>")]
[assembly: SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures", Scope = "member", Target = "Common.IEnumerableCollectionPair`1.Nodes")]
[assembly: SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures", Scope = "member", Target = "Common.NodeTree`1.Nodes")]
[assembly: SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures", Scope = "member", Target = "Common.NodeTree`1+AllEnumerator.Nodes")]
[assembly: SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures", Scope = "member", Target = "Common.NodeTree`1+BaseEnumerableCollectionPair.Nodes")]
[assembly: SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures", Scope = "member", Target = "Common.NodeTree`1+BaseEnumerableCollectionPair+BaseNodesEnumerableCollection.GetEnumerator():System.Collections.Generic.IEnumerator`1<Common.INode`1<T>>")]
[assembly: SuppressMessage("Microsoft.Design", "CA1034:NestedTypesShouldNotBeVisible", Scope = "type", Target = "Common.NodeTree`1+AllEnumerator")]
[assembly: SuppressMessage("Microsoft.Design", "CA1034:NestedTypesShouldNotBeVisible", Scope = "type", Target = "Common.NodeTree`1+BaseEnumerableCollectionPair")]
[assembly: SuppressMessage("Microsoft.Design", "CA1034:NestedTypesShouldNotBeVisible", Scope = "type", Target = "Common.NodeTree`1+RootObject")]
[assembly: SuppressMessage("Microsoft.Design", "CA1034:NestedTypesShouldNotBeVisible", Scope = "type", Target = "Common.NodeTree`1+NodeXmlSerializationAdapter")]
[assembly: SuppressMessage("Microsoft.Design", "CA1034:NestedTypesShouldNotBeVisible", Scope = "type", Target = "Common.NodeTree`1+NodeXmlSerializationAdapter+IXmlCollection")]
[assembly: SuppressMessage("Microsoft.Design", "CA1034:NestedTypesShouldNotBeVisible", Scope = "type", Target = "Common.NodeTree`1+TreeXmlSerializationAdapter")]
[assembly: SuppressMessage("Microsoft.Design", "CA1063:ImplementIDisposableCorrectly", Scope = "member", Target = "Common.NodeTree`1.Dispose():System.Void")]
[assembly: SuppressMessage("Microsoft.Design", "CA1063:ImplementIDisposableCorrectly", Scope = "member", Target = "Common.NodeTree`1.Finalize():System.Void")]
[assembly: SuppressMessage("Microsoft.Design", "CA1063:ImplementIDisposableCorrectly", Scope = "member", Target = "Common.NodeTree`1+BaseEnumerableCollectionPair+BaseNodesEnumerableCollection.Dispose():System.Void")]
[assembly: SuppressMessage("Microsoft.Design", "CA1063:ImplementIDisposableCorrectly", Scope = "member", Target = "Common.NodeTree`1+BaseEnumerableCollectionPair+BaseNodesEnumerableCollection.Finalize():System.Void")]
[assembly: SuppressMessage("Microsoft.Usage", "CA2211:NonConstantFieldsShouldNotBeVisible", Scope = "member", Target = "Common.NodeTree`1.XmlAdapterTag")]
[assembly: SuppressMessage("Microsoft.Usage", "CA2227:CollectionPropertiesShouldBeReadOnly", Scope = "member", Target = "Common.NodeTree`1+NodeXmlSerializationAdapter.Children")]

namespace Common
{
	//-----------------------------------------------------------------------------
	// IDeepCopy

	public interface IDeepCopy
	{
		object CreateDeepCopy();
	}

	//-----------------------------------------------------------------------------
	// IEnumerableCollection

	public interface IEnumerableCollection<T> : IEnumerable<T>, ICollection
	{
		bool Contains(T item);
	}

	//-----------------------------------------------------------------------------
	// IEnumerableCollectionPair

	public interface IEnumerableCollectionPair<T>
	{
		IEnumerableCollection<INode<T>> Nodes { get; }
		IEnumerableCollection<T> Values { get; }
		INode<T> Find(T item);
		INode<T> Find(Predicate<T> predicate);
	}

	//-----------------------------------------------------------------------------
	// EventArgs

	public class NodeTreeDataEventArgs<T> : EventArgs
	{
		private T _Data = default(T);

		public T Data { get { return _Data; } }

		public NodeTreeDataEventArgs(T data)
		{
			_Data = data;
		}
	}

	public class NodeTreeNodeEventArgs<T> : EventArgs
	{
		private INode<T> _Node = null;

		public INode<T> Node { get { return _Node; } }

		public NodeTreeNodeEventArgs(INode<T> node)
		{
			_Node = node;
		}
	}

	public enum NodeTreeInsertOperation
	{
		Previous,
		Next,
		Child,
		Tree
	}

	public class NodeTreeInsertEventArgs<T> : EventArgs
	{
		private NodeTreeInsertOperation _Operation;
		public NodeTreeInsertOperation Operation { get { return _Operation; } }

		private INode<T> _Node = null;
		public INode<T> Node { get { return _Node; } }

		public NodeTreeInsertEventArgs(NodeTreeInsertOperation operation, INode<T> node)
		{
			_Operation = operation;
			_Node = node;
		}
	}

	//-----------------------------------------------------------------------------
	// INode<T>

	/// <summary>
	/// Uwe Keim start.
	/// </summary>
	public delegate string ToStringRecursiveAction<in T>(T obj);
	/// <summary>
	/// Uwe Keim end.
	/// </summary>

	public interface INode<T> : IEnumerableCollectionPair<T>, IDisposable//, ICollection<T>
	{
		T Data { get; set; }

		string ToStringRecursive();
		/// <summary>
		/// Uwe Keim start.
		/// </summary>
		string ToStringRecursive(ToStringRecursiveAction<INode<T>> action);
		/// <summary>
		/// Uwe Keim end.
		/// </summary>

		int Depth { get; }
		int BranchIndex { get; }
		int BranchCount { get; }

		int Count { get; }
		int DirectChildCount { get; }

		INode<T> Parent { get; }
		INode<T> Previous { get; }
		INode<T> Next { get; }
		INode<T> Child { get; }

		ITree<T> Tree { get; }

		INode<T> Root { get; }
		INode<T> Top { get; }
		INode<T> First { get; }
		INode<T> Last { get; }

		INode<T> LastChild { get; }

		bool IsTree { get; }
		bool IsRoot { get; }
		bool IsTop { get; }
		bool HasParent { get; }
		bool HasPrevious { get; }
		bool HasNext { get; }
		bool HasChild { get; }
		bool IsFirst { get; }
		bool IsLast { get; }

		INode<T> this[T item] { get; }

		bool Contains(INode<T> item);
		bool Contains(T item);

		INode<T> InsertPrevious(T o);
		INode<T> InsertNext(T o);
		INode<T> InsertChild(T o);
		INode<T> Add(T o);
		INode<T> AddChild(T o);

		void InsertPrevious(ITree<T> tree);
		void InsertNext(ITree<T> tree);
		void InsertChild(ITree<T> tree);
		void Add(ITree<T> tree);
		void AddChild(ITree<T> tree);

		ITree<T> Cut(T o);
		ITree<T> Copy(T o);
		ITree<T> DeepCopy(T o);
		bool Remove(T o);

		ITree<T> Cut();
		ITree<T> Copy();
		ITree<T> DeepCopy();
		void Remove();

		bool CanMoveToParent { get; }
		bool CanMoveToPrevious { get; }
		bool CanMoveToNext { get; }
		bool CanMoveToChild { get; }
		bool CanMoveToFirst { get; }
		bool CanMoveToLast { get; }

		void MoveToParent();
		void MoveToPrevious();
		void MoveToNext();
		void MoveToChild();
		void MoveToFirst();
		void MoveToLast();

		IEnumerableCollectionPair<T> All { get; }
		IEnumerableCollectionPair<T> AllChildren { get; }
		IEnumerableCollectionPair<T> DirectChildren { get; }
		IEnumerableCollectionPair<T> DirectChildrenInReverse { get; }

		void SortAllChildren();
		void SortAllChildren(Comparison<T> comparison);
		void SortAllChildren(IComparer<T> comparer);

		void SortDirectChildren();
		void SortDirectChildren(Comparison<T> comparison);
		void SortDirectChildren(IComparer<T> comparer);

		event EventHandler<NodeTreeDataEventArgs<T>> Validate;
		event EventHandler<NodeTreeDataEventArgs<T>> Setting;
		event EventHandler<NodeTreeDataEventArgs<T>> SetDone;
		event EventHandler<NodeTreeInsertEventArgs<T>> Inserting;
		event EventHandler<NodeTreeInsertEventArgs<T>> Inserted;
		event EventHandler Cutting;
		event EventHandler CutDone;
		event EventHandler<NodeTreeNodeEventArgs<T>> Copying;
		event EventHandler<NodeTreeNodeEventArgs<T>> Copied;
		event EventHandler<NodeTreeNodeEventArgs<T>> DeepCopying;
		event EventHandler<NodeTreeNodeEventArgs<T>> DeepCopied;
	}

	//-----------------------------------------------------------------------------
	// ITree<T>

	public interface ITree<T> : IEnumerableCollectionPair<T>, IDisposable//, ICollection<T>
	{
		Type DataType { get; }

		IEqualityComparer<T> DataComparer { get; set; }

		void XmlSerialize(Stream stream);

		void Clear();
		int Count { get; }
		int DirectChildCount { get; }

		INode<T> Root { get; }

		INode<T> this[T o] { get; }

		string ToStringRecursive();
		/// <summary>
		/// Uwe Keim start.
		/// </summary>
		string ToStringRecursive(ToStringRecursiveAction<INode<T>> action);
		/// <summary>
		/// Uwe Keim end.
		/// </summary>

		bool Contains(T item);
		bool Contains(INode<T> item);

		INode<T> InsertChild(T o);
		INode<T> AddChild(T o);

		void InsertChild(ITree<T> tree);
		void AddChild(ITree<T> tree);

		ITree<T> Cut(T o);
		ITree<T> Copy(T o);
		ITree<T> DeepCopy(T o);
		bool Remove(T o);

		ITree<T> Copy();
		ITree<T> DeepCopy();

		IEnumerableCollectionPair<T> All { get; }
		IEnumerableCollectionPair<T> AllChildren { get; }
		IEnumerableCollectionPair<T> DirectChildren { get; }
		IEnumerableCollectionPair<T> DirectChildrenInReverse { get; }

		void SortAllChildren();
		void SortAllChildren(Comparison<T> comparison);
		void SortAllChildren(IComparer<T> comparer);

		event EventHandler<NodeTreeDataEventArgs<T>> Validate;
		event EventHandler Clearing;
		event EventHandler Cleared;
		event EventHandler<NodeTreeDataEventArgs<T>> Setting;
		event EventHandler<NodeTreeDataEventArgs<T>> SetDone;
		event EventHandler<NodeTreeInsertEventArgs<T>> Inserting;
		event EventHandler<NodeTreeInsertEventArgs<T>> Inserted;
		event EventHandler Cutting;
		event EventHandler CutDone;
		event EventHandler<NodeTreeNodeEventArgs<T>> Copying;
		event EventHandler<NodeTreeNodeEventArgs<T>> Copied;
		event EventHandler<NodeTreeNodeEventArgs<T>> DeepCopying;
		event EventHandler<NodeTreeNodeEventArgs<T>> DeepCopied;
	}

	//-----------------------------------------------------------------------------
	// NodeTree

	[Serializable]
	public class NodeTree<T> : INode<T>, ITree<T>, ISerializable
	{
		private T _Data = default(T);

		private NodeTree<T> _Parent = null;
		private NodeTree<T> _Previous = null;
		private NodeTree<T> _Next = null;
		private NodeTree<T> _Child = null;

		protected NodeTree() { }

		~NodeTree()
		{
			Dispose(false);
		}

		public void Dispose()
		{
			Dispose(true);

			GC.SuppressFinalize(this);
		}

		protected virtual void Dispose(bool disposing)
		{
			if (disposing)
			{
				if (_EventHandlerList != null) _EventHandlerList.Dispose();
			}
		}

		//-----------------------------------------------------------------------------
		// Instantiation

		public static ITree<T> NewTree()
		{
			return new RootObject();
		}

		public static ITree<T> NewTree(IEqualityComparer<T> dataComparer)
		{
			return new RootObject(dataComparer);
		}

		protected static INode<T> NewNode()
		{
			return new NodeTree<T>();
		}

		protected virtual NodeTree<T> CreateTree()
		{
			return new RootObject();
		}

		protected virtual NodeTree<T> CreateNode()
		{
			return new NodeTree<T>();
		}

		//-----------------------------------------------------------------------------
		// ToString

		/// <summary>Obtains the <see cref="String"/> representation of this instance.</summary>
		/// <returns>The <see cref="String"/> representation of this instance.</returns>
		/// <remarks>
		/// <p>
		/// This method returns a <see cref="String"/> that represents this instance.
		/// </p>
		/// </remarks>
		public override string ToString()
		{
			T data = Data;
			if (data == null) return String.Empty;
			return data.ToString();
		}

		/// <summary>
		/// Uwe Keim start.
		/// </summary>
		public virtual string ToStringRecursive(
			ToStringRecursiveAction<INode<T>> action)
		{
			var s = string.Empty;

			foreach (NodeTree<T> node in All.Nodes)
			{
				s += action(node);
			}

			return s;
		}

		public virtual string ToStringRecursive()
		{
			return ToStringRecursive(
				node => new string('\t', node.Depth) +
					node +
						Environment.NewLine);
		}
		/*
		public virtual string ToStringRecursive()
		{
			string s = String.Empty;

			foreach (NodeTree<T> node in All.Nodes)
				s += new String('\t', node.Depth) + node + Environment.NewLine;

			return s;
		}*/
		/// <summary>
		/// Uwe Keim end.
		/// </summary>

		//-----------------------------------------------------------------------------
		// Counts

		public virtual int Depth
		{
			get
			{
				int i = -1;

				for (INode<T> node = this; !node.IsRoot; node = node.Parent) i++;

				return i;
			}
		}

		public virtual int BranchIndex
		{
			get
			{
				int i = -1;

				for (INode<T> node = this; node != null; node = node.Previous) i++;

				return i;
			}
		}

		public virtual int BranchCount
		{
			get
			{
				int i = 0;

				for (INode<T> node = First; node != null; node = node.Next) i++;

				return i;
			}
		}

		//-----------------------------------------------------------------------------
		// DeepCopyData

		[ReflectionPermission(SecurityAction.Demand, Unrestricted = true)]
		protected virtual T DeepCopyData(T data)
		{
			//if ( ! Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			if (data == null) { Debug.Assert(true); return default(T); }

			// IDeepCopy
			IDeepCopy deepCopy = data as IDeepCopy;
			if (deepCopy != null) return (T)deepCopy.CreateDeepCopy();

			// ICloneable
			ICloneable cloneable = data as ICloneable;
			if (cloneable != null) return (T)cloneable.Clone();

			// Copy constructor
			ConstructorInfo ctor = data.GetType().GetConstructor(
				 BindingFlags.Instance | BindingFlags.Public,
				 null, new Type[] { typeof(T) }, null);
			if (ctor != null) return (T)ctor.Invoke(new object[] { data });
			//return ( T ) Activator.CreateInstance( typeof( T ), new object[] { data } );

			// give up
			return data;
		}

		//-----------------------------------------------------------------------------
		// RootObject

		[Serializable]
		protected class RootObject : NodeTree<T>
		{
			private int _Version = 0;
			protected override int Version
			{
				get { return _Version; }
				set { _Version = value; }
			}

			private IEqualityComparer<T> _DataComparer;
			public override IEqualityComparer<T> DataComparer
			{
				get
				{
					if (_DataComparer == null) _DataComparer = EqualityComparer<T>.Default;

					return _DataComparer;
				}

				set { _DataComparer = value; }
			}

			public RootObject()
			{
			}

			public RootObject(IEqualityComparer<T> dataComparer)
			{
				_DataComparer = dataComparer;
			}

			/// <summary>Obtains the <see cref="String"/> representation of this instance.</summary>
			/// <returns>The <see cref="String"/> representation of this instance.</returns>
			/// <remarks>
			/// <p>
			/// This method returns a <see cref="String"/> that represents this instance.
			/// </p>
			/// </remarks>
			public override string ToString() { return "ROOT: " + DataType.Name; }

			// Save
			/// <summary>Populates a SerializationInfo with the data needed to serialize the target T.</summary>
			/// <param name="info">The SerializationInfo to populate with data.</param>
			/// <param name="context">The destination for this serialization.</param>
			/// <remarks>
			/// <p>This method is called during serialization.</p>
			/// <p>Do not call this method directly.</p>
			/// </remarks>
			[SecurityPermission(SecurityAction.Demand, SerializationFormatter = true)]
			public override void GetObjectData(SerializationInfo info, StreamingContext context)
			{
				base.GetObjectData(info, context);

				info.AddValue("RootObjectVersion", 1);
				//info.AddValue( "DataType", _DataType );
			}

			// Load
			/// <summary>Initializes a new instance of the class during deserialization.</summary>
			/// <param name="info">The SerializationInfo populated with data.</param>
			/// <param name="context">The source for this serialization.</param>
			/// <remarks>
			/// <p>This method is called during deserialization.</p>
			/// <p>Do not call this method directly.</p>
			/// </remarks>
			protected RootObject(SerializationInfo info, StreamingContext context)
				: base(info, context)
			{
				int iVersion = info.GetInt32("RootObjectVersion");
				if (iVersion != 1) throw new SerializationException("Unknown version");

				//_DataType = info.GetValue( "DataType", typeof( Type ) ) as Type;
			}
		}

		//-----------------------------------------------------------------------------
		// GetRootObject

		protected virtual RootObject GetRootObject
		{
			get
			{
				return (RootObject)Root;
			}
		}

		//-----------------------------------------------------------------------------
		// DataComparer

		public virtual IEqualityComparer<T> DataComparer
		{
			get
			{
				if (!Root.IsTree) throw new InvalidOperationException("This is not a Tree");

				return GetRootObject.DataComparer;
			}

			set
			{
				if (!Root.IsTree) throw new InvalidOperationException("This is not a Tree");

				GetRootObject.DataComparer = value;
			}
		}

		//-----------------------------------------------------------------------------
		// Version

		protected virtual int Version
		{
			get
			{
				INode<T> root = Root;

				if (!root.IsTree) throw new InvalidOperationException("This is not a Tree");

				return GetNodeTree(root).Version;
			}

			set
			{
				INode<T> root = Root;

				if (!root.IsTree) throw new InvalidOperationException("This is not a Tree");

				GetNodeTree(root).Version = value;
			}
		}

		protected bool HasChanged(int version) { return (Version != version); }

		protected void IncrementVersion()
		{
			INode<T> root = Root;

			if (!root.IsTree) throw new InvalidOperationException("This is not a Tree");

			GetNodeTree(root).Version++;
		}

		//-----------------------------------------------------------------------------
		// ISerializable

		// Save
		/// <summary>Populates a SerializationInfo with the data needed to serialize the target T.</summary>
		/// <param name="info">The SerializationInfo to populate with data.</param>
		/// <param name="context">The destination for this serialization.</param>
		/// <remarks>
		/// <p>This method is called during serialization.</p>
		/// <p>Do not call this method directly.</p>
		/// </remarks>
		[SecurityPermission(SecurityAction.Demand, SerializationFormatter = true)]
		public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
		{
			info.AddValue("NodeTreeVersion", 1);
			info.AddValue("Data", _Data);
			info.AddValue("Parent", _Parent);
			info.AddValue("Previous", _Previous);
			info.AddValue("Next", _Next);
			info.AddValue("Child", _Child);
		}

		// Load
		/// <summary>Initializes a new instance of the class during deserialization.</summary>
		/// <param name="info">The SerializationInfo populated with data.</param>
		/// <param name="context">The source for this serialization.</param>
		/// <remarks>
		/// <p>This method is called during deserialization.</p>
		/// <p>Do not call this method directly.</p>
		/// </remarks>
		protected NodeTree(SerializationInfo info, StreamingContext context)
		{
			int iVersion = info.GetInt32("NodeTreeVersion");
			if (iVersion != 1) throw new SerializationException("Unknown version");

			_Data = (T)info.GetValue("Data", typeof(T));
			_Parent = (NodeTree<T>)info.GetValue("Parent", typeof(NodeTree<T>));
			_Previous = (NodeTree<T>)info.GetValue("Previous", typeof(NodeTree<T>));
			_Next = (NodeTree<T>)info.GetValue("Next", typeof(NodeTree<T>));
			_Child = (NodeTree<T>)info.GetValue("Child", typeof(NodeTree<T>));
		}

		//-----------------------------------------------------------------------------
		// XmlSerialization

		public virtual void XmlSerialize(Stream stream)
		{
			XmlSerializer xmlSerializer;

			try
			{
				xmlSerializer = new XmlSerializer(typeof(TreeXmlSerializationAdapter));
			}
			catch (Exception x)
			{
				Debug.Assert(x == null); // false
				throw;
			}

			try
			{
				xmlSerializer.Serialize(stream, new TreeXmlSerializationAdapter(XmlAdapterTag, this));
			}
			catch (Exception x)
			{
				Debug.Assert(x == null); // false
				throw;
			}

		}

		public static ITree<T> XmlDeserialize(Stream stream)
		{
			XmlSerializer xmlSerializer;

			try
			{
				xmlSerializer = new XmlSerializer(typeof(TreeXmlSerializationAdapter));
			}
			catch (Exception x)
			{
				Debug.Assert(x == null); // false
				throw;
			}

			object o;

			try
			{
				o = xmlSerializer.Deserialize(stream);
			}
			catch (Exception x)
			{
				Debug.Assert(x == null); // false
				throw;
			}

			TreeXmlSerializationAdapter adapter = (TreeXmlSerializationAdapter)o;

			ITree<T> tree = adapter.Tree;

			return tree;
		}

		//-----------------------------------------------------------------------------

		protected static readonly object XmlAdapterTag = new object();

		[XmlType("Tree")]
		public class TreeXmlSerializationAdapter
		{
			private int _Version = 0;

			[XmlAttribute]
			public int Version
			{
				get { return 1; }
				set { _Version = value; }
			}

			private ITree<T> _Tree;

			[XmlIgnore]
			public ITree<T> Tree
			{
				get { return _Tree; }
			}

			private TreeXmlSerializationAdapter()
			{
			}

			public TreeXmlSerializationAdapter(object tag, ITree<T> tree)
			{
				if (!ReferenceEquals(XmlAdapterTag, tag)) throw new InvalidOperationException("Don't use this class");

				_Tree = tree;
			}

			public NodeXmlSerializationAdapter Root
			{
				get
				{
					return new NodeXmlSerializationAdapter(XmlAdapterTag, _Tree.Root);
				}

				set
				{
					_Tree = NodeTree<T>.NewTree();

					ReformTree(_Tree.Root, value);
				}
			}

			private void ReformTree(INode<T> parent, NodeXmlSerializationAdapter node)
			{
				foreach (NodeXmlSerializationAdapter child in node.Children)
				{
					INode<T> n = parent.AddChild(child.Data);

					ReformTree(n, child);
				}
			}

		}

		[XmlType("Node")]
		public class NodeXmlSerializationAdapter
		{
			private int _Version = 0;

			[XmlAttribute]
			public int Version
			{
				get { return 1; }
				set { _Version = value; }
			}

			private INode<T> _Node;

			private IXmlCollection _Children = new ChildCollection();

			[XmlIgnore]
			public INode<T> Node
			{
				get { return _Node; }
			}

			// Load
			private NodeXmlSerializationAdapter()
			{
				_Node = NodeTree<T>.NewNode();
			}

			// Save
			public NodeXmlSerializationAdapter(object tag, INode<T> node)
			{
				if (!ReferenceEquals(XmlAdapterTag, tag)) throw new InvalidOperationException("Don't use this class");

				_Node = node;

				foreach (INode<T> child in node.DirectChildren.Nodes)
					_Children.Add(new NodeXmlSerializationAdapter(XmlAdapterTag, child));
			}

			public T Data
			{
				get { return _Node.Data; }

				set
				{
					GetNodeTree(_Node)._Data = value;
				}
			}

			public IXmlCollection Children
			{
				get { return _Children; }
				set { Debug.Assert(value == null); }
			}

			public interface IXmlCollection : ICollection
			{
				NodeXmlSerializationAdapter this[int index] { get; }

				void Add(NodeXmlSerializationAdapter item);
			}

			private class ChildCollection : List<NodeXmlSerializationAdapter>, IXmlCollection { }
		}


		//-----------------------------------------------------------------------------
		// INode<T>

		public T Data
		{
			get
			{
				return _Data;
			}

			set
			{
				if (IsRoot) throw new InvalidOperationException("This is a Root");

				OnSetting(this, value);

				_Data = value;

				OnSetDone(this, value);
			}
		}

		public INode<T> Parent { get { return _Parent; } }
		public INode<T> Previous { get { return _Previous; } }
		public INode<T> Next { get { return _Next; } }
		public INode<T> Child { get { return _Child; } }

		//-----------------------------------------------------------------------------

		public ITree<T> Tree
		{
			get
			{
				return (ITree<T>)Root;
			}
		}

		public INode<T> Root
		{
			get
			{
				INode<T> node = this;

				while (node.Parent != null)
					node = node.Parent;

				return node;
			}
		}

		public INode<T> Top
		{
			get
			{
				if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");
				//if ( this.IsRoot ) throw new InvalidOperationException( "This is a Root" );
				if (this.IsRoot) return null;

				INode<T> node = this;

				while (node.Parent.Parent != null)
					node = node.Parent;

				return node;
			}
		}

		public INode<T> First
		{
			get
			{
				INode<T> node = this;

				while (node.Previous != null)
					node = node.Previous;

				return node;
			}
		}

		public INode<T> Last
		{
			get
			{
				INode<T> node = this;

				while (node.Next != null)
					node = node.Next;

				return node;
			}
		}

		public INode<T> LastChild
		{
			get
			{
				if (Child == null) return null;
				return Child.Last;
			}
		}

		//-----------------------------------------------------------------------------

		public bool HasPrevious { get { return Previous != null; } }
		public bool HasNext { get { return Next != null; } }
		public bool HasChild { get { return Child != null; } }
		public bool IsFirst { get { return Previous == null; } }
		public bool IsLast { get { return Next == null; } }

		public bool IsTree
		{
			get
			{
				if (!IsRoot) return false;
				return this is RootObject;
			}
		}

		public bool IsRoot
		{
			get
			{
				bool b = (Parent == null);

				if (b)
				{
					Debug.Assert(Previous == null);
					Debug.Assert(Next == null);
				}

				return b;
			}
		}

		public bool HasParent
		{
			get
			{
				//if ( IsRoot ) throw new InvalidOperationException( "This is a Root" );
				if (IsRoot) return false;
				return Parent.Parent != null;
			}
		}

		public bool IsTop
		{
			get
			{
				//if ( IsRoot ) throw new InvalidOperationException( "This is a Root" );
				if (IsRoot) return false;
				return Parent.Parent == null;
			}
		}

		//-----------------------------------------------------------------------------

		public virtual INode<T> this[T item]
		{
			get
			{
				if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

				IEqualityComparer<T> comparer = DataComparer;

				foreach (INode<T> n in All.Nodes)
					if (comparer.Equals(n.Data, item))
						return n;

				return null;
			}
		}

		public virtual bool Contains(INode<T> item)
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			return All.Nodes.Contains(item);
		}

		public virtual bool Contains(T item)
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			return All.Values.Contains(item);
		}

		public virtual INode<T> Find(T item)
		{
			return All.Find(item);
		}

		public virtual INode<T> Find(Predicate<T> predicate)
		{
			return All.Find(predicate);
		}

		//-----------------------------------------------------------------------------

		public INode<T> InsertPrevious(T o)
		{
			if (this.IsRoot) throw new InvalidOperationException("This is a Root");
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			NodeTree<T> newNode = CreateNode();
			newNode._Data = o;

			this.InsertPreviousCore(newNode);

			return newNode;
		}

		public INode<T> InsertNext(T o)
		{
			if (this.IsRoot) throw new InvalidOperationException("This is a Root");
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			NodeTree<T> newNode = CreateNode();
			newNode._Data = o;

			this.InsertNextCore(newNode);

			return newNode;
		}

		public INode<T> InsertChild(T o)
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			NodeTree<T> newNode = CreateNode();
			newNode._Data = o;

			this.InsertChildCore(newNode);

			return newNode;
		}

		public INode<T> Add(T o)
		{
			if (this.IsRoot) throw new InvalidOperationException("This is a Root");
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			return this.Last.InsertNext(o);
		}

		public INode<T> AddChild(T o)
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			if (Child == null)
				return InsertChild(o);
			else
				return Child.Add(o);
		}

		//-----------------------------------------------------------------------------

		public void InsertPrevious(ITree<T> tree)
		{
			if (this.IsRoot) throw new InvalidOperationException("This is a Root");
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			NodeTree<T> newTree = GetNodeTree(tree);

			if (!newTree.IsRoot) throw new ArgumentException("Tree is not a Root");
			if (!newTree.IsTree) throw new ArgumentException("Tree is not a tree");

			for (INode<T> n = newTree.Child; n != null; n = n.Next)
			{
				NodeTree<T> node = GetNodeTree(n);
				NodeTree<T> copy = node.CopyCore();
				InsertPreviousCore(copy);
			}
		}

		public void InsertNext(ITree<T> tree)
		{
			if (this.IsRoot) throw new InvalidOperationException("This is a Root");
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			NodeTree<T> newTree = GetNodeTree(tree);

			if (!newTree.IsRoot) throw new ArgumentException("Tree is not a Root");
			if (!newTree.IsTree) throw new ArgumentException("Tree is not a tree");

			for (INode<T> n = newTree.LastChild; n != null; n = n.Previous)
			{
				NodeTree<T> node = GetNodeTree(n);
				NodeTree<T> copy = node.CopyCore();
				InsertNextCore(copy);
			}
		}

		public void InsertChild(ITree<T> tree)
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			NodeTree<T> newTree = GetNodeTree(tree);

			if (!newTree.IsRoot) throw new ArgumentException("Tree is not a Root");
			if (!newTree.IsTree) throw new ArgumentException("Tree is not a tree");

			for (INode<T> n = newTree.LastChild; n != null; n = n.Previous)
			{
				NodeTree<T> node = GetNodeTree(n);
				NodeTree<T> copy = node.CopyCore();
				InsertChildCore(copy);
			}
		}

		public void Add(ITree<T> tree)
		{
			if (this.IsRoot) throw new InvalidOperationException("This is a Root");
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			this.Last.InsertNext(tree);
		}

		public void AddChild(ITree<T> tree)
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			if (this.Child == null)
				this.InsertChild(tree);
			else
				this.Child.Add(tree);
		}

		//-----------------------------------------------------------------------------

		protected virtual void InsertPreviousCore(INode<T> newINode)
		{
			if (this.IsRoot) throw new InvalidOperationException("This is a Root");
			if (!newINode.IsRoot) throw new ArgumentException("Node is not a Root");
			if (newINode.IsTree) throw new ArgumentException("Node is a tree");

			IncrementVersion();

			OnInserting(this, NodeTreeInsertOperation.Previous, newINode);

			NodeTree<T> newNode = GetNodeTree(newINode);

			newNode._Parent = this._Parent;
			newNode._Previous = this._Previous;
			newNode._Next = this;
			this._Previous = newNode;

			if (newNode.Previous != null)
			{
				NodeTree<T> Previous = GetNodeTree(newNode.Previous);
				Previous._Next = newNode;
			}
			else // this is a first node
			{
				NodeTree<T> Parent = GetNodeTree(newNode.Parent);
				Parent._Child = newNode;
			}

			OnInserted(this, NodeTreeInsertOperation.Previous, newINode);
		}

		protected virtual void InsertNextCore(INode<T> newINode)
		{
			if (this.IsRoot) throw new InvalidOperationException("This is a Root");
			if (!newINode.IsRoot) throw new ArgumentException("Node is not a Root");
			if (newINode.IsTree) throw new ArgumentException("Node is a tree");

			IncrementVersion();

			OnInserting(this, NodeTreeInsertOperation.Next, newINode);

			NodeTree<T> newNode = GetNodeTree(newINode);

			newNode._Parent = this._Parent;
			newNode._Previous = this;
			newNode._Next = this._Next;
			this._Next = newNode;

			if (newNode.Next != null)
			{
				NodeTree<T> Next = GetNodeTree(newNode.Next);
				Next._Previous = newNode;
			}

			OnInserted(this, NodeTreeInsertOperation.Next, newINode);
		}

		protected virtual void InsertChildCore(INode<T> newINode)
		{
			if (!newINode.IsRoot) throw new ArgumentException("Node is not a Root");
			if (newINode.IsTree) throw new ArgumentException("Node is a tree");

			IncrementVersion();

			OnInserting(this, NodeTreeInsertOperation.Child, newINode);

			NodeTree<T> newNode = GetNodeTree(newINode);

			newNode._Parent = this;
			newNode._Next = this._Child;
			this._Child = newNode;

			if (newNode.Next != null)
			{
				NodeTree<T> Next = GetNodeTree(newNode.Next);
				Next._Previous = newNode;
			}

			OnInserted(this, NodeTreeInsertOperation.Child, newINode);
		}

		protected virtual void AddCore(INode<T> newINode)
		{
			if (this.IsRoot) throw new InvalidOperationException("This is a Root");

			NodeTree<T> lastNode = GetNodeTree(Last);

			lastNode.InsertNextCore(newINode);
		}

		protected virtual void AddChildCore(INode<T> newINode)
		{
			if (this.Child == null)
				this.InsertChildCore(newINode);
			else
			{
				NodeTree<T> childNode = GetNodeTree(Child);

				childNode.AddCore(newINode);
			}
		}

		//-----------------------------------------------------------------------------

		public ITree<T> Cut(T o)
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			INode<T> n = this[o];
			if (n == null) return null;
			return n.Cut();
		}

		public ITree<T> Copy(T o)
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			INode<T> n = this[o];
			if (n == null) return null;
			return n.Copy();
		}

		public ITree<T> DeepCopy(T o)
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			INode<T> n = this[o];
			if (n == null) return null;
			return n.DeepCopy();
		}

		public bool Remove(T o)
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			INode<T> n = this[o];
			if (n == null) return false;

			n.Remove();
			return true;
		}

		//-----------------------------------------------------------------------------

		private NodeTree<T> BoxInTree(NodeTree<T> node)
		{
			if (!node.IsRoot) throw new ArgumentException("Node is not a Root");
			if (node.IsTree) throw new ArgumentException("Node is a tree");

			NodeTree<T> tree = CreateTree();

			tree.AddChildCore(node);

			return tree;
		}

		public ITree<T> Cut()
		{
			if (this.IsRoot) throw new InvalidOperationException("This is a Root");
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			NodeTree<T> node = CutCore();

			return BoxInTree(node);
		}

		public ITree<T> Copy()
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			if (IsTree)
			{
				NodeTree<T> NewTree = CopyCore();

				return NewTree;
			}
			else
			{
				NodeTree<T> NewNode = CopyCore();

				return BoxInTree(NewNode);
			}
		}

		public ITree<T> DeepCopy()
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			if (IsTree)
			{
				NodeTree<T> NewTree = DeepCopyCore();

				return NewTree;
			}
			else
			{
				NodeTree<T> NewNode = DeepCopyCore();

				return BoxInTree(NewNode);
			}
		}

		public void Remove()
		{
			if (this.IsRoot) throw new InvalidOperationException("This is a Root");
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			RemoveCore();
		}

		//-----------------------------------------------------------------------------

		protected virtual NodeTree<T> CutCore()
		{
			if (this.IsRoot) throw new InvalidOperationException("This is a Root");

			IncrementVersion();

			OnCutting(this);

			INode<T> OldRoot = Root;

			if (this._Next != null)
				this._Next._Previous = this._Previous;

			if (this.Previous != null)
				this._Previous._Next = this._Next;
			else // this is a first node
			{
				Debug.Assert(Parent.Child == this);
				this._Parent._Child = this._Next;
				Debug.Assert(this.Next == null || this.Next.Previous == null);
			}

			this._Parent = null;
			this._Previous = null;
			this._Next = null;

			OnCutDone(OldRoot, this);

			return this;
		}

		protected virtual NodeTree<T> CopyCore()
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");
			if (IsRoot && !IsTree) throw new InvalidOperationException("This is a Root");

			if (IsTree)
			{
				NodeTree<T> NewTree = CreateTree();

				OnCopying(this, NewTree);

				CopyChildNodes(this, NewTree, false);

				OnCopied(this, NewTree);

				return NewTree;
			}
			else
			{
				NodeTree<T> NewNode = CreateNode();

				NewNode._Data = Data;

				OnCopying(this, NewNode);

				CopyChildNodes(this, NewNode, false);

				OnCopied(this, NewNode);

				return NewNode;
			}
		}

		protected virtual NodeTree<T> DeepCopyCore()
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");
			if (IsRoot && !IsTree) throw new InvalidOperationException("This is a Root");

			if (IsTree)
			{
				NodeTree<T> NewTree = CreateTree();

				OnCopying(this, NewTree);

				CopyChildNodes(this, NewTree, true);

				OnCopied(this, NewTree);

				return NewTree;
			}
			else
			{
				NodeTree<T> NewNode = CreateNode();

				NewNode._Data = DeepCopyData(Data);

				OnDeepCopying(this, NewNode);

				CopyChildNodes(this, NewNode, true);

				OnDeepCopied(this, NewNode);

				return NewNode;
			}
		}

		private void CopyChildNodes(INode<T> oldNode, NodeTree<T> newNode, bool bDeepCopy)
		{
			NodeTree<T> previousNewChildNode = null;

			for (INode<T> oldChildNode = oldNode.Child; oldChildNode != null; oldChildNode = oldChildNode.Next)
			{
				NodeTree<T> newChildNode = CreateNode();

				if (!bDeepCopy)
					newChildNode._Data = oldChildNode.Data;
				else
					newChildNode._Data = DeepCopyData(oldChildNode.Data);

				//				if ( ! bDeepCopy )
				//					OnCopying( oldChildNode, newChildNode );
				//				else
				//					OnDeepCopying( oldChildNode, newChildNode );

				if (oldChildNode.Previous == null) newNode._Child = newChildNode;

				newChildNode._Parent = newNode;
				newChildNode._Previous = previousNewChildNode;
				if (previousNewChildNode != null) previousNewChildNode._Next = newChildNode;

				//				if ( ! bDeepCopy )
				//					OnCopied( oldChildNode, newChildNode );
				//				else
				//					OnDeepCopied( oldChildNode, newChildNode );

				CopyChildNodes(oldChildNode, newChildNode, bDeepCopy);

				previousNewChildNode = newChildNode;
			}
		}


		protected virtual void RemoveCore()
		{
			if (this.IsRoot) throw new InvalidOperationException("This is a Root");

			CutCore();
		}

		//-----------------------------------------------------------------------------

		public bool CanMoveToParent
		{
			get
			{
				if (this.IsRoot) return false;
				if (this.IsTop) return false;

				return true;
			}
		}

		public bool CanMoveToPrevious
		{
			get
			{
				if (this.IsRoot) return false;
				if (this.IsFirst) return false;

				return true;
			}
		}

		public bool CanMoveToNext
		{
			get
			{
				if (this.IsRoot) return false;
				if (this.IsLast) return false;

				return true;
			}
		}

		public bool CanMoveToChild
		{
			get
			{
				if (this.IsRoot) return false;
				if (this.IsFirst) return false;

				return true;
			}
		}

		public bool CanMoveToFirst
		{
			get
			{
				if (this.IsRoot) return false;
				if (this.IsFirst) return false;

				return true;
			}
		}

		public bool CanMoveToLast
		{
			get
			{
				if (this.IsRoot) return false;
				if (this.IsLast) return false;

				return true;
			}
		}

		//-----------------------------------------------------------------------------

		public void MoveToParent()
		{
			if (!CanMoveToParent) throw new InvalidOperationException("Cannot move to Parent");

			NodeTree<T> parentNode = GetNodeTree(this.Parent);

			NodeTree<T> thisNode = this.CutCore();

			parentNode.InsertNextCore(thisNode);
		}

		public void MoveToPrevious()
		{
			if (!CanMoveToPrevious) throw new InvalidOperationException("Cannot move to Previous");

			NodeTree<T> previousNode = GetNodeTree(this.Previous);

			NodeTree<T> thisNode = this.CutCore();

			previousNode.InsertPreviousCore(thisNode);
		}

		public void MoveToNext()
		{
			if (!CanMoveToNext) throw new InvalidOperationException("Cannot move to Next");

			NodeTree<T> nextNode = GetNodeTree(this.Next);

			NodeTree<T> thisNode = this.CutCore();

			nextNode.InsertNextCore(thisNode);
		}

		public void MoveToChild()
		{
			if (!CanMoveToChild) throw new InvalidOperationException("Cannot move to Child");

			NodeTree<T> previousNode = GetNodeTree(this.Previous);

			NodeTree<T> thisNode = this.CutCore();

			previousNode.AddChildCore(thisNode);
		}

		public void MoveToFirst()
		{
			if (!CanMoveToFirst) throw new InvalidOperationException("Cannot move to first");

			NodeTree<T> firstNode = GetNodeTree(this.First);

			NodeTree<T> thisNode = this.CutCore();

			firstNode.InsertPreviousCore(thisNode);
		}


		public void MoveToLast()
		{
			if (!CanMoveToLast) throw new InvalidOperationException("Cannot move to last");

			NodeTree<T> lastNode = GetNodeTree(this.Last);

			NodeTree<T> thisNode = this.CutCore();

			lastNode.InsertNextCore(thisNode);
		}

		//-----------------------------------------------------------------------------
		// Enumerators

		public virtual IEnumerableCollection<INode<T>> Nodes
		{
			get
			{
				return All.Nodes;
			}
		}

		public virtual IEnumerableCollection<T> Values
		{
			get
			{
				return All.Values;
			}
		}

		//-----------------------------------------------------------------------------
		// BaseEnumerableCollectionPair

		protected abstract class BaseEnumerableCollectionPair : IEnumerableCollectionPair<T>
		{
			private NodeTree<T> _Root = null;

			protected NodeTree<T> Root
			{
				get { return _Root; }
				set { _Root = value; }
			}

			protected BaseEnumerableCollectionPair(NodeTree<T> root)
			{
				_Root = root;
			}

			// Nodes
			public abstract IEnumerableCollection<INode<T>> Nodes { get; }

			protected abstract class BaseNodesEnumerableCollection : IEnumerableCollection<INode<T>>, IEnumerator<INode<T>>
			{
				private int _Version = 0;
				private object _SyncRoot = new object();

				private NodeTree<T> _Root = null;
				protected NodeTree<T> Root
				{
					get { return _Root; }
					set { _Root = value; }
				}

				private INode<T> _CurrentNode = null;
				protected INode<T> CurrentNode
				{
					get { return _CurrentNode; }
					set { _CurrentNode = value; }
				}

				private bool _BeforeFirst = true;
				protected bool BeforeFirst
				{
					get { return _BeforeFirst; }
					set { _BeforeFirst = value; }
				}

				private bool _AfterLast = false;
				protected bool AfterLast
				{
					get { return _AfterLast; }
					set { _AfterLast = value; }
				}

				protected BaseNodesEnumerableCollection(NodeTree<T> root)
				{
					_Root = root;
					_CurrentNode = root;

					_Version = _Root.Version;
				}

				~BaseNodesEnumerableCollection()
				{
					Dispose(false);
				}

				protected abstract BaseNodesEnumerableCollection CreateCopy();

				protected virtual bool HasChanged { get { return _Root.HasChanged(_Version); } }

				// IDisposable
				public void Dispose()
				{
					Dispose(true);

					GC.SuppressFinalize(this);
				}

				protected virtual void Dispose(bool disposing)
				{
				}

				// IEnumerable
				IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }

				// IEnumerable<INode<T>>
				public virtual IEnumerator<INode<T>> GetEnumerator()
				{
					Reset();

					return this;
				}

				// ICollection
				public virtual int Count
				{
					get
					{
						BaseNodesEnumerableCollection e = CreateCopy();

						int i = 0;
						foreach (INode<T> o in e) i++;
						return i;
					}
				}

				public virtual bool IsSynchronized { get { return false; } }

				public virtual object SyncRoot { get { return _SyncRoot; } }

				void ICollection.CopyTo(Array array, int index)
				{
					if (array == null) throw new ArgumentNullException("array");
					if (array.Rank > 1) throw new ArgumentException("array is multidimensional", "array");
					if (index < 0) throw new ArgumentOutOfRangeException("index");

					int count = Count;

					if (count > 0)
						if (index >= array.Length) throw new ArgumentException("index is out of bounds", "index");

					if (index + count > array.Length) throw new ArgumentException("Not enough space in array", "array");

					BaseNodesEnumerableCollection e = CreateCopy();

					foreach (INode<T> n in e)
						array.SetValue(n, index++);
				}

				public virtual void CopyTo(T[] array, int index)
				{
					((ICollection)this).CopyTo(array, index);
				}

				// ICollectionEnumerable<INode<T>>
				public virtual bool Contains(INode<T> item)
				{
					BaseNodesEnumerableCollection e = CreateCopy();

					IEqualityComparer<INode<T>> comparer = EqualityComparer<INode<T>>.Default;

					foreach (INode<T> n in e)
						if (comparer.Equals(n, item))
							return true;

					return false;
				}

				// IEnumerator
				object IEnumerator.Current
				{
					get { return Current; }
				}

				// IEnumerator<INode<T>>
				public virtual void Reset()
				{
					if (HasChanged) throw new InvalidOperationException("Tree has been modified.");

					_CurrentNode = _Root;

					_BeforeFirst = true;
					_AfterLast = false;
				}

				public virtual bool MoveNext()
				{
					if (HasChanged) throw new InvalidOperationException("Tree has been modified.");

					_BeforeFirst = false;

					return true;
				}

				public virtual INode<T> Current
				{
					get
					{
						if (_BeforeFirst) throw new InvalidOperationException("Enumeration has not started.");
						if (_AfterLast) throw new InvalidOperationException("Enumeration has finished.");

						return _CurrentNode;
					}
				}

			}

			// Find
			public virtual INode<T> Find(T data)
			{
				IEqualityComparer<T> comparer = _Root.DataComparer;

				INode<T> retval = null;

				foreach (INode<T> node in this.Nodes)
					if (comparer.Equals(node.Data, data))
						if (retval != null)
						{
							Debug.Assert(false, "Multiple matches");
							return null;
						}
						else retval = node;

				return retval;
			}

			public virtual INode<T> Find(Predicate<T> predicate)
			{
				INode<T> retval = null;

				foreach (INode<T> node in this.Nodes)
					if (predicate(node.Data))
						if (retval != null)
						{
							Debug.Assert(false, "Multiple matches");
							return null;
						}
						else retval = node;

				return retval;
			}


			// Values
			public virtual IEnumerableCollection<T> Values
			{
				get
				{
					return new ValuesEnumerableCollection(_Root.DataComparer, this.Nodes);
				}
			}

			private class ValuesEnumerableCollection : IEnumerableCollection<T>, IEnumerator<T>
			{
				IEqualityComparer<T> _DataComparer;
				private IEnumerableCollection<INode<T>> _Nodes;
				private IEnumerator<INode<T>> _Enumerator;

				public ValuesEnumerableCollection(IEqualityComparer<T> dataComparer, IEnumerableCollection<INode<T>> nodes)
				{
					_DataComparer = dataComparer;
					_Nodes = nodes;
					_Enumerator = _Nodes.GetEnumerator();
				}

				protected ValuesEnumerableCollection(ValuesEnumerableCollection o)
				{
					_Nodes = o._Nodes;
					_Enumerator = _Nodes.GetEnumerator();
				}

				protected virtual ValuesEnumerableCollection CreateCopy()
				{
					return new ValuesEnumerableCollection(this);
				}

				// IDisposable
				~ValuesEnumerableCollection()
				{
					Dispose(false);
				}

				public void Dispose()
				{
					Dispose(true);

					GC.SuppressFinalize(this);
				}

				protected virtual void Dispose(bool disposing)
				{
				}

				// IEnumerable
				IEnumerator IEnumerable.GetEnumerator()
				{
					return GetEnumerator();
				}

				// IEnumerable<T>
				public virtual IEnumerator<T> GetEnumerator()
				{
					Reset();

					return this;
				}

				// ICollection
				public virtual int Count
				{
					get
					{
						return _Nodes.Count;
					}
				}

				public virtual bool IsSynchronized { get { return false; } }

				public virtual object SyncRoot { get { return _Nodes.SyncRoot; } }

				public virtual void CopyTo(Array array, int index)
				{
					if (array == null) throw new ArgumentNullException("array");
					if (array.Rank > 1) throw new ArgumentException("array is multidimensional", "array");
					if (index < 0) throw new ArgumentOutOfRangeException("index");

					int count = Count;

					if (count > 0)
						if (index >= array.Length) throw new ArgumentException("index is out of bounds", "index");

					if (index + count > array.Length) throw new ArgumentException("Not enough space in array", "array");

					ValuesEnumerableCollection e = CreateCopy();

					foreach (T n in e)
						array.SetValue(n, index++);
				}

				// IEnumerableCollection<T>
				public virtual bool Contains(T item)
				{
					ValuesEnumerableCollection e = CreateCopy();

					foreach (T n in e)
						if (_DataComparer.Equals(n, item))
							return true;

					return false;
				}

				// IEnumerator
				object IEnumerator.Current
				{
					get { return Current; }
				}

				// IEnumerator<T> Members
				public virtual void Reset()
				{
					_Enumerator.Reset();
				}

				public virtual bool MoveNext()
				{
					return _Enumerator.MoveNext();
				}

				public virtual T Current
				{
					get
					{
						if (_Enumerator == null) { Debug.Assert(false); return default(T); }
						if (_Enumerator.Current == null) { Debug.Assert(false); return default(T); }

						return _Enumerator.Current.Data;
					}
				}
			}
		}

		//-----------------------------------------------------------------------------
		// AllEnumerator

		public IEnumerableCollectionPair<T> All { get { return new AllEnumerator(this); } }

		protected class AllEnumerator : BaseEnumerableCollectionPair
		{
			public AllEnumerator(NodeTree<T> root) : base(root) { }

			public override IEnumerableCollection<INode<T>> Nodes
			{
				get
				{
					return new NodesEnumerableCollection(Root);
				}
			}

			protected class NodesEnumerableCollection : BaseNodesEnumerableCollection
			{
				private bool _First = true;

				public NodesEnumerableCollection(NodeTree<T> root) : base(root) { }

				protected NodesEnumerableCollection(NodesEnumerableCollection o) : base(o.Root) { }

				protected override BaseNodesEnumerableCollection CreateCopy()
				{
					return new NodesEnumerableCollection(this);
				}

				public override void Reset()
				{
					base.Reset();

					_First = true;
				}

				public override bool MoveNext()
				{
					if (!base.MoveNext()) goto hell;

					if (CurrentNode == null) throw new InvalidOperationException("Current is null");

					if (CurrentNode.IsRoot)
					{
						CurrentNode = CurrentNode.Child;
						if (CurrentNode == null) goto hell;
					}

					if (_First) { _First = false; return true; }

					if (CurrentNode.Child != null) { CurrentNode = CurrentNode.Child; return true; }

					for (; CurrentNode.Parent != null; CurrentNode = CurrentNode.Parent)
					{
						if (CurrentNode == Root) goto hell;
						if (CurrentNode.Next != null) { CurrentNode = CurrentNode.Next; return true; }
					}

				hell:

					AfterLast = true;
					return false;
				}
			}

		}

		//-----------------------------------------------------------------------------
		// AllChildrenEnumerator

		public IEnumerableCollectionPair<T> AllChildren { get { return new AllChildrenEnumerator(this); } }

		private class AllChildrenEnumerator : BaseEnumerableCollectionPair
		{
			public AllChildrenEnumerator(NodeTree<T> root) : base(root) { }

			public override IEnumerableCollection<INode<T>> Nodes
			{
				get
				{
					return new NodesEnumerableCollection(Root);
				}
			}

			protected class NodesEnumerableCollection : BaseNodesEnumerableCollection
			{
				public NodesEnumerableCollection(NodeTree<T> root) : base(root) { }

				protected NodesEnumerableCollection(NodesEnumerableCollection o) : base(o.Root) { }

				protected override BaseNodesEnumerableCollection CreateCopy()
				{
					return new NodesEnumerableCollection(this);
				}

				public override bool MoveNext()
				{
					if (!base.MoveNext()) goto hell;

					if (CurrentNode == null) throw new InvalidOperationException("Current is null");

					if (CurrentNode.Child != null) { CurrentNode = CurrentNode.Child; return true; }

					for (; CurrentNode.Parent != null; CurrentNode = CurrentNode.Parent)
					{
						if (CurrentNode == Root) goto hell;
						if (CurrentNode.Next != null) { CurrentNode = CurrentNode.Next; return true; }
					}

				hell:

					AfterLast = true;
					return false;
				}
			}
		}

		//-----------------------------------------------------------------------------
		// DirectChildrenEnumerator

		public IEnumerableCollectionPair<T> DirectChildren { get { return new DirectChildrenEnumerator(this); } }

		private class DirectChildrenEnumerator : BaseEnumerableCollectionPair
		{
			public DirectChildrenEnumerator(NodeTree<T> root) : base(root) { }

			public override IEnumerableCollection<INode<T>> Nodes
			{
				get
				{
					return new NodesEnumerableCollection(Root);
				}
			}

			protected class NodesEnumerableCollection : BaseNodesEnumerableCollection
			{
				public NodesEnumerableCollection(NodeTree<T> root) : base(root) { }

				protected NodesEnumerableCollection(NodesEnumerableCollection o) : base(o.Root) { }

				protected override BaseNodesEnumerableCollection CreateCopy()
				{
					return new NodesEnumerableCollection(this);
				}

				public override int Count
				{
					get
					{
						return Root.DirectChildCount;
					}
				}

				public override bool MoveNext()
				{
					if (!base.MoveNext()) goto hell;

					if (CurrentNode == null) throw new InvalidOperationException("Current is null");

					if (CurrentNode == Root)
						CurrentNode = Root.Child;
					else
						CurrentNode = CurrentNode.Next;

					if (CurrentNode != null) return true;

				hell:

					AfterLast = true;
					return false;
				}
			}
		}

		//-----------------------------------------------------------------------------
		// DirectChildrenInReverseEnumerator

		public IEnumerableCollectionPair<T> DirectChildrenInReverse { get { return new DirectChildrenInReverseEnumerator(this); } }

		private class DirectChildrenInReverseEnumerator : BaseEnumerableCollectionPair
		{
			public DirectChildrenInReverseEnumerator(NodeTree<T> root) : base(root) { }

			public override IEnumerableCollection<INode<T>> Nodes
			{
				get
				{
					return new NodesEnumerableCollection(Root);
				}
			}

			protected class NodesEnumerableCollection : BaseNodesEnumerableCollection
			{
				public NodesEnumerableCollection(NodeTree<T> root) : base(root) { }

				protected NodesEnumerableCollection(NodesEnumerableCollection o) : base(o.Root) { }

				protected override BaseNodesEnumerableCollection CreateCopy()
				{
					return new NodesEnumerableCollection(this);
				}

				public override int Count
				{
					get
					{
						return Root.DirectChildCount;
					}
				}

				public override bool MoveNext()
				{
					if (!base.MoveNext()) goto hell;

					if (CurrentNode == null) throw new InvalidOperationException("Current is null");

					if (CurrentNode == Root)
						CurrentNode = Root.LastChild;
					else
						CurrentNode = CurrentNode.Previous;

					if (CurrentNode != null) return true;

				hell:

					AfterLast = true;
					return false;
				}
			}
		}

		//-----------------------------------------------------------------------------
		// DirectChildCount

		public int DirectChildCount
		{
			get
			{
				int i = 0;

				for (INode<T> n = this.Child; n != null; n = n.Next) i++;

				return i;
			}
		}

		//-----------------------------------------------------------------------------
		// ITree<T>

		public virtual Type DataType
		{
			get
			{
				return typeof(T);
			}
		}

		public void Clear()
		{
			if (!this.IsRoot) throw new InvalidOperationException("This is not a Root");
			if (!this.IsTree) throw new InvalidOperationException("This is not a tree");

			OnClearing(this);

			_Child = null;

			OnCleared(this);
		}

		//-----------------------------------------------------------------------------
		// GetNodeTree

		protected static NodeTree<T> GetNodeTree(ITree<T> tree)
		{
			if (tree == null) throw new ArgumentNullException("Tree is null");

			return (NodeTree<T>)tree; // can throw an InvalidCastException.
		}

		protected static NodeTree<T> GetNodeTree(INode<T> node)
		{
			if (node == null) throw new ArgumentNullException("Node is null");

			return (NodeTree<T>)node; // can throw an InvalidCastException.
		}

		//-----------------------------------------------------------------------------
		// ICollection

		//		public virtual bool IsSynchronized { get { return false; } } // Not thread safe

		//		public virtual T SyncRoot { get { return this; } } // Not sure about this!

		public virtual int Count
		{
			get
			{
				int i = IsRoot ? 0 : 1;

				for (INode<T> n = this.Child; n != null; n = n.Next)
					i += n.Count;

				return i;
			}
		}

		public virtual bool IsReadOnly { get { return false; } }

		//-----------------------------------------------------------------------------
		// Sorting

		public virtual void SortAllChildren()
		{
			foreach (INode<T> node in All.Nodes) node.SortDirectChildren();
		}

		public virtual void SortAllChildren(Comparison<T> comparison)
		{
			foreach (INode<T> node in All.Nodes) node.SortDirectChildren(comparison);
		}

		public virtual void SortAllChildren(IComparer<T> comparer)
		{
			foreach (INode<T> node in All.Nodes) node.SortDirectChildren(comparer);
		}

		public virtual void SortDirectChildren()
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			if (DirectChildCount < 2) return;

			List<INode<T>> children = new List<INode<T>>(DirectChildren.Nodes);

			children.Sort();

			SortDirectChildrenCore(children);
		}

		public virtual void SortDirectChildren(Comparison<T> comparison)
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			if (DirectChildCount < 2) return;

			List<INode<T>> children = new List<INode<T>>(DirectChildren.Nodes);

			children.Sort((x, y) => comparison(x.Data, y.Data));

			SortDirectChildrenCore(children);
		}

		public virtual void SortDirectChildren(IComparer<T> comparer)
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");

			if (DirectChildCount < 2) return;

			List<INode<T>> children = new List<INode<T>>(DirectChildren.Nodes);

			NodeComparer<T> nodeComparer = new NodeComparer<T>(comparer);

			children.Sort(nodeComparer);

			SortDirectChildrenCore(children);
		}

		class NodeComparer<T> : IComparer<INode<T>>
		{
			IComparer<T> _DataComparer = null;

			public NodeComparer(IComparer<T> dataComparer)
			{
				_DataComparer = dataComparer;
			}

			public int Compare(INode<T> x, INode<T> y)
			{
				return _DataComparer.Compare(x.Data, y.Data);
			}
		}

		void SortDirectChildrenCore(List<INode<T>> children)
		{
			_Child = null;

			NodeTree<T> previous = null;
			foreach (INode<T> iChild in children)
			{
				NodeTree<T> child = GetNodeTree(iChild);

				child._Parent = this;

				child._Previous = null;
				child._Next = null;

				if (_Child == null)
				{
					_Child = child;
				}
				else
				{
					previous._Next = child;
					child._Previous = previous;
				}

				previous = child;
			}
		}

		//-----------------------------------------------------------------------------
		// Events

		private EventHandlerList _EventHandlerList;

		protected EventHandlerList EventHandlerList
		{
			get { return _EventHandlerList; }
			//set { _EventHandlerList = value; }
		}

		protected EventHandlerList GetCreateEventHandlerList()
		{
			if (_EventHandlerList == null) _EventHandlerList = new EventHandlerList();

			return _EventHandlerList;
		}

		private static readonly object _ValidateEventKey = new object();
		private static readonly object _ClearingEventKey = new object();
		private static readonly object _ClearedEventKey = new object();
		private static readonly object _SettingEventKey = new object();
		private static readonly object _SetDoneEventKey = new object();
		private static readonly object _InsertingEventKey = new object();
		private static readonly object _InsertedEventKey = new object();
		private static readonly object _CuttingEventKey = new object();
		private static readonly object _CutDoneEventKey = new object();
		private static readonly object _CopyingEventKey = new object();
		private static readonly object _CopiedEventKey = new object();
		private static readonly object _DeepCopyingEventKey = new object();
		private static readonly object _DeepCopiedEventKey = new object();

		protected static object ValidateEventKey { get { return _ValidateEventKey; } }
		protected static object ClearingEventKey { get { return _ClearingEventKey; } }
		protected static object ClearedEventKey { get { return _ClearedEventKey; } }
		protected static object SettingEventKey { get { return _SettingEventKey; } }
		protected static object SetDoneEventKey { get { return _SetDoneEventKey; } }
		protected static object InsertingEventKey { get { return _InsertingEventKey; } }
		protected static object InsertedEventKey { get { return _InsertedEventKey; } }
		protected static object CuttingEventKey { get { return _CuttingEventKey; } }
		protected static object CutDoneEventKey { get { return _CutDoneEventKey; } }
		protected static object CopyingEventKey { get { return _CopyingEventKey; } }
		protected static object CopiedEventKey { get { return _CopiedEventKey; } }
		protected static object DeepCopyingEventKey { get { return _DeepCopyingEventKey; } }
		protected static object DeepCopiedEventKey { get { return _DeepCopiedEventKey; } }

		public event EventHandler<NodeTreeDataEventArgs<T>> Validate
		{
			add
			{
				GetCreateEventHandlerList().AddHandler(ValidateEventKey, value);
			}

			remove
			{
				GetCreateEventHandlerList().RemoveHandler(ValidateEventKey, value);
			}
		}

		public event EventHandler Clearing
		{
			add
			{
				GetCreateEventHandlerList().AddHandler(ClearingEventKey, value);
			}

			remove
			{
				GetCreateEventHandlerList().RemoveHandler(ClearingEventKey, value);
			}
		}

		public event EventHandler Cleared
		{
			add
			{
				GetCreateEventHandlerList().AddHandler(ClearedEventKey, value);
			}

			remove
			{
				GetCreateEventHandlerList().RemoveHandler(ClearedEventKey, value);
			}
		}

		public event EventHandler<NodeTreeDataEventArgs<T>> Setting
		{
			add
			{
				GetCreateEventHandlerList().AddHandler(SettingEventKey, value);
			}

			remove
			{
				GetCreateEventHandlerList().RemoveHandler(SettingEventKey, value);
			}
		}

		public event EventHandler<NodeTreeDataEventArgs<T>> SetDone
		{
			add
			{
				GetCreateEventHandlerList().AddHandler(SetDoneEventKey, value);
			}

			remove
			{
				GetCreateEventHandlerList().RemoveHandler(SetDoneEventKey, value);
			}
		}

		public event EventHandler<NodeTreeInsertEventArgs<T>> Inserting
		{
			add
			{
				GetCreateEventHandlerList().AddHandler(InsertingEventKey, value);
			}

			remove
			{
				GetCreateEventHandlerList().RemoveHandler(InsertingEventKey, value);
			}
		}

		public event EventHandler<NodeTreeInsertEventArgs<T>> Inserted
		{
			add
			{
				GetCreateEventHandlerList().AddHandler(InsertedEventKey, value);
			}

			remove
			{
				GetCreateEventHandlerList().RemoveHandler(InsertedEventKey, value);
			}
		}

		public event EventHandler Cutting
		{
			add
			{
				GetCreateEventHandlerList().AddHandler(CuttingEventKey, value);
			}

			remove
			{
				GetCreateEventHandlerList().RemoveHandler(CuttingEventKey, value);
			}
		}

		public event EventHandler CutDone
		{
			add
			{
				GetCreateEventHandlerList().AddHandler(CutDoneEventKey, value);
			}

			remove
			{
				GetCreateEventHandlerList().RemoveHandler(CutDoneEventKey, value);
			}
		}

		public event EventHandler<NodeTreeNodeEventArgs<T>> Copying
		{
			add
			{
				GetCreateEventHandlerList().AddHandler(CopyingEventKey, value);
			}

			remove
			{
				GetCreateEventHandlerList().RemoveHandler(CopyingEventKey, value);
			}
		}

		public event EventHandler<NodeTreeNodeEventArgs<T>> Copied
		{
			add
			{
				GetCreateEventHandlerList().AddHandler(CopiedEventKey, value);
			}

			remove
			{
				GetCreateEventHandlerList().RemoveHandler(CopiedEventKey, value);
			}
		}

		public event EventHandler<NodeTreeNodeEventArgs<T>> DeepCopying
		{
			add
			{
				GetCreateEventHandlerList().AddHandler(DeepCopyingEventKey, value);
			}

			remove
			{
				GetCreateEventHandlerList().RemoveHandler(DeepCopyingEventKey, value);
			}
		}

		public event EventHandler<NodeTreeNodeEventArgs<T>> DeepCopied
		{
			add
			{
				GetCreateEventHandlerList().AddHandler(DeepCopiedEventKey, value);
			}

			remove
			{
				GetCreateEventHandlerList().RemoveHandler(DeepCopiedEventKey, value);
			}
		}


		//-----------------------------------------------------------------------------
		// Validate

		protected virtual void OnValidate(INode<T> node, T data)
		{
			if (!Root.IsTree) throw new InvalidOperationException("This is not a tree");
			if (data is INode<T>) throw new ArgumentException("Object is a node");

			if ((!typeof(T).IsClass) || ((object)data) != null)
				if (!DataType.IsInstanceOfType(data))
					throw new ArgumentException("Object is not a " + DataType.Name);

			if (_EventHandlerList != null)
			{
				EventHandler<NodeTreeDataEventArgs<T>> e = (EventHandler<NodeTreeDataEventArgs<T>>)_EventHandlerList[ValidateEventKey];
				if (e != null) e(node, new NodeTreeDataEventArgs<T>(data));
			}

			if (!IsRoot) GetNodeTree(Root).OnValidate(node, data);
		}

		//-----------------------------------------------------------------------------
		// Clear

		protected virtual void OnClearing(ITree<T> tree)
		{
			if (_EventHandlerList != null)
			{
				EventHandler e = (EventHandler)_EventHandlerList[ClearingEventKey];
				if (e != null) e(tree, EventArgs.Empty);
			}
		}

		protected virtual void OnCleared(ITree<T> tree)
		{
			if (_EventHandlerList != null)
			{
				EventHandler e = (EventHandler)_EventHandlerList[ClearedEventKey];
				if (e != null) e(tree, EventArgs.Empty);
			}
		}

		//-----------------------------------------------------------------------------
		// Set

		protected virtual void OnSetting(INode<T> node, T data)
		{
			OnSettingCore(node, data, true);
		}

		protected virtual void OnSettingCore(INode<T> node, T data, bool raiseValidate)
		{
			if (_EventHandlerList != null)
			{
				EventHandler<NodeTreeDataEventArgs<T>> e = (EventHandler<NodeTreeDataEventArgs<T>>)_EventHandlerList[SettingEventKey];
				if (e != null) e(node, new NodeTreeDataEventArgs<T>(data));
			}

			if (!IsRoot) GetNodeTree(Root).OnSettingCore(node, data, false);

			if (raiseValidate) OnValidate(node, data);
		}

		protected virtual void OnSetDone(INode<T> node, T data)
		{
			OnSetDoneCore(node, data, true);
		}

		protected virtual void OnSetDoneCore(INode<T> node, T data, bool raiseValidate)
		{
			if (_EventHandlerList != null)
			{
				EventHandler<NodeTreeDataEventArgs<T>> e = (EventHandler<NodeTreeDataEventArgs<T>>)_EventHandlerList[SetDoneEventKey];
				if (e != null) e(node, new NodeTreeDataEventArgs<T>(data));
			}

			if (!IsRoot) GetNodeTree(Root).OnSetDoneCore(node, data, false);

			//			if ( raiseValidate ) OnValidate( Node, Data );
		}

		//-----------------------------------------------------------------------------
		// Insert

		protected virtual void OnInserting(INode<T> oldNode, NodeTreeInsertOperation operation, INode<T> newNode)
		{
			OnInsertingCore(oldNode, operation, newNode, true);
		}

		protected virtual void OnInsertingCore(INode<T> oldNode, NodeTreeInsertOperation operation, INode<T> newNode, bool raiseValidate)
		{
			if (_EventHandlerList != null)
			{
				EventHandler<NodeTreeInsertEventArgs<T>> e = (EventHandler<NodeTreeInsertEventArgs<T>>)_EventHandlerList[InsertingEventKey];
				if (e != null) e(oldNode, new NodeTreeInsertEventArgs<T>(operation, newNode));
			}

			if (!IsRoot) GetNodeTree(Root).OnInsertingCore(oldNode, operation, newNode, false);

			if (raiseValidate) OnValidate(oldNode, newNode.Data);

			if (raiseValidate) OnInsertingTree(newNode);
		}

		protected virtual void OnInsertingTree(INode<T> newNode)
		{
			for (INode<T> child = newNode.Child; child != null; child = child.Next)
			{
				OnInsertingTree(newNode, child);

				OnInsertingTree(child);
			}
		}

		protected virtual void OnInsertingTree(INode<T> newNode, INode<T> child)
		{
			OnInsertingTreeCore(newNode, child, true);
		}

		protected virtual void OnInsertingTreeCore(INode<T> newNode, INode<T> child, bool raiseValidate)
		{
			if (_EventHandlerList != null)
			{
				EventHandler<NodeTreeInsertEventArgs<T>> e = (EventHandler<NodeTreeInsertEventArgs<T>>)_EventHandlerList[InsertingEventKey];
				if (e != null) e(newNode, new NodeTreeInsertEventArgs<T>(NodeTreeInsertOperation.Tree, child));
			}

			if (!IsRoot) GetNodeTree(Root).OnInsertingTreeCore(newNode, child, false);

			if (raiseValidate) OnValidate(newNode, child.Data);
		}

		protected virtual void OnInserted(INode<T> oldNode, NodeTreeInsertOperation operation, INode<T> newNode)
		{
			OnInsertedCore(oldNode, operation, newNode, true);
		}

		protected virtual void OnInsertedCore(INode<T> oldNode, NodeTreeInsertOperation operation, INode<T> newNode, bool raiseValidate)
		{
			if (_EventHandlerList != null)
			{
				EventHandler<NodeTreeInsertEventArgs<T>> e = (EventHandler<NodeTreeInsertEventArgs<T>>)_EventHandlerList[InsertedEventKey];
				if (e != null) e(oldNode, new NodeTreeInsertEventArgs<T>(operation, newNode));
			}

			if (!IsRoot) GetNodeTree(Root).OnInsertedCore(oldNode, operation, newNode, false);

			//			if ( raiseValidate ) OnValidate( OldNode, NewNode.Data );

			if (raiseValidate) OnInsertedTree(newNode);
		}

		protected virtual void OnInsertedTree(INode<T> newNode)
		{
			for (INode<T> child = newNode.Child; child != null; child = child.Next)
			{
				OnInsertedTree(newNode, child);

				OnInsertedTree(child);
			}
		}

		protected virtual void OnInsertedTree(INode<T> newNode, INode<T> child)
		{
			OnInsertedTreeCore(newNode, child, true);
		}

		protected virtual void OnInsertedTreeCore(INode<T> newNode, INode<T> child, bool raiseValidate)
		{
			if (_EventHandlerList != null)
			{
				EventHandler<NodeTreeInsertEventArgs<T>> e = (EventHandler<NodeTreeInsertEventArgs<T>>)_EventHandlerList[InsertedEventKey];
				if (e != null) e(newNode, new NodeTreeInsertEventArgs<T>(NodeTreeInsertOperation.Tree, child));
			}

			if (!IsRoot) GetNodeTree(Root).OnInsertedTreeCore(newNode, child, false);

			//			if ( raiseValidate ) OnValidate( newNode, child.Data );
		}

		//-----------------------------------------------------------------------------
		// Cut

		protected virtual void OnCutting(INode<T> oldNode)
		{
			if (_EventHandlerList != null)
			{
				EventHandler e = (EventHandler)_EventHandlerList[CuttingEventKey];
				if (e != null) e(oldNode, EventArgs.Empty);
			}

			if (!IsRoot) GetNodeTree(Root).OnCutting(oldNode);
		}

		protected virtual void OnCutDone(INode<T> oldRoot, INode<T> oldNode)
		{
			if (_EventHandlerList != null)
			{
				EventHandler e = (EventHandler)_EventHandlerList[CutDoneEventKey];
				if (e != null) e(oldNode, EventArgs.Empty);
			}

			if (!IsTree) GetNodeTree(oldRoot).OnCutDone(oldRoot, oldNode);
		}

		//-----------------------------------------------------------------------------
		// Copy

		protected virtual void OnCopying(INode<T> oldNode, INode<T> newNode)
		{
			OnCopyingCore(oldNode, newNode, true);
		}

		protected virtual void OnCopyingCore(INode<T> oldNode, INode<T> newNode, bool raiseValidate)
		{
			if (_EventHandlerList != null)
			{
				EventHandler<NodeTreeNodeEventArgs<T>> e = (EventHandler<NodeTreeNodeEventArgs<T>>)_EventHandlerList[CopyingEventKey];
				if (e != null) e(oldNode, new NodeTreeNodeEventArgs<T>(newNode));
			}

			if (!IsRoot) GetNodeTree(Root).OnCopyingCore(oldNode, newNode, false);

			//			if ( raiseValidate ) OnValidate( oldNode, newNode.Data );
		}

		protected virtual void OnCopied(INode<T> oldNode, INode<T> newNode)
		{
			OnCopiedCore(oldNode, newNode, true);
		}

		protected virtual void OnCopiedCore(INode<T> oldNode, INode<T> newNode, bool raiseValidate)
		{
			if (_EventHandlerList != null)
			{
				EventHandler<NodeTreeNodeEventArgs<T>> e = (EventHandler<NodeTreeNodeEventArgs<T>>)_EventHandlerList[CopiedEventKey];
				if (e != null) e(oldNode, new NodeTreeNodeEventArgs<T>(newNode));
			}

			if (!IsRoot) GetNodeTree(Root).OnCopiedCore(oldNode, newNode, false);

			//			if ( raiseValidate ) OnValidate( oldNode, newNode.Data );
		}

		//-----------------------------------------------------------------------------
		// DeepCopy

		protected virtual void OnDeepCopying(INode<T> oldNode, INode<T> newNode)
		{
			OnDeepCopyingCore(oldNode, newNode, true);
		}

		protected virtual void OnDeepCopyingCore(INode<T> oldNode, INode<T> newNode, bool raiseValidate)
		{
			if (_EventHandlerList != null)
			{
				EventHandler<NodeTreeNodeEventArgs<T>> e = (EventHandler<NodeTreeNodeEventArgs<T>>)_EventHandlerList[DeepCopyingEventKey];
				if (e != null) e(oldNode, new NodeTreeNodeEventArgs<T>(newNode));
			}

			if (!IsRoot) GetNodeTree(Root).OnDeepCopyingCore(oldNode, newNode, false);

			//			if ( raiseValidate ) OnValidate( oldNode, newNode.Data );
		}

		protected virtual void OnDeepCopied(INode<T> oldNode, INode<T> newNode)
		{
			OnDeepCopiedCore(oldNode, newNode, true);
		}

		protected virtual void OnDeepCopiedCore(INode<T> oldNode, INode<T> newNode, bool raiseValidate)
		{
			if (_EventHandlerList != null)
			{
				EventHandler<NodeTreeNodeEventArgs<T>> e = (EventHandler<NodeTreeNodeEventArgs<T>>)_EventHandlerList[DeepCopiedEventKey];
				if (e != null) e(oldNode, new NodeTreeNodeEventArgs<T>(newNode));
			}

			if (!IsRoot) GetNodeTree(Root).OnDeepCopiedCore(oldNode, newNode, false);

			//			if ( raiseValidate ) OnValidate( oldNode, newNode.Data );
		}

		//-----------------------------------------------------------------------------

	} // class NodeTree

	//-----------------------------------------------------------------------------
}