API Proposal SortedSet<T> Nearest Element APIs Enhance .NET Sorted Sets

This article discusses an API proposal to enhance the SortedSet<T> class in .NET by introducing methods for efficiently finding the nearest elements. Specifically, the proposal suggests adding four new methods: GetLowerThan, GetLowerThanEqualTo, GetHigherThanEqualTo, and GetHigherThan. These methods aim to provide developers with a more streamlined and performant way to locate elements within a sorted set that are closest to a given value. This article delves into the background, motivation, proposed API, usage examples, and alternative designs considered for this enhancement. By addressing the current limitations of the SortedSet<T> class, this proposal seeks to improve the developer experience and enable more efficient implementations of various algorithms and data structures.

Background and Motivation

The SortedSet<T> class in .NET is a valuable tool for maintaining a collection of unique elements in a sorted order. However, it currently lacks built-in methods to directly find elements that are nearest to a specified value. This limitation often forces developers to resort to manual and less efficient workarounds. The current methods available do not provide an optimal solution for scenarios where finding the immediate lower or upper bounds is crucial. This proposal addresses this gap by introducing methods that offer a more direct and efficient way to retrieve these nearest elements.

Currently, developers needing to find the nearest elements in a SortedSet<T> must rely on manual iteration or other less-than-ideal approaches. These workarounds often involve using IEnumerable based search patterns, which can be cumbersome and performance-intensive, especially for large sets. For example, a developer might need to iterate through the set to find the largest element less than a given value, which can be an O(N) operation. This contrasts with the potential for O(log N) performance that could be achieved with dedicated methods for this purpose. The absence of these methods leads to increased code complexity and reduced performance in scenarios where nearest element lookups are frequent.

The proposal introduces four new API methods to address this issue, which provide a more efficient and intuitive way to find the nearest elements. These methods are designed to enhance the functionality of SortedSet<T> by allowing developers to quickly and easily find elements that meet specific criteria related to a target value. The addition of these methods not only simplifies the code required for such operations but also significantly improves performance by leveraging the sorted nature of the set. This enhancement is particularly beneficial in applications where performance and efficiency are critical, such as real-time systems, large-scale data processing, and high-frequency trading platforms.

• GetLowerThan(T item) – Returns the greatest element strictly less than the given item.
• GetLowerThanEqualTo(T item) – Returns the greatest element less than or equal to the given item.
• GetHigherThanEqualTo(T item) – Returns the smallest element greater than or equal to the given item.
• GetHigherThan(T item) – Returns the smallest element strictly greater than the given item.

These methods are designed to provide a more intuitive and efficient way to interact with sorted sets, aligning with common use cases and developer expectations. By offering direct access to the nearest elements, the proposed API reduces the need for manual iteration and complex logic, making the SortedSet<T> class more versatile and user-friendly. This improvement is expected to have a positive impact on the overall developer experience and the performance of applications that utilize sorted sets.

Comparison with GetViewBetween

While the existing GetViewBetween method provides a way to extract a subset of the SortedSet<T> within specified bounds, it does not offer the same level of efficiency or direct access as the proposed methods. Understanding the differences between GetViewBetween and the new methods is crucial for choosing the right tool for a specific task. This comparison highlights the performance advantages and specific use cases for the new API, further emphasizing its value.

GetViewBetween: Returns a subset of the SortedSet<T> between the specified lower and upper bounds. This method is useful when you need to extract multiple elements within a given range. However, it does not provide direct access to a single element at the lower or upper bound. The time complexity of GetViewBetween is O(N), where N is the number of elements in the set, as it potentially needs to iterate through a significant portion of the set to create the view. This makes it less efficient for scenarios where only a single nearest element is required.

In contrast, the proposed methods (GetLowerThan, GetLowerThanEqualTo, GetHigherThanEqualTo, and GetHigherThan) are designed to provide direct access to the nearest elements in O(log N) time complexity. This logarithmic time complexity is a significant improvement over the linear time complexity of GetViewBetween, especially for large sets. The new methods leverage the sorted nature of the set to quickly locate the desired elements without the need for extensive iteration. This efficiency makes them ideal for scenarios where performance is critical and only the nearest elements are of interest.

Furthermore, GetViewBetween returns a new SortedSet<T> instance representing the subset, which can incur additional memory overhead. The proposed methods, on the other hand, simply return the element itself, avoiding the overhead of creating a new collection. This makes the new methods more memory-efficient and suitable for applications with memory constraints. The direct access and lower overhead of the new methods make them a superior choice for finding single nearest elements within a sorted set.

The primary advantage of GetViewBetween lies in its ability to extract a range of elements. It is particularly useful when you need to perform operations on a subset of the sorted set, such as filtering or transforming elements within a specific range. However, for the specific task of finding the nearest elements, the proposed methods offer a more efficient and direct solution. The choice between GetViewBetween and the new methods depends on the specific requirements of the task, with the new methods being the preferred option for single element lookups and performance-critical scenarios.

