//******************************
// Written by Peter Golde
// Copyright (c) 2004-2005, Wintellect
//
// Use and restribution of this code is subject to the license agreement 
// contained in the file "License.txt" accompanying this file.
//******************************

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


namespace Wintellect.PowerCollections 
{
    /// <summary>
    /// Describes what to do if a key is already in the tree when doing an
    /// insertion.
    /// </summary>
    internal enum DuplicatePolicy { 
        InsertFirst,               // Insert a new node before duplicates
        InsertLast,               // Insert a new node after duplicates
        ReplaceFirst,            // Replace the first of the duplicate nodes
        ReplaceLast,            // Replace the last of the duplicate nodes
        DoNothing                // Do nothing to the tree
    };

	/// <summary>
	/// The base implementation for various collections classes that use Red-Black trees
	/// as part of their implementation. This class should not (and can not) be 
	/// used directly by end users; it's only for internal use by the collections package.
	/// </summary>
	/// <remarks>
	/// The Red-Black tree manages items of type T, and uses a IComparer&lt;T&gt; that
	/// compares items to sort the tree. Multiple items can compare equal and be stored
	/// in the tree. Insert, Delete, and Find operations are provided in their full generality;
	/// all operations allow dealing with either the first or last of items that compare equal. 
	///</remarks>
    [Serializable]
	internal class RedBlackTree<T>: IEnumerable<T> {
		private IComparer<T> comparer;			// interface for comparing elements, only Compare is used.
		private Node root;					// The root of the tree. Can be null when tree is empty.
		private int count;						// The count of elements in the tree.

        private int changeStamp;        // An integer that is changed every time the tree structurally changes.
                                                        // Used so that enumerations throw an exception if the tree is changed
                                                        // during enumeration.

        private Node[] stack;               // A stack of nodes. This is cached locally to avoid constant re-allocated it.

        /// <summary>
        /// Create an array of Nodes big enough for any path from top 
        /// to bottom. This is cached, and reused from call-to-call, so only one
        /// can be around at a time per tree.
        /// </summary>
        /// <returns>The node stack.</returns>
        private Node[] GetNodeStack()
        {
            // Maximum depth needed is 2 * lg count + 1.
            int maxDepth;
            if (count < 0x400)
                maxDepth = 21;
            else if (count < 0x10000)
                maxDepth = 41;
            else
                maxDepth = 65;

            if (stack == null || stack.Length < maxDepth)
                stack = new Node[maxDepth];

            return stack;
        }

        /// <summary>
		/// The class that is each node in the red-black tree.
		/// </summary>
        [Serializable]
		private class Node {
			public Node left, right;
			public T item;

            private const uint REDMASK = 0x80000000;
            private uint count;

            /// <summary>
            /// Is this a red node?
            /// </summary>
            public bool IsRed {
                get { return (count & REDMASK) != 0; }
                set { 
                    if (value) 
                        count |= REDMASK; 
                    else
                        count &= ~REDMASK;
                }
            }

            /// <summary>
            /// Get or set the Count field -- a 31-bit field
            /// that holds the number of nodes at or below this
            /// level.
            /// </summary>
            public int Count
            {
                get { return (int)(count & ~REDMASK); }
                set { count = (count & REDMASK) | (uint)value; }
            }

            /// <summary>
            /// Add one to the Count.
            /// </summary>
            public void IncrementCount()
            {
                ++count;
            }

            /// <summary>
            /// Subtract one from the Count. The current
            /// Count must be non-zero.
            /// </summary>
            public void DecrementCount()
            {
                Debug.Assert(Count != 0);
                --count;
            }

            /// <summary>
            /// Clones a node and all its descendants.
            /// </summary>
            /// <returns>The cloned node.</returns>
            public Node Clone()
            {
                Node newNode = new Node();
                newNode.item = item;

                newNode.count = count;

                if (left != null)
                    newNode.left = left.Clone();

                if (right != null)
                    newNode.right = right.Clone();

                return newNode;
            }
        }

        /// <summary>
        /// Must be called whenever there is a structural change in the tree. Causes
        /// changeStamp to be changed, which causes any in-progress enumerations
        /// to throw exceptions.
        /// </summary>
        internal void StopEnumerations()
        {
            ++changeStamp;
        }

        /// <summary>
        /// Checks the given stamp against the current change stamp. If different, the
        /// collection has changed during enumeration and an InvalidOperationException
        /// must be thrown
        /// </summary>
        /// <param name="startStamp">changeStamp at the start of the enumeration.</param>
        private void CheckEnumerationStamp(int startStamp)
        {
            if (startStamp != changeStamp) {
                throw new InvalidOperationException(Strings.ChangeDuringEnumeration);
            }
        }

