PBL - The program base library
C# AvlDictionary and Priority Queue implementation
 All Classes Namespaces Files Functions Properties
AvlDictionary.cs
Go to the documentation of this file.
1 /*
2  AvlDictionary.cs - C# implementation of an AVL tree based generic IDictionary<TKey,TValue> interface.
3 
4  Copyright (C) 2009 Peter Graf
5 
6  This file is part of PBL - The Program Base Library.
7  PBL is free software.
8 
9  This library is free software; you can redistribute it and/or
10  modify it under the terms of the GNU Lesser General Public
11  License as published by the Free Software Foundation; either
12  version 2.1 of the License, or (at your option) any later version.
13 
14  This library is distributed in the hope that it will be useful,
15  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17  Lesser General Public License for more details.
18 
19  You should have received a copy of the GNU Lesser General Public
20  License along with this library; if not, write to the Free Software
21  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 
23  For more information on the Program Base Library or Peter Graf,
24  please see: http://www.mission-base.com/.
25 
26  $Log: AvlDictionary.cs,v $
27  Revision 1.2 2012/12/11 00:42:34 peter
28  Removed some warnings
29 
30  Revision 1.1 2009/11/26 18:56:32 peter
31  Initial
32 
33 
34  */
35 
36 using System;
37 using System.Collections;
38 using System.Collections.Generic;
39 using System.Runtime.InteropServices;
40 using System.Diagnostics;
41 
42 namespace Com.Mission_Base.Pbl
43 {
54  [Serializable]
55  [ComVisible(false)]
56  [DebuggerDisplay("Count = {Count}")]
57  public class AvlDictionary<TKey, TValue> :
58  IDictionary<TKey, TValue>,
59  ICollection
60  where TKey : IComparable<TKey>
61  {
65  public class AvlDictionaryBaseEnumerator
66  {
67  private readonly AvlDictionary<TKey, TValue> _avlDictionary;
68  private AvlTreeNode _node;
69  private bool _isExhausted;
70  private readonly long _changeCounter;
71 
78 
79  protected AvlDictionaryBaseEnumerator(AvlDictionary<TKey, TValue> dictionary)
80  {
81  _avlDictionary = dictionary;
82  _changeCounter = dictionary._changeCounter;
83  _node = null;
84  _isExhausted = _avlDictionary._rootNode == null;
85  }
86 
93 
94  protected bool IsPositioned
95  {
96  get { return !_isExhausted && null != _node; }
97  }
98 
105 
106  protected KeyValuePair<TKey, TValue> CurrentPair
107  {
108  get
109  {
110  if (!_isExhausted && null != _node)
111  {
112  return _node.Pair;
113  }
114  return new KeyValuePair<TKey, TValue>(default(TKey), default(TValue));
115  }
116  }
117 
124 
125  protected TKey CurrentKey
126  {
127  get
128  {
129  if (!_isExhausted && null != _node)
130  {
131  return _node.Pair.Key;
132  }
133  return default(TKey);
134  }
135  }
136 
143 
144  protected TValue CurrentValue
145  {
146  get
147  {
148  if (!_isExhausted && null != _node)
149  {
150  return _node.Pair.Value;
151  }
152  return default(TValue);
153  }
154  }
155 
161  // if the enumerator has passed the end of the collection.
166  public bool MoveNext()
167  {
168  if (_changeCounter != _avlDictionary._changeCounter)
169  {
170  throw new InvalidOperationException("The AvlDictionary was modified after the enumerator was created.");
171  }
172  if (_isExhausted)
173  {
174  return false;
175  }
176  if (null == _avlDictionary._rootNode)
177  {
178  _isExhausted = true;
179  return false;
180  }
181 
182  AvlTreeNode next = null == _node ? _avlDictionary._rootNode.PblTreeNodeFirst() : _node.PblTreeNodeNext();
183  if (null == next)
184  {
185  _isExhausted = true;
186  return false;
187  }
188  _node = next;
189 
190  return true;
191  }
192 
196 
197  public void Reset()
198  {
199  _node = null;
200  _isExhausted = _avlDictionary._rootNode == null;
201  }
202 
203  #region IDisposable Member
204 
208 
209  public void Dispose()
210  {
211  }
212 
213  #endregion
214  }
215 
219  public sealed class Enumerator : AvlDictionaryBaseEnumerator, IEnumerator<KeyValuePair<TKey, TValue>>
220  {
227 
228  public Enumerator(AvlDictionary<TKey, TValue> dictionary)
229  : base(dictionary)
230  {
231  }
232 
233  #region IEnumerator<KeyValuePair<TKey,TValue>> Member
234 
241 
242  public KeyValuePair<TKey, TValue> Current
243  {
244  get { return CurrentPair; }
245  }
246 
247  #endregion
248 
249  #region IEnumerator Member
250 
260 
261  object IEnumerator.Current
262  {
263  get
264  {
265  if (!IsPositioned)
266  {
267  throw new InvalidOperationException("The enumerator is not positioned.");
268  }
269  return CurrentPair;
270  }
271  }
272 
273  #endregion
274  }
275 
279  [Serializable]
280  private sealed class AvlTreeNode
281  {
282  internal KeyValuePair<TKey, TValue> Pair;
283  internal AvlTreeNode Prev;
284  internal AvlTreeNode Next;
285  internal AvlTreeNode Parent;
286  private int _balance;
287 
288  private AvlTreeNode(KeyValuePair<TKey, TValue> pair)
289  {
290  Pair = pair;
291  Prev = null;
292  Next = null;
293  Parent = null;
294  _balance = 0;
295  }
296 
297  /*
298  * Returns the first node in the tree defined by the node.
299  *
300  * @return AvlTreeNode node: The first node in the sub tree.
301  */
302  internal AvlTreeNode PblTreeNodeFirst()
303  {
304  AvlTreeNode node = this;
305  while (node.Prev != null)
306  {
307  node = node.Prev;
308  }
309  return node;
310  }
311 
312  /*
313  * Returns the next node after the node.
314  *
315  * @return AvlTreeNode node: The next node, may be null.
316  */
317  internal AvlTreeNode PblTreeNodeNext()
318  {
319  AvlTreeNode node = this;
320  if (node.Next != null)
321  {
322  return node.Next.PblTreeNodeFirst();
323  }
324  else
325  {
326  AvlTreeNode child = node;
327 
328  while ((node = node.Parent) != null)
329  {
330  if (child == node.Prev)
331  {
332  return node;
333  }
334  child = node;
335  }
336  }
337 
338  return null;
339  }
340 
341  /*
342  * Methods for setting node pointers and maintaining the parentNode pointer
343  */
344  private void PblAvlTreeSetLeft(AvlTreeNode referenceNode)
345  {
346  if (Prev != referenceNode)
347  {
348  if ((Prev = referenceNode) != null) { Prev.Parent = this; }
349  }
350  }
351 
352  private void PblAvlTreeSetRight(AvlTreeNode referenceNode)
353  {
354  if (Next != referenceNode)
355  {
356  if ((Next = referenceNode) != null) { Next.Parent = this; }
357  }
358  }
359 
360 
361  /*
362  * Inserts a new tree node into a tree set
363  *
364  * @return AvlTreeNode retPtr != null: The subtree p after the insert.
365  * @return AvlTreeNode retPtr == null: An error, see pbl_errno:
366  *
367  * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
368  */
369  static internal AvlTreeNode PblTreeNodeInsert(
370  AvlTreeNode parentNode,
371  TKey key,
372  TValue value,
373  out int heightChanged,
374  out AvlTreeNode node,
375  out bool nodeAdded
376  )
377  {
378  AvlTreeNode p1;
379  AvlTreeNode p2;
380 
381  if (null == parentNode)
382  {
383  /*
384  * Element is not in the tree yet, insert it.
385  */
386  heightChanged = 1;
387  node = new AvlTreeNode(new KeyValuePair<TKey, TValue>(key, value));
388  nodeAdded = true;
389  return node;
390  }
391 
392  heightChanged = 0;
393  nodeAdded = false;
394 
395  int compareResult = key.CompareTo(parentNode.Pair.Key);
396  if (compareResult == 0)
397  {
398  /*
399  * Element already in tree
400  */
401  node = parentNode;
402  return parentNode;
403  }
404 
405  if (compareResult < 0)
406  {
407  /*
408  * Insert into left sub tree
409  */
410  p1 = PblTreeNodeInsert(parentNode.Prev, key, value, out heightChanged, out node, out nodeAdded);
411 
412  parentNode.PblAvlTreeSetLeft(p1);
413 
414  if (0 == heightChanged)
415  {
416  return parentNode;
417  }
418 
419  /*
420  * Left sub tree increased in height
421  */
422  if (parentNode._balance == 1)
423  {
424  parentNode._balance = 0;
425  heightChanged = 0;
426  return parentNode;
427  }
428 
429  if (parentNode._balance == 0)
430  {
431  parentNode._balance = -1;
432  return parentNode;
433  }
434 
435  /*
436  * Balancing needed
437  */
438  p1 = parentNode.Prev;
439 
440  if (p1._balance == -1)
441  {
442  /*
443  * Simple LL rotation
444  */
445  parentNode.PblAvlTreeSetLeft(p1.Next);
446 
447  p1.PblAvlTreeSetRight(parentNode);
448  parentNode._balance = 0;
449 
450  parentNode = p1;
451  parentNode._balance = 0;
452  heightChanged = 0;
453  return parentNode;
454  }
455 
456  /*
457  * double LR rotation
458  */
459  p2 = p1.Next;
460 
461  p1.PblAvlTreeSetRight(p2.Prev);
462 
463  p2.PblAvlTreeSetLeft(p1);
464 
465  parentNode.PblAvlTreeSetLeft(p2.Next);
466 
467  p2.PblAvlTreeSetRight(parentNode);
468 
469  parentNode._balance = p2._balance == -1 ? 1 : 0;
470 
471  if (p2._balance == 1)
472  {
473  p1._balance = -1;
474  }
475  else
476  {
477  p1._balance = 0;
478  }
479  parentNode = p2;
480  parentNode._balance = 0;
481  heightChanged = 0;
482  return parentNode;
483  }
484 
485  /*
486  * Insert into right sub tree
487  */
488  p1 = PblTreeNodeInsert(parentNode.Next, key, value, out heightChanged, out node, out nodeAdded);
489 
490  parentNode.PblAvlTreeSetRight(p1);
491 
492  if (0 == heightChanged)
493  {
494  return parentNode;
495  }
496 
497  /*
498  * Right sub tree increased in height
499  */
500  if (parentNode._balance == -1)
501  {
502  parentNode._balance = 0;
503  heightChanged = 0;
504  return parentNode;
505  }
506 
507  if (parentNode._balance == 0)
508  {
509  parentNode._balance = 1;
510  return parentNode;
511  }
512 
513  /*
514  * Balancing needed
515  */
516  p1 = parentNode.Next;
517 
518  if (p1._balance == 1)
519  {
520  /*
521  * Simple RR rotation
522  */
523  parentNode.PblAvlTreeSetRight(p1.Prev);
524 
525  p1.PblAvlTreeSetLeft(parentNode);
526  parentNode._balance = 0;
527 
528  parentNode = p1;
529  parentNode._balance = 0;
530  heightChanged = 0;
531  return parentNode;
532  }
533 
534  /*
535  * double RL rotation
536  */
537  p2 = p1.Prev;
538 
539  p1.PblAvlTreeSetLeft(p2.Next);
540 
541  p2.PblAvlTreeSetRight(p1);
542 
543  parentNode.PblAvlTreeSetRight(p2.Prev);
544 
545  p2.PblAvlTreeSetLeft(parentNode);
546 
547  if (p2._balance == 1)
548  {
549  parentNode._balance = -1;
550  }
551  else
552  {
553  parentNode._balance = 0;
554  }
555 
556  p1._balance = p2._balance == -1 ? 1 : 0;
557  parentNode = p2;
558  parentNode._balance = 0;
559  heightChanged = 0;
560  return parentNode;
561  }
562 
563 
564  /*
565  * Balances an AVL tree.
566  *
567  * Used if left sub tree decreased in size.
568  *
569  * @return PblTreeNode * retPtr: The subtree p after the balance.
570  *
571  */
572  private AvlTreeNode PblTreeNodeBalanceLeft(
573  out int heightChanged
574  )
575  {
576  heightChanged = 1;
577 
578  if (_balance == -1)
579  {
580  _balance = 0;
581  return this;
582  }
583 
584  if (_balance == 0)
585  {
586  _balance = 1;
587  heightChanged = 0;
588  return this;
589  }
590 
591  /*
592  * Balancing needed
593  */
594  AvlTreeNode p1 = Next;
595  int b1 = p1._balance;
596 
597  if (b1 >= 0)
598  {
599  /*
600  * Simple RR rotation
601  */
602  PblAvlTreeSetRight(p1.Prev);
603 
604  p1.PblAvlTreeSetLeft(this);
605 
606  if (b1 == 0)
607  {
608  _balance = 1;
609  p1._balance = -1;
610  heightChanged = 0;
611  }
612  else
613  {
614  _balance = 0;
615  p1._balance = 0;
616  }
617  return p1;
618  }
619 
620  /*
621  * double RL rotation
622  */
623  AvlTreeNode p2 = p1.Prev;
624  int b2 = p2._balance;
625 
626  p1.PblAvlTreeSetLeft(p2.Next);
627 
628  p2.PblAvlTreeSetRight(p1);
629 
630  PblAvlTreeSetRight(p2.Prev);
631 
632  p2.PblAvlTreeSetLeft(this);
633 
634  if (b2 == 1)
635  {
636  _balance = -1;
637  }
638  else
639  {
640  _balance = 0;
641  }
642 
643  p1._balance = b2 == -1 ? 1 : 0;
644 
645  p2._balance = 0;
646  return p2;
647  }
648 
649  /*
650  * Balances an AVL tree.
651  *
652  * Used if right sub tree decreased in size.
653  *
654  * @return PblTreeNode * retPtr: The subtree p after the balance.
655  *
656  */
657  private AvlTreeNode PblTreeNodeBalanceRight(
658  out int heightChanged
659  )
660  {
661  heightChanged = 1;
662 
663  if (_balance == 1)
664  {
665  _balance = 0;
666  return this;
667  }
668 
669  if (_balance == 0)
670  {
671  _balance = -1;
672  heightChanged = 0;
673  return this;
674  }
675 
676  /*
677  * Balancing needed
678  */
679  AvlTreeNode p1 = Prev;
680  int b1 = p1._balance;
681 
682  if (b1 <= 0)
683  {
684  /*
685  * Simple LL rotation
686  */
687  PblAvlTreeSetLeft(p1.Next);
688 
689  p1.PblAvlTreeSetRight(this);
690 
691  if (b1 == 0)
692  {
693  _balance = -1;
694  p1._balance = 1;
695  heightChanged = 0;
696  }
697  else
698  {
699  _balance = 0;
700  p1._balance = 0;
701  }
702  return p1;
703  }
704 
705  /*
706  * double LR rotation
707  */
708  AvlTreeNode p2 = p1.Next;
709  int b2 = p2._balance;
710 
711  p1.PblAvlTreeSetRight(p2.Prev);
712 
713  p2.PblAvlTreeSetLeft(p1);
714 
715  PblAvlTreeSetLeft(p2.Next);
716 
717  p2.PblAvlTreeSetRight(this);
718 
719  _balance = b2 == -1 ? 1 : 0;
720 
721  if (b2 == 1)
722  {
723  p1._balance = -1;
724  }
725  else
726  {
727  p1._balance = 0;
728  }
729 
730  p2._balance = 0;
731  return p2;
732  }
733 
734  /*
735  * Helper function for AVL tree remove.
736  *
737  * @return PblTreeNode * retPtr: The subtree p after the remove.
738  */
739  private AvlTreeNode PblTreeNodeRemove2(
740  AvlTreeNode q,
741  out int heightChanged,
742  out bool nodeRemoved
743  )
744  {
745  AvlTreeNode r = this;
746  AvlTreeNode p;
747 
748  if (null != r.Next)
749  {
750  p = r.Next.PblTreeNodeRemove2(q, out heightChanged, out nodeRemoved);
751  r.PblAvlTreeSetRight(p);
752  if (0 != heightChanged)
753  {
754  r = r.PblTreeNodeBalanceRight(out heightChanged);
755  }
756  return r;
757  }
758 
759  q.Pair = r.Pair;
760  p = r.Prev;
761 
762  heightChanged = 1;
763  nodeRemoved = true;
764 
765  return p;
766  }
767 
768 
769  /*
770  * Removes a tree node from a tree set
771  *
772  * @return PblTreeNode * retPtr: The subtree p after the remove.
773  */
774  internal AvlTreeNode PblTreeNodeRemove(
775  TKey key,
776  out int heightChanged,
777  out bool nodeRemoved
778  )
779  {
780  AvlTreeNode p = this;
781  AvlTreeNode q = null;
782 
783  heightChanged = 0;
784  nodeRemoved = false;
785 
786  int compareResult = key.CompareTo(p.Pair.Key);
787 
788  if (compareResult < 0)
789  {
790  if (null != p.Prev)
791  {
792  q = p.Prev.PblTreeNodeRemove(key, out heightChanged, out nodeRemoved);
793  }
794  p.PblAvlTreeSetLeft(q);
795 
796  if (0 != heightChanged)
797  {
798  p = p.PblTreeNodeBalanceLeft(out heightChanged);
799  }
800  return p;
801  }
802 
803  if (compareResult > 0)
804  {
805  if (null != p.Next)
806  {
807  q = p.Next.PblTreeNodeRemove(key, out heightChanged, out nodeRemoved);
808  }
809  p.PblAvlTreeSetRight(q);
810 
811  if (0 != heightChanged)
812  {
813  p = p.PblTreeNodeBalanceRight(out heightChanged);
814  }
815  return p;
816  }
817 
818  /*
819  * p is the node that needs to be removed!
820  */
821  q = p;
822 
823  if (null == q.Next)
824  {
825  p = q.Prev;
826  heightChanged = 1;
827 
828  nodeRemoved = true;
829  }
830  else if (null == q.Prev)
831  {
832  p = q.Next;
833  heightChanged = 1;
834 
835  nodeRemoved = true;
836  }
837  else
838  {
839  /*
840  * Replace q with is biggest predecessor and remove that
841  */
842  AvlTreeNode p1 = q.Prev.PblTreeNodeRemove2(q, out heightChanged, out nodeRemoved);
843  q.PblAvlTreeSetLeft(p1);
844 
845  if (0 != heightChanged)
846  {
847  p = p.PblTreeNodeBalanceLeft(out heightChanged);
848  }
849  }
850 
851  return p;
852  }
853  }
854 
859  [Serializable]
860  public sealed class KeyCollection : ICollection<TKey>, ICollection
861  {
866 
867  public sealed class CollectionEnumerator : AvlDictionaryBaseEnumerator, IEnumerator<TKey>
868  {
875 
876  public CollectionEnumerator(AvlDictionary<TKey, TValue> dictionary)
877  : base(dictionary)
878  {
879  }
880 
881  #region IEnumerator<TKey> Member
882 
889 
890  public TKey Current
891  {
892  get
893  {
894  return CurrentKey;
895  }
896  }
897 
898  #endregion
899 
900 
901  #region IEnumerator Member
902 
909 
910  object IEnumerator.Current
911  {
912  get
913  {
914  return CurrentKey;
915  }
916  }
917 
918  #endregion
919  }
920 
921  private readonly AvlDictionary<TKey, TValue> _avlDictionary;
922 
923  internal KeyCollection(AvlDictionary<TKey, TValue> avlDictionary)
924  {
925  _avlDictionary = avlDictionary;
926  }
927 
928  #region ICollection<TKey> Member
929 
936 
937  public void Add(TKey item)
938  {
939  throw new NotSupportedException("The AvlDictionary.KeyCollection is read-only.");
940  }
941 
948 
949  public void Clear()
950  {
951  throw new NotSupportedException("The AvlDictionary.KeyCollection is read-only.");
952  }
953 
966 
967  public bool Contains(TKey item)
968  {
969  return _avlDictionary.ContainsKey(item);
970  }
971 
996 
997  public void CopyTo(TKey[] array, int index)
998  {
999  if (array == null)
1000  {
1001  throw new ArgumentNullException("array");
1002  }
1003  if (index < 0)
1004  {
1005  throw new ArgumentOutOfRangeException("index", "index is less than zero.");
1006  }
1007  if (index >= array.Length)
1008  {
1009  throw new ArgumentException("index is equal to or greater than the length of array.");
1010  }
1011 
1012  if (_avlDictionary.Size == 0)
1013  {
1014  return;
1015  }
1016 
1017  if (index + _avlDictionary.Size > array.Length)
1018  {
1019  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.");
1020  }
1021 
1022  IEnumerator<TKey> en = GetEnumerator();
1023  for (int i = 0; en.MoveNext(); i++)
1024  {
1025  array[i + index] = en.Current;
1026  }
1027  }
1028 
1036 
1037  public int Count
1038  {
1039  get { return _avlDictionary.Count; }
1040  }
1041 
1048 
1049  public bool IsReadOnly
1050  {
1051  get { return true; }
1052  }
1053 
1060 
1061  public bool Remove(TKey item)
1062  {
1063  throw new NotSupportedException("The AvlDictionary.KeyCollection is read-only.");
1064  }
1065 
1066  #endregion
1067 
1068  #region IEnumerable<TKey> Member
1069 
1076 
1077  public IEnumerator<TKey> GetEnumerator()
1078  {
1079  return new CollectionEnumerator(_avlDictionary);
1080  }
1081 
1082  #endregion
1083 
1084  #region IEnumerable Member
1085 
1092 
1093  IEnumerator IEnumerable.GetEnumerator()
1094  {
1095  return new CollectionEnumerator(_avlDictionary);
1096  }
1097 
1098  #endregion
1099 
1100  #region ICollection Member
1101 
1126 
1127  public void CopyTo(Array array, int index)
1128  {
1129  if (array == null)
1130  {
1131  throw new ArgumentNullException("array");
1132  }
1133  if (index < 0)
1134  {
1135  throw new ArgumentOutOfRangeException("index", "index is less than zero.");
1136  }
1137  if (index >= array.Length)
1138  {
1139  throw new ArgumentException("index is equal to or greater than the length of array.");
1140  }
1141 
1142  if (Count == 0)
1143  {
1144  return;
1145  }
1146 
1147  if (index + Count > array.Length)
1148  {
1149  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.");
1150  }
1151 
1152  IEnumerator<TKey> en = GetEnumerator();
1153  for (int i = 0; en.MoveNext(); i++)
1154  {
1155  array.SetValue(en.Current, i + index);
1156  }
1157  }
1158 
1165 
1166  public bool IsSynchronized
1167  {
1168  get { return false; }
1169  }
1170 
1177 
1178  public object SyncRoot
1179  {
1180  get { return _avlDictionary._lock; }
1181  }
1182 
1183  #endregion
1184  }
1185 
1190  [Serializable]
1191  public sealed class ValueCollection : ICollection<TValue>, ICollection
1192  {
1197  public sealed class CollectionEnumerator : AvlDictionaryBaseEnumerator, IEnumerator<TValue>
1198  {
1205 
1206  public CollectionEnumerator(AvlDictionary<TKey, TValue> dictionary)
1207  : base(dictionary)
1208  {
1209  }
1210 
1211  #region IEnumerator<TKey> Member
1212 
1219 
1220  public TValue Current
1221  {
1222  get
1223  {
1224  return CurrentValue;
1225  }
1226  }
1227 
1228  #endregion
1229 
1230  #region IEnumerator Member
1231 
1238 
1239  object IEnumerator.Current
1240  {
1241  get
1242  {
1243  return CurrentValue;
1244  }
1245  }
1246 
1247  #endregion
1248  }
1249 
1250  private readonly AvlDictionary<TKey, TValue> _avlDictionary;
1251 
1252  internal ValueCollection(AvlDictionary<TKey, TValue> avlDictionary)
1253  {
1254  _avlDictionary = avlDictionary;
1255  }
1256 
1257  #region ICollection<TValue> Member
1258 
1265 
1266  public void Add(TValue item)
1267  {
1268  throw new NotSupportedException("The AvlDictionary.ValueCollection is read-only.");
1269  }
1270 
1277 
1278  public void Clear()
1279  {
1280  throw new NotSupportedException("The AvlDictionary.ValueCollection is read-only.");
1281  }
1282 
1295 
1296  public bool Contains(TValue item)
1297  {
1298  if (_avlDictionary.Size == 0)
1299  {
1300  return false;
1301  }
1302 
1303  if (item == null)
1304  {
1305  for (IEnumerator<TValue> en = GetEnumerator(); en.MoveNext(); )
1306  {
1307  if (null == en.Current)
1308  {
1309  return true;
1310  }
1311  }
1312  }
1313  else
1314  {
1315  for (IEnumerator<TValue> en = GetEnumerator(); en.MoveNext(); )
1316  {
1317  if (item.Equals(en.Current))
1318  {
1319  return true;
1320  }
1321  }
1322  }
1323  return false;
1324  }
1325 
1350 
1351  public void CopyTo(TValue[] array, int index)
1352  {
1353  if (array == null)
1354  {
1355  throw new ArgumentNullException("array");
1356  }
1357  if (index < 0)
1358  {
1359  throw new ArgumentOutOfRangeException("index", "index is less than zero.");
1360  }
1361  if (index >= array.Length)
1362  {
1363  throw new ArgumentException("index is equal to or greater than the length of array.");
1364  }
1365 
1366  if (_avlDictionary.Size == 0)
1367  {
1368  return;
1369  }
1370 
1371  if (index + _avlDictionary.Size > array.Length)
1372  {
1373  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.");
1374  }
1375 
1376  IEnumerator<TValue> en = GetEnumerator();
1377  for (int i = 0; en.MoveNext(); i++)
1378  {
1379  array[i + index] = en.Current;
1380  }
1381  }
1382 
1390 
1391  public int Count
1392  {
1393  get { return _avlDictionary.Count; }
1394  }
1395 
1402 
1403  public bool IsReadOnly
1404  {
1405  get { return true; }
1406  }
1407 
1414 
1415  public bool Remove(TValue item)
1416  {
1417  throw new NotSupportedException("The AvlDictionary.ValueCollection is read-only.");
1418  }
1419 
1420  #endregion
1421 
1422  #region IEnumerable<TValue> Member
1423 
1430 
1431  public IEnumerator<TValue> GetEnumerator()
1432  {
1433  return new CollectionEnumerator(_avlDictionary);
1434  }
1435 
1436  #endregion
1437 
1438  #region IEnumerable Member
1439 
1446 
1447  IEnumerator IEnumerable.GetEnumerator()
1448  {
1449  return new CollectionEnumerator(_avlDictionary);
1450  }
1451 
1452  #endregion
1453 
1454  #region ICollection Member
1455 
1480 
1481  public void CopyTo(Array array, int index)
1482  {
1483  if (array == null)
1484  {
1485  throw new ArgumentNullException("array");
1486  }
1487  if (index < 0)
1488  {
1489  throw new ArgumentOutOfRangeException("index", "index is less than zero.");
1490  }
1491  if (index >= array.Length)
1492  {
1493  throw new ArgumentException("index is equal to or greater than the length of array.");
1494  }
1495 
1496  if (Count == 0)
1497  {
1498  return;
1499  }
1500 
1501  if (index + Count > array.Length)
1502  {
1503  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.");
1504  }
1505 
1506  IEnumerator<TValue> en = GetEnumerator();
1507  for (int i = 0; en.MoveNext(); i++)
1508  {
1509  array.SetValue(en.Current, i + index);
1510  }
1511  }
1512 
1519 
1520  public bool IsSynchronized
1521  {
1522  get { return false; }
1523  }
1524 
1531 
1532  public object SyncRoot
1533  {
1534  get { return _avlDictionary._lock; }
1535  }
1536 
1537  #endregion
1538  }
1539 
1540  private AvlTreeNode _rootNode;
1541 
1542  private long _changeCounter;
1543 
1544  private readonly object _lock;
1545 
1546  private int Size { get; set; }
1547 
1548  private readonly KeyCollection _keys;
1549 
1550  private readonly ValueCollection _values;
1551 
1552  private AvlTreeNode FindNode(TKey key)
1553  {
1554  if (Size == 0)
1555  {
1556  return null;
1557  }
1558 
1559  AvlTreeNode node = _rootNode;
1560 
1561  while (node != null)
1562  {
1563  int compareResult = key.CompareTo(node.Pair.Key);
1564  if (compareResult == 0)
1565  {
1566  return node;
1567  }
1568 
1569  node = compareResult < 0 ? node.Prev : node.Next;
1570  }
1571  return null;
1572  }
1573 
1574  private AvlTreeNode AddNode(TKey key, TValue value, out bool nodeAdded)
1575  {
1576  if (key == null)
1577  {
1578  throw new ArgumentNullException("key");
1579  }
1580 
1581  if (IsReadOnly)
1582  {
1583  throw new NotSupportedException("The AvlDictionary is read-only.");
1584  }
1585 
1586  int heightChanged;
1587  AvlTreeNode node;
1588 
1589  AvlTreeNode insertResult = AvlTreeNode.PblTreeNodeInsert(_rootNode, key, value, out heightChanged, out node, out nodeAdded);
1590  if (!nodeAdded)
1591  {
1592  return node;
1593  }
1594 
1595  Size += 1;
1596  _changeCounter++;
1597 
1598  /*
1599  * Remember the tree after the insert
1600  */
1601  insertResult.Parent = null;
1602  _rootNode = insertResult;
1603  return node;
1604  }
1605 
1609  public AvlDictionary()
1610  {
1611  _changeCounter = 0;
1612  _lock = new object();
1613  _keys = new KeyCollection(this);
1614  _values = new ValueCollection(this);
1615  }
1616 
1634  public AvlDictionary(IEnumerable<KeyValuePair<TKey, TValue>> dictionary)
1635  : this()
1636  {
1637  if (null == dictionary)
1638  {
1639  throw new ArgumentNullException("dictionary");
1640  }
1641 
1642  for (IEnumerator<KeyValuePair<TKey, TValue>> en = dictionary.GetEnumerator(); en.MoveNext(); )
1643  {
1644  Add(en.Current);
1645  }
1646  }
1647 
1648  #region IDictionary<TKey,TValue> Member
1649 
1668  public void Add(TKey key, TValue value)
1669  {
1670  bool nodeAdded;
1671  AddNode(key, value, out nodeAdded);
1672  if (!nodeAdded)
1673  {
1674  throw new ArgumentException(string.Format("An element with the same key '{0}' already exists in the AvlDictionary.", key));
1675  }
1676  }
1677 
1693  public bool ContainsKey(TKey key)
1694  {
1695  return FindNode(key) != null;
1696  }
1697 
1704 
1705  public ICollection<TKey> Keys
1706  {
1707  get { return _keys; }
1708  }
1709 
1729  public bool Remove(TKey key)
1730  {
1731  if (key == null)
1732  {
1733  throw new ArgumentNullException("key");
1734  }
1735 
1736  if (IsReadOnly)
1737  {
1738  throw new NotSupportedException("The AvlDictionary is read-only.");
1739  }
1740 
1741  if (null == _rootNode)
1742  {
1743  return false;
1744  }
1745 
1746  int heightChanged;
1747  bool nodeRemoved;
1748 
1749  AvlTreeNode removeResult = _rootNode.PblTreeNodeRemove(key, out heightChanged, out nodeRemoved);
1750  if (nodeRemoved)
1751  {
1752  Size -= 1;
1753  _changeCounter++;
1754 
1755  /*
1756  * Remember the tree after the removal
1757  */
1758  if (removeResult != null)
1759  {
1760  removeResult.Parent = null;
1761  }
1762  _rootNode = removeResult;
1763  }
1764 
1765  return nodeRemoved;
1766  }
1767 
1789  public bool TryGetValue(TKey key, out TValue value)
1790  {
1791  if (key == null)
1792  {
1793  throw new ArgumentNullException("key");
1794  }
1795 
1796  AvlTreeNode node = FindNode(key);
1797  if (node == null)
1798  {
1799  value = default(TValue);
1800  return false;
1801  }
1802 
1803  value = node.Pair.Value;
1804  return true;
1805  }
1806 
1813  public ICollection<TValue> Values
1814  {
1815  get { return _values; }
1816  }
1817 
1841  public TValue this[TKey key]
1842  {
1843  get
1844  {
1845  TValue value;
1846  if (TryGetValue(key, out value))
1847  {
1848  return value;
1849  }
1850  throw new KeyNotFoundException("key does not exist in the collection.");
1851  }
1852  set
1853  {
1854  if (IsReadOnly)
1855  {
1856  throw new NotSupportedException("The AvlDictionary is read-only.");
1857  }
1858 
1859  bool nodeAdded;
1860  AvlTreeNode node = AddNode(key, value, out nodeAdded);
1861  if (!nodeAdded)
1862  {
1863  if (null == value)
1864  {
1865  if (null != node.Pair.Value)
1866  {
1867  node.Pair = new KeyValuePair<TKey, TValue>(key, value);
1868  }
1869  }
1870  else
1871  {
1872  if (!value.Equals(node.Pair.Value))
1873  {
1874  node.Pair = new KeyValuePair<TKey, TValue>(key, value);
1875  }
1876  }
1877  }
1878  }
1879  }
1880 
1881  #endregion
1882 
1883  #region ICollection<KeyValuePair<TKey,TValue>> Member
1884 
1900  public void Add(KeyValuePair<TKey, TValue> item)
1901  {
1902  bool nodeAdded;
1903  AvlTreeNode node = AddNode(item.Key, item.Value, out nodeAdded);
1904  if (!nodeAdded)
1905  {
1906  throw new ArgumentException(string.Format("An element with the same key '{0}' already exists in the AvlDictionary.", item.Key));
1907  }
1908  node.Pair = item;
1909  }
1910 
1917  public void Clear()
1918  {
1919  if (IsReadOnly)
1920  {
1921  throw new NotSupportedException("The AvlDictionary is read-only.");
1922  }
1923 
1924  _rootNode = null;
1925  Size = 0;
1926  }
1927 
1940  public bool Contains(KeyValuePair<TKey, TValue> item)
1941  {
1942  AvlTreeNode node = FindNode(item.Key);
1943  if (node == null)
1944  {
1945  return false;
1946  }
1947  return item.Equals(node.Pair);
1948  }
1949 
1974  public void CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
1975  {
1976  if (array == null)
1977  {
1978  throw new ArgumentNullException("array");
1979  }
1980  if (index < 0)
1981  {
1982  throw new ArgumentOutOfRangeException("index", "index is less than zero.");
1983  }
1984  if (index >= array.Length)
1985  {
1986  throw new ArgumentException("index is equal to or greater than the length of array.");
1987  }
1988 
1989  if (Size == 0)
1990  {
1991  return;
1992  }
1993 
1994  if (index + Size > array.Length)
1995  {
1996  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.");
1997  }
1998 
1999  IEnumerator<KeyValuePair<TKey, TValue>> en = GetEnumerator();
2000  for (int i = 0; en.MoveNext(); i++)
2001  {
2002  array[i + index] = en.Current;
2003  }
2004  }
2005 
2013  public int Count
2014  {
2015  get { return Size; }
2016  }
2017 
2024  public bool IsReadOnly
2025  {
2026  get { return false; }
2027  }
2028 
2046  public bool Remove(KeyValuePair<TKey, TValue> item)
2047  {
2048  if (IsReadOnly)
2049  {
2050  throw new NotSupportedException("The AvlDictionary is read-only.");
2051  }
2052 
2053  AvlTreeNode node = FindNode(item.Key);
2054  if (node == null)
2055  {
2056  return false;
2057  }
2058  if (item.Equals(node.Pair))
2059  {
2060  Remove(item.Key);
2061  return true;
2062  }
2063  return false;
2064  }
2065 
2066  #endregion
2067 
2068  #region IEnumerable<KeyValuePair<TKey,TValue>> Member
2069 
2076  public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
2077  {
2078  return new Enumerator(this);
2079  }
2080 
2081  #endregion
2082 
2083  #region IEnumerable Member
2084 
2091  IEnumerator IEnumerable.GetEnumerator()
2092  {
2093  return new Enumerator(this);
2094  }
2095 
2096  #endregion
2097 
2098  #region ICollection Member
2099 
2123  public void CopyTo(Array array, int index)
2124  {
2125  if (array == null)
2126  {
2127  throw new ArgumentNullException("array");
2128  }
2129  if (index < 0)
2130  {
2131  throw new ArgumentOutOfRangeException("index", "index is less than zero.");
2132  }
2133  if (index >= array.Length)
2134  {
2135  throw new ArgumentException("index is equal to or greater than the length of array.");
2136  }
2137 
2138  if (Size == 0)
2139  {
2140  return;
2141  }
2142 
2143  if (index + Size > array.Length)
2144  {
2145  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.");
2146  }
2147 
2148  IEnumerator<KeyValuePair<TKey, TValue>> en = GetEnumerator();
2149  for (int i = 0; en.MoveNext(); i++)
2150  {
2151  array.SetValue(en.Current, i + index);
2152  }
2153  }
2154 
2161  public bool IsSynchronized
2162  {
2163  get { return false; }
2164  }
2165 
2172  public object SyncRoot
2173  {
2174  get { return _lock; }
2175  }
2176 
2177  #endregion
2178  }
2179 }