Feature Proposal: Introduce Higher Level APIs like ceil / floor

[Asayu123]

trafficstars

Motivation

• Other programming languages support high-level APIs like

  • Get next smaller value (or item)
  • Get floor value (or item)
  • Get ceil value (or item)
  • Get next larger value (or item) In Tree data structure.

• We can achieve this by using bisect method + index range check, but providing higher-level API would help users to avoid writing wrapper code every time.

API Definition

SortedList

• def next_smaller(self, value: object) -> Optional[object]
• def floor (self, value: object) -> Optional[object]
• def ceil (self, value: object) -> Optional[object]
• def next_greater(self, value: object) -> Optional[object]

SortedSet

• def next_smaller(self, value: Hashable) -> Optional[object]
• def floor (self, value: Hashable) -> Optional[object]
• def ceil (self, value: Hashable) -> Optional[object]
• def next_greater(self, value: Hashable) -> Optional[object]

SortedDict

• def next_smaller_item(self, key: Hashable) -> tuple[Optional[Hashable], Optional[object]]
• def floor_item (self, key: Hashable) -> tuple[Optional[Hashable], Optional[object]]
• def ceil_item (self, key: Hashable) -> tuple[Optional[Hashable], Optional[object]]
• def next_greater_item(self, key: Hashable) -> tuple[Optional[Hashable], Optional[object]]

Prototype Code (Implementation / Tests)

• https://github.com/grantjenks/python-sortedcontainers/pull/206

P.S

• If this idea sounds good to you, I'd love to discuss API design (including naming), testing strategy, etc.
• Thank you so much for your attention and participation.

[grantjenks]

There’s already an existing API for these operations. See https://grantjenks.com/docs/sortedcontainers/sortedlist.html#sortedcontainers.SortedList.irange The advantage of irange is that it does not require the positional index to be built. The irange method is available on all provided data types.

From a design point of view, I’d rather keep a smaller surface than larger one, especially as the functionality here is rather easily implemented using existing APIs.

[Asayu123]

Actually, I have two concerns related to the above API (irange) since

1. It will introduce additional computational overheads, especially for use cases that pick only one value.
2. It will introduce additional complexity to driver codes. Using bisect methods would be much simpler while it still requires wrappers.

I feel we can keep opening this issue and see how other people react to this discussion. (Also, I feel if we do not receive any posts for several months, we could close this Issue since it indicates no needs for these proposed APIs)

[grantjenks]

One thought looking over the issue today: would we also need to add key variants of these functions like next_key_smaller, floor_key, ceil_key, and next_key_greater similar to how the bisect_key_left and bisect_key_right functions parallel bisect_left and bisect_right?