        /// <summary>
		/// Initialize a red-black tree, using the given interface instance to compare elements. Only
		/// Compare is used on the IComparer interface.
		/// </summary>
		/// <param name="comparer">The IComparer&lt;T&gt; used to sort keys.</param>
		public RedBlackTree(IComparer<T> comparer) {
			this.comparer = comparer;
			this.count = 0;
			this.root = null;
		}

		/// <summary>
		/// Returns the number of elements in the tree.
		/// </summary>
		public int ElementCount {
			get {
				return count;
			}
		}

        /// <summary>
        /// Clone the tree, returning a new tree containing the same items. Should
        /// take O(N) take.
        /// </summary>
        /// <returns>Clone version of this tree.</returns>
        public RedBlackTree<T> Clone()
        {
            RedBlackTree<T> newTree = new RedBlackTree<T>(comparer);
            newTree.count = this.count;
            if (this.root != null)
                newTree.root = this.root.Clone();
            return newTree;
        }

		/// <summary>
		/// Finds the key in the tree. If multiple items in the tree have
		/// compare equal to the key, finds the first or last one. Optionally replaces the item
		/// with the one searched for.
		/// </summary>
		/// <param name="key">Key to search for.</param>
		/// <param name="findFirst">If true, find the first of duplicates, else finds the last of duplicates.</param>
        /// <param name="replace">If true, replaces the item with key (if function returns true)</param>
        /// <param name="item">Returns the found item, before replacing (if function returns true).</param>
        /// <returns>True if the key was found.</returns>
		public bool Find(T key, bool findFirst, bool replace, out T item) {
			Node current = root;			// current search location in the tree
			Node found = null;			// last node found with the key, or null if none.
			
			while (current != null) {
				int compare = comparer.Compare(key, current.item);

				if (compare < 0) {
					current = current.left;
				}
				else if (compare > 0) {
					current = current.right;
				}
				else {
					// Go left/right on equality to find first/last of elements with this key.
					Debug.Assert(compare == 0);
					found = current;
					if (findFirst)
						current = current.left;
					else
						current = current.right;
				}
			}

			if (found != null) {
				item = found.item;
                if (replace)
                    found.item = key;
                return true;
			}
			else {
				item = default(T);	
				return false;
			}
		}

        /// <summary>
        /// Finds the index of the key in the tree. If multiple items in the tree have
        /// compare equal to the key, finds the first or last one. 
        /// </summary>
        /// <param name="key">Key to search for.</param>
        /// <param name="findFirst">If true, find the first of duplicates, else finds the last of duplicates.</param>
        /// <returns>Index of the item found if the key was found, -1 if not found.</returns>
        public int FindIndex(T key, bool findFirst)
        {
            T dummy;
            if (findFirst)
                return FirstItemInRange(EqualRangeTester(key), out dummy);
            else
                return LastItemInRange(EqualRangeTester(key), out dummy);
        }

        /// <summary>
        /// Find the item at a particular index in the tree.
        /// </summary>
        /// <param name="index">The zero-based index of the item. Must be &gt;= 0 and &lt; Count.</param>
        /// <returns>The item at the particular index.</returns>
        public T GetItemByIndex(int index)
        {
            if (index < 0 || index >= count)
                throw new ArgumentOutOfRangeException("index");

			Node current = root;			// current search location in the tree

            for (; ; ) {
                int leftCount;

                if (current.left != null) 
                    leftCount = current.left.Count;
                else 
                    leftCount = 0;

                if (leftCount > index)
                    current = current.left;
                else if (leftCount == index)
                    return current.item;
                else {
                    index -= leftCount + 1;
                    current = current.right;
                }
            }
		}

		/// <summary>
		/// Insert a new node into the tree, maintaining the red-black invariants.
		/// </summary>
		/// <remarks>Algorithm from Sedgewick, "Algorithms".</remarks>
		/// <param name="item">The new item to insert</param>
		/// <param name="dupPolicy">What to do if equal item is already present.</param>
		/// <param name="previous">If false, returned, the previous item.</param>
		/// <returns>false if duplicate exists, otherwise true.</returns>
		public bool Insert(T item, DuplicatePolicy dupPolicy, out T previous) {
			Node node = root;
			Node parent = null, gparent = null, ggparent = null;	// parent, grand, a great-grantparent of node.
			bool wentLeft = false, wentRight = false;				// direction from parent to node.
            bool rotated;
			Node duplicateFound = null;