AvlDictionary - Eine C# Avl-Tree basierte generic IDictionary<TKey,TValue> Implementierung.

Beschreibung:

AvlDictionary - Eine C# Avl-Tree basierte generic IDictionary<TKey,TValue> Implementierung.
Dokumentation zu der Klasse und einen Speicher- und Zeitvergleich zu den Standardklassen Dictionary, SortedDictionary und SortedList gibt es unter

http://www.mission-base.com/peter/source/AvlDictionary/

/*
 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: [URL]http://www.mission-base.com/[/URL].

 $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
    }
}

Schlagwörter: Generic IDictionary, AVL, Dictionary, Tree, Balanced Tree, SortedDictionary, SortedList, Collection

Find ich toll.

Gewaltig groß und sicher kompliziert, aber extrem toll =].
Vor allem findet man so mächtige Snippets für .NET eher selten unter der GPL.

Was mich allerdings stutzig macht sind die statischen Methoden, pblTreeNodeInsert zum Beispiel. Wieso sind die statisch, wenn ich fragen darf?

Hallo Emiswelt,

den eigentlichen avl-tree code hatte ich mit moeglichst wenig Aufwand von einer
frueheren C Implemetierung portiert. Nachdem C keine Objekte kennt wurden
eben statische Methoden draus.

Nachdem das C# Interface extern sauber objektorientiert ist und ich andererseits weiss,
dass der C Code alt und viel getestet ist, war es mir fuer die Internas wichtiger nahe am C
zu bleiben, als alles auf Objekte umzuheben.

siehe
http://www.mission-base.com/peter/source/pbl/doc/set.html
und
http://www.mission-base.com/peter/source/pbl/pblSet.c

Gruesse

Peter