0

For key equality lookup, we can use a data type like a hashmap, but is there a data structure for looking up values matching arbitrary ranges?

The Rust code below emulates this using a match expression but I'm looking to not have to hard code the cases in code.

let x = 5;

match x {
    d if d <= 0 => println!("d <= 0"),
    d if 1 < d && d <= 3 => println!("1 < d <= 3"),
    d if 4 < d && d <= 6 => println!("4 < d <= 6"),
    _ => {}
}

(Rust playground)

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
N.Clarke
  • 268
  • 1
  • 6
  • [`BTreeMap`](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html) is similar to `HashMap` but also supports [looking-up for ranges](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html#method.range). – mcarton Jan 07 '19 at 23:13
  • Possible duplicate of [Data structure to build and lookup set of integer ranges](https://stackoverflow.com/questions/4601749/data-structure-to-build-and-lookup-set-of-integer-ranges) – Shepmaster Jan 08 '19 at 00:08
  • See also [What data structure would efficiently store integer ranges?](https://cs.stackexchange.com/questions/13874/what-data-structure-would-efficiently-store-integer-ranges); [O(1) access into an array-like data structure with numerical ranges for keys](https://cs.stackexchange.com/q/49659/39403); [Range tree](https://en.wikipedia.org/wiki/Range_tree) – Shepmaster Jan 08 '19 at 00:09

1 Answers1

1

You could create a list of ranges, with start and end values. Sort that list by start value.

When you get a query, do a binary search on the starting values. When your value is greater than or equal to the starting value, and less than or equal to the ending value, you know you got the right range.

If you have a relatively small total range (say, integers from 1 to 1000), you could pre-fill an array of references to ranges. Say you have the 4 ranges and the possible query values are 0 through 10:

range1: 0, 2
range2: 3, 5
range3: 6, 8
range4: 7, 10

Your array, then, would be [range1, range1, range1, range2, range2, range2, range3, range3, range3, range4, range4, range4, range4].

You could extend that to however large you want it, depending on how much memory you want to spend. That gives you a direct lookup.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351