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