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.Diagnostics; 6 using System.Runtime.Serialization; 7 8 namespace System.Collections.Generic 9 { 10 public partial class SortedSet<T> 11 { 12 /// <summary> 13 /// This class represents a subset view into the tree. Any changes to this view 14 /// are reflected in the actual tree. It uses the comparer of the underlying tree. 15 /// </summary> 16 [Serializable] 17 internal sealed class TreeSubSet : SortedSet<T>, ISerializable, IDeserializationCallback 18 { 19 private SortedSet<T> _underlying; 20 private T _min, _max; 21 // these exist for unbounded collections 22 // for instance, you could allow this subset to be defined for i > 10. The set will throw if 23 // anything <= 10 is added, but there is no upper bound. These features Head(), Tail(), were punted 24 // in the spec, and are not available, but the framework is there to make them available at some point. 25 private bool _lBoundActive, _uBoundActive; 26 // used to see if the count is out of date 27 28 #if DEBUG versionUpToDate()29 internal override bool versionUpToDate() 30 { 31 return (version == _underlying.version); 32 } 33 #endif 34 TreeSubSet(SortedSet<T> Underlying, T Min, T Max, bool lowerBoundActive, bool upperBoundActive)35 public TreeSubSet(SortedSet<T> Underlying, T Min, T Max, bool lowerBoundActive, bool upperBoundActive) 36 : base(Underlying.Comparer) 37 { 38 _underlying = Underlying; 39 _min = Min; 40 _max = Max; 41 _lBoundActive = lowerBoundActive; 42 _uBoundActive = upperBoundActive; 43 root = _underlying.FindRange(_min, _max, _lBoundActive, _uBoundActive); // root is first element within range 44 count = 0; 45 version = -1; 46 VersionCheckImpl(); 47 } 48 AddIfNotPresent(T item)49 internal override bool AddIfNotPresent(T item) 50 { 51 if (!IsWithinRange(item)) 52 { 53 throw new ArgumentOutOfRangeException(nameof(item)); 54 } 55 56 bool ret = _underlying.AddIfNotPresent(item); 57 VersionCheck(); 58 #if DEBUG 59 Debug.Assert(this.versionUpToDate() && root == _underlying.FindRange(_min, _max)); 60 #endif 61 62 return ret; 63 } 64 Contains(T item)65 public override bool Contains(T item) 66 { 67 VersionCheck(); 68 #if DEBUG 69 Debug.Assert(versionUpToDate() && root == _underlying.FindRange(_min, _max)); 70 #endif 71 return base.Contains(item); 72 } 73 DoRemove(T item)74 internal override bool DoRemove(T item) 75 { 76 if (!IsWithinRange(item)) 77 { 78 return false; 79 } 80 81 bool ret = _underlying.Remove(item); 82 VersionCheck(); 83 #if DEBUG 84 Debug.Assert(versionUpToDate() && root == _underlying.FindRange(_min, _max)); 85 #endif 86 return ret; 87 } 88 Clear()89 public override void Clear() 90 { 91 if (count == 0) 92 { 93 return; 94 } 95 96 List<T> toRemove = new List<T>(); 97 BreadthFirstTreeWalk(n => { toRemove.Add(n.Item); return true; }); 98 while (toRemove.Count != 0) 99 { 100 _underlying.Remove(toRemove[toRemove.Count - 1]); 101 toRemove.RemoveAt(toRemove.Count - 1); 102 } 103 104 root = null; 105 count = 0; 106 version = _underlying.version; 107 } 108 IsWithinRange(T item)109 internal override bool IsWithinRange(T item) 110 { 111 int comp = _lBoundActive ? Comparer.Compare(_min, item) : -1; 112 if (comp > 0) 113 { 114 return false; 115 } 116 117 comp = _uBoundActive ? Comparer.Compare(_max, item) : 1; 118 return comp >= 0; 119 } 120 121 internal override T MinInternal 122 { 123 get 124 { 125 Node current = root; 126 T result = default(T); 127 128 while (current != null) 129 { 130 131 int comp = _lBoundActive ? Comparer.Compare(_min, current.Item) : -1; 132 if (comp == 1) 133 { 134 current = current.Right; 135 } 136 else 137 { 138 result = current.Item; 139 if (comp == 0) 140 { 141 break; 142 } 143 current = current.Left; 144 } 145 } 146 147 return result; 148 } 149 } 150 151 internal override T MaxInternal 152 { 153 get 154 { 155 Node current = root; 156 T result = default(T); 157 158 while (current != null) 159 { 160 int comp = _uBoundActive ? Comparer.Compare(_max, current.Item) : 1; 161 if (comp == -1) 162 { 163 current = current.Left; 164 } 165 else 166 { 167 result = current.Item; 168 if (comp == 0) 169 { 170 break; 171 } 172 current = current.Right; 173 } 174 } 175 176 return result; 177 } 178 } 179 InOrderTreeWalk(TreeWalkPredicate<T> action)180 internal override bool InOrderTreeWalk(TreeWalkPredicate<T> action) 181 { 182 VersionCheck(); 183 184 if (root == null) 185 { 186 return true; 187 } 188 189 // The maximum height of a red-black tree is 2*lg(n+1). 190 // See page 264 of "Introduction to algorithms" by Thomas H. Cormen 191 Stack<Node> stack = new Stack<Node>(2 * (int)SortedSet<T>.Log2(count + 1)); // this is not exactly right if count is out of date, but the stack can grow 192 Node current = root; 193 while (current != null) 194 { 195 if (IsWithinRange(current.Item)) 196 { 197 stack.Push(current); 198 current = current.Left; 199 } 200 else if (_lBoundActive && Comparer.Compare(_min, current.Item) > 0) 201 { 202 current = current.Right; 203 } 204 else 205 { 206 current = current.Left; 207 } 208 } 209 210 while (stack.Count != 0) 211 { 212 current = stack.Pop(); 213 if (!action(current)) 214 { 215 return false; 216 } 217 218 Node node = current.Right; 219 while (node != null) 220 { 221 if (IsWithinRange(node.Item)) 222 { 223 stack.Push(node); 224 node = node.Left; 225 } 226 else if (_lBoundActive && Comparer.Compare(_min, node.Item) > 0) 227 { 228 node = node.Right; 229 } 230 else 231 { 232 node = node.Left; 233 } 234 } 235 } 236 return true; 237 } 238 BreadthFirstTreeWalk(TreeWalkPredicate<T> action)239 internal override bool BreadthFirstTreeWalk(TreeWalkPredicate<T> action) 240 { 241 VersionCheck(); 242 243 if (root == null) 244 { 245 return true; 246 } 247 248 Queue<Node> processQueue = new Queue<Node>(); 249 processQueue.Enqueue(root); 250 Node current; 251 252 while (processQueue.Count != 0) 253 { 254 current = processQueue.Dequeue(); 255 if (IsWithinRange(current.Item) && !action(current)) 256 { 257 return false; 258 } 259 if (current.Left != null && (!_lBoundActive || Comparer.Compare(_min, current.Item) < 0)) 260 { 261 processQueue.Enqueue(current.Left); 262 } 263 if (current.Right != null && (!_uBoundActive || Comparer.Compare(_max, current.Item) > 0)) 264 { 265 processQueue.Enqueue(current.Right); 266 } 267 } 268 return true; 269 } 270 FindNode(T item)271 internal override SortedSet<T>.Node FindNode(T item) 272 { 273 if (!IsWithinRange(item)) 274 { 275 return null; 276 } 277 278 VersionCheck(); 279 #if DEBUG 280 Debug.Assert(this.versionUpToDate() && root == _underlying.FindRange(_min, _max)); 281 #endif 282 return base.FindNode(item); 283 } 284 285 // this does indexing in an inefficient way compared to the actual sortedset, but it saves a 286 // lot of space InternalIndexOf(T item)287 internal override int InternalIndexOf(T item) 288 { 289 int count = -1; 290 foreach (T i in this) 291 { 292 count++; 293 if (Comparer.Compare(item, i) == 0) 294 return count; 295 } 296 #if DEBUG 297 Debug.Assert(this.versionUpToDate() && root == _underlying.FindRange(_min, _max)); 298 #endif 299 return -1; 300 } 301 302 /// <summary> 303 /// Checks whether this subset is out of date, and updates it if necessary. 304 /// </summary> VersionCheck()305 internal override void VersionCheck() => VersionCheckImpl(); 306 VersionCheckImpl()307 private void VersionCheckImpl() 308 { 309 Debug.Assert(_underlying != null); 310 if (version != _underlying.version) 311 { 312 root = _underlying.FindRange(_min, _max, _lBoundActive, _uBoundActive); 313 version = _underlying.version; 314 count = 0; 315 InOrderTreeWalk(n => { count++; return true; }); 316 } 317 } 318 319 // This passes functionality down to the underlying tree, clipping edges if necessary 320 // There's nothing gained by having a nested subset. May as well draw it from the base 321 // Cannot increase the bounds of the subset, can only decrease it GetViewBetween(T lowerValue, T upperValue)322 public override SortedSet<T> GetViewBetween(T lowerValue, T upperValue) 323 { 324 if (_lBoundActive && Comparer.Compare(_min, lowerValue) > 0) 325 { 326 throw new ArgumentOutOfRangeException(nameof(lowerValue)); 327 } 328 if (_uBoundActive && Comparer.Compare(_max, upperValue) < 0) 329 { 330 throw new ArgumentOutOfRangeException(nameof(upperValue)); 331 } 332 return (TreeSubSet)_underlying.GetViewBetween(lowerValue, upperValue); 333 } 334 335 #if DEBUG IntersectWithEnumerable(IEnumerable<T> other)336 internal override void IntersectWithEnumerable(IEnumerable<T> other) 337 { 338 base.IntersectWithEnumerable(other); 339 Debug.Assert(versionUpToDate() && root == _underlying.FindRange(_min, _max)); 340 } 341 #endif 342 ISerializable.GetObjectData(SerializationInfo info, StreamingContext context)343 void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context) => GetObjectData(info, context); 344 GetObjectData(SerializationInfo info, StreamingContext context)345 protected override void GetObjectData(SerializationInfo info, StreamingContext context) 346 { 347 throw new PlatformNotSupportedException(); 348 } 349 IDeserializationCallback.OnDeserialization(Object sender)350 void IDeserializationCallback.OnDeserialization(Object sender) 351 { 352 throw new PlatformNotSupportedException(); 353 } 354 355 protected override void OnDeserialization(Object sender) => throw new PlatformNotSupportedException(); 356 } 357 } 358 } 359