Comparison with Other Languages

To further illustrate the value of the proposed API, it is beneficial to compare its functionality with similar features in other programming languages and libraries. Many popular languages provide built-in methods for finding nearest elements in sorted collections, highlighting the widespread need for this functionality. This comparison underscores the importance of adding these methods to .NET's SortedSet<T> class to align with industry standards and provide developers with a more complete and efficient toolset.

Language / Library	Equivalent Methods
Java (TreeSet)	lower(), floor(), ceiling(), higher()
C++ (std::set)	lower_bound(), upper_bound() with reverse iterators
Python (bisect)	bisect_left(), bisect_right()
Rust (BTreeSet)	range(), iter(), split_off()

In Java's TreeSet, the lower() method returns the greatest element strictly less than the given element, floor() returns the greatest element less than or equal to the given element, ceiling() returns the smallest element greater than or equal to the given element, and higher() returns the smallest element strictly greater than the given element. These methods provide functionality directly analogous to the proposed methods for SortedSet<T>, demonstrating the established pattern for nearest element lookups in sorted sets.

C++'s std::set provides lower_bound() and upper_bound() methods, which return iterators to the first element not less than (i.e., greater than or equal to) and the first element greater than a given value, respectively. To find the elements strictly less than or less than or equal to a value, reverse iterators must be used in conjunction with these methods. While C++ provides similar functionality, the need to use reverse iterators for certain operations adds complexity compared to the direct methods proposed for .NET.

Python's bisect module offers bisect_left() and bisect_right() functions, which return the insertion point for a value in a sorted list to maintain the sorted order. These functions can be used to find the nearest elements, but they require additional logic to retrieve the actual elements. The proposed methods for .NET provide a more direct and intuitive way to access these elements without the need for additional calculations.

Rust's BTreeSet provides a range() method for creating a sub-range view of the set, as well as iter() for iterating over the elements and split_off() for splitting the set into two. While these methods offer flexibility in working with sorted sets, they do not provide the same level of direct access to nearest elements as the proposed methods for .NET. The proposed methods offer a more specialized and efficient solution for this common use case.

This comparison clearly shows that many other languages and libraries offer similar functionality for finding nearest elements in sorted collections. The addition of GetLowerThan, GetLowerThanEqualTo, GetHigherThanEqualTo, and GetHigherThan to .NET's SortedSet<T> class would bring it in line with these industry standards, providing .NET developers with a more complete and efficient toolset for working with sorted data.

Benefits

The introduction of the proposed API methods offers significant benefits in terms of performance improvement and code simplification. These benefits are particularly pronounced in applications where frequent nearest element lookups are required. By providing a more efficient and direct way to access these elements, the new methods can lead to substantial performance gains and a reduction in code complexity. These improvements translate to faster execution times, reduced resource consumption, and more maintainable codebases.

Performance Improvement and Simplified Code are key advantages of the proposed API. The new methods are designed to operate in O(log N) time complexity, which is a significant improvement over the O(N) time complexity of manual iteration or using GetViewBetween. This logarithmic time complexity ensures that the performance of nearest element lookups remains efficient even for large sets. The performance gains are particularly noticeable in applications dealing with large datasets or real-time systems where quick responses are critical.

In addition to performance improvements, the new methods simplify the code required for nearest element lookups. Currently, developers often need to write complex and verbose code to achieve the same functionality. This code typically involves manual iteration, conditional checks, and potentially the use of LINQ queries. The proposed methods encapsulate this logic into a single, easy-to-use API call, reducing the amount of code developers need to write and maintain. This simplification not only makes the code more readable but also reduces the risk of errors and improves overall code quality.

These operations are common in various applications and industries, including:

• Scheduling and calendar systems: In scheduling applications, finding the next upcoming event or the previous completed event often requires nearest element lookups. The proposed methods can efficiently locate these events in a sorted set of time points.
• Time-series data analysis: Time-series data analysis involves analyzing data points collected over time. Finding data points within a specific time range or identifying the nearest data points to a given timestamp are common operations that can benefit from the new methods.
• Range-based caching: Caching systems often use sorted sets to manage cached items based on their expiration times. The proposed methods can efficiently identify items that are about to expire or have already expired, allowing the cache to be updated and maintained effectively.
• Memory allocation and interval trees: Memory allocation algorithms and interval trees rely on efficient nearest element lookups to manage memory blocks and intervals. The new methods can improve the performance of these algorithms by providing a fast and direct way to find the nearest available memory blocks or intervals.
• Game development (e.g., spatial partitioning): In game development, spatial partitioning techniques are used to divide the game world into smaller regions for efficient object management. Nearest element lookups are essential for collision detection, proximity queries, and other spatial operations. The new methods can enhance the performance of these operations, leading to smoother gameplay and more responsive game environments.

