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

Go to the documentation of this file.

#ifndef BSTSET_H
#define BSTSET_H

#include "Adt.h"
#include "Util.h"

namespace grafalgo {

typedef int bst;                // tree in collection
typedef uint64_t keytyp;

class BstSet : public Adt {
public:
                BstSet(int);
                ~BstSet();

        // pair of bsts, returned by split
        struct BstPair {
                bst t1, t2;
                BstPair(bst tt1, bst tt2) : t1(tt1), t2(tt2) {}
        };

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

        keytyp  key(index) const;       
        bst     find(index) const;
        index   first(bst) const;       
        index   last(bst) const;        
        index   suc(index) const;       
        index   pred(index) const;      
        index   access(keytyp,bst&) const;

        void    setkey(index,keytyp);
        bool    insert(index,bst&);     
        void    remove(index,bst&);
        bst     join(bst,index,bst);    
        BstSet::BstPair split(index,bst);       

        string& bst2string(bst, string&) const;
        string& toString(string&) const;
protected:
        struct BstNode {
        index   left, right, p;         // left child, right child, parent
        keytyp  kee;                    // key values
        };
        BstNode *node;

        void virtual swap(index,index);
        void virtual rotate(index);     
        index   sibling(index, index);
        index   remove(index);  

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

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

inline keytyp BstSet::key(index i) const { return node[i].kee; }

inline void BstSet::setkey(index i, keytyp k) {
        assert(node[i].left == 0 && node[i].right == 0 && node[i].p == 0);
        node[i].kee = k;
}

index inline BstSet:: sibling(index x, index px) {
        return (x == node[px].left ? node[px].right : node[px].left);
}

} // ends namespace

#endif