peraltaJacob's blog

Custom Interval map implementation
By peraltaJacob, history, 3 years ago, In English

I want to develop a custom Interval map something like this.
Initially all keys in the map will point to value k. Now we will insert ranges in the map let's suppose :- (1,4)-> 2 , (3,5)-> 6 Then we can access values via keys provided in the map. The main issue is we have to implement all of this in o(log(n)) complexity all for insertion, deletion, retrieval.

PS: Map's key type and value type can be anything(key can be decimal, integer string etc).Even ranges can be decimal.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Did you mean value can be anything (rather than key can be anything)? Asking this since having intervals of strings doesn't make sense to me.

For simple intervals, you can maintain a map from intervals to values, and use lower_bound and similar things (and incrementing iterators) to perform such operations. The overall time complexity becomes amortized $$$O(\log n)$$$ where $$$n$$$ is the number of intervals.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Keys can be numeric and decimal. We can't use a simple map of intervals because we have to merge intervals too. For eg:- (1,5)-> "10" (2,7)-> "12" (1,3)-> "15"
    Then we have to merge and break intervals, hope you get the idea.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      What I don't understand are the semantics of your intervals. From what I figured out, they can refer to two things:

      1. Intervals don't mean anything, they're just keys.
      2. Intervals store the common value assigned to all elements in that interval.

      Clearly the first one is uninteresting (and there are no obvious semantics you would follow to merge/break intervals), so I'm assuming that it's the second case.

      I'll explain my previous comment in more detail below.

      If initially everything points to some value $$$k$$$, if you think of the real line as the interval $$$(-\infty, \infty)$$$, then the map initially has just one interval $$$(-\infty, \infty)$$$ which has value $$$k$$$.

      The map we will store will have disjoint intervals at all times (and they will form a partition of the real line). If we have an interval $$$[a, b)$$$, by going down the BBST (i.e., doing something like lower_bound on the map), we can find the first interval that intersects with this interval, and by incrementing the iterator till you get the last interval that intersects with this interval, you get a contiguous range of intervals that you need to remove or modify (to fix the property that we maintain disjoint intervals, that is).

      If you need to delete an interval, it is equivalent to setting the value of that interval to the original value in the map (I'm assuming these semantics since the old semantics aren't clear enough). If you want to revert back to some old value, I have a feeling that you could do that with some persistent BBST but I don't think that will cut it, and you might need to use confluently persistent BBSTs instead. So yeah, it depends on what behaviour you want.

      To retrieve a value, you can just do a similar thing to check which range in the BBST your value lies.

      If you removed $$$k$$$ intervals in this whole process, the total cost would be $$$O(k \log n + \log n)$$$. The change in the number of intervals is at most $$$2 - k$$$ and at least $$$-k$$$. So the overall complexity is no more than $$$O(q \log q)$$$.

      → Reply