The benefits of the proposed API extend beyond these specific examples. Any application that uses sorted sets and requires frequent nearest element lookups can benefit from the performance improvements and code simplification offered by the new methods. The addition of these methods to the SortedSet<T> class would make it a more versatile and powerful tool for .NET developers, enabling them to build more efficient and maintainable applications.

API Proposal

This section details the proposed API for the new methods to be added to the SortedSet<T> class. The API is designed to be intuitive and consistent with existing .NET conventions, making it easy for developers to adopt and use. The proposal includes the method signatures, descriptions, and expected behavior, providing a clear and comprehensive overview of the new functionality. This detailed specification ensures that the API is well-defined and meets the needs of developers working with sorted sets.

namespace System.Collections.Generic
{
    public class SortedSet<T>
    {
        /// <summary>
        /// Returns the greatest element strictly less than the specified item
        /// Throws InvalidOperationException if no such element exists
        /// </summary>
        public T GetLowerThan(T item);

        /// <summary>
        /// Returns the greatest element less than or equal to the specified item
        /// Throws InvalidOperationException if no such element exists
        /// </summary>
        public T GetLowerThanEqualTo(T item);

        /// <summary>
        /// Returns the smallest element greater than or equal to the specified item
        /// Throws InvalidOperationException if no such element exists
        /// </summary>
        public T GetHigherThanEqualTo(T item);

        /// <summary>
        /// Returns the smallest element strictly greater than the specified item
        /// Throws InvalidOperationException if no such element exists
        /// </summary>
        public T GetHigherThan(T item);
    }
}

The proposed API includes four new methods that extend the functionality of the SortedSet<T> class. Each method is designed to find a specific element relative to a given value, providing developers with a comprehensive set of tools for nearest element lookups.

• GetLowerThan(T item): This method returns the greatest element in the set that is strictly less than the specified item. If no such element exists, the method throws an InvalidOperationException. This method is useful for finding the element immediately preceding a given value in the sorted set.
• GetLowerThanEqualTo(T item): This method returns the greatest element in the set that is less than or equal to the specified item. If no such element exists, the method throws an InvalidOperationException. This method is useful for finding the element that is either equal to or immediately precedes a given value in the sorted set.
• GetHigherThanEqualTo(T item): This method returns the smallest element in the set that is greater than or equal to the specified item. If no such element exists, the method throws an InvalidOperationException. This method is useful for finding the element that is either equal to or immediately follows a given value in the sorted set.
• GetHigherThan(T item): This method returns the smallest element in the set that is strictly greater than the specified item. If no such element exists, the method throws an InvalidOperationException. This method is useful for finding the element immediately following a given value in the sorted set.

The methods are designed to throw an InvalidOperationException if no suitable element is found. This behavior is consistent with other .NET collection methods that throw exceptions when an operation cannot be completed due to the absence of a matching element. This ensures that developers are notified when a lookup fails, allowing them to handle the situation appropriately. The use of exceptions also avoids the need for nullable return types or other mechanisms for indicating failure, keeping the API clean and straightforward.

The proposed API is designed to be consistent with existing .NET conventions and naming patterns. The method names clearly indicate their purpose, making the API easy to understand and use. The methods are also designed to be efficient, leveraging the sorted nature of the SortedSet<T> class to provide O(log N) performance for nearest element lookups. This efficiency is crucial for applications that require frequent nearest element lookups, ensuring that performance remains optimal even for large sets.

API Usage

To illustrate how the proposed API methods can be used in practice, this section provides several examples of common scenarios. These examples demonstrate the versatility and ease of use of the new methods, highlighting their benefits in various use cases. By showcasing practical applications of the API, this section helps developers understand how to integrate the new methods into their existing code and leverage their capabilities.

SortedSet<int> set = [10, 20, 30, 40];

Method	Call	Expected Output
GetLowerThan	set.GetLowerThan(25)	20
GetLowerThanEqualTo	set.GetLowerThanEqualTo(30)	30
GetHigherThanEqualTo	set.GetHigherThanEqualTo(25)	30
GetHigherThan	set.GetHigherThan(30)	40

These examples demonstrate how the proposed methods can be used to find the nearest elements in a sorted set. Each example showcases a different method and its expected output, providing a clear understanding of their functionality.

