/Users/jst/src/grafalgo/cpp/include/DkBstSet.h

Go to the documentation of this file.

#ifndef DKBSTSET_H
#define DKBSTSET_H

#include "SaBstSet.h"

namespace grafalgo {

class DkBstSet : public SaBstSet {
public:         DkBstSet(int);
                ~DkBstSet();
        static  const int MAX2 = Util::BIGINT32-1;  

        // common methods
        void    clear();
        void    resize(int);
        void    expand(int);
        void    copyFrom(const DkBstSet&);

        // access methods
        keytyp  key1(index);               
        keytyp  key2(index);              
        index   first(bst) const;        
        index   next(index) const;      
        index   access(keytyp,bst);
        keytyp  min2(bst);              

        // modifiers
        void    setkey(index,keytyp,keytyp); 
        void    change2(keytyp,bst); 
        bst     insert(index,bst);
        bst     remove(index,bst);        
        bst     join(bst,index,bst);     
        BstPair split(index,bst);       

private:
        keytyp  *dmin;                  // delta min value for key 2
        keytyp  *dkey;                  // delta key value for key 2
        void    virtual rotate(index);

        virtual string& node2string(index, string&) const;

        void    makeSpace(int);
        void    freeSpace();
};

void inline DkBstSet::setkey(index i, keytyp k1, keytyp k2) {
        assert(0 <= i && i <= n() && k2 <= MAX2);
        assert(node[i].p == 0 && node[i].left == 0 && node[i].right == 0);
        node[i].kee = k1; dmin[i] = k2; dkey[i] = 0;
}

keytyp inline DkBstSet::key1(index i) {
        assert(1 <= i && i <= n());
        return node[i].kee;
}

keytyp inline DkBstSet::min2(bst s) {
        assert(1 <= s && s <= n());
        return dmin[s];
}

void inline DkBstSet::change2(keytyp diff, bst s) {
        assert(1 <= s && s <= n());
        dmin[s] += diff;
}

} // ends namespace

#endif