# 715. Range Module

A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as **half-open intervals** and query about them.

A **half-open interval** `[left, right)` denotes all the real numbers `x` where `left <= x < right`.

Implement the `RangeModule` class:

* `RangeModule()` Initializes the object of the data structure.
* `void addRange(int left, int right)` Adds the **half-open interval** `[left, right)`, tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval `[left, right)` that are not already tracked.
* `boolean queryRange(int left, int right)` Returns `true` if every real number in the interval `[left, right)` is currently being tracked, and `false` otherwise.
* `void removeRange(int left, int right)` Stops tracking every real number currently being tracked in the **half-open interval** `[left, right)`.

**Example 1:**

```
Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]

Explanation
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); // return True,(Every number in [10, 14) is being tracked)
rangeModule.queryRange(13, 15); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)
```

**Constraints:**

* `1 <= left < right <= 109`
* At most `104` calls will be made to `addRange`, `queryRange`, and `removeRange`.

## Solution

When we add a new range\[left, right), there are only 3 cases we should consider of.

We assume the previous range is "***start range***" (floorKey of left), and the floorKey of right is called "***end range"***.

We want :&#x20;

1. Enlarge the ***start range***, if ***start range*** will overlap with the new-added range
2. Enlarge the ***end range***, if ***end range*** will overalap with the new-added range

-> When the new range is added, we want to **remove any sub-range among the new range**.

\*\*\* We need to make the change not impact the correctness.

So get the value first and update the map at the last step;

```java

    TreeMap<Integer, Integer> map;
    public RangeModule() {
        map = new TreeMap<>();
    }
    
    public void addRange(int left, int right) {
        if(right <= left) return;
        Integer prevStart = map.floorKey(left);
        Integer nextStart = map.floorKey(right);
        if(prevStart != null && map.get(prevStart) >= left){
            left = prevStart;
        }
        if(nextStart != null && map.get(nextStart) > right){
            right = map.get(nextStart);
        }
        map.put(left, right);
        
        map.subMap(left, false, right, true).clear();
        
    }
    
    public boolean queryRange(int left, int right) {
        Integer prevStart = map.floorKey(left);
        if(prevStart == null) return false;
        return map.get(prevStart) >= right;
    }
    
    public void removeRange(int left, int right) {
        Integer prevStart = map.floorKey(left);
        Integer prevEnd = (prevStart == null) ? -1 : map.get(prevStart);
        Integer nextStart = map.floorKey(right);
        Integer nextEnd = (nextStart == null) ? -1 : map.get(nextStart);
        if(prevEnd > left){
            map.put(prevStart, left);
        }
        if(nextEnd > right){
            map.put(right, nextEnd);
        }
        map.subMap(left, true, right, false).clear();
    }
```
