mcs/class/System/System.Collections.Specialized/ListDictionary.cs

   1 //
   2 // System.Collections.Specialized.ListDictionary.cs
   3 //
   4 // Copyright (C) 2004, 2005 Novell (http://www.novell.com)
   5 //
   6
   7 //
   8 // Permission is hereby granted, free of charge, to any person obtaining
   9 // a copy of this software and associated documentation files (the
  10 // "Software"), to deal in the Software without restriction, including
  11 // without limitation the rights to use, copy, modify, merge, publish,
  12 // distribute, sublicense, and/or sell copies of the Software, and to
  13 // permit persons to whom the Software is furnished to do so, subject to
  14 // the following conditions:
  15 //
  16 // The above copyright notice and this permission notice shall be
  17 // included in all copies or substantial portions of the Software.
  18 //
  19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  20 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  21 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  22 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  23 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  24 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  25 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  26 //
  27 using System;
  28 using System.Runtime.Serialization;
  29
  30 namespace System.Collections.Specialized
  31 {
  32         [Serializable]
  33         public class ListDictionary : IDictionary, ICollection, IEnumerable {
  34                 private int count;
  35                 private int version;
  36                 private DictionaryNode head;
  37                 private IComparer comparer;
  38
  39                 public ListDictionary ()
  40                 {
  41                         count = 0;
  42                         version = 0;
  43                         comparer = null;
  44                         head = null;
  45                 }
  46
  47                 public ListDictionary (IComparer comparer) : this ()
  48                 {
  49                         this.comparer = comparer;
  50                 }
  51
  52                 private DictionaryNode FindEntry (object key, out DictionaryNode prev)
  53                 {
  54                         if (key == null)
  55                                 throw new ArgumentNullException ("key", "Attempted lookup for a null key.");
  56
  57                         DictionaryNode entry = head;
  58                         prev = null;
  59                         if (comparer == null) {
  60                                 while (entry != null) {
  61                                         if (key.Equals (entry.key))
  62                                                 break;
  63                                         prev = entry;
  64                                         entry = entry.next;
  65                                 }
  66                         } else {
  67                                 while (entry != null) {
  68                                         if (comparer.Compare (key, entry.key) == 0)
  69                                                 break;
  70                                         prev = entry;
  71                                         entry = entry.next;
  72                                 }
  73                         }
  74                         return entry;
  75                 }
  76
  77                 private void AddImpl (object key, object value, DictionaryNode prev)
  78                 {
  79                         //
  80                         // Code in the MCS compiler (doc.cs) appears to depend on the new entry being
  81                         // added at the end, even though we don't promise any such thing.
  82                         // Preferably, this code would just have been:
  83                         //
  84                         //   head = new DictionaryNode (key, value, head);
  85                         //
  86                         if (prev == null)
  87                                 head = new DictionaryNode (key, value, head);
  88                         else
  89                                 prev.next = new DictionaryNode (key, value, prev.next);
  90                         ++count;
  91                         ++version;
  92                 }
  93
  94                 // IEnumerable Interface
  95                 IEnumerator IEnumerable.GetEnumerator ()
  96                 {
  97                         return new DictionaryNodeEnumerator (this);
  98                 }
  99
 100                 // ICollection Interface
 101                 public int Count {
 102                         get { return count; }
 103                 }
 104
 105                 public bool IsSynchronized {
 106                         get { return false; }
 107                 }
 108
 109                 public object SyncRoot {
 110                         get { return this; }
 111                 }
 112
 113                 public void CopyTo (Array array, int index)
 114                 {
 115                         if (array == null)
 116                                 throw new ArgumentNullException ("array", "Array cannot be null.");
 117                         if (index < 0)
 118                                 throw new ArgumentOutOfRangeException ("index", "index is less than 0");
 119                         if (index > array.Length)
 120                                 throw new IndexOutOfRangeException ("index is too large");
 121                         if (Count > array.Length - index)
 122                                 throw new ArgumentException ("Not enough room in the array");
 123
 124                         foreach (DictionaryEntry entry in this)
 125                                 array.SetValue (entry, index++);
 126                 }
 127
 128                 // IDictionary Interface
 129                 public bool IsFixedSize {
 130                         get { return false; }
 131                 }
 132
 133                 public bool IsReadOnly {
 134                         get { return false; }
 135                 }
 136
 137                 // Indexer
 138                 public object this [object key] {
 139                         get {
 140                                 DictionaryNode prev;
 141                                 DictionaryNode entry = FindEntry (key, out prev);
 142                                 return entry == null ? null : entry.value;
 143                         }
 144
 145                         set {
 146                                 DictionaryNode prev;
 147                                 DictionaryNode entry = FindEntry (key, out prev);
 148                                 if (entry != null)
 149                                         entry.value = value;
 150                                 else
 151                                         AddImpl (key, value, prev);
 152                         }
 153                 }
 154
 155                 public ICollection Keys {
 156                         get { return new DictionaryNodeCollection (this, true); }
 157                 }
 158
 159                 public ICollection Values {
 160                         get { return new DictionaryNodeCollection (this, false); }
 161                 }
 162
 163                 public void Add (object key, object value)
 164                 {
 165                         DictionaryNode prev;
 166                         DictionaryNode entry = FindEntry (key, out prev);
 167                         if (entry != null)
 168                                 throw new ArgumentException ("key", "Duplicate key in add.");
 169
 170                         AddImpl (key, value, prev);
 171                 }
 172
 173                 public void Clear ()
 174                 {
 175                         head = null;
 176                         count = 0;
 177                         version++;
 178                 }
 179
 180                 public bool Contains (object key)
 181                 {
 182                         DictionaryNode prev;
 183                         return FindEntry (key, out prev) != null;
 184                 }
 185
 186                 public IDictionaryEnumerator GetEnumerator ()
 187                 {
 188                         return new DictionaryNodeEnumerator (this);
 189                 }
 190
 191                 public void Remove (object key)
 192                 {
 193                         DictionaryNode prev;
 194                         DictionaryNode entry = FindEntry (key, out prev);
 195                         if (entry == null)
 196                                 return;
 197                         if (prev == null)
 198                                 head = entry.next;
 199                         else
 200                                 prev.next = entry.next;
 201                         entry.value = null;
 202                         count--;
 203                         version++;
 204                 }
 205
 206
 207                 [Serializable]
 208                 private class DictionaryNode {
 209                         public object key;
 210                         public object value;
 211                         public DictionaryNode next;
 212                         public DictionaryNode (object key, object value, DictionaryNode next)
 213                         {
 214                                 this.key = key;
 215                                 this.value = value;
 216                                 this.next = next;
 217                         }
 218                 }
 219
 220                 private class DictionaryNodeEnumerator : IEnumerator, IDictionaryEnumerator {
 221                         private ListDictionary dict;
 222                         private bool isAtStart;
 223                         private DictionaryNode current;
 224                         private int version;
 225
 226                         public DictionaryNodeEnumerator (ListDictionary dict)
 227                         {
 228                                 this.dict = dict;
 229                                 version = dict.version;
 230                                 Reset();
 231                         }
 232
 233                         private void FailFast()
 234                         {
 235                                 if (version != dict.version) {
 236                                         throw new InvalidOperationException (
 237                                                 "The ListDictionary's contents changed after this enumerator was instantiated.");
 238                                 }
 239                         }
 240
 241                         public bool MoveNext ()
 242                         {
 243                                 FailFast ();
 244                                 if (current == null && !isAtStart)
 245                                         return false;
 246                                 current = isAtStart ? dict.head : current.next;
 247                                 isAtStart = false;
 248                                 return current != null;
 249                         }
 250
 251                         public void Reset ()
 252                         {
 253                                 FailFast ();
 254                                 isAtStart = true;
 255                                 current = null;
 256                         }
 257
 258                         public object Current {
 259                                 get { return Entry; }
 260                         }
 261
 262                         private DictionaryNode DictionaryNode {
 263                                 get {
 264                                         FailFast ();
 265                                         if (current == null)
 266                                                 throw new InvalidOperationException (
 267                                                         "Enumerator is positioned before the collection's first element or after the last element.");
 268                                         return current;
 269                                 }
 270                         }
 271
 272                         // IDictionaryEnumerator
 273                         public DictionaryEntry Entry {
 274                                 get {
 275                                         object key = DictionaryNode.key;
 276                                         return new DictionaryEntry (key, current.value);
 277                                 }
 278                         }
 279
 280                         public object Key {
 281                                 get { return DictionaryNode.key; }
 282                         }
 283
 284                         public object Value {
 285                                 get { return DictionaryNode.value; }
 286                         }
 287                 }
 288
 289                 private class DictionaryNodeCollection : ICollection {
 290                         private ListDictionary dict;
 291                         private bool isKeyList;
 292
 293                         public DictionaryNodeCollection (ListDictionary dict, bool isKeyList)
 294                         {
 295                                 this.dict = dict;
 296                                 this.isKeyList = isKeyList;
 297                         }
 298
 299                         // ICollection Interface
 300                         public int Count {
 301                                 get { return dict.Count; }
 302                         }
 303
 304                         public bool IsSynchronized {
 305                                 get { return false; }
 306                         }
 307
 308                         public object SyncRoot {
 309                                 get { return dict.SyncRoot; }
 310                         }
 311
 312                         public void CopyTo (Array array, int index)
 313                         {
 314                                 if (array == null)
 315                                         throw new ArgumentNullException ("array", "Array cannot be null.");
 316                                 if (index < 0)
 317                                         throw new ArgumentOutOfRangeException ("index", "index is less than 0");
 318                                 if (index > array.Length)
 319                                         throw new IndexOutOfRangeException ("index is too large");
 320                                 if (Count > array.Length - index)
 321                                         throw new ArgumentException ("Not enough room in the array");
 322
 323                                 foreach (object obj in this)
 324                                         array.SetValue (obj, index++);
 325                         }
 326
 327                         // IEnumerable Interface
 328                         public IEnumerator GetEnumerator()
 329                         {
 330                                 return new DictionaryNodeCollectionEnumerator (dict.GetEnumerator (), isKeyList);
 331                         }
 332
 333                         private class DictionaryNodeCollectionEnumerator : IEnumerator {
 334                                 private IDictionaryEnumerator inner;
 335                                 private bool isKeyList;
 336
 337                                 public DictionaryNodeCollectionEnumerator (IDictionaryEnumerator inner, bool isKeyList)
 338                                 {
 339                                         this.inner = inner;
 340                                         this.isKeyList = isKeyList;
 341                                 }
 342
 343                                 public object Current {
 344                                         get { return isKeyList ? inner.Key : inner.Value; }
 345                                 }
 346
 347                                 public bool MoveNext ()
 348                                 {
 349                                         return inner.MoveNext ();
 350                                 }
 351
 352                                 public void Reset ()
 353                                 {
 354                                         inner.Reset ();
 355                                 }
 356                         }
 357                 }
 358         }
 359 }