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)
  53                 {
  54                         if (key == null)
  55                                 throw new ArgumentNullException ("key", "Attempted lookup for a null key.");
  56
  57                         DictionaryNode entry = head;
  58                         if (comparer == null) {
  59                                 while (entry != null) {
  60                                         if (key.Equals (entry.key))
  61                                                 break;
  62                                         entry = entry.next;
  63                                 }
  64                         } else {
  65                                 while (entry != null) {
  66                                         if (comparer.Compare (key, entry.key) == 0)
  67                                                 break;
  68                                         entry = entry.next;
  69                                 }
  70                         }
  71                         return entry;
  72                 }
  73                 private DictionaryNode FindEntry (object key, out DictionaryNode prev)
  74                 {
  75                         if (key == null)
  76                                 throw new ArgumentNullException ("key", "Attempted lookup for a null key.");
  77
  78                         DictionaryNode entry = head;
  79                         prev = null;
  80                         if (comparer == null) {
  81                                 while (entry != null) {
  82                                         if (key.Equals (entry.key))
  83                                                 break;
  84                                         prev = entry;
  85                                         entry = entry.next;
  86                                 }
  87                         } else {
  88                                 while (entry != null) {
  89                                         if (comparer.Compare (key, entry.key) == 0)
  90                                                 break;
  91                                         prev = entry;
  92                                         entry = entry.next;
  93                                 }
  94                         }
  95                         return entry;
  96                 }
  97
  98                 private void AddImpl (object key, object value, DictionaryNode prev)
  99                 {
 100                         //
 101                         // Code in the MCS compiler (doc.cs) appears to depend on the new entry being
 102                         // added at the end, even though we don't promise any such thing.
 103                         // Preferably, this code would just have been:
 104                         //
 105                         //   head = new DictionaryNode (key, value, head);
 106                         //
 107                         if (prev == null)
 108                                 head = new DictionaryNode (key, value, head);
 109                         else
 110                                 prev.next = new DictionaryNode (key, value, prev.next);
 111                         ++count;
 112                         ++version;
 113                 }
 114
 115                 // IEnumerable Interface
 116                 IEnumerator IEnumerable.GetEnumerator ()
 117                 {
 118                         return new DictionaryNodeEnumerator (this);
 119                 }
 120
 121                 // ICollection Interface
 122                 public int Count {
 123                         get { return count; }
 124                 }
 125
 126                 public bool IsSynchronized {
 127                         get { return false; }
 128                 }
 129
 130                 public object SyncRoot {
 131                         get { return this; }
 132                 }
 133
 134                 public void CopyTo (Array array, int index)
 135                 {
 136                         if (array == null)
 137                                 throw new ArgumentNullException ("array", "Array cannot be null.");
 138                         if (index < 0)
 139                                 throw new ArgumentOutOfRangeException ("index", "index is less than 0");
 140                         if (index > array.Length)
 141                                 throw new IndexOutOfRangeException ("index is too large");
 142                         if (Count > array.Length - index)
 143                                 throw new ArgumentException ("Not enough room in the array");
 144
 145                         foreach (DictionaryEntry entry in this)
 146                                 array.SetValue (entry, index++);
 147                 }
 148
 149                 // IDictionary Interface
 150                 public bool IsFixedSize {
 151                         get { return false; }
 152                 }
 153
 154                 public bool IsReadOnly {
 155                         get { return false; }
 156                 }
 157
 158                 // Indexer
 159                 public object this [object key] {
 160                         get {
 161                                 DictionaryNode entry = FindEntry (key);
 162                                 return entry == null ? null : entry.value;
 163                         }
 164
 165                         set {
 166                                 DictionaryNode prev;
 167                                 DictionaryNode entry = FindEntry (key, out prev);
 168                                 if (entry != null)
 169                                         entry.value = value;
 170                                 else
 171                                         AddImpl (key, value, prev);
 172                         }
 173                 }
 174
 175                 public ICollection Keys {
 176                         get { return new DictionaryNodeCollection (this, true); }
 177                 }
 178
 179                 public ICollection Values {
 180                         get { return new DictionaryNodeCollection (this, false); }
 181                 }
 182
 183                 public void Add (object key, object value)
 184                 {
 185                         DictionaryNode prev;
 186                         DictionaryNode entry = FindEntry (key, out prev);
 187                         if (entry != null)
 188                                 throw new ArgumentException ("key", "Duplicate key in add.");
 189
 190                         AddImpl (key, value, prev);
 191                 }
 192
 193                 public void Clear ()
 194                 {
 195                         head = null;
 196                         count = 0;
 197                         version++;
 198                 }
 199
 200                 public bool Contains (object key)
 201                 {
 202                         return FindEntry (key) != null;
 203                 }
 204
 205                 public IDictionaryEnumerator GetEnumerator ()
 206                 {
 207                         return new DictionaryNodeEnumerator (this);
 208                 }
 209
 210                 public void Remove (object key)
 211                 {
 212                         DictionaryNode prev;
 213                         DictionaryNode entry = FindEntry (key, out prev);
 214                         if (entry == null)
 215                                 return;
 216                         if (prev == null)
 217                                 head = entry.next;
 218                         else
 219                                 prev.next = entry.next;
 220                         entry.value = null;
 221                         count--;
 222                         version++;
 223                 }
 224
 225
 226                 [Serializable]
 227                 private class DictionaryNode {
 228                         public object key;
 229                         public object value;
 230                         public DictionaryNode next;
 231                         public DictionaryNode (object key, object value, DictionaryNode next)
 232                         {
 233                                 this.key = key;
 234                                 this.value = value;
 235                                 this.next = next;
 236                         }
 237                 }
 238
 239                 private class DictionaryNodeEnumerator : IEnumerator, IDictionaryEnumerator {
 240                         private ListDictionary dict;
 241                         private bool isAtStart;
 242                         private DictionaryNode current;
 243                         private int version;
 244
 245                         public DictionaryNodeEnumerator (ListDictionary dict)
 246                         {
 247                                 this.dict = dict;
 248                                 version = dict.version;
 249                                 Reset();
 250                         }
 251
 252                         private void FailFast()
 253                         {
 254                                 if (version != dict.version) {
 255                                         throw new InvalidOperationException (
 256                                                 "The ListDictionary's contents changed after this enumerator was instantiated.");
 257                                 }
 258                         }
 259
 260                         public bool MoveNext ()
 261                         {
 262                                 FailFast ();
 263                                 if (current == null && !isAtStart)
 264                                         return false;
 265                                 current = isAtStart ? dict.head : current.next;
 266                                 isAtStart = false;
 267                                 return current != null;
 268                         }
 269
 270                         public void Reset ()
 271                         {
 272                                 FailFast ();
 273                                 isAtStart = true;
 274                                 current = null;
 275                         }
 276
 277                         public object Current {
 278                                 get { return Entry; }
 279                         }
 280
 281                         private DictionaryNode DictionaryNode {
 282                                 get {
 283                                         FailFast ();
 284                                         if (current == null)
 285                                                 throw new InvalidOperationException (
 286                                                         "Enumerator is positioned before the collection's first element or after the last element.");
 287                                         return current;
 288                                 }
 289                         }
 290
 291                         // IDictionaryEnumerator
 292                         public DictionaryEntry Entry {
 293                                 get {
 294                                         object key = DictionaryNode.key;
 295                                         return new DictionaryEntry (key, current.value);
 296                                 }
 297                         }
 298
 299                         public object Key {
 300                                 get { return DictionaryNode.key; }
 301                         }
 302
 303                         public object Value {
 304                                 get { return DictionaryNode.value; }
 305                         }
 306                 }
 307
 308                 private class DictionaryNodeCollection : ICollection {
 309                         private ListDictionary dict;
 310                         private bool isKeyList;
 311
 312                         public DictionaryNodeCollection (ListDictionary dict, bool isKeyList)
 313                         {
 314                                 this.dict = dict;
 315                                 this.isKeyList = isKeyList;
 316                         }
 317
 318                         // ICollection Interface
 319                         public int Count {
 320                                 get { return dict.Count; }
 321                         }
 322
 323                         public bool IsSynchronized {
 324                                 get { return false; }
 325                         }
 326
 327                         public object SyncRoot {
 328                                 get { return dict.SyncRoot; }
 329                         }
 330
 331                         public void CopyTo (Array array, int index)
 332                         {
 333                                 if (array == null)
 334                                         throw new ArgumentNullException ("array", "Array cannot be null.");
 335                                 if (index < 0)
 336                                         throw new ArgumentOutOfRangeException ("index", "index is less than 0");
 337                                 if (index > array.Length)
 338                                         throw new IndexOutOfRangeException ("index is too large");
 339                                 if (Count > array.Length - index)
 340                                         throw new ArgumentException ("Not enough room in the array");
 341
 342                                 foreach (object obj in this)
 343                                         array.SetValue (obj, index++);
 344                         }
 345
 346                         // IEnumerable Interface
 347                         public IEnumerator GetEnumerator()
 348                         {
 349                                 return new DictionaryNodeCollectionEnumerator (dict.GetEnumerator (), isKeyList);
 350                         }
 351
 352                         private class DictionaryNodeCollectionEnumerator : IEnumerator {
 353                                 private IDictionaryEnumerator inner;
 354                                 private bool isKeyList;
 355
 356                                 public DictionaryNodeCollectionEnumerator (IDictionaryEnumerator inner, bool isKeyList)
 357                                 {
 358                                         this.inner = inner;
 359                                         this.isKeyList = isKeyList;
 360                                 }
 361
 362                                 public object Current {
 363                                         get { return isKeyList ? inner.Key : inner.Value; }
 364                                 }
 365
 366                                 public bool MoveNext ()
 367                                 {
 368                                         return inner.MoveNext ();
 369                                 }
 370
 371                                 public void Reset ()
 372                                 {
 373                                         inner.Reset ();
 374                                 }
 375                         }
 376                 }
 377         }
 378 }