• set.GetLowerThan(25): This call returns 20, which is the greatest element in the set that is strictly less than 25. This example demonstrates how to find the element immediately preceding a given value in the sorted set.
• set.GetLowerThanEqualTo(30): This call returns 30, which is the greatest element in the set that is less than or equal to 30. This example demonstrates how to find the element that is either equal to or immediately precedes a given value in the sorted set.
• set.GetHigherThanEqualTo(25): This call returns 30, which is the smallest element in the set that is greater than or equal to 25. This example demonstrates how to find the element that is either equal to or immediately follows a given value in the sorted set.
• set.GetHigherThan(30): This call returns 40, which is the smallest element in the set that is strictly greater than 30. This example demonstrates how to find the element immediately following a given value in the sorted set.

These examples illustrate the simplicity and efficiency of the proposed API methods. By providing direct access to the nearest elements, these methods eliminate the need for manual iteration or complex logic, making it easier for developers to work with sorted sets. The clear and concise nature of the API ensures that developers can quickly understand and use the methods, reducing the time and effort required for nearest element lookups.

In addition to these basic examples, the proposed methods can be used in a variety of more complex scenarios. For instance, they can be used in scheduling applications to find the next upcoming event or the previous completed event. They can also be used in time-series data analysis to find data points within a specific time range or identify the nearest data points to a given timestamp. The versatility of the methods makes them a valuable addition to the SortedSet<T> class, enabling developers to build more efficient and maintainable applications.

Alternative Designs

In considering the proposed API, alternative designs were evaluated to ensure the best possible solution for finding nearest elements in a SortedSet<T>. This section discusses the alternatives considered and the rationale for choosing the proposed design. By examining these alternatives, we can better understand the strengths and weaknesses of the chosen API and its advantages over other approaches.

NA

• Manual iteration using GetViewBetween() or Reverse(): inefficient and verbose
• Third-party libraries: adds dependencies and lacks standardization

One alternative design involves using manual iteration with the existing GetViewBetween() method or the Reverse() method. However, this approach is inefficient and verbose. Manual iteration requires developers to write complex code to traverse the set and compare elements, which can be error-prone and time-consuming. The GetViewBetween() method, while useful for extracting a range of elements, has a time complexity of O(N), making it less efficient for single element lookups. Using Reverse() to iterate in reverse order can also be inefficient, especially for large sets. These manual approaches lack the performance and simplicity of the proposed methods.

Another alternative is to rely on third-party libraries that provide similar functionality. While these libraries may offer nearest element lookup methods, they add dependencies to the project and lack standardization. Using third-party libraries can increase the complexity of the project, making it harder to maintain and deploy. Additionally, different libraries may have different APIs and behaviors, making it difficult to switch between them or integrate them seamlessly. The lack of standardization can also lead to inconsistencies across different projects and teams. The proposed API, on the other hand, provides a standardized and built-in solution that avoids these issues.

The proposed API offers several advantages over these alternatives. It provides a direct and efficient way to find nearest elements in O(log N) time complexity, leveraging the sorted nature of the SortedSet<T> class. The methods are easy to use and understand, reducing the amount of code developers need to write and maintain. The built-in nature of the API ensures consistency and avoids the need for external dependencies. These advantages make the proposed API the preferred solution for nearest element lookups in SortedSet<T>.

Risks

This section outlines the potential risks associated with the proposed API and considerations for mitigating these risks. Identifying and addressing these risks is crucial for ensuring the successful implementation and adoption of the new methods. By carefully evaluating the potential challenges, we can develop strategies to minimize their impact and ensure that the API meets the needs of developers effectively.

• Need to add check other data structures where new API may also applicable like ImmutableSortedSet<T>, SortedDictionary<T, U>
• Do we need Tryxxx methods?

One potential risk is the need to consider other data structures where the new API may also be applicable. For example, ImmutableSortedSet<T> and SortedDictionary<T, U> are other sorted collection types in .NET that may benefit from similar nearest element lookup methods. Failing to consider these data structures could lead to inconsistencies in the .NET API and limit the usefulness of the new methods. To mitigate this risk, it is important to review these other data structures and determine whether similar methods should be added to them as well. This comprehensive approach will ensure that the .NET API remains consistent and provides a complete set of tools for working with sorted data.

Another risk is the question of whether to provide Tryxxx methods in addition to the proposed methods. The proposed methods throw an InvalidOperationException if no suitable element is found. While this behavior is consistent with other .NET collection methods, it may not be ideal for all scenarios. Tryxxx methods, such as TryGetLowerThan, would provide a non-throwing alternative that returns a boolean value indicating success or failure, along with an output parameter for the result. This approach allows developers to handle the case where no suitable element is found without relying on exceptions, which can be more efficient in some situations. To address this risk, it is important to carefully consider the trade-offs between throwing exceptions and providing Tryxxx methods, taking into account the common use cases and performance implications.

In conclusion, while the proposed API offers significant benefits, it is important to carefully consider these risks and develop strategies to mitigate them. By addressing these risks proactively, we can ensure that the new methods are a valuable addition to the .NET framework and meet the needs of developers effectively.