.NET equivalent of Java's TreeSet.floor & TreeSet.ceiling

user_2376997 0
Viewed 1417

As an example, there's a Binary Search Tree which holds a range of values. Before adding a new value, I need to check if it already contains it's 'almost duplicate'. I have Java solution which simply performs floor and ceiling and further condition to do the job.

JAVA: Given a TreeSet, floor() returns the greatest element in this set less than or equal to the given element; ceiling() returns the least element in this set greater than or equal to the given element

TreeSet<Long> set = new TreeSet<>();

long l = (long)1;  // anything
Long floor = set.floor(l);
Long ceil = set.ceiling(l);

C#: Closest data structure seems to be SortedSet<>. Could anyone advise the best way to get floor and ceil results for an input value?

SortedSet<long> set = new SortedSet<long>();
binary-search-tree .net c#
2 Answers

The above, as mentioned, is not the answer since this is a tree we expect logarithmic times. Java's floor and ceiling methods are logarithmic. GetViewBetween is logarigmic and so are Max and Min, so:

floor for SortedSet<long>: sortedSet.GetViewBetween(long.MinValue, num).Max

ceiling for SortedSet<long>: sortedSet.GetViewBetween(num, long.MaxValue).Min

user_74484270

You can use something like this. In Linq there is LastOrDefault method:

var floor = sortedSet.LastOrDefault(i => i < num);
// num is the number whose floor is to be calculated
if (! (floor < sortedSet.ElementAt(0)))
{
  // we have a floor
}
else
 // nothing is smaller in the set
{
}
user_25491100
Related