rangeModule_smartpointer.cc

rangeModule_smartpointer.cc

class STNode{
public:
    long l, r, m;
    bool tracked;
    shared_ptr<STNode> lnode, rnode;
    STNode(int ll, int rr):l(ll), r(rr), lnode(nullptr), rnode(nullptr){
        m = (l+r)/2;
        tracked = false;
    }
    
    void remove(shared_ptr<STNode> & node){
        if(!node) {node = nullptr; return;}
        remove(node->lnode);
        remove(node->rnode);        
        node = nullptr;
    }
    
    void addTrack(int left, int right){
        if(left >= r || right <= l) return;
        if(left <= l && right >= r) {
            remove(lnode); 
            remove(rnode); 
            tracked = true;
            return;
        }
        
        godown();
        if(left <= m) lnode->addTrack(left, right);
        if(right>= m) rnode->addTrack(left, right);
        maintain();
    }
    
    void maintain(){
        tracked = lnode->tracked && rnode->tracked;
    }
    
    void godown(){
        if(!lnode || !rnode) {
            lnode = make_shared<STNode>(l, m);
            lnode->tracked = tracked;
            rnode = make_shared<STNode>(m, r);
            rnode->tracked = tracked;
        }
    }
    
    bool query(int left, int right){
        if(left <= l && r <= right) {
            return tracked;
        }
        if(left >= r || right <= l) return true; // out of range
             
        if(!lnode && !rnode) return tracked;
        bool res = true;
        if(left <= m && lnode) res = res && lnode->query(left, right);
        if(right>= m && rnode) res = res && rnode->query(left, right);
        return res;        
    }
    
    void removeTrack(int left, int right){
        if(left >= r || right <= l) return;
        if(left <= l && r <= right) {
            remove(lnode); 
            remove(rnode); 
            tracked = false; 
            return;
        }
        
        godown();
        if(left <= m) lnode->removeTrack(left, right); 
        if(right >= m) rnode->removeTrack(left, right);        
        maintain();
    }
        
};

class RangeModule {
public: 
    shared_ptr<STNode> root;
    RangeModule() {
        root = make_shared<STNode>(1, 1000000000);        // share_ptr
    }
    
    void addRange(int left, int right) {
        root->addTrack(left, right);
    }
    
    bool queryRange(int left, int right) {
        return root->query(left, right);
    }
    
    void removeRange(int left, int right) {
        root->removeTrack(left, right);
    }
};

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * bool param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */