mcs/class/corlib/System.Collections.ObjectModel/KeyedCollection.cs

   1 // -*- Mode: csharp; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*-
   2 //
   3 // System.Collections.ObjectModel.KeyedCollection
   4 //
   5 // Author:
   6 //    Zoltan Varga (vargaz@gmail.com)
   7 //
   8 // (C) 2005 Novell, Inc.
   9 //
  10
  11 //
  12 // Copyright (C) 2005 Novell, Inc (http://www.novell.com)
  13 //
  14 // Permission is hereby granted, free of charge, to any person obtaining
  15 // a copy of this software and associated documentation files (the
  16 // "Software"), to deal in the Software without restriction, including
  17 // without limitation the rights to use, copy, modify, merge, publish,
  18 // distribute, sublicense, and/or sell copies of the Software, and to
  19 // permit persons to whom the Software is furnished to do so, subject to
  20 // the following conditions:
  21 //
  22 // The above copyright notice and this permission notice shall be
  23 // included in all copies or substantial portions of the Software.
  24 //
  25 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  26 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  27 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  28 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  29 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  30 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  31 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  32 //
  33
  34 using System;
  35 using System.Collections.Generic;
  36 using System.Runtime.InteropServices;
  37 using System.Diagnostics;
  38
  39 namespace System.Collections.ObjectModel
  40 {
  41         [ComVisible(false)]
  42         [Serializable]
  43         [DebuggerDisplay ("Count={Count}")]
  44         [DebuggerTypeProxy (typeof (CollectionDebuggerView<,>))]
  45         public abstract class KeyedCollection<TKey, TItem> : Collection<TItem>
  46         {
  47                 private Dictionary<TKey, TItem> dictionary;
  48                 private IEqualityComparer<TKey> comparer;
  49                 private int dictionaryCreationThreshold;
  50
  51                 protected KeyedCollection ()
  52                         : this (null, 0)
  53                 {
  54                 }
  55
  56                 protected KeyedCollection (IEqualityComparer<TKey> comparer)
  57                         : this(comparer, 0)
  58                 {
  59                 }
  60
  61                 protected KeyedCollection (IEqualityComparer<TKey> comparer, int dictionaryCreationThreshold)
  62                 {
  63                         if (comparer != null)
  64                                 this.comparer = comparer;
  65                         else
  66                                 this.comparer = EqualityComparer<TKey>.Default;
  67
  68                         this.dictionaryCreationThreshold = dictionaryCreationThreshold;
  69
  70                         if (dictionaryCreationThreshold == 0)
  71                                 dictionary = new Dictionary<TKey, TItem> (this.comparer);
  72                 }
  73
  74                 public bool Contains (TKey key)
  75                 {
  76                         if (dictionary != null)
  77                                 return dictionary.ContainsKey (key);
  78                         return IndexOfKey (key) >= 0;
  79                 }
  80
  81                 private int IndexOfKey (TKey key)
  82                 {
  83                         for (int i = Count - 1; i >= 0; i--)
  84                         {
  85                                 TKey lkey = GetKeyForItem (this [i]);
  86                                 if (comparer.Equals (key, lkey))
  87                                         return i;
  88                         }
  89                         return -1;
  90                 }
  91
  92                 public bool Remove (TKey key)
  93                 {
  94                         TItem item;
  95                         if (dictionary != null)
  96                         {
  97                                 if (dictionary.TryGetValue (key, out item))
  98                                         return base.Remove(item);
  99                                 else
 100                                         return false;
 101                         }
 102
 103                         int idx = IndexOfKey (key);
 104
 105                         if (idx == -1)
 106                                 return false;
 107
 108                         RemoveAt(idx);
 109                         return true;
 110                 }
 111
 112                 public IEqualityComparer<TKey> Comparer {
 113                         get {
 114                                 return comparer;
 115                         }
 116                 }
 117
 118                 public TItem this [TKey key] {
 119                         get {
 120                                 if (dictionary != null)
 121                                         return dictionary [key];
 122
 123                                 int idx = IndexOfKey (key);
 124                                 if (idx >= 0)
 125                                         return base [idx];
 126                                 else
 127                                         throw new KeyNotFoundException();
 128                         }
 129                 }
 130
 131                 protected void ChangeItemKey (TItem item, TKey newKey)
 132                 {
 133                         if (!Contains(item)) throw new ArgumentException();
 134
 135                         TKey oldKey = GetKeyForItem (item);
 136                         if (comparer.Equals (oldKey, newKey)) return;
 137
 138                         if (Contains (newKey)) throw new ArgumentException();
 139                         if (dictionary != null)
 140                         {
 141
 142                                 if (!dictionary.Remove (oldKey))
 143                                         throw new ArgumentException();
 144
 145                                 dictionary.Add (newKey, item);
 146                         }
 147                 }
 148
 149                 protected override void ClearItems ()
 150                 {
 151                         if (dictionary != null)
 152                         {
 153                                 dictionary.Clear();
 154                         }
 155
 156                         base.ClearItems ();
 157                 }
 158
 159                 protected abstract TKey GetKeyForItem (TItem item);
 160
 161                 protected override void InsertItem (int index, TItem item)
 162                 {
 163                         TKey key = GetKeyForItem (item);
 164                         if (key == null)
 165                                 throw new ArgumentNullException ("GetKeyForItem(item)");
 166
 167                         if (dictionary != null && dictionary.ContainsKey (key))
 168                                 throw new ArgumentException ("An element with the same key already exists in the dictionary.");
 169
 170                         if (dictionary == null)
 171                                 for (int i = 0; i < Count; ++i) {
 172                                         if (comparer.Equals (key, GetKeyForItem (this [i]))) {
 173                                                 throw new ArgumentException ("An element with the same key already exists in the dictionary.");
 174                                         }
 175                                 }
 176
 177                         base.InsertItem (index, item);
 178
 179                         if (dictionary != null)
 180                                 dictionary.Add (key, item);
 181                         else if (dictionaryCreationThreshold != -1 && Count > dictionaryCreationThreshold) {
 182                                 dictionary = new Dictionary<TKey, TItem> (comparer);
 183
 184                                 for (int i = 0; i < Count; ++i) {
 185                                         TItem dictitem = this [i];
 186                                         dictionary.Add (GetKeyForItem (dictitem), dictitem);
 187                                 }
 188                         }
 189                 }
 190
 191                 protected override void RemoveItem (int index)
 192                 {
 193                         if (dictionary != null)
 194                         {
 195                                 TKey key = GetKeyForItem (this [index]);
 196                                 dictionary.Remove (key);
 197                         }
 198                         base.RemoveItem (index);
 199                 }
 200
 201                 protected override void SetItem (int index, TItem item)
 202                 {
 203                         if (dictionary != null)
 204                         {
 205                                 dictionary.Remove (GetKeyForItem (this [index]));
 206                                 dictionary.Add (GetKeyForItem (item), item);
 207                         }
 208                         base.SetItem (index, item);
 209                 }
 210
 211                 protected IDictionary<TKey, TItem> Dictionary {
 212                         get {
 213                                 return dictionary;
 214                         }
 215                 }
 216         }
 217 }