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

   1 namespace System.Collections.Specialized\r
   2 {\r
   3         [Serializable]\r
   4         public class ListDictionary : IDictionary, ICollection, IEnumerable\r
   5         {\r
   6                 private int count;\r
   7                 private int modCount;\r
   8                 private ListEntry root;\r
   9                 private IComparer comparer;\r
  10                 \r
  11                 \r
  12                 public ListDictionary()\r
  13                 {\r
  14                         count = 0;\r
  15                         modCount = 0;\r
  16                         comparer = null;\r
  17                         root = null;\r
  18                 }\r
  19                 \r
  20                 public ListDictionary(IComparer comparer) : this()\r
  21                 {\r
  22                         this.comparer = comparer;\r
  23                 }\r
  24                 \r
  25                 private bool AreEqual(object obj1, object obj2)\r
  26                 {\r
  27                         if (comparer != null) {\r
  28                                 if (comparer.Compare(obj1, obj2) == 0) {\r
  29                                         return true;\r
  30                                 }\r
  31                         } else {\r
  32                                 if (obj1.Equals(obj2)) {\r
  33                                         return true;\r
  34                                 }\r
  35                         }\r
  36                         \r
  37                         return false;\r
  38                 }\r
  39                 \r
  40                 private ListEntry FindEntry(object key)\r
  41                 {\r
  42                         if (key == null) {\r
  43                                 throw new ArgumentNullException("Attempted lookup for a null key.");\r
  44                         }\r
  45                         \r
  46                         if (root == null) {\r
  47                                 return null;\r
  48                         } else {\r
  49                                 ListEntry entry = root;\r
  50                                 \r
  51                                 while (entry != null) {\r
  52                                         if (AreEqual(key, entry.key)) {\r
  53                                                 return entry;\r
  54                                         }\r
  55                                         \r
  56                                         entry = entry.next;\r
  57                                 }\r
  58                         }\r
  59                         \r
  60                         return null;\r
  61                 }\r
  62 \r
  63                 private void AddImpl(object key, object value)\r
  64                 {\r
  65                         if (key == null) {\r
  66                                 throw new ArgumentNullException("Attempted add with a null key.");\r
  67                         }\r
  68                         \r
  69                         if (root == null) {\r
  70                                 root = new ListEntry();\r
  71                                 root.key = key;\r
  72                                 root.value = value;\r
  73                         } else {\r
  74                                 ListEntry entry = root;\r
  75                                 \r
  76                                 while (entry != null) {\r
  77                                         if (AreEqual(key, entry.key)) {\r
  78                                                 throw new ArgumentException("Duplicate key in add.");\r
  79                                         }\r
  80                                         \r
  81                                         if (entry.next == null) {\r
  82                                                 break;\r
  83                                         }\r
  84                                         \r
  85                                         entry = entry.next;\r
  86                                 }\r
  87                                 \r
  88                                 entry.next = new ListEntry();\r
  89                                 entry.next.key = key;\r
  90                                 entry.next.value = value;\r
  91                         }\r
  92                         \r
  93                         count++;\r
  94                         modCount++;\r
  95                 }\r
  96                 \r
  97                 // IEnumerable Interface\r
  98                 IEnumerator IEnumerable.GetEnumerator()\r
  99                 {\r
 100                         return new ListEntryEnumerator(this);\r
 101                 }\r
 102                 \r
 103                 // ICollection Interface\r
 104                 public int Count {\r
 105                         get {\r
 106                                 return count;\r
 107                         }\r
 108                 }\r
 109                 \r
 110                 public bool IsSynchronized {\r
 111                         get {\r
 112                                 return false;\r
 113                         }\r
 114                 }\r
 115                 \r
 116                 public object SyncRoot {\r
 117                         get {\r
 118                                 return this;\r
 119                         }\r
 120                 }\r
 121 \r
 122                 public void CopyTo(Array array, int index)\r
 123                 {\r
 124                         if (array == null)\r
 125                                 throw new ArgumentNullException(\r
 126                                         "array",\r
 127                                         "Array cannot be null.");\r
 128 \r
 129                         if (index < 0)\r
 130                                 throw new ArgumentOutOfRangeException("index", "index is less than 0");\r
 131 \r
 132                         int i = index;\r
 133                         foreach ( DictionaryEntry entry in this )\r
 134                                 array.SetValue( entry, i++ );\r
 135                 }\r
 136                 \r
 137                 // IDictionary Interface\r
 138                 public bool IsFixedSize\r
 139                 {\r
 140                         get {\r
 141                                 return false;\r
 142                         }\r
 143                 }\r
 144                 \r
 145                 public bool IsReadOnly\r
 146                 {\r
 147                         get {\r
 148                                 return false;\r
 149                         }\r
 150                 }\r
 151                 \r
 152                 // Indexer\r
 153                 public object this[object key]\r
 154                 {\r
 155                         get {\r
 156                                 ListEntry entry = FindEntry(key);\r
 157                                 return entry == null ? entry : entry.value;\r
 158                         }\r
 159                         \r
 160                         set {\r
 161                                 ListEntry entry = FindEntry(key);\r
 162                                 if (entry != null)\r
 163                                         entry.value = value;\r
 164                                 else\r
 165                                         AddImpl(key, value);\r
 166                         }\r
 167                 }\r
 168                 \r
 169                 public ICollection Keys\r
 170                 {\r
 171                         get {\r
 172                                 return new ListEntryCollection(this, true);\r
 173                         }\r
 174                 }\r
 175                 \r
 176                 public ICollection Values\r
 177                 {\r
 178                         get {\r
 179                                 return new ListEntryCollection(this, false);\r
 180                         }\r
 181                 }\r
 182                 \r
 183                 public void Add(object key, object value)\r
 184                 {\r
 185                         AddImpl(key, value);\r
 186                 }\r
 187                 \r
 188                 public void Clear()\r
 189                 {\r
 190                         root = null;\r
 191                         count = 0;\r
 192                         modCount++;\r
 193                 }\r
 194                 \r
 195                 public bool Contains(object key)\r
 196                 {\r
 197                         return FindEntry(key) != null ? true : false;\r
 198                 }\r
 199                 \r
 200                 public IDictionaryEnumerator GetEnumerator()\r
 201                 {\r
 202                         return new ListEntryEnumerator(this);\r
 203                 }\r
 204                 \r
 205                 public void Remove(object key)\r
 206                 {\r
 207                         if (key == null)\r
 208                                 throw new ArgumentNullException(\r
 209                                         "key",\r
 210                                         "Key cannot be null.");\r
 211 \r
 212                         \r
 213                         ListEntry entry = root;\r
 214                         \r
 215                         for (ListEntry prev = null; entry != null; prev = entry, entry = entry.next) {\r
 216                                 if (AreEqual(key, entry.key)) {\r
 217                                         if (prev != null) {\r
 218                                                 prev.next = entry.next;\r
 219                                         } else {\r
 220                                                 root = entry.next;\r
 221                                         }\r
 222                                         \r
 223                                         entry.value = null;\r
 224                                         count--;\r
 225                                         modCount++;\r
 226                                 }\r
 227                         }\r
 228                 }\r
 229                 \r
 230 \r
 231                 private class ListEntry\r
 232                 {\r
 233                         public object key = null;\r
 234                         public object value = null;\r
 235                         public ListEntry next = null;\r
 236                 }\r
 237 \r
 238 \r
 239                 private class ListEntryEnumerator : IEnumerator, IDictionaryEnumerator\r
 240                 {\r
 241                         private ListDictionary dict;\r
 242                         private bool isAtStart;\r
 243                         private ListEntry current;\r
 244                         private int version;\r
 245                         \r
 246                         public ListEntryEnumerator(ListDictionary dict)\r
 247                         {\r
 248                                 this.dict = dict;\r
 249                                 version = dict.modCount;\r
 250                                 Reset();\r
 251                         }\r
 252 \r
 253                         private void FailFast()\r
 254                         {\r
 255                                 if (version != dict.modCount) {\r
 256                                         throw new InvalidOperationException(\r
 257                                                 "The ListDictionary's contents changed after this enumerator was instantiated.");\r
 258                                 }\r
 259                         }\r
 260                                 \r
 261                         public bool MoveNext()\r
 262                         {\r
 263                                 FailFast();\r
 264                                 \r
 265                                 if (isAtStart) {\r
 266                                         current = dict.root;\r
 267                                         isAtStart = false;\r
 268                                 } else {\r
 269                                         current = current.next;\r
 270                                 }\r
 271                                 \r
 272                                 return current != null ? true : false;  \r
 273                         }\r
 274                         \r
 275                         public void Reset()\r
 276                         {\r
 277                                 FailFast();\r
 278 \r
 279                                 isAtStart = true;\r
 280                                 current = null;\r
 281                         }\r
 282                         \r
 283                         public object Current\r
 284                         {\r
 285                                 get {\r
 286                                         FailFast();\r
 287                                         \r
 288                                         if (isAtStart || current == null) {\r
 289                                                 throw new InvalidOperationException(\r
 290                                                         "Enumerator is positioned before the collection's first element or after the last element.");\r
 291                                         }\r
 292                                         \r
 293                                         return new DictionaryEntry(current.key, current.value);\r
 294                                 }\r
 295                         }\r
 296                         \r
 297                         // IDictionaryEnumerator\r
 298                         public DictionaryEntry Entry\r
 299                         {\r
 300                                 get {\r
 301                                         FailFast();\r
 302                                         return (DictionaryEntry) Current;\r
 303                                 }\r
 304                         }\r
 305                         \r
 306                         public object Key\r
 307                         {\r
 308                                 get {\r
 309                                         FailFast();\r
 310                                         \r
 311                                         if (isAtStart || current == null) {\r
 312                                                 throw new InvalidOperationException(\r
 313                                                         "Enumerator is positioned before the collection's first element or after the last element.");\r
 314                                         }\r
 315                                         \r
 316                                         return current.key;\r
 317                                 }\r
 318                         }\r
 319                         \r
 320                         public object Value\r
 321                         {\r
 322                                 get {\r
 323                                         FailFast();\r
 324                                         \r
 325                                         if (isAtStart || current == null) {\r
 326                                                 throw new InvalidOperationException(\r
 327                                                         "Enumerator is positioned before the collection's first element or after the last element.");\r
 328                                         }\r
 329                                         \r
 330                                         return current.value;\r
 331                                 }\r
 332                         }\r
 333                 }\r
 334                 \r
 335                 private class ListEntryCollection : ICollection\r
 336                 {\r
 337                         private ListDictionary dict;\r
 338                         private bool isKeyList;\r
 339                                 \r
 340                         public ListEntryCollection(ListDictionary dict, bool isKeyList)\r
 341                         {\r
 342                                 this.dict = dict;\r
 343                                 this.isKeyList = isKeyList;\r
 344                         }\r
 345                         \r
 346                         // ICollection Interface\r
 347                         public int Count {\r
 348                                 get {\r
 349                                         return dict.Count;\r
 350                                 }\r
 351                         }\r
 352                         \r
 353                         public bool IsSynchronized\r
 354                         {\r
 355                                 get {\r
 356                                         return false;\r
 357                                 }\r
 358                         }\r
 359                         \r
 360                         public object SyncRoot\r
 361                         {\r
 362                                 get {\r
 363                                         return dict.SyncRoot;\r
 364                                 }\r
 365                         }\r
 366 \r
 367                         public void CopyTo(Array array, int index)\r
 368                         {\r
 369                                 int i = index;\r
 370                                 foreach ( object obj in this )\r
 371                                         array.SetValue( obj, i++ );\r
 372                         }\r
 373                         \r
 374                         // IEnumerable Interface\r
 375                         public IEnumerator GetEnumerator()\r
 376                         {\r
 377                                 return new ListEntryCollectionEnumerator(dict, isKeyList);\r
 378                         }\r
 379                         \r
 380                         private class ListEntryCollectionEnumerator : IEnumerator\r
 381                         {\r
 382                                 private ListDictionary dict;\r
 383                                 private bool isKeyList;\r
 384                                 private bool isAtStart;\r
 385                                 private int version;\r
 386                                 private ListEntry current;\r
 387                                         \r
 388                                 public ListEntryCollectionEnumerator(ListDictionary dict, bool isKeyList)\r
 389                                 {\r
 390                                         this.dict = dict;\r
 391                                         this.isKeyList = isKeyList;\r
 392                                         isAtStart = true;\r
 393                                         version = dict.modCount;\r
 394                                 }\r
 395 \r
 396                                 private void FailFast()\r
 397                                 {\r
 398                                         if (version != dict.modCount) {\r
 399                                                 throw new InvalidOperationException(\r
 400                                                         "The Collection's contents changed after this " +\r
 401                                                         "enumerator was instantiated.");\r
 402                                         }\r
 403                                 }\r
 404                                 \r
 405                                 public object Current\r
 406                                 {\r
 407                                         get {\r
 408                                                 FailFast();\r
 409                                                 \r
 410                                                 if (isAtStart || current == null) {\r
 411                                                         throw new InvalidOperationException(\r
 412                                                                 "Enumerator is positioned before the collection's " +\r
 413                                                                 "first element or after the last element.");\r
 414                                                 }\r
 415                                                 \r
 416                                                 return isKeyList ? current.key : current.value;\r
 417                                         }\r
 418                                 }\r
 419                                 \r
 420                                 public bool MoveNext()\r
 421                                 {\r
 422                                         FailFast();\r
 423                                         \r
 424                                         if (isAtStart) {\r
 425                                                 current = dict.root;\r
 426                                                 isAtStart = false;\r
 427                                         } else {\r
 428                                                 current = current.next;\r
 429                                         }\r
 430                                         \r
 431                                         return current != null ? true : false;\r
 432                                 }\r
 433                                 \r
 434                                 public void Reset()\r
 435                                 {\r
 436                                         FailFast();\r
 437                                         isAtStart = true;\r
 438                                         current = null;\r
 439                                 }\r
 440                         }\r
 441                 }\r
 442         }\r
 443 }\r