// Licensed to the .NET Foundation under one or more agreements. // The .NET Foundation licenses this file to you under the MIT license. // See the LICENSE file in the project root for more information. using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using Microsoft.CodeAnalysis.Collections; using Microsoft.CodeAnalysis.Collections.Internal; using Roslyn.Utilities; namespace Microsoft.CodeAnalysis.Shared.Collections; /// <summary> /// Implementation of an <see cref="IIntervalTree{T}"/> backed by a contiguous array of values. This is a more memory /// efficient way to store an interval tree than the traditional binary tree approach. This should be used when the /// values of the interval tree are known up front and will not change after the tree is created. /// </summary> /// <typeparam name="T"></typeparam> internal readonly struct ImmutableIntervalTree<T> : IIntervalTree<T> { private readonly record struct Node(T Value, int MaxEndNodeIndex); public static readonly ImmutableIntervalTree<T> Empty = new(new SegmentedArray<Node>(0)); /// <summary> /// The nodes of this interval tree flatted into a single array. The root is as index 0. The left child of any /// node at index <c>i</c> is at <c>2*i + 1</c> and the right child is at <c>2*i + 2</c>. If a left/right child /// index is beyond the length of this array, that is equivalent to that node not having such a child. /// </summary> /// <remarks> /// The binary tree we represent here is a *complete* binary tree (not to be confused with a *perfect* binary tree). /// A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, /// and all nodes in the last level are as far left as possible. /// </remarks> private readonly SegmentedArray<Node> _array; private ImmutableIntervalTree(SegmentedArray<Node> array) => _array = array; /// <summary> /// Provides access to lots of common algorithms on this interval tree. /// </summary> public IntervalTreeAlgorithms<T, ImmutableIntervalTree<T>> Algorithms => new(this); /// <summary> /// Creates a <see cref="ImmutableIntervalTree{T}"/> from an unsorted list of <paramref name="values"/>. This will /// incur a delegate allocation to sort the values. If callers can avoid that allocation by pre-sorting the values, /// they should do so and call <see cref="CreateFromSorted"/> instead. /// </summary> /// <remarks> /// <paramref name="values"/> will be sorted in place. /// </remarks> public static ImmutableIntervalTree<T> CreateFromUnsorted<TIntrospector>(in TIntrospector introspector, SegmentedList<T> values) where TIntrospector : struct, IIntervalIntrospector<T> { var localIntrospector = introspector; values.Sort((t1, t2) => localIntrospector.GetSpan(t1).Start - localIntrospector.GetSpan(t2).Start); return CreateFromSorted(introspector, values); } /// <summary> /// Creates an interval tree from a sorted list of values. This is more efficient than creating from an unsorted /// list as building doesn't need to figure out where the nodes need to go n-log(n) and doesn't have to rebalance /// anything (again, another n-log(n) operation). Rebalancing is particularly expensive as it involves tons of /// pointer chasing operations, which is both slow, and which impacts the GC which has to track all those writes. /// </summary> /// <remarks> /// The values must be sorted such that given any two elements 'a' and 'b' in the list, if 'a' comes before 'b' in /// the list, then it's "start position" (as determined by the introspector) must be less than or equal to 'b's /// start position. This is a requirement for the algorithm to work correctly. /// </remarks> public static ImmutableIntervalTree<T> CreateFromSorted<TIntrospector>(in TIntrospector introspector, SegmentedList<T> values) where TIntrospector : struct, IIntervalIntrospector<T> { #if DEBUG var localIntrospector = introspector; Debug.Assert(values.IsSorted(Comparer<T>.Create((t1, t2) => localIntrospector.GetSpan(t1).Start - localIntrospector.GetSpan(t2).Start))); #endif if (values.Count == 0) return Empty; // Create the array to sort the binary search tree nodes in. var array = new SegmentedArray<Node>(values.Count); // Place the values into the array in a way that will create a complete binary tree. BuildCompleteTree(values, sourceStartInclusive: 0, sourceEndExclusive: values.Count, array, destinationIndex: 0); // Next, do a pass over the entire tree, updating each node to point at the max end node in its subtree. ComputeMaxEndNodes(array, 0, in introspector); return new ImmutableIntervalTree<T>(array); static void BuildCompleteTree( SegmentedList<T> source, int sourceStartInclusive, int sourceEndExclusive, SegmentedArray<Node> destination, int destinationIndex) { var length = sourceEndExclusive - sourceStartInclusive; if (length == 0) return; // Find the element we want to make the root of this subtree. // // Note: rootIndex is computed entirely based on the length of the subtree. So it comes back in the range // [0, length). // // To then index into source, we need to offset it by sourceStartInclusive as that is the start of the // source corresponding to the subtree we've walked into. var rootIndex = GetRootSourceIndex(length); var rootIndexInSource = sourceStartInclusive + rootIndex; // Place that element in the appropriate location in the destination. destination[destinationIndex] = new(source[rootIndexInSource], destinationIndex); // Now recurse into the left and right subtrees to the left/right of the root index in this subtree. BuildCompleteTree(source, sourceStartInclusive, rootIndexInSource, destination, destinationIndex * 2 + 1); BuildCompleteTree(source, rootIndexInSource + 1, sourceEndExclusive, destination, destinationIndex * 2 + 2); } // <param name="subtreeNodeCount">Number of nodes in this particular subtree</param> static int GetRootSourceIndex(int subtreeNodeCount) { // Trivial case. The tree has one element. That element will be the root. if (subtreeNodeCount == 1) return 0; // We are building a complete binary tree. By definition, this means that we either have a perfect tree // (where every level is full). Or we have a tree where every level is full except the last level which is // filled from left to right. // // The perfect case is trivial. We simply take the middle element of the array and make it the root, and // then recurse into the left and right halves of the array. // The height of the perfect portion of the tree (the rows that are completely full from left to right). // This is '3' in both of the examples below. It will be the height of the whole tree if the whole tree is // perfect itself. var perfectPortionHeight = SegmentedArraySortUtils.Log2((uint)subtreeNodeCount + 1); // Then number of nodes in the perfect portion. For the example trees below this is 7. var perfectPortionNodeCount = PerfectTreeNodeCount(perfectPortionHeight); // If the entire subtree we're looking at is perfect or not. It's perfect if every layer is full. // In the above example, both trees are not perfect. var wholeSubtreeIsPerfect = perfectPortionNodeCount == subtreeNodeCount; // If we do have a perfect tree, the root item trivially the s the middle element of that tree. var perfectPortionMidwayPoint = perfectPortionNodeCount / 2; if (wholeSubtreeIsPerfect) return perfectPortionMidwayPoint; // The interesting, imperfect, cases case be demonstrated with the following examples: // // 10 elements: // g, d, i, b, f, h, j, a, c, e // // g // _____/ \_____ // d i // __/ \__ / \ // b f h j // / \ / // a c e // // 13 elements: // h, d, l, b, f, j, m, a, c, e, g, i, k // // h // _____/ \_____ // d l // __/ \__ / \ // b f j m // / \ / \ / \ // a c e g i k // // The difference in these cases is the 'd' subtree. We either have: // // 1. not enough elements to start filling the right sibling ('i'). This is the case in the 10 element // tree. // // 2. enough elements to fill it and start filling its right sibling ('l'). This is the case in the 13 // element tree. // // In both cases, one of the two children of the root will be a perfect tree (the right child in the 10 // element case, and the left element in the 13 element case). So, when we recurse into either, we either // recurse into a perfect tree (which we know is trivial to handle). Or we will recurse into another tree // that we can handle using the balancing logic below. // The total tree height. Since we know we're not perfect, we computed based on one greater than than the // perfect-portion height. var nodeCountIfTreeWerePerfect = PerfectTreeNodeCount(height: perfectPortionHeight + 1); var elementsInLastIncompleteRow = subtreeNodeCount - perfectPortionNodeCount; var elementsInLastRowIfTreeWerePerfect = nodeCountIfTreeWerePerfect - perfectPortionNodeCount; // The min point in the last row. If we have it filled less than half full, it's the number of elements. // If it is more than half full, it's the midway point. var elementsInLastRowCappedAtMidwayPoint = Math.Min(elementsInLastIncompleteRow, elementsInLastRowIfTreeWerePerfect / 2); // The pivot point in the array. While filling up the first half of the final row, we're continually // incrementing the pivot point (so we include more elements in the left tree). Once we hit the halfway // point in the last row, then we want to stop incrementing the pivot point (so that we include more // elements in the right tree). return perfectPortionMidwayPoint + elementsInLastRowCappedAtMidwayPoint; } static int PerfectTreeNodeCount(int height) => (1 << height) - 1; // Returns the max end *position* of tree rooted at currentNodeIndex. If there is no tree here (it refers to a // null child), then this will return -1; static int ComputeMaxEndNodes(SegmentedArray<Node> array, int currentNodeIndex, in TIntrospector introspector) { if (currentNodeIndex >= array.Length) return -1; var leftChildIndex = GetLeftChildIndex(currentNodeIndex); var rightChildIndex = GetRightChildIndex(currentNodeIndex); // ensure the left and right trees have their max end nodes computed first. var leftMaxEndValue = ComputeMaxEndNodes(array, leftChildIndex, in introspector); var rightMaxEndValue = ComputeMaxEndNodes(array, rightChildIndex, in introspector); // Now get the max end of the left and right children and compare to our end. Whichever is the rightmost // endpoint is considered the max end index. var currentNode = array[currentNodeIndex]; var thisEndValue = introspector.GetSpan(currentNode.Value).End; if (thisEndValue >= leftMaxEndValue && thisEndValue >= rightMaxEndValue) { // The root's end was further to the right than both the left subtree and the right subtree. No need to // change it as that is what we store by default for any node. return thisEndValue; } // One of the left or right subtrees went further to the right. Contract.ThrowIfTrue(leftMaxEndValue < 0 && rightMaxEndValue < 0); if (leftMaxEndValue >= rightMaxEndValue) { // Set this node's max end to be the left subtree's max end. var maxEndNodeIndex = array[leftChildIndex].MaxEndNodeIndex; array[currentNodeIndex] = new Node(currentNode.Value, maxEndNodeIndex); return leftMaxEndValue; } else { Contract.ThrowIfFalse(rightMaxEndValue > leftMaxEndValue); // Set this node's max end to be the right subtree's max end. var maxEndNodeIndex = array[rightChildIndex].MaxEndNodeIndex; array[currentNodeIndex] = new Node(currentNode.Value, maxEndNodeIndex); return rightMaxEndValue; } } } private static int GetLeftChildIndex(int nodeIndex) => (2 * nodeIndex) + 1; private static int GetRightChildIndex(int nodeIndex) => (2 * nodeIndex) + 2; bool IIntervalTree<T>.Any<TIntrospector, TIntervalTester>(int start, int length, in TIntrospector introspector, in TIntervalTester intervalTester) => IntervalTreeHelpers<T, ImmutableIntervalTree<T>, /*TNode*/ int, FlatArrayIntervalTreeWitness>.Any(this, start, length, introspector, intervalTester); int IIntervalTree<T>.FillWithIntervalsThatMatch<TIntrospector, TIntervalTester>( int start, int length, ref TemporaryArray<T> builder, in TIntrospector introspector, in TIntervalTester intervalTester, bool stopAfterFirst) { return IntervalTreeHelpers<T, ImmutableIntervalTree<T>, /*TNode*/ int, FlatArrayIntervalTreeWitness>.FillWithIntervalsThatMatch( this, start, length, ref builder, in introspector, in intervalTester, stopAfterFirst); } IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator(); public IntervalTreeHelpers<T, ImmutableIntervalTree<T>, /*TNode*/ int, FlatArrayIntervalTreeWitness>.Enumerator GetEnumerator() => IntervalTreeHelpers<T, ImmutableIntervalTree<T>, /*TNode*/ int, FlatArrayIntervalTreeWitness>.GetEnumerator(this); /// <summary> /// Wrapper type to allow the IntervalTreeHelpers type to work with this type. /// </summary> internal readonly struct FlatArrayIntervalTreeWitness : IIntervalTreeWitness<T, ImmutableIntervalTree<T>, int> { public T GetValue(ImmutableIntervalTree<T> tree, int node) => tree._array[node].Value; public int GetMaxEndNode(ImmutableIntervalTree<T> tree, int node) => tree._array[node].MaxEndNodeIndex; public bool TryGetRoot(ImmutableIntervalTree<T> tree, out int root) { root = 0; return tree._array.Length > 0; } public bool TryGetLeftNode(ImmutableIntervalTree<T> tree, int node, out int leftNode) { leftNode = GetLeftChildIndex(node); return leftNode < tree._array.Length; } public bool TryGetRightNode(ImmutableIntervalTree<T> tree, int node, out int rightNode) { rightNode = GetRightChildIndex(node); return rightNode < tree._array.Length; } } } |