首页 > 代码库 > .NET源码 SortedSet(红黑树)

.NET源码 SortedSet(红黑树)

  1. // #define USING_HASH_SET
  2. // ==++==
  3. //
  4. // Copyright (c) Microsoft Corporation. All rights reserved.
  5. //
  6. // ==--==
  7. /*============================================================
  8. **
  9. ** Class: SortedSet
  10. **
  11. ** Purpose: A generic sorted set.
  12. **
  13. ** Date: August 15, 2008
  14. **
  15. ===========================================================*/
  16. namespace System.Collections.Generic {
  17. using System;
  18. using System.Diagnostics;
  19. using System.Diagnostics.CodeAnalysis;
  20. using System.Runtime.Serialization;
  21. //
  22. // A binary search tree is a red-black tree if it satisfies the following red-black properties:
  23. // 1. Every node is either red or black
  24. // 2. Every leaf (nil node) is black
  25. // 3. If a node is red, then both its children are black
  26. // 4. Every simple path from a node to a descendant leaf contains the same number of black nodes
  27. //
  28. // The basic idea of red-black tree is to represent 2-3-4 trees as standard BSTs but to add one extra bit of information
  29. // per node to encode 3-nodes and 4-nodes.
  30. // 4-nodes will be represented as: B
  31. // R R
  32. // 3 -node will be represented as: B or B
  33. // R B B R
  34. //
  35. // For a detailed description of the algorithm, take a look at "Algorithms" by Robert Sedgewick.
  36. //
  37. internal delegate bool TreeWalkPredicate<T>(SortedSet<T>.Node node);
  38. internal enum TreeRotation {
  39. LeftRotation = 1,
  40. RightRotation = 2,
  41. RightLeftRotation = 3,
  42. LeftRightRotation = 4,
  43. }
  44. [SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix", Justification = "by design name choice")]
  45. [DebuggerTypeProxy(typeof(System.Collections.Generic.SortedSetDebugView<>))]
  46. [DebuggerDisplay("Count = {Count}")]
  47. #if !FEATURE_NETCORE
  48. [Serializable]
  49. public class SortedSet<T> : ISet<T>, ICollection<T>, ICollection, ISerializable, IDeserializationCallback, IReadOnlyCollection<T> {
  50. #else
  51. public class SortedSet<T> : ISet<T>, ICollection<T>, ICollection, IReadOnlyCollection<T> {
  52. #endif //!FEATURE_NETCORE
  53. #region local variables/constants
  54. Node root;
  55. IComparer<T> comparer;
  56. int count;
  57. int version;
  58. private Object _syncRoot;
  59. private const String ComparerName = "Comparer";
  60. private const String CountName = "Count";
  61. private const String ItemsName = "Items";
  62. private const String VersionName = "Version";
  63. //needed for enumerator
  64. private const String TreeName = "Tree";
  65. private const String NodeValueName = "Item";
  66. private const String EnumStartName = "EnumStarted";
  67. private const String ReverseName = "Reverse";
  68. private const String EnumVersionName = "EnumVersion";
  69. #if !FEATURE_NETCORE
  70. //needed for TreeSubset
  71. private const String minName = "Min";
  72. private const String maxName = "Max";
  73. private const String lBoundActiveName = "lBoundActive";
  74. private const String uBoundActiveName = "uBoundActive";
  75. private SerializationInfo siInfo; //A temporary variable which we need during deserialization.
  76. #endif
  77. internal const int StackAllocThreshold = 100;
  78. #endregion
  79. #region Constructors
  80. public SortedSet() {
  81. this.comparer = Comparer<T>.Default;
  82. }
  83. public SortedSet(IComparer<T> comparer) {
  84. if (comparer == null) {
  85. this.comparer = Comparer<T>.Default;
  86. } else {
  87. this.comparer = comparer;
  88. }
  89. }
  90. public SortedSet(IEnumerable<T> collection) : this(collection, Comparer<T>.Default) { }
  91. public SortedSet(IEnumerable<T> collection, IComparer<T> comparer)
  92. : this(comparer) {
  93. if (collection == null) {
  94. throw new ArgumentNullException("collection");
  95. }
  96. // these are explicit type checks in the mould of HashSet. It would have worked better
  97. // with something like an ISorted<T> (we could make this work for SortedList.Keys etc)
  98. SortedSet<T> baseSortedSet = collection as SortedSet<T>;
  99. SortedSet<T> baseTreeSubSet = collection as TreeSubSet;
  100. if (baseSortedSet != null && baseTreeSubSet == null && AreComparersEqual(this, baseSortedSet)) {
  101. //breadth first traversal to recreate nodes
  102. if (baseSortedSet.Count == 0) {
  103. count = 0;
  104. version = 0;
  105. root = null;
  106. return;
  107. }
  108. //pre order way to replicate nodes
  109. Stack<Node> theirStack = new Stack<SortedSet<T>.Node>(2 * log2(baseSortedSet.Count) + 2);
  110. Stack<Node> myStack = new Stack<SortedSet<T>.Node>(2 * log2(baseSortedSet.Count) + 2);
  111. Node theirCurrent = baseSortedSet.root;
  112. Node myCurrent = (theirCurrent != null ? new SortedSet<T>.Node(theirCurrent.Item, theirCurrent.IsRed) : null);
  113. root = myCurrent;
  114. while (theirCurrent != null) {
  115. theirStack.Push(theirCurrent);
  116. myStack.Push(myCurrent);
  117. myCurrent.Left = (theirCurrent.Left != null ? new SortedSet<T>.Node(theirCurrent.Left.Item, theirCurrent.Left.IsRed) : null);
  118. theirCurrent = theirCurrent.Left;
  119. myCurrent = myCurrent.Left;
  120. }
  121. while (theirStack.Count != 0) {
  122. theirCurrent = theirStack.Pop();
  123. myCurrent = myStack.Pop();
  124. Node theirRight = theirCurrent.Right;
  125. Node myRight = null;
  126. if (theirRight != null) {
  127. myRight = new SortedSet<T>.Node(theirRight.Item, theirRight.IsRed);
  128. }
  129. myCurrent.Right = myRight;
  130. while (theirRight != null) {
  131. theirStack.Push(theirRight);
  132. myStack.Push(myRight);
  133. myRight.Left = (theirRight.Left != null ? new SortedSet<T>.Node(theirRight.Left.Item, theirRight.Left.IsRed) : null);
  134. theirRight = theirRight.Left;
  135. myRight = myRight.Left;
  136. }
  137. }
  138. count = baseSortedSet.count;
  139. version = 0;
  140. } else { //As it stands, you‘re doing an NlogN sort of the collection
  141. List<T> els = new List<T>(collection);
  142. els.Sort(this.comparer);
  143. for (int i = 1; i < els.Count; i++) {
  144. if (comparer.Compare(els[i], els[i - 1]) == 0) {
  145. els.RemoveAt(i);
  146. i--;
  147. }
  148. }
  149. root = ConstructRootFromSortedArray(els.ToArray(), 0, els.Count - 1, null);
  150. count = els.Count;
  151. version = 0;
  152. }
  153. }
  154. #if !FEATURE_NETCORE
  155. protected SortedSet(SerializationInfo info, StreamingContext context) {
  156. siInfo = info;
  157. }
  158. #endif
  159. #endregion
  160. #region Bulk Operation Helpers
  161. private void AddAllElements(IEnumerable<T> collection) {
  162. foreach (T item in collection) {
  163. if (!this.Contains(item))
  164. Add(item);
  165. }
  166. }
  167. private void RemoveAllElements(IEnumerable<T> collection) {
  168. T min = this.Min;
  169. T max = this.Max;
  170. foreach (T item in collection) {
  171. if (!(comparer.Compare(item, min) < 0 || comparer.Compare(item, max) > 0) && this.Contains(item))
  172. this.Remove(item);
  173. }
  174. }
  175. private bool ContainsAllElements(IEnumerable<T> collection) {
  176. foreach (T item in collection) {
  177. if (!this.Contains(item)) {
  178. return false;
  179. }
  180. }
  181. return true;
  182. }
  183. //
  184. // Do a in order walk on tree and calls the delegate for each node.
  185. // If the action delegate returns false, stop the walk.
  186. //
  187. // Return true if the entire tree has been walked.
  188. // Otherwise returns false.
  189. //
  190. internal bool InOrderTreeWalk(TreeWalkPredicate<T> action) {
  191. return InOrderTreeWalk(action, false);
  192. }
  193. // Allows for the change in traversal direction. Reverse visits nodes in descending order
  194. internal virtual bool InOrderTreeWalk(TreeWalkPredicate<T> action, bool reverse) {
  195. if (root == null) {
  196. return true;
  197. }
  198. // The maximum height of a red-black tree is 2*lg(n+1).
  199. // See page 264 of "Introduction to algorithms" by Thomas H. Cormen
  200. // note: this should be logbase2, but since the stack grows itself, we
  201. // don‘t want the extra cost
  202. Stack<Node> stack = new Stack<Node>(2 * (int)(SortedSet<T>.log2(Count + 1)));
  203. Node current = root;
  204. while (current != null) {
  205. stack.Push(current);
  206. current = (reverse ? current.Right : current.Left);
  207. }
  208. while (stack.Count != 0) {
  209. current = stack.Pop();
  210. if (!action(current)) {
  211. return false;
  212. }
  213. Node node = (reverse ? current.Left : current.Right);
  214. while (node != null) {
  215. stack.Push(node);
  216. node = (reverse ? node.Right : node.Left);
  217. }
  218. }
  219. return true;
  220. }
  221. //
  222. // Do a left to right breadth first walk on tree and
  223. // calls the delegate for each node.
  224. // If the action delegate returns false, stop the walk.
  225. //
  226. // Return true if the entire tree has been walked.
  227. // Otherwise returns false.
  228. //
  229. internal virtual bool BreadthFirstTreeWalk(TreeWalkPredicate<T> action) {
  230. if (root == null) {
  231. return true;
  232. }
  233. List<Node> processQueue = new List<Node>();
  234. processQueue.Add(root);
  235. Node current;
  236. while (processQueue.Count != 0) {
  237. current = processQueue[0];
  238. processQueue.RemoveAt(0);
  239. if (!action(current)) {
  240. return false;
  241. }
  242. if (current.Left != null) {
  243. processQueue.Add(current.Left);
  244. }
  245. if (current.Right != null) {
  246. processQueue.Add(current.Right);
  247. }
  248. }
  249. return true;
  250. }
  251. #endregion
  252. #region Properties
  253. public int Count {
  254. get {
  255. VersionCheck();
  256. return count;
  257. }
  258. }
  259. public IComparer<T> Comparer {
  260. get {
  261. return comparer;
  262. }
  263. }
  264. bool ICollection<T>.IsReadOnly {
  265. get {
  266. return false;
  267. }
  268. }
  269. bool ICollection.IsSynchronized {
  270. get {
  271. return false;
  272. }
  273. }
  274. object ICollection.SyncRoot {
  275. get {
  276. if (_syncRoot == null) {
  277. System.Threading.Interlocked.CompareExchange(ref _syncRoot, new Object(), null);
  278. }
  279. return _syncRoot;
  280. }
  281. }
  282. #endregion
  283. #region Subclass helpers
  284. //virtual function for subclass that needs to update count
  285. internal virtual void VersionCheck() { }
  286. //virtual function for subclass that needs to do range checks
  287. internal virtual bool IsWithinRange(T item) {
  288. return true;
  289. }
  290. #endregion
  291. #region ICollection<T> Members
  292. /// <summary>
  293. /// Add the value ITEM to the tree, returns true if added, false if duplicate
  294. /// </summary>
  295. /// <param name="item">item to be added</param>
  296. public bool Add(T item) {
  297. return AddIfNotPresent(item);
  298. }
  299. void ICollection<T>.Add(T item) {
  300. AddIfNotPresent(item);
  301. }
  302. /// <summary>
  303. /// Adds ITEM to the tree if not already present. Returns TRUE if value was successfully added
  304. /// or FALSE if it is a duplicate
  305. /// </summary>
  306. internal virtual bool AddIfNotPresent(T item) {
  307. if (root == null) { // empty tree
  308. root = new Node(item, false);
  309. count = 1;
  310. version++;
  311. return true;
  312. }
  313. //
  314. // Search for a node at bottom to insert the new node.
  315. // If we can guanratee the node we found is not a 4-node, it would be easy to do insertion.
  316. // We split 4-nodes along the search path.
  317. //
  318. Node current = root;
  319. Node parent = null;
  320. Node grandParent = null;
  321. Node greatGrandParent = null;
  322. //even if we don‘t actually add to the set, we may be altering its structure (by doing rotations
  323. //and such). so update version to disable any enumerators/subsets working on it
  324. version++;
  325. int order = 0;
  326. while (current != null) {
  327. order = comparer.Compare(item, current.Item);
  328. if (order == 0) {
  329. // We could have changed root node to red during the search process.
  330. // We need to set it to black before we return.
  331. root.IsRed = false;
  332. return false;
  333. }
  334. // split a 4-node into two 2-nodes
  335. if (Is4Node(current)) {
  336. Split4Node(current);
  337. // We could have introduced two consecutive red nodes after split. Fix that by rotation.
  338. if (IsRed(parent)) {
  339. InsertionBalance(current, ref parent, grandParent, greatGrandParent);
  340. }
  341. }
  342. greatGrandParent = grandParent;
  343. grandParent = parent;
  344. parent = current;
  345. current = (order < 0) ? current.Left : current.Right;
  346. }
  347. Debug.Assert(parent != null, "Parent node cannot be null here!");
  348. // ready to insert the new node
  349. Node node = new Node(item);
  350. if (order > 0) {
  351. parent.Right = node;
  352. } else {
  353. parent.Left = node;
  354. }
  355. // the new node will be red, so we will need to adjust the colors if parent node is also red
  356. if (parent.IsRed) {
  357. InsertionBalance(node, ref parent, grandParent, greatGrandParent);
  358. }
  359. // Root node is always black
  360. root.IsRed = false;
  361. ++count;
  362. return true;
  363. }
  364. /// <summary>
  365. /// Remove the T ITEM from this SortedSet. Returns true if successfully removed.
  366. /// </summary>
  367. /// <param name="item"></param>
  368. /// <returns></returns>
  369. public bool Remove(T item) {
  370. return this.DoRemove(item); // hack so it can be made non-virtual
  371. }
  372. internal virtual bool DoRemove(T item) {
  373. if (root == null) {
  374. return false;
  375. }
  376. // Search for a node and then find its succesor.
  377. // Then copy the item from the succesor to the matching node and delete the successor.
  378. // If a node doesn‘t have a successor, we can replace it with its left child (if not empty.)
  379. // or delete the matching node.
  380. //
  381. // In top-down implementation, it is important to make sure the node to be deleted is not a 2-node.
  382. // Following code will make sure the node on the path is not a 2 Node.
  383. //even if we don‘t actually remove from the set, we may be altering its structure (by doing rotations
  384. //and such). so update version to disable any enumerators/subsets working on it
  385. version++;
  386. Node current = root;
  387. Node parent = null;
  388. Node grandParent = null;
  389. Node match = null;
  390. Node parentOfMatch = null;
  391. bool foundMatch = false;
  392. while (current != null) {
  393. if (Is2Node(current)) { // fix up 2-Node
  394. if (parent == null) { // current is root. Mark it as red
  395. current.IsRed = true;
  396. } else {
  397. Node sibling = GetSibling(current, parent);
  398. if (sibling.IsRed) {
  399. // If parent is a 3-node, flip the orientation of the red link.
  400. // We can acheive this by a single rotation
  401. // This case is converted to one of other cased below.
  402. Debug.Assert(!parent.IsRed, "parent must be a black node!");
  403. if (parent.Right == sibling) {
  404. RotateLeft(parent);
  405. } else {
  406. RotateRight(parent);
  407. }
  408. parent.IsRed = true;
  409. sibling.IsRed = false; // parent‘s color
  410. // sibling becomes child of grandParent or root after rotation. Update link from grandParent or root
  411. ReplaceChildOfNodeOrRoot(grandParent, parent, sibling);
  412. // sibling will become grandParent of current node
  413. grandParent = sibling;
  414. if (parent == match) {
  415. parentOfMatch = sibling;
  416. }
  417. // update sibling, this is necessary for following processing
  418. sibling = (parent.Left == current) ? parent.Right : parent.Left;
  419. }
  420. Debug.Assert(sibling != null || sibling.IsRed == false, "sibling must not be null and it must be black!");
  421. if (Is2Node(sibling)) {
  422. Merge2Nodes(parent, current, sibling);
  423. } else {
  424. // current is a 2-node and sibling is either a 3-node or a 4-node.
  425. // We can change the color of current to red by some rotation.
  426. TreeRotation rotation = RotationNeeded(parent, current, sibling);
  427. Node newGrandParent = null;
  428. switch (rotation) {
  429. case TreeRotation.RightRotation:
  430. Debug.Assert(parent.Left == sibling, "sibling must be left child of parent!");
  431. Debug.Assert(sibling.Left.IsRed, "Left child of sibling must be red!");
  432. sibling.Left.IsRed = false;
  433. newGrandParent = RotateRight(parent);
  434. break;
  435. case TreeRotation.LeftRotation:
  436. Debug.Assert(parent.Right == sibling, "sibling must be left child of parent!");
  437. Debug.Assert(sibling.Right.IsRed, "Right child of sibling must be red!");
  438. sibling.Right.IsRed = false;
  439. newGrandParent = RotateLeft(parent);
  440. break;
  441. case TreeRotation.RightLeftRotation:
  442. Debug.Assert(parent.Right == sibling, "sibling must be left child of parent!");
  443. Debug.Assert(sibling.Left.IsRed, "Left child of sibling must be red!");
  444. newGrandParent = RotateRightLeft(parent);
  445. break;
  446. case TreeRotation.LeftRightRotation:
  447. Debug.Assert(parent.Left == sibling, "sibling must be left child of parent!");
  448. Debug.Assert(sibling.Right.IsRed, "Right child of sibling must be red!");
  449. newGrandParent = RotateLeftRight(parent);
  450. break;
  451. }
  452. newGrandParent.IsRed = parent.IsRed;
  453. parent.IsRed = false;
  454. current.IsRed = true;
  455. ReplaceChildOfNodeOrRoot(grandParent, parent, newGrandParent);
  456. if (parent == match) {
  457. parentOfMatch = newGrandParent;
  458. }
  459. grandParent = newGrandParent;
  460. }
  461. }
  462. }
  463. // we don‘t need to compare any more once we found the match
  464. int order = foundMatch ? -1 : comparer.Compare(item, current.Item);
  465. if (order == 0) {
  466. // save the matching node
  467. foundMatch = true;
  468. match = current;
  469. parentOfMatch = parent;
  470. }
  471. grandParent = parent;
  472. parent = current;
  473. if (order < 0) {
  474. current = current.Left;
  475. } else {
  476. current = current.Right; // continue the search in right sub tree after we find a match
  477. }
  478. }
  479. // move successor to the matching node position and replace links
  480. if (match != null) {
  481. ReplaceNode(match, parentOfMatch, parent, grandParent);
  482. --count;
  483. }
  484. if (root != null) {
  485. root.IsRed = false;
  486. }
  487. return foundMatch;
  488. }
  489. public virtual void Clear() {
  490. root = null;
  491. count = 0;
  492. ++version;
  493. }
  494. public virtual bool Contains(T item) {
  495. return FindNode(item) != null;
  496. }
  497. public void CopyTo(T[] array) { CopyTo(array, 0, Count); }
  498. public void CopyTo(T[] array, int index) { CopyTo(array, index, Count); }
  499. public void CopyTo(T[] array, int index, int count) {
  500. if (array == null) {
  501. ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
  502. }
  503. if (index < 0) {
  504. ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index);
  505. }
  506. if (count < 0) {
  507. throw new ArgumentOutOfRangeException("count", SR.GetString(SR.ArgumentOutOfRange_NeedNonNegNum));
  508. }
  509. // will array, starting at arrayIndex, be able to hold elements? Note: not
  510. // checking arrayIndex >= array.Length (consistency with list of allowing
  511. // count of 0; subsequent check takes care of the rest)
  512. if (index > array.Length || count > array.Length - index) {
  513. throw new ArgumentException(SR.GetString(SR.Arg_ArrayPlusOffTooSmall));
  514. }
  515. //upper bound
  516. count += index;
  517. InOrderTreeWalk(delegate(Node node) {
  518. if (index >= count) {
  519. return false;
  520. } else {
  521. array[index++] = node.Item;
  522. return true;
  523. }
  524. });
  525. }
  526. void ICollection.CopyTo(Array array, int index) {
  527. if (array == null) {
  528. ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
  529. }
  530. if (array.Rank != 1) {
  531. ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
  532. }
  533. if (array.GetLowerBound(0) != 0) {
  534. ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound);
  535. }
  536. if (index < 0) {
  537. ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.arrayIndex, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  538. }
  539. if (array.Length - index < Count) {
  540. ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall);
  541. }
  542. T[] tarray = array as T[];
  543. if (tarray != null) {
  544. CopyTo(tarray, index);
  545. } else {
  546. object[] objects = array as object[];
  547. if (objects == null) {
  548. ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
  549. }
  550. try {
  551. InOrderTreeWalk(delegate(Node node) { objects[index++] = node.Item; return true; });
  552. } catch (ArrayTypeMismatchException) {
  553. ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
  554. }
  555. }
  556. }
  557. #endregion
  558. #region IEnumerable<T> members
  559. public Enumerator GetEnumerator() {
  560. return new Enumerator(this);
  561. }
  562. IEnumerator<T> IEnumerable<T>.GetEnumerator() {
  563. return new Enumerator(this);
  564. }
  565. IEnumerator IEnumerable.GetEnumerator() {
  566. return new Enumerator(this);
  567. }
  568. #endregion
  569. #region Tree Specific Operations
  570. private static Node GetSibling(Node node, Node parent) {
  571. if (parent.Left == node) {
  572. return parent.Right;
  573. }
  574. return parent.Left;
  575. }
  576. // After calling InsertionBalance, we need to make sure current and parent up-to-date.
  577. // It doesn‘t matter if we keep grandParent and greatGrantParent up-to-date
  578. // because we won‘t need to split again in the next node.
  579. // By the time we need to split again, everything will be correctly set.
  580. //
  581. private void InsertionBalance(Node current, ref Node parent, Node grandParent, Node greatGrandParent) {
  582. Debug.Assert(grandParent != null, "Grand parent cannot be null here!");
  583. bool parentIsOnRight = (grandParent.Right == parent);
  584. bool currentIsOnRight = (parent.Right == current);
  585. Node newChildOfGreatGrandParent;
  586. if (parentIsOnRight == currentIsOnRight) { // same orientation, single rotation
  587. newChildOfGreatGrandParent = currentIsOnRight ? RotateLeft(grandParent) : RotateRight(grandParent);
  588. } else { // different orientaton, double rotation
  589. newChildOfGreatGrandParent = currentIsOnRight ? RotateLeftRight(grandParent) : RotateRightLeft(grandParent);
  590. // current node now becomes the child of greatgrandparent
  591. parent = greatGrandParent;
  592. }
  593. // grand parent will become a child of either parent of current.
  594. grandParent.IsRed = true;
  595. newChildOfGreatGrandParent.IsRed = false;
  596. ReplaceChildOfNodeOrRoot(greatGrandParent, grandParent, newChildOfGreatGrandParent);
  597. }
  598. private static bool Is2Node(Node node) {
  599. Debug.Assert(node != null, "node cannot be null!");
  600. return IsBlack(node) && IsNullOrBlack(node.Left) && IsNullOrBlack(node.Right);
  601. }
  602. private static bool Is4Node(Node node) {
  603. return IsRed(node.Left) && IsRed(node.Right);
  604. }
  605. private static bool IsBlack(Node node) {
  606. return (node != null && !node.IsRed);
  607. }
  608. private static bool IsNullOrBlack(Node node) {
  609. return (node == null || !node.IsRed);
  610. }
  611. private static bool IsRed(Node node) {
  612. return (node != null && node.IsRed);
  613. }
  614. private static void Merge2Nodes(Node parent, Node child1, Node child2) {
  615. Debug.Assert(IsRed(parent), "parent must be be red");
  616. // combing two 2-nodes into a 4-node
  617. parent.IsRed = false;
  618. child1.IsRed = true;
  619. child2.IsRed = true;
  620. }
  621. // Replace the child of a parent node.
  622. // If the parent node is null, replace the root.
  623. private void ReplaceChildOfNodeOrRoot(Node parent, Node child, Node newChild) {
  624. if (parent != null) {
  625. if (parent.Left == child) {
  626. parent.Left = newChild;
  627. } else {
  628. parent.Right = newChild;
  629. }
  630. } else {
  631. root = newChild;
  632. }
  633. }
  634. // Replace the matching node with its succesor.
  635. private void ReplaceNode(Node match, Node parentOfMatch, Node succesor, Node parentOfSuccesor) {
  636. if (succesor == match) { // this node has no successor, should only happen if right child of matching node is null.
  637. Debug.Assert(match.Right == null, "Right child must be null!");
  638. succesor = match.Left;
  639. } else {
  640. Debug.Assert(parentOfSuccesor != null, "parent of successor cannot be null!");
  641. Debug.Assert(succesor.Left == null, "Left child of succesor must be null!");
  642. Debug.Assert((succesor.Right == null && succesor.IsRed) || (succesor.Right.IsRed && !succesor.IsRed), "Succesor must be in valid state");
  643. if (succesor.Right != null) {
  644. succesor.Right.IsRed = false;
  645. }
  646. if (parentOfSuccesor != match) { // detach succesor from its parent and set its right child
  647. parentOfSuccesor.Left = succesor.Right;
  648. succesor.Right = match.Right;
  649. }
  650. succesor.Left = match.Left;
  651. }
  652. if (succesor != null) {
  653. succesor.IsRed = match.IsRed;
  654. }
  655. ReplaceChildOfNodeOrRoot(parentOfMatch, match, succesor);
  656. }
  657. internal virtual Node FindNode(T item) {
  658. Node current = root;
  659. while (current != null) {
  660. int order = comparer.Compare(item, current.Item);
  661. if (order == 0) {
  662. return current;
  663. } else {
  664. current = (order < 0) ? current.Left : current.Right;
  665. }
  666. }
  667. return null;
  668. }
  669. //used for bithelpers. Note that this implementation is completely different
  670. //from the Subset‘s. The two should not be mixed. This indexes as if the tree were an array.
  671. //http://en.wikipedia.org/wiki/Binary_Tree#Methods_for_storing_binary_trees
  672. internal virtual int InternalIndexOf(T item) {
  673. Node current = root;
  674. int count = 0;
  675. while (current != null) {
  676. int order = comparer.Compare(item, current.Item);
  677. if (order == 0) {
  678. return count;
  679. } else {
  680. current = (order < 0) ? current.Left : current.Right;
  681. count = (order < 0) ? (2 * count + 1) : (2 * count + 2);
  682. }
  683. }
  684. return -1;
  685. }
  686. internal Node FindRange(T from, T to) {
  687. return FindRange(from, to, true, true);
  688. }
  689. internal Node FindRange(T from, T to, bool lowerBoundActive, bool upperBoundActive) {
  690. Node current = root;
  691. while (current != null) {
  692. if (lowerBoundActive && comparer.Compare(from, current.Item) > 0) {
  693. current = current.Right;
  694. } else {
  695. if (upperBoundActive && comparer.Compare(to, current.Item) < 0) {
  696. current = current.Left;
  697. } else {
  698. return current;
  699. }
  700. }
  701. }
  702. return null;
  703. }
  704. internal void UpdateVersion() {
  705. ++version;
  706. }
  707. private static Node RotateLeft(Node node) {
  708. Node x = node.Right;
  709. node.Right = x.Left;
  710. x.Left = node;
  711. return x;
  712. }
  713. private static Node RotateLeftRight(Node node) {
  714. Node child = node.Left;
  715. Node grandChild = child.Right;
  716. node.Left = grandChild.Right;
  717. grandChild.Right = node;
  718. child.Right = grandChild.Left;
  719. grandChild.Left = child;
  720. return grandChild;
  721. }
  722. private static Node RotateRight(Node node) {
  723. Node x = node.Left;
  724. node.Left = x.Right;
  725. x.Right = node;
  726. return x;
  727. }
  728. private static Node RotateRightLeft(Node node) {
  729. Node child = node.Right;
  730. Node grandChild = child.Left;
  731. node.Right = grandChild.Left;
  732. grandChild.Left = node;
  733. child.Left = grandChild.Right;
  734. grandChild.Right = child;
  735. return grandChild;
  736. }
  737. /// <summary>
  738. /// Testing counter that can track rotations
  739. /// </summary>
  740. private static TreeRotation RotationNeeded(Node parent, Node current, Node sibling) {
  741. Debug.Assert(IsRed(sibling.Left) || IsRed(sibling.Right), "sibling must have at least one red child");
  742. if (IsRed(sibling.Left)) {
  743. if (parent.Left == current) {
  744. return TreeRotation.RightLeftRotation;
  745. }
  746. return TreeRotation.RightRotation;
  747. } else {
  748. if (parent.Left == current) {
  749. return TreeRotation.LeftRotation;
  750. }
  751. return TreeRotation.LeftRightRotation;
  752. }
  753. }
  754. /// <summary>
  755. /// Used for deep equality of SortedSet testing
  756. /// </summary>
  757. /// <returns></returns>
  758. public static IEqualityComparer<SortedSet<T>> CreateSetComparer() {
  759. return new SortedSetEqualityComparer<T>();
  760. }
  761. /// <summary>
  762. /// Create a new set comparer for this set, where this set‘s members‘ equality is defined by the
  763. /// memberEqualityComparer. Note that this equality comparer‘s definition of equality must be the
  764. /// same as this set‘s Comparer‘s definition of equality
  765. /// </summary>
  766. public static IEqualityComparer<SortedSet<T>> CreateSetComparer(IEqualityComparer<T> memberEqualityComparer) {
  767. return new SortedSetEqualityComparer<T>(memberEqualityComparer);
  768. }
  769. /// <summary>
  770. /// Decides whether these sets are the same, given the comparer. If the EC‘s are the same, we can
  771. /// just use SetEquals, but if they aren‘t then we have to manually check with the given comparer
  772. /// </summary>
  773. internal static bool SortedSetEquals(SortedSet<T> set1, SortedSet<T> set2, IComparer<T> comparer) {
  774. // handle null cases first
  775. if (set1 == null) {
  776. return (set2 == null);
  777. } else if (set2 == null) {
  778. // set1 != null
  779. return false;
  780. }
  781. if (AreComparersEqual(set1, set2)) {
  782. if (set1.Count != set2.Count)
  783. return false;
  784. return set1.SetEquals(set2);
  785. } else {
  786. bool found = false;
  787. foreach (T item1 in set1) {
  788. found = false;
  789. foreach (T item2 in set2) {
  790. if (comparer.Compare(item1, item2) == 0) {
  791. found = true;
  792. break;
  793. }
  794. }
  795. if (!found)
  796. return false;
  797. }
  798. return true;
  799. }
  800. }
  801. //This is a little frustrating because we can‘t support more sorted structures
  802. private static bool AreComparersEqual(SortedSet<T> set1, SortedSet<T> set2) {
  803. return set1.Comparer.Equals(set2.Comparer);
  804. }
  805. private static void Split4Node(Node node) {
  806. node.IsRed = true;
  807. node.Left.IsRed = false;
  808. node.Right.IsRed = false;
  809. }
  810. /// <summary>
  811. /// Copies this to an array. Used for DebugView
  812. /// </summary>
  813. /// <returns></returns>
  814. internal T[] ToArray() {
  815. T[] newArray = new T[Count];
  816. CopyTo(newArray);
  817. return newArray;
  818. }
  819. #endregion
  820. #region ISet Members
  821. /// <summary>
  822. /// Transform this set into its union with the IEnumerable OTHER
  823. ///Attempts to insert each element and rejects it if it exists.
  824. /// NOTE: The caller object is important as UnionWith uses the Comparator
  825. ///associated with THIS to check equality
  826. /// Throws ArgumentNullException if OTHER is null
  827. /// </summary>
  828. /// <param name="other"></param>
  829. public void UnionWith(IEnumerable<T> other) {
  830. if (other == null) {
  831. throw new ArgumentNullException("other");
  832. }
  833. SortedSet<T> s = other as SortedSet<T>;
  834. TreeSubSet t = this as TreeSubSet;
  835. if (t != null)
  836. VersionCheck();
  837. if (s != null && t == null && this.count == 0) {
  838. SortedSet<T> dummy = new SortedSet<T>(s, this.comparer);
  839. this.root = dummy.root;
  840. this.count = dummy.count;
  841. this.version++;
  842. return;
  843. }
  844. if (s != null && t == null && AreComparersEqual(this, s) && (s.Count > this.Count / 2)) { //this actually hurts if N is much greater than M the /2 is arbitrary
  845. //first do a merge sort to an array.
  846. T[] merged = new T[s.Count + this.Count];
  847. int c = 0;
  848. Enumerator mine = this.GetEnumerator();
  849. Enumerator theirs = s.GetEnumerator();
  850. bool mineEnded = !mine.MoveNext(), theirsEnded = !theirs.MoveNext();
  851. while (!mineEnded && !theirsEnded) {
  852. int comp = Comparer.Compare(mine.Current, theirs.Current);
  853. if (comp < 0) {
  854. merged[c++] = mine.Current;
  855. mineEnded = !mine.MoveNext();
  856. } else if (comp == 0) {
  857. merged[c++] = theirs.Current;
  858. mineEnded = !mine.MoveNext();
  859. theirsEnded = !theirs.MoveNext();
  860. } else {
  861. merged[c++] = theirs.Current;
  862. theirsEnded = !theirs.MoveNext();
  863. }
  864. }
  865. if (!mineEnded || !theirsEnded) {
  866. Enumerator remaining = (mineEnded ? theirs : mine);
  867. do {
  868. merged[c++] = remaining.Current;
  869. } while (remaining.MoveNext());
  870. }
  871. //now merged has all c elements
  872. //safe to gc the root, we have all the elements
  873. root = null;
  874. root = SortedSet<T>.ConstructRootFromSortedArray(merged, 0, c - 1, null);
  875. count = c;
  876. version++;
  877. } else {
  878. AddAllElements(other);
  879. }
  880. }
  881. private static Node ConstructRootFromSortedArray(T[] arr, int startIndex, int endIndex, Node redNode) {
  882. //what does this do?
  883. //you‘re given a sorted array... say 1 2 3 4 5 6
  884. //2 cases:
  885. // If there are odd # of elements, pick the middle element (in this case 4), and compute
  886. // its left and right branches
  887. // If there are even # of elements, pick the left middle element, save the right middle element
  888. // and call the function on the rest
  889. // 1 2 3 4 5 6 -> pick 3, save 4 and call the fn on 1,2 and 5,6
  890. // now add 4 as a red node to the lowest element on the right branch
  891. // 3 3
  892. // 1 5 -> 1 5
  893. // 2 6 2 4 6
  894. // As we‘re adding to the leftmost of the right branch, nesting will not hurt the red-black properties
  895. // Leaf nodes are red if they have no sibling (if there are 2 nodes or if a node trickles
  896. // down to the bottom
  897. //the iterative way to do this ends up wasting more space than it saves in stack frames (at
  898. //least in what i tried)
  899. //so we‘re doing this recursively
  900. //base cases are described below
  901. int size = endIndex - startIndex + 1;
  902. if (size == 0) {
  903. return null;
  904. }
  905. Node root = null;
  906. if (size == 1) {
  907. root = new Node(arr[startIndex], false);
  908. if (redNode != null) {
  909. root.Left = redNode;
  910. }
  911. } else if (size == 2) {
  912. root = new Node(arr[startIndex], false);
  913. root.Right = new Node(arr[endIndex], false);
  914. root.Right.IsRed = true;
  915. if (redNode != null) {
  916. root.Left = redNode;
  917. }
  918. } else if (size == 3) {
  919. root = new Node(arr[startIndex + 1], false);
  920. root.Left = new Node(arr[startIndex], false);
  921. root.Right = new Node(arr[endIndex], false);
  922. if (redNode != null) {
  923. root.Left.Left = redNode;
  924. }
  925. } else {
  926. int midpt = ((startIndex + endIndex) / 2);
  927. root = new Node(arr[midpt], false);
  928. root.Left = ConstructRootFromSortedArray(arr, startIndex, midpt - 1, redNode);
  929. if (size % 2 == 0) {
  930. root.Right = ConstructRootFromSortedArray(arr, midpt + 2, endIndex, new Node(arr[midpt + 1], true));
  931. } else {
  932. root.Right = ConstructRootFromSortedArray(arr, midpt + 1, endIndex, null);
  933. }
  934. }
  935. return root;
  936. }
  937. /// <summary>
  938. /// Transform this set into its intersection with the IEnumerable OTHER
  939. /// NOTE: The caller object is important as IntersectionWith uses the
  940. /// comparator associated with THIS to check equality
  941. /// Throws ArgumentNullException if OTHER is null
  942. /// </summary>
  943. /// <param name="other"></param>
  944. public virtual void IntersectWith(IEnumerable<T> other) {
  945. if (other == null) {
  946. throw new ArgumentNullException("other");
  947. }
  948. if (Count == 0)
  949. return;
  950. //HashSet<T> optimizations can‘t be done until equality comparers and comparers are related
  951. //Technically, this would work as well with an ISorted<T>
  952. SortedSet<T> s = other as SortedSet<T>;
  953. TreeSubSet t = this as TreeSubSet;
  954. if (t != null)
  955. VersionCheck();
  956. //only let this happen if i am also a SortedSet, not a SubSet
  957. if (s != null && t == null && AreComparersEqual(this, s)) {
  958. //first do a merge sort to an array.
  959. T[] merged = new T[this.Count];
  960. int c = 0;
  961. Enumerator mine = this.GetEnumerator();
  962. Enumerator theirs = s.GetEnumerator();
  963. bool mineEnded = !mine.MoveNext(), theirsEnded = !theirs.MoveNext();
  964. T max = Max;
  965. T min = Min;
  966. while (!mineEnded && !theirsEnded && Comparer.Compare(theirs.Current, max) <= 0) {
  967. int comp = Comparer.Compare(mine.Current, theirs.Current);
  968. if (comp < 0) {
  969. mineEnded = !mine.MoveNext();
  970. } else if (comp == 0) {
  971. merged[c++] = theirs.Current;
  972. mineEnded = !mine.MoveNext();
  973. theirsEnded = !theirs.MoveNext();
  974. } else {
  975. theirsEnded = !theirs.MoveNext();
  976. }
  977. }
  978. //now merged has all c elements
  979. //safe to gc the root, we have all the elements
  980. root = null;
  981. root = SortedSet<T>.ConstructRootFromSortedArray(merged, 0, c - 1, null);
  982. count = c;
  983. version++;
  984. } else {
  985. IntersectWithEnumerable(other);
  986. }
  987. }
  988. internal virtual void IntersectWithEnumerable(IEnumerable<T> other) {
  989. //
  990. List<T> toSave = new List<T>(this.Count);
  991. foreach (T item in other) {
  992. if (this.Contains(item)) {
  993. toSave.Add(item);
  994. this.Remove(item);
  995. }
  996. }
  997. this.Clear();
  998. AddAllElements(toSave);
  999. }
  1000. /// <summary>
  1001. /// Transform this set into its complement with the IEnumerable OTHER
  1002. /// NOTE: The caller object is important as ExceptWith uses the
  1003. /// comparator associated with THIS to check equality
  1004. /// Throws ArgumentNullException if OTHER is null
  1005. /// </summary>
  1006. /// <param name="other"></param>
  1007. public void ExceptWith(IEnumerable<T> other) {
  1008. if (other == null) {
  1009. throw new ArgumentNullException("other");
  1010. }
  1011. if (count == 0)
  1012. return;
  1013. if (other == this) {
  1014. this.Clear();
  1015. return;
  1016. }
  1017. SortedSet<T> asSorted = other as SortedSet<T>;
  1018. if (asSorted != null && AreComparersEqual(this, asSorted)) {
  1019. //outside range, no point doing anything
  1020. if (!(comparer.Compare(asSorted.Max, this.Min) < 0 || comparer.Compare(asSorted.Min, this.Max) > 0)) {
  1021. T min = this.Min;
  1022. T max = this.Max;
  1023. foreach (T item in other) {
  1024. if (comparer.Compare(item, min) < 0)
  1025. continue;
  1026. if (comparer.Compare(item, max) > 0)
  1027. break;
  1028. Remove(item);
  1029. }
  1030. }
  1031. } else {
  1032. RemoveAllElements(other);
  1033. }
  1034. }
  1035. /// <summary>
  1036. /// Transform this set so it contains elements in THIS or OTHER but not both
  1037. /// NOTE: The caller object is important as SymmetricExceptWith uses the
  1038. /// comparator associated with THIS to check equality
  1039. /// Throws ArgumentNullException if OTHER is null
  1040. /// </summary>
  1041. /// <param name="other"></param>
  1042. public void SymmetricExceptWith(IEnumerable<T> other) {
  1043. if (other == null) {
  1044. throw new ArgumentNullException("other");
  1045. }
  1046. if (this.Count == 0) {
  1047. this.UnionWith(other);
  1048. return;
  1049. }
  1050. if (other == this) {
  1051. this.Clear();
  1052. return;
  1053. }
  1054. SortedSet<T> asSorted = other as SortedSet<T>;
  1055. #if USING_HASH_SET
  1056. HashSet<T> asHash = other as HashSet<T>;
  1057. #endif
  1058. if (asSorted != null && AreComparersEqual(this, asSorted)) {
  1059. SymmetricExceptWithSameEC(asSorted);
  1060. }
  1061. #if USING_HASH_SET
  1062. else if (asHash != null && this.comparer.Equals(Comparer<T>.Default) && asHash.Comparer.Equals(EqualityComparer<T>.Default)) {
  1063. SymmetricExceptWithSameEC(asHash);
  1064. }
  1065. #endif
  1066. else {
  1067. //need perf improvement on this
  1068. T[] elements = (new List<T>(other)).ToArray();
  1069. Array.Sort(elements, this.Comparer);
  1070. SymmetricExceptWithSameEC(elements);
  1071. }
  1072. }
  1073. //OTHER must be a set
  1074. internal void SymmetricExceptWithSameEC(ISet<T> other) {
  1075. foreach (T item in other) {
  1076. //yes, it is classier to say
  1077. //if (!this.Remove(item))this.Add(item);
  1078. //but this ends up saving on rotations
  1079. if (this.Contains(item)) {
  1080. this.Remove(item);
  1081. } else {
  1082. this.Add(item);
  1083. }
  1084. }
  1085. }
  1086. //OTHER must be a sorted array
  1087. internal void SymmetricExceptWithSameEC(T[] other) {
  1088. if (other.Length == 0) {
  1089. return;
  1090. }
  1091. T last = other[0];
  1092. for (int i = 0; i < other.Length; i++) {
  1093. while (i < other.Length && i != 0 && comparer.Compare(other[i], last) == 0)
  1094. i++;
  1095. if (i >= other.Length)
  1096. break;
  1097. if (this.Contains(other[i])) {
  1098. this.Remove(other[i]);
  1099. } else {
  1100. this.Add(other[i]);
  1101. }
  1102. last = other[i];
  1103. }
  1104. }
  1105. /// <summary>
  1106. /// Checks whether this Tree is a subset of the IEnumerable other
  1107. /// </summary>
  1108. /// <param name="other"></param>
  1109. /// <returns></returns>
  1110. [System.Security.SecuritySafeCritical]
  1111. public bool IsSubsetOf(IEnumerable<T> other) {
  1112. if (other == null) {
  1113. throw new ArgumentNullException("other");
  1114. }
  1115. if (Count == 0)
  1116. return true;
  1117. SortedSet<T> asSorted = other as SortedSet<T>;
  1118. if (asSorted != null && AreComparersEqual(this, asSorted)) {
  1119. if (this.Count > asSorted.Count)
  1120. return false;
  1121. return IsSubsetOfSortedSetWithSameEC(asSorted);
  1122. } else {
  1123. //worst case: mark every element in my set and see if i‘ve counted all
  1124. //O(MlogN)
  1125. ElementCount result = CheckUniqueAndUnfoundElements(other, false);
  1126. return (result.uniqueCount == Count && result.unfoundCount >= 0);
  1127. }
  1128. }
  1129. private bool IsSubsetOfSortedSetWithSameEC(SortedSet<T> asSorted) {
  1130. SortedSet<T> prunedOther = asSorted.GetViewBetween(this.Min, this.Max);
  1131. foreach (T item in this) {
  1132. if (!prunedOther.Contains(item))
  1133. return false;
  1134. }
  1135. return true;
  1136. }
  1137. /// <summary>
  1138. /// Checks whether this Tree is a proper subset of the IEnumerable other
  1139. /// </summary>
  1140. /// <param name="other"></param>
  1141. /// <returns></returns>
  1142. [System.Security.SecuritySafeCritical]
  1143. public bool IsProperSubsetOf(IEnumerable<T> other) {
  1144. if (other == null) {
  1145. throw new ArgumentNullException("other");
  1146. }
  1147. if ((other as ICollection) != null) {
  1148. if (Count == 0)
  1149. return (other as ICollection).Count > 0;
  1150. }
  1151. #if USING_HASH_SET
  1152. //do it one way for HashSets
  1153. HashSet<T> asHash = other as HashSet<T>;
  1154. if (asHash != null && comparer.Equals(Comparer<T>.Default) && asHash.Comparer.Equals(EqualityComparer<T>.Default)) {
  1155. return asHash.IsProperSupersetOf(this);
  1156. }
  1157. #endif
  1158. //another for sorted sets with the same comparer
  1159. SortedSet<T> asSorted = other as SortedSet<T>;
  1160. if (asSorted != null && AreComparersEqual(this, asSorted)) {
  1161. if (this.Count >= asSorted.Count)
  1162. return false;
  1163. return IsSubsetOfSortedSetWithSameEC(asSorted);
  1164. }
  1165. //worst case: mark every element in my set and see if i‘ve counted all
  1166. //O(MlogN).
  1167. ElementCount result = CheckUniqueAndUnfoundElements(other, false);
  1168. return (result.uniqueCount == Count && result.unfoundCount > 0);
  1169. }
  1170. /// <summary>
  1171. /// Checks whether this Tree is a super set of the IEnumerable other
  1172. /// </summary>
  1173. /// <param name="other"></param>
  1174. /// <returns></returns>
  1175. public bool IsSupersetOf(IEnumerable<T> other) {
  1176. if (other == null) {
  1177. throw new ArgumentNullException("other");
  1178. }
  1179. if ((other as ICollection) != null && (other as ICollection).Count == 0)
  1180. return true;
  1181. //do it one way for HashSets
  1182. #if USING_HASH_SET
  1183. HashSet<T> asHash = other as HashSet<T>;
  1184. if (asHash != null && comparer.Equals(Comparer<T>.Default) && asHash.Comparer.Equals(EqualityComparer<T>.Default)) {
  1185. return asHash.IsSubsetOf(this);
  1186. }
  1187. #endif
  1188. //another for sorted sets with the same comparer
  1189. SortedSet<T> asSorted = other as SortedSet<T>;
  1190. if (asSorted != null && AreComparersEqual(this, asSorted)) {
  1191. if (this.Count < asSorted.Count)
  1192. return false;
  1193. SortedSet<T> pruned = GetViewBetween(asSorted.Min, asSorted.Max);
  1194. foreach (T item in asSorted) {
  1195. if (!pruned.Contains(item))
  1196. return false;
  1197. }
  1198. return true;
  1199. }
  1200. //and a third for everything else
  1201. return ContainsAllElements(other);
  1202. }
  1203. /// <summary>
  1204. /// Checks whether this Tree is a proper super set of the IEnumerable other
  1205. /// </summary>
  1206. /// <param name="other"></param>
  1207. /// <returns></returns>
  1208. [System.Security.SecuritySafeCritical]
  1209. public bool IsProperSupersetOf(IEnumerable<T> other) {
  1210. if (other == null) {
  1211. throw new ArgumentNullException("other");
  1212. }
  1213. if (Count == 0)
  1214. return false;
  1215. if ((other as ICollection) != null && (other as ICollection).Count == 0)
  1216. return true;
  1217. #if USING_HASH_SET
  1218. //do it one way for HashSets
  1219. HashSet<T> asHash = other as HashSet<T>;
  1220. if (asHash != null && comparer.Equals(Comparer<T>.Default) && asHash.Comparer.Equals(EqualityComparer<T>.Default)) {
  1221. return asHash.IsProperSubsetOf(this);
  1222. }
  1223. #endif
  1224. //another way for sorted sets
  1225. SortedSet<T> asSorted = other as SortedSet<T>;
  1226. if (asSorted != null && AreComparersEqual(asSorted, this)) {
  1227. if (asSorted.Count >= this.Count)
  1228. return false;
  1229. SortedSet<T> pruned = GetViewBetween(asSorted.Min, asSorted.Max);
  1230. foreach (T item in asSorted) {
  1231. if (!pruned.Contains(item))
  1232. return false;
  1233. }
  1234. return true;
  1235. }
  1236. //worst case: mark every element in my set and see if i‘ve counted all
  1237. //O(MlogN)
  1238. //slight optimization, put it into a HashSet and then check can do it in O(N+M)
  1239. //but slower in better cases + wastes space
  1240. ElementCount result = CheckUniqueAndUnfoundElements(other, true);
  1241. return (result.uniqueCount < Count && result.unfoundCount == 0);
  1242. }
  1243. /// <summary>
  1244. /// Checks whether this Tree has all elements in common with IEnumerable other
  1245. /// </summary>
  1246. /// <param name="other"></param>
  1247. /// <returns></returns>
  1248. [System.Security.SecuritySafeCritical]
  1249. public bool SetEquals(IEnumerable<T> other) {
  1250. if (other == null) {
  1251. throw new ArgumentNullException("other");
  1252. }
  1253. #if USING_HASH_SET
  1254. HashSet<T> asHash = other as HashSet<T>;
  1255. if (asHash != null && comparer.Equals(Comparer<T>.Default) && asHash.Comparer.Equals(EqualityComparer<T>.Default)) {
  1256. return asHash.SetEquals(this);
  1257. }
  1258. #endif
  1259. SortedSet<T> asSorted = other as SortedSet<T>;
  1260. if (asSorted != null && AreComparersEqual(this, asSorted)) {
  1261. IEnumerator<T> mine = this.GetEnumerator();
  1262. IEnumerator<T> theirs = asSorted.GetEnumerator();
  1263. bool mineEnded = !mine.MoveNext();
  1264. bool theirsEnded = !theirs.MoveNext();
  1265. while (!mineEnded && !theirsEnded) {
  1266. if (Comparer.Compare(mine.Current, theirs.Current) != 0) {
  1267. return false;
  1268. }
  1269. mineEnded = !mine.MoveNext();
  1270. theirsEnded = !theirs.MoveNext();
  1271. }
  1272. return mineEnded && theirsEnded;
  1273. }
  1274. //worst case: mark every element in my set and see if i‘ve counted all
  1275. //O(N) by size of other
  1276. ElementCount result = CheckUniqueAndUnfoundElements(other, true);
  1277. return (result.uniqueCount == Count && result.unfoundCount == 0);
  1278. }
  1279. /// <summary>
  1280. /// Checks whether this Tree has any elements in common with IEnumerable other
  1281. /// </summary>
  1282. /// <param name="other"></param>
  1283. /// <returns></returns>
  1284. public bool Overlaps(IEnumerable<T> other) {
  1285. if (other == null) {
  1286. throw new ArgumentNullException("other");
  1287. }
  1288. if (this.Count == 0)
  1289. return false;
  1290. if ((other as ICollection<T> != null) && (other as ICollection<T>).Count == 0)
  1291. return false;
  1292. SortedSet<T> asSorted = other as SortedSet<T>;
  1293. if (asSorted != null && AreComparersEqual(this, asSorted) && (comparer.Compare(Min, asSorted.Max) > 0 || comparer.Compare(Max, asSorted.Min) < 0)) {
  1294. return false;
  1295. }
  1296. #if USING_HASH_SET
  1297. HashSet<T> asHash = other as HashSet<T>;
  1298. if (asHash != null && comparer.Equals(Comparer<T>.Default) && asHash.Comparer.Equals(EqualityComparer<T>.Default)) {
  1299. return asHash.Overlaps(this);
  1300. }
  1301. #endif
  1302. foreach (T item in other) {
  1303. if (this.Contains(item)) {
  1304. return true;
  1305. }
  1306. }
  1307. return false;
  1308. }
  1309. /// <summary>
  1310. /// This works similar to HashSet‘s CheckUniqueAndUnfound (description below), except that the bit
  1311. /// array maps differently than in the HashSet. We can only use this for the bulk boolean checks.
  1312. ///
  1313. /// Determines counts that can be used to determine equality, subset, and superset. This
  1314. /// is only used when other is an IEnumerable and not a HashSet. If other is a HashSet
  1315. /// these properties can be checked faster without use of marking because we can assume
  1316. /// other has no duplicates.
  1317. ///
  1318. /// The following count checks are performed by callers:
  1319. /// 1. Equals: checks if unfoundCount = 0 and uniqueFoundCount = Count; i.e. everything
  1320. /// in other is in this and everything in this is in other
  1321. /// 2. Subset: checks if unfoundCount >= 0 and uniqueFoundCount = Count; i.e. other may
  1322. /// have elements not in this and everything in this is in other
  1323. /// 3. Proper subset: checks if unfoundCount > 0 and uniqueFoundCount = Count; i.e
  1324. /// other must have at least one element not in this and everything in this is in other
  1325. /// 4. Proper superset: checks if unfound count = 0 and uniqueFoundCount strictly less
  1326. /// than Count; i.e. everything in other was in this and this had at least one element
  1327. /// not contained in other.
  1328. ///
  1329. /// An earlier implementation used delegates to perform these checks rather than returning
  1330. /// an ElementCount struct; however this was changed due to the perf overhead of delegates.
  1331. /// </summary>
  1332. /// <param name="other"></param>
  1333. /// <param name="returnIfUnfound">Allows us to finish faster for equals and proper superset
  1334. /// because unfoundCount must be 0.</param>
  1335. /// <returns></returns>
  1336. // <SecurityKernel Critical="True" Ring="0">
  1337. // <UsesUnsafeCode Name="Local bitArrayPtr of type: Int32*" />
  1338. // <ReferencesCritical Name="Method: BitHelper..ctor(System.Int32*,System.Int32)" Ring="1" />
  1339. // <ReferencesCritical Name="Method: BitHelper.IsMarked(System.Int32):System.Boolean" Ring="1" />
  1340. // <ReferencesCritical Name="Method: BitHelper.MarkBit(System.Int32):System.Void" Ring="1" />
  1341. // </SecurityKernel>
  1342. [System.Security.SecurityCritical]
  1343. private unsafe ElementCount CheckUniqueAndUnfoundElements(IEnumerable<T> other, bool returnIfUnfound) {
  1344. ElementCount result;
  1345. // need special case in case this has no elements.
  1346. if (Count == 0) {
  1347. int numElementsInOther = 0;
  1348. foreach (T item in other) {
  1349. numElementsInOther++;
  1350. // break right away, all we want to know is whether other has 0 or 1 elements
  1351. break;
  1352. }
  1353. result.uniqueCount = 0;
  1354. result.unfoundCount = numElementsInOther;
  1355. return result;
  1356. }
  1357. int originalLastIndex = Count;
  1358. int intArrayLength = BitHelper.ToIntArrayLength(originalLastIndex);
  1359. BitHelper bitHelper;
  1360. if (intArrayLength <= StackAllocThreshold) {
  1361. int* bitArrayPtr = stackalloc int[intArrayLength];
  1362. bitHelper = new BitHelper(bitArrayPtr, intArrayLength);
  1363. } else {
  1364. int[] bitArray = new int[intArrayLength];
  1365. bitHelper = new BitHelper(bitArray, intArrayLength);
  1366. }
  1367. // count of items in other not found in this
  1368. int unfoundCount = 0;
  1369. // count of unique items in other found in this
  1370. int uniqueFoundCount = 0;
  1371. foreach (T item in other) {
  1372. int index = InternalIndexOf(item);
  1373. if (index >= 0) {
  1374. if (!bitHelper.IsMarked(index)) {
  1375. // item hasn‘t been seen yet
  1376. bitHelper.MarkBit(index);
  1377. uniqueFoundCount++;
  1378. }
  1379. } else {
  1380. unfoundCount++;
  1381. if (returnIfUnfound) {
  1382. break;
  1383. }
  1384. }
  1385. }
  1386. result.uniqueCount = uniqueFoundCount;
  1387. result.unfoundCount = unfoundCount;
  1388. return result;
  1389. }
  1390. public int RemoveWhere(Predicate<T> match) {
  1391. if (match == null) {
  1392. throw new ArgumentNullException("match");
  1393. }
  1394. List<T> matches = new List<T>(this.Count);
  1395. BreadthFirstTreeWalk(delegate(Node n) {
  1396. if (match(n.Item)) {
  1397. matches.Add(n.Item);
  1398. }
  1399. return true;
  1400. });
  1401. // reverse breadth first to (try to) incur low cost
  1402. int actuallyRemoved = 0;
  1403. for (int i = matches.Count - 1; i >= 0; i--) {
  1404. if (this.Remove(matches[i])) {
  1405. actuallyRemoved++;
  1406. }
  1407. }
  1408. return actuallyRemoved;
  1409. }
  1410. #endregion
  1411. #region ISorted Members
  1412. public T Min {
  1413. get {
  1414. T ret = default(T);
  1415. InOrderTreeWalk(delegate(SortedSet<T>.Node n) { ret = n.Item; return false; });
  1416. return ret;
  1417. }
  1418. }
  1419. public T Max {
  1420. get {
  1421. T ret = default(T);
  1422. InOrderTreeWalk(delegate(SortedSet<T>.Node n) { ret = n.Item; return false; }, true);
  1423. return ret;
  1424. }
  1425. }
  1426. public IEnumerable<T> Reverse() {
  1427. Enumerator e = new Enumerator(this, true);
  1428. while (e.MoveNext()) {
  1429. yield return e.Current;
  1430. }
  1431. }
  1432. /// <summary>
  1433. /// Returns a subset of this tree ranging from values lBound to uBound
  1434. /// Any changes made to the subset reflect in the actual tree
  1435. /// </summary>
  1436. /// <param name="lowVestalue">Lowest Value allowed in the subset</param>
  1437. /// <param name="highestValue">Highest Value allowed in the subset</param>
  1438. public virtual SortedSet<T> GetViewBetween(T lowerValue, T upperValue) {
  1439. if (Comparer.Compare(lowerValue, upperValue) > 0) {
  1440. throw new ArgumentException("lowerBound is greater than upperBound");
  1441. }
  1442. return new TreeSubSet(this, lowerValue, upperValue, true, true);
  1443. }
  1444. #if DEBUG
  1445. /// <summary>
  1446. /// debug status to be checked whenever any operation is called
  1447. /// </summary>
  1448. /// <returns></returns>
  1449. internal virtual bool versionUpToDate() {
  1450. return true;
  1451. }
  1452. #endif
  1453. /// <summary>
  1454. /// This class represents a subset view into the tree. Any changes to this view
  1455. /// are reflected in the actual tree. Uses the Comparator of the underlying tree.
  1456. /// </summary>
  1457. /// <typeparam name="T"></typeparam>
  1458. #if !FEATURE_NETCORE
  1459. [Serializable]
  1460. internal sealed class TreeSubSet : SortedSet<T>, ISerializable, IDeserializationCallback {
  1461. #else
  1462. internal sealed class TreeSubSet : SortedSet<T> {
  1463. #endif
  1464. SortedSet<T> underlying;
  1465. T min, max;
  1466. //these exist for unbounded collections
  1467. //for instance, you could allow this subset to be defined for i>10. The set will throw if
  1468. //anything <=10 is added, but there is no upperbound. These features Head(), Tail(), were punted
  1469. //in the spec, and are not available, but the framework is there to make them available at some point.
  1470. bool lBoundActive, uBoundActive;
  1471. //used to see if the count is out of date
  1472. #if DEBUG
  1473. internal override bool versionUpToDate() {
  1474. return (this.version == underlying.version);
  1475. }
  1476. #endif
  1477. public TreeSubSet(SortedSet<T> Underlying, T Min, T Max, bool lowerBoundActive, bool upperBoundActive)
  1478. : base(Underlying.Comparer) {
  1479. underlying = Underlying;
  1480. min = Min;
  1481. max = Max;
  1482. lBoundActive = lowerBoundActive;
  1483. uBoundActive = upperBoundActive;
  1484. root = underlying.FindRange(min, max, lBoundActive, uBoundActive); // root is first element within range
  1485. count = 0;
  1486. version = -1;
  1487. VersionCheckImpl();
  1488. }
  1489. #if !FEATURE_NETCORE
  1490. /// <summary>
  1491. /// For serialization and deserialization
  1492. /// </summary>
  1493. private TreeSubSet() {
  1494. comparer = null;
  1495. }
  1496. [SuppressMessage("Microsoft.Usage", "CA2236:CallBaseClassMethodsOnISerializableTypes", Justification = "special case TreeSubSet serialization")]
  1497. private TreeSubSet(SerializationInfo info, StreamingContext context) {
  1498. siInfo = info;
  1499. OnDeserializationImpl(info);
  1500. }
  1501. #endif // !FEATURE_NETCORE
  1502. /// <summary>
  1503. /// Additions to this tree need to be added to the underlying tree as well
  1504. /// </summary>
  1505. internal override bool AddIfNotPresent(T item) {
  1506. if (!IsWithinRange(item)) {
  1507. ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.collection);
  1508. }
  1509. bool ret = underlying.AddIfNotPresent(item);
  1510. VersionCheck();
  1511. #if DEBUG
  1512. Debug.Assert(this.versionUpToDate() && this.root == this.underlying.FindRange(min, max));
  1513. #endif
  1514. return ret;
  1515. }
  1516. public override bool Contains(T item) {
  1517. VersionCheck();
  1518. #if DEBUG
  1519. Debug.Assert(this.versionUpToDate() && this.root == this.underlying.FindRange(min, max));
  1520. #endif
  1521. return base.Contains(item);
  1522. }
  1523. internal override bool DoRemove(T item) { // todo: uppercase this and others
  1524. if (!IsWithinRange(item)) {
  1525. return false;
  1526. }
  1527. bool ret = underlying.Remove(item);
  1528. VersionCheck();
  1529. #if DEBUG
  1530. Debug.Assert(this.versionUpToDate() && this.root == this.underlying.FindRange(min, max));
  1531. #endif
  1532. return ret;
  1533. }
  1534. public override void Clear() {
  1535. if (count == 0) {
  1536. return;
  1537. }
  1538. List<T> toRemove = new List<T>();
  1539. BreadthFirstTreeWalk(delegate(Node n) { toRemove.Add(n.Item); return true; });
  1540. while (toRemove.Count != 0) {
  1541. underlying.Remove(toRemove[toRemove.Count - 1]);
  1542. toRemove.RemoveAt(toRemove.Count - 1);
  1543. }
  1544. root = null;
  1545. count = 0;
  1546. version = underlying.version;
  1547. }
  1548. internal override bool IsWithinRange(T item) {
  1549. int comp = (lBoundActive ? Comparer.Compare(min, item) : -1);
  1550. if (comp > 0) {
  1551. return false;
  1552. }
  1553. comp = (uBoundActive ? Comparer.Compare(max, item) : 1);
  1554. if (comp < 0) {
  1555. return false;
  1556. }
  1557. return true;
  1558. }
  1559. internal override bool InOrderTreeWalk(TreeWalkPredicate<T> action, Boolean reverse) {
  1560. VersionCheck();
  1561. if (root == null) {
  1562. return true;
  1563. }
  1564. // The maximum height of a red-black tree is 2*lg(n+1).
  1565. // See page 264 of "Introduction to algorithms" by Thomas H. Cormen
  1566. 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
  1567. Node current = root;
  1568. while (current != null) {
  1569. if (IsWithinRange(current.Item)) {
  1570. stack.Push(current);
  1571. current = (reverse ? current.Right : current.Left);
  1572. } else if (lBoundActive && Comparer.Compare(min, current.Item) > 0) {
  1573. current = current.Right;
  1574. } else {
  1575. current = current.Left;
  1576. }
  1577. }
  1578. while (stack.Count != 0) {
  1579. current = stack.Pop();
  1580. if (!action(current)) {
  1581. return false;
  1582. }
  1583. Node node = (reverse ? current.Left : current.Right);
  1584. while (node != null) {
  1585. if (IsWithinRange(node.Item)) {
  1586. stack.Push(node);
  1587. node = (reverse ? node.Right : node.Left);
  1588. } else if (lBoundActive && Comparer.Compare(min, node.Item) > 0) {
  1589. node = node.Right;
  1590. } else {
  1591. node = node.Left;
  1592. }
  1593. }
  1594. }
  1595. return true;
  1596. }
  1597. internal override bool BreadthFirstTreeWalk(TreeWalkPredicate<T> action) {
  1598. VersionCheck();
  1599. if (root == null) {
  1600. return true;
  1601. }
  1602. List<Node> processQueue = new List<Node>();
  1603. processQueue.Add(root);
  1604. Node current;
  1605. while (processQueue.Count != 0) {
  1606. current = processQueue[0];
  1607. processQueue.RemoveAt(0);
  1608. if (IsWithinRange(current.Item) && !action(current)) {
  1609. return false;
  1610. }
  1611. if (current.Left != null && (!lBoundActive || Comparer.Compare(min, current.Item) < 0)) {
  1612. processQueue.Add(current.Left);
  1613. }
  1614. if (current.Right != null && (!uBoundActive || Comparer.Compare(max, current.Item) > 0)) {
  1615. processQueue.Add(current.Right);
  1616. }
  1617. }
  1618. return true;
  1619. }
  1620. internal override SortedSet<T>.Node FindNode(T item) {
  1621. if (!IsWithinRange(item)) {
  1622. return null;
  1623. }
  1624. VersionCheck();
  1625. #if DEBUG
  1626. Debug.Assert(this.versionUpToDate() && this.root == this.underlying.FindRange(min, max));
  1627. #endif
  1628. return base.FindNode(item);
  1629. }
  1630. //this does indexing in an inefficient way compared to the actual sortedset, but it saves a
  1631. //lot of space
  1632. internal override int InternalIndexOf(T item) {
  1633. int count = -1;
  1634. foreach (T i in this) {
  1635. count++;
  1636. if (Comparer.Compare(item, i) == 0)
  1637. return count;
  1638. }
  1639. #if DEBUG
  1640. Debug.Assert(this.versionUpToDate() && this.root == this.underlying.FindRange(min, max));
  1641. #endif
  1642. return -1;
  1643. }
  1644. /// <summary>
  1645. /// checks whether this subset is out of date. updates if necessary.
  1646. /// </summary>
  1647. internal override void VersionCheck() {
  1648. VersionCheckImpl();
  1649. }
  1650. private void VersionCheckImpl() {
  1651. Debug.Assert(underlying != null, "Underlying set no longer exists");
  1652. if (this.version != underlying.version) {
  1653. this.root = underlying.FindRange(min, max, lBoundActive, uBoundActive);
  1654. this.version = underlying.version;
  1655. count = 0;
  1656. InOrderTreeWalk(delegate(Node n) { count++; return true; });
  1657. }
  1658. }
  1659. //This passes functionality down to the underlying tree, clipping edges if necessary
  1660. //There‘s nothing gained by having a nested subset. May as well draw it from the base
  1661. //Cannot increase the bounds of the subset, can only decrease it
  1662. public override SortedSet<T> GetViewBetween(T lowerValue, T upperValue) {
  1663. if (lBoundActive && Comparer.Compare(min, lowerValue) > 0) {
  1664. //lBound = min;
  1665. throw new ArgumentOutOfRangeException("lowerValue");
  1666. }
  1667. if (uBoundActive && Comparer.Compare(max, upperValue) < 0) {
  1668. //uBound = max;
  1669. throw new ArgumentOutOfRangeException("upperValue");
  1670. }
  1671. TreeSubSet ret = (TreeSubSet)underlying.GetViewBetween(lowerValue, upperValue);
  1672. return ret;
  1673. }
  1674. internal override void IntersectWithEnumerable(IEnumerable<T> other) {
  1675. List<T> toSave = new List<T>(this.Count);
  1676. foreach (T item in other) {
  1677. if (this.Contains(item)) {
  1678. toSave.Add(item);
  1679. this.Remove(item);
  1680. }
  1681. }
  1682. this.Clear();
  1683. this.AddAllElements(toSave);
  1684. #if DEBUG
  1685. Debug.Assert(this.versionUpToDate() && this.root == this.underlying.FindRange(min, max));
  1686. #endif
  1687. }
  1688. #if !FEATURE_NETCORE
  1689. void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context) {
  1690. GetObjectData(info, context);
  1691. }
  1692. protected override void GetObjectData(SerializationInfo info, StreamingContext context) {
  1693. if (info == null) {
  1694. ThrowHelper.ThrowArgumentNullException(ExceptionArgument.info);
  1695. }
  1696. info.AddValue(maxName, max, typeof(T));
  1697. info.AddValue(minName, min, typeof(T));
  1698. info.AddValue(lBoundActiveName, lBoundActive);
  1699. info.AddValue(uBoundActiveName, uBoundActive);
  1700. base.GetObjectData(info, context);
  1701. }
  1702. void IDeserializationCallback.OnDeserialization(Object sender) {
  1703. //don‘t do anything here as its already been done by the constructor
  1704. //OnDeserialization(sender);
  1705. }
  1706. protected override void OnDeserialization(Object sender) {
  1707. OnDeserializationImpl(sender);
  1708. }
  1709. private void OnDeserializationImpl(Object sender) {
  1710. if (siInfo == null) {
  1711. ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_InvalidOnDeser);
  1712. }
  1713. comparer = (IComparer<T>)siInfo.GetValue(ComparerName, typeof(IComparer<T>));
  1714. int savedCount = siInfo.GetInt32(CountName);
  1715. max = (T)siInfo.GetValue(maxName, typeof(T));
  1716. min = (T)siInfo.GetValue(minName, typeof(T));
  1717. lBoundActive = siInfo.GetBoolean(lBoundActiveName);
  1718. uBoundActive = siInfo.GetBoolean(uBoundActiveName);
  1719. underlying = new SortedSet<T>();
  1720. if (savedCount != 0) {
  1721. T[] items = (T[])siInfo.GetValue(ItemsName, typeof(T[]));
  1722. if (items == null) {
  1723. ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_MissingValues);
  1724. }
  1725. for (int i = 0; i < items.Length; i++) {
  1726. underlying.Add(items[i]);
  1727. }
  1728. }
  1729. underlying.version = siInfo.GetInt32(VersionName);
  1730. count = underlying.count;
  1731. version = underlying.version - 1;
  1732. VersionCheck(); //this should update the count to be right and update root to be right
  1733. if (count != savedCount) {
  1734. ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_MismatchedCount);
  1735. }
  1736. siInfo = null;
  1737. }
  1738. #endif // !FEATURE_NETCORE
  1739. }
  1740. #endregion
  1741. #region Serialization methods
  1742. #if !FEATURE_NETCORE
  1743. // LinkDemand here is unnecessary as this is a methodimpl and linkdemand from the interface should suffice
  1744. void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context) {
  1745. GetObjectData(info, context);
  1746. }
  1747. protected virtual void GetObjectData(SerializationInfo info, StreamingContext context) {
  1748. if (info == null) {
  1749. ThrowHelper.ThrowArgumentNullException(ExceptionArgument.info);
  1750. }
  1751. info.AddValue(CountName, count); //This is the length of the bucket array.
  1752. info.AddValue(ComparerName, comparer, typeof(IComparer<T>));
  1753. info.AddValue(VersionName, version);
  1754. if (root != null) {
  1755. T[] items = new T[Count];
  1756. CopyTo(items, 0);
  1757. info.AddValue(ItemsName, items, typeof(T[]));
  1758. }
  1759. }
  1760. void IDeserializationCallback.OnDeserialization(Object sender) {
  1761. OnDeserialization(sender);
  1762. }
  1763. protected virtual void OnDeserialization(Object sender) {
  1764. if (comparer != null) {
  1765. return; //Somebody had a dependency on this class and fixed us up before the ObjectManager got to it.
  1766. }
  1767. if (siInfo == null) {
  1768. ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_InvalidOnDeser);
  1769. }
  1770. comparer = (IComparer<T>)siInfo.GetValue(ComparerName, typeof(IComparer<T>));
  1771. int savedCount = siInfo.GetInt32(CountName);
  1772. if (savedCount != 0) {
  1773. T[] items = (T[])siInfo.GetValue(ItemsName, typeof(T[]));
  1774. if (items == null) {
  1775. ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_MissingValues);
  1776. }
  1777. for (int i = 0; i < items.Length; i++) {
  1778. Add(items[i]);
  1779. }
  1780. }
  1781. version = siInfo.GetInt32(VersionName);
  1782. if (count != savedCount) {
  1783. ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_MismatchedCount);
  1784. }
  1785. siInfo = null;
  1786. }
  1787. #endif //!FEATURE_NETCORE
  1788. #endregion
  1789. #region Helper Classes
  1790. internal class Node {
  1791. public bool IsRed;
  1792. public T Item;
  1793. public Node Left;
  1794. public Node Right;
  1795. public Node(T item) {
  1796. // The default color will be red, we never need to create a black node directly.
  1797. this.Item = item;
  1798. IsRed = true;
  1799. }
  1800. public Node(T item, bool isRed) {
  1801. // The default color will be red, we never need to create a black node directly.
  1802. this.Item = item;
  1803. this.IsRed = isRed;
  1804. }
  1805. }
  1806. [SuppressMessage("Microsoft.Performance", "CA1815:OverrideEqualsAndOperatorEqualsOnValueTypes", Justification = "not an expected scenario")]
  1807. #if !FEATURE_NETCORE
  1808. [Serializable]
  1809. public struct Enumerator : IEnumerator<T>, IEnumerator, ISerializable, IDeserializationCallback {
  1810. #else
  1811. public struct Enumerator : IEnumerator<T>, IEnumerator {
  1812. #endif
  1813. private SortedSet<T> tree;
  1814. private int version;
  1815. private Stack<SortedSet<T>.Node> stack;
  1816. private SortedSet<T>.Node current;
  1817. static SortedSet<T>.Node dummyNode = new SortedSet<T>.Node(default(T));
  1818. private bool reverse;
  1819. #if !FEATURE_NETCORE
  1820. private SerializationInfo siInfo;
  1821. #endif
  1822. internal Enumerator(SortedSet<T> set) {
  1823. tree = set;
  1824. //this is a hack to make sure that the underlying subset has not been changed since
  1825. //
  1826. tree.VersionCheck();
  1827. version = tree.version;
  1828. // 2lg(n + 1) is the maximum height
  1829. stack = new Stack<SortedSet<T>.Node>(2 * (int)SortedSet<T>.log2(set.Count + 1));
  1830. current = null;
  1831. reverse = false;
  1832. #if !FEATURE_NETCORE
  1833. siInfo = null;
  1834. #endif
  1835. Intialize();
  1836. }
  1837. internal Enumerator(SortedSet<T> set, bool reverse) {
  1838. tree = set;
  1839. //this is a hack to make sure that the underlying subset has not been changed since
  1840. //
  1841. tree.VersionCheck();
  1842. version = tree.version;
  1843. // 2lg(n + 1) is the maximum height
  1844. stack = new Stack<SortedSet<T>.Node>(2 * (int)SortedSet<T>.log2(set.Count + 1));
  1845. current = null;
  1846. this.reverse = reverse;
  1847. #if !FEATURE_NETCORE
  1848. siInfo = null;
  1849. #endif
  1850. Intialize();
  1851. }
  1852. #if !FEATURE_NETCORE
  1853. private Enumerator(SerializationInfo info, StreamingContext context) {
  1854. tree = null;
  1855. version = -1;
  1856. current = null;
  1857. reverse = false;
  1858. stack = null;
  1859. this.siInfo = info;
  1860. }
  1861. void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context) {
  1862. GetObjectData(info, context);
  1863. }
  1864. private void GetObjectData(SerializationInfo info, StreamingContext context) {
  1865. if (info == null) {
  1866. ThrowHelper.ThrowArgumentNullException(ExceptionArgument.info);
  1867. }
  1868. info.AddValue(TreeName, tree, typeof(SortedSet<T>));
  1869. info.AddValue(EnumVersionName, version);
  1870. info.AddValue(ReverseName, reverse);
  1871. info.AddValue(EnumStartName, !NotStartedOrEnded);
  1872. info.AddValue(NodeValueName, (current == null ? dummyNode.Item : current.Item), typeof(T));
  1873. }
  1874. void IDeserializationCallback.OnDeserialization(Object sender) {
  1875. OnDeserialization(sender);
  1876. }
  1877. private void OnDeserialization(Object sender) {
  1878. if (siInfo == null) {
  1879. ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_InvalidOnDeser);
  1880. }
  1881. tree = (SortedSet<T>)siInfo.GetValue(TreeName, typeof(SortedSet<T>));
  1882. version = siInfo.GetInt32(EnumVersionName);
  1883. reverse = siInfo.GetBoolean(ReverseName);
  1884. bool EnumStarted = siInfo.GetBoolean(EnumStartName);
  1885. stack = new Stack<SortedSet<T>.Node>(2 * (int)SortedSet<T>.log2(tree.Count + 1));
  1886. current = null;
  1887. if (EnumStarted) {
  1888. T item = (T)siInfo.GetValue(NodeValueName, typeof(T));
  1889. Intialize();
  1890. //go until it reaches the value we want
  1891. while (this.MoveNext()) {
  1892. if (tree.Comparer.Compare(this.Current, item) == 0)
  1893. break;
  1894. }
  1895. }
  1896. }
  1897. #endif //!FEATURE_NETCORE
  1898. private void Intialize() {
  1899. current = null;
  1900. SortedSet<T>.Node node = tree.root;
  1901. Node next = null, other = null;
  1902. while (node != null) {
  1903. next = (reverse ? node.Right : node.Left);
  1904. other = (reverse ? node.Left : node.Right);
  1905. if (tree.IsWithinRange(node.Item)) {
  1906. stack.Push(node);
  1907. node = next;
  1908. } else if (next == null || !tree.IsWithinRange(next.Item)) {
  1909. node = other;
  1910. } else {
  1911. node = next;
  1912. }
  1913. }
  1914. }
  1915. public bool MoveNext() {
  1916. //this is a hack to make sure that the underlying subset has not been changed since
  1917. //
  1918. tree.VersionCheck();
  1919. if (version != tree.version) {
  1920. ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
  1921. }
  1922. if (stack.Count == 0) {
  1923. current = null;
  1924. return false;
  1925. }
  1926. current = stack.Pop();
  1927. SortedSet<T>.Node node = (reverse ? current.Left : current.Right);
  1928. Node next = null, other = null;
  1929. while (node != null) {
  1930. next = (reverse ? node.Right : node.Left);
  1931. other = (reverse ? node.Left : node.Right);
  1932. if (tree.IsWithinRange(node.Item)) {
  1933. stack.Push(node);
  1934. node = next;
  1935. } else if (other == null || !tree.IsWithinRange(other.Item)) {
  1936. node = next;
  1937. } else {
  1938. node = other;
  1939. }
  1940. }
  1941. return true;
  1942. }
  1943. public void Dispose() {
  1944. }
  1945. public T Current {
  1946. get {
  1947. if (current != null) {
  1948. return current.Item;
  1949. }
  1950. return default(T);
  1951. }
  1952. }
  1953. object IEnumerator.Current {
  1954. get {
  1955. if (current == null) {
  1956. ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
  1957. }
  1958. return current.Item;
  1959. }
  1960. }
  1961. internal bool NotStartedOrEnded {
  1962. get {
  1963. return current == null;
  1964. }
  1965. }
  1966. internal void Reset() {
  1967. if (version != tree.version) {
  1968. ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
  1969. }
  1970. stack.Clear();
  1971. Intialize();
  1972. }
  1973. void IEnumerator.Reset() {
  1974. Reset();
  1975. }
  1976. }
  1977. internal struct ElementCount {
  1978. internal int uniqueCount;
  1979. internal int unfoundCount;
  1980. }
  1981. #endregion
  1982. #region misc
  1983. // used for set checking operations (using enumerables) that rely on counting
  1984. private static int log2(int value) {
  1985. //Contract.Requires(value>0)
  1986. int c = 0;
  1987. while (value > 0) {
  1988. c++;
  1989. value >>= 1;
  1990. }
  1991. return c;
  1992. }
  1993. #endregion
  1994. }
  1995. /// <summary>
  1996. /// A class that generates an IEqualityComparer for this SortedSet. Requires that the definition of
  1997. /// equality defined by the IComparer for this SortedSet be consistent with the default IEqualityComparer
  1998. /// for the type T. If not, such an IEqualityComparer should be provided through the constructor.
  1999. /// </summary>
  2000. internal class SortedSetEqualityComparer<T> : IEqualityComparer<SortedSet<T>> {
  2001. private IComparer<T> comparer;
  2002. private IEqualityComparer<T> e_comparer;
  2003. public SortedSetEqualityComparer() : this(null, null) { }
  2004. public SortedSetEqualityComparer(IComparer<T> comparer) : this(comparer, null) { }
  2005. public SortedSetEqualityComparer(IEqualityComparer<T> memberEqualityComparer) : this(null, memberEqualityComparer) { }
  2006. /// <summary>
  2007. /// Create a new SetEqualityComparer, given a comparer for member order and another for member equality (these
  2008. /// must be consistent in their definition of equality)
  2009. /// </summary>
  2010. public SortedSetEqualityComparer(IComparer<T> comparer, IEqualityComparer<T> memberEqualityComparer) {
  2011. if (comparer == null)
  2012. this.comparer = Comparer<T>.Default;
  2013. else
  2014. this.comparer = comparer;
  2015. if (memberEqualityComparer == null)
  2016. e_comparer = EqualityComparer<T>.Default;
  2017. else
  2018. e_comparer = memberEqualityComparer;
  2019. }
  2020. // using comparer to keep equals properties in tact; don‘t want to choose one of the comparers
  2021. public bool Equals(SortedSet<T> x, SortedSet<T> y) {
  2022. return SortedSet<T>.SortedSetEquals(x, y, comparer);
  2023. }
  2024. //IMPORTANT: this part uses the fact that GetHashCode() is consistent with the notion of equality in
  2025. //the set
  2026. public int GetHashCode(SortedSet<T> obj) {
  2027. int hashCode = 0;
  2028. if (obj != null) {
  2029. foreach (T t in obj) {
  2030. hashCode = hashCode ^ (e_comparer.GetHashCode(t) & 0x7FFFFFFF);
  2031. }
  2032. } // else returns hashcode of 0 for null HashSets
  2033. return hashCode;
  2034. }
  2035. // Equals method for the comparer itself.
  2036. public override bool Equals(Object obj) {
  2037. SortedSetEqualityComparer<T> comparer = obj as SortedSetEqualityComparer<T>;
  2038. if (comparer == null) {
  2039. return false;
  2040. }
  2041. return (this.comparer == comparer.comparer);
  2042. }
  2043. public override int GetHashCode() {
  2044. return comparer.GetHashCode() ^ e_comparer.GetHashCode();
  2045. }
  2046. }
  2047. }



null


.NET源码 SortedSet(红黑树)