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