Does SortedSet support ceiling/floor method or similiar?

[ywchang]

Hi,

I was wondering how SortedSet can help achieve the same functionality that Java TreeSet implementing ceiling/floor method? Let's take ceiling for example, it accepts a object as parameter, and tries to find if the current set has a matching element first. If the element exists in set, then return; otherwise, return the next element in the set that is larger than this parameter. If it exists return, otherwise return null.

Below are some test cases.

[1,2,3,4,5]
ceiling(3) => 3
[1,2,3,5]
ceiling(4) => 5
[1,2,3,4,5]
ceiling(6) => null

In Java, since it's using a red-black tree, it can utilise the balancing property to find out this ceiling/floor value very efficiently. However, in Ruby I've no idea how to do it effectively. Would appreciate if you can share any thoughts/comments on this. Many thanks!

[jaynetics]

@ywchang

edit: updated my answer because I misread the question the first time.

you are probably looking for the RBTree methods #lower_bound, #upper_bound. You could use RBTree directly, or access it in a hacky way:

set = SortedSet.new([1, 2, 3])
tree = set.instance_variable_get(:@hash) # => #<RBTree>
tree.lower_bound(1) # => [1, true]
tree.upper_bound(3) # => [3, true]

of course, these methods would ideally be exposed by sorted_set, just as rbtrees efficient #first and #last methods should be exposed through overrides of #min, #max and #minmax, which currently fall back to the inefficient implementation from the included Enumerable module.