src/System.Private.CoreLib/src/System/Runtime/InteropServices/WindowsRuntime/ConstantSplittableMap.cs

   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 #nullable enable
   6 using System.Diagnostics;
   7 using System.Collections;
   8 using System.Collections.Generic;
   9
  10 namespace System.Runtime.InteropServices.WindowsRuntime
  11 {
  12     /// <summary>
  13     /// This is a constant map aimed to efficiently support a Split operation (map decomposition).
  14     /// A Split operation returns two non-overlapping, non-empty views of the existing map (or both
  15     /// values are set to NULL). The two views returned should contain roughly the same number of elements.
  16     /// This map is backed by a sorted array. Thus, split operations are O(1) and enumerations are fast;
  17     /// however, look-up in the map are O(log n).
  18     /// </summary>
  19     /// <typeparam name="TKey">Type of objects that act as keys.</typeparam>
  20     /// <typeparam name="TValue">Type of objects that act as entries / values.</typeparam>
  21     [DebuggerDisplay("Count = {Count}")]
  22     internal sealed class ConstantSplittableMap<TKey, TValue> : IMapView<TKey, TValue>
  23     {
  24         private class KeyValuePairComparator : IComparer<KeyValuePair<TKey, TValue>>
  25         {
  26             private static readonly IComparer<TKey> keyComparator = Comparer<TKey>.Default;
  27
  28             public int Compare(KeyValuePair<TKey, TValue> x, KeyValuePair<TKey, TValue> y)
  29             {
  30                 return keyComparator.Compare(x.Key, y.Key);
  31             }
  32         }  // private class KeyValuePairComparator
  33
  34
  35         private static readonly KeyValuePairComparator keyValuePairComparator = new KeyValuePairComparator();
  36
  37         private readonly KeyValuePair<TKey, TValue>[] items;
  38         private readonly int firstItemIndex;
  39         private readonly int lastItemIndex;
  40
  41         internal ConstantSplittableMap(IReadOnlyDictionary<TKey, TValue> data)
  42         {
  43             if (data == null)
  44                 throw new ArgumentNullException(nameof(data));
  45
  46             firstItemIndex = 0;
  47             lastItemIndex = data.Count - 1;
  48             items = CreateKeyValueArray(data.Count, data.GetEnumerator());
  49         }
  50
  51
  52         private ConstantSplittableMap(KeyValuePair<TKey, TValue>[] items, int firstItemIndex, int lastItemIndex)
  53         {
  54             this.items = items;
  55             this.firstItemIndex = firstItemIndex;
  56             this.lastItemIndex = lastItemIndex;
  57         }
  58
  59
  60         private KeyValuePair<TKey, TValue>[] CreateKeyValueArray(int count, IEnumerator<KeyValuePair<TKey, TValue>> data)
  61         {
  62             KeyValuePair<TKey, TValue>[] kvArray = new KeyValuePair<TKey, TValue>[count];
  63
  64             int i = 0;
  65             while (data.MoveNext())
  66                 kvArray[i++] = data.Current;
  67
  68             Array.Sort(kvArray, keyValuePairComparator);
  69
  70             return kvArray;
  71         }
  72
  73
  74         public int Count
  75         {
  76             get
  77             {
  78                 return lastItemIndex - firstItemIndex + 1;
  79             }
  80         }
  81
  82
  83         // [CLSCompliant(false)]
  84         public uint Size
  85         {
  86             get
  87             {
  88                 return (uint)(lastItemIndex - firstItemIndex + 1);
  89             }
  90         }
  91
  92
  93         public TValue Lookup(TKey key)
  94         {
  95             TValue value;
  96             bool found = TryGetValue(key, out value);
  97
  98             if (!found)
  99             {
 100                 Debug.Assert(key != null);
 101                 Exception e = new KeyNotFoundException(SR.Format(SR.Arg_KeyNotFoundWithKey, key.ToString()));
 102                 e.HResult = HResults.E_BOUNDS;
 103                 throw e;
 104             }
 105
 106             return value;
 107         }
 108
 109
 110         public bool HasKey(TKey key)
 111         {
 112             TValue value;
 113             bool hasKey = TryGetValue(key, out value);
 114             return hasKey;
 115         }
 116
 117         IEnumerator IEnumerable.GetEnumerator()
 118         {
 119             return ((IEnumerable<IKeyValuePair<TKey, TValue>>)this).GetEnumerator();
 120         }
 121
 122         public IIterator<IKeyValuePair<TKey, TValue>> First()
 123         {
 124             return new EnumeratorToIteratorAdapter<IKeyValuePair<TKey, TValue>>(GetEnumerator());
 125         }
 126
 127         public IEnumerator<IKeyValuePair<TKey, TValue>> GetEnumerator()
 128         {
 129             return new IKeyValuePairEnumerator(items, firstItemIndex, lastItemIndex);
 130         }
 131
 132         public void Split(out IMapView<TKey, TValue>? firstPartition, out IMapView<TKey, TValue>? secondPartition)
 133         {
 134             if (Count < 2)
 135             {
 136                 firstPartition = null;
 137                 secondPartition = null;
 138                 return;
 139             }
 140
 141             int pivot = (int)(((long)firstItemIndex + (long)lastItemIndex) / (long)2);
 142
 143             firstPartition = new ConstantSplittableMap<TKey, TValue>(items, firstItemIndex, pivot);
 144             secondPartition = new ConstantSplittableMap<TKey, TValue>(items, pivot + 1, lastItemIndex);
 145         }
 146
 147         #region IReadOnlyDictionary members
 148
 149         public bool TryGetValue(TKey key, out TValue value)
 150         {
 151             KeyValuePair<TKey, TValue> searchKey = new KeyValuePair<TKey, TValue>(key, default!); // TODO-NULLABLE-GENERIC
 152             int index = Array.BinarySearch(items, firstItemIndex, Count, searchKey, keyValuePairComparator);
 153
 154             if (index < 0)
 155             {
 156                 value = default!; // TODO-NULLABLE-GENERIC
 157                 return false;
 158             }
 159
 160             value = items[index].Value;
 161             return true;
 162         }
 163
 164         #endregion IReadOnlyDictionary members
 165
 166         #region IKeyValuePair Enumerator
 167
 168         internal struct IKeyValuePairEnumerator : IEnumerator<IKeyValuePair<TKey, TValue>>
 169         {
 170             private KeyValuePair<TKey, TValue>[] _array;
 171             private int _start;
 172             private int _end;
 173             private int _current;
 174
 175             internal IKeyValuePairEnumerator(KeyValuePair<TKey, TValue>[] items, int first, int end)
 176             {
 177                 Debug.Assert(items != null);
 178                 Debug.Assert(first >= 0);
 179                 Debug.Assert(end >= 0);
 180                 Debug.Assert(first < items.Length);
 181                 Debug.Assert(end < items.Length);
 182
 183                 _array = items;
 184                 _start = first;
 185                 _end = end;
 186                 _current = _start - 1;
 187             }
 188
 189             public bool MoveNext()
 190             {
 191                 if (_current < _end)
 192                 {
 193                     _current++;
 194                     return true;
 195                 }
 196                 return false;
 197             }
 198
 199             public IKeyValuePair<TKey, TValue> Current
 200             {
 201                 get
 202                 {
 203                     if (_current < _start) throw new InvalidOperationException(SR.InvalidOperation_EnumNotStarted);
 204                     if (_current > _end) throw new InvalidOperationException(SR.InvalidOperation_EnumEnded);
 205                     return new CLRIKeyValuePairImpl<TKey, TValue>(ref _array[_current]);
 206                 }
 207             }
 208
 209             object? IEnumerator.Current // TODO-NULLABLE:
 210             {
 211                 get
 212                 {
 213                     return Current;
 214                 }
 215             }
 216
 217             void IEnumerator.Reset()
 218             {
 219                 _current = _start - 1;
 220             }
 221
 222             public void Dispose()
 223             {
 224             }
 225         }
 226
 227         #endregion IKeyValuePair Enumerator
 228     }  // internal ConstantSplittableMap<TKey, TValue>
 229 }  // namespace System.Runtime.InteropServices.WindowsRuntime