LC-715

RangeModule.java

class RangeModule {

    static class Range {
            private static final boolean DEBUG = false;
            private static final boolean BIASED_SPLIT = true;
            private static final int MID_NON_MARKED = -1;
            private static final int MID_ALL_MARKED = -2;

            int startValue;
            int endValue;
            // we use this index to mark 3 status: non-marked, all-marked, splitted
            int midValue;
            Range leftChild;
            Range rightChild;

            Range(int startValue, int endValue) {
                this.startValue = startValue;
                this.endValue = endValue;
                this.leftChild = null;
                this.rightChild = null;
                this.midValue = MID_NON_MARKED;
            }

            private void markRangeOp(int leftValue, int rightValue, int target_mid_status, int split_mid_status) {
                if (DEBUG) {
                    System.out.println(String.format("marking op: from %d to %d (mid:%d) for(%d:%d)", this.startValue,
                            this.endValue, this.midValue, leftValue, rightValue));
                }
                if (this.midValue == target_mid_status) {
                    return;
                }
                if (this.startValue == leftValue && this.endValue == rightValue) {
                    if (DEBUG) {
                        System.out.println(
                                String.format("marked from %d to %d as %d", leftValue, rightValue, target_mid_status));
                    }
                    // we have a full marked range
                    this.midValue = target_mid_status;
                    this.leftChild = null;
                    this.rightChild = null;
                    return;
                }
                if (this.midValue == split_mid_status) {
                    // whenever we are marking a non marked range, we need to create the mid and
                    // left/right child
                    if (BIASED_SPLIT) {
                        int leftDist = leftValue - this.startValue;
                        int rightDist = this.endValue - rightValue;
                        if (leftDist < rightDist) {
                            // split on right value
                            this.midValue = rightValue;
                        } else {
                            // split on left value
                            this.midValue = leftValue - 1;
                        }
                    } else {
                        this.midValue = (this.startValue + this.endValue) / 2;
                    }
                    
                    this.leftChild = new Range(this.startValue, this.midValue);
                    this.leftChild.midValue = split_mid_status;
                    if (this.midValue + 1 <= this.endValue) {
                        this.rightChild = new Range(this.midValue + 1, this.endValue);
                        this.rightChild.midValue = split_mid_status;
                    }
                    if (DEBUG) {
                        System.out.println(String.format("split from %d to %d at %d", this.startValue, this.endValue,
                                this.midValue));
                    }
                }

                if (rightValue <= this.midValue) {
                    // no split
                    this.leftChild.markRangeOp(leftValue, rightValue, target_mid_status, split_mid_status);
                } else if (leftValue > this.midValue) {
                    // no split
                    this.rightChild.markRangeOp(leftValue, rightValue, target_mid_status, split_mid_status);
                } else {
                    this.leftChild.markRangeOp(leftValue, this.midValue, target_mid_status, split_mid_status);
                    this.rightChild.markRangeOp(this.midValue + 1, rightValue, target_mid_status, split_mid_status);
                }

                if (this.leftChild.midValue == target_mid_status && this.rightChild.midValue == target_mid_status) {
                    if (DEBUG) {
                        System.out.println(String.format("marked(2) from %d to %d as %d", leftValue, rightValue,
                                target_mid_status));
                    }
                    // we have a full marked range
                    this.midValue = target_mid_status;
                    this.leftChild = null;
                    this.rightChild = null;
                }
            }

            public void markRange(int leftValue, int rightValue) {
                this.markRangeOp(leftValue, rightValue, MID_ALL_MARKED, MID_NON_MARKED);
            }

            public void unMarkRange(int leftValue, int rightValue) {
                this.markRangeOp(leftValue, rightValue, MID_NON_MARKED, MID_ALL_MARKED);
            }

            public boolean isMarked(int leftValue, int rightValue) {
                if (this.midValue == MID_ALL_MARKED) {
                    return true;
                }

                if (this.midValue == MID_NON_MARKED) {
                    return false;
                }

                if (rightValue <= this.midValue) {
                    // no split
                    return this.leftChild.isMarked(leftValue, rightValue);
                } else if (leftValue > this.midValue) {
                    // no split
                    return this.rightChild.isMarked(leftValue, rightValue);
                } else {
                    return this.leftChild.isMarked(leftValue, this.midValue)
                            && this.rightChild.isMarked(this.midValue + 1, rightValue);
                }

            }

    }

    private Range root = null;

    public RangeModule() {
        root = new Range(1, (int)Math.pow(10, 9));
    }
    
    public void addRange(int left, int right) {
        this.root.markRange(left, right-1);
    }
    

    public boolean queryRange(int left, int right) {
        return this.root.isMarked(left, right-1);
    }
    
    public void removeRange(int left, int right) {
        this.root.unMarkRange(left, right-1);
    }
}