/*
 AvlDictionary.cs - C# implementation of an AVL tree based generic IDictionary<TKey,TValue> interface.

 Copyright (C) 2009   Peter Graf

 This file is part of PBL - The Program Base Library.
 PBL is free software.

 This library is free software; you can redistribute it and/or
 modify it under the terms of the GNU Lesser General Public
 License as published by the Free Software Foundation; either
 version 2.1 of the License, or (at your option) any later version.

 This library is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 Lesser General Public License for more details.

 You should have received a copy of the GNU Lesser General Public
 License along with this library; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 For more information on the Program Base Library or Peter Graf,
 please see: http://www.mission-base.com/.

 $Log: AvlDictionary.cs,v $

 */

using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.InteropServices;
using System.Diagnostics;

namespace Com.Mission_Base.Pbl
{
    /// <summary>
    /// AvlDictionary&lt;TKey,TValue&gt; is an implementation of the generic IDictionary&lt;TKey,TValue&gt; interface based on an AVL-tree.
    /// The AvlDictionary&lt;TKey,TValue&gt; represents a collection of key/value pairs that are sorted on the key.
    /// </summary>
    /// <typeparam name="TKey">
    /// The type of keys in the dictionary.
    /// </typeparam>
    /// <typeparam name="TValue">
    /// The type of values in the dictionary.
    /// </typeparam>
    [Serializable]
    [ComVisible(false)]
    [DebuggerDisplay("Count = {Count}")]
    public class AvlDictionary<TKey, TValue> :
        IDictionary<TKey, TValue>,
        ICollection<KeyValuePair<TKey, TValue>>,
        IEnumerable<KeyValuePair<TKey, TValue>>,
        ICollection,
        IEnumerable
        where TKey : IComparable<TKey>
    {
        /// <summary>
        /// Provides the common base functionality of all Enumerators used with an AvlDictionary&lt;TKey,TValue&gt;.
        /// </summary>
        public class AvlDictionaryBaseEnumerator
        {
            private AvlDictionary<TKey, TValue> _AvlDictionary;
            private AvlTreeNode _Node;
            private bool _IsExhausted;
            private long _ChangeCounter;

            /// <summary>
            /// Creates a new enumerator of the AvlDictionary&lt;TKey,TValue&gt;.
            /// </summary>
            /// <param name="dictionary">
            /// The AvlDictionary&lt;TKey,TValue&gt; the enumerator is created for.
            /// </param>

            protected AvlDictionaryBaseEnumerator(AvlDictionary<TKey, TValue> dictionary)
            {
                _AvlDictionary = dictionary;
                _ChangeCounter = dictionary._ChangeCounter;
                _Node = null;
                _IsExhausted = _AvlDictionary._RootNode == null;
            }

            /// <summary>
            /// Tests whether the enumerator is properly postioned.
            /// </summary>
            /// <returns>
            /// true if the enumerator is postioned; otherwise, false.
            /// </returns>

            protected bool IsPositioned
            {
                get { return !_IsExhausted && null != _Node; }
            }

            /// <summary>
            /// Gets the element at the current position of the enumerator.
            /// </summary>
            /// <returns>
            /// The KeyValuePair&lt;TKey, TValue&gt; in the AvlDictionary&lt;TKey,TValue&gt; at the current position of the enumerator.
            /// </returns>

            protected KeyValuePair<TKey, TValue> CurrentPair
            {
                get
                {
                    if (!_IsExhausted && null != _Node)
                    {
                        return _Node.item;
                    }
                    return new KeyValuePair<TKey, TValue>(default(TKey), default(TValue));
                }
            }

            /// <summary>
            /// Gets the key at the current position of the enumerator.
            /// </summary>
            /// <returns>
            /// The key in the AvlDictionary&lt;TKey,TValue&gt;.KeyCollection at the current position of the enumerator.
            /// </returns>

            protected TKey CurrentKey
            {
                get
                {
                    if (!_IsExhausted && null != _Node)
                    {
                        return _Node.item.Key;
                    }
                    return default(TKey);
                }
            }

            /// <summary>
            /// Gets the value at the current position of the enumerator.
            /// </summary>
            /// <returns>
            /// The value in the AvlDictionary&lt;TKey,TValue&gt;.ValueCollection at the current position of the enumerator.
            /// </returns>

            protected TValue CurrentValue
            {
                get
                {
                    if (!_IsExhausted && null != _Node)
                    {
                        return _Node.item.Value;
                    }
                    return default(TValue);
                }
            }

            /// <summary>
            /// Advances the enumerator to the next element of the AvlDictionary&lt;TKey,TValue&gt;.
            /// </summary>
            /// <returns>
            /// true if the enumerator was successfully advanced to the next element; false
            //  if the enumerator has passed the end of the collection.
            /// </returns>
            /// <exception cref="System.InvalidOperationException">
            /// The AvlDictionary was modified after the enumerator was created.
            /// </exception>    
            public bool MoveNext()
            {
                if (_ChangeCounter != _AvlDictionary._ChangeCounter)
                {
                    throw new System.InvalidOperationException("The AvlDictionary was modified after the enumerator was created.");
                }
                if (_IsExhausted)
                {
                    return false;
                }
                if (null == _AvlDictionary._RootNode)
                {
                    _IsExhausted = true;
                    return false;
                }

                AvlTreeNode next;
                if (null == _Node)
                {
                    next = _AvlDictionary._RootNode.pblTreeNodeFirst();
                }
                else
                {
                    next = _Node.pblTreeNodeNext();
                }
                if (null == next)
                {
                    _IsExhausted = true;
                    return false;
                }
                _Node = next;

                return true;
            }

            /// <summary>
            /// Resets the enumerator of the AvlDictionary&lt;TKey,TValue&gt;.
            /// </summary>

            public void Reset()
            {
                _Node = null;
                _IsExhausted = _AvlDictionary._RootNode == null;
            }

            #region IDisposable Member

            /// <summary>
            /// Disposes the enumerator of the AvlDictionary&lt;TKey,TValue&gt;.
            /// </summary>

            public void Dispose()
            {
            }

            #endregion
        }

        /// <summary>
        /// Enumerates the elements of an AvlDictionary&lt;TKey,TValue&gt;.
        /// </summary>
        public sealed class Enumerator : AvlDictionaryBaseEnumerator, System.Collections.Generic.IEnumerator<KeyValuePair<TKey, TValue>>
        {
            /// <summary>
            /// Creates a new enumerator of the AvlDictionary&lt;TKey,TValue&gt;.
            /// </summary>
            /// <param name="dictionary">
            /// The AvlDictionary&lt;TKey,TValue&gt; the enumerator is created for.
            /// </param>

            public Enumerator(AvlDictionary<TKey, TValue> dictionary)
                : base(dictionary)
            {
            }

            #region IEnumerator<KeyValuePair<TKey,TValue>> Member

            /// <summary>
            /// Gets the element at the current position of the enumerator.
            /// </summary>
            /// <returns>
            /// The KeyValuePair&lt;TKey, TValue&gt; in the AvlDictionary&lt;TKey,TValue&gt; at the current position of the enumerator.
            /// </returns>

            public KeyValuePair<TKey, TValue> Current
            {
                get { return this.CurrentPair; }
            }

            #endregion

            #region IEnumerator Member

            /// <summary>
            /// Gets the element at the current position of the enumerator.
            /// </summary>
            /// <returns>
            /// The KeyValuePair&lt;TKey, TValue&gt; in the AvlDictionary&lt;TKey,TValue&gt; at the current position of the enumerator.
            /// </returns>
            /// <exception cref="System.InvalidOperationException">
            /// The enumerator is not positioned.
            /// </exception>    

            object IEnumerator.Current
            {
                get
                {
                    if (!IsPositioned)
                    {
                        throw new System.InvalidOperationException("The enumerator is not positioned.");
                    }
                    return this.CurrentPair;
                }
            }

            #endregion
        }

        /// <summary>
        /// The actual AVL-tree code. It was lifted from the C implementation in pblSet.c.
        /// </summary>
        [Serializable]
        private sealed class AvlTreeNode
        {
            internal KeyValuePair<TKey, TValue> item;
            internal AvlTreeNode prev;
            internal AvlTreeNode next;
            internal AvlTreeNode parent;
            private int balance;

            internal AvlTreeNode(KeyValuePair<TKey, TValue> item)
            {
                this.item = item;
                this.prev = null;
                this.next = null;
                this.parent = null;
                this.balance = 0;
            }

            /*
             * Returns the first node in the tree defined by the node.
             * 
             * @return AvlTreeNode node: The first node in the sub tree.
             */
            internal AvlTreeNode pblTreeNodeFirst()
            {
                AvlTreeNode node = this;
                while (node.prev != null)
                {
                    node = node.prev;
                }
                return node;
            }

            /*
             * Returns the next node after the node.
             *
             * @return AvlTreeNode node: The next node, may be null.
             */
            internal AvlTreeNode pblTreeNodeNext()
            {
                AvlTreeNode node = this;
                if (node.next != null)
                {
                    return node.next.pblTreeNodeFirst();
                }
                else
                {
                    AvlTreeNode child = node;

                    while ((node = node.parent) != null)
                    {
                        if (child == node.prev)
                        {
                            return node;
                        }
                        child = node;
                    }
                }

                return null;
            }

            /*
             * Returns the last node in the tree defined by the node.
             * 
             * @return AvlTreeNode node: The last node in the sub tree.
             */
            internal AvlTreeNode pblTreeNodeLast()
            {
                AvlTreeNode node = this;
                while (node.next != null)
                {
                    node = node.next;
                }
                return node;
            }

            /*
             * Returns the previous node before the node.
             *
             * @return AvlTreeNode node: The previous node, may be null.
             */
            internal AvlTreeNode pblTreeNodePrevious()
            {
                AvlTreeNode node = this;
                if (node.prev != null)
                {
                    return node.prev.pblTreeNodeLast();
                }
                else
                {
                    AvlTreeNode child = node;

                    while ((node = node.parent) != null)
                    {
                        if (child == node.next)
                        {
                            return node;
                        }
                        child = node;
                    }
                }

                return null;
            }

            /*
             * Methods for setting node pointers and maintaining the parentNode pointer
             */
            private void PBL_AVL_TREE_SET_LEFT(AvlTreeNode referenceNode)
            {
                if (this.prev != referenceNode)
                {
                    if ((this.prev = referenceNode) != null) { this.prev.parent = this; }
                }
            }

            private void PBL_AVL_TREE_SET_RIGHT(AvlTreeNode referenceNode)
            {
                if (this.next != referenceNode)
                {
                    if ((this.next = referenceNode) != null) { this.next.parent = this; }
                }
            }


            /*
             * Inserts a new tree node into a tree set
             *
             * @return AvlTreeNode retPtr != null: The subtree p after the insert.
             * @return AvlTreeNode retPtr == null: An error, see pbl_errno:
             *
             * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
             */
            static internal AvlTreeNode pblTreeNodeInsert(
            AvlTreeNode parentNode,              /** The parent node node to insert to   */
            TKey key,                            /** The key to insert                   */
            TValue value,                        /** The value to insert                 */
            out int heightChanged,               /** Set if the tree height changed      */
            out AvlTreeNode node,                /** For returning the node added        */
            out bool nodeAdded                   /** Flag showing whether node was added */
            )
            {
                AvlTreeNode p1;
                AvlTreeNode p2;
                int compareResult;

                if (null == parentNode)
                {
                    /*
                     * Element is not in the tree yet, insert it.
                     */
                    heightChanged = 1;
                    node = new AvlTreeNode(new KeyValuePair<TKey, TValue>(key, value));
                    nodeAdded = true;
                    return node;
                }

                heightChanged = 0;
                nodeAdded = false;

                compareResult = key.CompareTo(parentNode.item.Key);
                if (compareResult == 0)
                {
                    /*
                     * Element already in tree
                     */
                    node = parentNode;
                    return parentNode;
                }

                if (compareResult < 0)
                {
                    /*
                     * Insert into left sub tree
                     */
                    p1 = pblTreeNodeInsert(parentNode.prev, key, value, out heightChanged, out node, out nodeAdded);

                    parentNode.PBL_AVL_TREE_SET_LEFT(p1);

                    if (0 == heightChanged)
                    {
                        return parentNode;
                    }

                    /*
                     * Left sub tree increased in height
                     */
                    if (parentNode.balance == 1)
                    {
                        parentNode.balance = 0;
                        heightChanged = 0;
                        return parentNode;
                    }

                    if (parentNode.balance == 0)
                    {
                        parentNode.balance = -1;
                        return parentNode;
                    }

                    /*
                     * Balancing needed
                     */
                    p1 = parentNode.prev;

                    if (p1.balance == -1)
                    {
                        /*
                         * Simple LL rotation
                         */
                        parentNode.PBL_AVL_TREE_SET_LEFT(p1.next);

                        p1.PBL_AVL_TREE_SET_RIGHT(parentNode);
                        parentNode.balance = 0;

                        parentNode = p1;
                        parentNode.balance = 0;
                        heightChanged = 0;
                        return parentNode;
                    }

                    /*
                     * double LR rotation
                     */
                    p2 = p1.next;

                    p1.PBL_AVL_TREE_SET_RIGHT(p2.prev);

                    p2.PBL_AVL_TREE_SET_LEFT(p1);

                    parentNode.PBL_AVL_TREE_SET_LEFT(p2.next);

                    p2.PBL_AVL_TREE_SET_RIGHT(parentNode);

                    if (p2.balance == -1)
                    {
                        parentNode.balance = 1;
                    }
                    else
                    {
                        parentNode.balance = 0;
                    }

                    if (p2.balance == 1)
                    {
                        p1.balance = -1;
                    }
                    else
                    {
                        p1.balance = 0;
                    }
                    parentNode = p2;
                    parentNode.balance = 0;
                    heightChanged = 0;
                    return parentNode;
                }

                /*
                 * Insert into right sub tree
                 */
                p1 = pblTreeNodeInsert(parentNode.next, key, value, out heightChanged, out node, out nodeAdded);

                parentNode.PBL_AVL_TREE_SET_RIGHT(p1);

                if (0 == heightChanged)
                {
                    return parentNode;
                }

                /*
                 * Right sub tree increased in height
                 */
                if (parentNode.balance == -1)
                {
                    parentNode.balance = 0;
                    heightChanged = 0;
                    return parentNode;
                }

                if (parentNode.balance == 0)
                {
                    parentNode.balance = 1;
                    return parentNode;
                }

                /*
                 * Balancing needed
                 */
                p1 = parentNode.next;

                if (p1.balance == 1)
                {
                    /*
                     * Simple RR rotation
                     */
                    parentNode.PBL_AVL_TREE_SET_RIGHT(p1.prev);

                    p1.PBL_AVL_TREE_SET_LEFT(parentNode);
                    parentNode.balance = 0;

                    parentNode = p1;
                    parentNode.balance = 0;
                    heightChanged = 0;
                    return parentNode;
                }

                /*
                 * double RL rotation
                 */
                p2 = p1.prev;

                p1.PBL_AVL_TREE_SET_LEFT(p2.next);

                p2.PBL_AVL_TREE_SET_RIGHT(p1);

                parentNode.PBL_AVL_TREE_SET_RIGHT(p2.prev);

                p2.PBL_AVL_TREE_SET_LEFT(parentNode);

                if (p2.balance == 1)
                {
                    parentNode.balance = -1;
                }
                else
                {
                    parentNode.balance = 0;
                }

                if (p2.balance == -1)
                {
                    p1.balance = 1;
                }
                else
                {
                    p1.balance = 0;
                }
                parentNode = p2;
                parentNode.balance = 0;
                heightChanged = 0;
                return parentNode;
            }


            /*
             * Balances an AVL tree.
             *
             * Used if left sub tree decreased in size.
             *
             * @return PblTreeNode * retPtr: The subtree p after the balance.
             *
             */
            private AvlTreeNode pblTreeNodeBalanceLeft(
            out int heightChanged                     /** Set if the tree height changed */
            )
            {
                AvlTreeNode p1;
                AvlTreeNode p2;
                int b1;
                int b2;

                heightChanged = 1;

                if (this.balance == -1)
                {
                    this.balance = 0;
                    return this;
                }

                if (this.balance == 0)
                {
                    this.balance = 1;
                    heightChanged = 0;
                    return this;
                }

                /*
                 * Balancing needed
                 */
                p1 = this.next;
                b1 = p1.balance;

                if (b1 >= 0)
                {
                    /*
                     * Simple RR rotation
                     */
                    this.PBL_AVL_TREE_SET_RIGHT(p1.prev);

                    p1.PBL_AVL_TREE_SET_LEFT(this);

                    if (b1 == 0)
                    {
                        this.balance = 1;
                        p1.balance = -1;
                        heightChanged = 0;
                    }
                    else
                    {
                        this.balance = 0;
                        p1.balance = 0;
                    }
                    return p1;
                }

                /*
                 * double RL rotation
                 */
                p2 = p1.prev;
                b2 = p2.balance;

                p1.PBL_AVL_TREE_SET_LEFT(p2.next);

                p2.PBL_AVL_TREE_SET_RIGHT(p1);

                this.PBL_AVL_TREE_SET_RIGHT(p2.prev);

                p2.PBL_AVL_TREE_SET_LEFT(this);

                if (b2 == 1)
                {
                    this.balance = -1;
                }
                else
                {
                    this.balance = 0;
                }

                if (b2 == -1)
                {
                    p1.balance = 1;
                }
                else
                {
                    p1.balance = 0;
                }

                p2.balance = 0;
                return p2;
            }

            /*
             * Balances an AVL tree.
             *
             * Used if right sub tree decreased in size.
             *
             * @return PblTreeNode * retPtr: The subtree p after the balance.
             *
             */
            private AvlTreeNode pblTreeNodeBalanceRight(
            out int heightChanged                     /** Set if the tree height changed */
            )
            {
                AvlTreeNode p1;
                AvlTreeNode p2;
                int b1;
                int b2;

                heightChanged = 1;

                if (this.balance == 1)
                {
                    this.balance = 0;
                    return this;
                }

                if (this.balance == 0)
                {
                    this.balance = -1;
                    heightChanged = 0;
                    return this;
                }

                /*
                 * Balancing needed
                 */
                p1 = this.prev;
                b1 = p1.balance;

                if (b1 <= 0)
                {
                    /*
                     * Simple LL rotation
                     */
                    this.PBL_AVL_TREE_SET_LEFT(p1.next);

                    p1.PBL_AVL_TREE_SET_RIGHT(this);

                    if (b1 == 0)
                    {
                        this.balance = -1;
                        p1.balance = 1;
                        heightChanged = 0;
                    }
                    else
                    {
                        this.balance = 0;
                        p1.balance = 0;
                    }
                    return p1;
                }

                /*
                 * double LR rotation
                 */
                p2 = p1.next;
                b2 = p2.balance;

                p1.PBL_AVL_TREE_SET_RIGHT(p2.prev);

                p2.PBL_AVL_TREE_SET_LEFT(p1);

                this.PBL_AVL_TREE_SET_LEFT(p2.next);

                p2.PBL_AVL_TREE_SET_RIGHT(this);

                if (b2 == -1)
                {
                    this.balance = 1;
                }
                else
                {
                    this.balance = 0;
                }

                if (b2 == 1)
                {
                    p1.balance = -1;
                }
                else
                {
                    p1.balance = 0;
                }

                p2.balance = 0;
                return p2;
            }

            /*
             * Helper function for AVL tree remove.
             *
             * @return PblTreeNode * retPtr: The subtree p after the remove.
             */
            private AvlTreeNode pblTreeNodeRemove2(
            AvlTreeNode q,
            out int heightChanged,
            out bool nodeRemoved
            )
            {
                AvlTreeNode r = this;
                AvlTreeNode p;

                if (null != r.next)
                {
                    p = r.next.pblTreeNodeRemove2(q, out heightChanged, out nodeRemoved);
                    r.PBL_AVL_TREE_SET_RIGHT(p);
                    if (0 != heightChanged)
                    {
                        r = r.pblTreeNodeBalanceRight(out heightChanged);
                    }
                    return r;
                }

                q.item = r.item;
                p = r.prev;

                heightChanged = 1;
                nodeRemoved = true;

                return p;
            }


            /*
             * Removes a tree node from a tree set
             *
             * @return PblTreeNode * retPtr: The subtree p after the remove.
             */
            internal AvlTreeNode pblTreeNodeRemove(
            TKey key,                               /** The element to remove            */
            out int heightChanged,               /** Set if the tree height changed   */
            out bool nodeRemoved                 /** Showing whether node was removed */
            )
            {
                AvlTreeNode p = this;
                AvlTreeNode q = null;
                AvlTreeNode p1;
                int compareResult;

                heightChanged = 0;
                nodeRemoved = false;

                compareResult = key.CompareTo(p.item.Key);

                if (compareResult < 0)
                {
                    if (null != p.prev)
                    {
                        q = p.prev.pblTreeNodeRemove(key, out heightChanged, out nodeRemoved);
                    }
                    p.PBL_AVL_TREE_SET_LEFT(q);

                    if (0 != heightChanged)
                    {
                        p = p.pblTreeNodeBalanceLeft(out heightChanged);
                    }
                    return p;
                }

                if (compareResult > 0)
                {
                    if (null != p.next)
                    {
                        q = p.next.pblTreeNodeRemove(key, out heightChanged, out nodeRemoved);
                    }
                    p.PBL_AVL_TREE_SET_RIGHT(q);

                    if (0 != heightChanged)
                    {
                        p = p.pblTreeNodeBalanceRight(out heightChanged);
                    }
                    return p;
                }

                /*
                 * p is the node that needs to be removed!
                 */
                q = p;

                if (null == q.next)
                {
                    p = q.prev;
                    heightChanged = 1;

                    nodeRemoved = true;
                }
                else if (null == q.prev)
                {
                    p = q.next;
                    heightChanged = 1;

                    nodeRemoved = true;
                }
                else
                {
                    /*
                     * Replace q with is biggest predecessor and remove that
                     */
                    p1 = q.prev.pblTreeNodeRemove2(q, out heightChanged, out nodeRemoved);
                    q.PBL_AVL_TREE_SET_LEFT(p1);

                    if (0 != heightChanged)
                    {
                        p = p.pblTreeNodeBalanceLeft(out heightChanged);
                    }
                }

                return p;
            }
        }

        /// <summary>
        /// Represents the collection of keys in an AvlDictionary&lt;TKey,TValue&gt;. 
        /// This class cannot be inherited.
        /// </summary>
        [Serializable]
        public sealed class KeyCollection : ICollection<TKey>, ICollection
        {
            /// <summary>
            /// Enumerates the elements of an AvlDictionary&lt;TKey,TValue&gt;.KeyCollection. 
            /// This class cannot be inherited.
            /// </summary>

            public sealed class Enumerator : AvlDictionaryBaseEnumerator, System.Collections.Generic.IEnumerator<TKey>
            {
                /// <summary>
                /// Creates a new enumerator of the AvlDictionary&lt;TKey,TValue&gt;.KeyCollection.
                /// </summary>
                /// <param name="dictionary">
                /// The AvlDictionary&lt;TKey,TValue&gt; the enumerator is created for.
                /// </param>

                public Enumerator(AvlDictionary<TKey, TValue> dictionary)
                    : base(dictionary)
                {
                }

                #region IEnumerator<TKey> Member

                /// <summary>
                /// Gets the key at the current position of the enumerator.
                /// </summary>
                /// <returns>
                /// The key in the AvlDictionary&lt;TKey,TValue&gt;.KeyCollection at the current position of the enumerator.
                /// </returns>

                public TKey Current
                {
                    get
                    {
                        return this.CurrentKey;
                    }
                }

                #endregion


                #region IEnumerator Member

                /// <summary>
                /// Gets the key at the current position of the enumerator.
                /// </summary>
                /// <returns>
                /// The key in the AvlDictionary&lt;TKey,TValue&gt;.KeyCollection at the current position of the enumerator.
                /// </returns>

                object IEnumerator.Current
                {
                    get
                    {
                        return this.CurrentKey;
                    }
                }

                #endregion
            }

            private AvlDictionary<TKey, TValue> _AvlDictionary;

            internal KeyCollection(AvlDictionary<TKey, TValue> avlDictionary)
            {
                _AvlDictionary = avlDictionary;
            }

            #region ICollection<TKey> Member

            /// <summary>
            /// Because the KeyCollection is read only, this method always throws a System.NotSupportedException.
            /// </summary>
            /// <exception cref="System.NotSupportedException">
            /// The AvlDictionary.KeyCollection is read-only.
            /// </exception>    

            public void Add(TKey item)
            {
                throw new NotSupportedException("The AvlDictionary.KeyCollection is read-only.");
            }

            /// <summary>
            /// Because the KeyCollection is read only, this method always throws a System.NotSupportedException.
            /// </summary>
            /// <exception cref="System.NotSupportedException">
            /// The AvlDictionary.KeyCollection is read-only.
            /// </exception>    

            public void Clear()
            {
                throw new NotSupportedException("The AvlDictionary.KeyCollection is read-only.");
            }

            /// <summary>
            /// Determines whether the AvlDictionary.KeyCollection contains a specific item.
            /// </summary>
            /// <param name="item">
            /// The TKey to locate in the AvlDictionary.KeyCollection.
            /// </param>
            /// <remarks>
            /// This method is an O(log N) operation, where N is the number of elements in the AvlDictionary.KeyCollection.
            /// </remarks>
            /// <returns>
            /// true if item is found in the AvlDictionary.KeyCollection; otherwise, false.
            /// </returns>

            public bool Contains(TKey item)
            {
                return _AvlDictionary.ContainsKey(item);
            }

            /// <summary>
            /// Copies the elements of the AvlDictionary.KeyCollection to an existing 
            /// one-dimensional TKey[], starting at the specified array index.
            /// </summary>
            /// <param name="array">
            /// The one-dimensional TKey[] that is the destination of the elements
            /// copied from AvlDictionary.KeyCollection.
            /// The array must have zero-based indexing.
            /// </param>
            /// <param name="arrayIndex">
            /// The zero-based index in array at which copying begins.
            /// </param>
            /// <exception cref="System.ArgumentNullException">
            /// array is null.
            /// </exception>    
            /// <exception cref="System.ArgumentOutOfRangeException">
            /// arrayIndex is less than zero.
            /// </exception>    
            /// <exception cref="System.ArgumentException">
            /// arrayIndex is equal to or greater than the length of array.  -or- The number of
            /// elements in the source AvlDictionary.KeyCollection
            /// is greater than the available space from arrayIndex to the end of the destination
            /// array.
            /// </exception>    

            public void CopyTo(TKey[] array, int arrayIndex)
            {
                if (array == null)
                {
                    throw new System.ArgumentNullException("array is null.");
                }
                if (arrayIndex < 0)
                {
                    throw new System.ArgumentOutOfRangeException("arrayIndex is less than zero.");
                }
                if (arrayIndex >= array.Length)
                {
                    throw new System.ArgumentException("arrayIndex is equal to or greater than the length of array.");
                }

                if (_AvlDictionary.Size == 0)
                {
                    return;
                }

                if (arrayIndex + _AvlDictionary.Size > array.Length)
                {
                    throw new System.ArgumentException("number of elements in the source AvlDictionary.KeyCollection is greater than the available space from arrayIndex to the end of the destination array.");
                }

                IEnumerator<TKey> en = GetEnumerator();
                for (int i = 0; en.MoveNext(); i++)
                {
                    array[i + arrayIndex] = en.Current;
                }
            }

            /// <summary>
            /// Gets the number of elements contained in the AvlDictionary.
            /// </summary>
            /// <returns>
            /// The number of elements contained in the AvlDictionary.
            /// Retrieving the value of this property is an O(1) operation.
            /// </returns>

            public int Count
            {
                get { return _AvlDictionary.Count; }
            }

            /// <summary>
            /// Gets a value indicating whether the AvlDictionary.KeyCollection is read-only.
            /// </summary>
            /// <returns>
            /// true.
            /// </returns>

            public bool IsReadOnly
            {
                get { return true; }
            }

            /// <summary>
            /// Because the KeyCollection is read only, this method always throws a System.NotSupportedException.
            /// </summary>
            /// <exception cref="System.NotSupportedException">
            /// The AvlDictionary.KeyCollection is read-only.
            /// </exception>    

            public bool Remove(TKey item)
            {
                throw new NotSupportedException("The AvlDictionary.KeyCollection is read-only.");
            }

            #endregion

            #region IEnumerable<TKey> Member

            /// <summary>
            /// Returns an enumerator that iterates through the AvlDictionary.KeyCollection.
            /// </summary>
            /// <returns>
            /// An IEnumerator&lt;TKey&gt; enumerator for the AvlDictionary.KeyCollection.
            /// </returns>

            public IEnumerator<TKey> GetEnumerator()
            {
                return new Enumerator(_AvlDictionary);
            }

            #endregion

            #region IEnumerable Member

            /// <summary>
            /// Returns an enumerator that iterates through the AvlDictionary.KeyCollection.
            /// </summary>
            /// <returns>
            /// An IEnumerator&lt;TKey&gt; enumerator for the AvlDictionary.KeyCollection.
            /// </returns>

            IEnumerator IEnumerable.GetEnumerator()
            {
                return new Enumerator(_AvlDictionary);
            }

            #endregion

            #region ICollection Member

            /// <summary>
            /// Copies the elements of the AvlDictionary.KeyCollection to an existing 
            /// one-dimensional Array, starting at the specified array index.
            /// </summary>
            /// <param name="array">
            /// The one-dimensional Array that is the destination of the elements
            /// copied from AvlDictionary.KeyCollection.
            /// The array must have zero-based indexing.
            /// </param>
            /// <param name="index">
            /// The zero-based index in array at which copying begins.
            /// </param>
            /// <exception cref="System.ArgumentNullException">
            /// array is null.
            /// </exception>    
            /// <exception cref="System.ArgumentOutOfRangeException">
            /// index is less than zero.
            /// </exception>    
            /// <exception cref="System.ArgumentException">
            /// index is equal to or greater than the length of array.  -or- The number of
            /// elements in the source AvlDictionary.KeyCollection
            /// is greater than the available space from index to the end of the destination
            /// array.
            /// </exception>    

            public void CopyTo(Array array, int index)
            {
                if (array == null)
                {
                    throw new System.ArgumentNullException("array is null.");
                }
                if (index < 0)
                {
                    throw new System.ArgumentOutOfRangeException("index is less than zero.");
                }
                if (index >= array.Length)
                {
                    throw new System.ArgumentException("index is equal to or greater than the length of array.");
                }

                if (Count == 0)
                {
                    return;
                }

                if (index + Count > array.Length)
                {
                    throw new System.ArgumentException("number of elements in the source AvlDictionary.KeyCollection is greater than the available space from index to the end of the destination array.");
                }

                IEnumerator<TKey> en = GetEnumerator();
                for (int i = 0; en.MoveNext(); i++)
                {
                    array.SetValue(en.Current, i + index);
                }
            }

            /// <summary>
            /// Gets a value indicating whether access to the AvlDictionary.KeyCollection is synchronized (thread safe).
            /// </summary>
            /// <returns>
            /// false.
            /// </returns>

            public bool IsSynchronized
            {
                get { return false; }
            }

            /// <summary>
            /// Gets an object that can be used to synchronize access to the AvlDictionary.
            /// </summary>
            /// <returns>
            /// An object that can be used to synchronize access to the AvlDictionary.
            /// </returns>

            public object SyncRoot
            {
                get { return _AvlDictionary._Lock; }
            }

            #endregion
        }

        /// <summary>
        /// Represents the collection of values in an AvlDictionary&lt;TKey,TValue&gt;. 
        /// This class cannot be inherited.
        /// </summary>
        [Serializable]
        public sealed class ValueCollection : ICollection<TValue>, ICollection
        {
            /// <summary>
            /// Enumerates the elements of an AvlDictionary&lt;TKey,TValue&gt;.ValueCollection. 
            /// This class cannot be inherited.
            /// </summary>
            public sealed class Enumerator : AvlDictionaryBaseEnumerator, System.Collections.Generic.IEnumerator<TValue>
            {
                /// <summary>
                /// Creates a new enumerator of the AvlDictionary&lt;TKey,TValue&gt;.ValueCollection.
                /// </summary>
                /// <param name="dictionary">
                /// The AvlDictionary&lt;TKey,TValue&gt; the enumerator is created for.
                /// </param>

                public Enumerator(AvlDictionary<TKey, TValue> dictionary)
                    : base(dictionary)
                {
                }

                #region IEnumerator<TKey> Member

                /// <summary>
                /// Gets the value at the current position of the enumerator.
                /// </summary>
                /// <returns>
                /// The value in the AvlDictionary&lt;TKey,TValue&gt;.ValueCollection at the current position of the enumerator.
                /// </returns>

                public TValue Current
                {
                    get
                    {
                        return this.CurrentValue;
                    }
                }

                #endregion

                #region IEnumerator Member

                /// <summary>
                /// Gets the value at the current position of the enumerator.
                /// </summary>
                /// <returns>
                /// The value in the AvlDictionary&lt;TKey,TValue&gt;.ValueCollection at the current position of the enumerator.
                /// </returns>

                object IEnumerator.Current
                {
                    get
                    {
                        return this.CurrentValue;
                    }
                }

                #endregion
            }

            private AvlDictionary<TKey, TValue> _AvlDictionary;

            internal ValueCollection(AvlDictionary<TKey, TValue> avlDictionary)
            {
                _AvlDictionary = avlDictionary;
            }

            #region ICollection<TValue> Member

            /// <summary>
            /// Because the ValueCollection is read only, this method always throws a System.NotSupportedException.
            /// </summary>
            /// <exception cref="System.NotSupportedException">
            /// The AvlDictionary.ValueCollection is read-only.
            /// </exception>    

            public void Add(TValue item)
            {
                throw new NotSupportedException("The AvlDictionary.ValueCollection is read-only.");
            }

            /// <summary>
            /// Because the ValueCollection is read only, this method always throws a System.NotSupportedException.
            /// </summary>
            /// <exception cref="System.NotSupportedException">
            /// The AvlDictionary.ValueCollection is read-only.
            /// </exception>    

            public void Clear()
            {
                throw new NotSupportedException("The AvlDictionary.ValueCollection is read-only.");
            }

            /// <summary>
            /// Determines whether the AvlDictionary.ValueCollection contains a specific value.
            /// </summary>
            /// <param name="item">
            /// The TValue to locate in the AvlDictionary.ValueCollection.
            /// </param>
            /// <remarks>
            /// This method is an O(N) operation, where N is the number of elements in the AvlDictionary.ValueCollection.
            /// </remarks>
            /// <returns>
            /// true if item is found in the AvlDictionary.ValueCollection; otherwise, false.
            /// </returns>

            public bool Contains(TValue item)
            {
                if (_AvlDictionary.Size == 0)
                {
                    return false;
                }

                if (item == null)
                {
                    for (IEnumerator<TValue> en = GetEnumerator(); en.MoveNext(); )
                    {
                        if (null == en.Current)
                        {
                            return true;
                        }
                    }
                }
                else
                {
                    for (IEnumerator<TValue> en = GetEnumerator(); en.MoveNext(); )
                    {
                        if (item.Equals(en.Current))
                        {
                            return true;
                        }
                    }
                }
                return false;
            }

            /// <summary>
            /// Copies the elements of the AvlDictionary.ValueCollection to an existing 
            /// one-dimensional TValue[], starting at the specified array index.
            /// </summary>
            /// <param name="array">
            /// The one-dimensional TValue[] that is the destination of the elements
            /// copied from AvlDictionary.ValueCollection.
            /// The array must have zero-based indexing.
            /// </param>
            /// <param name="arrayIndex">
            /// The zero-based index in array at which copying begins.
            /// </param>
            /// <exception cref="System.ArgumentNullException">
            /// array is null.
            /// </exception>    
            /// <exception cref="System.ArgumentOutOfRangeException">
            /// arrayIndex is less than zero.
            /// </exception>    
            /// <exception cref="System.ArgumentException">
            /// arrayIndex is equal to or greater than the length of array.  -or- The number of
            /// elements in the source AvlDictionary.ValueCollection
            /// is greater than the available space from arrayIndex to the end of the destination
            /// array.
            /// </exception>    

            public void CopyTo(TValue[] array, int arrayIndex)
            {
                if (array == null)
                {
                    throw new System.ArgumentNullException("array is null.");
                }
                if (arrayIndex < 0)
                {
                    throw new System.ArgumentOutOfRangeException("arrayIndex is less than zero.");
                }
                if (arrayIndex >= array.Length)
                {
                    throw new System.ArgumentException("arrayIndex is equal to or greater than the length of array.");
                }

                if (_AvlDictionary.Size == 0)
                {
                    return;
                }

                if (arrayIndex + _AvlDictionary.Size > array.Length)
                {
                    throw new System.ArgumentException("number of elements in the source AvlDictionary.ValueCollection is greater than the available space from arrayIndex to the end of the destination array.");
                }

                IEnumerator<TValue> en = GetEnumerator();
                for (int i = 0; en.MoveNext(); i++)
                {
                    array[i + arrayIndex] = en.Current;
                }
            }

            /// <summary>
            /// Gets the number of elements contained in the AvlDictionary.
            /// </summary>
            /// <returns>
            /// The number of elements contained in the AvlDictionary.
            /// Retrieving the value of this property is an O(1) operation.
            /// </returns>

            public int Count
            {
                get { return _AvlDictionary.Count; }
            }

            /// <summary>
            /// Gets a value indicating whether the AvlDictionary.ValueCollection is read-only.
            /// </summary>
            /// <returns>
            /// true.
            /// </returns>

            public bool IsReadOnly
            {
                get { return true; }
            }

            /// <summary>
            /// Because the ValueCollection is read only, this method always throws a System.NotSupportedException.
            /// </summary>
            /// <exception cref="System.NotSupportedException">
            /// The AvlDictionary.ValueCollection is read-only.
            /// </exception>    

            public bool Remove(TValue item)
            {
                throw new NotSupportedException("The AvlDictionary.ValueCollection is read-only.");
            }

            #endregion

            #region IEnumerable<TValue> Member

            /// <summary>
            /// Returns an enumerator that iterates through the AvlDictionary.ValueCollection.
            /// </summary>
            /// <returns>
            /// An IEnumerator&lt;TValue&gt; enumerator for the AvlDictionary.ValueCollection.
            /// </returns>

            public IEnumerator<TValue> GetEnumerator()
            {
                return new Enumerator(_AvlDictionary);
            }

            #endregion

            #region IEnumerable Member

            /// <summary>
            /// Returns an enumerator that iterates through the AvlDictionary.ValueCollection.
            /// </summary>
            /// <returns>
            /// An IEnumerator&lt;TValue&gt; enumerator for the AvlDictionary.ValueCollection.
            /// </returns>

            IEnumerator IEnumerable.GetEnumerator()
            {
                return new Enumerator(_AvlDictionary);
            }

            #endregion

            #region ICollection Member

            /// <summary>
            /// Copies the elements of the AvlDictionary.ValueCollection to an existing 
            /// one-dimensional Array, starting at the specified array index.
            /// </summary>
            /// <param name="array">
            /// The one-dimensional Array that is the destination of the elements
            /// copied from AvlDictionary.ValueCollection.
            /// The array must have zero-based indexing.
            /// </param>
            /// <param name="index">
            /// The zero-based index in array at which copying begins.
            /// </param>
            /// <exception cref="System.ArgumentNullException">
            /// array is null.
            /// </exception>    
            /// <exception cref="System.ArgumentOutOfRangeException">
            /// index is less than zero.
            /// </exception>    
            /// <exception cref="System.ArgumentException">
            /// index is equal to or greater than the length of array.  -or- The number of
            /// elements in the source AvlDictionary.ValueCollection
            /// is greater than the available space from index to the end of the destination
            /// array.
            /// </exception>    

            public void CopyTo(Array array, int index)
            {
                if (array == null)
                {
                    throw new System.ArgumentNullException("array is null.");
                }
                if (index < 0)
                {
                    throw new System.ArgumentOutOfRangeException("index is less than zero.");
                }
                if (index >= array.Length)
                {
                    throw new System.ArgumentException("index is equal to or greater than the length of array.");
                }

                if (Count == 0)
                {
                    return;
                }

                if (index + Count > array.Length)
                {
                    throw new System.ArgumentException("number of elements in the source AvlDictionary.ValueCollection is greater than the available space from index to the end of the destination array.");
                }

                IEnumerator<TValue> en = GetEnumerator();
                for (int i = 0; en.MoveNext(); i++)
                {
                    array.SetValue(en.Current, i + index);
                }
            }

            /// <summary>
            /// Gets a value indicating whether access to the AvlDictionary.ValueCollection is synchronized (thread safe).
            /// </summary>
            /// <returns>
            /// false.
            /// </returns>

            public bool IsSynchronized
            {
                get { return false; }
            }

            /// <summary>
            /// Gets an object that can be used to synchronize access to the AvlDictionary.
            /// </summary>
            /// <returns>
            /// An object that can be used to synchronize access to the AvlDictionary.
            /// </returns>

            public object SyncRoot
            {
                get { return _AvlDictionary._Lock; }
            }

            #endregion
        }

        private AvlTreeNode _RootNode;

        private long _ChangeCounter;

        private object _Lock;

        private int Size { get; set; }

        private KeyCollection _Keys;

        private ValueCollection _Values;

        private AvlTreeNode FindNode(TKey key)
        {
            if (Size == 0)
            {
                return null;
            }

            AvlTreeNode node = _RootNode;
            int compareResult;

            while (node != null)
            {
                compareResult = key.CompareTo(node.item.Key);
                if (compareResult == 0)
                {
                    return node;
                }

                if (compareResult < 0)
                {
                    node = node.prev;
                }
                else
                {
                    node = node.next;
                }
            }
            return null;
        }

        private AvlTreeNode AddNode(TKey key, TValue value, out bool nodeAdded )
        {
            if (key == null)
            {
                throw new ArgumentNullException("key is null.");
            }

            if (IsReadOnly)
            {
                throw new System.NotSupportedException("The AvlDictionary is read-only.");
            }

            int heightChanged;
            AvlTreeNode node;

            AvlTreeNode insertResult = AvlTreeNode.pblTreeNodeInsert(_RootNode, key, value, out heightChanged, out node, out nodeAdded);
            if (!nodeAdded)
            {
                return node;
            }

            Size += 1;
            _ChangeCounter++;

            /*
             * Remember the tree after the insert
             */
            insertResult.parent = null;
            _RootNode = insertResult;
            return node;
        }

        /// <summary>
        /// Initializes a new instance of the AvlDictionary&lt;TKey,TValue&gt; class that is empty.
        /// </summary>
        public AvlDictionary()
        {
            _ChangeCounter = 0;
            _Lock = new object();
            _Keys = new KeyCollection(this);
            _Values = new ValueCollection(this);
        }

        /// <summary>
        /// Initializes a new instance of the AvlDictionary&lt;TKey,TValue&gt;
        /// class that contains elements copied from the specified System.Collections.Generic.IDictionary&lt;TKey,TValue&gt;.
        /// </summary>
        /// <param name="dictionary">
        /// The System.Collections.Generic.IDictionary&lt;TKey,TValue&gt; whose elements are
        /// copied to the new AvlDictionary&lt;TKey,TValue&gt;.
        /// </param>
        /// <remarks>
        /// This method is an O(N * log N) operation, where N is dictionary.Count.
        /// </remarks>
        /// <exception cref="System.ArgumentNullException">
        /// dictionary is null.
        /// </exception>       
        /// <exception cref="System.ArgumentException">
        /// dictionary contains one or more duplicate keys.
        /// </exception>       
        public AvlDictionary(IDictionary<TKey, TValue> dictionary)
            : this()
        {
            if (null == dictionary)
            {
                throw new System.ArgumentNullException("dictionary is null.");
            }

            for (IEnumerator<KeyValuePair<TKey, TValue>> en = dictionary.GetEnumerator(); en.MoveNext(); )
            {
                Add(en.Current);
            }
        }

        #region IDictionary<TKey,TValue> Member

        /// <summary>
        /// Adds the specified key and value to the AvlDictionary.
        /// </summary>
        /// <param name="key">
        /// The key of the element to add.
        /// </param>
        /// <param name="value">
        /// The value of the element to add. The value can be null for reference types.
        /// </param>
        /// <remarks>
        /// This method is an O(log N) operation, where N is the number of elements in the AvlDictionary.
        /// </remarks>
        /// <exception cref="System.ArgumentNullException">
        /// key is null.
        /// </exception>       
        /// <exception cref="System.ArgumentException">
        /// An element with the same key already exists in the AvlDictionary.
        /// </exception>       
        public void Add(TKey key, TValue value)
        {
            bool nodeAdded;
            AddNode(key, value, out nodeAdded);
            if( !nodeAdded )
            {
                throw new ArgumentException(string.Format("An element with the same key '{0}' already exists in the AvlDictionary.", key.ToString()));
            }
        }

        /// <summary>
        /// Determines whether the AvlDictionary contains the specified key.
        /// </summary>
        /// <param name="key">
        /// The key to locate in the AvlDictionary.
        /// </param>
        /// <remarks>
        /// This method is an O(log N) operation, where N is the number of elements in the AvlDictionary.
        /// </remarks>
        /// <returns>
        /// true if the AvlDictionary contains an element with the specified key; otherwise, false.
        /// </returns>
        /// <exception cref="System.ArgumentNullException">
        /// key is null.
        /// </exception>    
        public bool ContainsKey(TKey key)
        {
            return FindNode(key) != null;
        }

        /// <summary>
        /// Gets a collection containing the keys in the AvlDictionary.
        /// </summary>
        /// <returns>
        /// An ICollection&lt;TKey&gt; containing the keys in the AvlDictionary.
        /// </returns>

        public ICollection<TKey> Keys
        {
            get { return _Keys; }
        }

        /// <summary>
        /// Removes the value with the specified key from the AvlDictionary.
        /// </summary>
        /// <param name="key">
        /// The key of the element to remove.
        /// </param>
        /// <remarks>
        /// This method is an O(log N) operation, where N is the number of elements in the AvlDictionary.
        /// </remarks>
        /// <returns>
        /// true if the element is successfully found and removed; otherwise, false.
        /// This method returns false if key is not found in the AvlDictionary.
        /// </returns>
        /// <exception cref="System.ArgumentNullException">
        /// key is null.
        /// </exception>    
        /// <exception cref="System.NotSupportedException">
        /// "The AvlDictionary is read-only."
        /// </exception>    
        public bool Remove(TKey key)
        {
            if (key == null)
            {
                throw new ArgumentNullException("key is null.");
            }

            if (IsReadOnly)
            {
                throw new System.NotSupportedException("The AvlDictionary is read-only.");
            }

            if (null == _RootNode)
            {
                return false;
            }

            int heightChanged;
            bool nodeRemoved;

            AvlTreeNode removeResult = _RootNode.pblTreeNodeRemove(key, out heightChanged, out nodeRemoved);
            if (nodeRemoved)
            {
                Size -= 1;
                _ChangeCounter++;

                /*
                 * Remember the tree after the removal
                 */
                if (removeResult != null)
                {
                    removeResult.parent = null;
                }
                _RootNode = removeResult;
            }

            return nodeRemoved;
        }

        /// <summary>
        /// Gets the value associated with the specified key.
        /// </summary>
        /// <param name="key">
        /// The key of the value to get.
        /// </param>
        /// <param name="value">
        /// When this method returns, contains the value associated with the specified
        /// key, if the key is found; otherwise, the default value for the type of the
        /// value parameter. This parameter is passed uninitialized.
        /// </param>
        /// <remarks>
        /// This method is an O(log N) operation, where N is the number of elements in the AvlDictionary.
        /// </remarks>
        /// <returns>
        /// true if the AvlDictionary contains an
        /// element with the specified key; otherwise, false.
        /// </returns>
        /// <exception cref="System.ArgumentNullException">
        /// key is null.
        /// </exception>    
        public bool TryGetValue(TKey key, out TValue value)
        {
            if (key == null)
            {
                throw new ArgumentNullException("key is null.");
            }

            AvlTreeNode node = FindNode(key);
            if (node == null)
            {
                value = default(TValue);
                return false;
            }

            value = node.item.Value;
            return true;
        }

        /// <summary>
        /// Gets a collection containing the values in the AvlDictionary.
        /// </summary>
        /// <returns>
        /// An ICollection&lt;TValue&gt; containing the values in the AvlDictionary.
        /// </returns>
        public ICollection<TValue> Values
        {
            get { return _Values; }
        }

        /// <summary>
        /// Gets or sets the value associated with the specified key.
        /// </summary>
        /// <param name="key">
        /// The key of the value to get or set.
        /// </param>
        /// <remarks>
        /// This method is an O(log N) operation, where N is the number of elements in the AvlDictionary.
        /// </remarks>
        /// <returns>
        /// The value associated with the specified key. If the specified key is not
        /// found, a get operation throws a System.Collections.Generic.KeyNotFoundException,
        /// and a set operation creates a new element with the specified key.
        /// </returns>
        /// <exception cref="System.ArgumentNullException">
        /// key is null.
        /// </exception>    
        /// <exception cref="System.Collections.Generic.KeyNotFoundException">
        /// The property is retrieved and key does not exist in the collection.
        /// </exception>    
        /// <exception cref="System.Collections.Generic.NotSupportedException">
        /// The property is set and the AvlDictionary is read-only.
        /// </exception>    
        public TValue this[TKey key]
        {
            get
            {
                TValue value;
                if (TryGetValue(key, out value))
                {
                    return value;
                }
                throw new KeyNotFoundException("key does not exist in the collection.");
            }
            set
            {
                if (IsReadOnly)
                {
                    throw new System.NotSupportedException("The AvlDictionary is read-only.");
                }

                bool nodeAdded;
                AvlTreeNode node = AddNode(key, value, out nodeAdded);
                if (!nodeAdded)
                {
                    if (null == value)
                    {
                        if (null != node.item.Value)
                        {
                            node.item = new KeyValuePair<TKey, TValue>(key, value);
                        }
                    }
                    else
                    {
                        if (!value.Equals(node.item.Value))
                        {
                            node.item = new KeyValuePair<TKey, TValue>(key, value);
                        }
                    }
                }
            }
        }

        #endregion

        #region ICollection<KeyValuePair<TKey,TValue>> Member

        /// <summary>
        /// Adds a KeyValuePair&lt;TKey,TValue&gt; to the AvlDictionary.
        /// </summary>
        /// <param name="item">
        /// The KeyValuePair&lt;TKey,TValue&gt; to add to the AvlDictionary.
        /// </param>
        /// <remarks>
        /// This method is an O(log N) operation, where N is the number of elements in the AvlDictionary.
        /// </remarks>
        /// <exception cref="System.NotSupportedException">
        /// The AvlDictionary is read-only.
        /// </exception>    
        /// <exception cref="System.ArgumentException">
        /// An element with the same key already exists in the AvlDictionary.
        /// </exception>    
        public void Add(KeyValuePair<TKey, TValue> item)
        {
            bool nodeAdded;
            AvlTreeNode node = AddNode(item.Key, item.Value, out nodeAdded);
            if (!nodeAdded)
            {
                throw new ArgumentException(string.Format("An element with the same key '{0}' already exists in the AvlDictionary.", item.Key.ToString()));
            }
            node.item = item;
        }

        /// <summary>
        /// Removes all keys and values from the AvlDictionary.
        /// </summary>
        /// <exception cref="System.NotSupportedException">
        /// The AvlDictionary is read-only.
        /// </exception>    
        public void Clear()
        {
            if (IsReadOnly)
            {
                throw new System.NotSupportedException("The AvlDictionary is read-only.");
            }

            _RootNode = null;
            Size = 0;
        }

        /// <summary>
        /// Determines whether the AvlDictionary contains a specific KeyValuePair&lt;TKey,TValue&gt;.
        /// </summary>
        /// <param name="item">
        /// The KeyValuePair&lt;TKey,TValue&gt; to locate in the AvlDictionary.
        /// </param>
        /// <remarks>
        /// This method is an O(log N) operation, where N is the number of elements in the AvlDictionary.
        /// </remarks>
        /// <returns>
        /// true if item is found in the AvlDictionary; otherwise, false.
        /// </returns>
        public bool Contains(KeyValuePair<TKey, TValue> item)
        {
            AvlTreeNode node = FindNode(item.Key);
            if (node == null)
            {
                return false;
            }
            return item.Equals(node.item);
        }

        /// <summary>
        /// Copies the elements of the AvlDictionary to an existing 
        /// one-dimensional KeyValuePair&lt;TKey,TValue&gt;[], starting at the specified array index.
        /// </summary>
        /// <param name="array">
        /// The one-dimensional KeyValuePair&lt;TKey,TValue&gt;[] that is the destination of the elements
        /// copied from AvlDictionary.
        /// The array must have zero-based indexing.
        /// </param>
        /// <param name="arrayIndex">
        /// The zero-based index in array at which copying begins.
        /// </param>
        /// <exception cref="System.ArgumentNullException">
        /// array is null.
        /// </exception>    
        /// <exception cref="System.ArgumentOutOfRangeException">
        /// arrayIndex is less than zero.
        /// </exception>    
        /// <exception cref="System.ArgumentException">
        /// arrayIndex is equal to or greater than the length of array.  -or- The number of
        /// elements in the source AvlDictionary
        /// is greater than the available space from arrayIndex to the end of the destination
        /// array.
        /// </exception>    
        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            if (array == null)
            {
                throw new System.ArgumentNullException("array is null.");
            }
            if (arrayIndex < 0)
            {
                throw new System.ArgumentOutOfRangeException("index is less than zero.");
            }
            if (arrayIndex >= array.Length)
            {
                throw new System.ArgumentException("arrayIndex is equal to or greater than the length of array.");
            }

            if (Size == 0)
            {
                return;
            }

            if (arrayIndex + Size > array.Length)
            {
                throw new System.ArgumentException("number of elements in the source AvlDictionary is greater than the available space from arrayIndex to the end of the destination array.");
            }

            IEnumerator<KeyValuePair<TKey, TValue>> en = GetEnumerator();
            for (int i = 0; en.MoveNext(); i++)
            {
                array[i + arrayIndex] = en.Current;
            }
        }

