Is there any built-in support for range queries?

I have a data structure with a few fields, and a date field. I'd like an efficient query into a container of these data structures to return all elements whose date falls within a specific range.

Is there any built-in support in the Swift Standard Library for this? Obviously I can implement something like

let parts = self.parts.filter { inRange.contains($0.start) }

But that's O(n). I'd like to do better, if possible. I can implement any number of interval trees, but I'm hoping there's something already in Swift.

Thanks.

It a little non-trivial since you’re not filtering for data in inRange per se, but filtering for data that has start in inRange.
If the matching data ends up being non-contiguous, there isn’t much way around O(n) way you mentioned.

If you can, however, reformulate the problem to filtering for data with indices in range, most Collection supports O(1) SubSequence.

So it becomes something like this:

let parts = self.parts[indexRange]
// getting all data between
// self.part[indexRange.start] and
// self.part[indexRange.end]
// subjecting to inclusivity of the range itself

If self.parts is Array, local parts will be ArraySlice, which just store the base Array and it’s range of interest.

A few to note here:

  • indexRange is the range of index, not some attribute in data, you’ll need to convert inRange to proper start index and end index of some form
  • Most SubSequence uses the same indices as the base Collection, and skipped any indices out of range, so it doesn’t necessarily start at 0 (this is where the distinction between index and offset starts to appear)
  • These SubSequence generally store the base Collection so if the original data is huge relative to the subdata you’re using, you don’t want to store it for long