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

Go to the documentation of this file.

#ifndef DTREES_H
#define DTREES_H

#include "stdinc.h"
#include "Adt.h"
#include "Util.h"
#include "PathSet.h"

namespace grafalgo {

typedef int tree;
typedef PathSet::PathCostPair NodeCostPair;

class Dtrees : public Adt {
public:         Dtrees(int=100);
                ~Dtrees();

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

        index   findroot(index);        
        NodeCostPair findcost(path);
        void    addcost(index,cost);
        void    link(tree,index);
        void    cut(index);

        cost    nodeCost(index) const;
        index   parent(index) const;

        string& path2string(path,string&) const;
        string& toString(string&) const;
private:
        index   *parentOf;              
        index   *successor;             
        PathSet *ps;                    
        
        struct PathNodePair {
                path p; index i;
                PathNodePair(path pp, index ii) : p(pp), i(ii) {}
        };
        path    expose(index);
        PathNodePair splice(PathNodePair);

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

inline index Dtrees::parent(index i) const { return parentOf[i]; }

inline cost Dtrees::nodeCost(index i) const { return ps->nodeCost(i); }

} // ends namespace

#endif