        /// <summary>
        /// Gets the number of elements contained in the AvlDictionary.
        /// </summary>
        /// <returns>
        /// The number of elements contained in the AvlDictionary.
        /// Retrieving the value of this property is an O(1) operation.
        /// </returns>
        public int Count
        {
            get { return Size; }
        }

        /// <summary>
        /// Gets a value indicating whether the AvlDictionary is read-only.
        /// </summary>
        /// <returns>
        /// false.
        /// </returns>
        public bool IsReadOnly
        {
            get { return false; }
        }

        /// <summary>
        /// Removes the first occurrence of a specific KeyValuePair&lt;TKey,TValue&gt; from the AvlDictionary.
        /// </summary>
        /// <param name="item">
        /// The KeyValuePair&lt;TKey,TValue&gt; to remove from the AvlDictionary.
        /// </param>
        /// <remarks>
        /// This method is an O(log N) operation, where N is the number of elements in the AvlDictionary.
        /// </remarks>
        /// <returns>
        /// true if item was successfully removed from the AvlDictionary;
        /// otherwise, false. This method also returns false if item is not found in
        /// the original AvlDictionary.
        /// </returns>
        /// <exception cref="System.NotSupportedException">
        /// The AvlDictionary is read-only.
        /// </exception>    
        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            if (IsReadOnly)
            {
                throw new System.NotSupportedException("The AvlDictionary is read-only.");
            }

