C#: an ordered index with SortedSet

Answer range, minimum, maximum, and nearest-value queries on sorted keys.

using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    var ages = new SortedSet<int> { 31, 24, 45, 29 };

    Console.WriteLine("min " + ages.Min + " max " + ages.Max);
    Console.WriteLine("range 25..40: " + string.Join(" ", ages.GetViewBetween(25, 40)));

    int floor = ages.GetViewBetween(int.MinValue, 30).Max;
    int ceiling = ages.GetViewBetween(30, int.MaxValue).Min;
    Console.WriteLine("floor(30)=" + floor + " ceiling(30)=" + ceiling);
  }
}

Output

min 24 max 45
range 25..40: 29 31
floor(30)=29 ceiling(30)=31

Explanation

A database index that keeps keys in order can answer range queries and nearest-value queries without scanning every row. SortedSet<T> is a collection of unique values stored in a balanced tree, so adding, removing, and finding take O(log n).

Min and Max return the smallest and largest elements. GetViewBetween returns a live view of the elements inside a range, without copying them. The nearest value at or below a key is the maximum of the view from the smallest possible value up to the key, and the nearest at or above is the minimum of the view from the key to the largest possible value.

Explore the dry run

Guided walkthroughReady

1using System;

2using System.Collections.Generic;

4class Program {

5 static void Main() {

6 var ages = new SortedSet<int> { 31, 24, 45, 29 };

8 Console.WriteLine("min " + ages.Min + " max " + ages.Max);

9 Console.WriteLine("range 25..40: " + string.Join(" ", ages.GetViewBetween(25, 40)));

11 int floor = ages.GetViewBetween(int.MinValue, 30).Max;

12 int ceiling = ages.GetViewBetween(30, int.MaxValue).Min;

13 Console.WriteLine("floor(30)=" + floor + " ceiling(30)=" + ceiling);

14 }

15}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Values are kept sorted as they are added: 24, 29, 31, 45.	`ages = {24, 29, 31, 45}`	—
The ends of the sorted order.	`ages = {24, 29, 31, 45}`	min 24 max 45
A view over the keys from 25 through 40.	`ages = {24, 29, 31, 45}`	min 24 max 45 range 25..40: 29 31
The largest key at or below 30 is 29; the smallest at or above is 31.	`ages = {24, 29, 31, 45}`	min 24 max 45 range 25..40: 29 31 floor(30)=29 ceiling(30)=31

Cost and common mistakes

Add, Remove, and Contains are O(log n); a range view is created in O(log n) and enumerated in O(k).

Calling Max on an empty view throws or returns the default value. Check Count first.
A SortedSet stores unique values only. Use SortedDictionary or SortedList to attach a row to each key.

Try it yourself

How would you list the ages greater than 30?

Reveal answer and reasoning

Use ages.GetViewBetween(31, int.MaxValue); it contains 31 and 45.

C#: an ordered index with SortedSet

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading