1 // Licensed to the .NET Foundation under one or more agreements. 2 // The .NET Foundation licenses this file to you under the MIT license. 3 // See the LICENSE file in the project root for more information. 4 5 using System.Collections.Generic; 6 using System.Diagnostics; 7 using System.Diagnostics.CodeAnalysis; 8 using System.Diagnostics.Contracts; 9 10 namespace System.Collections.Immutable 11 { 12 /// <content> 13 /// Contains the inner <see cref="ImmutableSortedDictionary{TKey, TValue}.Builder"/> class. 14 /// </content> 15 [SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix", Justification = "Ignored")] 16 public sealed partial class ImmutableSortedDictionary<TKey, TValue> 17 { 18 /// <summary> 19 /// A sorted dictionary that mutates with little or no memory allocations, 20 /// can produce and/or build on immutable sorted dictionary instances very efficiently. 21 /// </summary> 22 /// <remarks> 23 /// <para> 24 /// This class allows multiple combinations of changes to be made to a set with equal efficiency. 25 /// </para> 26 /// <para> 27 /// Instance members of this class are <em>not</em> thread-safe. 28 /// </para> 29 /// </remarks> 30 [SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix", Justification = "Ignored")] 31 [SuppressMessage("Microsoft.Design", "CA1034:NestedTypesShouldNotBeVisible", Justification = "Ignored")] 32 [DebuggerDisplay("Count = {Count}")] 33 [DebuggerTypeProxy(typeof(ImmutableSortedDictionaryBuilderDebuggerProxy<,>))] 34 public sealed class Builder : IDictionary<TKey, TValue>, IReadOnlyDictionary<TKey, TValue>, IDictionary 35 { 36 /// <summary> 37 /// The binary tree used to store the contents of the map. Contents are typically not entirely frozen. 38 /// </summary> 39 private Node _root = Node.EmptyNode; 40 41 /// <summary> 42 /// The key comparer. 43 /// </summary> 44 private IComparer<TKey> _keyComparer = Comparer<TKey>.Default; 45 46 /// <summary> 47 /// The value comparer. 48 /// </summary> 49 private IEqualityComparer<TValue> _valueComparer = EqualityComparer<TValue>.Default; 50 51 /// <summary> 52 /// The number of entries in the map. 53 /// </summary> 54 private int _count; 55 56 /// <summary> 57 /// Caches an immutable instance that represents the current state of the collection. 58 /// </summary> 59 /// <value>Null if no immutable view has been created for the current version.</value> 60 private ImmutableSortedDictionary<TKey, TValue> _immutable; 61 62 /// <summary> 63 /// A number that increments every time the builder changes its contents. 64 /// </summary> 65 private int _version; 66 67 /// <summary> 68 /// The object callers may use to synchronize access to this collection. 69 /// </summary> 70 private object _syncRoot; 71 72 /// <summary> 73 /// Initializes a new instance of the <see cref="Builder"/> class. 74 /// </summary> 75 /// <param name="map">A map to act as the basis for a new map.</param> Builder(ImmutableSortedDictionary<TKey, TValue> map)76 internal Builder(ImmutableSortedDictionary<TKey, TValue> map) 77 { 78 Requires.NotNull(map, nameof(map)); 79 _root = map._root; 80 _keyComparer = map.KeyComparer; 81 _valueComparer = map.ValueComparer; 82 _count = map.Count; 83 _immutable = map; 84 } 85 86 #region IDictionary<TKey, TValue> Properties and Indexer 87 88 /// <summary> 89 /// See <see cref="IDictionary{TKey, TValue}"/> 90 /// </summary> 91 ICollection<TKey> IDictionary<TKey, TValue>.Keys 92 { 93 get { return this.Root.Keys.ToArray(this.Count); } 94 } 95 96 /// <summary> 97 /// See <see cref="IReadOnlyDictionary{TKey, TValue}"/> 98 /// </summary> 99 public IEnumerable<TKey> Keys 100 { 101 get { return this.Root.Keys; } 102 } 103 104 /// <summary> 105 /// See <see cref="IDictionary{TKey, TValue}"/> 106 /// </summary> 107 ICollection<TValue> IDictionary<TKey, TValue>.Values 108 { 109 get { return this.Root.Values.ToArray(this.Count); } 110 } 111 112 /// <summary> 113 /// See <see cref="IReadOnlyDictionary{TKey, TValue}"/> 114 /// </summary> 115 public IEnumerable<TValue> Values 116 { 117 get { return this.Root.Values; } 118 } 119 120 /// <summary> 121 /// Gets the number of elements in this map. 122 /// </summary> 123 public int Count 124 { 125 get { return _count; } 126 } 127 128 /// <summary> 129 /// Gets a value indicating whether this instance is read-only. 130 /// </summary> 131 /// <value>Always <c>false</c>.</value> 132 bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly 133 { 134 get { return false; } 135 } 136 137 #endregion 138 139 /// <summary> 140 /// Gets the current version of the contents of this builder. 141 /// </summary> 142 internal int Version 143 { 144 get { return _version; } 145 } 146 147 /// <summary> 148 /// Gets or sets the root node that represents the data in this collection. 149 /// </summary> 150 private Node Root 151 { 152 get 153 { 154 return _root; 155 } 156 157 set 158 { 159 // We *always* increment the version number because some mutations 160 // may not create a new value of root, although the existing root 161 // instance may have mutated. 162 _version++; 163 164 if (_root != value) 165 { 166 _root = value; 167 168 // Clear any cached value for the immutable view since it is now invalidated. 169 _immutable = null; 170 } 171 } 172 } 173 174 #region IDictionary<TKey, TValue> Indexer 175 176 /// <summary> 177 /// Gets or sets the value for a given key. 178 /// </summary> 179 /// <param name="key">The key.</param> 180 /// <returns>The value associated with the given key.</returns> 181 public TValue this[TKey key] 182 { 183 get 184 { 185 TValue value; 186 if (this.TryGetValue(key, out value)) 187 { 188 return value; 189 } 190 191 throw new KeyNotFoundException(SR.Format(SR.Arg_KeyNotFoundWithKey, key.ToString())); 192 } 193 194 set 195 { 196 bool replacedExistingValue, mutated; 197 this.Root = _root.SetItem(key, value, _keyComparer, _valueComparer, out replacedExistingValue, out mutated); 198 if (mutated && !replacedExistingValue) 199 { 200 _count++; 201 } 202 } 203 } 204 205 #if FEATURE_ITEMREFAPI 206 /// <summary> 207 /// Returns a read-only reference to the value associated with the provided key. 208 /// </summary> 209 /// <exception cref="KeyNotFoundException">If the key is not present.</exception> ValueRef(TKey key)210 public ref readonly TValue ValueRef(TKey key) 211 { 212 Requires.NotNullAllowStructs(key, nameof(key)); 213 214 return ref _root.ValueRef(key, _keyComparer); 215 } 216 #endif 217 218 #endregion 219 220 #region IDictionary Properties 221 222 /// <summary> 223 /// Gets a value indicating whether the <see cref="IDictionary"/> object has a fixed size. 224 /// </summary> 225 /// <returns>true if the <see cref="IDictionary"/> object has a fixed size; otherwise, false.</returns> 226 bool IDictionary.IsFixedSize 227 { 228 get { return false; } 229 } 230 231 /// <summary> 232 /// Gets a value indicating whether the <see cref="ICollection{T}"/> is read-only. 233 /// </summary> 234 /// <returns>true if the <see cref="ICollection{T}"/> is read-only; otherwise, false. 235 /// </returns> 236 bool IDictionary.IsReadOnly 237 { 238 get { return false; } 239 } 240 241 /// <summary> 242 /// Gets an <see cref="ICollection{T}"/> containing the keys of the <see cref="IDictionary{TKey, TValue}"/>. 243 /// </summary> 244 /// <returns> 245 /// An <see cref="ICollection{T}"/> containing the keys of the object that implements <see cref="IDictionary{TKey, TValue}"/>. 246 /// </returns> 247 ICollection IDictionary.Keys 248 { 249 get { return this.Keys.ToArray(this.Count); } 250 } 251 252 /// <summary> 253 /// Gets an <see cref="ICollection{T}"/> containing the values in the <see cref="IDictionary{TKey, TValue}"/>. 254 /// </summary> 255 /// <returns> 256 /// An <see cref="ICollection{T}"/> containing the values in the object that implements <see cref="IDictionary{TKey, TValue}"/>. 257 /// </returns> 258 ICollection IDictionary.Values 259 { 260 get { return this.Values.ToArray(this.Count); } 261 } 262 263 #endregion 264 265 #region ICollection Properties 266 267 /// <summary> 268 /// Gets an object that can be used to synchronize access to the <see cref="ICollection"/>. 269 /// </summary> 270 /// <returns>An object that can be used to synchronize access to the <see cref="ICollection"/>.</returns> 271 [DebuggerBrowsable(DebuggerBrowsableState.Never)] 272 object ICollection.SyncRoot 273 { 274 get 275 { 276 if (_syncRoot == null) 277 { 278 Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null); 279 } 280 281 return _syncRoot; 282 } 283 } 284 285 /// <summary> 286 /// Gets a value indicating whether access to the <see cref="ICollection"/> is synchronized (thread safe). 287 /// </summary> 288 /// <returns>true if access to the <see cref="ICollection"/> is synchronized (thread safe); otherwise, false.</returns> 289 [DebuggerBrowsable(DebuggerBrowsableState.Never)] 290 bool ICollection.IsSynchronized 291 { 292 get { return false; } 293 } 294 295 /// <summary> 296 /// Gets or sets the key comparer. 297 /// </summary> 298 /// <value> 299 /// The key comparer. 300 /// </value> 301 public IComparer<TKey> KeyComparer 302 { 303 get 304 { 305 return _keyComparer; 306 } 307 308 set 309 { 310 Requires.NotNull(value, nameof(value)); 311 if (value != _keyComparer) 312 { 313 var newRoot = Node.EmptyNode; 314 int count = 0; 315 foreach (var item in this) 316 { 317 bool mutated; 318 newRoot = newRoot.Add(item.Key, item.Value, value, _valueComparer, out mutated); 319 if (mutated) 320 { 321 count++; 322 } 323 } 324 325 _keyComparer = value; 326 this.Root = newRoot; 327 _count = count; 328 } 329 } 330 } 331 332 /// <summary> 333 /// Gets or sets the value comparer. 334 /// </summary> 335 /// <value> 336 /// The value comparer. 337 /// </value> 338 public IEqualityComparer<TValue> ValueComparer 339 { 340 get 341 { 342 return _valueComparer; 343 } 344 345 set 346 { 347 Requires.NotNull(value, nameof(value)); 348 if (value != _valueComparer) 349 { 350 // When the key comparer is the same but the value comparer is different, we don't need a whole new tree 351 // because the structure of the tree does not depend on the value comparer. 352 // We just need a new root node to store the new value comparer. 353 _valueComparer = value; 354 _immutable = null; // invalidate cached immutable 355 } 356 } 357 } 358 359 #endregion 360 361 #region IDictionary Methods 362 363 /// <summary> 364 /// Adds an element with the provided key and value to the <see cref="IDictionary"/> object. 365 /// </summary> 366 /// <param name="key">The <see cref="object"/> to use as the key of the element to add.</param> 367 /// <param name="value">The <see cref="object"/> to use as the value of the element to add.</param> IDictionary.Add(object key, object value)368 void IDictionary.Add(object key, object value) 369 { 370 this.Add((TKey)key, (TValue)value); 371 } 372 373 /// <summary> 374 /// Determines whether the <see cref="IDictionary"/> object contains an element with the specified key. 375 /// </summary> 376 /// <param name="key">The key to locate in the <see cref="IDictionary"/> object.</param> 377 /// <returns> 378 /// true if the <see cref="IDictionary"/> contains an element with the key; otherwise, false. 379 /// </returns> IDictionary.Contains(object key)380 bool IDictionary.Contains(object key) 381 { 382 return this.ContainsKey((TKey)key); 383 } 384 385 /// <summary> 386 /// Returns an <see cref="IDictionaryEnumerator"/> object for the <see cref="IDictionary"/> object. 387 /// </summary> 388 /// <returns> 389 /// An <see cref="IDictionaryEnumerator"/> object for the <see cref="IDictionary"/> object. 390 /// </returns> IDictionary.GetEnumerator()391 IDictionaryEnumerator IDictionary.GetEnumerator() 392 { 393 return new DictionaryEnumerator<TKey, TValue>(this.GetEnumerator()); 394 } 395 396 /// <summary> 397 /// Removes the element with the specified key from the <see cref="IDictionary"/> object. 398 /// </summary> 399 /// <param name="key">The key of the element to remove.</param> IDictionary.Remove(object key)400 void IDictionary.Remove(object key) 401 { 402 this.Remove((TKey)key); 403 } 404 405 /// <summary> 406 /// Gets or sets the element with the specified key. 407 /// </summary> 408 /// <param name="key">The key.</param> 409 /// <returns></returns> 410 object IDictionary.this[object key] 411 { 412 get { return this[(TKey)key]; } 413 set { this[(TKey)key] = (TValue)value; } 414 } 415 416 #endregion 417 418 #region ICollection methods 419 420 /// <summary> 421 /// Copies the elements of the <see cref="ICollection"/> to an <see cref="Array"/>, starting at a particular <see cref="Array"/> index. 422 /// </summary> 423 /// <param name="array">The one-dimensional <see cref="Array"/> that is the destination of the elements copied from <see cref="ICollection"/>. The <see cref="Array"/> must have zero-based indexing.</param> 424 /// <param name="index">The zero-based index in <paramref name="array"/> at which copying begins.</param> ICollection.CopyTo(Array array, int index)425 void ICollection.CopyTo(Array array, int index) 426 { 427 this.Root.CopyTo(array, index, this.Count); 428 } 429 430 #endregion 431 432 #region IDictionary<TKey, TValue> Methods 433 434 /// <summary> 435 /// See <see cref="IDictionary{TKey, TValue}"/> 436 /// </summary> Add(TKey key, TValue value)437 public void Add(TKey key, TValue value) 438 { 439 bool mutated; 440 this.Root = this.Root.Add(key, value, _keyComparer, _valueComparer, out mutated); 441 if (mutated) 442 { 443 _count++; 444 } 445 } 446 447 /// <summary> 448 /// See <see cref="IDictionary{TKey, TValue}"/> 449 /// </summary> ContainsKey(TKey key)450 public bool ContainsKey(TKey key) 451 { 452 return this.Root.ContainsKey(key, _keyComparer); 453 } 454 455 /// <summary> 456 /// See <see cref="IDictionary{TKey, TValue}"/> 457 /// </summary> Remove(TKey key)458 public bool Remove(TKey key) 459 { 460 bool mutated; 461 this.Root = this.Root.Remove(key, _keyComparer, out mutated); 462 if (mutated) 463 { 464 _count--; 465 } 466 467 return mutated; 468 } 469 470 /// <summary> 471 /// See <see cref="IDictionary{TKey, TValue}"/> 472 /// </summary> TryGetValue(TKey key, out TValue value)473 public bool TryGetValue(TKey key, out TValue value) 474 { 475 return this.Root.TryGetValue(key, _keyComparer, out value); 476 } 477 478 /// <summary> 479 /// See the <see cref="IImmutableDictionary{TKey, TValue}"/> interface. 480 /// </summary> TryGetKey(TKey equalKey, out TKey actualKey)481 public bool TryGetKey(TKey equalKey, out TKey actualKey) 482 { 483 Requires.NotNullAllowStructs(equalKey, nameof(equalKey)); 484 return this.Root.TryGetKey(equalKey, _keyComparer, out actualKey); 485 } 486 487 /// <summary> 488 /// See <see cref="IDictionary{TKey, TValue}"/> 489 /// </summary> Add(KeyValuePair<TKey, TValue> item)490 public void Add(KeyValuePair<TKey, TValue> item) 491 { 492 this.Add(item.Key, item.Value); 493 } 494 495 /// <summary> 496 /// See <see cref="IDictionary{TKey, TValue}"/> 497 /// </summary> Clear()498 public void Clear() 499 { 500 this.Root = ImmutableSortedDictionary<TKey, TValue>.Node.EmptyNode; 501 _count = 0; 502 } 503 504 /// <summary> 505 /// See <see cref="IDictionary{TKey, TValue}"/> 506 /// </summary> Contains(KeyValuePair<TKey, TValue> item)507 public bool Contains(KeyValuePair<TKey, TValue> item) 508 { 509 return this.Root.Contains(item, _keyComparer, _valueComparer); 510 } 511 512 /// <summary> 513 /// See <see cref="IDictionary{TKey, TValue}"/> 514 /// </summary> CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)515 void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex) 516 { 517 this.Root.CopyTo(array, arrayIndex, this.Count); 518 } 519 520 /// <summary> 521 /// See <see cref="IDictionary{TKey, TValue}"/> 522 /// </summary> Remove(KeyValuePair<TKey, TValue> item)523 public bool Remove(KeyValuePair<TKey, TValue> item) 524 { 525 if (this.Contains(item)) 526 { 527 return this.Remove(item.Key); 528 } 529 530 return false; 531 } 532 533 /// <summary> 534 /// See <see cref="IDictionary{TKey, TValue}"/> 535 /// </summary> GetEnumerator()536 public ImmutableSortedDictionary<TKey, TValue>.Enumerator GetEnumerator() 537 { 538 return this.Root.GetEnumerator(this); 539 } 540 541 /// <summary> 542 /// See <see cref="IDictionary{TKey, TValue}"/> 543 /// </summary> GetEnumerator()544 IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator() 545 { 546 return this.GetEnumerator(); 547 } 548 549 /// <summary> 550 /// See <see cref="IDictionary{TKey, TValue}"/> 551 /// </summary> IEnumerable.GetEnumerator()552 IEnumerator IEnumerable.GetEnumerator() 553 { 554 return this.GetEnumerator(); 555 } 556 557 #endregion 558 559 #region Public methods 560 561 /// <summary> 562 /// Determines whether the <see cref="ImmutableSortedDictionary{TKey, TValue}"/> 563 /// contains an element with the specified value. 564 /// </summary> 565 /// <param name="value"> 566 /// The value to locate in the <see cref="ImmutableSortedDictionary{TKey, TValue}"/>. 567 /// The value can be null for reference types. 568 /// </param> 569 /// <returns> 570 /// true if the <see cref="ImmutableSortedDictionary{TKey, TValue}"/> contains 571 /// an element with the specified value; otherwise, false. 572 /// </returns> 573 [Pure] ContainsValue(TValue value)574 public bool ContainsValue(TValue value) 575 { 576 return _root.ContainsValue(value, _valueComparer); 577 } 578 579 /// <summary> 580 /// Removes any entries from the dictionaries with keys that match those found in the specified sequence. 581 /// </summary> 582 /// <param name="items">The keys for entries to remove from the dictionary.</param> 583 [SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures")] AddRange(IEnumerable<KeyValuePair<TKey, TValue>> items)584 public void AddRange(IEnumerable<KeyValuePair<TKey, TValue>> items) 585 { 586 Requires.NotNull(items, nameof(items)); 587 588 foreach (var pair in items) 589 { 590 this.Add(pair); 591 } 592 } 593 594 /// <summary> 595 /// Removes any entries from the dictionaries with keys that match those found in the specified sequence. 596 /// </summary> 597 /// <param name="keys">The keys for entries to remove from the dictionary.</param> RemoveRange(IEnumerable<TKey> keys)598 public void RemoveRange(IEnumerable<TKey> keys) 599 { 600 Requires.NotNull(keys, nameof(keys)); 601 602 foreach (var key in keys) 603 { 604 this.Remove(key); 605 } 606 } 607 608 /// <summary> 609 /// Gets the value for a given key if a matching key exists in the dictionary. 610 /// </summary> 611 /// <param name="key">The key to search for.</param> 612 /// <returns>The value for the key, or the default value for type <typeparamref name="TValue"/> if no matching key was found.</returns> 613 [Pure] GetValueOrDefault(TKey key)614 public TValue GetValueOrDefault(TKey key) 615 { 616 return this.GetValueOrDefault(key, default(TValue)); 617 } 618 619 /// <summary> 620 /// Gets the value for a given key if a matching key exists in the dictionary. 621 /// </summary> 622 /// <param name="key">The key to search for.</param> 623 /// <param name="defaultValue">The default value to return if no matching key is found in the dictionary.</param> 624 /// <returns> 625 /// The value for the key, or <paramref name="defaultValue"/> if no matching key was found. 626 /// </returns> 627 [Pure] GetValueOrDefault(TKey key, TValue defaultValue)628 public TValue GetValueOrDefault(TKey key, TValue defaultValue) 629 { 630 Requires.NotNullAllowStructs(key, nameof(key)); 631 632 TValue value; 633 if (this.TryGetValue(key, out value)) 634 { 635 return value; 636 } 637 638 return defaultValue; 639 } 640 641 /// <summary> 642 /// Creates an immutable sorted dictionary based on the contents of this instance. 643 /// </summary> 644 /// <returns>An immutable map.</returns> 645 /// <remarks> 646 /// This method is an O(n) operation, and approaches O(1) time as the number of 647 /// actual mutations to the set since the last call to this method approaches 0. 648 /// </remarks> ToImmutable()649 public ImmutableSortedDictionary<TKey, TValue> ToImmutable() 650 { 651 // Creating an instance of ImmutableSortedMap<T> with our root node automatically freezes our tree, 652 // ensuring that the returned instance is immutable. Any further mutations made to this builder 653 // will clone (and unfreeze) the spine of modified nodes until the next time this method is invoked. 654 if (_immutable == null) 655 { 656 _immutable = Wrap(this.Root, _count, _keyComparer, _valueComparer); 657 } 658 659 return _immutable; 660 } 661 #endregion 662 } 663 } 664 /// <summary> 665 /// A simple view of the immutable collection that the debugger can show to the developer. 666 /// </summary> 667 internal class ImmutableSortedDictionaryBuilderDebuggerProxy<TKey, TValue> 668 { 669 /// <summary> 670 /// The collection to be enumerated. 671 /// </summary> 672 private readonly ImmutableSortedDictionary<TKey, TValue>.Builder _map; 673 674 /// <summary> 675 /// The simple view of the collection. 676 /// </summary> 677 private KeyValuePair<TKey, TValue>[] _contents; 678 679 /// <summary> 680 /// Initializes a new instance of the <see cref="ImmutableSortedDictionaryBuilderDebuggerProxy{TKey, TValue}"/> class. 681 /// </summary> 682 /// <param name="map">The collection to display in the debugger</param> ImmutableSortedDictionaryBuilderDebuggerProxy(ImmutableSortedDictionary<TKey, TValue>.Builder map)683 public ImmutableSortedDictionaryBuilderDebuggerProxy(ImmutableSortedDictionary<TKey, TValue>.Builder map) 684 { 685 Requires.NotNull(map, nameof(map)); 686 _map = map; 687 } 688 689 /// <summary> 690 /// Gets a simple debugger-viewable collection. 691 /// </summary> 692 [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] 693 public KeyValuePair<TKey, TValue>[] Contents 694 { 695 get 696 { 697 if (_contents == null) 698 { 699 _contents = _map.ToArray(_map.Count); 700 } 701 702 return _contents; 703 } 704 } 705 } 706 } 707