            AvlTreeNode node = FindNode(item.Key);
            if (node == null)
            {
                return false;
            }
            if (item.Equals(node.item))
            {
                Remove(item.Key);
                return true;
            }
            return false;
        }

        #endregion

        #region IEnumerable<KeyValuePair<TKey,TValue>> Member

        /// <summary>
        /// Returns an enumerator that iterates through the AvlDictionary.
        /// </summary>
        /// <returns>
        /// An IEnumerator&lt;KeyValuePair&lt;TKey, TValue&gt;&gt; enumerator for the AvlDictionary.
        /// </returns>
        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return new Enumerator(this);
        }

        #endregion

        #region IEnumerable Member

        /// <summary>
        /// Returns an enumerator that iterates through the AvlDictionary.
        /// </summary>
        /// <returns>
        /// An IEnumerator enumerator for the AvlDictionary.
        /// </returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        #endregion

        #region ICollection Member

        /// <summary>
        /// Copies the elements of the elements of the AvlDictionary to an System.Array, starting at a particular System.Array index.
        /// </summary>
        /// <param name="array">
        /// The one-dimensional System.Array that is the destination of the elements
        /// copied from AvlDictionary. The System.Array must have zero-based
        /// indexing.
        /// </param>
        /// <param name="index">
        /// The zero-based index in array at which copying begins.
        /// </param>
        /// <exception cref="System.ArgumentNullException">
        /// array is null.
        /// </exception>    
        /// <exception cref="System.ArgumentOutOfRangeException">
        /// index is less than zero.
        /// </exception>    
        /// <exception cref="System.ArgumentException">
        /// array is multidimensional.  -or- index is equal to or greater than the length
        /// of array.  -or- The number of elements in the source AvlDictionary
        /// is greater than the available space from index to the end of the destination
        /// array.
        /// </exception>    
        public void CopyTo(Array array, int index)
        {
            if (array == null)
            {
                throw new System.ArgumentNullException("array is null.");
            }
            if (index < 0)
            {
                throw new System.ArgumentOutOfRangeException("index is less than zero.");
            }
            if (index >= array.Length)
            {
                throw new System.ArgumentException("index is equal to or greater than the length of array.");
            }

            if (Size == 0)
            {
                return;
            }

            if (index + Size > array.Length)
            {
                throw new System.ArgumentException("number of elements in the source AvlDictionary is greater than the available space from index to the end of the destination array.");
            }

            IEnumerator<KeyValuePair<TKey, TValue>> en = GetEnumerator();
            for (int i = 0; en.MoveNext(); i++)
            {
                array.SetValue(en.Current, i + index);
            }
        }

        /// <summary>
        /// Gets a value indicating whether access to the AvlDictionary is synchronized (thread safe).
        /// </summary>
        /// <returns>
        /// false.
        /// </returns>
        public bool IsSynchronized
        {
            get { return false; }
        }

        /// <summary>
        /// Gets an object that can be used to synchronize access to the AvlDictionary.
        /// </summary>
        /// <returns>
        /// An object that can be used to synchronize access to the AvlDictionary.
        /// </returns>
        public object SyncRoot
        {
            get { return _Lock; }
        }

        #endregion
    }
}