AvlDictionary.cs

Go to the documentation of this file.

/*
 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: https://www.mission-base.com/.

 $Log: AvlDictionary.cs,v $
 Revision 1.2  2012/12/11 00:42:34  peter
 Removed some warnings

 Revision 1.1  2009/11/26 18:56:32  peter
 Initial


 */

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

namespace Com.Mission_Base.Pbl
{
    [Serializable]
    [ComVisible(false)]
    [DebuggerDisplay("Count = {Count}")]
    public class AvlDictionary<TKey, TValue> :
        IDictionary<TKey, TValue>,
        ICollection
        where TKey : IComparable<TKey>
    {
        public class AvlDictionaryBaseEnumerator
        {
            private readonly AvlDictionary<TKey, TValue> _avlDictionary;
            private AvlTreeNode _node;
            private bool _isExhausted;
            private readonly long _changeCounter;


            protected AvlDictionaryBaseEnumerator(AvlDictionary<TKey, TValue> dictionary)
            {
                _avlDictionary = dictionary;
                _changeCounter = dictionary._changeCounter;
                _node = null;
                _isExhausted = _avlDictionary._rootNode == null;
            }


            protected bool IsPositioned
            {
                get { return !_isExhausted && null != _node; }
            }


            protected KeyValuePair<TKey, TValue> CurrentPair
            {
                get
                {
                    if (!_isExhausted && null != _node)
                    {
                        return _node.Pair;
                    }
                    return new KeyValuePair<TKey, TValue>(default(TKey), default(TValue));
                }
            }


            protected TKey CurrentKey
            {
                get
                {
                    if (!_isExhausted && null != _node)
                    {
                        return _node.Pair.Key;
                    }
                    return default(TKey);
                }
            }


            protected TValue CurrentValue
            {
                get
                {
                    if (!_isExhausted && null != _node)
                    {
                        return _node.Pair.Value;
                    }
                    return default(TValue);
                }
            }

            //  if the enumerator has passed the end of the collection.
            public bool MoveNext()
            {
                if (_changeCounter != _avlDictionary._changeCounter)
                {
                    throw new InvalidOperationException("The AvlDictionary was modified after the enumerator was created.");
                }
                if (_isExhausted)
                {
                    return false;
                }
                if (null == _avlDictionary._rootNode)
                {
                    _isExhausted = true;
                    return false;
                }

                AvlTreeNode next = null == _node ? _avlDictionary._rootNode.PblTreeNodeFirst() : _node.PblTreeNodeNext();
                if (null == next)
                {
                    _isExhausted = true;
                    return false;
                }
                _node = next;

                return true;
            }


            public void Reset()
            {
                _node = null;
                _isExhausted = _avlDictionary._rootNode == null;
            }

            #region IDisposable Member


            public void Dispose()
            {
            }

            #endregion
        }

        public sealed class Enumerator : AvlDictionaryBaseEnumerator, IEnumerator<KeyValuePair<TKey, TValue>>
        {

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

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


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

            #endregion

            #region IEnumerator Member


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

            #endregion
        }

        [Serializable]
        private sealed class AvlTreeNode
        {
            internal KeyValuePair<TKey, TValue> Pair;
            internal AvlTreeNode Prev;
            internal AvlTreeNode Next;
            internal AvlTreeNode Parent;
            private int _balance;

            private AvlTreeNode(KeyValuePair<TKey, TValue> pair)
            {
                Pair = pair;
                Prev = null;
                Next = null;
                Parent = null;
                _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;
            }

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

            private void PblAvlTreeSetRight(AvlTreeNode referenceNode)
            {
                if (Next != referenceNode)
                {
                    if ((Next = referenceNode) != null) { 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,              
            TKey key,                            
            TValue value,                        
            out int heightChanged,               
            out AvlTreeNode node,                
            out bool nodeAdded                   
            )
            {
                AvlTreeNode p1;
                AvlTreeNode p2;

                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;

                int compareResult = key.CompareTo(parentNode.Pair.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.PblAvlTreeSetLeft(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.PblAvlTreeSetLeft(p1.Next);

                        p1.PblAvlTreeSetRight(parentNode);
                        parentNode._balance = 0;

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

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

                    p1.PblAvlTreeSetRight(p2.Prev);

                    p2.PblAvlTreeSetLeft(p1);

                    parentNode.PblAvlTreeSetLeft(p2.Next);

                    p2.PblAvlTreeSetRight(parentNode);

                    parentNode._balance = p2._balance == -1 ? 1 : 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.PblAvlTreeSetRight(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.PblAvlTreeSetRight(p1.Prev);

                    p1.PblAvlTreeSetLeft(parentNode);
                    parentNode._balance = 0;

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

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

                p1.PblAvlTreeSetLeft(p2.Next);

                p2.PblAvlTreeSetRight(p1);

                parentNode.PblAvlTreeSetRight(p2.Prev);

                p2.PblAvlTreeSetLeft(parentNode);

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

                p1._balance = p2._balance == -1 ? 1 : 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                     
            )
            {
                heightChanged = 1;

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

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

                /*
                 * Balancing needed
                 */
                AvlTreeNode p1 = Next;
                int b1 = p1._balance;

                if (b1 >= 0)
                {
                    /*
                     * Simple RR rotation
                     */
                    PblAvlTreeSetRight(p1.Prev);

                    p1.PblAvlTreeSetLeft(this);

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

                /*
                 * double RL rotation
                 */
                AvlTreeNode p2 = p1.Prev;
                int b2 = p2._balance;

                p1.PblAvlTreeSetLeft(p2.Next);

                p2.PblAvlTreeSetRight(p1);

                PblAvlTreeSetRight(p2.Prev);

                p2.PblAvlTreeSetLeft(this);

                if (b2 == 1)
                {
                    _balance = -1;
                }
                else
                {
                    _balance = 0;
                }

                p1._balance = b2 == -1 ? 1 : 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                     
            )
            {
                heightChanged = 1;

                if (_balance == 1)
                {
                    _balance = 0;
                    return this;
                }

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

                /*
                 * Balancing needed
                 */
                AvlTreeNode p1 = Prev;
                int b1 = p1._balance;

                if (b1 <= 0)
                {
                    /*
                     * Simple LL rotation
                     */
                    PblAvlTreeSetLeft(p1.Next);

                    p1.PblAvlTreeSetRight(this);

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

                /*
                 * double LR rotation
                 */
                AvlTreeNode p2 = p1.Next;
                int b2 = p2._balance;

                p1.PblAvlTreeSetRight(p2.Prev);

                p2.PblAvlTreeSetLeft(p1);

                PblAvlTreeSetLeft(p2.Next);

                p2.PblAvlTreeSetRight(this);

                _balance = b2 == -1 ? 1 : 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.PblAvlTreeSetRight(p);
                    if (0 != heightChanged)
                    {
                        r = r.PblTreeNodeBalanceRight(out heightChanged);
                    }
                    return r;
                }

                q.Pair = r.Pair;
                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,                               
            out int heightChanged,               
            out bool nodeRemoved                 
            )
            {
                AvlTreeNode p = this;
                AvlTreeNode q = null;

                heightChanged = 0;
                nodeRemoved = false;

                int compareResult = key.CompareTo(p.Pair.Key);

                if (compareResult < 0)
                {
                    if (null != p.Prev)
                    {
                        q = p.Prev.PblTreeNodeRemove(key, out heightChanged, out nodeRemoved);
                    }
                    p.PblAvlTreeSetLeft(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.PblAvlTreeSetRight(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
                     */
                    AvlTreeNode p1 = q.Prev.PblTreeNodeRemove2(q, out heightChanged, out nodeRemoved);
                    q.PblAvlTreeSetLeft(p1);

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

                return p;
            }
        }

        [Serializable]
        public sealed class KeyCollection : ICollection<TKey>, ICollection
        {

            public sealed class CollectionEnumerator : AvlDictionaryBaseEnumerator, IEnumerator<TKey>
            {

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

                #region IEnumerator<TKey> Member


                public TKey Current
                {
                    get
                    {
                        return CurrentKey;
                    }
                }

                #endregion


                #region IEnumerator Member


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

                #endregion
            }

            private readonly AvlDictionary<TKey, TValue> _avlDictionary;

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

            #region ICollection<TKey> Member


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


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


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


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

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

                if (index + _avlDictionary.Size > array.Length)
                {
                    throw new 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[i + index] = en.Current;
                }
            }


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


            public bool IsReadOnly
            {
                get { return true; }
            }


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

            #endregion

            #region IEnumerable<TKey> Member


            public IEnumerator<TKey> GetEnumerator()
            {
                return new CollectionEnumerator(_avlDictionary);
            }

            #endregion

            #region IEnumerable Member


            IEnumerator IEnumerable.GetEnumerator()
            {
                return new CollectionEnumerator(_avlDictionary);
            }

            #endregion

            #region ICollection Member


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

                if (Count == 0)
                {
                    return;
                }

                if (index + Count > array.Length)
                {
                    throw new 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);
                }
            }


            public bool IsSynchronized
            {
                get { return false; }
            }


            public object SyncRoot
            {
                get { return _avlDictionary._lock; }
            }

            #endregion
        }

        [Serializable]
        public sealed class ValueCollection : ICollection<TValue>, ICollection
        {
            public sealed class CollectionEnumerator : AvlDictionaryBaseEnumerator, IEnumerator<TValue>
            {

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

                #region IEnumerator<TKey> Member


                public TValue Current
                {
                    get
                    {
                        return CurrentValue;
                    }
                }

                #endregion

                #region IEnumerator Member


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

                #endregion
            }

            private readonly AvlDictionary<TKey, TValue> _avlDictionary;

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

            #region ICollection<TValue> Member


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


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


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


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

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

                if (index + _avlDictionary.Size > array.Length)
                {
                    throw new 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[i + index] = en.Current;
                }
            }


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


            public bool IsReadOnly
            {
                get { return true; }
            }


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

            #endregion

            #region IEnumerable<TValue> Member


            public IEnumerator<TValue> GetEnumerator()
            {
                return new CollectionEnumerator(_avlDictionary);
            }

            #endregion

            #region IEnumerable Member


            IEnumerator IEnumerable.GetEnumerator()
            {
                return new CollectionEnumerator(_avlDictionary);
            }

            #endregion

            #region ICollection Member


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

                if (Count == 0)
                {
                    return;
                }

                if (index + Count > array.Length)
                {
                    throw new 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);
                }
            }


            public bool IsSynchronized
            {
                get { return false; }
            }


            public object SyncRoot
            {
                get { return _avlDictionary._lock; }
            }

            #endregion
        }

        private AvlTreeNode _rootNode;

        private long _changeCounter;

        private readonly object _lock;

        private int Size { get; set; }

        private readonly KeyCollection _keys;

        private readonly ValueCollection _values;

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

            AvlTreeNode node = _rootNode;

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

                node = compareResult < 0 ? node.Prev : node.Next;
            }
            return null;
        }

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

            if (IsReadOnly)
            {
                throw new 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;
        }

        public AvlDictionary()
        {
            _changeCounter = 0;
            _lock = new object();
            _keys = new KeyCollection(this);
            _values = new ValueCollection(this);
        }

        public AvlDictionary(IEnumerable<KeyValuePair<TKey, TValue>> dictionary)
            : this()
        {
            if (null == dictionary)
            {
                throw new ArgumentNullException("dictionary");
            }

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

        #region IDictionary<TKey,TValue> Member

        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));
            }
        }

        public bool ContainsKey(TKey key)
        {
            return FindNode(key) != null;
        }


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

        public bool Remove(TKey key)
        {
            if (key == null)
            {
                throw new ArgumentNullException("key");
            }

            if (IsReadOnly)
            {
                throw new 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;
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            if (key == null)
            {
                throw new ArgumentNullException("key");
            }

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

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

        public ICollection<TValue> Values
        {
            get { return _values; }
        }

        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 NotSupportedException("The AvlDictionary is read-only.");
                }

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

        #endregion

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

        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));
            }
            node.Pair = item;
        }

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

            _rootNode = null;
            Size = 0;
        }

        public bool Contains(KeyValuePair<TKey, TValue> item)
        {
            AvlTreeNode node = FindNode(item.Key);
            if (node == null)
            {
                return false;
            }
            return item.Equals(node.Pair);
        }

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

            if (Size == 0)
            {
                return;
            }

            if (index + Size > array.Length)
            {
                throw new 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[i + index] = en.Current;
            }
        }

        public int Count
        {
            get { return Size; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            if (IsReadOnly)
            {
                throw new NotSupportedException("The AvlDictionary is read-only.");
            }

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

        #endregion

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

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            return new Enumerator(this);
        }

        #endregion

        #region IEnumerable Member

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

        #endregion

        #region ICollection Member

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

            if (Size == 0)
            {
                return;
            }

            if (index + Size > array.Length)
            {
                throw new 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);
            }
        }

        public bool IsSynchronized
        {
            get { return false; }
        }

        public object SyncRoot
        {
            get { return _lock; }
        }

        #endregion
    }
}