Data structure to represent mapping of intervals

user_5546046 0
Viewed 73

Here is a function which can deduce the status of a person given their age

def getStatus(age: Int): String = {
  age match {
    case age if 0 until 2 contains age => "infant"
    case age if 2 until 10 contains age => "child"
    case age if 10 until 18 contains age => "teen"
    case _ => "adult"
  }
}

Let's say the boundaries can change. We can decide a person can be considered as an infant until 3 years old. As they change we do not want the boundaries to be hard coded and they will be stored externally.

What is a data-structure that can store mappings based on an interval?

Something like

val intervalMap = IntervalMap(
  (0, 2) -> "infant",
  (2, 10) -> "child",
  (10, 18) -> "teen",
  (18, 200 ) -> "adult"
)
intervalMap(1) // "infant"
intervalMap(12) // "teen"

I'm developping in Scala but a language agnostic answer will be much appreciated.

data-structures scala
1 Answers

Easy Answer

There isn't anything in the Scala standard library that does that, but if the number of "categories" is low like in your example, there's no harm in implementing a naive O(N) apply method on your IntervalMap class.

def apply(in: Int) = categories.collectFirst { 
  case ((min, max), value) if in >= min && in < max => value 
}

Guava

Looks like the Guava library has a RangeMap class that seems to fit your use-case.

Fancier DIY Idea

To get a O(log N) lookup characteristic, you could represent your category data as a binary tree:

  • Each node defines a min and max
  • Root node represents the absolute minimum to the absolute maximum, e.g. Int.MinValue to Int.MaxValue
  • Leaf nodes define a value (e.g. "child")
  • Non-leaf nodes define a split value, where the left child's max will be equal to the split, and the right child's min will be equal to the split
  • Find values in the tree by traversing left/right depending on whether your input number (e.g. age) is greater than or less than the current node's split

You'd have to deal with balancing the tree as it gets built... and TBH this is probably how Guava's doing it under the hood (I did not look into the implementation)

user_5748150
Related